(精品)第5章数组与广义表.ppt

《(精品)第5章数组与广义表.ppt》由会员分享，可在线阅读，更多相关《(精品)第5章数组与广义表.ppt（85页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第5 5章章 数组与广义表数组与广义表 数组5.15.1 稀疏矩阵5.35.3 广义表5.45.4 特殊矩阵的压缩存储5.25.2 本章主要内容本章主要内容 一、数组的存储结构及其地址变换 二、特殊矩阵的压缩存储及其地址变换 三、稀疏矩阵的存储结构与算法 四、广义表的存储结构与算法返回首页返回首页5.1 5.1 数组数组 数组是线性表的直接推广。如果线性表的元素又是具有相同数据类型的线性表，这种线性表就是二维数组，若在二维数组中，元素还是线性表，即得到三维数组，依次类推可以得到n维数组。本节主要讨论数组的有关概念、存储结构及地址变换。5 51 11 1 数组类型与存储结构数组类型与存储结构一

2、、二维数组一、二维数组 一个m行n列的二维数组如下表所示：数组类型与存储结构数组类型与存储结构 令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)也是一个元素为线性表的线性表。基于这一原因，而把数组看成是线性表的推广。数组类型与存储结构数组类型与存储结构 数组是一个具有固定格式、固定个数的数据元素构成的有序集合，每一个数据元素有唯一的一对下标标识（i，j)，因此，在数组中不能做插入、删除操作。在高级语言中，数组一旦被定义，每一维的

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

4、b2，,bnbn)：初始化数组。DestroyArray(&ADestroyArray(&A)：撤销数组。Value(AValue(A，&e&e，j1j1，j2j2，jnjn):):取某个数据元素的值 Assign(&AAssign(&A，e e，j1j1，j2j2，jnjn)：为数据元素赋值。数组的内存映象数组的内存映象一、二维数组的存储结构及地址变换1、以行为主序顺序存储。用一块连续存储空间逐行顺序存储数组元素。例如：一个mn数组按行存储表示如下图：数组的内存映象数组的内存映象2、以列为主序顺序存储。用连续存储空间逐列顺序存储数组元素。例如：mn数组按列顺序存储，如下图所示：5 51 12

5、 2 数组的内存映象数组的内存映象3 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。数组的内存映象数组的内存映象 对于“以列为主序”的存储方式，数组元素aij的前面有j

6、-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 c1 c2)+(j-c2)(d1 c1+1)+(i-c1)L。数组的内存映象数组的内存映象二、n维数组 LOC()=LOC()+(d2-c

7、2+1)(d3-c3+1)(dn-cn+1)j1 +(d3-c3+1)(d4-c4+1)(dn-cn+1)j2+(dn-cn+1)jn-1+jn L=LOC()+()L例如：三维数组Amnp，元素aijk其物理地址为：LOC(aijk)=LOC(a111)+(i-1)np+(j-1)p+k-1)L 数组的内存映象数组的内存映象举例举例:若矩阵Amn 中存在某个元素aij满足：aij是第i行中最小值且是第j列中的最大值，则称该元素为矩阵A的一个鞍点。试编写一个算法，找出A中的所有鞍点。解决此问题的基本思想是：在矩阵A中求出每一行的最小值元素，然后判断该元素它是否是它所在列中的最大值，是则打印出，

8、否则不输出，接着处理下一行。设矩阵A用一个二维数组表示。数组的内存映象数组的内存映象算法如下：算法如下：void saddle(int A ,int m,int n)/m,n是矩阵A的行数和列数 int i,j,min;for(i=0;im;i+)/按行处理 min=Ai0 for(j=1;jn;j+)if(Aijmin)min=AIj;/找第i行最小值 for(j=0;jn;j+)/检测该行中的每一个最小值是否是鞍点 if(AIj=min)k=j;p=0;while(pm&Apj=m)printf(%d,%d,%dn,i,k,min);/if /for/返回首页返回首页5.2 5.2 特殊矩

9、阵的压缩存储特殊矩阵的压缩存储5 52 21 1 对称矩阵对称矩阵一、对称矩阵的压缩存储一、对称矩阵的压缩存储对称矩阵：n阶方阵中，若aij=aji，其中1i,jn，则称该矩阵为对称矩阵。如下图所示的矩阵是一个阶对称矩阵。特殊矩阵的压缩存储特殊矩阵的压缩存储 对称矩阵的元素关于主对角线对称，因此只需存储上三角或下三角部分即可。例如：上图（a）给出的5阶对称矩阵存储到一个一维数组如下图（b）所示。对称矩阵的压缩存储对称矩阵的压缩存储 将一个对称矩阵只存储下三角（或上三角）部分的元素aij，此时有ji且1in，对于上三角部分的元素aij和它对应的aji相等，因此当访问的元素在上三角时，直接去访问与

10、其对应的下三角元素即可。这样，原来需要n2个存储单元，现在只需要 个，可节约 个存储单元。对称矩阵的压缩存储对称矩阵的压缩存储 采用以行为主序的方法顺序存储到一个一维数组中。因为下三角中共有个 元素，设存储结构为一维数组。A ，如下图所示。对称矩阵的压缩存储对称矩阵的压缩存储二、地址变换二、地址变换 设矩阵的下三角部分的元素aij，下标满足条件：ij且1in，存储到一维数组A的第k个元素Ak中，则有：5 52 22 2 三角矩阵三角矩阵一、下三角矩阵的压缩存储一、下三角矩阵的压缩存储 形如下图所示的矩阵称为下三角矩阵。主对角线上方所有元素等于同一个常数C。一、下三角矩阵的压缩存储一、下三角矩阵

11、的压缩存储 下三角矩阵的压缩存储与对称矩阵的压缩存储类似。例如：下图所给给出一个下三角矩阵存储结构。下三角矩阵的压缩存储下三角矩阵的压缩存储下三角矩阵压缩存储的地址变换 用一维数组A 。存储下三角矩阵。如下图所示：设aji 存放在Ak中，则k与i、j的对应关系有如下公式：k=当ij时，k=当ij 时5 52 23 3 带状矩阵带状矩阵 n阶矩阵A称为带状矩阵，如果存在最小正数m，满足当i-jm时，aij=0，这时称w=2n-1为矩阵A的带宽。例如下图是一个w=3(m=2)的带状矩阵。带状矩阵带状矩阵 带状矩阵A采用压缩存储有两种方法:第一种方法：第一种方法：将A压缩到一个n行w列的二维数组B中

12、，如下图所示。当某行非零元素的个数小于带宽w时，先存放非零元素然后补零。带状矩阵带状矩阵另一种压缩方法另一种压缩方法:将带状矩阵压缩到一维数组中去，按以行为主序存储，顺序存放非零元素，如下图所示，按此规律，可得到相应的映象函数。如当w=3时，映象函数为：k=2（i-1)+j 返回首页返回首页5.3 5.3 稀疏矩阵稀疏矩阵 当m*n矩阵中有t个非零元素且tm*n时，这样的矩阵称为稀疏矩阵。稀疏矩阵压缩存储方法是仅存放非零元素。由于非零元素分布没有规律，为了能找到相应的元素，所以仅存储非零元素的值是不够的，还必须记下它们所在的行号和列号。为此采取如下方法：将非零元素所在的行、列以及它的值构成一个

13、三元组（i,j,v），然后将这些三元组按某种规律顺序存储，这种方法可以节约大量的存储空间。稀疏矩阵稀疏矩阵稀疏矩阵的稀疏矩阵的ADTADT定义定义对稀疏矩阵的操作只定义一下8种：创建稀疏矩阵。CreareSMatrix（&M）撤销稀疏矩阵。DetroySMatrix（&M）输出稀疏矩阵。PrintSMatrix（M）复制稀疏矩阵。CopySMatrix（M,&T）稀疏矩阵加法。AddSMatrix（M,N,&T）稀疏矩阵减法。SubtractSMatrix（M,N,&T）稀疏矩阵乘法。MultSMatrix（M,N,&T）稀疏矩阵转置。TransposeSMatrix（M,&T）5 53 31

14、 1 稀疏矩阵的三元组存储与转置、乘法稀疏矩阵的三元组存储与转置、乘法一、稀疏矩阵的三元组存储表示一、稀疏矩阵的三元组存储表示 将稀疏矩阵每个非0元素的值以及行下标、列下标构成的三元组按行优先顺序存储，同一行中列号按从小到大排列成一个线性表，称这种存储方法为三元组表示。例如，设稀疏矩阵如下图(a)所示，对应的三元组存储结构如图(b)所示。稀疏矩阵的三元组存储与转置、乘法稀疏矩阵的三元组存储与转置、乘法存储结构的定义：存储结构的定义：define MAXSIZE 1024 /非0元素的个数数typedef struct /定义三元组元素结构 int i,j;/非零元素的行号和列号 ElemTyp

15、e e;/非零元素的值 Triple;/三元组类型typedef struct SPNode dataMAXSIZE+1;/三元组顺序表int mu,nu,tu;/矩阵的行、列及非零元素的个数 TSMatrix;/三元组表的存储类型 稀疏矩阵的三元组存储与转置、乘法稀疏矩阵的三元组存储与转置、乘法二、稀疏矩阵的算法实现二、稀疏矩阵的算法实现1 1矩阵的转置矩阵的转置设TSMatrixTSMatrix A表示一个mn的稀疏矩阵，其转置TSMatrixTSMatrix B是一个nm的稀疏矩阵。转置算法基本思想：A的行、列转化成B的列、行；在A.data中依次找第一列的、第二列的、直到最后一列，并将

16、找到的每个三元组的行、列交换后顺序存储到B.data中。稀疏矩阵的三元组存储与转置、乘法稀疏矩阵的三元组存储与转置、乘法算法描述如下：算法描述如下：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;/TransposeSMatrix 稀疏矩阵的三元组存储与转置、乘法稀疏矩阵的三元组存储与转置、乘法算法性能分析。设m、n

17、是原矩阵的行数和列数，t是稀疏矩阵的非零元素个数。该算法的时间主要耗费在二重循环上，所以时间复杂性为O(n*t)。显然当非零元素的个数t和m*n同数量级时，算法的时间复杂度为O(m*n2)。与通常存储方式下矩阵转置算法相比，可能节约了一定量的存储空间，但算法的时间性能更差一些。稀疏矩阵的三元组存储与转置、乘法稀疏矩阵的三元组存储与转置、乘法2 2带列逻辑连接的三元组顺序存储与改进的转置算法带列逻辑连接的三元组顺序存储与改进的转置算法引入两个向量：numn+1和cpotn+1，其中numcol表示矩阵A中第col列的非零元素的个数（为了方便下标均从1开始），cpotcol的初始值表示矩阵A中的第

18、col列的第一个非零元素在B.data中的位置。于是cpot的初始值为：cpot1=1；cpotcol=cpotcol-1+numcol-1；2coln 稀疏矩阵的三元组存储与转置、乘法稀疏矩阵的三元组存储与转置、乘法例如:下图（a）所给矩阵A的num和cpot的数组值如右图所示。改进的稀疏矩阵转置算法称为快速转置。算法思想：依次扫描A.data，当扫描到一个col列元素时，直接将其存放在B.data的cpotcol位置上，且cpotcol加，cpotcol中始终是下一个col列元素在B.data中的位置。稀疏矩阵的三元组存储与转置、乘法稀疏矩阵的三元组存储与转置、乘法快速转置算法如下：快速转

19、置算法如下：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;numj+;cpot1=1;/求矩阵A中每一列第一个非零元素在B.data中的位置 for(i=2;i=A.nu;i+)cpoti=cpoti-1+numi-1;for(i=1;i=A.tu;i+)/扫描三元组表

20、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;/返回的是转置矩阵的指针 /FastTransposeSMatrix 稀疏矩阵的三元组存储与转置、乘法稀疏矩阵的三元组存储与转置、乘法算法的时间复杂度分析：算法的时间复杂度分析：上述算法中有四个循环，分别执行n，t，n-1，t次，在每个循环中，每次迭代的时间是一个常量，因此总的计算量是O（n+t）。所需要的存储空间比前

21、一个算法多了两个向量，空间复杂度为O（t）。2 2带行逻辑连接的三元组顺序存储与乘积算法带行逻辑连接的三元组顺序存储与乘积算法 已知稀疏矩阵A(m1 n1)和B(m2 n2)，求乘积C(m1 n2)。例如：稀疏矩阵A、B、C及它们对应的三元组顺序表A.data、B.data、C.data如下图(a)和(b)所示。带行逻辑连接的三元组顺序存储与乘积算法带行逻辑连接的三元组顺序存储与乘积算法由矩阵乘法规则知：Ci，j=Ai,1B1,j+Ai,2B2,j+Ai,nBn,j=当A的元素Ai,k的列号与B的元素Bk,p的行号相等时才能相乘，且当两项都不为零时，乘积中的这一项才不为零。为运算方便设一个累加

22、器：datatype tempn+1；用来存放当前行中cij的值，当前行中所有元素全部计算出之后，再存放到C.data中去。带行逻辑连接的三元组顺序存储与乘积算法带行逻辑连接的三元组顺序存储与乘积算法 为了便于在B.data中寻找B中的第k行的第一个非零元素，与前面类似，引入numn和rpotn两个向量。numk表示矩阵B中第k行的非零元素的个数；rpotk表示第k行的第一个非零元素在B.data中的位置。于是有：rpot1=1 rpotk=rpotk-1+numk-1 2kn带行逻辑连接的三元组顺序存储与乘积算法带行逻辑连接的三元组顺序存储与乘积算法例如，下图（a）的矩阵B的其numn 和r

23、potn 的值如右边的表所示。k1234num k 2020cpot k 1335带行逻辑连接的三元组顺序存储与乘积算法带行逻辑连接的三元组顺序存储与乘积算法稀疏矩阵存储结构定义：存储结构定义：#define MAXSIZE 1024#define MAXSIZE 1024 /稀疏矩阵非0元素最大个数#define MAXRC 100#define MAXRC 100 /稀疏矩阵的最大行数typedeftypedef structstruct /定义带行逻辑连接的三元组顺序表类型 Triple data MAXSIZE+1;Triple data MAXSIZE+1;intint rpotMA

24、XRC+1 rpotMAXRC+1 intint mumu,nu,nu,tutu;RLSMatrixRLSMatrix 稀疏矩阵乘法的算算步骤：初始化。清理一些单元，准备按行顺序存放乘积矩阵;求B的numn和rpotn数组值;做矩阵乘法。将A.data中三元组的列值与B.data中三元组的行值相等的非零元素相乘，并将具有相同下标的乘积元素相加。带行逻辑连接的三元组顺序存储与乘积算法带行逻辑连接的三元组顺序存储与乘积算法稀疏矩阵乘法的算法描述：稀疏矩阵乘法的算法描述：Status MatrixMultiply(RLSMatrix*A,RLSMatrix*B,RLSMatrix&C)/求稀疏矩阵C

25、=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;/求矩阵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;带行逻辑连接的三元组顺序存

26、储与乘积算法带行逻辑连接的三元组顺序存储与乘积算法r=0;/当前C中非零元素的个数 p=1;/指示A.data中当前非零元素的位置 for(i=1;i=A.mu;i+)for(j=1;j=B.nu;j+)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

27、.e p+;/while for(j=1;jnu;j+)if(tempj)r+;C.datar=i,j,tempj;/for iC.tu=r;returnOK;/MulSMatrix 带行逻辑连接的三元组顺序存储与乘积算法带行逻辑连接的三元组顺序存储与乘积算法算法的时间性能分析算法的时间性能分析:求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.t

28、u*B.tu)/B.nu)。5 53 32 2 稀疏矩阵的十字链表存储与求和稀疏矩阵的十字链表存储与求和一、十字链表存储结构十字链表存储结构 基本思想：每个非零元素用一个结点存储，结点由5个域组成，如下图所示。其中：i域存储非零元素的行号，j域存储非零元素的列号，e域存储元素的值，right是横向链表指针域，down是纵向链表指针域。稀疏矩阵的十字链表存储与求和稀疏矩阵的十字链表存储与求和存储方法：存储方法：将稀疏矩阵的每一行的非0元素结点按列号从小到大的顺序，由right指针拉成一个带表头结点的行单链表。每一列的非0元素按行号从小到大的顺序，由down指针拉成一个带表头结点的列单链表。每个非

29、零元素aij，既是第i个行链表中的一个结点，又是第j个列链表中的一个结点。所有行链表的头指针用一个指针数组rheadm存放，所有列链表的头指针用指针数组cheadn存放。稀疏矩阵的十字链表存储与求和稀疏矩阵的十字链表存储与求和存储结构定义：存储结构定义：typedef struct OLNnode /十字链表的结点结构int row,col;/元素的行号与列号域ElemtType e;/数据元素域 struct OLNode*down,*right;/行、列链表指针域 OLNode,*OLink;typedef struct /定义行、列链表头结点指针数组OLink *rhead,*chead

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

31、素的的三元组输入完为止。稀疏矩阵的十字链表存储与求和稀疏矩阵的十字链表存储与求和算法描述如下：算法描述如下：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+1)*(sizeof(OLink);/申请列头指针数组空间 if(!M.chead)exit(OVERFLOW

32、);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个链表插入结点 稀疏矩阵的十字链表存储与求和稀疏矩阵的十字链表存储与求和 p-right=M.rheadi；M.rheadi=p;else /在第i个行链表找插入位置 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个列链表插入结点

33、 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;上述算法的时间复杂度为O(ts)，其中s=max(m,n)。稀疏矩阵的十字链表存储与求和稀疏矩阵的十字链表存储与求和基于十字链表的稀疏矩阵求和 已知两个稀疏矩阵A和B，分别采用十字链表存储，计算C=A+B，C也采用十字链表方式存储，并且在A的基础上形成C。对于求C=A-B，可表示成C=A+（-B）矩阵加法规则：只有当A与B的行数和列数相等时二者才能

34、相加，且cij=aij+bij。稀疏矩阵的十字链表存储与求和稀疏矩阵的十字链表存储与求和以下假定将B加到A上。设pa和pb分别指向A和B的十字链表中行号相同的两个结点，对应元素相加时分为下列4种情况：(1)若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-jp

35、b-j或pa-j0（即是表头结点），则需要在矩阵A的十字链表中插入一个pb所指结点。稀疏矩阵的十字链表存储与求和稀疏矩阵的十字链表存储与求和算法描述如下：算法描述如下：status 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=

36、ca;/qa指向pa的前驱 pb=cb-right;/pb指向B矩阵当前行中第一个结点 while(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);/从列链表的头结点找起稀疏矩阵的十字链表存

37、储与求和稀疏矩阵的十字链表存储与求和 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-down;q-down=pa-down;free(pa);pa=qa;/if(x=0)else /第一种情况

38、 pa-e=x;qa=pa;pa=pa-right;pb=pb-right;/while c a=ca-next;/ca指向A中下一行的表头结点 cb=cb-next;/cb指向B中下一行的表头结点 while(ca-i=0)/当还有未处理完的行则继续 返回首页返回首页5 54 4 广义表广义表 5.4.15.4.1广义表的概念与广义表的概念与ADTADT定义定义一、广义表的概念与性质一、广义表的概念与性质1广义表的定义。广义表是n（n0）个数据元素a1，a2，ai，an的有序序列，一般记作：Ls（a1，a2，ai，an）其中：Ls是广义表的名称，n称为广义表的长度，记为Length(Ls)。

39、每个元素ai（1in）称为Ls的成员，它们既可以是单个元素，也可以是一个广义表，分别称为广义表Ls的原子和子表。当广义表Ls非空时，称第一个元素a1为Ls的表头记为head（Ls），称其余元素组成的子表（a2，ai，an）为Ls的表尾,记为tail(Ls)。一个广义表中的括号嵌套层数称为该广义表的深度,记为Depth(Ls)。广义表是递归定义的。广义表广义表例如：下面是一些广义表的例子例如：下面是一些广义表的例子.A（），空广义表，Length(A)=0，Depth(A)=1。B（e），单个原子构成的广义表，Length(B)=1，Depth(B)=1。C（a，（b，c，d），一个原子和一个子

40、表构成的广义表。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。广义表广义表2 2广义表的性质广义表的性质 广义表是一种多层次的数据结构。广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表。可以用树结构表示广义表，其中原子用小矩形表示，子表用圆圈表示。例如，上述例子中的广义表

41、D，画成树的形式如下图所示。广义表广义表 广义表可以是递归的表。广义表的定义并没有限制元素的递归，即广义表的元素也可以是其自身的子表。例如表E就是一个递归的表。广义表可以为其他表所共享。例如，广义表A、B、C是广义表D的共享子表。在D中可以不必列出子表的值，而用子表的名称来引用。广义表广义表二、广义表二、广义表ADTADT定义定义 1初始化广义表InitGList(&L)。2创建广义表CreateGLists(&L,S)。3撤消广义表DestroyGList(&L)。4复制广义表CopyGList(&T，L)。5判断广义表是否空EmptyGList(&L)。6求广义表的长度GListLengt

42、h(L)。7求广义表的深度GListDepth(L)。8在广义表L中查找数据元素GListLocate(L，x)。9插入一个元素InsertFirst(&L，e)。10删除一个元素DeleteFirstge(&L，&e)。11取表头GetHead(L)。12取表尾GetTail(L)。13遍历广义表TraverseGList(L,visit()。广义表广义表广义表操作举例 对前面所给出的广义表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）;GetH

43、ead（E）a,GetTail（E）（E）;GetHead（F）（）GetTail（F）（）。5 54 42 2 广义表的存储广义表的存储一、头尾表示法一、头尾表示法 广义表中的数据元素既可能是广义表，也可能是原子，相应地在头尾表示法中，结点的结构形式有两种：一种是子表结点，用以表示子表；另一种是原子结点，用以表示原子。在表结点中应该包括一个指向表头的指针和指向表尾的指针；而在原子结点中应该包括所表示原子的元素值。为了区分这两类结点，在结点中还要设置一个标志域，如果标志为1，则表示该结点为子表结点；如果标志为0，则表示该结点为原子结点。结点结构如图所示：广义表的存储广义表的存储存储结构定义：t

44、ypedeftypedef enumenum ATOM,LIST ATOM,LIST ElemtagElemtag;/ATOM=0表示单元素；LIST=1表示子表typedeftypedef structstruct GLNodeGLNode ElemtagElemtag tag;tag;/标志域，用于区分元素结点和表结点 union union /元素结点和表结点的联合部分 AtomTypeAtomType atom;atom;/atom是元素结点的值域 structstruct structstruct GLNodeGLNode *hp,*hp,*tptp;ptrptr;/ptr是表结点的

45、指针域，ptr.hp和ptr.tp分别指向表头和表尾 *GListGList;/广义表类型 广义表的存储广义表的存储举例:对前面所给的广义表A、B、C、D、E、F，存储结构如下图所示。广义表的存储广义表的存储二、孩子兄弟表示法二、孩子兄弟表示法两种结点形式：一种是有孩子结点，用以表示列表；另一种是无孩子结点，用以表示单元素。在有孩子结点中包括一个指向第一个孩子（长子）的指针和一个指向兄弟的指针；而在无孩子结点中包括一个指向兄弟的指针和该元素的元素值。为了能区分这两类结点，在结点中还要设置一个标志域。如果标志为1，则表示该结点为有孩子结点；如果标志为0，则表示该结点为无孩子结点。结点结构如图所示

46、。广义表的存储广义表的存储存储结构定义：存储结构定义：typedef enum ATOM,LIST Elemtag;/ATOM=0：单元素；LIST=1：子表typedef struct GLNode Elemtag tag;/标志域，用于区分元素结点和表结点 union /元素结点和表结点的联合部分 AtomType atom;/元素结点的值域 struct GLNode *hp;/表结点的表头指针 ;struct GLNode *tp;/指向下一个结点 *GList;/广义表类型 广义表的存储广义表的存储举例:对于前面所给的广义表A、B、C、D、E、F，孩子兄弟表示法如下图所示:5 54

47、43 3 广义表的基本操作算法广义表的基本操作算法算法思想算法思想：假设广义表以串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的过程完全相同，这显然是一个递归问题。对每个ai又分三种情况：（1）ai是带括号

48、的空串；（2）ai是长度为1的单字符串；（3）ai是长度大于1的字符串。前两种情况就是递归的终结状态，第三种情况是递归调用。广义表的基本操作算法广义表的基本操作算法递归过程如下：基本项：置空广义表，当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-atom=S;/创建原子结点 else L-tag=LIST;p=L;/重复建立n个子表 SubSt

49、ring(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=p;while(!StrEmpty(sub);q-ptr.tp=NULL;return OK;广义表的基本操作算法广义表的基本操作算法status sever(SString&str,SString&hstr)n=

50、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)p=L-hp;return p;GList GetTail(GList L)if(L-tag=1)p=L-tp;return p;广义表的基本操作算法广义表的基本操作算法三、求广义表的深度三、求广义表的深度设广义表LS=(a1,a2,an)，求广义表深度的递归形式如下：基本项：Depth(LS)=1，当LS为空广义表；Depth(LS)=0，当LS为原子时；归纳项：Depth(LS)=