第5章 数组和广义表 本章主题：多维数组、特殊矩阵和广义表 教学目的：掌握数组和广义表的定义、运算及存储结构 教学难点：矩阵的压缩存储

Presentation on theme: "第5章 数组和广义表 本章主题：多维数组、特殊矩阵和广义表 教学目的：掌握数组和广义表的定义、运算及存储结构 教学难点：矩阵的压缩存储"— Presentation transcript:

1 第5章 数组和广义表 本章主题：多维数组、特殊矩阵和广义表 教学目的：掌握数组和广义表的定义、运算及存储结构 教学难点：矩阵的压缩存储
第5章 数组和广义表 本章主题：多维数组、特殊矩阵和广义表 教学目的：掌握数组和广义表的定义、运算及存储结构 教学难点：矩阵的压缩存储 2019/4/28

2 本章学习导读 1．多维数组的定义及在计算机中的存储表示； 2．对称矩阵、三角矩阵、对角矩阵等特殊矩阵在计算机中的压缩存储表示及地址计算公式；
本章主要介绍数组的概念及多维数组在计算机中的存放，特殊矩阵的压缩存储及相应运算，广义表的概念和存储结构及其相关运算的实现。通过本章学习，要求掌握如下内容： 1．多维数组的定义及在计算机中的存储表示； 2．对称矩阵、三角矩阵、对角矩阵等特殊矩阵在计算机中的压缩存储表示及地址计算公式； 3．稀疏矩阵的三元组表示及转置算法实现； 4．稀疏矩阵的十字链表表示及相加算法实现； 5．广义表存储结构表示及基本运算。 2019/4/28

3 数组和广义表可看成是一种特殊的线性表，其特殊在于，表中的数所元素本身也是一种线性表。
5.1 数 组 数组和广义表可看成是一种特殊的线性表，其特殊在于，表中的数所元素本身也是一种线性表。 数组的定义 数组是大家都已经很熟悉的一种数据类型，几乎所有高级语言程序设计中都设定了数组类型。 数组（Array）是由n(n>1)个相同类型数据元素a0，al，…ai…，an-1构成的有限序列。n是数组的长度。其中数组中的数据元素ai是一个数据结构，即ai可以是线性表中的一个元素，本身也可以是一个线性表，而线性子表中的每一个数据元素还可以再分解…… 。根据数组元素ai的组织形式不同，数组可以分为一维数组、二维数组以及多维（n维）数组。 2019/4/28

4 有时也把一维数组称为向量，二维数组称为矩阵。在二维或多维数组中，每个数组元素都受到2个或n个关系的约束。当数组为n维时，其对应线性表中的每个元素又是一个线性表。在每个关系中，每个元素都有一个直接后继。因此，就其单个关系而言，这n个关系中的每一个仍然是一种线性关系。 数组中每个元素都是由一个值和一组下标来确定的。同线性表一样，数组中的所有数据元素都必须属于同一数据类型。元素下标的个数被称为数组的维数。显然，当维数为1时，数组就退化为定长的线性表。 2019/4/28

5 一维数组可以看成是一个线性表或一个向量，它在计算机内是存放在一块连续的存储单元中，适合于随机查找。
1．一维数组 一维数组可以看成是一个线性表或一个向量，它在计算机内是存放在一块连续的存储单元中，适合于随机查找。 一维数组记为A[n]或A=( a0，al，…ai，…，an-1) 一维数组中，一旦a0的存储地址、一个数据元素所占存储单元数k确定，则ai的存储地址LOC(ai)就可求出： LOC(ai)=LOC(a0)+i*k (0≤i<n) 2．二维数组 二维数组，又称矩阵(matrix)。二维数组中的每一个元素又是一个定长的线性表（一维数组），都要受到两个关系即行关系和列关系的约束，也就是每个元素都同属于两个线性表。例如，设A是一个有m行n列的二维数组，则A可以表示为： 2019/4/28

6 可以看成由m个行向量组成的向量，也可以看由n个列向量组成的向量。
数组中的每个元素由元素值aij及一组下标（i，j）来确定。aij既属于第i行的行向量，又属于第j列的列向量。 其中，ai=( ai,0 ai,1 … ai,n-1) (0≤i＜n) 可以认为Am*n=A，A是这样的一维数组： A=( a0，al，…，ai，…，am-1) 2019/4/28

7 (1) 数组中的数据元素数目固定。一旦定义了一个数组，其数据元素数目不再有增减变化。它属于静态分配存储空间的数据结构。
显然，二维数组同样满足数组的定义。一个二维数组可以看作是每个数据元素都是相同类型的一维数组。以此类推，任何多维数组都可以看作一个线性表，这时线性表中的每个数据元素也是一个线性表。多维数组是特殊的线性表，是线性表的推广。 数组的性质： (1) 数组中的数据元素数目固定。一旦定义了一个数组，其数据元素数目不再有增减变化。它属于静态分配存储空间的数据结构。 (2) 数组中的数据元素必须具有相同的数据类型。 (3) 数组中的每个数据元素都有一组唯一的下标值。 (4) 数组是一种随机存储结构。可随机存取数组中的任意数据元素。 2019/4/28

8 5.1.2 数组的基本操作 数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组的基本操作一般不会含有元素的插入或删除等操作,数组只有访问数组元素和修改元素值的操作。 (1) value(A，indexl，index2，…，indexd)：A是已存在的d维数组，indexl，index2，…，indexd是指定的d个下标值，且这些下标均不超过对应维的上界。其运算结果是返回由下标指定的A中的对应元素的值。 (2) assign(A，e，indexl，index2，…，indexd)：A是已存在的d维数组，e为元素变量，indexl，index2，…，indexd是指定的d个下标值，且这些下标均未越界。其运算结果是将e的值赋给由下标指定的A中的对应元素。 2019/4/28

9 (3) disp(A)：输出数组A的所有元素。
在大多数程序设计语言中，取数组元素值操作value(A，indexl，index2，…，indexd) 通常直接写作A[indexl][ index2]…[indexd]，而对数组元素的赋值操作assign(A，e，indexl，index2，…，indexd)写作e= A[indexl][ index2]…[indexd]，或者类似的形式。 2019/4/28

10 由于数组一般不作删除或插入运算，所以一旦数组被定义后，数组中的元素个数和元素之间的关系就不再变动。通常采用顺序存储结构表示数组。
5.1.3 数组的存储结构 由于数组一般不作删除或插入运算，所以一旦数组被定义后，数组中的元素个数和元素之间的关系就不再变动。通常采用顺序存储结构表示数组。 对于一维数组，数组的存储结构关系为: LOC(ai)=LOC(a0)+i * k (0≤i<n) 对于二维数组，由于计算机的存储单元是一维线性结构，如何用线性的存储结构存放二维数组元素就有行/列次序问题。常用两种存储方法：以行序(row major order)为主序的存储方式和以列序(column major order)为主序的存储方式。 2019/4/28

11 ⑴行优先顺序——将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为：
a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn 在PASCAL、C语言中，数组就是按行优先顺序存储的。 ⑵列优先顺序——将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后，A的m*n个元素按列优先顺序存储的线性序列为： a11,a21,…,am1,a12,a22,…am2,……,an1,an2,…,anm 在FORTRAN语言中，数组就是按列优先顺序存储的。 2019/4/28

12 LOC(ai,j)=LOC(a0,0)+(i×n+j) k 其中n为每行中的列数。
图 5-1 二维数组的两种存储结构 对一个以行序为主序的计算机系统，当二维数组第一个数据元素a0,0的存储地址LOC(a0,0)以及每个数据元素所占用的存储单元k确定后，该二维数组中任一数据元素ai,j的存储地址可由下式确定: LOC(ai,j)=LOC(a0,0)+(i×n+j) k 其中n为每行中的列数。 2019/4/28

13 LOC(ai,j)=LOC(a0,0)+(i×n+j) k 其中n为每行中的列数。
图 5-1 二维数组的两种存储结构 对一个以行序为主序的计算机系统，当二维数组第一个数据元素a0,0的存储地址LOC(a0,0)以及每个数据元素所占用的存储单元k确定后，该二维数组中任一数据元素ai,j的存储地址可由下式确定: LOC(ai,j)=LOC(a0,0)+(i×n+j) k 其中n为每行中的列数。 2019/4/28

14 【例5-1】对于给定的二维数组float a[3][4]，计算： (1) 数组a中的数组元素数目；
【解】(1)由于C语言中数组的行、列下标值的下界均为0，该数组行上界为3-1=2，列上界为4-1=3，所以该数组的元素数目共有3*4=12个。 (2)由于C语言采用行序为主序的存储方式，有： LOC(a2,3)=LOC(a0,0)+(i*n+j)*k =1000+(2*4+3)*4 =1044 2019/4/28

15 【例5-2】有m名学生，每人考n门功课，试写出求任一学生总分数和任一课程总分数的数据结构和算法。
【解】把学生的考试成绩存放在m行n列的二维数组中，则第i(0≤i<m)行第j(0≤j<n)列中存放了第i个学生的第j门课程考试成绩。即数据结构为： #define M //假设<学生人数>为10人 #define N //假设<课程门数>为3 int score[M][N]; //学生成绩二维数组 求第i名学生总分数的算法为： int student_sum(int score[M][N],int i) { int j,sum=0; for(j=0;j<N;j++) sum=sum+score[i][j]; return(sum); } 2019/4/28

16 int course_sum(int score[M][N],int j) { int i,sum=0;
for(i=0;i<M;i++) sum=sum+score[i][j]; return(sum); } 2019/4/28

17 5.2 矩阵的压缩存储 矩阵是数值计算程序设计中经常用到的数学模型，它是由 m 行和 n 列的数值构成（当m=n 时称为方阵）。在高级程序设计语言中，通常用二维数组表示矩阵。然而在数值分析过程中经常遇到一些比较特殊的矩阵，它们的阶数很高，矩阵中元素数量很大，而且有很多元素的值相同或零值元素，如对称矩阵、三角矩阵、带状矩阵和稀疏矩阵等。为了节省存储空间并且加快处理速度，需要对这类矩阵进行压缩存储，压缩存储的原则是：不重复存储相同元素；不存储零值元素。 2019/4/28

18 特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。主要形式有对称矩阵、三角矩阵、对角矩阵等。
5.2.1 特殊矩阵的压缩存储方法 特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。主要形式有对称矩阵、三角矩阵、对角矩阵等。 1．对称矩阵的压缩存储 对称矩阵是一个n阶方阵。若一个n阶矩阵A中的元素满足: ai,j=aj,I (0≤i，j≤n-1)，则称A为n阶对称矩阵。 a00 a10 a 11 a20 a a23 ……………….. an-1 0 a n-1 1 a n-1 2 …a n-1 n-1 对称矩阵 2019/4/28

19 在这个下三角矩阵中，第i行恰有i+1个元素，元素总数为：
(i+1)=n(n+1)/2 由于对称矩阵中的元素关于主对角线对称，因此可以为每一对对称的矩阵元素分配 1 个存储空间，n阶矩阵中的n×n个元素就可以被压缩到 n(n+1)/2 个元素的存储空间中去。 对称矩阵的压缩存储 称一维数组sa[0..n(n+1)/2] 为n 阶对称矩阵A的压缩存储。其存储对应关系如上图 : 2019/4/28

20 2．三角矩阵的压缩存储 三角矩阵也是一个n阶方阵，有上三角和下三角矩阵。下(上)三角矩阵是主对角线以上（下）元素均为零的n阶矩阵。设以一维数组sb[0..n(n+1)/2]作为n阶三角矩阵B的存储结构，仍采用按行存储方案，则B中任一元素bi,j和sb[k]之间存在着如下对应关系： 其中，sb[n(n+1)/2]中存放常数c或0。 2019/4/28

21 3．对角矩阵的压缩存储 对角方阵(或称带状矩阵)是指所有的非零元素(简称非零元)都集中在以主对角线为中心的带状区域中，即除了主对角线上和紧靠着主对角线上下方若干条对角线上的元素外，所有其它元素皆为零的矩阵。常见的有三对角矩阵、五对角矩阵、七对角矩阵等。下图是一个具有3(1≤m＜n)条非零元素带的n阶对角矩阵。 具有3条非零对角线的对角矩阵 2019/4/28

22 对于n阶有m (m必为奇数，因为副对角线关于主对角线对称) 条非零元素带的对角矩阵，只需存放对角区域内的所有非零元素即可。
在n阶对角矩阵A中，主对角线元素数最多（n个），然后向两边依次减少，每隔一条元素带元素数就减少1个，最外端的对角线有n-(m-1)/2个元素，所以非零元素总数u为： u=m×n-2×[(m-1)/2+((m-1)/2-1)+…+l] =m×n-(m2-1)/4 设以一维数组sa[u+l]为对角矩阵A的存储结构，若按行存储非零元，则A中任一元素ai,j和sa[k]之间存在着如下对应关系： 结论：对特殊矩阵的压缩存储实质上就是将二维矩阵中的部分元素按照某种方案排列到一维数组中，不同的排列方案也就对应不同的存储方案。 2019/4/28

23 5.2.2 稀疏矩阵的压缩存储方法 如果一个矩阵中有很多元素的值为零，即零元素的个数远远大于非零元素的个数时，称该矩阵为稀疏矩阵。
根据存储时所附加信息的不同，稀疏矩阵的顺序存储方法包括：三元组表示法、带辅助行向量的二元组表示法和伪地址表示法，其中以三元组表示法最常用。 三元组表示法就是在存储非零元的同时，存储该元素所对应的行下标和列下标。稀疏矩阵中的每一个非零元素由一个三元组(i，j，aij)唯一确定。矩阵中所有非零元素存放在由三元组组成的数组中。 由线性表的两种不同存储结构可以得到稀疏矩阵压缩的不同的存储方法。 2019/4/28

24 (a) 稀疏矩阵 (b) 三元组表示 假设有一个6×7阶稀疏矩阵A，其元素情况以及非零元对应的三元组表（以行序为主序）如图所示。
2019/4/28

25 1．三元组顺序表 假设以行序为主序，且以一维数组作为三元组表的存储结构，可以得到稀疏矩阵的一种压缩存储方法，称为三元组顺序表。三元组顺序表的数据结构定义如下： #define NUM //矩阵中非零元素最大个数 typedef struct //三元组结构 { int r, c; //行(列)号 ElemType d; //元素值 }tupletype; //三元组定义 typedef struct { int rows; //矩阵行数值 int cols; //矩阵列数值 int nums; //非零元素个数 tupletype data[NUM]; //三元组表 }table; //三元组顺序表定义 2019/4/28

26 对于一个m×n的矩阵其转置矩阵是一个n×m的矩阵，设为Bn×m 且满足ai ,j=bj,i
1．稀疏矩阵的转置运算 转置是矩阵中最简单的一种运算。 对于一个m×n的矩阵其转置矩阵是一个n×m的矩阵，设为Bn×m 且满足ai ,j=bj,i 即：a[i][j]=b[j][i]，其中：0≤i≤m-1，0≤j≤n-1 即A的行是B的列，A的列是B的行。 稀疏矩阵的三元组表 2019/4/28

27 三元组表示的稀疏矩阵的转置常用的算法有以下两种： 1）矩阵的列序转置（传统的转置算法）
矩阵A是按行序为主序存储的，若按列序为主序进行转置就可以得到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.rows; //m为矩阵A的列数 n=ma.cols; //n为矩阵A的行数 t=ma.nums; //为矩阵中非零元素个数 mb.rows=n; //转置矩阵B的列数 mb.cols; //转置矩阵B的行数 mb.nums=t; //转置矩阵中的非零元素个数 for(i=0;i<n;i++) //按矩阵A的列序扫描 2019/4/28

28 for (j=0；j＜m；j++＝ b[i][j]=a[j][i]； 此时，时间复杂度为O(m×n) 。
for(j=0;j<t;j++) if(ma.data[j].c==i) //判断第j个三元组是不是第i列的 { mb.data[k].r=ma.data[j].c; mb.data[k].c=ma.data[j].r; mb.data[k++].d=ma.data[j].d; } return(1); //成功完成矩阵转置 以上算法的时间复杂度分析：若n为转置矩阵的列数，t为矩阵中非零元素个数，则算法的时间花费主要在两个循环上，所以若时间复杂度为O(n×t)。也就是说，时间的花费和矩阵A的列数和非零元素个数的乘积成正比。若用m×n的二维数组表示矩阵，则相应的矩阵转置算法的循环为： for ( i=0；i＜n；i++ ) for (j=0；j＜m；j++＝ b[i][j]=a[j][i]； 此时，时间复杂度为O(m×n) 。 2019/4/28

29 2）快速转置算法： 三元组顺序表虽然节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算是法的难度。因此，此算法仅适用于t<=m*n的情况。 其算法思想为：对A扫描一次，按A第二列提供的列号一次确定位置装入B的一个三元组。具体实施如下：一遍扫描先确定三元组的位置关系，二次扫描由位置关系装入三元组。可见，位置关系是此种算法的关键。 为了预先确定矩阵M中的每一列的第一个非零元素在数组T中应有的位置，需要先求得矩阵M中的每一列中非零元素的个数。因为矩阵M中第一列的第一个非零元素在数组T中应有的位置等于前一列第一个非零元素的位置加上前列非零元素的个数。 2019/4/28

30 为此，需要设置两个一维数组num[0..n]和rpos[0..n]： num[0..n]：统计M中每列非零元素的个数。
rpos[0..n]：M中的每列第一个非零元素在T中的位置。 算法通过rpos数组建立位置对应关系： rpos[0]=0 ； rpos[col]=rpos[col-1]+num[col-1] ＜col＜M.rows； 例如图5-4(a) 所示的稀疏矩阵的三元组表对应的num[0..n-1]和rpos[0..n-1]如图5-5所示。 图5-5 矩阵的num和rpos 数组值 （算法见教科书） 2019/4/28

31 快速转置算法如下： void fasttranstri(tritupletable b,tritupletable a){
int p,q,col,k; int num[0..a.n],copt[0..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) num[col]=0; for(k=1;k<=a.t;++k) ++num[a.data[k].j]; cpot[0]=1; for(col=2;col<=a.t;++col) cpot[col]=cpot[col-1]+num[col-1]; for(p=1;p<=a.t;++p){ col=a.data[p].j; q=cpot[col]; b.data[q].i=a.data[p].j; b.data[q].j=a.data[p].i; b.data[q].v=a.data[p].v; ++cpot[col]; } 2019/4/28

32 triple data[maxsize]; int rpos[maxrow]; int n,m,t; }rtripletable
2．行逻辑链接的顺序表(带行表的三元组) 有时为了方便某些矩阵运算，在按行优先存储的三元组中，加入一个行表来记录稀疏矩阵中每行的非零元素在三元组表中的起始位置。当将行表作为三元组表的一个新增属性加以描述时，就得到了稀疏矩阵的另一种顺序存储结构：带行表的三元组表。称这种“带行链接信息”的三元组表为行逻辑链接的顺序表。 其类型描述如下： #define maxrow 100 typedef struct{ triple data[maxsize]; int rpos[maxrow]; int n,m,t; }rtripletable 2019/4/28

33 下面讨论两个稀疏矩阵相乘的例子，容易看出这种表示方法的优越性： 若设 Q=M*N 其中，M是m1*n1矩阵，N是m2*n2矩阵。
for(i=1;i<=m1;++i) for(j=1;j<=n2;++j){ q[i][j]=0 for(k=1;k<=n1;++k) q[i][j]+=m[i][k]*n[k][j]; } 此算法的复杂度为O(m1*n1*n2)。 2019/4/28

34 3． 十字链表 稀疏矩阵中非零元的位置或个数经常变动时，三元组就不适合于作稀疏矩阵的存储结构，此时，采用链表作为存储结构更为恰当。 十字链表为稀疏矩阵中的链接存储中的一种较好的存储方法，在该方法中，每一个非零元用一个结点表示，结点中除了表示非零元所在的行、列和值的三元组（i,j,v）外，还需增加两个链域：行指针域（rptr），用来指向本行中下一个非零元素；列指针域（cptr），用来指向本列中下一个非零元素。稀疏矩阵中同一行的非零元通过向右的rptr指针链接成一个带表头结点的循环链表。同一列的非零元也通过cptr指针链接成一个带表头结点的循环链表。因此，每个非零元既是第i行循环链表中的一个结点，又是第j列循环链表中的一个结点，相当于处在一个十字交叉路口，故称链表为十字链表。 2019/4/28

35 另外，为了运算方便，我们规定行、列循环链表的表头结点和表示非零元的结点一样，也定为五个域，且规定行、列、域值为0(因此，为了使表头结点和表示非零元的表结点不发生混淆，三元组中，输入行和列的下标不能从0开始!!!而必须从1开始)，并且将所有的行、列链表和头结点一起链成一个循环链表。 在行（列）表头结点中，行、列域的值都为0，故两组表头结点可以共用，即第i行链表和第i列链表共用一个表头结点，这些表头结点本身又可以通过V域（非零元值域，但在表头结点中为next，指向下一个表头结点）相链接。另外，再增加一个附加结点（由指针hm指示，行、列域分别为稀疏矩阵的行、列数目），附加结点指向第一个表头结点，则整个十字链表可由hm指针惟一确定。 2019/4/28

36 3． 十字链表 用三元数组的结构来表示稀疏矩阵，在某些情况下可以节省存储空间并加快运算速度。但在运算过程中，若稀疏矩阵的非零元素位置发生变化，必将会引起数组中元素的频繁移动。这时，采用链式存储结构(十字链表)表示三元组的线性表更为恰当。 十字链表(orthogonal list)是稀疏矩阵的另一种存储结构。它是用多重链表来存储稀疏矩阵。十字链表适用于操作过程中非零元素的个数及元素位置变动频繁的稀疏矩阵。 十字链表为矩阵中的每一行设置一个单独链表，同时也为每一列设置一个单独链表。这样，矩阵中的每个非零元就同时包含在两个链表中（即所在行和所在列的链表）。这就大大降低了链表的长度，方便了算法中行方向和列方向的搜索，大大降低了算法的时间复杂度。 2019/4/28

37 对于一个m×n的稀疏矩阵，每个非零元用一个含有五个域的结点来表示。如图5-6所示。其中各分量含义如下：
(1) 矩阵中非零元素的行号i； (2) 矩阵中非零元素的列号j； (3) 矩阵中非零元素的值value； (4) 向右域right，用以链接同一行中下一个非零元素； (5) 向下域down，用以链接同一列中下一个非零元素。长度，方便了算法中行方向和列方向的搜索，大大降低了算法的时间复杂度。 即同一行的非零元素通过right域链接成一个链表，同一列的非零元素通过down域链接成一个链表，每一个非零元既是某个行链表中的结点，同时又是某个列链表中的结点。整个矩阵构成了一个十字交叉的链表。故称为十字链表。 2019/4/28

38 (a) 结点结构 (b) 头结点结构 图5-6 十字链表结点结构 例如，假设稀疏矩阵B3ⅹ4为 对应矩阵B3ⅹ4的十字链表如图5-7所示。为图示方便清楚，把每个行列头结点分别画成两个（一个行头结点和一个列头结点），而实际上，行头结点hi(0≤i≤4)与列头结点hi是存在于一个行列头结点中的。 2019/4/28

39 图 5-7 稀疏矩阵的十字链表 2019/4/28

40 综上所述，稀疏矩阵的十字链表表示共有三种线性链表： (1) 由各行(列)表头结点组成的线性链表，其结点之间用各结点的next域相链接。
(2) 由同一行中的非零元素结点组成的线性链表，其结点之间用各结点的right域相链接。 (3)由同一列中的非零元素结点组成的线性链表，其结点之间用各结点的down域相链接。 2019/4/28

41 十字链表结点结构和头结点的数据结构可定义如下： #define M 3 //矩阵行数 #define N 4 //矩阵列数
#define Max((M)>(N)?(M)：(N)) //矩阵行列较大者 typedef struct mtxn { int row； int col； struct mtxn *right，*down； union { int value； struct mtxn *next； }tag； } MatNode； 2019/4/28

42 5.3 广义表的定义 5.3.1 广义表的定义 1．广义表的定义 广义表也是线性表的推广，是一种多层次的线性结构，线性表中的元素仅限于原子项，即不可以再分； 而广义表中的元素既可以是原子项，也可以是子表（另一个线性表）。主要用于人工智能领域的表处理语言LISP语言。 广义表是n≥0个元素a1，a2，…，an的有限序列，其中每一个ai或者是原子，或者是一个子表。广义表通常记为LS=(a1,a2,…,an)，其中LS为广义表的名字，n为广义表的长度， 每一个ai为广义表的元素。但在习惯中，一般用大写字母表示广义表，小写字母表示原子。 若n=0时为空表。记作：L=( )。 2019/4/28

43 2）B=(e) B是一个只含有原子e的表，其长度为l； 。 3）C=(a，(b，c，d))
当广义表L非空(n＞0)时，第一个数据元素a0被称为广义表的表头(head)，其余数据元素组成的表(a1，…an-1) 被称为广义表L的表尾(tail)，分别记为head(A)= a0，tail=(a1，…an-1)。 因此：一个广义表是由表头和表尾构成的。 2．广义表举例 1）A=( ) A为空表，长度为0。 2）B=(e) B是一个只含有原子e的表，其长度为l； 。 3）C=(a，(b，c，d)) C是长度为2的广义表，第一项为原子，第二项为子表。 4）D= (A，B，C)=(()，(e)，(a，(b，c，d))) 5）E=((a，(a，b)，((a，b)，c))) E 中只含有一个元素，该元素是一个表，E的长度为l。 6）F=(a，F)=(a，(a，(a，...))) F是长度为2的广义表，第一项为原子，第二项为它本身。 2019/4/28

44 3．广义表的表示方法（用次序关系和层次关系表示） （1）用L=(a1，a2，…，an)形式，其中每一个ai为原子或广义表
例如：A=(b,c) B=(a,A) E=(a,E) 都是广义表。 （2）将广义表中所有子表写成原子形式，并利用圆括号嵌套 例如，广义表A、B、C可以描述为： A(b,c) B(a,A(b,c)) E(a,E(a,E（…）)) （3）将广义表用树和图来描述 （层次关系） 上面提到的广义表A、B、C的描述见图5-8。 （次序关系） 2019/4/28

45 广义表中数据元素的最大层次为表的深度。数据元素的层次就是包括该元素韵括号对 的数目。例如广义表G=(a，b，(c，(d)))中，数据元素a，b在第一层，数据元素c在第二层，数据元素d在第三层，广义表G的深度为3。 （次序关系） 图 5-8 广义表的图形表示 从图5-8可以看出：广义表的图形表示像倒着画的一棵树，树根结点代表整个广义表，各层树枝结点代表相应的子表，树叶结点代表单元素或空表（如A表）。 2019/4/28

46 例如，A=(b,c)的深度为1，B=(A,d)的深度为2，C=(f,B,h)的深度为3; 广义表兼有线性结构和层次结构的特性，归纳如下：
4．广义表的深度 一个广义表的深度是指该广义表展开后所含括号的层数。 例如，A=(b,c)的深度为1，B=(A,d)的深度为2，C=(f,B,h)的深度为3; 广义表兼有线性结构和层次结构的特性，归纳如下： (1) 广义表中的数据元素有固定的相对次序； (2) 广义表的长度定义为最外层括弧中包含的数据元素个数； (3) 广义表的深度定义为广义表书写形式中括弧的最大重数，因此空表的深度为1，因为一个单元素不是广义表，所以从定义上讲没有深度可言，但可以认为它的深度为0； (4) 广义表可被其它广义表所共享。例如上述例子中广义表B同时也是广义表 D 中的一个子表； (5) 广义表可以是一个自递归的表。例如上述例子中的广义表 F，自递归的广义表的长度是个有限值，而深度为无限值。 2019/4/28

47 （2）纯表：与树对应的广义表，见图5-8的(c) 、(d)、 (e) 。 （3）再入表：与图对应的广义表(允许结点共享)，
5．广义表的分类 （1）线性表：元素全部是原子的广义表。 （2）纯表：与树对应的广义表，见图5-8的(c) 、(d)、 (e) 。 （3）再入表：与图对应的广义表(允许结点共享)， （4）递归表：允许有递归关系的广义表，例如E=(a,E)。 这四种表的关系满足：递归表再入表 纯表  线性表 再入表 2019/4/28

48 广义表的存储结构 由于广义表的元素类型不一定相同，表中的数据元素可以是单元素（原子项），也可以是广义表，因此，难以用顺序结构存储表中元素，通常采用链接存储方法来存储广义表中元素，并称之为广义链表。需要两种结构的结点： (1) 表结点：用以表示广义表。由三个域组成：标志域tag、指向表头的指针域sublist和指向下一个结点的指针域link。如图5-9(a)所示。 (2) 原子结点：用以表示原子项。由三个域组成：标志域tag、值域data和指向下一个元素结点的指针域link。如图5-9(b)所示。 2019/4/28

49 每个数据元素都可用表结点或原子结点表示。它们的主要区别在于从不同的角度反映广义表的构成。
例如，广义表C的链表存储结构如图5-10所示。 二叉树 图 广义表(a,(b,c,d))的链表存储结构图 2019/4/28

50 可将一个广义表看成一棵树，为了方便存储，通常将其转换成一棵二叉树 。广义表C转换成二叉树过程 如图5-11所示：
广义表的链式结构描述如下： typedef char ElemType; typedef struct glnode { int tag; union { ElemType data; struct glnode *sublist; }val; struct glnode *link; }GListNode; 可将一个广义表看成一棵树，为了方便存储，通常将其转换成一棵二叉树 。广义表C转换成二叉树过程 如图5-11所示： 2019/4/28

51 广义表C 图5-11 广义表的转换过程 2019/4/28

52 5.3.3 广义表的基本操作 广义表的基本操作主要有： 求广义表的长度和深度、向广义表插入元素和从广义表中查找或删除元素、建立广义表的存储结构、输出广义表和复制广义表等。 由于广义表是一种递归的数据结构，所以对广义表的运算一般采用递归的算法。 1．求广义表的长度 在广义表中，同一层次的每个结点是通过1ink域链接起来的，可把它看做是由1ink域链接起来的单链表。 求广义表的长度就变成求单链表的长度，则它的深度可以递归求出。 2019/4/28

53 求广义表长度的递归算法如下： int GListLength(GListNode *h) //h为一个广义表头结点的指针 { int n=0; h=h->val.sublist; //h指向广义表的第一个元素 while(h!=NULL) { n++; h=h->link; } return n; 2．求广义表的深度 广义表深度的递归定义是：它等于所有子表中表的最大深度加1。若一个表为空或仅由单元素所组成，则深度为l。求广义表深度的递归函数GListDepth()如下： 2019/4/28

54 max{GListDepth(sh)|sh为h的子表}+1 其它情况
GListDepth(h)= max{GListDepth(sh)|sh为h的子表} 其它情况 int GListDepth(GListNode *h) { //h为广义表头结点的sublist域值或为不带头结点的广义表 int max=0,dep; //max中存放子表的最大深度 while(h!=NULL) //遍历表中的每一个结点 { if(h->tag==1) //只需要求出子表深度即可，单元素深度为0 { dep=GListDepth(h->val.sublist); //递归调用求出子表的深度 if(dep>max) //让max始终为同一层所求过的子表中深度的最大值 max=dep; } h=h->link; //使h指向同一层的下一个结点 return max+l; //返回表的深度 2019/4/28

55 例如“(a，(b，c，d))”，就是一个符合上述规定的广义表格式（注意：不包括引号）。
3．建立广义表的存储结构 假设广义表以单链表的形式存储，广义表的元素类型elemtype 为字符型char，广义表由键盘输入，假定全部为字母，输入格式为：元素之间用逗号分隔，表元素的起止符号分别为左、右圆括号，空表在其圆括号内使用一个“#”字符表示，最后使用一个分号作为整个广义表的结束。 例如“(a，(b，c，d))”，就是一个符合上述规定的广义表格式（注意：不包括引号）。 建立广义表存储结构的算法同样是一个递归算法。 2019/4/28

56 GListNode *GListCreat(char *s) { GListNode *h; char ch;
建立广义表的算法如下： GListNode *GListCreat(char *s) { GListNode *h; char ch; ch=*s; //取一个扫描字符 s++; //串指针后移一位 if(ch!=’\0’) //串未结束判断 { h=(GListNode*)malloc(sizeof(GListNode))；//创建一个新结点 if(ch==’(’ ) //当前字符为左括号时 { h->tag=l; //新结点作为表头结点 h->val.sublist=GListCreat(s); //递归构造子表并链到表头结点 } else if(ch==’)’) //遇到’)’字符，子表为空 h=NULL; else { h->tag=0; //新结点作为单元素结点 h->val.data=ch; 2019/4/28

57 h->link=GListCreat(s); //递归构造后续子表 else //串结束
h=NULL; //串结束，子表为空 ch=*s; //取下一个扫描字符 s++; //串指针后移一位 if(h!=NULL) //串未结束判断 if(ch=’,’) //当前字符为 h->link=GListCreat(s); //递归构造后续子表 else //串结束 h->link=NULL; //处理表的最后一个元素 return h; //返回广义表指针 } 2019/4/28

58 4． 输出广义表 以h作为带表头附加结点的广义表的表头指针，打印输出该广义表时，需要对子表进行递归调用。当h结点为表元素结点时，应首先输出作为一个表的起始符号的左括号，然后再输出以h->sublist为表头指针的表；当h结点为单元素结点时，则应输出该元素的值。当以h->sublist为表头指针的表输出完毕后，应在其最后输出一个作为表终止符的右括号。当h结点输出结束后，若存在后继结点，则应首先输出一个逗号作为分隔符，然后再递归输出由h->link指针所指向的后继表。 2019/4/28

59 void DispGList(GlistNode h) //h为一个广义表的头结点指针 { if(h!=NULL) //表不为空判断
算法描述如下： void DispGList(GlistNode h) //h为一个广义表的头结点指针 { if(h!=NULL) //表不为空判断 { if (h->tag==1) //为表结点时 { printf(“(“); //输出左括号 if(h->val.sublist==NULL) printf(“”); //输出空子表 else DispGList(h->val.sublist); //递归输出子表 } else //为原子结点时 printf(“%c”,h->val.data); //输出元素值 if(h->tag==1) //为表结点时 printf(“)”); //输出右括号 if(h->link!=NULL) { printf(“,”); DispGList (h->link); //递归输出后续表的内容 2019/4/28

60 5．广义表的复制 复制一个广义表的过程如下：对于广义表的头结点*p，若为空，则返回空指针；若为表结点，则递归复制子表；否则，复制单元素结点，然后再递归复制后续表。返回复制后的广义表链表的指针。其算法如下： GListNode *GListCopy(GListNode *p) /*p为被被复制的广义表的头结点指针*/ { GListNode *q; if(p==NULL) return NULL； q=(GListNode*)malloc(sizeof(GListNode)); q->tag=p->tag; if(p->tag==1) q->val.sublist= GListCopy(p->val.sublist); else q->val.data=p->val.data; q->link=GListCopy(p->link); return q; } 2019/4/28

61 【例5-5】设计一个算法DelNode(*h，x)，删除广义表h中所有值为x的元素。例如，DelNode((a，(a))，a)的结果为(( ))。
【解】让p指向广义表的第1个元素，循环处理所有的元素，删除元素的过程如下：当p为单元素时，如果其data域值为x，则删除之(分是否为第1个元素两种情况，若为第1个元素，则又分是否有后续元素两种情况)；若p为子表，则递归处理该子表。算法如下： int DelNode(GListNode h,ElemType x) //h为广义表的表头结点指针 { GListNode *p=h->val.sublist,*pre,*q; //pre指向p的前驱结点 if(h==NULL) return 0; while(p!=NULL) { if(p->tag==0) //为原子的情况 { if(p->val.data==x) //其data域值为x时删除之 { q=p; //q指向被删结点 if(h->val.sublist==p) //被删的是第1个结点 if(p->link==NULL) //被删结点无后续结点 h->val.sublist=NULL; //置为空表 2019/4/28

62 h->val.sublist=p->link; else //被删的不是第1个结点
pre->link=p->link; p=p->link; free(q); } else //单元素结点的data域值不为x {pre=p; p=p->link; else //为子表的情况 { pre=p; DelNode(p,x); //递归删除子表中的x return 1; 2019/4/28

63 h->link=GListCreat(s); //递归构造后续子表 else //串结束
h=NULL; //串结束，子表为空 ch=*s; //取下一个扫描字符 s++; //串指针后移一位 if(h!=NULL) //串未结束判断 if(ch=’,’) //当前字符为 h->link=GListCreat(s); //递归构造后续子表 else //串结束 h->link=NULL; //处理表的最后一个元素 return h; //返回广义表指针 } 2019/4/28

64 本章小结 数组作为一种数据类型，它是一种多维的线性结构，需要采用顺序存储结构，通常只进行存取或修改某个元素的值。
对于特殊矩阵的压缩存储，实质就是将特殊矩阵的二维表中的数据按照一定的次序存放到一维数组中，元素aij的位置通过相应的地址计算公式（映射公式）来确定；对于稀疏矩阵，由于非零元素排列无规律，通常采用三元组法来实现压缩存储。三元组法具体采用哪种实现形式，取决于应用中矩阵的形态以及主要进行什么样的运算。 广义表是一种递归定义的线性结构，它兼有线性结构和层次结构的特点。若将广义表看成是由表头和表尾合成的结构，则它的操作的实现类似于树的操作，而若将广义表看成是n个子表的序列，则它的操作的实现是线性表操作的一种扩充。由于广义表自身定义的递归性，几乎使所有的广义表操作算法都是递归算法，因此，通过对本章广义表部分的学习，读者应更好的掌握递归程序设计技巧。 2019/4/28