数据结构经典课件.ppt

1、第5章 数组和广义表 西安科技大学精品课程第第5 5章章 数组和广义表数组和广义表1 1教学目的：教学目的：掌握数组和广义表的定义、特点及典型算法。掌握数组和广义表的定义、特点及典型算法。2 2教学要求：教学要求：掌握数组在以行为主的存储结构中的地址计算方法。掌握数组在以行为主的存储结构中的地址计算方法。掌握矩阵实现压缩存储时的下标变换。掌握矩阵实现压缩存储时的下标变换。理解稀疏矩阵的两种存储方式的特点和适用范围，领会以三元组表示稀理解稀疏矩阵的两种存储方式的特点和适用范围，领会以三元组表示稀疏矩阵时进行运算采用的处理方法。疏矩阵时进行运算采用的处理方法。掌握广义表的定义及其存储结构，学会将广

2、义表分解为表头，表尾的方掌握广义表的定义及其存储结构，学会将广义表分解为表头，表尾的方法。法。3 3教学重点：教学重点：掌握特殊矩阵的压缩存储。掌握特殊矩阵的压缩存储。掌握稀疏矩阵采用三元组存储时典型算法的实现。掌握稀疏矩阵采用三元组存储时典型算法的实现。广义表的定义、运算。广义表的定义、运算。4 4教学难点：教学难点：数组的十字链表存储结构。数组的十字链表存储结构。第5章 数组和广义表 西安科技大学精品课程图图5.1 Amn的二维数组的二维数组5.1 数组数组5.1.1 5.1.1 数组的逻辑结构数组的逻辑结构 是是线性表线性表的推广的推广 数组数组特点特点：元素本身可以是具有某种结构的数据

3、元素本身可以是具有某种结构的数据，但属于同一但属于同一数据类型。数据类型。比如：一维数组可以看作一个线性表，二维数组可以看作比如：一维数组可以看作一个线性表，二维数组可以看作“数数据元素是一维数组据元素是一维数组”的一维数组，依此类推。图的一维数组，依此类推。图5.1是一个是一个m行行n列列的二维数组。的二维数组。第5章 数组和广义表 西安科技大学精品课程图5.2 矩阵Amn看成n个列向量的线性表 第5章 数组和广义表 西安科技大学精品课程图5.3 矩阵Amn看成m个行向量的线性表 推广：推广：n维数组维数组每个数据元素受每个数据元素受n个关系的约束，任一单个个关系的约束，任一单个关系，仍是线

4、性关系。关系，仍是线性关系。第5章 数组和广义表 西安科技大学精品课程通过以上分析可总结出数组具有以下性质：通过以上分析可总结出数组具有以下性质：数组中数据元素数目固定。数组中数据元素数目固定。数组中数据元素具有数组中数据元素具有相同的数据类型相同的数据类型。数组中每一个数据元素由数组中每一个数据元素由唯一的一组下标来标识唯一的一组下标来标识。数组是数组是随机存取随机存取的存储结构。的存储结构。在数组上在数组上不能做插入、删除数据元素的操作不能做插入、删除数据元素的操作。通常在各种高级语言中数组一旦被定义，通常在各种高级语言中数组一旦被定义，每一维的大小及上下每一维的大小及上下界都不能改变界都

5、不能改变。两种操作：两种操作：取值操作：给定一组下标，读其对应的数据元素。取值操作：给定一组下标，读其对应的数据元素。赋值操作：给定一组下标，存储或修改其相对应的数据元素。赋值操作：给定一组下标，存储或修改其相对应的数据元素。第5章 数组和广义表 西安科技大学精品课程 二维数组形式化表示为：二维数组形式化表示为：数组的顺序存储结构有两种：数组的顺序存储结构有两种：2Array（D,R）D=aij|i=c1,c1+1,d1,j=c2,c2+1,d2,aijD0 R=Row,Col Row|c1 i d1,c2 j d2-1,aij,ai(j+1)D0 Col|c1 i d1-1,c2 j d2,

6、aij,a(i+1)j D0 第5章 数组和广义表 西安科技大学精品课程 5.1.2 5.1.2 数组的存储结构数组的存储结构 数组的顺序存储结构有两种：数组的顺序存储结构有两种：1.按行序存储。如：按行序存储。如：BASIC、COBOL和和PASCAL语言。语言。2.按列序存储。如：按列序存储。如：FORTRAN语言。语言。二维数组二维数组Amn以行为主的存储序列为：以行为主的存储序列为：a11,a12,，a1n,a21,a22,a2n,am1,am2,amn 而以列为主的存储序列为：而以列为主的存储序列为：a11,a21,，am1，a12,a22,am2,a1n,a2n,amn第5章 数组

7、和广义表 西安科技大学精品课程设有二维数组设有二维数组Amn，按元素的下标求其地址的计算：，按元素的下标求其地址的计算：以以“以行为主序以行为主序”的分配为例：设数组的基址为的分配为例：设数组的基址为LOC(a11)，每个，每个数组元素占据数组元素占据l个地址单元，那么个地址单元，那么aij的物理地址计算为：的物理地址计算为：LOC(aij)=LOC(a11)+(i-1)*n+j-1)*l第5章 数组和广义表 西安科技大学精品课程 在在C语言中，数组中每一维的下界定义为语言中，数组中每一维的下界定义为0，则：，则：LOC(aij)=LOC(a00)+(i*n+j)*l 推广到一般二维数组：推广

8、到一般二维数组：Ac1.d1c2.d2，aij地址计算函数为：地址计算函数为：LOC(aij)=LOC(a c1 c2)+(i-c1)*(d2-c2+1)+(j-c2)*l 同理对于三维数组同理对于三维数组Amnp，即，即mnp数组，数组，aijk其物理地址为：其物理地址为：LOC(aijk)=LOC(a111)+(i-1)*n*p+(j-1)*p+k-1)*l 推广到一般的三维数组：推广到一般的三维数组：Ac1.d1c2.d2c3.d3，则，则aijk物理地址物理地址为：为：LOC(i,j,k)=LOC(a c1 c2 c3)+(i-c1)*(d2-c2+1)*(d3-c3+1)+(j-c2

9、)*(d3-c3+1)+(k-c3)*l第5章 数组和广义表 西安科技大学精品课程 容易看出，数组元素的存储位置是其下标的线性函数，一旦数容易看出，数组元素的存储位置是其下标的线性函数，一旦数组下标的组下标的界偶界偶确定之后，数组中的元素可随机存取。我们称具有确定之后，数组中的元素可随机存取。我们称具有这一特点的存储结构为这一特点的存储结构为随机存储结构随机存储结构。lcjcdcjcccLoclcjcjcdcjcdcdcjcdcdcccLocjjjLocnnnikkkniiinnnnnnnnnnnnn)()1()(,)()(1()(1()1()(1()1(,111211122331122212

10、1 对于维数组对于维数组A(c1.d1,c2.d2，,cn.dn)，元素，元素aj1j2jn的存储地址的的存储地址的计算公式计算公式:第5章 数组和广义表 西安科技大学精品课程例例5.1 若矩阵若矩阵Amn 中存在某个元素中存在某个元素aij满足：满足：aij是第是第i行中最小值且行中最小值且是第是第j列中的最大值，则称该元素为矩阵列中的最大值，则称该元素为矩阵A的一个鞍点。试编写一个的一个鞍点。试编写一个算法，找出算法，找出A中的所有鞍点。中的所有鞍点。基本思想：在矩阵基本思想：在矩阵A中求出每一行的最小值元素，然后判断该中求出每一行的最小值元素，然后判断该元素是不是它所在列中的最大值，是则

11、打印输出，接着处理下一行元素是不是它所在列中的最大值，是则打印输出，接着处理下一行。矩阵。矩阵A用一个二维数组表示。用一个二维数组表示。第5章 数组和广义表 西安科技大学精品课程void saddle(int A,int m,int n)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)

12、printf(%d,%d,%dn,i,k,min);/*if*/*for i*/算法的时间性能为算法的时间性能为O(m*(n+m*n)。第5章 数组和广义表 西安科技大学精品课程5.2 特殊矩阵的压缩存储特殊矩阵的压缩存储特殊矩阵：特殊矩阵：1.非零元素非常少；非零元素非常少；2.矩阵元素的分布有一定规律矩阵元素的分布有一定规律所谓所谓压缩存储压缩存储是指：是指：为多个值相同的元素只分配一个存储空间，为多个值相同的元素只分配一个存储空间，值为零的元素不分配空间值为零的元素不分配空间。第5章 数组和广义表 西安科技大学精品课程5.2.1 5.2.1 对称矩阵对称矩阵 特点：在一个特点：在一个n阶

13、方阵中，有阶方阵中，有aij=aji，其中，其中1i,jn，如图，如图5.3所示是一个所示是一个5阶对称矩阵。阶对称矩阵。第5章 数组和广义表 西安科技大学精品课程 对于元素对于元素aij，特点是：，特点是：ij且且1in，下标下标k与与i、j的关系为：的关系为：k=i*(i-1)/2+j-1 (kn*(n+1)/2)若若ij，则，则aij是上三角中的元素，因为是上三角中的元素，因为aij=aji，这样，访问上三，这样，访问上三角中的元素角中的元素aij时则去访问和它对应的下三角中的时则去访问和它对应的下三角中的aji即可，因此将上即可，因此将上式中的行列下标交换就是上三角中的元素在式中的行列

14、下标交换就是上三角中的元素在SA中的对应关系：中的对应关系：k=j*(j-1)/2+i-1 (kj)在一维数组在一维数组A中的位置为：中的位置为：Loci,j=Loc1,1+前前i-1行非零元个数行非零元个数+第第i行中行中aij前非零元个数前非零元个数 即：即：Loci,j=Loc1,1+i(i-1)/2+j-1设存入向量：设存入向量：SAn*(n+1)/2+1中，中，SA k与与aij的对应关系为：的对应关系为：k=i*(i-1)/2+j-1 当当ijn*(n+1)/2 当当ij（2）上三角矩阵，也可以将其压缩存储到一个大小为）上三角矩阵，也可以将其压缩存储到一个大小为n(n+1)/2的一

15、的一维数组维数组C中。其中元素中。其中元素aij(ij第5章 数组和广义表 西安科技大学精品课程图图5.8 带状矩阵带状矩阵A 三对角带状矩阵有如下特点：三对角带状矩阵有如下特点：i=1,j=1,2;1in,j=i-1,i,i+1;i=n,j=n-1,n;时，时，aij非零，其它元素均为零。非零，其它元素均为零。当当5.2.3 带状矩阵带状矩阵 第5章 数组和广义表 西安科技大学精品课程 1.确定存储该矩阵所需的一维向量空间的大小确定存储该矩阵所需的一维向量空间的大小 假设每个非零元素所占空间的大小为假设每个非零元素所占空间的大小为1个单元。个单元。所需一维向量空间的大小为所需一维向量空间的大

16、小为2+2+3（n-2）=3n-2，如图，如图5.9所示。所示。图图5.9 带状矩阵的压缩形式带状矩阵的压缩形式 第5章 数组和广义表 西安科技大学精品课程 2.确定非零元素在一维数组空间中的位置确定非零元素在一维数组空间中的位置 Loci,j=Loc1,1+前前i-1行非零元个数行非零元个数+第第i行中行中aij前非零元个数；前非零元个数；前前i-1行元素个数行元素个数=3(i-1)-1（因为第（因为第1行只有行只有2个非零元素）；个非零元素）；第第i行中行中aij前非零元素个数前非零元素个数=j-i+1，其中，其中-1(ji)j-i=由此得到由此得到 Loci,j=Loc1,1+3(i-1

17、)-1+j-i+1 =Loc1,1+2(i-1)+j-1 第5章 数组和广义表 西安科技大学精品课程5.3 稀疏矩阵的压缩存储稀疏矩阵的压缩存储 设设mn矩阵中有矩阵中有t个非零元素且个非零元素且tmn，这样的矩阵称为稀，这样的矩阵称为稀疏矩阵。疏矩阵。第5章 数组和广义表 西安科技大学精品课程5.3.1 稀疏矩阵稀疏矩阵 非零元个数远远小于零元个数。非零元个数远远小于零元个数。图图5.10 稀疏矩阵稀疏矩阵 第5章 数组和广义表 西安科技大学精品课程第5章 数组和广义表 西安科技大学精品课程三元组表的类型说明如下：三元组表的类型说明如下：define SMAX 1024 typedef st

18、ruct int i,j;datatype v;SPNode;typedef struct int mu,nu,tu;SPNode dataSMAX;SPMatrix;第5章 数组和广义表 西安科技大学精品课程1)用三元组表实现稀疏矩阵的转置运算用三元组表实现稀疏矩阵的转置运算如图所示的如图所示的67矩阵矩阵M，它的转置矩阵就是，它的转置矩阵就是76的矩阵的矩阵N，并且并且N（row，col）=M（col，row），），其中，其中，1row7，1col6。第5章 数组和广义表 西安科技大学精品课程采用矩阵的正常存储方式时，采用矩阵的正常存储方式时，实现矩阵转置的经典算法如下：实现矩阵转置的经典

19、算法如下：void TransMatrix（datatype sourcenm,datatype destmn）int i,j;for(i=0;im;i+)for(j=0;jmu=A.nu;B-nu=A.mu;B-tu=A.tu;if(B-tu0)j=1;for(k=1;k=A.nu;k+)for(i=1;idataj.row=A.datai.col B-dataj.col=A.datai.row;B-dataj.e=A.datai.e;j+;【算法算法5.1 基于稀疏矩阵的三元组表示矩阵的转置算法基于稀疏矩阵的三元组表示矩阵的转置算法】第5章 数组和广义表 西安科技大学精品课程 时间复杂度为

20、时间复杂度为O（A.nA.len）,最坏情况当最坏情况当A.len=A.mA.n时，时间复杂度为时，时间复杂度为O（A.mA.n2）。采用正常方式实现矩阵转）。采用正常方式实现矩阵转置的算法时间复杂度为置的算法时间复杂度为O（A.mA.n）。）。方法二方法二：依次按三元组表依次按三元组表A的次序进行转置，转置后直接放到三元组的次序进行转置，转置后直接放到三元组表表B的正确位置上的正确位置上。这种转置算法称为快速转置算法。这种转置算法称为快速转置算法。为了能将待转置三元组表为了能将待转置三元组表A中元素一次定位到三元组表中元素一次定位到三元组表B的正的正确位置上，需要预先计算以下数据：确位置上，

21、需要预先计算以下数据：(1)待转置矩阵每一列中非零元素的个数。待转置矩阵每一列中非零元素的个数。(2)待转置矩阵每一列中第一个非零元素在三元组表待转置矩阵每一列中第一个非零元素在三元组表B中的正中的正确位置确位置。第5章 数组和广义表 西安科技大学精品课程 为此，为此，需要设两个数组需要设两个数组 numcol用来存放用来存放A中第中第col列非零元素个数列非零元素个数 positioncol用来存放用来存放A中第中第col列中第一个非零元素在三列中第一个非零元素在三元组表元组表B中的正确位置。中的正确位置。其中：其中：（1）numcol的计算方法：的计算方法：将三元组表将三元组表A扫描一遍，

22、对于其中列号为扫描一遍，对于其中列号为k的元素，给相应的元素，给相应的的numk加加1。（2）positioncol的计算方法：的计算方法：position1=1，positioncol=position col-1+numcol-1，其中，其中2colA.nu。第5章 数组和广义表 西安科技大学精品课程第5章 数组和广义表 西安科技大学精品课程 具体算法如下：具体算法如下：FastTransposeTSMatrix(TSMatrix *A)/*基于矩阵的三元组表示，基于矩阵的三元组表示，采用快速转置法，采用快速转置法，将矩阵将矩阵A转置为转置为B所指的矩阵所指的矩阵*/int col,t,p

23、，q;int numMAXSIZE,positionMAXSIZE;B-tu=A-tu;B-nu=A-mu;B-mu=A-nu;if(B-tu)for(col=1;colnu;col+)numcol=0;for(t=1;ttu;t+)numA-datat.col+;/*计算每一列的非零元素的个数计算每一列的非零元素的个数*/第5章 数组和广义表 西安科技大学精品课程 position1=1;for(col=2;colnu;col+)/*求求col列第一个非零元素在列第一个非零元素在B.data的位置的位置*/positioncol=positioncol-1+numcol-1;for(p=1;

24、pdataq.row=A.datap.col;B-dataq.col=A.datap.row;B-dataq.e=A.datap.e positioncol+;【算法5.2 快速稀疏矩阵转置算法】第5章 数组和广义表 西安科技大学精品课程 快速转置算法快速转置算法时间耗费时间耗费在四个并列的单循环上，这四个并列的在四个并列的单循环上，这四个并列的单循环分别执行了单循环分别执行了A.nu，A.tu，A.nu，A.tu次，因而总的时间复杂次，因而总的时间复杂度为度为O(A.nu)+O(A.tu)+O(A.nu)+O(A.tu)。当待转置矩阵当待转置矩阵M中非零中非零元素个数接近于元素个数接近于A.

25、muA.nu 时，其时间复杂度接近于经典算法的时，其时间复杂度接近于经典算法的时间复杂度时间复杂度O(A.muA.nu)。空间耗费空间耗费上除了三元组表所占用的空间外，还需要两个辅助向量上除了三元组表所占用的空间外，还需要两个辅助向量空间，即空间，即num1.A-nu，position1.A-nu。可见，。可见，算法在时间上算法在时间上的节省，是以更多的的节省，是以更多的存储空间为代价的。存储空间为代价的。第5章 数组和广义表 西安科技大学精品课程 2)用三元组表实现稀疏矩阵的乘法运算用三元组表实现稀疏矩阵的乘法运算 两个矩阵相乘也是矩阵的一种常用的运算。设矩阵两个矩阵相乘也是矩阵的一种常用的

26、运算。设矩阵M是是m1n1矩阵，矩阵，N是是m2n2矩阵；矩阵；若可以相乘，则必须满足矩若可以相乘，则必须满足矩阵阵M的列数的列数n1与矩阵与矩阵N的行数的行数m2相等相等，才能得到结果矩阵，才能得到结果矩阵Q=MN（一个（一个m1n2的矩阵）。的矩阵）。数学中矩阵数学中矩阵Q中的元素的计算方法如下：中的元素的计算方法如下：11nkjkNkiMjiQ其中：1im1,1jn2。第5章 数组和广义表 西安科技大学精品课程图5.17 Q=MN 000200105003M00420120N400160Q 图图5.17给出了一个矩阵相乘的例子。当矩阵给出了一个矩阵相乘的例子。当矩阵M、N是稀疏矩阵是稀疏

27、矩阵时，我们可以采用三元组表时，我们可以采用三元组表的表示形式来实现矩阵的相乘。的表示形式来实现矩阵的相乘。第5章 数组和广义表 西安科技大学精品课程图5.18 矩阵M、N、Q的三元组表 第5章 数组和广义表 西安科技大学精品课程 因为三元组表只对矩阵的非零元素做存储。所以可以采用固定三元组因为三元组表只对矩阵的非零元素做存储。所以可以采用固定三元组表表a中的元素（中的元素（i，k，Mik）（）（1im1，1kn1），在三元组表），在三元组表b中找所有中找所有行号为行号为k的对应元素（的对应元素（k，j，Nkj）（）（1km2，1jn2）进行）进行相乘、相乘、累加累加，从而得到从而得到Qij，

28、即以三元组表，即以三元组表a中的元素为基准，中的元素为基准，依次求出其与三元组依次求出其与三元组表表b的有效乘积。的有效乘积。算法中附设两个向量算法中附设两个向量num、first，其中，其中numrow表示三元组表表示三元组表b中中第第row行非零元素个数（行非零元素个数（1rowm2），），firstrow表示三元组表表示三元组表b中第中第row行第一个非零元素所在的位置。显行第一个非零元素所在的位置。显然，然，firstrow+1-1指向三元组表指向三元组表b中第中第row行最后一个非零元素的位置。行最后一个非零元素的位置。第5章 数组和广义表 西安科技大学精品课程5.3.2 稀疏矩阵的

29、十字链表存储稀疏矩阵的十字链表存储*与用二维数组存储稀疏矩阵比较，用三元组表表示的稀疏矩与用二维数组存储稀疏矩阵比较，用三元组表表示的稀疏矩阵不仅节约了空间，而且使得矩阵某些运算的运算时间比经典算阵不仅节约了空间，而且使得矩阵某些运算的运算时间比经典算法还少。法还少。但是在进行矩阵加法、减法和乘法等运算时，有时矩阵中的但是在进行矩阵加法、减法和乘法等运算时，有时矩阵中的非零元素的位置和个数会发生很大的变化。如非零元素的位置和个数会发生很大的变化。如A=A+B，将矩阵将矩阵B加到矩阵加到矩阵A上，此时若还用三元组表表示法，势必会为了保持上，此时若还用三元组表表示法，势必会为了保持三元组表三元组表

30、“以行序为主序以行序为主序”而大量移动元素。而大量移动元素。第5章 数组和广义表 西安科技大学精品课程 在十字链表中，矩阵的每一个非零元素用一个结点表示，在十字链表中，矩阵的每一个非零元素用一个结点表示，该结该结点除了（点除了（row，col，value）以外，还要有以下两个链域：）以外，还要有以下两个链域：right：用于链接同一行中的下一个非零元素；：用于链接同一行中的下一个非零元素；down：用于链接同一列中的下一个非零元素。：用于链接同一列中的下一个非零元素。第5章 数组和广义表 西安科技大学精品课程 再再附设一个存放所有行链表的头指针的一维数组附设一个存放所有行链表的头指针的一维数组

31、和和一个存放一个存放所有列链表的头指针的一维数组所有列链表的头指针的一维数组。图。图5.15(b)给出了稀疏矩阵图给出了稀疏矩阵图5.15(a)的十字链表。的十字链表。第5章 数组和广义表 西安科技大学精品课程十字链表的结构类型说明如下：十字链表的结构类型说明如下：typedef struct OLNode int row,col;/*非零元素的行和列下标非零元素的行和列下标*/datatype value;struct OLNode *right,*down;/*非零元所在行、列表的后继链域非零元所在行、列表的后继链域*/OLNode;*OLink;typedef struct OLink

32、*row-head,*col-head;/*行、行、列链表的头指针向量列链表的头指针向量*/int m,n,len;/*稀疏矩阵的行数、稀疏矩阵的行数、列数、列数、非零元素的个数非零元素的个数*/CrossList;第5章 数组和广义表 西安科技大学精品课程 CreateCrossList(CrossList*M)/*采用十字链表存储结构，采用十字链表存储结构，创建稀疏矩阵创建稀疏矩阵M*/if(M!=NULL)free(M);scanf(&m,&n,&t);/*输入输入M的行数的行数,列数和非零元素的个数列数和非零元素的个数*/M-m=m;M-n=n;M-len=t;If(!(M-row-h

33、ead=(OLink*)malloc(m+1)*sizeof(OLink)exit(OVERFLOW);If(!(M-col-head=(OLink*)malloc(n+1)*sizeof(OLink)exit(OVERFLOW);M-row-head=M-col-head=NULL;/*初始化行、初始化行、列头指针向量，列头指针向量，各行、各行、列链表为空的链表列链表为空的链表*/for(scanf(&i,&j,&e);i!=0;scanf(&i,&j,&e)if(!(p=(OLNode*)malloc(sizeof(OLNode)exit(OVERFLOW);p-row=i;p-col=j

34、;p-value=e;/*生成结点生成结点*/if(M-row-headi=NULL)M-row-headi=p;第5章 数组和广义表 西安科技大学精品课程 else /*寻找行表中的插入位置寻找行表中的插入位置*/for(q=M-row-headi;q-right&q-right-colright)p-right=q-right;q-right=p;/*完成插入完成插入*/if(M-col-headj=NULL)M-col-headj=p;else /*寻找列表中的插入位置寻找列表中的插入位置*/for(q=M-col-headj;q-down&q-down-rowdown)p-down=q

35、-down;q-down=p;/*完成插入完成插入*/【算法【算法5.4 建立稀疏矩阵的十字链表建立稀疏矩阵的十字链表】建十字链表的算法的时间复杂度为建十字链表的算法的时间复杂度为O（ts），），s=MAX（m，n)。第5章 数组和广义表 西安科技大学精品课程5.4 广广 义义 表表*广义表的定义广义表的定义 广义表广义表是是n个数据元素个数据元素a1，a2，ai，an的有序序列的有序序列。一般记为：一般记为：ls=（a1，a2，a3，an）广义表广泛地应用于人工智能等领域的表处理语言广义表广泛地应用于人工智能等领域的表处理语言LISP语言中。语言中。List(D,R)D=ai|ai Atom

36、set 或或 ai Lists R=|ai,ai+1 D 1=i=n-1其中其中（1）ai是单个元素或是一个广义表，称为是单个元素或是一个广义表，称为ls的原子或子表的原子或子表 （2）长度：）长度：n是广义表的长度。是广义表的长度。（3）表头：）表头：a1是广义表是广义表ls的表头的表头 （4）表尾：其余元素组成的表是表尾。）表尾：其余元素组成的表是表尾。（5）广义表示一个递归定义的表。）广义表示一个递归定义的表。第5章 数组和广义表 西安科技大学精品课程下面给出一些广义表的例子，以加深对广义表概念的理解。下面给出一些广义表的例子，以加深对广义表概念的理解。D=（）（）空表；其长度为零。空表

37、；其长度为零。A=(a，(b，c)表长度为表长度为2的广义表，其中第一个元素是单个数据的广义表，其中第一个元素是单个数据a，第二个元，第二个元素是一个子表素是一个子表(b，c)。B=(A，A，D)长度为长度为3的广义表，的广义表，其前两个元素为表其前两个元素为表A，第三个元素为空表第三个元素为空表D。C=(a，C)长度为长度为2递归定义的广义表，递归定义的广义表，C相当于无穷表相当于无穷表(a，(a,(a，()。下面以广义表下面以广义表A为例，为例，说明求表头、说明求表头、表尾的操作：表尾的操作：head（A）=a 表表A的表头是的表头是a。tail（A）=（b，c）表表A的表尾是（的表尾是（

38、b，c）。）。广义表的表尾一定是一个表。广义表的表尾一定是一个表。第5章 数组和广义表 西安科技大学精品课程 广义表的广义表的性质性质从上述广义表的定义和例子可以得到广义表的重要性质：从上述广义表的定义和例子可以得到广义表的重要性质：广义表是一种多层次的数据结构广义表是一种多层次的数据结构。广义表的元素可以是单元。广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表，素，也可以是子表，而子表的元素还可以是子表，。广义表可以是递归的表广义表可以是递归的表。例如表。例如表C 就是一个递归的表。就是一个递归的表。广义表可以为其它表所共享广义表可以为其它表所共享。如广义表。如广义表B就共享

39、表就共享表A。在表在表B中不必列出表中不必列出表A的内容，只要通过子表的名称就可以引用该表。的内容，只要通过子表的名称就可以引用该表。第5章 数组和广义表 西安科技大学精品课程 广义表基本运算广义表基本运算 基本操作，取头操作（基本操作，取头操作（Head）和取尾操作（）和取尾操作（Tail）。）。根据广义表的表头、表尾的定义可知，根据广义表的表头、表尾的定义可知，对于任意一个非空的广对于任意一个非空的广义表，其表头可能是单元素也可能是广义表，而表尾必为广义表。义表，其表头可能是单元素也可能是广义表，而表尾必为广义表。例如：例如：A（）（）B（e）C（a，（，（b，c，d）D（A，B，C）E（

40、a，E）F（）（）第5章 数组和广义表 西安科技大学精品课程那么：那么：head（B）e tail（B）（）（）head（C）a tail（C）（）（b，c，d）head（D）A tail（D）（）（B，C）head（E）a tail（E）（）（E）head（F）（）（）tail（F）（）（）例如：例如：L=(a，(b，(c，d)，e)，f)如何访问到如何访问到d？第5章 数组和广义表 西安科技大学精品课程 在广义表上可以定义与线性表类似的一些操作，如建立、插入、在广义表上可以定义与线性表类似的一些操作，如建立、插入、删除、拆开、连接、复制、遍历等。删除、拆开、连接、复制、遍历等。Create

41、Lists(ls)：根据广义表的书写形式创建一个广义表：根据广义表的书写形式创建一个广义表ls。IsEmpty(ls)：若广义表：若广义表ls空，则返回空，则返回True；否则返回；否则返回False。Length(ls)：求广义表：求广义表ls的长度。的长度。Depth(ls)：求广义表：求广义表ls的深度。的深度。Locate(ls，x)：在广义表：在广义表ls中查找数据元素中查找数据元素x。Merge(ls1，ls2)：以：以ls1为头、为头、ls2为尾建立广义表。为尾建立广义表。CopyGList(ls1，ls2)：复制广义表，即按：复制广义表，即按ls1建立广义表建立广义表ls2。H

42、ead(ls)：返回广义表：返回广义表ls的头部。的头部。Tail(ls)：返回广义表的尾部。：返回广义表的尾部。第5章 数组和广义表 西安科技大学精品课程5.4.2 广义表的存储广义表的存储 广义表的存储结构：广义表的存储结构：顺序存储结构无法实现，顺序存储结构无法实现，单链表无法存储。单链表无法存储。例如：例如：L=(a，(b，(c，d)，e)，f)如何访问到如何访问到d？head(tail(head(tail(head(tail(L)=d 任何一个非空的广义表都可以分解成表头和表尾两部分，表中任何一个非空的广义表都可以分解成表头和表尾两部分，表中的每个元素可用一个结点来表示。的每个元素可

43、用一个结点来表示。有两类结点：有两类结点：（1）单个元素结点：有）单个元素结点：有两个域：标志域和值域。两个域：标志域和值域。（2）表结点：）表结点：由三个域构成：标志域、指向表头的指针域和指向由三个域构成：标志域、指向表头的指针域和指向表尾的指针域。表尾的指针域。第5章 数组和广义表 西安科技大学精品课程typedef enum ATOM,LISTElemtag;/*ATOM=0单元素；单元素；LIST=1子表子表*/typedef struct GLNode Elemtag tag;/*标志域，用于区分元素结点和表结点标志域，用于区分元素结点和表结点*/union /*元素结点和表结点的联

44、合部分元素结点和表结点的联合部分*/datatype data;/*data是元素结点的值域是元素结点的值域*/struct struct GLNode *hp,*tp ptr;/*ptr是表结点的指针域，是表结点的指针域，ptr.hp和和ptr.tp分别指向表头和表尾分别指向表头和表尾*/;*GList;第5章 数组和广义表 西安科技大学精品课程例如：有以下广义表：例如：有以下广义表：A=(a,b,c)B=(A,A,D)C=(a,C)D=()第5章 数组和广义表 西安科技大学精品课程 采用头尾表示法容易分清广义表中单元素或子表所在的层次。采用头尾表示法容易分清广义表中单元素或子表所在的层次。例如，在广义表例如，在广义表A中，单元素中，单元素a、b和和c在同一层次上。在同一层次上。最高层的表结点的个数即为广义表的长度。最高层的表结点的个数即为广义表的长度。例如，广义表例如，广义表A的最高层有三个表结点，广义表长度为的最高层有三个表结点，广义表长度为3。