数组与广义表

关于数组与广义表第1页，讲稿共85页，2023年5月2日，星期三第5章数组与广义表

本章主要内容一、数组的存储结构及其地址变换二、特殊矩阵的压缩存储及其地址变换三、稀疏矩阵的存储结构与算法四、广义表的存储结构与算法第2页，讲稿共85页，2023年5月2日，星期三5.1数组

数组是线性表的直接推广。如果线性表的元素又是具有相同数据类型的线性表，这种线性表就是二维数组，若在二维数组中，元素还是线性表，即得到三维数组，依次类推可以得到n维数组。本节主要讨论数组的有关概念、存储结构及地址变换。第3页，讲稿共85页，2023年5月2日，星期三5．1．1数组类型与存储结构一、二维数组

一个m行n列的二维数组如下表所示：

第4页，讲稿共85页，2023年5月2日，星期三数组类型与存储结构

令αi=（ai1，ai2，…，ai,n）(i=1,2,…,m)，每行作为一个元素，则A=(α1,α2,…,αm)是一个元素为线性表的线性表。 若令βj=(a1j，a2j，…，amj)T(j=1,2,…,n),每列作为一个元素，则A=(β1,β2,…,βn)也是一个元素为线性表的线性表。 基于这一原因，而把数组看成是线性表的推广。第5页，讲稿共85页，2023年5月2日，星期三数组类型与存储结构

数组是一个具有固定格式、固定个数的数据元素构成的有序集合，每一个数据元素有唯一的一对下标标识（i，j），因此，在数组中不能做插入、删除操作。在高级语言中，数组一旦被定义，每一维的下标上下界都不能改变。对数组可以施加的操作主要有以下两种：（1）取值操作：给定下标，读其对应的数据元素。（2）赋值操作：给定下标，存储或修改与其相对应的数据元素。第6页，讲稿共85页，2023年5月2日，星期三数组类型与存储结构

由含n个下标（0≦ji≦bi－1，i=1,2,…n）且具有相同类型的个数据元素构成的集合称为一个n维数组，bi称为第i维的长度。数组中的每个元素对应于一组下标（），受到n个关系的约束。固定n-1个下标，让另一个下标变换就是一个一维数组。在n个关系中，对于任意元素（0≦ji≦bi－2）都有一个直接后继。n维数组的ADT定义。

只包含4种操作：

InitArray(&A，n，b1，b2，…,bn)：初始化数组。

DestroyArray(&A)：撤销数组。

Value(A，&e，j1，j2，…，jn)。取某个数据元素的值

Assign(&A，e，j1，j2，…，jn)：为数据元素赋值。

第7页，讲稿共85页，2023年5月2日，星期三数组的内存映象一、二维数组的存储结构及地址变换1、以行为主序顺序存储。用一块连续存储空间逐行顺序存储数组元素。例如：一个m×n数组按行存储表示如下图：第8页，讲稿共85页，2023年5月2日，星期三数组的内存映象2、以列为主序顺序存储。用连续存储空间逐列顺序存储数组元素。例如：m×n数组按列顺序存储，如下图所示：第9页，讲稿共85页，2023年5月2日，星期三5．1．2数组的内存映象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)+(i×n+j)×L。第10页，讲稿共85页，2023年5月2日，星期三数组的内存映象对于“以列为主序”的存储方式，数组元素aij的前面有j-1列，每一列有m个元素数，在第j列中，它的前面还有i-1个元素，所以有：LOC(aij)=LOC(a11)+((j-1)×m+i-1)×L。当下界从0开始是，应改为：LOC(aij)=LOC(a00)+(j×m+i)×L。对一般的二维数组，设数组A[c1..d1][c2..d2]，下标的上、下界可以是任何整数，则aij的物理地址计算公式为：行主序：LOC(aij)=LOC(ac1c2)+((i-c1)×(d2-c2+1)+(j-c2))×L。列主序：LOC(aij)=LOC(ac1c2)+((j-c2)×(d1–c1+1)+(i-c1))×L。第11页，讲稿共85页，2023年5月2日，星期三数组的内存映象二、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例如：三维数组A[m][n][p]，元素aijk其物理地址为：LOC(aijk)=LOC(a111)+((i-1)×n×p+(j-1)×p+k-1)×L

第12页，讲稿共85页，2023年5月2日，星期三数组的内存映象举例。若矩阵Am×n

中存在某个元素aij满足：aij是第i行中最小值且是第j列中的最大值，则称该元素为矩阵A的一个鞍点。试编写一个算法，找出A中的所有鞍点。解决此问题的基本思想是：在矩阵A中求出每一行的最小值元素，然后判断该元素它是否是它所在列中的最大值，是则打印出，否则不输出，接着处理下一行。设矩阵A用一个二维数组表示。第13页，讲稿共85页，2023年5月2日，星期三数组的内存映象算法如下：voidsaddle(intA[][],intm,intn)//m,n是矩阵A的行数和列数{inti,j,min;for(i=0;i<m;i++)//按行处理

{min=A[i][0];for(j=1;j<n;j++){if(A[i][j]<min)min=A[i][j];k=j;}//找第i行最小值

for(p=0;p<m&&a[i][k]>a[p][k];p++)//检测该行中的每一个最小值是否是鞍点

if(p>=m)printf(＂%d,%d,%d\n＂,i,k,min);}//if}//for/}第14页，讲稿共85页，2023年5月2日，星期三5.2特殊矩阵的压缩存储5．2．1对称矩阵一、对称矩阵的压缩存储对称矩阵：n阶方阵中，若aij=aji，其中1≤i,j≤n，则称该矩阵为对称矩阵。如下图所示的矩阵是一个５阶对称矩阵。第15页，讲稿共85页，2023年5月2日，星期三特殊矩阵的压缩存储对称矩阵的元素关于主对角线对称，因此只需存储上三角或下三角部分即可。例如：上图（a）给出的5阶对称矩阵存储到一个一维数组如下图（b）所示。第16页，讲稿共85页，2023年5月2日，星期三对称矩阵的压缩存储将一个对称矩阵只存储下三角（或上三角）部分的元素aij，此时有j≤i且1≤i≤n，对于上三角部分的元素aij和它对应的aji相等，因此当访问的元素在上三角时，直接去访问与其对应的下三角元素即可。这样，原来需要n2个存储单元，现在只需要个，可节约个存储单元。第17页，讲稿共85页，2023年5月2日，星期三对称矩阵的压缩存储采用以行为主序的方法顺序存储到一个一维数组中。因为下三角中共有个元素，设存储结构为一维数组。A[]，如下图所示。第18页，讲稿共85页，2023年5月2日，星期三对称矩阵的压缩存储二、地址变换设矩阵的下三角部分的元素aij，下标满足条件：i≥j且1≤i≤n，存储到一维数组A的第k个元素A[k]中，则有：第19页，讲稿共85页，2023年5月2日，星期三5．2．2三角矩阵一、下三角矩阵的压缩存储形如下图所示的矩阵称为下三角矩阵。主对角线上方所有元素等于同一个常数C。第20页，讲稿共85页，2023年5月2日，星期三一、下三角矩阵的压缩存储下三角矩阵的压缩存储与对称矩阵的压缩存储类似。例如：下图所给给出一个下三角矩阵存储结构。第21页，讲稿共85页，2023年5月2日，星期三下三角矩阵的压缩存储下三角矩阵压缩存储的地址变换用一维数组A[]。存储下三角矩阵。如下图所示：设aji存放在A[k]中，则k与i、j的对应关系有如下公式：当i≥j时，k=当i<j时k=。第22页，讲稿共85页，2023年5月2日，星期三二、上三角矩阵

三角矩阵，存储思想与下三角类似，以行为主序顺序存储上三角部分，最后存储对角线下方的常量，如下图所示。第23页，讲稿共85页，2023年5月2日，星期三上三角矩阵地址变换公式：若元素aji

存储在一维数组A的A[k]中，则k与i和j的对应关系为：k=当i≤j时k=当i>j时第24页，讲稿共85页，2023年5月2日，星期三5．2．3带状矩阵n阶矩阵A称为带状矩阵，如果存在最小正数m，满足当∣i-j∣≥m时，aij=0，这时称w=2n-1为矩阵A的带宽。例如下图是一个w=3(m=2)的带状矩阵。第25页，讲稿共85页，2023年5月2日，星期三带状矩阵带状矩阵A采用压缩存储有两种方法。第一种方法：将A压缩到一个n行w列的二维数组B中，如下图所示。当某行非零元素的个数小于带宽w时，先存放非零元素然后补零。第26页，讲稿共85页，2023年5月2日，星期三带状矩阵另一种压缩方法是将带状矩阵压缩到一维数组中去，按以行为主序存储，顺序存放非零元素，如下图所示，按此规律，可得到相应的映象函数。如当w=3时，映象函数为：k=2（i-1)+j-1第27页，讲稿共85页，2023年5月2日，星期三5.3稀疏矩阵当m*n矩阵中有t个非零元素且t<<m*n时，这样的矩阵称为稀疏矩阵。稀疏矩阵压缩存储方法是仅存放非零元素。由于非零元素分布没有规律，为了能找到相应的元素，所以仅存储非零元素的值是不够的，还必须记下它们所在的行号和列号。为此采取如下方法：将非零元素所在的行、列以及它的值构成一个三元组（i,j,v），然后将这些三元组按某种规律顺序存储，这种方法可以节约大量的存储空间。第28页，讲稿共85页，2023年5月2日，星期三稀疏矩阵稀疏矩阵的ADT定义对稀疏矩阵的操作只定义一下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）第29页，讲稿共85页，2023年5月2日，星期三5．3．1稀疏矩阵的三元组存储与转置、乘法一、稀疏矩阵的三元组存储表示

将稀疏矩阵每个非0元素的值以及行下标、列下标构成的三元组按行优先顺序存储，同一行中列号按从小到大排列成一个线性表，称这种存储方法为三元组表示。例如，设稀疏矩阵如下图(a)所示，对应的三元组存储结构如图(b)所示。第30页，讲稿共85页，2023年5月2日，星期三稀疏矩阵的三元组存储与转置、乘法存储结构的定义：defineMAXSIZE1024//非0元素的个数数typedefstruct//定义三元组元素结构

{inti,j;//非零元素的行号和列号

ElemTypee;//非零元素的值

}Triple;//三元组类型typedefstruct{SPNodedata[MAXSIZE+1];//三元组顺序表intmu,nu,tu;//矩阵的行、列及非零元素的个数

}TSMatrix;//三元组表的存储类型第31页，讲稿共85页，2023年5月2日，星期三稀疏矩阵的三元组存储与转置、乘法二、稀疏矩阵的算法实现1．矩阵的转置设TSMatrixA表示一个m×n的稀疏矩阵，其转置TSMatrixB是一个n×m的稀疏矩阵。转置算法基本思想：①A的行、列转化成B的列、行；②在A.data中依次找第一列的、第二列的、…、直到最后一列，并将找到的每个三元组的行、列交换后顺序存储到B.data中。

第32页，讲稿共85页，2023年5月2日，星期三稀疏矩阵的三元组存储与转置、乘法算法描述如下：voidTransposeSMatrix(TSMatrixA,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;p<=A.tu;p++)//扫描整个三元组表

if(A.data[p].j==col){B.data[q].i=A.data[p].j;B.data[q].j=A.data[p].i;B.data[q].e=A.data[p].e;q++;}//if}//if(B->tu>0)returnOK;

}//TransposeSMatrix第33页，讲稿共85页，2023年5月2日，星期三稀疏矩阵的三元组存储与转置、乘法算法性能分析。设m、n是原矩阵的行数和列数，t是稀疏矩阵的非零元素个数。该算法的时间主要耗费在二重循环上，所以时间复杂性为O(n*t)。显然当非零元素的个数t和m*n同数量级时，算法的时间复杂度为O(m*n2)。与通常存储方式下矩阵转置算法相比，可能节约了一定量的存储空间，但算法的时间性能更差一些。第34页，讲稿共85页，2023年5月2日，星期三稀疏矩阵的三元组存储与转置、乘法2．带列逻辑连接的三元组顺序存储与改进的转置算法引入两个向量：num[n+1]和cpot[n+1]，其中num[col]表示矩阵A中第col列的非零元素的个数（为了方便下标均从1开始），cpot［col］的初始值表示矩阵A中的第col列的第一个非零元素在B.data中的位置。于是cpot的初始值为：cpot[1]=1；cpot[col]=cpot[col-1]+num[col-1]；2≤col≤n

第35页，讲稿共85页，2023年5月2日，星期三稀疏矩阵的三元组存储与转置、乘法例如。下图（a）所给矩阵A的num和cpot的数组值如右图所示。改进的稀疏矩阵转置算法称为快速转置。算法思想：依次扫描A.data，当扫描到一个col列元素时，直接将其存放在B.data的cpot[col]位置上，且cpot[col]加１，cpot[col]中始终是下一个col列元素在B.data中的位置。第36页，讲稿共85页，2023年5月2日，星期三稀疏矩阵的三元组存储与转置、乘法快速转置算法如下：StatusFastTransposeSMatrix(TSMatrixA,TSMatrix&B){

B.mu=A.nu;B.nu=A.mu;

B.tu=A.tu;//稀疏矩阵的行、列及元素个数

if(B.tu>0)//有非零元素则转换

{for(i=1;i<=A.nu;i++)num[i]=0;for(i=1;i<=A.tu;i++)//求矩阵A中每一列非零元素的个数

{j=A.data[i].j;num[j]++;}cpot[1]=1;//求矩阵A中每一列第一个非零元素在B.data中的位置for(i=2;i<=A.nu;i++)cpot[i]=cpot[i-1]+num[i-1];for(i=1;i<=A.tu;i++)//扫描三元组表

{j=A.data[i].j;//当前三元组的列号

k=cpot[j];//当前三元组在B.data中的位置

B.data[k].i=A.data[i].j;B.data[k].j=A.data[i].i;B.data[k].v=A.data[i].v;cpot[j]++;}//fori

}//if(B.tu)

returnB;//返回的是转置矩阵的指针

}//FastTransposeSMatrix第37页，讲稿共85页，2023年5月2日，星期三稀疏矩阵的三元组存储与转置、乘法算法的时间复杂度分析：上述算法中有四个循环，分别执行n，t，n-1，t次，在每个循环中，每次迭代的时间是一个常量，因此总的计算量是O（n+t）。所需要的存储空间比前一个算法多了两个向量，空间复杂度为O（t）。第38页，讲稿共85页，2023年5月2日，星期三2．带行逻辑连接的三元组顺序存储与乘积算法已知稀疏矩阵A(m1×n1)和B(m2×n2)，求乘积C(m1×n2)。例如：稀疏矩阵A、B、C及它们对应的三元组顺序表A.data、B.data、C.data如下图(a)和(b)所示。

第39页，讲稿共85页，2023年5月2日，星期三带行逻辑连接的三元组顺序存储与乘积算法由矩阵乘法规则知：C[i，j]=A[i,1]×B[1,j]+A[i,2]×B[2,j]+…+A[i,n]×B[n,j]=当A的元素A[i,k]的列号与B的元素B[k,p]的行号相等时才能相乘，且当两项都不为零时，乘积中的这一项才不为零。为运算方便设一个累加器：datatypetemp[n+1]；用来存放当前行中cij的值，当前行中所有元素全部计算出之后，再存放到C.data中去。第40页，讲稿共85页，2023年5月2日，星期三带行逻辑连接的三元组顺序存储与乘积算法为了便于在B.data中寻找B中的第k行的第一个非零元素，与前面类似，引入num[n]和rpot[n]两个向量。num[k]表示矩阵B中第k行的非零元素的个数；rpot[k]表示第k行的第一个非零元素在B.data中的位置。于是有：rpot[1]=1rpot[k]=rpot[k-1]+num[k-1]2≤k≤n第41页，讲稿共85页，2023年5月2日，星期三带行逻辑连接的三元组顺序存储与乘积算法例如，下图（a）的矩阵B的其num[n]和rpot[n]的值如右边的表所示。k1234num[k]2020cpot[k]1335第42页，讲稿共85页，2023年5月2日，星期三带行逻辑连接的三元组顺序存储与乘积算法稀疏矩阵存储结构定义：#defineMAXSIZE1024//稀疏矩阵非0元素最大个数#defineMAXRC100//稀疏矩阵的最大行数typedefstruct{//定义带行逻辑连接的三元组顺序表类型

Tripledata[MAXSIZE+1];intrpot[MAXRC+1]intmu,nu,tu;}RLSMatrix

稀疏矩阵乘法的算算步骤：⑴初始化。清理一些单元，准备按行顺序存放乘积矩阵;⑵求B的num[n]和rpot[n]数组值;⑶做矩阵乘法。将A.data中三元组的列值与B.data中三元组的行值相等的非零元素相乘，并将具有相同下标的乘积元素相加。第43页，讲稿共85页，2023年5月2日，星期三带行逻辑连接的三元组顺序存储与乘积算法稀疏矩阵乘法的算法描述：StatusMatrixMultiply(RLSMatrix*A,RLSMatrix*B,RLSMatrix&C)//求稀疏矩阵C=A×B{intp,q,i,j,k,r;ElemTypectemp[n+1];intnum[B.nu+1];if(A.nu!=B.mu)returnERROR;//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++)num[i]=0;//求矩阵B中每一行非零元素的个数for(k=1;k<=B.tu;k++){i=B.data[k].i;num[i]++;}

rpot[1]=1;//求矩阵B中每一行第一个非零元素在B.data中的位置for(i=2;i<=B.mu;i++)rpot[i]=rpot[i-1]+num[i-1];第44页，讲稿共85页，2023年5月2日，星期三带行逻辑连接的三元组顺序存储与乘积算法r=0;//当前C中非零元素的个数

p=1;//指示A.data中当前非零元素的位置

for(i=1;i<=A.mu;i++){for(j=1;j<=B.nu;j++)temp[j]=0;//cij的累加器初始化

while(A.data[p].i==i)//求第i行的

{k=A.data[p].j;//A中当前非零元的列号

if(k<B.mu)t=rpot[k+1];elset=B.tu+1;//确定B中第k行的非零元素在B.data中的下限位置

for(q=rpot[k];q<t;q++)//B中第k行的每一个非零元素

{j=B.data[q].j;

temp[j]+=A.data[p].e*B.data[q].e}p++;

}//whilefor(j=1;j<=B->nu;j++)if(temp[j]){r++;C.data[r]={i,j,temp[j]};}

}//foriC.tu=r;returnOK;}//MulSMatrix第45页，讲稿共85页，2023年5月2日，星期三带行逻辑连接的三元组顺序存储与乘积算法算法的时间性能分析。求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)。第46页，讲稿共85页，2023年5月2日，星期三5．3．2稀疏矩阵的十字链表存储与求和一、十字链表存储结构

基本思想：每个非零元素用一个结点存储，结点由5个域组成，如下图所示。其中：i域存储非零元素的行号，j域存储非零元素的列号，e域存储元素的值，right是横向链表指针域，down是纵向链表指针域。

第47页，讲稿共85页，2023年5月2日，星期三稀疏矩阵的十字链表存储与求和存储方法：将稀疏矩阵的每一行的非0元素结点按列号从小到大的顺序，由right指针拉成一个带表头结点的行单链表。每一列的非0元素按行号从小到大的顺序，由down指针拉成一个带表头结点的列单链表。每个非零元素aij，既是第i个行链表中的一个结点，又是第j个列链表中的一个结点。所有行链表的头指针用一个指针数组rhead[m]存放，所有列链表的头指针用指针数组chead[n]存放。

第48页，讲稿共85页，2023年5月2日，星期三稀疏矩阵的十字链表存储与求和存储结构定义：typedefstructOLNnode{//十字链表的结点结构introw,col;//元素的行号与列号域ElemtTypee;//

数据元素域

structOLNode*down,*right;//行、列链表指针域

}OLNode,*OLink;

typedefstruct{//定义行、列链表头结点指针数组OLink*rhead,*chead;//行、列链表头结点指针数组

intmu,nu,tu;//

行数、列数、非0元素个数域}CrossList;

第49页，讲稿共85页，2023年5月2日，星期三稀疏矩阵的十字链表存储与求和例如。稀疏矩阵A的十字链表存储结构如下图所示。

第50页，讲稿共85页，2023年5月2日，星期三稀疏矩阵的十字链表存储与求和二、基于十字链表存储结构的稀疏矩阵求和算法。1．建立稀疏矩阵的十字链表算法步骤：（1）输入矩阵M的行数m、列数n和非0元素个数r。（2）申请行、列头指针数组空间，并初始化为空指针。（3）逐个输入非0元素的形如（i,j,aij）的三元组，建立三元组结点，分别插入到行链表和列链表中，直到所有非0元素的的三元组输入完为止。第51页，讲稿共85页，2023年5月2日，星期三稀疏矩阵的十字链表存储与求和算法描述如下：statusCreateSMatrixOL(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);M.rhead[]=M.chead[]=NULL;//行、列头指针数置空

for(k=1;k<M.tu;k++){p=(OLink*)malloc(sizeof(OLink);//申请第k个结点if(!p)exit(OVERFLOW);scanf(“%d,%d,%d”,&i,&j,&e);//输入结点数据p->i=i;p->j=j;p->e=e;//生成结点if(M.rhead[i]==NULL||M.rhead[i]->j>j)//在第i个链表插入结点第52页，讲稿共85页，2023年5月2日，星期三稀疏矩阵的十字链表存储与求和

{p->right=M.rhead[i]；M.rhead[i]=p;}else{//在第i个行链表找插入位置

for(q=M.chead;(q->right)&&q.right->j<j)q=q->right；p->right=q->right;q->right=p;//插入结点}if(M.chead[j]==NULL||M.rhead[j]->i>i)//在第j个列链表插入结点

{p->down=M.chead[j]；M.chead[j]=p;}else{//在第j个列链表找插入位置

for(q=M.chead[j];(q->down)&&q.down->i<i)q=q->doen；p->down=q->right;q->down=p;//插入结点}}returnOK;}上述算法的时间复杂度为O(t×s)，其中s=max(m,n)。

第53页，讲稿共85页，2023年5月2日，星期三稀疏矩阵的十字链表存储与求和２．基于十字链表的稀疏矩阵求和已知两个稀疏矩阵A和B，分别采用十字链表存储，计算C=A+B，C也采用十字链表方式存储，并且在A的基础上形成C。对于求C=A-B，可表示成C=A+（-B）矩阵加法规则：只有当A与B的行数和列数相等时二者才能相加，且cij=aij+bij。第54页，讲稿共85页，2023年5月2日，星期三稀疏矩阵的十字链表存储与求和以下假定将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<pb->j且pa->j≠0（即不是表头结点），则只需要将pa指针向右推进一步，继续进行比较。(4)若pa->j>pb->j或pa->j＝0（即是表头结点），则需要在矩阵A的十字链表中插入一个pb所指结点。第55页，讲稿共85页，2023年5月2日，星期三稀疏矩阵的十字链表存储与求和算法描述如下：statusAddMatrix(CrossList&A,CrossListB)//求稀疏矩阵的乘积A×B{OLNode*p,*q,*pa,*pb,*ca,*cb,*qa;if(A.mu!=B.mu||A.nu!=B.nu)returnERROR;ca=A.rhead[1];//初始化ca指向A的第一个结点

cb=B.rhead[1];//初始化cb指向B的第一个结点do{pa=ca->right;//pa指向A矩阵当前行中第一个结点

qa=ca;//qa指向pa的前驱

pb=cb->right;//pb指向B矩阵当前行中第一个结点

while(pb->j!=0)//当前行没有处理完

{if(pa->j<pb->j&&pa->j!=0)//第三种情况

{qa=pa;pa=pa->right;}elseif(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);//从列链表的头结点找起第56页，讲稿共85页，2023年5月2日，星期三稀疏矩阵的十字链表存储与求和

while(q->down->i!=0&&q->down->i<p->i)q=q->down;p->down=q->down;//插在*q的后面

q->down=p;pb=pb->right;}//endifelse//第一、二种情况

{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<pa->i)q=q->down;q->down=pa->down;free(pa);pa=qa;}//if(x==0)else//第一种情况{pa->e=x;qa=pa;}pa=pa->right;pb=pb->right;}}//whileca=ca->next;//ca指向A中下一行的表头结点

cb=cb->next;//cb指向B中下一行的表头结点

}while(ca->i==0)//当还有未处理完的行则继续

}第57页，讲稿共85页，2023年5月2日，星期三5．4广义表

5.4.1广义表的概念与ADT定义一、广义表的概念与性质1．广义表的定义。广义表是n（n≥0）个数据元素a1，a2，…，ai，…，an的有限序列，一般记作：Ls＝（a1，a2，…，ai，…，an）其中：Ls是广义表的名称，n称为广义表的长度，记为Length(Ls)。每个元素ai（1≤i≤n）称为Ls的成员，它们既可以是单个元素，也可以是一个广义表，分别称为广义表Ls的原子和子表。当广义表Ls非空时，称第一个元素a1为Ls的表头记为head（Ls），称其余元素组成的子表（a2，…，ai，…，an）为Ls的表尾,记为tail(Ls)。一个广义表中的括号嵌套层数称为该广义表的深度,记为Depth(Ls)。广义表是递归定义的。第58页，讲稿共85页，2023年5月2日，星期三广义表例如：下面是一些广义表的例子。A＝（），空广义表，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。第59页，讲稿共85页，2023年5月2日，星期三广义表2．广义表的性质

⑴广义表是一种多层次的数据结构。广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表。可以用树结构表示广义表，其中原子用小矩形表示，子表用圆圈表示。例如，上述例子中的广义表D，画成树的形式如下图所示。第60页，讲稿共85页，2023年5月2日，星期三广义表⑵广义表可以是递归的表。广义表的定义并没有限制元素的递归，即广义表的元素也可以是其自身的子表。例如表E就是一个递归的表。⑶广义表可以为其他表所共享。例如，广义表A、B、C是广义表D的共享子表。在D中可以不必列出子表的值，而用子表的名称来引用。第61页，讲稿共85页，2023年5月2日，星期三广义表二、广义表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．取表头GetHead(L)。12．取表尾GetTail(L)。13．遍历广义表TraverseGList(L,visit())。第62页，讲稿共85页，2023年5月2日，星期三广义表广义表操作举例。对前面所给出的广义表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）＝（）。第63页，讲稿共85页，2023年5月2日，星期三5．4．2广义表的存储一、头尾表示法

广义表中的数据元素既可能是广义表，也可能是原子，相应地在头尾表示法中，结点的结构形式有两种：一种是子表结点，用以表示子表；另一种是原子结点，用以表示原子。在表结点中应该包括一个指向表头的指针和指向表尾的指针；而在原子结点中应该包括所表示原子的元素值。为了区分这两类结点，在结点中还要设置一个标志域，如果标志为1，则表示该结点为子表结点；如果标志为0，则表示该结点为原子结点。结点结构如图所示：第64页，讲稿共85页，2023年5月2日，星期三广义表的存储存储结构定义：typedefenum{ATOM,LIST}Elemtag;//ATOM=0表示单元素；LIST=1表示子表typedefstructGLNode{Elemtagtag;//标志域，用于区分元素结点和表结点

union{//元素结点和表结点的联合部分

AtomTypeatom;//atom是元素结点的值域

struct{structGLNode*hp,*tp;}ptr;//ptr是表结点的指针域，ptr.hp和ptr.tp分别指向表头和表尾

}}*GList;//广义表类型第65页，讲稿共85页，2023年5月2日，星期三广义表的存储举例．对前面所给的广义表A、B、C、D、E、F，存储结构如下图所示。

D＝（A，B，C）=(（），（e），（a，（b，c，d））)第66页，讲稿共85页，2023年5月2日，星期三广义表的存储二、孩子兄弟表示法两种结点形式：一种是有孩子结点，用以表示列表；另一种是无孩子结点，用以表示单元素。在有孩子结点中包括一个指向第一个孩子（长子）的指针和一个指向兄弟的指针；而在无孩子结点中包括一个指向兄弟的指针和该元素的元素值。为了能区分这两类结点，在结点中还要设置一个标志域。如果标志为1，则表示该结点为有孩子结点；如果标志为0，则表示该结点为无孩子结点。结点结构如图所示。第67页，讲稿共85页，2023年5月2日，星期三广义表的存储存储结构定义：typedefenum{ATOM,LIST}Elemtag;//ATOM=0：单元素；LIST=1：子表typedefstructGLNode{Elemtagtag;//标志域，用于区分元素结点和表结点

union{//元素结点和表结点的联合部分

AtomTypeatom;//元素结点的值域

structGLNode*hp;//表结点的表头指针

};structGLNode*tp;//指向下一个结点

}*GList;//广义表类型第68页，讲稿共85页，2023年5月2日，星期三广义表的存储举例．对于前面所给的广义表A、B、C、D、E、F，孩子兄弟表示法如下图所示。

D＝（A，B，C）=(（），（e），（a，（b，c，d））)第69页，讲稿共85页，2023年5月2日，星期三5．4．3广义表的基本操作算法算法思想：假设广义表以串S的形式给出，当广义表为空时，即S=()，此时直接返回L=NULL。当广义表为不空时，S=(a1,a2,…,an)，其中ai(i=1,2,…,n)为S的子串表示的子表。建立广义表S就是建立n个子表结点拉成的链表。第i个（1≤i≤n）表结点的tp指针指向第i+1个表结点，第n个表结点的tp指针为NULL。第i个表结点的hp指针指向由ai建立的子表。由此可见，建立广义表S转化为建立子表ai（1≤i≤n）的问题。而建立子表ai（1≤i≤n）的过程与建立广义表S的过程完全相同，这显然是一个递归问题。对每个ai又分三种情况：（1）ai是带括号的空串；（2）ai是长度为1的单字符串；（3）ai是长度大于1的字符串。前两种情况就是递归的终结状态，第三种情况是递归调用。

第70页，讲稿共85页，2023年5月2日，星期三广义表的基本操作算法递归过程如下：基本项：置空广义表，当S为空表串时；建立原子结点子表，当S为单字符串时；归纳项：假定S=(a1,a2,…,an)，sub=’s1,s2,…,sn’是S脱去的最外层括号之后的字符串，其中si(i=1,2,…,n)是非空的字符串，对每个si建立一个表结点，结点的hp指针域指向由si建立的子表，tp指针指向由si+1（i<n）建立的表结点，最后一个表结点的tp指针为NULL。

第71页，讲稿共85页，2023年5月2日，星期三广义表的基本操作算法算法描述：statusCreateGLint(GList&L,SStringS){if(StrEmpty(S))L=NULL;//创建空表

else{if(!(L=(GList)malloc(sizeof(GLNode))))exit(OVERFLOW);//建表结点

if(StrLength(S)==1){L->tag=ATOM;L->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=p;}}while(!StrEmpty(sub));q->ptr.tp=NULL;}}returnOK;}第72页，讲稿共85页，2023年5月2日，星期三广义表的基本操作算法statussever(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;elseif(ch==')')--k;}if(i<=n){hstr=SubStr(hstr,str,1,i-2);str=SubStr(str,str,i,n-i+1);}else{StrCopy(hstr,str);ClearStr(str);}}第73页，讲稿共85页，2023年5月2日，星期三广义表的基本操作算法二、取广义表的头、尾部分算法思想很简单，只要返回表头或表尾结点的指针即可。GListGetHead(GListL){if(L->tag==1)p=L->hp;returnp;}GListGetTail(GListL){if(L->tag==1)p=L->tp;returnp;}

第74页，讲稿共85页，2023年5月2日，星期三广义表的基本操作算法三、求广义表的深度设广义表LS=(a1,a2,…,an)，求广义表深度的递归形式如下：基本项：Depth(LS)=1，当LS为空广义表；

Depth(LS)=0，当LS为原子时；归纳项：Depth(LS)=1+max{Depth(si)|1<=i<=n}，n>=1。算法描述：intGListDepth(GListL){if(!L)return1;//空表深度为1

if(L->tag==ATOM)return0;//单元素深度为0

for(max=0,p=L;p;p=p->ptr.tp){dep=GListDepth(p->ptr.hp);//求以p->ptr.hp尾头指针的子表深度

if(dep>max)max=dep;}

returnmax+1;//非空表的深度是各元素的深度的最大值加1

}第75页，讲稿共85页，2023年5月2日，星期三广义表的基本操作算法四、求广义表的长度算法思想：只需统计最顶层的表结点个数即可。算法描述：intGListLength(GListL){if(L)return1+GListLength(L->tp);elsereturn0;}

第76页，讲稿共85页，2023年5月2日，星期三广义表的基本操作算法五、复制广义表算法思想：将广义表分成表头和表尾两部分，先复制表头部分，再复制表尾部分。若表头部分是原子，就建立一个原子结点，若表头是子表，则又将分成表头和表尾两部分处理。表尾一定是子表，又分成表头和表尾两部分处理。复制整个广义表和复制子表的过程完全相同。设复制后的广义表为NewLS，递归过程如下：基本项：InitGList(NewLS),当LS为空广义表，置空表；归纳项：COPY(GetHead(LS),GetHead(NewLS))//复制表头

COPY(GetTail(LS),GetTail(NewLS))//复制表尾

第77页，讲稿