第5章数组和广义表 数组和广义表是线性表的推广,表中的数据元素本身也可以是一个数据结构。本章介 绍数组和广义表的定义、存储结构与算法实现。 5.数组的基本概念 1 5.1 数组的定义与特点 1. 1.数组的定义 数据结构中讨论的数组(aray)不同于高级语言中的数组。高级语言中数组是一种数 据类型,而且只有顺序结构。本章所讨论的数组是一种数据结构,既可以是顺序结构,也可 以是链式结构,用户可根据需要选择。 数组A=(a1,an-1)由一组名字相同、下标不同的变量构成。若ai (0≤i≤ a0,a2,…, n-1)是同类型的元素,则 A 是一维数组。若ai(0≤i1时,元素ai0。 由此可知,一个带宽为d(的对角矩阵 A 是满足下述条件的矩阵:若|i-j|> d-ij= 不失一般性,对角矩阵可按行优先顺序或对角线的顺序,将其压缩存储到一个一维数组 (1)/2,则元素a0。 d 为奇数) 7(为行主序的一维数组压 中,并且也能找到每个非零元素和数组下标的对应关系。图5.b) 缩存储。若采用行优先顺序,则存储带宽为 d 的对角矩阵中非零元素aj 的地址公式为 Loc()=Loc(-1+(i+(d-1)/2)(i) aija00)+d×ij 图5. 7 对角矩阵及其压缩存储 4.稀疏矩阵 设m×n 的矩阵 A 中有 s 个非零元素,若 s 远远小于矩阵元素的总数,则称 A 为稀疏矩 阵。令e=s/(称 e 为矩阵的稀疏因子。通常认为e≤0. m×n), 05时为稀疏矩阵。 稀疏矩阵中非零元素的分布一般是没有规律的,因此在存储非零元素的同时,还必须同 时记下它所在的行和列的位置(j)。 i, 稀疏矩阵中每个非零元素和它对应的行下标和列下标构成一个三元组。三元组的结构 119 如图5.其中i,aij 表示非零元素的值。 8所示, j 分别表示非零元素的行号和列号, 图5. 8 三元组的结点结构 一个三元组(j,)可以唯一确定矩阵 A 的一个非零元素。稀疏矩阵可由表示非零 i,aij 元素的三元组及其行列数唯一确定。 图5..aa 9 稀疏矩阵 M 及其三元组表adt 例如,图5.a) 其中只有6个非零元素。6个三元组 9(所示的稀疏矩阵 M 有42 个元素, (1,3,9),(1,5,-7),(3,1,8),(4,3,-2),(5,2,5),(6,6,3)表示该矩阵的6个非零元素。 若以行主序将这6个三元组排列起来,再加上一个表示矩阵 M 的行数、列数及非零元素的 个数的特殊三元组(6,7,6), 则所形成的三元组表就能唯一确定稀疏矩阵 M ,如图5.b) 所示。 9( 三元组表可用顺序表存储,也可用链表存储。用顺序表存储的三元组表称为三元组顺 序表,用链表存储的三元组表称为三元组链表。 对于稀疏矩阵,三元组表存储结构对存储空间的需求量比通常的方法少得多。例如, m×n 的矩阵 M ,非零元的个数为num,若用三元组表来表示,在每个元素占一个存储单元 的情况下,只需要3×(num+1)个存储单元(包括特殊三元组所占用的3个单元); 若用传 统的二维数组表示,则需要m×n 个存储单元。当矩阵越大、越稀疏时,三元组存储方式的 优越性就越明显。 5.矩阵的算法实现 3 矩阵最常用的操作有矩阵加、矩阵减、矩阵乘、矩阵转置、矩阵求逆、矩阵行列式等。在 掌握线性表的基本操作的基础上,这些操作都不难实现。但是,稀疏矩阵的快速转置算法思 想巧妙,性能优良。因此,下面仅以稀疏矩阵的快速转置算法为例进行算法实现。 一个m×n 的矩阵 M ,它的转置矩阵 T 是一个n×m 的矩阵,且Tij =Mji,其中,0≤i≤ n-1,0≤j≤m-1。 在这里沿用上面介绍的三元组的方式存储矩阵。 明确了存储方式后,就不难进行相应的存储结构的定义。 120 121 三元组的定义如下。 1. template 2. struct Triple { 3. int i, j; //非零元素的行下标和列下标 4. T elem; 5. }; 矩阵类的定义如下。 1. template 2. struct Matrix { 3. int row, col; 4. int num; 5. Triple*data; 6. 7. Matrix(int r, int c, int n) : row(r), col(c), num(n) { 8. data =new Triple[num +1]; //非零三元组表,data[0]未用 9. } 10. 11. ~Matrix() { delete[]data; } 12. }; 上述的两段代码共同构成了矩阵的头文件。 1.算法功能 采用三元组表存储矩阵,由矩阵M 的三元组表a.data求得其转置矩阵T 的三元组表 b.data,实现矩阵M 的转置。 2.算法思路 (1)预先确定矩阵M 中每一列,即转置矩阵T 中每一行的第一个非零元素在b.data中 的位置。为此,需事先求得矩阵M 的每一列中非零元素的个数。可设置两个数组num [col]和cpot[col],分别存放矩阵M 中每一列的非零元素个数和每一列第一个非零元素在 b.data中的位置,即 ● M 中的列变量用col表示。 ● num[col]存放M 中第col列中非零元素个数。 ● cpot[col]存放M 中第col列的第一个非零元素在b.data中的位置。 于是有 cpot[1]=1 {cpot[col]=cpot[col-1]+num[col-1], 2≤col≤a.col (2)按照a.data中三元组的次序进行转置。对于扫描到的a.data中的当前元素,利用 其列信息,即可在cpot[col]中直接查出它在b.data中的最终存放位置。 转置后的元素不连续存放,直接按照cpot[col]的结果将其放到b.data中最终的位置 上。同时,修改该列的cpot[col]为cpot[col]+1,为该列的下一个元素的存放做好准备。这 样既可避免元素移动,又只需对a.data扫描一次即可实现矩阵的转置。 3. 实例描述 稀疏矩阵 M 的三元组表a.a如图5.a)所示,其中,ow 为行号,l为列号, 为值。求该矩阵的稀疏矩阵T。 dat10(rcovalue (1)首先将num[col]和cpot[col]初始化,数组元素清零。 图5. 10 矩阵 M 的快速转置过程 (2)扫描矩阵 M 的三元组表a.a,计算nl]的值,如图5.b)所示。 datum[co10( 第一个元素(1,3,9), 列号为3,num[3]=1; 第二个元素(1,5,-7), 列号为5,num[5]=1; 第三个元素(3,1,8), 列号为1,num[1]=1; 第四个元素(4,3,-2), 列号为3,num[3]=2; 第五个元素(5,2,5), 列号为2,num[2]=1; 第六个元素(6,6,3), 列号为6,num[6]=1 。 poco10( (3)计算ct[l]的值,如图5.b)所示 。 cpot[1]=1; cpot[2]=cpot[1]+num[1]=1+1=2; cpot[3]=cpot[2]+num[2]=2+1=3; cpot[4]=cpot[3]+num[3]=3+2=5; cpot[5]=cpot[4]+num[4]=5+0=5; cpot[6]=cpot[5]+num[5]=5+1=6; cpot[7]=cpot[6]+num[6]=6+1=7 。 (4)扫描矩阵 M 的三元组表adt生成转置矩阵 T 的三元组表bdt如图510(所示。 .aa, .aa, .c) 第一个元素(1,3,9)列号为3,t[3]3,转置后的元素(3,1,9)是b.a中的第3个 元素,并修改cpot[3]=4; cpo=dat 第二个元素(7), 列号为5,转置后的元素(是b.a中的 1,5,-cpot[5]=5, 5,1,-7) dat 第5个元素,并修改cpot[5]=6; 第三个元素,(3,8), 列号为1,pt[=1,转置后的元素(3,8)是b.aa中的第1 1,co1]1,dt 122 123 个元素,并修改cpot[1]=2; 第四个元素(4,3,-2),列号为3,cpot[3]=4,转置后的元素(3,4,-2)是b.data中的 第4个元素,并修改cpot[3]=5; 第五个元素(5,2,5),列号为2,cpot[2]=2,转置后的元素(2,5,5)是b.data中的第2 个元素,并修改cpot[2]=3; 第六个元素(6,6,3),列号为6,cpot[6]=6,转置后的元素(6,6,3)是b.data中的第6 个元素,并修改cpot[6]=7。 只需要扫描一遍矩阵M 的三元组表a.data,而且不需要元素的移动,即可生成转置矩 阵T 的三元组表b.data。 4.参考程序 定义文件中的主程序如下。 1. #include "Matrix.h" 2. #include 3. using namespace std; 4. 5. void create_Matrix(Matrix&M) 6. { 7. cout <<"请按照行优先顺序输入稀疏矩阵" 8. <>M.data[k].i >>M.data[k].j >>M.data[k].elem; 13. } 14. cout <FastTranspose_Matrix(Matrix&M) 19. { 20. Matrix T(M.col, M.row, M.num); 21. if (M.num ==0) 22. return T; 23. int *num =new int[M.col +1](); 24. int *cpot =new int[M.col +1](); 25. 26. //计算num[col]的值 27. for (int t =1; t <=M.num; t++) 28. num[M.data[t].j]++; 29. //计算cpot[col]的值 30. cpot[1] =1; 31. for (int col =2; col <=M.col; col++) 32. cpot[col] =cpot[col -1] +num[col -1]; 124 33. //扫描矩阵M 的三元组表a.data,生成转置矩阵T 的三元组表b.data 34. for (int p =1; p <=M.num; p++) 35. { 36. int q =cpot[M.data[p].j]; 37. T.data[q].i =M.data[p].j; 38. T.data[q].j =M.data[p].i; 39. T.data[q].elem =M.data[p].elem; 40. cpot[q]++; 41. } 42. 43. delete[] num; 44. delete[] cpot; 45. return T; 46. } 47. 48. void print_Matrix(Matrix&M) 49. { 50. cout <<"共有" <>r >>c; 77. cout <<"输入稀疏矩阵非零元素个数:";