数组和广义表

1、关于数组与广义表第一张，PPT共八十五页，创作于2022年6月第5章 数组与广义表 本章主要内容一、数组的存储结构及其地址变换二、特殊矩阵的压缩存储及其地址变换三、稀疏矩阵的存储结构与算法四、广义表的存储结构与算法第二张，PPT共八十五页，创作于2022年6月5.1 数组 数组是线性表的直接推广 。如果线性表的元素又是具有相同数据类型的线性表，这种线性表就是二维数组，若在二维数组中，元素还是线性表，即得到三维数组，依次类推可以得到n维数组。 本节主要讨论数组的有关概念、存储结构及地址变换。 第三张，PPT共八十五页，创作于2022年6月511 数组类型与存储结构一、二维数组 一个m行n列的二维

2、数组如下表所示： 第四张，PPT共八十五页，创作于2022年6月数组类型与存储结构 令i =（ai1，ai2，ai,n）(i=1,2,m) ，每行作为一个元素，则A=(1 ,2 ,m) 是一个元素为线性表的线性表。若令j = (a1j，a2j，am j)T (j=1,2,n),每列作为一个元素，则A=(1,2,n)也是一个元素为线性表的线性表。基于这一原因，而把数组看成是线性表的推广。 第五张，PPT共八十五页，创作于2022年6月数组类型与存储结构 数组是一个具有固定格式、固定个数的数据元素构成的有序集合，每一个数据元素有唯一的一对下标标识（i，j），因此，在数组中不能做插入、删除操作。在高

3、级语言中，数组一旦被定义，每一维的下标上下界都不能改变。对数组可以施加的操作主要有以下两种：（1）取值操作：给定下标，读其对应的数据元素。（2）赋值操作：给定下标，存储或修改与其相对应的数据元素。 第六张，PPT共八十五页，创作于2022年6月数组类型与存储结构 由含n个下标（0jibi1，i=1,2,n）且具有相同类型的 个数据元素构成的集合称为一个n维数组，bi称为第i维的长度。数组中的每个元素对应于一组下标（ ），受到n个关系的约束。固定n-1个下标，让另一个下标变换就是一个一维数组。在n个关系中，对于任意元素（0jibi2）都有一个直接后继。n维数组的ADT定义。 只包含4种操作： I

4、nitArray(&A，n，b1，b2，,bn)：初始化数组。 DestroyArray(&A)：撤销数组。 Value(A，&e，j1，j2，jn)。取某个数据元素的值 Assign(&A，e，j1，j2，jn)：为数据元素赋值。 第七张，PPT共八十五页，创作于2022年6月数组的内存映象一、二维数组的存储结构及地址变换1、以行为主序顺序存储。用一块连续存储空间逐行顺序存储数组元素。例如：一个mn数组按行存储表示如下图： 第八张，PPT共八十五页，创作于2022年6月数组的内存映象2、以列为主序顺序存储。用连续存储空间逐列顺序存储数组元素。例如：mn数组按列顺序存储，如下图所示：第九张，P

5、PT共八十五页，创作于2022年6月512 数组的内存映象3、地址变换设二维数组Amn顺序存储在连续区域中，基地址为LOC(a11)，每个数组元素占据L个地址单元，现在考察由元素aij的下标求其存储地址的计算公式为：对于“以行为主序”的存储方式，因为数组元素aij的前面有i-1行，每一行有n个元素数，在第i行中，它的前面还有j-1个元素，所以有： LOC(aij) = LOC(a11) + ( (i-1)n + j-1 )L 。在C语言中，对数组的每一维下标，规定下界从0开始，所以可改为：LOC(aij) = LOC(a00) + ( in + j )L。第十张，PPT共八十五页，创作于202

6、2年6月数组的内存映象对于“以列为主序”的存储方式，数组元素aij的前面有j-1列，每一列有m个元素数，在第j列中，它的前面还有i-1个元素，所以有： LOC(aij) = LOC(a11) + ( (j-1)m + i-1 )L。当下界从0开始是，应改为：LOC(aij) = LOC(a00) + ( jm + i )L。对一般的二维数组，设数组Ac1.d1 c2.d2，下标的上、下界可以是任何整数，则aij的物理地址计算公式为：行主序：LOC(aij)=LOC(a c1 c2)+( (i- c1)( d2 - c2 + 1)+ (j- c2) )L。列主序：LOC(aij)=LOC(a c

7、1 c2)+( (j- c2)( d1 c1 + 1)+ (i- c1) )L。 第十一张，PPT共八十五页，创作于2022年6月数组的内存映象二、n维数组 LOC( )=LOC( )+(d2-c2+1)(d3-c3+1)(dn-cn+1)(j1-c1 )+(d3-c3+1)(d4-c4+1)(dn-cn+1)(j2-c2) +(dn-cn+1)jn-1-cn-1) + (jn-cn )L= LOC( ) + ( )L例如：三维数组Amnp，元素aijk其物理地址为：LOC(aijk)=LOC(a111)+( ( i-1)np+ (j-1)p +k-1)L 第十二张，PPT共八十五页，创作于2

8、022年6月数组的内存映象举例。若矩阵Amn 中存在某个元素aij满足：aij是第i行中最小值且是第j列中的最大值，则称该元素为矩阵A的一个鞍点。试编写一个算法，找出A中的所有鞍点。解决此问题的基本思想是：在矩阵A中求出每一行的最小值元素，然后判断该元素它是否是它所在列中的最大值，是则打印出，否则不输出，接着处理下一行。设矩阵A用一个二维数组表示。 第十三张，PPT共八十五页，创作于2022年6月数组的内存映象算法如下：void saddle (int A ,int m, int n) / m,n是矩阵A的行数和列数 int i,j,min; for (i=0;im;i+) / 按行处理 mi

9、n=Ai0; for (j=1; jn; j+) if (Aijmin ) min=Aij; k=j; / 找第i行最小值 for (p=0;papk; p+) / 检测该行中的每一个最小值是否是鞍点 if ( p=m) printf (%d,%d,%dn, i ,k,min); / if /for/ 第十四张，PPT共八十五页，创作于2022年6月5.2 特殊矩阵的压缩存储521 对称矩阵一、对称矩阵的压缩存储对称矩阵：n阶方阵中，若aij=aji，其中1i,jn，则称该矩阵为对称矩阵。如下图所示的矩阵是一个阶对称矩阵。第十五张，PPT共八十五页，创作于2022年6月特殊矩阵的压缩存储对称矩

10、阵的元素关于主对角线对称，因此只需存储上三角或下三角部分即可。例如：上图（a）给出的5阶对称矩阵存储到一个一维数组如下图（b）所示。第十六张，PPT共八十五页，创作于2022年6月对称矩阵的压缩存储将一个对称矩阵只存储下三角（或上三角）部分的元素aij，此时有ji且1in，对于上三角部分的元素aij和它对应的aji相等，因此当访问的元素在上三角时，直接去访问与其对应的下三角元素即可。这样，原来需要n2个存储单元，现在只需要 个，可节约 个存储单元。第十七张，PPT共八十五页，创作于2022年6月对称矩阵的压缩存储采用以行为主序的方法顺序存储到一个一维数组中。因为下三角中共有个 元素，设存储结构

11、为一维数组。A ，如下图所示。 第十八张，PPT共八十五页，创作于2022年6月对称矩阵的压缩存储二、地址变换设矩阵的下三角部分的元素aij，下标满足条件：ij且1in，存储到一维数组A的第k个元素Ak中， 则有： 第十九张，PPT共八十五页，创作于2022年6月522 三角矩阵一、下三角矩阵的压缩存储形如下图所示的矩阵称为下三角矩阵。主对角线上方所有元素等于同一个常数C。第二十张，PPT共八十五页，创作于2022年6月一、下三角矩阵的压缩存储下三角矩阵的压缩存储与对称矩阵的压缩存储类似。例如：下图所给给出一个下三角矩阵存储结构。第二十一张，PPT共八十五页，创作于2022年6月下三角矩阵的压

12、缩存储下三角矩阵压缩存储的地址变换用一维数组A 。存储下三角矩阵。如下图所示： 设aji 存放在Ak中，则k与i、j的对应关系有如下公式：当ij时， k= 当ij 时第二十四张，PPT共八十五页，创作于2022年6月523 带状矩阵n阶矩阵A称为带状矩阵，如果存在最小正数m，满足当i-jm时，aij =0，这时称w=2n-1为矩阵A的带宽。例如下图是一个w=3(m=2)的带状矩阵。 第二十五张，PPT共八十五页，创作于2022年6月带状矩阵带状矩阵A采用压缩存储有两种方法。第一种方法：将A压缩到一个n行w列的二维数组B中，如下图所示。当某行非零元素的个数小于带宽w时，先存放非零元素然后补零。第

13、二十六张，PPT共八十五页，创作于2022年6月带状矩阵另一种压缩方法是将带状矩阵压缩到一维数组中去，按以行为主序存储，顺序存放非零元素，如下图所示，按此规律，可得到相应的映象函数。如当w=3时，映象函数为：k=2（i-1)+j-1 第二十七张，PPT共八十五页，创作于2022年6月5.3 稀疏矩阵当m*n矩阵中有t个非零元素且tm*n时，这样的矩阵称为稀疏矩阵。 稀疏矩阵压缩存储方法是仅存放非零元素。由于非零元素分布没有规律，为了能找到相应的元素，所以仅存储非零元素的值是不够的，还必须记下它们所在的行号和列号。为此采取如下方法：将非零元素所在的行、列以及它的值构成一个三元组（i,j,v），然

14、后将这些三元组按某种规律顺序存储，这种方法可以节约大量的存储空间。 第二十八张，PPT共八十五页，创作于2022年6月稀疏矩阵稀疏矩阵的ADT定义对稀疏矩阵的操作只定义一下8种：创建稀疏矩阵。 CreareSMatrix（&M）撤销稀疏矩阵。 DetroySMatrix（&M）输出稀疏矩阵。 PrintSMatrix（M）复制稀疏矩阵。 CopySMatrix（M , &T）稀疏矩阵加法。 AddSMatrix（M , N , &T）稀疏矩阵减法。 SubtractSMatrix（M , N , &T）稀疏矩阵乘法。MultSMatrix（M , N , &T）稀疏矩阵转置。 Transpos

15、eSMatrix（M , &T）第二十九张，PPT共八十五页，创作于2022年6月531 稀疏矩阵的三元组存储与转置、乘法一、稀疏矩阵的三元组存储表示 将稀疏矩阵每个非0元素的值以及行下标、列下标构成的三元组按行优先顺序存储，同一行中列号按从小到大排列成一个线性表，称这种存储方法为三元组表示。例如，设稀疏矩阵如下图 (a)所示，对应的三元组存储结构如图 (b)所示。 第三十张，PPT共八十五页，创作于2022年6月稀疏矩阵的三元组存储与转置、乘法存储结构的定义：define MAXSIZE 1024 / 非0元素的个数数typedef struct / 定义三元组元素结构 int i , j;

16、 / 非零元素的行号和列号 ElemType e ; / 非零元素的值 Triple ; / 三元组类型typedef struct SPNode dataMAXSIZE+1; / 三元组顺序表int mu , nu , tu ; / 矩阵的行、列及非零元素的个数 TSMatrix ; / 三元组表的存储类型 第三十一张，PPT共八十五页，创作于2022年6月稀疏矩阵的三元组存储与转置、乘法二、稀疏矩阵的算法实现1矩阵的转置设TSMatrix A表示一个mn的稀疏矩阵，其转置TSMatrix B是一个nm的稀疏矩阵。转置算法基本思想：A的行、列转化成B的列、行；在A.data中依次找第一列的、

17、第二列的、直到最后一列，并将找到的每个三元组的行、列交换后顺序存储到B.data中。 第三十二张，PPT共八十五页，创作于2022年6月稀疏矩阵的三元组存储与转置、乘法算法描述如下：void TransposeSMatrix ( TSMatrix A , TSMatrix &B) B.mu=A.nu; B.nu=A.mu; B.tu=A.tu ; / 复制行、列数及元素个数 if ( B.tu ) / 有非零元素则转换 q=1; for ( col = 1; col = A.nu ; col+ ) / 按A的列序转换 for ( p=1; ptu0) return OK; / Transpos

18、eSMatrix 第三十三张，PPT共八十五页，创作于2022年6月稀疏矩阵的三元组存储与转置、乘法算法性能分析。设m、n是原矩阵的行数和列数，t是稀疏矩阵的非零元素个数。该算法的时间主要耗费在二重循环上，所以时间复杂性为O(n*t)。显然当非零元素的个数t和m*n同数量级时，算法的时间复杂度为O(m*n2)。与通常存储方式下矩阵转置算法相比，可能节约了一定量的存储空间，但算法的时间性能更差一些。 第三十四张，PPT共八十五页，创作于2022年6月稀疏矩阵的三元组存储与转置、乘法2带列逻辑连接的三元组顺序存储与改进的转置算法引入两个向量：numn+1和cpotn+1，其中numcol表示矩阵A

19、中第col列的非零元素的个数（为了方便下标均从1开始），cpotcol的初始值表示矩阵A中的第col列的第一个非零元素在B.data中的位置。于是cpot的初始值为：cpot1=1；cpotcol=cpotcol-1+numcol-1； 2coln 第三十五张，PPT共八十五页，创作于2022年6月稀疏矩阵的三元组存储与转置、乘法例如。下图（a）所给矩阵A的num和cpot的数组值如右图所示。改进的稀疏矩阵转置算法称为快速转置。算法思想：依次扫描A.data，当扫描到一个col列元素时，直接将其存放在B.data的cpotcol位置上，且cpotcol加，cpotcol中始终是下一个col列元

20、素在B.data中的位置。第三十六张，PPT共八十五页，创作于2022年6月稀疏矩阵的三元组存储与转置、乘法快速转置算法如下：Status FastTransposeSMatrix ( TSMatri x A , TSMatrix &B ) B.mu=A.nu ; B.nu=A.mu ; B.tu=A.tu ; / 稀疏矩阵的行、列及元素个数 if ( B.tu0 ) / 有非零元素则转换 for ( i = 1 ; i = A.nu ; i+ ) numi=0; for (i= 1 ; i = A.tu ; i+ ) / 求矩阵A中每一列非零元素的个数 j = A.datai.j ; num

21、j+; cpot1 = 1 ; / 求矩阵A中每一列第一个非零元素在B.data中的位置for ( i = 2 ; i = A.nu ; i+ ) cpoti= cpoti-1+numi-1; for ( i =1; i = A.tu ; i+) / 扫描三元组表 j =A.datai.j ; / 当前三元组的列号 k = cpotj ; / 当前三元组在B.data中的位置 B.datak.i = A.datai.j ; B.datak.j = A.datai.i ; B.datak.v = A.datai.v ;cpotj+; / for i / if (B.tu) return B; /

22、 返回的是转置矩阵的指针 / FastTransposeSMatrix 第三十七张，PPT共八十五页，创作于2022年6月稀疏矩阵的三元组存储与转置、乘法算法的时间复杂度分析：上述算法中有四个循环，分别执行n，t，n-1，t次，在每个循环中，每次迭代的时间是一个常量，因此总的计算量是O（n+t）。所需要的存储空间比前一个算法多了两个向量，空间复杂度为O（t）。 第三十八张，PPT共八十五页，创作于2022年6月2带行逻辑连接的三元组顺序存储与乘积算法已知稀疏矩阵A(m1 n1)和B(m2 n2)，求乘积C(m1 n2)。例如：稀疏矩阵A、B、C及它们对应的三元组顺序表A.data、B.data

23、、C.data如下图 (a)和(b)所示。 第三十九张，PPT共八十五页，创作于2022年6月带行逻辑连接的三元组顺序存储与乘积算法由矩阵乘法规则知：Ci，j=Ai,1B1,j+Ai,2B2,j+Ai,nBn,j =当A的元素Ai,k的列号与B的元素Bk,p的行号相等时才能相乘，且当两项都不为零时，乘积中的这一项才不为零。为运算方便设一个累加器：datatype tempn+1；用来存放当前行中cij的值，当前行中所有元素全部计算出之后，再存放到C.data中去。 第四十张，PPT共八十五页，创作于2022年6月带行逻辑连接的三元组顺序存储与乘积算法为了便于在B.data中寻找B中的第k行的第

24、一个非零元素，与前面类似，引入numn和rpotn两个向量。numk表示矩阵B中第k行的非零元素的个数；rpotk表示第k行的第一个非零元素在B.data中的位置。于是有：rpot1=1rpotk=rpotk-1+numk-1 2kn第四十一张，PPT共八十五页，创作于2022年6月带行逻辑连接的三元组顺序存储与乘积算法例如，下图（a）的矩阵B的其numn 和rpotn 的值如右边的表所示。k1234num k 2020cpot k 1335第四十二张，PPT共八十五页，创作于2022年6月带行逻辑连接的三元组顺序存储与乘积算法稀疏矩阵存储结构定义：# define MAXSIZE 1024

25、/ 稀疏矩阵非0元素最大个数# define MAXRC 100 / 稀疏矩阵的最大行数typedef struct / 定义带行逻辑连接的三元组顺序表类型 Triple data MAXSIZE+1 ; int rpotMAXRC+1 int mu , nu , tu ; RLSMatrix 稀疏矩阵乘法的算算步骤：初始化。清理一些单元，准备按行顺序存放乘积矩阵;求B的numn和rpotn数组值;做矩阵乘法。将A.data中三元组的列值与B.data中三元组的行值相等的非零元素相乘，并将具有相同下标的乘积元素相加。第四十三张，PPT共八十五页，创作于2022年6月带行逻辑连接的三元组顺序存储

26、与乘积算法稀疏矩阵乘法的算法描述：Status MatrixMultiply (RLSMatrix *A, RLSMatrix *B, RLSMatrix &C) / 求稀疏矩阵C=AB int p , q , i , j , k , r ; ElemType ctempn+1; int numB.nu+1; if (A.nu != B.mu) return ERROR ; / A的列与B的行不相等 C.mu = A.mu ; C.nu = B.nu ; C.tu = 0 ; if (A.tu*B.tu != 0 ) for ( i =1 ; i = B.mu ; i+ ) numi=0; /

27、 求矩阵B中每一行非零元素的个数for ( k =1 ; k = B.tu ; k+) i = B.datak.i ;numi+; rpot1=1; / 求矩阵B中每一行第一个非零元素在B.data中的位置for (i=2 ; i= B.mu ; i+ ) rpoti = rpoti-1 + numi-1 ;第四十四张，PPT共八十五页，创作于2022年6月带行逻辑连接的三元组顺序存储与乘积算法r = 0 ; / 当前C中非零元素的个数 p=1; / 指示A.data中当前非零元素的位置 for ( i= 1; i= A.mu; i+) for ( j =1 ; j = B.nu ; j+)

28、tempj=0; / cij的累加器初始化 while (A.datap.i = = i ) / 求第i行的 k = A.datap.j; / A中当前非零元的列号 if (kB.mu) t = rpotk+1 ; else t = B.tu+1; / 确定B中第k行的非零元素在B.data中的下限位置 for (q = rpotk ; qt ; q+ ) / B中第k行的每一个非零元素 j = B.dataq.j ; tempj + = A.datap.e * B.dataq.e p+; / while for (j=1;jnu;j+) if (tempj ) r+; C.datar= i

29、, j , tempj ; /for iC.tu = r ; returnOK ; / MulSMatrix 第四十五张，PPT共八十五页，创作于2022年6月带行逻辑连接的三元组顺序存储与乘积算法算法的时间性能分析。求num的时间复杂度为O(B.nu+B.tu)；求rpot 时间复杂度为O(B.mu)；求temp时间复杂度为O(A.mu*B.nu)；求C的所有非零元素的时间复杂度为O(A.tu*B.tu / B.mu)；压缩存储时间复杂度为O(A.mu*B.nu)；所以总的时间复杂度为O(A.mu*B.nu+(A.tu*B.tu) / B.nu )。 第四十六张，PPT共八十五页，创作于20

30、22年6月532 稀疏矩阵的十字链表存储与求和一、十字链表存储结构 基本思想：每个非零元素用一个结点存储，结点由5个域组成，如下图所示。其中： i域存储非零元素的行号， j域存储非零元素的列号， e域存储元素的值，right是横向链表指针域，down是纵向链表指针域。 第四十七张，PPT共八十五页，创作于2022年6月稀疏矩阵的十字链表存储与求和存储方法：将稀疏矩阵的每一行的非0元素结点按列号从小到大的顺序，由right指针拉成一个带表头结点的行单链表。每一列的非0元素按行号从小到大的顺序，由down指针拉成一个带表头结点的列单链表。每个非零元素aij，既是第i个行链表中的一个结点，又是第j个

31、列链表中的一个结点。所有行链表的头指针用一个指针数组rheadm存放，所有列链表的头指针用指针数组cheadn存放。 第四十八张，PPT共八十五页，创作于2022年6月稀疏矩阵的十字链表存储与求和存储结构定义：typedef struct OLNnode / 十字链表的结点结构int row , col ; / 元素的行号与列号域ElemtType e ; / 数据元素域 struct OLNode *down , *right ; / 行、列链表指针域 OLNode , *OLink ; typedef struct / 定义行、列链表头结点指针数组OLink *rhead , *chead

32、 ; / 行、列链表头结点指针数组 int mu , nu , tu ; / 行数、列数、非0元素个数域 CrossList ; 第四十九张，PPT共八十五页，创作于2022年6月稀疏矩阵的十字链表存储与求和例如。稀疏矩阵A的十字链表存储结构如下图所示。 第五十张，PPT共八十五页，创作于2022年6月稀疏矩阵的十字链表存储与求和二、基于十字链表存储结构的稀疏矩阵求和算法。1建立稀疏矩阵的十字链表算法步骤：（1）输入矩阵M的行数m、列数n和非0元素个数r。（2）申请行、列头指针数组空间，并初始化为空指针。（3）逐个输入非0元素的形如（i,j,aij）的三元组，建立三元组结点，分别插入到行链表和

33、列链表中，直到所有非0元素的的三元组输入完为止。第五十一张，PPT共八十五页，创作于2022年6月稀疏矩阵的十字链表存储与求和算法描述如下：status CreateSMatrixOL (CrossList &M ) / 创建十字链表针if ( M ) free ( M ) ;scanf (“%d ,%d, %d”, &m , &n , &t ) ; M.rhead = (OLink *)malloc(m+1)*(sizeof (OLink); / 申请行头指针数组空间 if ( !M.rhead ) exit ( OVERFLOW ) ;M.chead = (OLink *)malloc(n

34、+1)*(sizeof (OLink); / 申请列头指针数组空间 if ( !M.chead ) exit ( OVERFLOW ) ; M.rhead = M.chead = NULL ; / 行、列头指针数置空 for( k =1; k i = i ; p-j = j ; p-e = e ; / 生成结点if ( M.rheadi = = NULL | M.rheadi-j j ) / 在第i个链表插入结点 第五十二张，PPT共八十五页，创作于2022年6月稀疏矩阵的十字链表存储与求和 p-right = M.rheadi；M.rheadi = p ; else / 在第i个行链表找插入

35、位置 for (q = M.chead; (q-right) & q.right-j right ；p-right = q-right ; q-right = p ; / 插入结点if ( M.cheadj = = NULL | M.rheadj-i i ) / 在第j个列链表插入结点 p-down = M.cheadj；M.cheadj = p ; else / 在第j个列链表找插入位置 for (q = M.cheadj; (q-down) & q.down-i doen ；p-down = q-right ; q-down = p ; / 插入结点 return OK ; 上述算法的时间

36、复杂度为O(ts)，其中s=max(m,n)。 第五十三张，PPT共八十五页，创作于2022年6月稀疏矩阵的十字链表存储与求和基于十字链表的稀疏矩阵求和已知两个稀疏矩阵A和B，分别采用十字链表存储，计算C=A+B，C也采用十字链表方式存储，并且在A的基础上形成C。对于求C=A-B，可表示成C=A+（-B）矩阵加法规则：只有当A与B的行数和列数相等时二者才能相加，且cij = aij + bij。 第五十四张，PPT共八十五页，创作于2022年6月稀疏矩阵的十字链表存储与求和以下假定将B加到A上。设pa和pb分别指向A和B的十字链表中行号相同的两个结点，对应元素相加时分为下列4种情况：(1) 若

37、pa-j = pb-j且pa-e + pb-e 0，则只要用aij+bij的值改写pa所指结点的数据域即可。(2) 若pa-j=pb-j且pa-e + pb-e =0，则需要在矩阵A的十字链表中删除pa所指结点，此时需改变该行链表中前趋结点的right域，以及该列链表中前趋结点的down域。(3) 若pa-j j且pa-j0（即不是表头结点），则只需要将pa指针向右推进一步，继续进行比较。(4) 若pa-jpb-j或pa-j0（即是表头结点），则需要在矩阵A的十字链表中插入一个pb所指结点。 第五十五张，PPT共八十五页，创作于2022年6月稀疏矩阵的十字链表存储与求和算法描述如下：statu

38、s AddMatrix (CrossList &A , CrossList B) / 求稀疏矩阵的乘积AB OLNode *p, *q,*pa,*pb,*ca,*cb,*qa; if (A.mu != B.mu | A.nu != B.nu ) return ERROR ; ca = A.rhead1 ; / 初始化ca指向A的第一个结点 cb = B.rhead1 ; / 初始化cb指向B的第一个结点 do pa = ca-right; / pa指向A矩阵当前行中第一个结点 qa = ca; / qa指向pa的前驱 pb=cb-right; / pb指向B矩阵当前行中第一个结点 while

39、(pb-j != 0 ) / 当前行没有处理完 if (pa-j j & pa-j !=0 ) / 第三种情况 qa=pa; pa=pa-right; else if (pa-j pb-j | pa-j = =0 ) / 第四种情况 p= malloc(sizeof(MNode); p-i = pb- i ; p-j = pb-j; p-e = pb-e ; p-right = pa ; qa-right = p ; / 新结点插入*pa的前面 pa=p; / 新结点还要插到列链表的合适位置，先找位置，再插入 q = Find_JH (Ha,p-col); / 从列链表的头结点找起第五十六张，

40、PPT共八十五页，创作于2022年6月稀疏矩阵的十字链表存储与求和 while (q-down-i != 0 & q-down-i i ) q=q-down; p-down=q-down; / 插在*q的后面 q-down=p ; pb=pb-right; / end if else / 第一、二种情况 x= pa-v_next.v+ pb-v_next.v; if (x= =0) / 第二种情况 qa-right = pa-right; / 从行链中删除q= Find_JH (Ha,pa-col); / 找*pa的列前驱结点并删除 while ( q-down-i i ) q = q-dow

41、n; q-down = pa-down ; free (pa) ; pa = qa; / if (x= =0) else / 第一种情况 pa-e = x ; qa = pa ; pa = pa-right; pb = pb-right; / while ca = ca-next; / ca指向A中下一行的表头结点 cb = cb-next; / cb指向B中下一行的表头结点 while (ca-i = =0 ) / 当还有未处理完的行则继续 第五十七张，PPT共八十五页，创作于2022年6月54 广义表 5.4.1广义表的概念与ADT定义一、广义表的概念与性质1广义表的定义。广义表是n（n0

42、）个数据元素a1，a2，ai，an的有限序列，一般记作：Ls（a1，a2，ai，an）其中：Ls是广义表的名称，n称为广义表的长度，记为Length(Ls)。每个元素ai（1in）称为Ls的成员，它们既可以是单个元素，也可以是一个广义表，分别称为广义表Ls的原子和子表。当广义表Ls非空时，称第一个元素a1为Ls的表头记为head（Ls），称其余元素组成的子表（a2，ai，an）为Ls的表尾,记为tail(Ls) 。一个广义表中的括号嵌套层数称为该广义表的深度,记为Depth(Ls)。广义表是递归定义的。 第五十八张，PPT共八十五页，创作于2022年6月广义表例如：下面是一些广义表的例子。A

43、（），空广义表，Length(A) =0，Depth(A)=1。B （e），单个原子构成的广义表，Length(B) =1，Depth(B)=1。C （a，（b，c，d），一个原子和一个子表构成的广义表。Length(C) =2，Depth(C)=2。D （A，B，C）= (（），（e），（a，（b，c，d）)，以三个广义表为元素的广义表，Length(D) =3，Depth(D)=3。E （a，E）= (a , (a , (a , (a, E ) ) ，这是一个递归的广义表，其长度和深度可以任意大。F （），这是一个由一个空广义表构成的广义表，Length(F) =1，Depth(F)=2。

44、 第五十九张，PPT共八十五页，创作于2022年6月广义表2广义表的性质 广义表是一种多层次的数据结构。广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表。可以用树结构表示广义表，其中原子用小矩形表示，子表用圆圈表示。例如，上述例子中的广义表D，画成树的形式如下图所示。 第六十张，PPT共八十五页，创作于2022年6月广义表广义表可以是递归的表。广义表的定义并没有限制元素的递归，即广义表的元素也可以是其自身的子表。例如表E就是一个递归的表。广义表可以为其他表所共享。例如，广义表A、B、C是广义表D的共享子表。在D中可以不必列出子表的值，而用子表的名称来引用。 第六十一张，PPT共

45、八十五页，创作于2022年6月广义表二、广义表ADT定义 1初始化广义表InitGList ( &L )。2创建广义表CreateGLists(&L , S) 。3撤消广义表DestroyGList ( &L )。4复制广义表CopyGList(&T ，L ) 。5判断广义表是否空EmptyGList(&L)。6求广义表的长度GListLength( L )。7求广义表的深度GListDepth( L )。8在广义表L中查找数据元素GListLocate (L ，x)。9插入一个元素InsertFirst (&L ，e )。10删除一个元素DeleteFirstge (&L ，&e )。11取

46、表头GetHead ( L )。 12取表尾GetTail ( L )。 13遍历广义表TraverseGList ( L , visit( ) )。 第六十二张，PPT共八十五页，创作于2022年6月广义表广义表操作举例。对前面所给出的广义表A、B、C、D、E、F有。GetHead（B） e , GetTail（B）（）;GetHead（C） a , GetTail（C）（b，c，d）;GetHead（D） A , GetTail（D）（B，C）;GetHead（E） a , GetTail（E）（E）;GetHead（F）（） GetTail（F）（）。 第六十三张，PPT共八十五页，创作

47、于2022年6月542 广义表的存储一、头尾表示法 广义表中的数据元素既可能是广义表，也可能是原子，相应地在头尾表示法中，结点的结构形式有两种：一种是子表结点，用以表示子表；另一种是原子结点，用以表示原子。在表结点中应该包括一个指向表头的指针和指向表尾的指针；而在原子结点中应该包括所表示原子的元素值。为了区分这两类结点，在结点中还要设置一个标志域，如果标志为1，则表示该结点为子表结点；如果标志为0，则表示该结点为原子结点。结点结构如图所示： 第六十四张，PPT共八十五页，创作于2022年6月广义表的存储存储结构定义：typedef enum ATOM, LIST Elemtag; / ATOM

48、=0表示单元素；LIST=1表示子表typedef struct GLNode Elemtag tag ; / 标志域，用于区分元素结点和表结点 union / 元素结点和表结点的联合部分 AtomType atom ; / atom是元素结点的值域 struct struct GLNode *hp, *tp ; ptr; / ptr是表结点的指针域，ptr.hp和ptr.tp分别指向表头和表尾 *GList; / 广义表类型 第六十五张，PPT共八十五页，创作于2022年6月广义表的存储举例对前面所给的广义表A、B、C、D、E、F，存储结构如下图所示。 D （A，B，C）= (（），（e），

49、（a，（b，c，d）)第六十六张，PPT共八十五页，创作于2022年6月广义表的存储二、孩子兄弟表示法两种结点形式：一种是有孩子结点，用以表示列表；另一种是无孩子结点，用以表示单元素。在有孩子结点中包括一个指向第一个孩子（长子）的指针和一个指向兄弟的指针；而在无孩子结点中包括一个指向兄弟的指针和该元素的元素值。为了能区分这两类结点，在结点中还要设置一个标志域。如果标志为1，则表示该结点为有孩子结点；如果标志为0，则表示该结点为无孩子结点。结点结构如图所示。 第六十七张，PPT共八十五页，创作于2022年6月广义表的存储存储结构定义：typedef enum ATOM, LIST Elemtag

50、; / ATOM=0：单元素；LIST=1：子表typedef struct GLNode Elemtag tag ; / 标志域，用于区分元素结点和表结点 union / 元素结点和表结点的联合部分 AtomType atom; / 元素结点的值域 struct GLNode *hp; / 表结点的表头指针 ; struct GLNode *tp; / 指向下一个结点 *GList; / 广义表类型 第六十八张，PPT共八十五页，创作于2022年6月广义表的存储举例对于前面所给的广义表A、B、C、D、E、F，孩子兄弟表示法如下图所示。 D （A，B，C）= (（），（e），（a，（b，c，d

51、）)第六十九张，PPT共八十五页，创作于2022年6月543 广义表的基本操作算法算法思想：假设广义表以串S的形式给出，当广义表为空时，即S=( )，此时直接返回L=NULL。当广义表为不空时，S=(a1 , a2 , , an )，其中ai(i=1,2,n)为S的子串表示的子表。建立广义表S就是建立n个子表结点拉成的链表。第i个（1in）表结点的tp指针指向第i+1个表结点，第n个表结点的tp指针为NULL。第i个表结点的hp指针指向由ai建立的子表。由此可见，建立广义表S转化为建立子表ai（1in）的问题。而建立子表ai（1in）的过程与建立广义表S的过程完全相同，这显然是一个递归问题。对

52、每个ai又分三种情况：（1）ai是带括号的空串；（2）ai是长度为1的单字符串；（3）ai是长度大于1的字符串。前两种情况就是递归的终结状态，第三种情况是递归调用。 第七十张，PPT共八十五页，创作于2022年6月广义表的基本操作算法递归过程如下：基本项：置空广义表， 当S为空表串时； 建立原子结点子表， 当S为单字符串时；归纳项：假定S =(a1 , a2 , , an )，sub=s1,s2,sn是S脱去的最外层括号之后的字符串，其中si(i=1,2,n)是非空的字符串，对每个si建立一个表结点，结点的hp指针域指向由si建立的子表，tp指针指向由si+1（itag = ATOM ; L-

53、atom = S; / 创建原子结点 else L-tag = LIST; p = L ; / 重复建立n个子表 SubString (sub , S , 2 , StrLength (S )-2 ) ; / 脱去外层括号 do sever ( sub , hsub ) ; / 从sub中分离出表头串 CreateGList (p-ptr.hp , hsub) ; q = p ; if (!StrEmpty (sub) / 表尾不空 if (!(p = (GList)malloc(sizeof(GLNode) exit (OVERFLOW); p-tag = LIST ; q-ptr.tp =

54、 p; while (!StrEmpty (sub) ); q-ptr.tp = NULL; return OK ; 第七十二张，PPT共八十五页，创作于2022年6月广义表的基本操作算法status sever(SString &str , SString &hstr) n = StrLength(str); i= 1; k = 0 ; for (i = 1, k = 0; i = n | k != 0; +i) ch = SubStr (ch , str , i ,1 ); if (ch = = ( ) +k; else if (ch = = ) -k; if (i tag = = 1)

55、p = L-hp; return p; GList GetTail(GList L) if ( L-tag = = 1) p = L-tp; return p; 第七十四张，PPT共八十五页，创作于2022年6月广义表的基本操作算法三、求广义表的深度设广义表LS=(a1 , a2 , , an )，求广义表深度的递归形式如下：基本项： Depth (LS) = 1， 当LS为空广义表； Depth (LS) = 0 ， 当LS为原子时；归纳项： Depth (LS) = 1 + max Depth (si) | 1=i=1 。算法描述：int GListDepth ( GList L ) if

56、 (! L) return 1; / 空表深度为1 if ( L-tag = = ATOM ) return 0; / 单元素深度为0 for ( max = 0 , p =L ; p ; p = p-ptr.tp) dep = GListDepth ( p-ptr.hp ) ; / 求以p-ptr.hp尾头指针的子表深度 if (dep max) max = dep; return max +1; / 非空表的深度是各元素的深度的最大值加1 第七十五张，PPT共八十五页，创作于2022年6月广义表的基本操作算法四、求广义表的长度算法思想：只需统计最顶层的表结点个数即可。算法描述：int GL

57、istLength ( GList L ) if ( L ) return 1+ GListLength ( L -tp ) ; else return 0 ; 第七十六张，PPT共八十五页，创作于2022年6月广义表的基本操作算法五、复制广义表算法思想：将广义表分成表头和表尾两部分，先复制表头部分，再复制表尾部分。若表头部分是原子，就建立一个原子结点，若表头是子表，则又将分成表头和表尾两部分处理。表尾一定是子表，又分成表头和表尾两部分处理。复制整个广义表和复制子表的过程完全相同。设复制后的广义表为NewLS，递归过程如下： 基本项：InitGList (NewLS), 当LS为空广义表，置空表； 归纳项：COPY(GetHead(LS) , GetHead (NewLS) ) / 复制表头 COPY(GetTail(LS) , GetTail (NewLS) ) / 复制表尾 第七十七张，PPT共八十五页，创作于2022年6月广义表的基本操作算法 算法过程描述：status Copy