第5章数组和广义表

1、2021-12-2312021-12-232 2021-12-233 数组是大家都已经很熟悉的一种数据类型，几乎所有高级语数组是大家都已经很熟悉的一种数据类型，几乎所有高级语言程序设计中都设定了数组类型。言程序设计中都设定了数组类型。 数组数组（ArrayArray）是由是由n(n1)个个相同类型数据元素相同类型数据元素a0，al，ai，an-1构成的构成的有限序列有限序列。n是数组的长度。其中数组中的数据元素是数组的长度。其中数组中的数据元素ai是是一个数据结构，即一个数据结构，即ai可以是线性表中的一个元素，本身也可以是可以是线性表中的一个元素，本身也可以是一个线性表一个线性表，而线性子表

2、中的每一个数据元素还可以再分解，而线性子表中的每一个数据元素还可以再分解 。根据数组元素根据数组元素ai的组织形式不同，数组可以分为一维数组、二维的组织形式不同，数组可以分为一维数组、二维数组以及多维（数组以及多维（n维）数组。维）数组。 2021-12-2342021-12-2351一维数组一维数组 一维数组可以看成是一个线性表或一个向量，它在计算机内是一维数组可以看成是一个线性表或一个向量，它在计算机内是存放在一块连续的存储单元中，适合于随机查找。存放在一块连续的存储单元中，适合于随机查找。 一维数组中，一旦一维数组中，一旦a0的存储地址、一个数据元素所占存储单元的存储地址、一个数据元素所

3、占存储单元数数k确定，则确定，则ai的存储地址的存储地址LOC(ai)就可求出：就可求出： LOC(ai)=LOC(a0)+i*k (0in) 2二维数组二维数组 二维数组，又称矩阵二维数组，又称矩阵(matrix)。二维数组中的每一个元素又是二维数组中的每一个元素又是一个定长的线性表（一维数组），都要受到两个关系即行关系和一个定长的线性表（一维数组），都要受到两个关系即行关系和列关系的约束，也就是每个元素都同属于两个线性表。列关系的约束，也就是每个元素都同属于两个线性表。例如，设例如，设A是一个有是一个有m行行n列的二维数组，则列的二维数组，则A可以表示为：可以表示为：2021-12-236

4、 a0,0 a0,1 a0,n-1A m n = a1,0 a1,1 a1,n-1 am-1,0 am-1,1 am-1,n-1 可以看成由可以看成由m m个行向量组成的向量，也可以看由个行向量组成的向量，也可以看由n n个列向量组成个列向量组成的向量。的向量。 数组中的每个元素由元素值数组中的每个元素由元素值a aijij及一组下标（及一组下标（i i，j j）来确定。来确定。a aijij既属于第既属于第i i行的行向量，又属于第行的行向量，又属于第j j列的列向量。列的列向量。 其中，其中，a ai i=(=( a ai i,0,0 a ai i,1,1 a ai i,n-1,n-1)

5、(0) (0i in)n) 可以认为可以认为A Am m* *n n=A=A，A A是这样的一维数组：是这样的一维数组： A=( aA=( a0 0，a al l，a ai i，a am-1m-1) ) 2021-12-237 显然，二维数组同样满足数组的定义。一个二维数组可以看显然，二维数组同样满足数组的定义。一个二维数组可以看作是每个数据元素都是相同类型的一维数组。以此类推，任何多作是每个数据元素都是相同类型的一维数组。以此类推，任何多维数组都可以看作一个线性表，这时线性表中的每个数据元素也维数组都可以看作一个线性表，这时线性表中的每个数据元素也是一个线性表。多维数组是特殊的线性表，是线性

6、表的推广。是一个线性表。多维数组是特殊的线性表，是线性表的推广。数组的性质：数组的性质：(1) (1) 数组中的数据元素数目固定。一旦定义了一个数组，其数据数组中的数据元素数目固定。一旦定义了一个数组，其数据元素数目不再有增减变化。它属于静态分配存储空间的数据结构。元素数目不再有增减变化。它属于静态分配存储空间的数据结构。(2) (2) 数组中的数据元素必须具有相同的数据类型。数组中的数据元素必须具有相同的数据类型。(3) (3) 数组中的每个数据元素都有一组唯一的下标值。数组中的每个数据元素都有一组唯一的下标值。 (4) (4) 数组是一种随机存储结构。可随机存取数组中的任意数数组是一种随机

7、存储结构。可随机存取数组中的任意数据元素。据元素。 2021-12-238 数组一旦被定义，它的维数和维界就不再改变。因此，除了结数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，构的初始化和销毁之外，数组的基本操作一般不会含有元素的插入数组的基本操作一般不会含有元素的插入或删除等操作或删除等操作, ,数组只有数组只有访问数组元素访问数组元素和修改元素值的操作。和修改元素值的操作。 (1) (1) value(Avalue(A，indexindexl l，indexindex2 2，indexindexd d) )：A A是已存在的是已存在的d d维维数组，数组，in

8、dexindexl l，indexindex2 2，indexindexd d是指定的是指定的d d个下标值，且这些下个下标值，且这些下标均不超过对应维的上界。其运算结果是返回由下标指定的标均不超过对应维的上界。其运算结果是返回由下标指定的A A中的中的对应元素的值。对应元素的值。(2) (2) assign(Aassign(A，e e，indexindexl l，indexindex2 2，indexindexd d) )：A A是已存在的是已存在的d d维数组，维数组，e e为元素变量，为元素变量，indexindexl l，indexindex2 2，indexindexd d是指定的是

9、指定的d d个个下标值，且这些下标均未越界。其运算结果是将下标值，且这些下标均未越界。其运算结果是将e e的值赋给由下标的值赋给由下标指定的指定的A A中的对应元素。中的对应元素。2021-12-239(3) (3) dispdisp(A)(A)：输出数组输出数组A A的所有元素。的所有元素。在大多数程序设计语言中，取数组元素值操作在大多数程序设计语言中，取数组元素值操作value(Avalue(A，indexindexl l，indexindex2 2，indexindexd d) ) 通常直接写作通常直接写作AAindexindexl l index index2 2 indexindex

10、d d ，而对数组元素的赋值操作而对数组元素的赋值操作assign(Aassign(A，e e，indexindexl l，indexindex2 2，indexindexd d) )写作写作e= Ae= Aindexindexl l index index2 2 indexindexd d ，或者类似的形式。或者类似的形式。 2021-12-2310 由于数组一般不作删除或插入运算，所以一旦数组被定义后，由于数组一般不作删除或插入运算，所以一旦数组被定义后，数组中的元素个数和元素之间的关系就不再变动。通常采用顺序存数组中的元素个数和元素之间的关系就不再变动。通常采用顺序存储结构表示数组。储结

11、构表示数组。 对于一维数组，数组的存储结构关系为对于一维数组，数组的存储结构关系为: : LOC(ai)=LOC(a0)+i * k (0in) 对于二维数组，由于计算机的存储单元是一维线性结构，如何对于二维数组，由于计算机的存储单元是一维线性结构，如何用线性的存储结构存放二维数组元素就有行用线性的存储结构存放二维数组元素就有行/ /列次序问题。常用两列次序问题。常用两种存储方法：以行序种存储方法：以行序( (row major order)row major order)为主序的存储方式和以列为主序的存储方式和以列序序( (column major order)column major or

12、der)为主序的存储方式。为主序的存储方式。 2021-12-2311 行优先顺序行优先顺序将数组元素按行排列，第将数组元素按行排列，第i+1i+1个行向量个行向量紧接在第紧接在第i i个行向量后面。以二维数组为例，按行优先顺序个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为：存储的线性序列为： a a1111,a,a1212, ,a,a1n1n,a,a2121,a,a2222, ,a a2n2n, ,a,am1m1,a,am2m2, , ,a amnmn 在在PASCALPASCAL、C C语言中，数组就是按行优先顺序存储的。语言中，数组就是按行优先顺序存储的。 列优先顺序列优先顺

13、序将数组元素按列向量排列，第将数组元素按列向量排列，第j+1j+1个列个列向量紧接在第向量紧接在第j j个列向量之后，个列向量之后，A A的的m m* *n n个元素按列优先顺序个元素按列优先顺序存储的线性序列为：存储的线性序列为： a a1111,a,a2121, ,a,am1m1,a,a1212,a,a2222, ,a am2m2, ,a,an1n1,a,an2n2, , ,a anmnm 在在FORTRANFORTRAN语言中，数组就是按列优先顺序存储的。语言中，数组就是按列优先顺序存储的。2021-12-2312 图图 5-1 二维数组的两种存储结构二维数组的两种存储结构 a00 a0

14、1A= a10 a11 a20 a21a00a01a10a11a20a21(a)二维数组a00a10a20a01a11a21(c)列序为主序(b)行序为主序对一个以行序为主序的计算机系统，当二维数组第一个数据元素对一个以行序为主序的计算机系统，当二维数组第一个数据元素a a0,00,0的存储地址的存储地址LOC(aLOC(a0,00,0) )以及每个数据元素所占用的存储单元以及每个数据元素所占用的存储单元k k确定确定后，该二维数组中任一数据元素后，该二维数组中任一数据元素a ai i,j,j的存储地址可由下式确定的存储地址可由下式确定:LOC(LOC(a ai i,j,j)=LOC(a)=L

15、OC(a0,00,0)+(i)+(in+jn+j) k) k其中其中n为每行中的列数。为每行中的列数。 2021-12-2313 图图 5-1 二维数组的两种存储结构二维数组的两种存储结构 a00 a01A= a10 a11 a20 a21a00a01a10a11a20a21(a)二维数组a00a10a20a01a11a21(c)列序为主序(b)行序为主序对一个以行序为主序的计算机系统，当二维数组第一个数据元素对一个以行序为主序的计算机系统，当二维数组第一个数据元素a a0,00,0的存储地址的存储地址LOC(aLOC(a0,00,0) )以及每个数据元素所占用的存储单元以及每个数据元素所占用

16、的存储单元k k确定确定后，该二维数组中任一数据元素后，该二维数组中任一数据元素a ai i,j,j的存储地址可由下式确定的存储地址可由下式确定:LOC(LOC(a ai i,j,j)=LOC(a)=LOC(a0,00,0)+(i)+(in+jn+j) k) k其中其中n为每行中的列数。为每行中的列数。 2021-12-2314 【例【例5-15-1】对于给定的二维数组】对于给定的二维数组float a34float a34，计算：计算： (1) (1) 数组数组a a中的数组元素数目；中的数组元素数目； (2) (2) 若数组若数组a a的起始地址为的起始地址为10001000，且每个数组元

17、素长度为，且每个数组元素长度为3232位位( (即即4 4个字节个字节) )，数组元素，数组元素a23a23的内存地址。的内存地址。【解】【解】(1)(1)由于由于C C语言中数组的行、列下标值的下界均为语言中数组的行、列下标值的下界均为0 0，该数组，该数组行上界为行上界为3-1=23-1=2，列上界为，列上界为4-1=34-1=3，所以该数组的元素数目共有，所以该数组的元素数目共有3 3* *4=124=12个。个。 (2) (2)由于由于C C语言采用行序为主序的存储方式，有：语言采用行序为主序的存储方式，有： LOC(aLOC(a2,32,3)=LOC(a)=LOC(a0,00,0)+

18、(i)+(i* *n+j)n+j)* *k k =1000+(2 =1000+(2* *4+3)4+3)* *4 4 =1044 =10442021-12-2315 【例【例5-25-2】有】有m m名学生，每人考名学生，每人考n n门功课，试写出求任一学生总分数门功课，试写出求任一学生总分数和任一课程总分数的数据结构和算法。和任一课程总分数的数据结构和算法。【解】把学生的考试成绩存放在【解】把学生的考试成绩存放在m m行行n n列的二维数组中，则第列的二维数组中，则第i(0i(0im)im)行第行第j(0j(0jn)jn)列中存放了第列中存放了第i i个学生的第个学生的第j j门课程考试成绩

19、。门课程考试成绩。即数据结构为：即数据结构为：#define M 10 /假设假设为为1010人人#define N 3 /假设假设为为3 3int scoreMN; /学生成绩二维数组学生成绩二维数组求第求第i i名学生总分数的算法为：名学生总分数的算法为：int student_sum(int scoreMN,int i) int j,sum=0; for(j=0;jN;j+) sum=sum+scoreij; return(sum); 2021-12-2316 求第求第j j门课程总分数的算法为：门课程总分数的算法为：int course_sum(int scoreMN,int j) i

20、nt i,sum=0; for(i=0;iM;i+) sum=sum+scoreij; return(sum); 2021-12-2317 矩阵是数值计算程序设计中经常用到的数学模型，它是矩阵是数值计算程序设计中经常用到的数学模型，它是由由 m m 行和行和 n n 列的数值构成（当列的数值构成（当m=n m=n 时称为方阵）。时称为方阵）。在高级在高级程序设计语言中程序设计语言中，通常用，通常用表示矩阵。然而表示矩阵。然而在数值分在数值分析过程中经常遇到一些比较特殊的矩阵，它们的阶数很高，析过程中经常遇到一些比较特殊的矩阵，它们的阶数很高，矩阵中元素数量很大，而且有很多元素的值相同或零值元素

21、，矩阵中元素数量很大，而且有很多元素的值相同或零值元素，如如对称矩阵对称矩阵、三角矩阵三角矩阵、带状矩阵带状矩阵和和稀疏矩阵稀疏矩阵等。等。为了节省为了节省存储空间并且加快处理速度，需要对存储空间并且加快处理速度，需要对这类矩阵这类矩阵进行压缩存储，进行压缩存储，压缩存储的原则压缩存储的原则是：是：。 2021-12-2318。 对称矩阵是一个对称矩阵是一个n n阶阶方阵。若一个方阵。若一个n n阶矩阵阶矩阵A A中的元素满足中的元素满足: : a ai i,j,j= =a aj j,I ,I (0i(0i，jn-1)jn-1)，则称则称A A为为n n阶对称矩阵。阶对称矩阵。 1 5 1 3

22、 7 a00 5 0 8 0 0 a10 a 11 1 8 9 2 6 a20 a21 a23 3 0 2 5 1 . 7 0 6 1 3 an-1 0 a n-1 1 a n-1 2 a n-1 n-1 对称矩阵对称矩阵2021-12-2319 在这个下三角矩阵中，第在这个下三角矩阵中，第i i行恰有行恰有i+1i+1个元素，元素总数为：个元素，元素总数为： ( (i+1)=n(n+1)/2i+1)=n(n+1)/2 由于对称矩阵中的元素关于主对角线对称，因此由于对称矩阵中的元素关于主对角线对称，因此可以为每一可以为每一对对称的矩阵元素分配对对称的矩阵元素分配 1 1 个存储空间，个存储空间

23、，n n阶矩阵中的阶矩阵中的n nn n个元素个元素就可以被压缩到就可以被压缩到 n(n+1)/2n(n+1)/2 个元素的存储空间中去。个元素的存储空间中去。 称一维数组称一维数组sa0.n(n+1)/2 为为n 阶对称矩阵阶对称矩阵A的压缩存储。的压缩存储。其存储对应关系如上图其存储对应关系如上图 : : k 0 1 2 3 4 n(n+1)/2-1a0,0 a1,0 a1,1 a2,0 a2,1 an-1,0 an-1,n-1Sak隐 含 元 素a0,1 a0,2 a0,n-1 对称矩阵的压缩存储对称矩阵的压缩存储 2021-12-2320其中，其中，sbn(n+1)/2中存放常数中存放

24、常数c或或0。 2021-12-2321常见的有三对角矩阵、五对角矩阵、七对角矩阵等。常见的有三对角矩阵、五对角矩阵、七对角矩阵等。具有具有3条非零对角线的对角矩阵条非零对角线的对角矩阵 66655655544544433433322322211211100100000000000000000000000000000000aaaaaaaaaaaaaaaaaaa2021-12-2322 ：对特殊矩阵的压缩存储实质上就是将二维矩阵中的部分：对特殊矩阵的压缩存储实质上就是将二维矩阵中的部分元素按照某种方案排列到一维数组中，不同的排列方案也就对应元素按照某种方案排列到一维数组中，不同的排列方案也就对应

25、不同的存储方案。不同的存储方案。2021-12-23235.2.2 稀疏矩阵的压缩存储方法稀疏矩阵的压缩存储方法 如果一个矩阵中有很多元素的值为零，即零元素的个数远远如果一个矩阵中有很多元素的值为零，即零元素的个数远远大于非零元素的个数时，称该矩阵为稀疏矩阵。大于非零元素的个数时，称该矩阵为稀疏矩阵。 根据存储时所附加信息的不同，稀疏矩阵的顺序存储方法包根据存储时所附加信息的不同，稀疏矩阵的顺序存储方法包括：三元组表示法、带辅助行向量的二元组表示法和伪地址表示括：三元组表示法、带辅助行向量的二元组表示法和伪地址表示法，其中以三元组表示法最常用。法，其中以三元组表示法最常用。 三元组表示法就是在

26、存储非零元的同时，存储该元素所对应三元组表示法就是在存储非零元的同时，存储该元素所对应的行下标和列下标。稀疏矩阵中的每一个非零元素由一个三元组的行下标和列下标。稀疏矩阵中的每一个非零元素由一个三元组( (i i，j j，a aijij) )唯一确定。矩阵中所有非零元素存放在由三元组组唯一确定。矩阵中所有非零元素存放在由三元组组成的数组中。成的数组中。 由由线性表的两种不同存储结构可以得到稀疏矩阵压缩的不同线性表的两种不同存储结构可以得到稀疏矩阵压缩的不同的存储方法。的存储方法。 2021-12-2324 假设有一个假设有一个6 67 7阶稀疏矩阵阶稀疏矩阵A A，其元素情况以及非零元对应其元素

27、情况以及非零元对应的三元组表（以行序为主序）如图所示。的三元组表（以行序为主序）如图所示。 0 0 1 0 0 0 0 0 2 0 0 0 0 0A67 = 3 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 7 4 0 6 7 71 0 2 12 1 1 23 2 0 34 3 3 55 4 4 66 5 5 77 5 6 4序号 行 列 值 (a) 稀疏矩阵稀疏矩阵 (b) 三元组表示三元组表示 三元组表中的第一行分别表示稀疏矩阵三元组表中的第一行分别表示稀疏矩阵A A的行数、列数和非零的行数、列数和非零元的个数。元的个数。显然，非零元素

28、的三元组是按行号递增的顺序、相同显然，非零元素的三元组是按行号递增的顺序、相同行号的三元组按列号递增的顺序排列的。行号的三元组按列号递增的顺序排列的。2021-12-23251 1三元组顺序表三元组顺序表 假设以行序为主序，且以一维数组作为三元组表的存储结构，假设以行序为主序，且以一维数组作为三元组表的存储结构，可以得到稀疏矩阵的一种压缩存储方法，称为三元组顺序表。三可以得到稀疏矩阵的一种压缩存储方法，称为三元组顺序表。三元组顺序表的数据结构定义如下：元组顺序表的数据结构定义如下：#define NUM 100 /矩阵中非零元素最大个数矩阵中非零元素最大个数typedef struct /三元

29、组结构三元组结构 int r, c; /行行(列列)号号 ElemType d; /元素值元素值 tupletype; /三元组定义三元组定义typedef struct int rows; /矩阵行数值矩阵行数值 int cols; /矩阵列数值矩阵列数值 int nums; /非零元素个数非零元素个数 tupletype dataNUM; /三元组表三元组表 table; /三元组顺序表定义三元组顺序表定义 2021-12-2326 1稀疏矩阵的转置运算稀疏矩阵的转置运算 转置是矩阵中最简单的一种运算。转置是矩阵中最简单的一种运算。 对于一个对于一个m mn n的矩阵其转置矩阵是一个的矩阵

30、其转置矩阵是一个n nm m的矩阵，设为的矩阵，设为B Bn nm m 且满足且满足a ai i ,j ,j= =b bj j,i ,i 即：即：aij=bjiaij=bji，其中：其中：00im-1im-1，0jn-10jn-1 即即A A的行是的行是B B的列，的列，A A的列是的列是B B的行。的行。稀疏矩阵的三元组表稀疏矩阵的三元组表2021-12-2327三元组表示的稀疏矩阵的转置常用的算法有以下两种：三元组表示的稀疏矩阵的转置常用的算法有以下两种：1 1）矩阵的列序转置）矩阵的列序转置（传统的转置算法）（传统的转置算法）矩阵矩阵A是按行序为主序存储的，若按列序为主序进行转置就可以是

31、按行序为主序存储的，若按列序为主序进行转置就可以得到得到A阵的转置矩阵阵的转置矩阵B。假设矩阵假设矩阵A的三元组存入一维数组中，只的三元组存入一维数组中，只要在数组中按三元组的列域要在数组中按三元组的列域cols的值开始扫描，从第的值开始扫描，从第0列至第列至第n-1列列，依序将三元组列域与行域之值对换，并顺次存人数组，依序将三元组列域与行域之值对换，并顺次存人数组mb中。算中。算法如下：法如下：int transpose(table ma,table mb) int i,j,k=0,n,t; if(ma.nums=0)return(0)； /矩阵中无非零元素矩阵中无非零元素 m=ma.row

32、s; /m为矩阵为矩阵A的列数的列数 n=ma.cols; /n为矩阵为矩阵A的行数的行数 t=ma.nums; /为矩阵中非零元素个数为矩阵中非零元素个数 mb.rows=n; /转置矩阵转置矩阵B的列数的列数 mb.cols; /转置矩阵转置矩阵B的行数的行数 mb.nums=t; /转置矩阵中的非零元素个数转置矩阵中的非零元素个数 for(i=0;in;i+) /按矩阵按矩阵A的列序扫描的列序扫描 2021-12-2328for(j=0;jt;j+) if(ma.dataj.c=i) /判断第判断第j个三元组是不是第个三元组是不是第i列的列的 mb.datak.r=ma.dataj.c;

33、 mb.datak.c=ma.dataj.r; mb.datak+.d=ma.dataj.d; return(1); /成功完成矩阵转置成功完成矩阵转置 以上算法的时间复杂度分析：以上算法的时间复杂度分析：若若n n为转置矩阵的列数，为转置矩阵的列数，t t为矩阵为矩阵中非零元素个数，则算法的时间花费主要在两个循环上，所以若中非零元素个数，则算法的时间花费主要在两个循环上，所以若时间复杂度为时间复杂度为O(nO(nt)t)。也就是说，时间的花费和矩阵也就是说，时间的花费和矩阵A A的列数和的列数和非零元素个数的乘积成正比。若用非零元素个数的乘积成正比。若用m mn n的二维数组表示矩阵，则的二

34、维数组表示矩阵，则相应的矩阵转置算法的循环为：相应的矩阵转置算法的循环为：for ( i=0for ( i=0；i in n；i+ )i+ ) for (j=0 for (j=0；j jm m；j+j+ bij=aji bij=aji； 此时，时间复杂度为此时，时间复杂度为O(mn) 。2021-12-23292 2）快速转置算法：）快速转置算法： 三元组顺序表虽然节省了存储空间，但时间复杂度比三元组顺序表虽然节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算是法一般矩阵转置的算法还要复杂，同时还有可能增加算是法的难度。因此，此算法仅适用于的难度。因此，此算法仅适用于

35、t=mt=m* *n n的情况。的情况。 其算法思想为：对其算法思想为：对A A扫描一次，按扫描一次，按A A第二列提供的列号一第二列提供的列号一次确定位置装入次确定位置装入B B的一个三元组。具体实施如下：一遍扫描的一个三元组。具体实施如下：一遍扫描先确定三元组的位置关系，二次扫描由位置关系装入三元先确定三元组的位置关系，二次扫描由位置关系装入三元组。可见，位置关系是此种算法的关键。组。可见，位置关系是此种算法的关键。 为了预先确定矩阵为了预先确定矩阵M M中的每一列的第一个非零元素在数组中的每一列的第一个非零元素在数组T T中中应有的位置，需要先求得矩阵应有的位置，需要先求得矩阵M M中的

36、每一列中非零元素的个数。中的每一列中非零元素的个数。因为矩阵因为矩阵M M中第一列的第一个非零元素在数组中第一列的第一个非零元素在数组T T中应有的位置等于中应有的位置等于前一列第一个非零元素的位置加上前列非零元素的个数。前一列第一个非零元素的位置加上前列非零元素的个数。2021-12-2330为此，需要设置两个一维数组为此，需要设置两个一维数组num0.nnum0.n和和rposrpos0.n0.n：num0.nnum0.n：统计统计M M中每列非零元素的个数。中每列非零元素的个数。rposrpos0.n0.n：M M中的每列第一个非零元素在中的每列第一个非零元素在T T中的位置。中的位置。

37、算法通过算法通过rposrpos数组建立位置对应关系：数组建立位置对应关系： rposrpos0=0 0=0 ； rpos rpos colcol=rposrpos colcol-1+num-1+numcolcol-1 0-1 0colcolM.rowsM.rows；例如图例如图5-4(5-4(a) a) 所示的稀疏矩阵的三元组表对应的所示的稀疏矩阵的三元组表对应的num0.n-1num0.n-1和和rposrpos0.n-10.n-1如图如图5-55-5所示。所示。 （算法见教科书）（算法见教科书）图图5-5 5-5 矩阵的矩阵的numnum和和rpos rpos 数组值数组值Col 0 1

38、 2 3 4 5 6numcol 1 1 1 1 1 1 1rposcol 0 1 2 3 4 5 62021-12-2331快速转置算法如下：快速转置算法如下： void fasttranstri(tritupletable b,tritupletable a) int p,q,col,k; int num0.a.n,copt0.a.n; b.m=a.n; b.n=a.m; b.t=a.t; if(b.t=0) printf(“a=0”n); for(col=1;col=a.u;+col) numcol=0; for(k=1;k=a.t;+k) +numa.datak.j; cpot0=1;

39、 for(col=2;col=a.t;+col) cpotcol=cpotcol-1+numcol-1;for(p=1;p=a.t;+p) col=a.datap.j; q=cpotcol; b.dataq.i=a.datap.j; b.dataq.j=a.datap.i; b.dataq.v=a.datap.v; +cpotcol; 2021-12-2332带行表的三元组带行表的三元组) ) 有时为了方便某些矩阵运算，在按行优先存储的三元组有时为了方便某些矩阵运算，在按行优先存储的三元组中，加入一个行表来记录稀疏矩阵中每行的非零元素在三元中，加入一个行表来记录稀疏矩阵中每行的非零元素在三元组

40、表中的起始位置。当将行表作为三元组表的一个新增属性组表中的起始位置。当将行表作为三元组表的一个新增属性加以描述时，就得到了稀疏矩阵的另一种顺序存储结构：带加以描述时，就得到了稀疏矩阵的另一种顺序存储结构：带行表的三元组表。行表的三元组表。称这种称这种“带行链接信息带行链接信息”的三元组表为行逻的三元组表为行逻辑链接的顺序表。辑链接的顺序表。其类型描述如下：其类型描述如下： # #definedefine maxrow maxrow 100 100 typedef struct typedef struct triple data triple datamaxsizemaxsize; int r

41、pos int rpos maxrowmaxrow; int int n,m,t; n,m,t; rtripletable rtripletable 2021-12-2333 下面讨论两个稀疏矩阵相乘的例子，容易看出这种表示下面讨论两个稀疏矩阵相乘的例子，容易看出这种表示方法的优越性：方法的优越性： 若设若设 Q=M*N 其中，其中，M是是m1*n1矩阵，矩阵，N是是m2*n2矩阵。矩阵。 当当n1=m2时有：时有： for(i=1;i=m1;+i) for(j=1;j=n2;+j) qij=0 for(k=1;k(N)?(M)：(N) /矩阵行列较大者矩阵行列较大者typedef struc

42、t mtxn int row； int col； struct mtxn *right，*down； union int value； struct mtxn *next； tag； MatNode； 2021-12-2342 广义表也是线性表的推广，是一种多层次的线性结构，广义表也是线性表的推广，是一种多层次的线性结构，线性表线性表中的元素仅限于原子项，即不可以再分；中的元素仅限于原子项，即不可以再分； 而广义表中的元素既可以是原子项，也可以是子表（另一个线而广义表中的元素既可以是原子项，也可以是子表（另一个线性表）。性表）。主要用于人工智能领域的表处理语言主要用于人工智能领域的表处理语言L

43、ISPLISP语言。语言。 广义表是广义表是n0个元素个元素a1，a2，an的有限序列，其中每一个的有限序列，其中每一个ai或者是原子，或者是一个子表。广义表通常记为或者是原子，或者是一个子表。广义表通常记为LS=(a1,a2,an)，其中其中LS为广义表的名字，为广义表的名字，n为广义表的长度，为广义表的长度， 每一个每一个ai为广义表为广义表的元素。但在习惯中，一般用大写字母表示广义表，小写字母的元素。但在习惯中，一般用大写字母表示广义表，小写字母表示原子。表示原子。 若若n=0n=0时为空表。记作：时为空表。记作：L=( )L=( )。 2021-12-2343 当广义表当广义表L L非

44、空非空( (n n0)0)时，第一个数据元素时，第一个数据元素a a0 0被称为广义表的表被称为广义表的表头头( (head)head)，其余数据元素组成的表其余数据元素组成的表( (a a1 1，a an-1n-1) ) 被称为广义表被称为广义表L L的的表尾表尾( (tail)tail)，分别记为分别记为head(A)= ahead(A)= a0 0，tail=(atail=(a1 1，a an-1n-1) )。 因此：一个广义表是由表头和表尾构成的。因此：一个广义表是由表头和表尾构成的。 1）A=( ) A=( ) A为空表，长度为为空表，长度为0。 2 2）B=(e) B=(e) B

45、B是一个只含有原子是一个只含有原子e e的表，其长度为的表，其长度为l l； 。 3 3）C=(aC=(a，(b(b，c c，d) d) C是长度为是长度为2的广义表，第一项为原子，第二项为子表。的广义表，第一项为原子，第二项为子表。 4 4）D= (AD= (A，B B，C)=()C)=()，(e)(e)，(a(a，(b(b，c c，d)d) 5 5）E=(E=( a a，( (a a，b b) )，( (， ) ) ) ) E E 中只含有一个元素，该元素是一个表，中只含有一个元素，该元素是一个表，E E的长度为的长度为l l。 6 6）F=(aF=(a，F)=(aF)=(a，(a(a，(

46、a(a，.).) F F是长度为是长度为2的广义表，第一项为原子，第二项为它本身。的广义表，第一项为原子，第二项为它本身。 2021-12-23443广义表的表示方法（用广义表的表示方法（用次序关系和层次关系表示）次序关系和层次关系表示）（1）用）用L=(a1，a2，an)形式，其中每一个形式，其中每一个ai为原子或广义表为原子或广义表 例如：例如：A=(b,c) B=(a,A) E=(a,E)都是广义表。都是广义表。 （2）将广义表中所有子表写成原子形式，并利用圆括号嵌套）将广义表中所有子表写成原子形式，并利用圆括号嵌套例如，广义表例如，广义表A、B、C可以描述为：可以描述为： A(b,c)

47、 B(a,A(b,c) E(a,E(a,E（）) （3）将广义表用树和图来描述将广义表用树和图来描述 （层次关系）层次关系） 上面提到的广义表上面提到的广义表A、B、C的描述见图的描述见图5-8。 （次序关系）（次序关系）2021-12-2345 广义表中数据元素的最大层次为表的深度。数据元素的层次广义表中数据元素的最大层次为表的深度。数据元素的层次就是包括该元素韵括号对就是包括该元素韵括号对 的数目。例如广义表的数目。例如广义表G=(a，b，(c，(d)中，数据元素中，数据元素a，b在第一层，数据元素在第一层，数据元素c在第二层，数据元在第二层，数据元素素d在第三层，广义表在第三层，广义表G

48、的深度为的深度为3。 （次序关系）（次序关系）eabcdabcdeabbcaaEDABCCBA图图 5-8 广义表的图形表示广义表的图形表示 从图从图5-8可以看出：广义表的图形表示像倒着画的一棵树，可以看出：广义表的图形表示像倒着画的一棵树，树根结点代表整个广义表，各层树枝结点代表相应的子表，树叶树根结点代表整个广义表，各层树枝结点代表相应的子表，树叶结点代表单元素或空表（如结点代表单元素或空表（如A表）。表）。 2021-12-2346 一个广义表的深度是指该广义表一个广义表的深度是指该广义表展开后所含展开后所含的的。例如，例如，A=(b,c)的深度为的深度为1，B=(A,d)的深度为的深

49、度为2，C=(f,B,h)的深度为的深度为3;广义表兼有线性结构和层次结构的特性，归纳如下：广义表兼有线性结构和层次结构的特性，归纳如下：(1) (1) 广义表中的数据元素有固定的相对次序；广义表中的数据元素有固定的相对次序；(2) (2) 广义表的长度定义为最外层括弧中包含的数据元素个数；广义表的长度定义为最外层括弧中包含的数据元素个数；(3) (3) 广义表的深度定义为广义表书写形式中括弧的最大重数，因此广义表的深度定义为广义表书写形式中括弧的最大重数，因此空表的深度为空表的深度为1 1，因为一个单元素不是广义表，所以从定义上讲没有，因为一个单元素不是广义表，所以从定义上讲没有深度可言，但

50、可以认为它的深度为深度可言，但可以认为它的深度为0 0；(4) (4) 广义表可被其它广义表所共享。例如上述例子中广义表广义表可被其它广义表所共享。例如上述例子中广义表B B同时也同时也是广义表是广义表 D D 中的一个子表；中的一个子表； (5) 广义表可以是一个自递归的表。例如上述例子中的广义表广义表可以是一个自递归的表。例如上述例子中的广义表 F，自递归的广义表的长度是个有限值，而深度为无限值。自递归的广义表的长度是个有限值，而深度为无限值。 2021-12-2347 5广义表的分类广义表的分类（1）线性表：元素全部是原子的广义表。）线性表：元素全部是原子的广义表。（2）纯表：与树对应的

51、广义表，见图）纯表：与树对应的广义表，见图5-8的的(c) 、(d)、 (e) 。（3）再入表：与图对应的广义表再入表：与图对应的广义表(允许结点共享允许结点共享)，（4）递归表：允许有递归关系的广义表，例如递归表：允许有递归关系的广义表，例如E=(a,E)。 这四种表的关系满足：递归表这四种表的关系满足：递归表 再入表再入表 纯表纯表 线性表线性表 BACbacAbcBaAbc再入表再入表2021-12-2348 5.3.2 广义表的存储结构由于广义表的元素类型不一定相同，由于广义表的元素类型不一定相同，表中的数据元素可以是单元素表中的数据元素可以是单元素（原子项），也可以是广义表，（原子项

52、），也可以是广义表，因此，难以用顺序结构存储表中元因此，难以用顺序结构存储表中元素，通常采用链接存储方法来存储广义表中元素，并称之为广义链素，通常采用链接存储方法来存储广义表中元素，并称之为广义链表。表。需要两种结构的结点：需要两种结构的结点：(1) (1) 表结点：用以表示广义表。由三个域组成：标志域表结点：用以表示广义表。由三个域组成：标志域tagtag、指向指向表头的指针域表头的指针域sublistsublist和指向下一个结点的指针域和指向下一个结点的指针域linklink。如图如图5-9(5-9(a)a)所示。所示。 (2) 原子结点：用以表示原子项。由三个域组成：标志域原子结点：用

53、以表示原子项。由三个域组成：标志域tag、值域值域data和指向下一个元素结点的指针域和指向下一个元素结点的指针域link。如图如图5-9(b)所示。所示。 tag=1 sublist link tag=0 data link（a）表结点（b）元素结点2021-12-2349 每个数据元素都可用表结点或原子结点表示。它们的主要区别每个数据元素都可用表结点或原子结点表示。它们的主要区别在于从不同的角度反映广义表的构成。在于从不同的角度反映广义表的构成。 例如，广义表例如，广义表C的链表存储结构如图的链表存储结构如图5-10所示。所示。 1 0 a1 0 b0 c0 d C图图 5-10 广义表广

54、义表(a,(b,c,d)的链表存储结构图的链表存储结构图 二叉树二叉树2021-12-2350广义表的链式结构描述如下：广义表的链式结构描述如下：typedef char ElemType;typedef struct glnode int tag; union ElemType data; struct glnode *sublist; val; struct glnode *link; GListNode; 可将一个广义表看成一棵树，为了方便存储，通常将其转换可将一个广义表看成一棵树，为了方便存储，通常将其转换成一棵二叉树成一棵二叉树 。广义表广义表C转换成二叉树过程转换成二叉树过程 如图

55、如图5-11所示：所示： 2021-12-2351acbd(a)广 义 表 的 图 形 表 示abddCC(b)转 换 后 的 树广义表广义表C C图图5-11 广义表的转换过程广义表的转换过程 2021-12-2352 广义表的基本操作主要有：广义表的基本操作主要有： 求广义表的长度和深度、向广求广义表的长度和深度、向广义表插入元素和从广义表中查找或删除元素、建立广义表的存储义表插入元素和从广义表中查找或删除元素、建立广义表的存储结构、输出广义表和复制广义表等。结构、输出广义表和复制广义表等。 由于广义表是一种递归的数据结构，所以对广义表的运算一由于广义表是一种递归的数据结构，所以对广义表的

56、运算一般采用递归的算法。般采用递归的算法。 在广义表中，同一层次的每个结点是通过在广义表中，同一层次的每个结点是通过1ink域链接起来的，域链接起来的，可把它看做是由可把它看做是由1ink域链接起来的单链表。域链接起来的单链表。 求广义表的长度就变成求单链表的长度，求广义表的长度就变成求单链表的长度，则它的深度可以递则它的深度可以递归求出。归求出。2021-12-2353求广义表长度的递归算法如下：求广义表长度的递归算法如下： int GListLength(GListNode *h) /h为一个广义表头结点的指针为一个广义表头结点的指针 int n=0; h=h-val.sublist; /

57、h指向广义表的第一个元素指向广义表的第一个元素 while(h!=NULL) n+; h=h-link; return n;广义表深度的递归定义是：它等于所有子表中表的最大深度加广义表深度的递归定义是：它等于所有子表中表的最大深度加1 1。若一个表为空或仅由单元素所组成，则深度为若一个表为空或仅由单元素所组成，则深度为l l。求广义表深度求广义表深度的递归函数的递归函数GListDepth()GListDepth()如下：如下： 2021-12-2354 1 h为空表为空表 GListDepth(h)= maxGListDepth(sh)|sh为为h的子表的子表+1 其它情况其它情况 int

58、GListDepth(GListNode *h) /h为广义表头结点的为广义表头结点的sublist域值或为不带头结点的广义表域值或为不带头结点的广义表 int max=0,dep; /max中存放子表的最大深度中存放子表的最大深度 while(h!=NULL) /遍历表中的每一个结点遍历表中的每一个结点 if(h-tag=1) /只需要求出子表深度即可，单元素深度为只需要求出子表深度即可，单元素深度为0 dep=GListDepth(h-val.sublist); /递归调用求出子表的深度递归调用求出子表的深度 if(depmax) /让让max始终为同一层所求过的子表中深度的最大值始终为同

59、一层所求过的子表中深度的最大值 max=dep; h=h-link; /使使h指向同一层的下一个结点指向同一层的下一个结点 return max+l; /返回表的深度返回表的深度 2021-12-2355假设广义表以单链表的形式存储，广义表的元素类型假设广义表以单链表的形式存储，广义表的元素类型elemtype 为为字符型字符型char，广义表由键盘输入，假定全部为字母，输入格式为：广义表由键盘输入，假定全部为字母，输入格式为：元素之间用逗号分隔，表元素的起止符号分别为左、右圆括号，元素之间用逗号分隔，表元素的起止符号分别为左、右圆括号，空表在其圆括号内使用一个空表在其圆括号内使用一个“#”字

60、符表示，最后使用一个分号字符表示，最后使用一个分号作为整个广义表的结束。作为整个广义表的结束。 例如例如“( (a a，(b(b，c c，d)d)”，就是一个符合上述规定的广义表格就是一个符合上述规定的广义表格式（注意：不包括引号）。式（注意：不包括引号）。建立广义表存储结构的算法同样是一个递归算法。建立广义表存储结构的算法同样是一个递归算法。 2021-12-2356 建立广义表的算法如下：建立广义表的算法如下：GListNode *GListCreat(char *s) GListNode *h; char ch; ch=*s; /取一个扫描字符取一个扫描字符 s+; /串指针后移一位串指