数据结构第五章wyz

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

2、义及其存储结构，学会将广义表分解为表头，表尾的方法。的方法。西安科技大学精品课程3教学重点：教学重点：掌握特殊矩阵的压缩存储。掌握特殊矩阵的压缩存储。掌握稀疏矩阵采用三元组存储时典型算法的实现。掌握稀疏矩阵采用三元组存储时典型算法的实现。广义表的定义、运算。广义表的定义、运算。4教学难点：教学难点：数组的十字链表存储结构。数组的十字链表存储结构。西安科技大学精品课程第第5章章 数组和广义表数组和广义表 5.1 数组数组 5.2 特殊矩阵的压缩存储特殊矩阵的压缩存储 5.3 稀疏矩阵的压缩存储稀疏矩阵的压缩存储 5.4 广义表广义表西安科技大学精品课程5.1 数组数组5.1.1 数组的逻辑结构数

3、组的逻辑结构特点：特点：元素本身可以是具有某种结构的数据，但属于同一数据类型。元素本身可以是具有某种结构的数据，但属于同一数据类型。 数组是非常有用的数据结构，几乎所有的高级程序设计语言数组是非常有用的数据结构，几乎所有的高级程序设计语言都提供了数组类型。都提供了数组类型。比如：比如：一维数组可以看作一个线性表，二维数组可以看作一维数组可以看作一个线性表，二维数组可以看作“数据元数据元素是一维数组素是一维数组”的一维数组，依此类推。的一维数组，依此类推。西安科技大学精品课程如图是一个如图是一个m行行n列的二维数组列的二维数组矩阵矩阵Amn看成看成n个列向量的线性表个列向量的线性表 ，推广：推广

4、： n维数组维数组每个数据元素受每个数据元素受n个个关系的约束，任一单个关系，仍关系的约束，任一单个关系，仍是线性关系。是线性关系。也可看成也可看成m个行向量的线性表个行向量的线性表 Amn=a11 a12 a1j a1na21 a22 a2j a2nai1 ai2 aij ainam1 am2 amj amnB=(i21ma11 a12 a1j a1na21 a22 a2j a2nai1 ai2 aij ainam1 am2 amj amnAmn=a11 a12 a1j a1na21 a22 a2j a2nai1 ai2 aij ainam1 am2 amj amnAmn=A=( 1 2 j

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

6、取值操作：给定一组下标，读其对应的数据元素。给定一组下标，读其对应的数据元素。 赋值操作：赋值操作：给定一组下标，存储或修改其相对应的数据元素。给定一组下标，存储或修改其相对应的数据元素。两种操作：两种操作：西安科技大学精品课程 二维数组形式化表示为：二维数组形式化表示为： A=(D,R) D=a0,0,a0,1,a0,m,am-1,n-1 R=Row,Col Row=, Col =,其中其中 Row是行关系，是行关系，Col是列关系是列关系西安科技大学精品课程5.1.2 数组的存储结构数组的存储结构 数组的顺序存储结构有两种：数组的顺序存储结构有两种：1. 按行序存储。按行序存储。如：如：B

7、ASIC、 COBOL和和PASCAL语言。语言。 2. 按列序存储。按列序存储。如：如：FORTRAN语言。语言。a23a22a21a13a12a11a23a22a21a13a12a11a23a13a22a12a21a11(a) 23数组的逻辑状态数组的逻辑状态(b) 以行为主序以行为主序(c) 以列为主序以列为主序图图5.2 23数组的物理状态数组的物理状态西安科技大学精品课程 设数组的基址为设数组的基址为LOC(a11)，每个数组元素占据，每个数组元素占据k个地址个地址单元，那么单元，那么aij的物理地址计算：的物理地址计算：设有二维数组设有二维数组Amn，按元素的下标求其地址的计算：，

8、按元素的下标求其地址的计算：2 以以“以列为主序以列为主序”的分配比例：的分配比例： LOC(aij)=LOC(a11)+(j-1)*m+(i-1)*k 1 以以“以行为主序以行为主序”的分配为例：的分配为例： LOC(aij)=LOC(a11)+(i-1)*n+j-1)*k3在在C语言中，数组中每一维的下界定义为语言中，数组中每一维的下界定义为0，则：，则： LOC(aij)=LOC(a00)+(i*n+j)*k西安科技大学精品课程 在矩阵在矩阵A中求出每一行的最小值元素，然后判断该元素是不是它所中求出每一行的最小值元素，然后判断该元素是不是它所在列中的最大值，是则打印输出，接着处理下一行。

9、矩阵在列中的最大值，是则打印输出，接着处理下一行。矩阵A用一个二维用一个二维数组表示。数组表示。例例5.1 若矩阵若矩阵Amn 中存在某个元素中存在某个元素aij满足：满足：aij是第是第i行中最小值且是第行中最小值且是第j列中的最大值，则称该元素为矩阵列中的最大值，则称该元素为矩阵A的一个鞍点。试编写一个算法，的一个鞍点。试编写一个算法，找出找出A中的所有鞍点。中的所有鞍点。基本思想：基本思想：Amn=a11 a12 a1j a1na21 a22 a2j a2nai1 ai2 aij ainam1 am2 amj amn西安科技大学精品课程void saddle(int A,int m, i

10、nt n)int i, j, min; for (i=0; im; i+) min=Ai0; for (j=1; jn; j+) if(Aijmin) min=Aij; 算法的时间性能为算法的时间性能为O(m*(n+m*n)算法实现算法实现按行处理按行处理找第找第i行最小值行最小值检测该行中的每一个检测该行中的每一个最小值是不是鞍点最小值是不是鞍点 for(j=0; jn; j+) if(Aij=min ) k=j; p=0; while(pm&Apj=m) printf(“%d,%d,%dn”, I, k, min); 西安科技大学精品课程5.2 特殊矩阵的压缩存储特殊矩阵的压缩存储矩阵：矩

11、阵：是一个二维数组，是科学和工程计算问题中常用到的数据模型。是一个二维数组，是科学和工程计算问题中常用到的数据模型。特殊矩阵：特殊矩阵：矩阵中的元素分布呈现某种规律。矩阵中的元素分布呈现某种规律。 为了节省存储空间，为了节省存储空间，特别是在高阶矩阵的情况下，可以利用特殊特别是在高阶矩阵的情况下，可以利用特殊矩阵矩阵的分布规律对他们进行的分布规律对他们进行压缩存储。压缩存储。 压缩存储：压缩存储：为多个值相同的元素只分配一个存储空间，值为零的为多个值相同的元素只分配一个存储空间，值为零的元素不分配空间。元素不分配空间。 压缩存储时，节约了存储单元，但在压缩后还需解决如何找到某压缩存储时，节约了

12、存储单元，但在压缩后还需解决如何找到某元素的方法，因此，还必须给出压缩前下标和压缩后下标之间的变换元素的方法，因此，还必须给出压缩前下标和压缩后下标之间的变换公式，使压缩存储变得有意义。公式，使压缩存储变得有意义。注意：注意：西安科技大学精品课程特点：特点：在一个在一个n阶方阵中，有阶方阵中，有aij=aji ，其中，其中1i、jn。如图如图5.3所示是一个所示是一个5阶对称矩阵阶对称矩阵 5.2.1 对称矩阵对称矩阵 对于对称矩阵，因其元素满足对于对称矩阵，因其元素满足aij=aji，只需存储其下三角（或上三，只需存储其下三角（或上三角）角）,即可实现压缩存储。即可实现压缩存储。3 6 4

13、7 86 2 8 4 24 8 1 6 9 7 4 6 0 58 2 9 5 7图图5.3 5阶对称方阵及它的压缩存储阵阶对称方阵及它的压缩存储阵759280647184263西安科技大学精品课程对于下三角元素对于下三角元素aij，前面共有，前面共有i行行,这这i行共有行共有 ? 个元素个元素,当前行当前行中中aij前亦有前亦有 ? 个元素。所以个元素。所以aij前共有前共有 ? 个元素，对于上三个元素，对于上三角元素角元素aij，由于，由于aij=aji,则访问和它对应的下三角中的则访问和它对应的下三角中的aji即可。即可。综合起来，对于对称矩阵中的任意元素综合起来，对于对称矩阵中的任意元素

14、aij得到转换公式：得到转换公式：对于对于n阶对称方阵，将阶对称方阵，将 ？ 个元素压缩到个元素压缩到 ？ 个空间中。个空间中。nnn(n+1)/2思考：思考：下三角的下三角的n(n+1)/2个元素存储到一维数组个元素存储到一维数组Bn(n+1)/2中。设矩阵元素中。设矩阵元素aij存储在存储在A数组的数组的Ak中，则关键问题是要找中，则关键问题是要找i、j与与k的关系。的关系。根据存储原则：根据存储原则：k=i*(i+1)/2+j (其中其中i=max(i,j),j=min(i,j); )(i+1)*i/2j(i+1)*i/2+j西安科技大学精品课程如图如图5.5为一个三角矩阵，其中为一个三

15、角矩阵，其中c为某个常数。其中：为某个常数。其中：(a)为下三角矩阵：主对角线以上均为同一个常数；为下三角矩阵：主对角线以上均为同一个常数；(b)为上三角矩阵，主对角线以下均为同一个常数；为上三角矩阵，主对角线以下均为同一个常数；5.2.2 三角矩阵三角矩阵下面讨论它们的压缩存储方法，可以借用对称矩阵的压缩存储方法下面讨论它们的压缩存储方法，可以借用对称矩阵的压缩存储方法 3 c c c c6 2 c c c4 8 1 c c 7 4 6 0 c8 2 9 5 73 4 8 1 0c 2 9 4 6c c 1 5 7 c c c 0 8c c c c 7(a) 下下三角矩阵三角矩阵(b) 上上

16、三角矩阵三角矩阵图图5.5 三角矩阵三角矩阵西安科技大学精品课程 1 下三角矩阵中元素下三角矩阵中元素aij(ij)在一维数组在一维数组A中，中，A数组的大小为数组的大小为 ？k=i*(i-1)/2+j-1 当当ijn*(n+1)/2 当当ij2 上三角矩阵，也可以将其压缩存储到一个大小为上三角矩阵，也可以将其压缩存储到一个大小为n(n+1)/2的一维数组的一维数组A中。其中元素中。其中元素aij(ijn*(n+1)/2+1其中元素其中元素aij(ij)在数组在数组A中的存储位置为：中的存储位置为：西安科技大学精品课程 主对角线上下方各有主对角线上下方各有b条次对角线。条次对角线。 b为矩阵的

17、半带宽，为矩阵的半带宽，2b+1为矩阵的带宽，常见的有三对角、为矩阵的带宽，常见的有三对角、五对角、七对角矩阵。五对角、七对角矩阵。5.2.3 对角矩阵对角矩阵 若矩阵中所有非零元素都集中在以主对角线为中心的带状区域中，若矩阵中所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为区域外的值全为0，则称此矩阵为对角矩阵。，则称此矩阵为对角矩阵。如图所示为三对角矩阵：如图所示为三对角矩阵：对角矩阵具有如下特点：对角矩阵具有如下特点：Amn=a11 a12 a21 a22 a23 a32 a33 a34 a43 a44 a45 西安科技大学精品课程 1.确定存储该矩阵所需的一维向量空间的

18、大小确定存储该矩阵所需的一维向量空间的大小 假设每个非零元素所占空间的大小为假设每个非零元素所占空间的大小为1个单元。个单元。 所需一维向量空间的大小为所需一维向量空间的大小为2+2+3(n-2)=3n-2以三对角矩阵为例讨论对角矩阵的压缩存储以三对角矩阵为例讨论对角矩阵的压缩存储 Loci,j = Loc0,0+前前i行非零元个数行非零元个数+第第i行中行中aij前非零元个前非零元个数数; 前前i行元素个数为：行元素个数为：3(i-2)+2 (因为第因为第1行只有行只有2个非零元素个非零元素); 第第i行中行中aij前非零元素个数前非零元素个数=j-i+1，其中，其中 2.确定非零元素在一维

19、数组空间中的位置确定非零元素在一维数组空间中的位置-1 (ji) j-i =由此得到由此得到:Loci, j=Loc0, 0+3(i-2)+2+j-i+1 西安科技大学精品课程5.3 稀疏矩阵的压缩存储稀疏矩阵的压缩存储稀疏矩阵稀疏矩阵：设设mn矩阵中有矩阵中有t个非零元素，且个非零元素，且tmu=A.nu; B-nu=A.mu; B-tu=A.tu; if (B-tu0) j=0; for(k=1; k=A.nu; k+) for(i=0; idataj.row=A.datai.col B-dataj.col=A.datai.row; B-dataj.v=A.datai.v; j+; 位置计

20、数器位置计数器j，初值为，初值为0，用，用于指向当前转置后元素应放于指向当前转置后元素应放入三元组表入三元组表B中的位置。中的位置。 处理完一个元处理完一个元素后，素后，j加加1时间复杂度为时间复杂度为O(A.nA.tu) , 最坏情况当最坏情况当A.tu=A.mA.n时，时，时间复杂度为时间复杂度为O(A.mA.n2)。与通常存储方式下矩阵转置算法相与通常存储方式下矩阵转置算法相比，虽然节约了一定量的存储空间，比，虽然节约了一定量的存储空间，但其算法的时间性能更差一些。但其算法的时间性能更差一些。 西安科技大学精品课程 依次按三元组表依次按三元组表A的次序进行转置，转置后的次序进行转置，转置

21、后直接直接放到三元组表放到三元组表B的正确位置上。这种转置算法称为的正确位置上。这种转置算法称为快速转置算法。快速转置算法。 为了能将待转置三元组表为了能将待转置三元组表A中元素一次定位到三元组表中元素一次定位到三元组表B的正确的正确位置上，需要预先计算以下数据：位置上，需要预先计算以下数据： (1) 待转置矩阵每一列中非零元素的个数。待转置矩阵每一列中非零元素的个数。 (2) 待转置矩阵每一列中第一个非零元素在三元组表待转置矩阵每一列中第一个非零元素在三元组表B中的正确位置。中的正确位置。 方法三：方法三： 为此，需要设两个数组为此，需要设两个数组numcol 用来存放用来存放A中第中第co

22、l列非零元素个数列非零元素个数cpotcol 用来存放用来存放A中第中第col列中第一个非零元素在三元组表列中第一个非零元素在三元组表B中中的正确位置。的正确位置。 西安科技大学精品课程举例：举例：col90781687531cpotcol01222 numcol54321 -746815167182562434514634-3133931212211ecolrow14368-7647244369135185241212315612-3311ecolrow(a) 三元组表三元组表A(b) 三元组表三元组表B其中：其中：(1) numcol的计算方法：的计算方法： 将三元组表将三元组表A扫描一遍

23、，对于其中列号为扫描一遍，对于其中列号为k的元素，给相应的的元素，给相应的numk加加1。(2) cpotcol的计算方法：的计算方法： cpot 1=1， cpotcol= cpot col-1+numcol-1，其中，其中2colA.nu。西安科技大学精品课程算法如下：算法如下： SPMatrix *FastTM (SPMatrix *A)SPMatrix *B; int col, t, p， q; int numMAXSIZE, cpotMAXSIZE; B-tu=A-tu; B-nu=A-mu; B-mu=A-nu; if (B-tu) for (col=1; colnu; col+)

24、 numcol=0; for(t=1; ttu; t+) numA-datat.col+; 将矩阵将矩阵A转置转置为为B所指的矩阵所指的矩阵计算每一列的计算每一列的非零元素的个非零元素的个数数cpot1=1; for(col=2; colnu; col+) cpotcol=cpotcol-1+numcol-1; for(p=1; pdataq.row=A.datap.col; B-dataq.col=A.datap.row; B-dataq.v=A.datap.v cpotcol+; return B； 求求col列第一个非列第一个非零元素在零元素在B.data的位置的位置西安科技大学精品课程

25、 快速转置算法时间耗费在四个并列的单循环上，这四个并列快速转置算法时间耗费在四个并列的单循环上，这四个并列的单循环分别执行了的单循环分别执行了A.nu，A.tu，A.nu，A.tu次；次； 因而总的时间复杂度为因而总的时间复杂度为O(A.nu)+O(A.tu)+O(A.nu)+O(A.tu)。 当待转置矩阵当待转置矩阵M中非零元素个数接近于中非零元素个数接近于A.muA.nu 时，其时，其时间复杂度接近于经典算法的时间复杂度时间复杂度接近于经典算法的时间复杂度O(A.muA.nu)。 空间耗费上除了三元组表所占用的空间外，还需要两个辅助空间耗费上除了三元组表所占用的空间外，还需要两个辅助向量空

26、间，即向量空间，即num1.A-nu，cpot1.A-nu。可见，算法在时间上的节省，是以更多的存储空间为代价的。可见，算法在时间上的节省，是以更多的存储空间为代价的。 西安科技大学精品课程 2) 2) 用三元组表实现稀疏矩阵的乘法运算用三元组表实现稀疏矩阵的乘法运算* *( (略略) ) 两个矩阵相乘也是矩阵的一种常用的运算。设矩阵两个矩阵相乘也是矩阵的一种常用的运算。设矩阵M是是m1n1矩矩阵，阵，N是是m2n2矩阵；若可以相乘，则必须满足矩阵矩阵；若可以相乘，则必须满足矩阵M的列数的列数n1与矩与矩阵阵N的行数的行数m2相等，才能得到结果矩阵相等，才能得到结果矩阵Q=MN（一个（一个m1

27、n2的矩阵）的矩阵） 因为三元组表只对矩阵的非零元素做存储。所以可以采用固定三元因为三元组表只对矩阵的非零元素做存储。所以可以采用固定三元组表组表a中的元素中的元素(i,k,D1)（1im1,1kn1），在三元组表），在三元组表b中找所有行中找所有行号为号为k的对应元素的对应元素(k,j,D2)（1km2,1jn2）进行相乘、）进行相乘、 累加，从而得累加，从而得到到Qij，即以三元组表，即以三元组表a中的元素为基准，中的元素为基准， 依次求出其与三元组表依次求出其与三元组表b的有效乘积。的有效乘积。 算法中附设两个向量算法中附设两个向量num 、first ，其中，其中numrow表示三元组

28、表表示三元组表b中中第第row行非零元素个数（行非零元素个数（1rowm2），）， firstrow表示三元组表表示三元组表b中第中第row行第一个非零元素所在的位置。显然，行第一个非零元素所在的位置。显然，firstrow+1-1指向三元组表指向三元组表b中第中第row行最后一个非零元素的位置。行最后一个非零元素的位置。 西安科技大学精品课程 与用二维数组存储稀疏矩阵比较，用三元组表表示的稀疏矩阵不仅与用二维数组存储稀疏矩阵比较，用三元组表表示的稀疏矩阵不仅节约了空间，而且使得矩阵某些运算的运算时间比经典算法还少。节约了空间，而且使得矩阵某些运算的运算时间比经典算法还少。 但是在进行矩阵加法

29、、减法和乘法等运算时，有时矩阵中的非零元但是在进行矩阵加法、减法和乘法等运算时，有时矩阵中的非零元素的位置和个数会发生很大的变化。如素的位置和个数会发生很大的变化。如A=A+B， 将矩阵将矩阵B加到矩阵加到矩阵A上，上，此时若还用三元组表表示法，势必会为了保持三元组表此时若还用三元组表表示法，势必会为了保持三元组表“以行序为主序以行序为主序”而大量移动元素。而大量移动元素。5.3.2 稀疏矩阵的十字链表存储稀疏矩阵的十字链表存储*西安科技大学精品课程 在十字链表中，矩阵的每一个非零元素用一个结点表示，在十字链表中，矩阵的每一个非零元素用一个结点表示， 该结点除该结点除了（了（row，col，v

30、alue）以外，还要有以下两个链域：）以外，还要有以下两个链域： right：用于链接同一行中的下一个非零元素；用于链接同一行中的下一个非零元素； down：用于链接同一列中的下一个非零元素。用于链接同一列中的下一个非零元素。 再附设一个存放所有行链表的头指针再附设一个存放所有行链表的头指针的一维数组和一个存放所有列链表的头指的一维数组和一个存放所有列链表的头指针的一维数组。图针的一维数组。图5.15(b)给出了稀疏矩阵给出了稀疏矩阵图图5.15(a)的十字链表。的十字链表。 down rightvaluecolrow图图5.14 十字链表的结点结构十字链表的结点结构A3 0 0 50 4 0

31、 03 0 0 0(a) 稀疏矩阵稀疏矩阵311422541313(b) 十字链表十字链表图图5.15 一个稀疏矩阵的十字链表一个稀疏矩阵的十字链表西安科技大学精品课程十字链表的结构类型说明如下：十字链表的结构类型说明如下： typedef struct OLNode int row,col; datatype value; struct OLNode * right, *down; OLNode; *OLink; 非零元素的行和列下标非零元素的行和列下标非零元所在行、列表非零元所在行、列表的后继链域的后继链域typedef struct OLink * row_head, * col_hea

32、d; int m,n, len; CrossList; 行、列链表的行、列链表的头指针向量头指针向量稀疏矩阵的行数、稀疏矩阵的行数、 列列数、数、 非零元素的个数非零元素的个数西安科技大学精品课程 CreateCrossList (CrossList * M) scanf(&m, &n, &t); M-m=m; M-n=n; M-len=t; if(!(M-row_head=(OLink * )malloc(m+1)*sizeof(OLink) exit(OVERFLOW); if(!(M-col-head=(OLink * )malloc(n+1)*sizeof(OLink) exit(OV

33、ERFLOW); 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; p-value=e; if(M-row-headi= =NULL) M-row-headi=p; 采用十字链表存储结构，采用十字链表存储结构， 创建稀疏矩阵创建稀疏矩阵M输入输入M的行数的行数, 列数和非列数和非零元素的个数零元素的个数初始化行、初始化行、 列头指列头指针向量，针向

34、量， 各行、各行、 列列链表为空的链表链表为空的链表生成结点生成结点建立稀疏矩阵的十字链表的算法：建立稀疏矩阵的十字链表的算法：西安科技大学精品课程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-down; q-down=p; 建十字链表的算法的时间复杂度为建十字链表的算法的时间复杂度为O(ts)，s=MA

35、X(m,n)。寻找行表中的插入位置寻找行表中的插入位置完成插入完成插入 寻找列表中的插入位置寻找列表中的插入位置完成插入完成插入西安科技大学精品课程5.4 广广 义义 表表是是n个数据元素个数据元素a1，a2，ai，an的有序序列。的有序序列。一般记为：一般记为： ls=（a1，a2，a3， ，an）广义表广泛地应用于人工智能等领域的表处理语言广义表广泛地应用于人工智能等领域的表处理语言LISP语言中。语言中。用二元组表示：用二元组表示： List(D,R) D=ai| aiAtomset 或或 ai Lists R=|ai,ai+1D ;1=i=n-1其中其中 （1）ai是单个元素或是一个广

36、义表，称为是单个元素或是一个广义表，称为ls的原子或子表的原子或子表 （2）长度：）长度：n是广义表的长度。是广义表的长度。 （3）表头：）表头：a1是广义表是广义表ls的表头的表头 （4）表尾：其余元素组成的表是表尾。）表尾：其余元素组成的表是表尾。 （5）广义表示一个递归定义的表。）广义表示一个递归定义的表。 广义表的定义广义表的定义西安科技大学精品课程D=( )空表；空表；其长度为零。其长度为零。A=(a, (b, c) 表长度为表长度为2的广义表，其中第一个元素是单个数据的广义表，其中第一个元素是单个数据a，第二个元素是一个，第二个元素是一个子表子表(b，c)。 B=(A,A,D)长度

37、为长度为3的广义表，的广义表， 其前两个元素为表其前两个元素为表A， 第三个元素为空表第三个元素为空表D。C=(a,C)长度为长度为2递归定义的广义表，递归定义的广义表，C相当于无穷表相当于无穷表(a，(a,(a，()。 下面给出一些广义表的例子，以加深对广义表概念的理解。下面给出一些广义表的例子，以加深对广义表概念的理解。下面以广义表下面以广义表A为例，为例， 说明求表头、说明求表头、 表尾的操作：表尾的操作：head(A)=a 表表A的表头是的表头是a。tail(A)=(b,c) 表表A的表尾是的表尾是(b,c)。广义表的表尾一定是一个表。广义表的表尾一定是一个表。西安科技大学精品课程 广

38、义表是一种多层次的数据结构。广义表的元素可以是单元广义表是一种多层次的数据结构。广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表，素，也可以是子表，而子表的元素还可以是子表，。 广义表可以是递归的表。例如表广义表可以是递归的表。例如表C 就是一个递归的表。就是一个递归的表。 广义表可以为其它表所共享。如广义表广义表可以为其它表所共享。如广义表B就共享表就共享表A。 在表在表B中不必列出表中不必列出表A的内容，只要通过子表的名称就可以引用该表。的内容，只要通过子表的名称就可以引用该表。 广义表的性质广义表的性质从上述广义表的定义和例子可以得到广义表的重要性质：从上述广义表的定义和

39、例子可以得到广义表的重要性质：西安科技大学精品课程 广义表基本运算广义表基本运算基本操作，取头操作（基本操作，取头操作（Head）和取尾操作（）和取尾操作（Tail）。）。根据广义表的表头、表尾的定义可知，对于任意一个非空根据广义表的表头、表尾的定义可知，对于任意一个非空的广义表，其表头可能是单元素也可能是广义表，而表尾的广义表，其表头可能是单元素也可能是广义表，而表尾必为广义表。必为广义表。A( )B(e)C(a,(b,c,d)D(A,B,C)E(a,E)F( )例如：例如：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 ？西安科技大学精品课程在广义表上可以定义与线性表类似的一些操作，如建立、插入、在广义表上可以定义与线性表类似的一些操作，如建立、插入、删除、拆开、连接、复制、遍历等。删除、拆开、连接、复制、遍历等。CreateLists(ls)：根据广义表的书写形式创建一个广义表根据广义表的书写形式创建一个广义表ls。IsEmpty(ls)：若广义表若广义