数据结构课件第5章数组和广义表

1第5章数组和广义表5.1数组的逻辑结构5.2数组的顺序存储结构5.3矩阵的压缩存储5.4广义表5.1数组的逻辑结构5.2数组的顺序存储结构5.3矩阵的压缩存储5.4广义表数据结构课件第5章数组和广义表共64页，您现在浏览的是第1页!数组(array)是最常用的数据结构之一。几乎所有的程序设计语言都把数组类型设定为固有类型。数组的定义线性结构中的数据都是非结构的原子类型，元素的值是不再分解的。而数组可以看成是线性表在下述含义上的扩展：5.1数组的逻辑结构2数组的基本操作表中的数据元素本身也是一种数据结构。数据结构课件第5章数组和广义表共64页，您现在浏览的是第2页!数组是由下标和值组成的序对集合。在数组中，一旦给定下标，都存在一个与其相对应的值，这个值就称为数组元素。也可以说，数组中的每个数据元素都对应于一组下标（j1

,j2

,…,jn），每个下标取值范围是1≤ji≤bi，bi称为第i

维的长度（i=1,2,…,n）。显然，当n=1时，n维数组就退化为定长的线性表。反之，n

维数组也可以看成是线性表的推广。3 5.1.1数组的定义数据结构课件第5章数组和广义表共64页，您现在浏览的是第3页! 每个数据元素α

j是一个列向量形式的线性表Am×n=…a1,na2,n…am,na13a23…am,3a12a22…am,2a11a21…am,1

二维数组A

还可以看成是一个线性表：A=(α1,α

2,…,α

n)

α

j=(a1j

,a2j

,…,am,j) 1≤j≤n 每个数据元素是一个行向量形式的线性表

B=(β1β2β3…,

βm)Am×n=((a11

a12

…a1,n

),…,(am,1am,2…am,n

))(a21

a22

…a2,n

),…,βi=(ai1,ai2,…,ai,n) 1≤i≤m4数据结构课件第5章数组和广义表共64页，您现在浏览的是第4页! 5.1.2数组的抽象类型定义ADTArray{

D={aj1j2j3…..jn|n>0,称为数组的维数,ji是数组的第i维下标,1≤ji

≤bi,

bi为数组第i维的长度，aj1j2j3…..jn∈ElementSet}数据关系：Ｒ

={R1,R2,…….Rn}Ri=<aj1…ji….jn,aj1…ji+1…jn>|1≤jk≤bk,1≤k≤n且k≠i,1≤ji

≤bi-1,aj1…j2….jn,aj1…ji+1…jn∈D,i=1,…n}基本操作:InitArray(A,n,bound1,…,boundn); 操作结果：如果维数n

和各维长度合法，则构造 相应的数组A，并且返回TRUE。数据结构课件第5章数组和广义表共64页，您现在浏览的是第5页!由于内存储器的结构是一维的。一维数组可直接采用顺序存储。用一维的内存存储表示多维数组时，需按某种次序将数组中元素排成一线性序列，再将这个线性序列存放在一维的内存中，即数组的顺序存储结构表示。顺序存储的定位公式5.2数组的顺序存储结构6数组的顺序存储表示基本操作的算法描述数据结构课件第5章数组和广义表共64页，您现在浏览的是第6页!a21a11…am,1a22a12…am,2a1,n…a2,n…am,na21a11…am,1a21a11…Am,1a21a11…am,1a22a12…am,2a22a12…am,2a22a12…am,2………a1,na2,n…am,na1,na2,n…am,na1,na2,n…am

n7列主次序存放数据结构课件第5章数组和广义表共64页，您现在浏览的是第7页!对于数组，一旦规定了它的维数和各维的长度，便可以为它分配存储空间。反之，只要给出一组下标，便可以求得相应数组的存储位置。8数据结构课件第5章数组和广义表共64页，您现在浏览的是第8页!

⑵二维数组的地址计算

假设每个数据元素占1

个存储单元，且以行序为主序的进行存储，则二维数组A

中任一元素aij

的存储位置可以由下面定位公式确定LOC(A[i],[j])=LOC(A[1],[1])+n*(i-1)+(j-1)其中：

LOC(A[i[,[j]) 是aij

的存储位置；

LOC(A[1],[1]) 是a11

的存储位置，即二维数组A

的起始存储位置，也称为基地址或基址；n 是数组第二维的长度。9

假设每个数据元素占size个存储单元，则二维数组A

中任一元素aij

的存储位置可以由下面定位公式确定LOC(A[i],[j])=LOC(A[1],[1])+(n*(i-1)+(j-1))*size数据结构课件第5章数组和广义表共64页，您现在浏览的是第9页!矩阵(matrix)是很多科学与工程计算问题中研究的数学对象。在数据结构中，我们感兴趣的不是矩阵本身，而是如何存储矩阵的元素而使矩阵的各种运算能够有效地进行。

特殊矩阵包括两个部份：①元素分布有特殊规律的矩阵,找到规律对应的公式，实现压缩存储。②非零元素很少的稀疏矩阵，可采用只存非零元素的方法实现压缩存储。5.3矩阵的压缩存储10数据结构课件第5章数组和广义表共64页，您现在浏览的是第10页!

假若相同的元素或者零元素在矩阵中的分布有一定规律，则称特殊矩阵。特殊矩阵主要有3种：对称矩阵、三角矩阵、带状矩阵。

在所有这些统称为“特殊矩阵”的矩阵中，非零元的分布都有一个明显的规律，从而都可以将其压缩存储到一维数组中，并且找到每个非零元在一维数组中的对应关系。11 5.3.1特殊矩阵的压缩存储数据结构课件第5章数组和广义表共64页，您现在浏览的是第11页!

对于对称矩阵，可以为每一对对称元只分配一个存储空间，这样就可以将n2

个元压缩存储到n(n+1)/2个元的空间中。假设以行序为主序存储对称矩阵的下三角（包括对角线）中的元。以一维数组B[n(n+1)/2]作为n

阶对称矩阵M

的存储结构，12a31a22a21a11an,n…an,1…BLoc(A[i][j]=1234……

Loc(A[i][j])=Loc(A[1][1])+i*(i-1)/2+j-1(i>j)数据结构课件第5章数组和广义表共64页，您现在浏览的是第12页!一个n

阶方阵，若它的全部非零元素落在一个以对角线为中心的带状区域中，则称该矩阵为带状矩阵，或对角矩阵。这个带状区域若包含主对角线上下各b

条对角线道上元素，那么，b

称为该带状矩阵的半带宽，或称该带状矩阵的带宽为(2b+1)。3.带状矩阵00b

条b

条13数据结构课件第5章数组和广义表共64页，您现在浏览的是第13页!带状矩阵中最常见的是三对角带状矩阵。14特点：当i=1j=1,21<i<n,j=i-1,i,i+1

i=n,j=n-1,n

aij非零，其它元素均为零

a11Ann=a12０00a21a22a23０00a32a33a34０0０a43a44a4500………数据结构课件第5章数组和广义表共64页，您现在浏览的是第14页!15一般来说，当矩阵中非零元素的个数远远小于矩阵元素的总数时，称之为稀疏矩阵。假设在m×n

的矩阵中，若有t

个元素不为零，令=t/(m×n)，则称为矩阵的稀疏因子。通常认为≤25%-30%时称为稀疏矩阵。 5.3.2稀疏矩阵的逻辑结构1.稀疏矩阵的定义数据结构课件第5章数组和广义表共64页，您现在浏览的是第15页!012900000000000-3000014000240000018000001500-7000M=矩阵M

可以由三元组表(1,3,-3)，(1,6,15)，(2,1,12)，(2,5,18)，(3,1,9)，(3,4,24)，(4,6,-7)，(6,3,14)再加上（7,6）这一对总的行列值来描述。16数据结构课件第5章数组和广义表共64页，您现在浏览的是第16页!012900000000000-3000014000240000018000001500-7000M=13-3161521122518319342446-76314rowcoleA.data[1]A.data[2]A.data[3]A.data[4]A.data[5]A.data[6]A.data[7]A.data[8](a)稀疏矩阵(b)三元组顺序表17数据结构课件第5章数组和广义表共64页，您现在浏览的是第17页!18原始的三元组表原矩阵012900000000000-3000014000240000018000001500-7000Ｍ=A.data[1]A.data[2]A.data[3]A.data[4]A.data[5]A.data[6]A.data[7]A.data[8]A.data13-3161521122518319342446-76314rowcole转置矩阵00-3001512000180900240000000-70000000014000000000Ｔ=转置的三元组表B.data[1]B.data[2]B.data[3]B.data[4]B.data[5]B.data[6]B.data[7]B.data[8]B.data121213931-3361443245218611564-7rowcole数据结构课件第5章数组和广义表共64页，您现在浏览的是第18页!①算法思想在A中按三元组的列域值(col)开始扫描，依序将三元组A.data的列域值(col

)与行域值(row

)进行对换，并且存入B中。由于A是以M的行序为主序来存放每个非零元的，由此得到转置后矩阵的三元组表B恰是以“行序为主序”。19

按照方法一，即按照“被转置矩阵”M的三元组表A

的“列序”递增顺序进行转置。为了找到矩阵M

的每一列中所有的非零元素，需要对其三元组A.data从行起进行扫描，方法如下：数据结构课件第5章数组和广义表共64页，您现在浏览的是第19页!voidTransposeTSMatrix(TSMatrixA,TSMatrix*B){//采用三元组表结构，求稀疏矩阵A

的转置矩阵B。在程序中，inti,j,k;//j

指示B->data中三元组的序号，//i

指示A.data中三元组的序号，//k指示A的列号（即B的行号）

B->m=A.n; //将稀疏矩阵A

的列数值作为其转置矩阵B

的行数值B->n=A.m; //将稀疏矩阵A

的行数值作为其转置矩阵B

的列数值B->len=A.len; //转置矩阵B与稀疏矩阵A的非零元个数相等②算法编(稀疏矩阵“列序”递增转置算法)

if(B->len>0){

j=1;20数据结构课件第5章数组和广义表共64页，您现在浏览的是第20页!③算法分析一般矩阵的转置算法（经典算法）为：21for(col=0;col<n;++col) for(row=0;row<m;++row)

dest[col][row]=source[row][col];时间复杂度为O(m×n)。

前面给出的求转置矩阵算法的主要工作是在i

和k的两重循环中完成的，所以此算法的时间复杂度为O(A.n×A.len)即和矩阵A

的列数和非零元的个数的乘积成正比。数据结构课件第5章数组和广义表共64页，您现在浏览的是第21页!当矩阵非零元素的位置或个数经常变动时，就不易采用顺序存储结构表示三元组的线性表。例如，在进行“将矩阵

B

加到矩阵A

上”的操作时，由于非零元素的插入或删除将会引起A.data中元素的大量移动。为此，对这种类型的矩阵，采用链式存储结构表示三元组的线性表更为恰当。222.十字链表数据结构课件第5章数组和广义表共64页，您现在浏览的是第22页!typedefstructOLNode{ //结点定义int row,col; //该非零元的行和列下标ElementTypevalue; //该非零元的值

structOLNode *right,*down;//该非零元所在的行表和列表的后继链域}OLNode;*Olink;typedefstruct{ //十字链表定义int m,n,len; //稀疏矩阵行数、列数和非零元个数Olink *row_head,*col_head;//行和列链表头指针向量，由CreateSMatrix分配}CrossList; //十字链表存储结构的类型名23将行链表的头指针存储在一维数组M.row_head中将列链表的头指针存储在一维数组M.col_head中数据结构课件第5章数组和广义表共64页，您现在浏览的是第23页!CreateSMatrix_OL(CrossList*M){//创建稀疏矩阵M。采用十字链表存储表示。(2)利用十字链表实现创建稀疏矩阵的运算if(!(M->row_head=(Olink*)malloc((m+1)*sizeof(Olink))))exit(OVERFLOW);if(!(M->col_head=(Olink*)malloc((n+1)*sizeof(Olink))))exit(OVERFLOW);if(M)free(M);scanf(&m,&n,&t); //输入M

的行数、列数和非零元个数

M->m=m;M->n=n;M->len=t;24①算法编写数据结构课件第5章数组和广义表共64页，您现在浏览的是第24页!if(M->row_head[i]==NULL){M->row_head[i]=p;p->right=NULL;}else{for(q=M->row_head[i];(q->right)&&q->right->col<j; q=q->right); p->right=q->right;q->right=p;}//完成行插入elseif(M->row_head[i]->col>j){//寻找在行表中的插入位置 p->right=M->row_head[i];M->row_head[i]=p;}25数据结构课件第5章数组和广义表共64页，您现在浏览的是第25页!∧∧∧∧∧∧∧M->col_headM->row_head(1)输入(1,1,3)1∧13∧p(2)输入(1,3,5)p135q∧(3)输入(1,4,9)∧149pq∧∧(4)输入(3,1,2)312∧p∧q26(5)输入(2,3,4)234q∧∧(6)输入(2,2,8)q创建稀疏矩阵M

的十字链表if(M.rhead[i]==NULL){M.rhead[i]=p;p->right=NULL;}for(q=M->col_head[i];(q->down)&&q->down->row<i; q=q->down);p->down=q->down;q->down=p;if(M->row_head[i]->j>j){p->right=M->row_head[i];M->row_head[i]=p;}if(M->col_head[j]==NULL){M->col_head[j]=p;p->down=NULL;}pq∧p228if(M->col_head[j]==NULL){M->col_head[j]=p;p->down=NULL;}for(q=M->row_head[i];(q->right)&&q->right->col<j; q=q->right);p->right=q->right;q->right=p;if(M->col_head[j]==NULL){M->col_head[j]=p;p->down=NULL;}for(q=M->row_head[i];(q->right)&&q->right->col<j; q=q->right);p->right=q->right;q->right=p;if(M->col_head[j]==NULL){M->col_head[j]=p;p->down=NULL;}if(M->row_head[i]==NULL){M->row_head[i]=p;p->right=NULL;}for(q=M->col_head[i];(q->down)&&q->down->row<i; q=q->down);p->down=q->down;q->down=p;if(M->row_head[i]==NULL){M->row_head[i]=p;p->right=NULL;}数据结构课件第5章数组和广义表共64页，您现在浏览的是第26页!广义表(generalizedlist)是线性表的推广，有时也称为列表（lists，用复数形式以示与统称的表list的区别）。广泛地应用于人工智能等领域的LISP（表处理语言），把广义表作为基本的数据结构，就连程序也表示为一系列的广义表。275.4广义表数据结构课件第5章数组和广义表共64页，您现在浏览的是第27页!28 5.4.1广义表的逻辑结构广义表一般记作：GL=(a1,a2,…,an)其中：

n

是广义表GL

的长度；

ai 可以是单个元素，也可以是广义表，分别称为广义表GL

的原子和子表，习惯上用大写字母表示广义表的名称，用小写字母表示原子的名称。GL

是广义表(a1,a2,…,an)的名称；1.广义表的定义数据结构课件第5章数组和广义表共64页，您现在浏览的是第28页!

例5-1

A=()，A

是一个空表，它的长度为零。

例5-2

B=(e)，B

只有一个原子e，它的长度为1。

例5-3

C=(a,(b,c,d))，C

的长度为2，两个元素分别为原子a

和子表(b,c,d)。

例5-4

D=(A,B,C)，D

的长度为3，三个元素分别为A、B和C，都是广义表。显然，将上面所述三个子表的值代入以后，则有D=((),(e),(a,(b,c,d)))。

例5-5

E=(a,E)，这是一个递归表，它的长度为2，E相当于一个无限的广义表E=(a,(a,(a,…)))。292.广义表的三个重要结论数据结构课件第5章数组和广义表共64页，您现在浏览的是第29页!ecdbaBACD表示广义表表示原子30数据结构课件第5章数组和广义表共64页，您现在浏览的是第30页!(1)A=() (2)B=(e)(3)C=(a,(b,c,d)) (4)D=(A,B,C)(5)E=(a,E)GetHead(B)=e GetTail(B)=()GetHead(C)=a GetTail(C)=((b,c,d))GetHead(D)=A GetTail(D)=(B,C)由于(B,C)为非空广义表，令F=(B,C)，则可以继续分解得到：

GetHead(F)=B GetTail(F)=(C)

任何一个非空广义表的表头可能是原子，也可能是广义表；而其表尾必定是广义表。例如，广义表如下：

对定义表B，C，D

取表头和取表尾的操作结果：31数据结构课件第5章数组和广义表共64页，您现在浏览的是第31页!由于广义表（a1,a2,…,an）中的数据元素可以具有不同的结构（或是原子，或是广义表），因此很难用顺序结构表示，通常采用链式存储结构。在这种结构中，需要两种结构的结点。32 5.4.2广义表的存储结构数据结构课件第5章数组和广义表共64页，您现在浏览的是第32页!typedefenum{ATOM,LIST}ElemTag;//ATOM==0:原子；LIST==1:子表typedefstructGLNode{ElemTagtag;//公共部分，用于区分原子结点和表结点

union{ //原子结点和表结点的联合部分AtomType atom; //原子结点的值域structGLNode*hp; //表结点的表头指针};structGLNode*tp;//相当于线性链表的next，指向下一个元素结点}GLNode,*GList; //广义表扩展线性链表类型名33数据结构课件第5章数组和广义表共64页，您现在浏览的是第33页!

可以把二维数组看成是这样一个定长线性表：它的每个数据元素也是一个定长线性表。Am×n=a11a21…am1a12a22…am2a13a23…am3…………a1.na2,n…am,n34例如，下面是一个二维数组，且以m

行n

列的矩阵形式表示。数据结构课件第5章数组和广义表共64页，您现在浏览的是第34页!数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取数据元素和修改数据元素值的操作。35数据结构课件第5章数组和广义表共64页，您现在浏览的是第35页!36 5.1.2数组的抽象类型定义DestroyArray(A):销毁数组A。GetValue(A,e,index1,…,indexn):初始条件：A

是n

维数组，e

为元素变量，随后是

n

个下标值。 操作结果：若各下标合法，则用e返回数组Ａ中由由index1,…indexn所指定的元素的值.SetValue(A,e,index1,…,indexn); 初始条件：A

是n

维数组，e

为元素变量，随后是

n

个下标值。 操作结果：若各下标合法，则将数组A中由index1,…indexn所指定的元素的值置为e.数据结构课件第5章数组和广义表共64页，您现在浏览的是第36页!

用顺序存储结构来存储数组中的元素，一定要按照某种次序将元素排成一个线性序列。有两种存储方式：(1)以列为主序(columnmajororder)的存储方式，即按列优先，逐列顺序存储。(2)以行为主序(rowmajororder)的存储方式，即按行优先，逐行顺序存储。37 5.2.1顺序存储的定位公式数据结构课件第5章数组和广义表共64页，您现在浏览的是第37页!a12a11…a1.na22a21…a2,nam,1…am,2…am,na12a11…a1.na22a21…a2,n………am,1am,2…am,na12a11…a1,na12a11…a1,na22a21…a2,na22a21…a2,nam,1am,2…am,nam,1am,2…am,n38行主次序存放数据结构课件第5章数组和广义表共64页，您现在浏览的是第38页!（１）一维数组的地址计算：设一维数组为：Ａ=(a1,a2,…,ai,…,an),数组中每个元素占size个存储单元，则元素ai的存储地址为：Loc(A[i])=Loc(A[1])+(i-1)*size。

数组的地址计算39数据结构课件第5章数组和广义表共64页，您现在浏览的是第39页!

⑶三维数组的地址计算

三维数组A(1:r,1:m,1:n)。假设每个数据元素占size个存储单元，且以行序为主序的进行存储，首元素a111的地址为Loc(A[1][1][1]),求任意元素aijk的地址。

显然，ai11地址为

Ｌoc(A[i][1][1])=Loc(A[1][1][1])+(i-1)*m*n,因为在该元素之前有i-1个m*n的二维数组。40不难得到三维数组任意元素aijk的地址：Loc(A[i][j][k])=Loc(A[1][1][1])+((i-1)*m*n+(j-1)*n+(k-1))*size,其中：１≤i≤r,１≤j≤m,１≤k≤n。数据结构课件第5章数组和广义表共64页，您现在浏览的是第40页!特殊矩阵的压缩存储所谓压缩存储是指：为多个值相同的元素只分配一个存储空间；对零元不分配空间。41稀疏矩阵的逻辑结构稀疏矩阵的存储结构数据结构课件第5章数组和广义表共64页，您现在浏览的是第41页!

若一个n

阶矩阵M

中的元素满足下述性质1.对称矩阵aij=aji

1≤i，j≤n则称为n

阶对称矩阵。42数据结构课件第5章数组和广义表共64页，您现在浏览的是第42页!

三角矩阵分为下三角矩阵和上三角矩阵。所谓下(上)三角矩阵是指矩阵的上(下)三角(不包括对角线)中的元均为常数c

或为零的n

阶矩阵。2.三角矩阵43下三角矩阵

三角矩阵除了和对称矩阵一样，只存储矩阵的下(上)三角中的元之外，再加上一个存储常数c

的存储空间即可。上三角矩阵数据结构课件第5章数组和广义表共64页，您现在浏览的是第43页!在带状矩阵中，当|i-j|>b

时，aij=0。该方阵共有(2b+1)n-(b+1)b

个非零元素。a11D=a12a1300a21a22a23a240a31a32a33a34a350a42a43a44a4500a53a54a55

D

矩阵是一个5阶、半带宽为2的带状矩阵，在其主对角线a11、a22、a33、a44、a55上下各有2条对角线，共有(2b+1)n-(b+1)b=19个非零元素。44例如：数据结构课件第5章数组和广义表共64页，您现在浏览的是第44页!

1.确定存储该矩阵所需的一维向量空间的大小除行和最后一行只有两个元素外，其余各行均有3个非零元素，由此得到一维向量所需的空间大小为：３n-2

2.确定非零元素在一维数组空间中的位置Ｌoc(a[i][j])=Loc(a[1][1])+2(i-1)+j-145

三对角带状矩阵的压缩存储，以行序为主序进行存储，且只存储非零元素。其方法为数据结构课件第5章数组和广义表共64页，您现在浏览的是第45页!按照压缩存储的概念，只存储稀疏矩阵的非零元素。因此，除了存储非零元素的值aij

之外，还必须同时记下非零元素所在矩阵的行i号和列j号。反之，一个三元组(i,j,aij)唯一确定了矩阵的一个非零元素。因此，稀疏矩阵可以由表示非零元的三元组及其矩阵的总的行列数唯一确定。假设以顺序存储结构表示三元组表，则可以得到稀疏矩阵的一种压缩存储方式，这种方式称之为三元组顺序表。46 5.3.3稀疏矩阵的存储结构1.三元组顺序表数据结构课件第5章数组和广义表共64页，您现在浏览的是第46页!#defineMAXSIZE 1000//假设非零元个数的最大值为1000typedefstruct{ //三元组顺序表的元素结构定义int row,;col //该非零元的行下标和列下标

ElementTypee; //该非零元的值}Triple;typedefstruct{ //三元组顺序表存储结构定义Tripledata[MAXSIZE+1];//非零元三元组表，data[0]未用

int m,n,len; //矩阵的行数、列数和非零个数}TSMatrix; //三元组顺序表的类型名47(1)三元组顺序存储表示

在这里，data域中表示非零元的三元组是以行序为主序顺序排列的。数据结构课件第5章数组和广义表共64页，您现在浏览的是第47页!(2)利用三元组顺序表实现矩阵的转置运算 将矩阵的行列值相互交互；在这3点中，最关键的是第3条，即如何使B.data中的三元组以Ｔ的行（Ｍ的列）为主序依次排列。48显然，一个稀疏矩阵的转置矩阵仍是稀疏矩阵。假设A

和B

是TSMatrix（三元组顺序表）类型变量，分别表示矩阵Ｍ和其转置矩阵Ｔ。那么，只要做到下面3点就可以由A

得到B，实现矩阵的转置。 将每三元组中的row

和col

相互调换； 重排三元组之间的次序。数据结构课件第5章数组和广义表共64页，您现在浏览的是第48页!使b.data中的三元组以T

的行（M

的列）为主序依次排列的方法有如下两种：49方法一：按照B.data中三元组的次序，依次在a.data中找到相应的三元组进行转置。方法二：按照A.data中三元组的次序进行转置，并将转置后的三元组置入B.data中恰当的位置。采用方法一数据结构课件第5章数组和广义表共64页，您现在浏览的是第49页!

转置的三元组表B->data原始的三元组表A.datar

c

v

1

2

12

1

3

9

3

1

-3

3

6

14

4

3

24

5

2

18

6

1

15

6

4

-750利用三元组顺序表存储实现矩阵的转置c

36151463r

11223346v

-3151218924-714

数据结构课件第5章数组和广义表共64页，您现在浏览的是第50页!for(k=1;k<=A.n;k++) for(i=1;i<=A.len;i++) if(A.data[i].col==k){ //进行转置

returnOK;}//TransposeSMatrix B->data[j].row=A.data[i].col; //稀疏矩阵A的列域值成为其转置矩阵B

的行域值 B->data[j].col=A.data[i].row; //稀疏矩阵A

的行域值成为其转置矩阵M

的列域值 B->data[j].e=A.data[i].e; //将稀疏矩阵M

的非零元值赋给其转置矩阵T

j++; //B->data中三元组的序号加1 }//if(A.data)结束}//if(B->len>0)结束51数据结构课件第5章数组和广义表共64页，您现在浏览的是第51页!52当矩阵M

中非零元个数几乎和矩阵元素个数相等时，即len

和m×n等数量级时，算法时间复杂度就为O(m×n2)，虽然节省了存储空间，但时间复杂度提高了。由此可见，上述求转置矩阵算法只适合于len<<m×n

的情况。数据结构课件第5章数组和广义表共64页，您现在浏览的是第52页!(1)稀疏矩阵的十字链表存储表示

矩阵中非零元的行号row；

矩阵中非零元的列号col；

矩阵中非零元的值e；

向右域right，用以链接同一行中下一个非零元；

向下域down，用以链接同一列中下一个非零元。53rowdowncolvalueright非零元行号非零元列号非零元的值向下域向右域在链表中，矩阵的非零元素可用如下结点表示：同一行的非零元通过right域链接成一个线性链表，同一列的非零元通过down域链接成一个线性链表，每个非零元Mij既是第i个行链表中的一个结点，又是第j个列链表中的一个结点，整个矩阵构成了一个十字交叉的链表，故称这样的存储结构为十字链表。数据结构课件第5章数组和广义表共64页，您现在浏览的是第53页!3020-10500000113145∧22-1∧312∧M.col_headM.row_head∧∧∧∧54数据结构课件第5章数组和广义表共64页，您现在浏览的是第54页!for(scanf(&i,&j,&e);i!=0;scanf(&i,&j,&e)){//按任意次序输入非零元if(!(p=(OLNode*)malloc(sizeof(OLNode)))) exit(OVERFLOW);p->row=i; //生成新结点的行号域p->col=j; //生成新结点的列号域p->value=e; //生成新结点的值域55M->row_head[]=NULL;//初始化行头指针向量；令各行链表为空链表M->col_head[]=NULL;//初始化列头指针向量；令各列链表为空链表数据结构课件第5章数组和广义表共64页，您现在浏览的是第55页!if(M->col_head[j]==NULL){ M_col_head[j]=p;p->down=NULL;}else{for(q=M->col_head[j];(q->down)&&q->down->row<