1
第 5章 数组
5.1 数组
5.2 动态 数组
5.3 特殊 矩阵 的压缩存储
5.4 稀疏 矩阵 的压缩存储
2
5.1 数组
一、数组的定义
数组：它是 n（ n>1)个相同数据类型的数据元素 a0,a1,a2,…a n-1
构成的占用一块地址连续的内存单元的有限序列。
数组的下标：数组元素的位置。
注意：
(1)C语言的数组定义下标从 0开始。
(2) 数组的处理相比其它复杂的结构要简单。
① 数组中各元素具有 统一的类型 ；
② 数组元素的下标一般具有 固定的上界和下界,即数组一旦被
定义，它的维数和维界就不再改变。
③数组的 基本操作比较简单,除了结构的初始化和销毁之外，
只有存取元素和修改元素值的操作。
(3)一个二维数组可以看作每个数据元素是一个一维数组的一维数
组。 二维数组是两维的，内存单元是一维的，存在向内存存储时
二维数组中数据元素的存储方法问题,C语言采用以行序为主序的
方法存储。
3
问题：数组与线性表的区别与联系
相同之处：
它们都是若干个 相同数据类型 的数据元素 a0,a1,a2,…, an-1
构成的有限序列。
不同之处：
(1)数组要求其元素占用一块 地址连续 的内存单元空间，而
线性表无此要求；
(2)线性表的元素是 逻辑意义上不可再分的元素,而数组中
的每个 元素还可以是一个数组 ；
(3)数组的 操作 主要是向某个下标的数组元素中存放数据和
取某个下标的数组元素，这与线性表的插入和删除操作 不同 。
4
二、数组的实现机制
１,一维数组（ n个元素）中任一元素 ai的内存单元地址
LOC(ai)=LOC(a０ )+i*k (0≤i <n)
２、一个 m行 n列的二维数组
LOC(aij)=LOC(a00)+(i*n+j)*k (0≤i<m,0≤j<n)
注,C语言中数组元素采用行主序的存放方法，即 行优先 顺序 。
a０ 的 内存单元地址 每个元素所需的字节个数
每个元素所需的字节个数a０ 0的 内存单元地址
一个 m× n的二维数组可以
看成是 m行的一维数组，或
者 n列的一维数组。
a0,0 a0,1 … a 0,n-1
a1,0 a1,1 … a 1,n-1
… … … …
am-1,0 am-1,1 … a m-1,n-1
Amn=
5
注：只要知道以下三要素便可随时求出任一元素的地址 （意
义：数组中的任一元素可随机存取）
①开始结点的存放地址（即基地址）；
②维数和每维的上、下界；
③每个数组元素所占用的单元数
例１ 〖 软考题 〗, 一个二维数组 A，行下标的范围是 1到 6，列下标的范围是 0到
7，每个数组元素用相邻的 6个字节存储，存储器按字节编址。那么，这个
数组的体积是 个字节。
答,Volume=m*n*L=(6-1+1)*(7- 0 +1)*6=48*6=288
例２ 设数组 a[０ … 60,０ … 70]的基地址为 2048，每个元素占 2个存储单元，
若以行序为主序顺序存储，则元素 a[32,58]的存储地址
为 。
答,根据行优先公式 LOC(aij)=LOC(a00)+(i*n+j)*k (0≤ i<m,0≤ j<n)
得,LOC(a32,58)=2048+(32*70+58)*2＝ 6644
288
6644
6
三,数组抽象数据类型
数据集合,｛ a0,a1,a2,…a n-1 } 每个数据类型为抽象数据元素类型
操作集合,(1)求 数组元素个数 ArrayLength(D)
(2)存数组元素 Storage(D,i,x)
(3)取数组元素 Get(D,i,x)
7
5.2 动态数组
一、动态数组的设计方法
1、动态数组的概念
动态数组,它是在需要存储单元空间时才给出数组的具体个
数。
C语言提供的支持函数有：
malloc( ),calloc( ),free( )
例：编写一个定义和使用二维 3行 4列动态数组的一个完整程序。
8
#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>
void main(void)
{ int i,j,row=3,col=4,**a;
a=(int **) malloc(row*sizeof(int *))；
for (i=0;i<row;i++)
a[i]=(int *)malloc(col*sizeof(int));
for(i=0;i<row;i++)
{ for(j=0;j<col;j++)
{ a[i][j]=i+j;
printf("%d ",a[i][j]); }
printf(“\n”);}
}
9
例：编写一个使用两维动态数组的函数。
int **Make2DArray(int row,int col)
{ int **a,i;
a=(int **) malloc(row*sizeof(int *))；
for (i=0;i<row;i++)
a[i]=(int *) malloc(col*sizeof(int))；
return a;
}
10
#include <malloc.h>
#include <stdio.h>
#include <stdlib.h> /*函数已经定义，同前 */
void main(void)
{ int i,j,c,row=3,col=4,**a;
a=Make2DArray(row,col);
for(i=0;i<row;i++)
{ for(j=0;j<col;j++)
{ a[i][j]=i+j;
printf(“%d”,a[i][j]); }
printf(“\n”); }
}
11
二、动态数组和静态数组对比
1、从使用方法上来说，动态数组和静态数组除向系统申
请内存空间的方法不同外，数组的使用方法完全相同。
静态数组采用数组定义语句向系统申请内存空间；
动态数组采用函数 malloc( )来向系统申请内存空间。
2、从性能上来说,静态数组 必须确切指定数组元素个数，这样的
指定在程序运行后 不能改变 ； 动态数组 虽然也要确切指定数组
元素个数，但因为这样的指定是在程序运行时通过调用函数实
现的，可以 改变其元素个数 。
12
5.3 特殊矩阵的压缩存储
特殊矩阵,指有许多值相同的元素或有许多零元素、且值相同的元素或零
元素的分布有一定规律的矩阵。
下面我们讨论几种特殊矩阵的压缩存储。
1,n阶对称矩阵
在一个 n阶方阵 A中，若元素满足下述性质：
aij=aji （ 1≦i,j≦n ）
则称 A为 n阶对称矩阵 。如图 5.1是一个 5阶对称矩阵。
1 5 1 3 7 a11
5 0 8 0 0 a21 a 22
1 8 9 2 6 a31 a32 a33
3 0 2 5 1 ………………..
7 0 6 1 3 an1 an2 an3 …a nn
图 5.1 对称矩阵
n阶对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三
角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，
能节约近一半的存储空间。不失一般性，我们按, 行优先 顺序”存储主
对角线（包括对角线）以下的元素。
13
i(i-1)/2+j-i 当 i≧ j
j(j-1)/2+i-1 当 i<jk=
在这个下三角矩阵中，第 i行恰有 i个元素，元素总数为 n(n+1)/2，这
样就可将 n2个数据元素压缩存储在 n(n+1)/2个存储单元中。
假设以一维数组 va作为 n阶对称矩阵 A的压缩存储单元,k为一维数组 va
的下标序号,aij为 n阶对称矩阵 A中 i行 j列的数据元素 (其中 1≦i,j≦n ），
其数学映射关系为：
2,n阶三角矩阵
以主对角线划分,n阶三角矩阵有 n阶上三角矩阵和 n阶下三角矩阵
两种。
n阶上三角矩阵如图 5.2(a)所示，它的下三角（不包括主对角线）
中的元素均为 0（或常数）。 n阶下三角矩阵正好相反，它的主对角线上
方均为 0（或常数），如图 5.2(b)所示。
注：在大多数情况下,n阶三角矩阵常数为零。
14
a11 a12 … a 1n a11 c … c
c a22 … a 2n a21 a22 … c
………………,………………
c c … a nn an1 an2 … a n n
(a)上三角矩阵 (b)下三角矩阵
图 5.2 三角矩阵
i(i-1)/2+j-1 当 i≧ j
n(n+1)/2 （或空） 当 i<j
k=
假设以一维数组 sa作为 n阶下三角矩阵 A的压缩存储单元,k为一维数
组 va的下标序号,aij为 n阶下三角矩阵 A中 i行 j列的数据元素 (其中
1≦i,j≦n ），其数学映射关系为：
注：此时一维数组 sa的数据元素个数为 (n(n+1)/2)+1个，其中数组
sa的最后一个位置存储 A中数值不为 0的那个常数。
15
5.4 稀疏 矩阵的压缩存储
一,概念
1、稀疏矩阵
矩阵中非零元素的个数较少（一般小于 5%）。
2、稠密矩阵
一个不稀疏的矩阵。
3、稀疏矩阵压缩存储方法
问题：
如果只存储 稀疏矩阵中的非零元素，那这些元素的 位置信
息 该如何表示？
实现方法：
将每个非零元素用一个三元组 （ i,j,aij）来表示，则每
个 稀疏矩阵可用一个 三元组线性表 来表示。
16
例 1,写出下图 5.3所示稀疏矩阵的压缩存储形式。
1 2 3 4 5 6
1
2
3
4
5
6
图 5.3
解,用 三元组 线性表 表示：
{{1,2,12},{1,3,9},{3,1,-3},{3,5,14},
{4,3,24},{5,2,18},{6,1,15},{6,4,-7}}
说明,稀疏矩阵的压缩存储结构主要有三元组顺序表和三元
组链表两大类型。
0 12 9 0 0 0
0 0 0 0 0 0
-3 0 0 0 14 0
0 0 24 0 0 0
0 18 0 0 0 0
15 0 0 -7 0 0
17
二、稀疏矩阵的三元组顺序表
1、三元组顺序表
指用顺序表存储的三元组线性表。
把三元组定义成顺序表的数据元素：
typedef struct
{ int i; /*行号 */
int j; /*列号 */
elemtype d; /*元素值 */
} DataType;
把稀疏矩阵的行数、列数和非零元个数定义成三元组顺序表
的控制数据结构体,typedef struct
{ int md; /*行数 */
int nd; /*列数 */
elemtype td; /*非零元素个数 */
} TriType;
18
1 2 12
1 3 9
3 1 -3
3 5 14
4 3 24
5 2 18
6 1 15
6 4 -7
i j d
0
1
2 说明：存储一个矩阵时，通常是按照
先行后列的顺序存储。
3
4
5 md
6 nd
7 td
图 5.4 稀疏矩阵的三元组顺序表
6
6
8
19
例 2,下面的三元组表表示一个稀疏矩阵，试还原出它
的稀疏矩阵。
1 2 2
2 1 12
3 1 3
4 4 4
5 3 6
6 1 16
i j d
1
2
3
4 md
5 nd
6 td
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
2 0 0
12 0 0 0
3 0 0 0
0 0 4
0 6 0
16 0 0 0
6
4
6
20
2、稀疏矩阵的操作
0 12 9 0 0 0
0 0 0 0 0 0
-3 0 0 0 14 0
0 0 24 0 0 0
0 18 0 0 0 0
15 0 0 -7 0 0
0 0 –3 0 0 15
12 0 0 0 18 0
9 0 0 24 0 0
0 0 0 0 0 -7
0 0 14 0 0 0
0 0 0 0 0 0
(1,2,12)
(1,3,9 )
(3,1,-3)
(3,5,14)
(4,3,24)
(5,2,18)
(6,1,15)
(6,4,-7)
(1,3,-3)
(1,6,15)
(2,1,12)
(2,5,18)
(3,1,9)
(3,4,24)
(4,6,-7)
(5,3,14)
已知
三
元
组
表
a
求
三
元
组
表
b
转置后M T
（以 转置运算 为例）
目的：
21
答,肯定不正确！
除了,（ 1）每个元素的行下标和列下标互换（即三元组
中的 i和 j互换 ）；
还需要,（ 2） T的总行数 md和总列数 nd也要 互换；
（ 3） 重排 三元组内各元素顺序,使转置后的三元
组也按行（或列）为主序有规律的排列。
上述（ 1）和（ 2）容易实现，难点在 （ 3） 。
若采用三元组压缩技术存储稀疏矩阵，只要把每个
元素的 行下标和列下标互换,就完成了对该矩阵的转置运
算，这种说法正确吗？
提问：
22
三元组顺序表的转置操作的算法实现：
void Transition2(SeqList a,TriType da,SeqList *b,TriType *db)
{ int p,q,v;
db->md = da.nd; /*行数值转为列数值 */
db->nd = da.md; /*列数值转为行数值 */
db->td = da.td; /*非零元个数不变 */
if (da.td==0) return;
else{ q = 0; /*q为 b->list[]的下标值 */
for (v=1;v<=da.nd;v++)
{ for(p = 0; p < da.td; p++)/*p为 a.list[]的下标值 */
{ if(a.list[p].j == v) /*寻找原矩阵中列下标值最小的 */
{ b->list[q].i = a.list[p].j; /*列号转为行号 */
b->list[q].j = a.list[p].i; /*行号转为列号 */
b->list[q].d = a.list[p].d; /*数组元素复制 */
q++; } }
}
}
}
23
三、稀疏矩阵的三元组链表
1、三元组链表
用链表存储的三元组线性表。
2、行指针数组结构的三元组链表
把每行非零元素三元组组织成一个单链表，再设计
一个指针类型的数组存储所有单链表的头指针。
3、三元组十字链表
把非零元素三元组按行和按列组织成单链表，这样
稀疏矩阵中的每个非零元素三元组结点都将既勾链
在行单链表上，又勾链在列单链表上，形成十字形
状。
第 5章 数组
5.1 数组
5.2 动态 数组
5.3 特殊 矩阵 的压缩存储
5.4 稀疏 矩阵 的压缩存储
2
5.1 数组
一、数组的定义
数组：它是 n（ n>1)个相同数据类型的数据元素 a0,a1,a2,…a n-1
构成的占用一块地址连续的内存单元的有限序列。
数组的下标：数组元素的位置。
注意：
(1)C语言的数组定义下标从 0开始。
(2) 数组的处理相比其它复杂的结构要简单。
① 数组中各元素具有 统一的类型 ；
② 数组元素的下标一般具有 固定的上界和下界,即数组一旦被
定义，它的维数和维界就不再改变。
③数组的 基本操作比较简单,除了结构的初始化和销毁之外，
只有存取元素和修改元素值的操作。
(3)一个二维数组可以看作每个数据元素是一个一维数组的一维数
组。 二维数组是两维的，内存单元是一维的，存在向内存存储时
二维数组中数据元素的存储方法问题,C语言采用以行序为主序的
方法存储。
3
问题：数组与线性表的区别与联系
相同之处：
它们都是若干个 相同数据类型 的数据元素 a0,a1,a2,…, an-1
构成的有限序列。
不同之处：
(1)数组要求其元素占用一块 地址连续 的内存单元空间，而
线性表无此要求；
(2)线性表的元素是 逻辑意义上不可再分的元素,而数组中
的每个 元素还可以是一个数组 ；
(3)数组的 操作 主要是向某个下标的数组元素中存放数据和
取某个下标的数组元素，这与线性表的插入和删除操作 不同 。
4
二、数组的实现机制
１,一维数组（ n个元素）中任一元素 ai的内存单元地址
LOC(ai)=LOC(a０ )+i*k (0≤i <n)
２、一个 m行 n列的二维数组
LOC(aij)=LOC(a00)+(i*n+j)*k (0≤i<m,0≤j<n)
注,C语言中数组元素采用行主序的存放方法，即 行优先 顺序 。
a０ 的 内存单元地址 每个元素所需的字节个数
每个元素所需的字节个数a０ 0的 内存单元地址
一个 m× n的二维数组可以
看成是 m行的一维数组，或
者 n列的一维数组。
a0,0 a0,1 … a 0,n-1
a1,0 a1,1 … a 1,n-1
… … … …
am-1,0 am-1,1 … a m-1,n-1
Amn=
5
注：只要知道以下三要素便可随时求出任一元素的地址 （意
义：数组中的任一元素可随机存取）
①开始结点的存放地址（即基地址）；
②维数和每维的上、下界；
③每个数组元素所占用的单元数
例１ 〖 软考题 〗, 一个二维数组 A，行下标的范围是 1到 6，列下标的范围是 0到
7，每个数组元素用相邻的 6个字节存储，存储器按字节编址。那么，这个
数组的体积是 个字节。
答,Volume=m*n*L=(6-1+1)*(7- 0 +1)*6=48*6=288
例２ 设数组 a[０ … 60,０ … 70]的基地址为 2048，每个元素占 2个存储单元，
若以行序为主序顺序存储，则元素 a[32,58]的存储地址
为 。
答,根据行优先公式 LOC(aij)=LOC(a00)+(i*n+j)*k (0≤ i<m,0≤ j<n)
得,LOC(a32,58)=2048+(32*70+58)*2＝ 6644
288
6644
6
三,数组抽象数据类型
数据集合,｛ a0,a1,a2,…a n-1 } 每个数据类型为抽象数据元素类型
操作集合,(1)求 数组元素个数 ArrayLength(D)
(2)存数组元素 Storage(D,i,x)
(3)取数组元素 Get(D,i,x)
7
5.2 动态数组
一、动态数组的设计方法
1、动态数组的概念
动态数组,它是在需要存储单元空间时才给出数组的具体个
数。
C语言提供的支持函数有：
malloc( ),calloc( ),free( )
例：编写一个定义和使用二维 3行 4列动态数组的一个完整程序。
8
#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>
void main(void)
{ int i,j,row=3,col=4,**a;
a=(int **) malloc(row*sizeof(int *))；
for (i=0;i<row;i++)
a[i]=(int *)malloc(col*sizeof(int));
for(i=0;i<row;i++)
{ for(j=0;j<col;j++)
{ a[i][j]=i+j;
printf("%d ",a[i][j]); }
printf(“\n”);}
}
9
例：编写一个使用两维动态数组的函数。
int **Make2DArray(int row,int col)
{ int **a,i;
a=(int **) malloc(row*sizeof(int *))；
for (i=0;i<row;i++)
a[i]=(int *) malloc(col*sizeof(int))；
return a;
}
10
#include <malloc.h>
#include <stdio.h>
#include <stdlib.h> /*函数已经定义，同前 */
void main(void)
{ int i,j,c,row=3,col=4,**a;
a=Make2DArray(row,col);
for(i=0;i<row;i++)
{ for(j=0;j<col;j++)
{ a[i][j]=i+j;
printf(“%d”,a[i][j]); }
printf(“\n”); }
}
11
二、动态数组和静态数组对比
1、从使用方法上来说，动态数组和静态数组除向系统申
请内存空间的方法不同外，数组的使用方法完全相同。
静态数组采用数组定义语句向系统申请内存空间；
动态数组采用函数 malloc( )来向系统申请内存空间。
2、从性能上来说,静态数组 必须确切指定数组元素个数，这样的
指定在程序运行后 不能改变 ； 动态数组 虽然也要确切指定数组
元素个数，但因为这样的指定是在程序运行时通过调用函数实
现的，可以 改变其元素个数 。
12
5.3 特殊矩阵的压缩存储
特殊矩阵,指有许多值相同的元素或有许多零元素、且值相同的元素或零
元素的分布有一定规律的矩阵。
下面我们讨论几种特殊矩阵的压缩存储。
1,n阶对称矩阵
在一个 n阶方阵 A中，若元素满足下述性质：
aij=aji （ 1≦i,j≦n ）
则称 A为 n阶对称矩阵 。如图 5.1是一个 5阶对称矩阵。
1 5 1 3 7 a11
5 0 8 0 0 a21 a 22
1 8 9 2 6 a31 a32 a33
3 0 2 5 1 ………………..
7 0 6 1 3 an1 an2 an3 …a nn
图 5.1 对称矩阵
n阶对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三
角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，
能节约近一半的存储空间。不失一般性，我们按, 行优先 顺序”存储主
对角线（包括对角线）以下的元素。
13
i(i-1)/2+j-i 当 i≧ j
j(j-1)/2+i-1 当 i<jk=
在这个下三角矩阵中，第 i行恰有 i个元素，元素总数为 n(n+1)/2，这
样就可将 n2个数据元素压缩存储在 n(n+1)/2个存储单元中。
假设以一维数组 va作为 n阶对称矩阵 A的压缩存储单元,k为一维数组 va
的下标序号,aij为 n阶对称矩阵 A中 i行 j列的数据元素 (其中 1≦i,j≦n ），
其数学映射关系为：
2,n阶三角矩阵
以主对角线划分,n阶三角矩阵有 n阶上三角矩阵和 n阶下三角矩阵
两种。
n阶上三角矩阵如图 5.2(a)所示，它的下三角（不包括主对角线）
中的元素均为 0（或常数）。 n阶下三角矩阵正好相反，它的主对角线上
方均为 0（或常数），如图 5.2(b)所示。
注：在大多数情况下,n阶三角矩阵常数为零。
14
a11 a12 … a 1n a11 c … c
c a22 … a 2n a21 a22 … c
………………,………………
c c … a nn an1 an2 … a n n
(a)上三角矩阵 (b)下三角矩阵
图 5.2 三角矩阵
i(i-1)/2+j-1 当 i≧ j
n(n+1)/2 （或空） 当 i<j
k=
假设以一维数组 sa作为 n阶下三角矩阵 A的压缩存储单元,k为一维数
组 va的下标序号,aij为 n阶下三角矩阵 A中 i行 j列的数据元素 (其中
1≦i,j≦n ），其数学映射关系为：
注：此时一维数组 sa的数据元素个数为 (n(n+1)/2)+1个，其中数组
sa的最后一个位置存储 A中数值不为 0的那个常数。
15
5.4 稀疏 矩阵的压缩存储
一,概念
1、稀疏矩阵
矩阵中非零元素的个数较少（一般小于 5%）。
2、稠密矩阵
一个不稀疏的矩阵。
3、稀疏矩阵压缩存储方法
问题：
如果只存储 稀疏矩阵中的非零元素，那这些元素的 位置信
息 该如何表示？
实现方法：
将每个非零元素用一个三元组 （ i,j,aij）来表示，则每
个 稀疏矩阵可用一个 三元组线性表 来表示。
16
例 1,写出下图 5.3所示稀疏矩阵的压缩存储形式。
1 2 3 4 5 6
1
2
3
4
5
6
图 5.3
解,用 三元组 线性表 表示：
{{1,2,12},{1,3,9},{3,1,-3},{3,5,14},
{4,3,24},{5,2,18},{6,1,15},{6,4,-7}}
说明,稀疏矩阵的压缩存储结构主要有三元组顺序表和三元
组链表两大类型。
0 12 9 0 0 0
0 0 0 0 0 0
-3 0 0 0 14 0
0 0 24 0 0 0
0 18 0 0 0 0
15 0 0 -7 0 0
17
二、稀疏矩阵的三元组顺序表
1、三元组顺序表
指用顺序表存储的三元组线性表。
把三元组定义成顺序表的数据元素：
typedef struct
{ int i; /*行号 */
int j; /*列号 */
elemtype d; /*元素值 */
} DataType;
把稀疏矩阵的行数、列数和非零元个数定义成三元组顺序表
的控制数据结构体,typedef struct
{ int md; /*行数 */
int nd; /*列数 */
elemtype td; /*非零元素个数 */
} TriType;
18
1 2 12
1 3 9
3 1 -3
3 5 14
4 3 24
5 2 18
6 1 15
6 4 -7
i j d
0
1
2 说明：存储一个矩阵时，通常是按照
先行后列的顺序存储。
3
4
5 md
6 nd
7 td
图 5.4 稀疏矩阵的三元组顺序表
6
6
8
19
例 2,下面的三元组表表示一个稀疏矩阵，试还原出它
的稀疏矩阵。
1 2 2
2 1 12
3 1 3
4 4 4
5 3 6
6 1 16
i j d
1
2
3
4 md
5 nd
6 td
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
2 0 0
12 0 0 0
3 0 0 0
0 0 4
0 6 0
16 0 0 0
6
4
6
20
2、稀疏矩阵的操作
0 12 9 0 0 0
0 0 0 0 0 0
-3 0 0 0 14 0
0 0 24 0 0 0
0 18 0 0 0 0
15 0 0 -7 0 0
0 0 –3 0 0 15
12 0 0 0 18 0
9 0 0 24 0 0
0 0 0 0 0 -7
0 0 14 0 0 0
0 0 0 0 0 0
(1,2,12)
(1,3,9 )
(3,1,-3)
(3,5,14)
(4,3,24)
(5,2,18)
(6,1,15)
(6,4,-7)
(1,3,-3)
(1,6,15)
(2,1,12)
(2,5,18)
(3,1,9)
(3,4,24)
(4,6,-7)
(5,3,14)
已知
三
元
组
表
a
求
三
元
组
表
b
转置后M T
（以 转置运算 为例）
目的：
21
答,肯定不正确！
除了,（ 1）每个元素的行下标和列下标互换（即三元组
中的 i和 j互换 ）；
还需要,（ 2） T的总行数 md和总列数 nd也要 互换；
（ 3） 重排 三元组内各元素顺序,使转置后的三元
组也按行（或列）为主序有规律的排列。
上述（ 1）和（ 2）容易实现，难点在 （ 3） 。
若采用三元组压缩技术存储稀疏矩阵，只要把每个
元素的 行下标和列下标互换,就完成了对该矩阵的转置运
算，这种说法正确吗？
提问：
22
三元组顺序表的转置操作的算法实现：
void Transition2(SeqList a,TriType da,SeqList *b,TriType *db)
{ int p,q,v;
db->md = da.nd; /*行数值转为列数值 */
db->nd = da.md; /*列数值转为行数值 */
db->td = da.td; /*非零元个数不变 */
if (da.td==0) return;
else{ q = 0; /*q为 b->list[]的下标值 */
for (v=1;v<=da.nd;v++)
{ for(p = 0; p < da.td; p++)/*p为 a.list[]的下标值 */
{ if(a.list[p].j == v) /*寻找原矩阵中列下标值最小的 */
{ b->list[q].i = a.list[p].j; /*列号转为行号 */
b->list[q].j = a.list[p].i; /*行号转为列号 */
b->list[q].d = a.list[p].d; /*数组元素复制 */
q++; } }
}
}
}
23
三、稀疏矩阵的三元组链表
1、三元组链表
用链表存储的三元组线性表。
2、行指针数组结构的三元组链表
把每行非零元素三元组组织成一个单链表，再设计
一个指针类型的数组存储所有单链表的头指针。
3、三元组十字链表
把非零元素三元组按行和按列组织成单链表，这样
稀疏矩阵中的每个非零元素三元组结点都将既勾链
在行单链表上，又勾链在列单链表上，形成十字形
状。
