数据结构05数组和广义表11.ppt

2019/9/8,1,本章主要介绍数组的概念及多维数组在计算机中的存放，特殊矩阵的压缩存储及相应运算，广义表的概念和存储结构及其相关运算的实现。通过本章学习，要求掌握如下内容： 1多维数组的定义及在计算机中的存储表示； 2对称矩阵、三角矩阵、对角矩阵等特殊矩阵在计算机中的压缩存储表示及地址计算公式； 3稀疏矩阵的三元组表示及转置算法实现； 4稀疏矩阵的十字链表表示及相加算法实现； 5广义表存储结构表示及基本运算。,本章学习导读,2019/9/8,2,数组和广义表可看成是一种特殊的线性表，其特殊在于，表中的数据元素本身也是一种线性表。 5.1 .1 数组的定义 数组是大家都已经很熟悉的一种数据类型，几乎所有高级语言程序设计中都设定了数组类型。 数组（Array）是由n(n1)个相同类型数据元素a0，al，ai，an-1构成的有限序列。n是数组的长度。其中数组中的数据元素ai是一个数据结构，即ai可以是线性表中的一个元素，本身也可以是一个线性表，而线性子表中的每一个数据元素还可以再分解 。根据数组元素ai的组织形式不同，数组可以分为一维数组、二维数组以及多维（n维）数组。,5.1 数 组,2019/9/8,3,有时也把一维数组称为向量，二维数组称为矩阵。在二维或多维数组中，每个数组元素都受到2个或n个关系的约束。当数组为n维时，其对应线性表中的每个元素又是一个线性表。在每个关系中，每个元素都有一个直接后继。因此，就其单个关系而言，这n个关系中的每一个仍然是一种线性关系。 数组中每个元素都是由一个值和一组下标来确定的。同线性表一样，数组中的所有数据元素都必须属于同一数据类型。元素下标的个数被称为数组的维数。显然，当维数为1时，数组就退化为定长的线性表。,2019/9/8,4,1一维数组 一维数组可以看成是一个线性表或一个向量，它在计算机内是存放在一块连续的存储单元中，适合于随机查找。 一维数组记为An或A=( a0，al，ai，an-1) 一维数组中，一旦a0的存储地址、一个数据元素所占存储单元数L确定，则ai的存储地址LOC(ai)就可求出： LOC(ai)=LOC(a0)+i*L (0in) 2二维数组 二维数组，又称矩阵(matrix)。二维数组中的每一个元素又是一个定长的线性表（一维数组），都要受到两个关系即行关系和列关系的约束，也就是每个元素都同属于两个线性表。例如，设A是一个有m行n列的二维数组，则A可以表示为：,2019/9/8,5,可以看成由m个行向量组成的向量，也可以看由n个列向量组成的向量。 数组中的每个元素由元素值aij及一组下标（i，j）来确定。aij既属于第i行的行向量，又属于第j列的列向量。 其中，ai=( ai,0 ai,1 ai,n-1) (0in) 可以认为Am*n=A，A是这样的一维数组： A=( a0，al，ai，am-1),2019/9/8,6,显然，二维数组同样满足数组的定义。一个二维数组可以看作是每个数据元素都是相同类型的一维数组。以此类推，任何多维数组都可以看作一个线性表，这时线性表中的每个数据元素也是一个线性表。多维数组是特殊的线性表，是线性表的推广。 数组的性质： (1) 数组中的数据元素数目固定。一旦定义了一个数组，其数据元素数目不再有增减变化。它属于静态分配存储空间的数据结构。 (2) 数组中的数据元素必须具有相同的数据类型。 (3) 数组中的每个数据元素都有一组唯一的下标值。 (4) 数组是一种随机存储结构。可随机存取数组中的任意数据元素。,2019/9/8,7,对于多维数组，有两种存储方式：Am,n 以行序为主序的顺序存储； 数组元素按行向量排列，即第i+1个行向量紧接在第i个行向量之后, 把所有数组元素顺序存放在一块连续的存储单元中。 任一数据元素的存储地址可由公式算出： Loc(a i,j)=loc(a 0,0)+(i*n+j)*L 以列序为主序的顺序存储 在以列序为主序的存储方式中，数组元素按列向量排列，即第j+1个列向量紧接在第j个列向量之后, 把所有数组元素顺序存放在一块连续的存储单元中。 任一数据元素的存储地址可由公式算出 Loc(a i,j)=loc(a 0,0)+(j*m+i)*L,2019/9/8,8,推广到一般 设二维数组行下界为c1,行上界为d1,列下界为c2，列上界为d2,即数组Ac1d1,c2d2. -则以行序为主序的求元素地址公式可以为： Loc(a i,j)=loc(a c1,c2)+(i-c1)*(d2-c2+1)+(j-c2)*L 则以列序为主序的求元素地址公式可以为： Loc(a i,j)=loc(a c1,c2)+(j-c1)*(d1-c1+1)+(i-c1)*L,2019/9/8,9,5.1.2 数组的基本操作 数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组的基本操作一般不会含有元素的插入或删除等操作,数组只有访问数组元素和修改元素值的操作。 (1) 取值操作：给定一组下标，读其对应的数据元素。 (2) 赋值操作：给定一组下标，存储或修改与其相对应的数据元素。 我们着重研究二维和三维数组，因为它们的应用是广泛的，尤其是二维数组。,2019/9/8,10,5.1.3 数组的存储结构,通常，数组在内存中被映象为向量，即用向量作为数组的一种存储结构，这是因为内存的地址空间是一维的，数组的行列固定后，通过一个映象函数，则可根据数组元素的下标得到它的存储地址。 对于一维数组按下标顺序分配即可。 对多维数组分配时，要把它的元素映象存储在一维存储器中，一般有两种存储方式：一是以行为主序（或先行后列）的顺序存放，如BASIC、PASCAL、COBOL、C等程序设计语言中用的是以行为主的顺序分配，即一行分配完了接着分配下一行。另一种是以列为主序（先列后行）的顺序存放，如FORTRAN语言中，用的是以列为主序的分配顺序，即一列一列地分配。,2019/9/8,11,以行为主序的分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变，从右向左，最后是左下标。 以列为主序的分配规律恰好相反：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变，从左向右，最后是右下标。,2019/9/8,12,例如一个23的二维数组，逻辑结构可以用左图表示。以行为主序的内存映象如右图（a）所示。 分配顺序为：a11 ，a12 ，a13 ，a21 ，a22 ，a23 ；以列为主序的分配顺序为：a11 ，a21 ，a12 ，a22 ，a13 ，a23 ；它的内存映象如右图（b）所示。,2019/9/8,13,设有mn二维数组Amn，下面我们看按元素的下标求其地址的计算： 以“行为主序”的分配为例：设数组的基址为LOC(a11)，每个数组元素占据l个地址单元，那么aij 的物理地址可用一线性寻址函数计算： LOC(aij) = LOC(a11) + ( (i-1)*n + j-1 ) * l 在C语言中，数组中每一维的下界定义为0，则： LOC(aij) = LOC(a00) + ( i*n + j ) * l 推广到一般的二维数组：Ac1d1 c2d2，则aij的物理地址计算函数为： LOC(aij)=LOC(a c1 c2)+( (i- c1) *( d2 - c2 + 1)+ (j- c2) )*l,2019/9/8,14,同理对于三维数组Amnp，即mnp数组，对于数组元素aijk其物理地址为： LOC(aijk)=LOC(a111)+( ( i-1) *n*p+ (j-1)*p +k-1)*l 推广到一般的三维数组：Ac1d1 c2d2 c3d3，则aijk的物理地址为：,LOC(i,j)=LOC(a c1 c2 c3)+( (i- c1) *( d2 - c2 + 1)* (d3- c3 + 1)+ (j- c2) *( d3- c3 + 1)+(k- c3)*l,2019/9/8,15,三维数组的逻辑结构和以行为主序的分配示意图如图所示。,2019/9/8,16,(2)由于C语言采用行序为主序的存储方式，有： LOC(a2,3)=LOC(a0,0)+(i*n+j)*k =1000+(2*4+3)*4 =1044,【例1】在C语言中，对于给定的二维数组float a34，计算： (1) 数组a中的数组元素数目； (2) 若数组a的起始地址为1000，且每个数组元素长度为32位(即4个字节)，数组元素a23的内存地址。,【解】(1)由于C语言中数组的行、列下标值的下界均为0，该数 组行上界为3-1=2，列上界为4-1=3，所以该数组的元素数目共有3*4=12个。,2019/9/8,17,【例2】有m名学生，每人考n门功课，试写出求任一学生总分数和任一课程总分数的数据结构和算法。 【解】把学生的考试成绩存放在m行n列的二维数组中，则第i(0i为10人 #define N 3 /假设为3 int scoreMN; /学生成绩二维数组 求第i名学生总分数的算法为： int student_sum(int scoreMN,int i) int j,sum=0; for(j=0;jN;j+) sum=sum+scoreij; return(sum); ,2019/9/8,18,求第j门课程总分数的算法为： int course_sum(int scoreMN,int j) int i,sum=0; for(i=0;iM;i+) sum=sum+scoreij; return(sum); ,2019/9/8,19,矩阵是数值计算程序设计中经常用到的数学模型，它是由 m 行和 n 列的数值构成（当m=n 时称为方阵）。在高级程序设计语言中，通常用二维数组表示矩阵。然而在数值分析过程中经常遇到一些比较特殊的矩阵，它们的阶数很高，矩阵中元素数量很大，而且有很多元素的值相同或是零值元素，如对称矩阵、三角矩阵、带状矩阵和稀疏矩阵等。为了节省存储空间并且加快处理速度，需要对这类矩阵进行压缩存储，压缩存储的原则是：不重复存储相同元素；不存储零值元素。,5.2 矩阵的压缩存储,2019/9/8,20,5.2.1 特殊矩阵的压缩存储方法 特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。主要形式有对称矩阵、三角矩阵、对角矩阵等。 1对称矩阵的压缩存储 对称矩阵是一个n阶方阵。若一个n阶矩阵A中的元素满足:ai,j=aj,i (0i，jn-1)，则称A为n阶对称矩阵。,1 5 1 3 7 a00 5 0 8 0 0 a10 a 11 1 8 9 2 6 a20 a21 a23 3 0 2 5 1 7 0 6 1 3 an-1 0 a n-1 1 a n-1 2 a n-1 n-1,对称矩阵,2019/9/8,21,在这个下三角矩阵中，第i行恰有i+1个元素，元素总数为：n*n, 现把这些元素存储在n(n+1)/2个元的空间中。 由于对称矩阵中的元素关于主对角线对称，因此可以为每一对对称的矩阵元素分配 1 个存储空间，n阶矩阵中的nn个元素就可以被压缩到 n(n+1)/2 个元素的存储空间中去。 Sak 与aji 的对应关系：,称一维数组Sa0n(n+1)/2 为n 阶对称矩阵A的压缩存储。其存储对应关系如上图 :,对称矩阵的压缩存储,2019/9/8,22,2三角矩阵的压缩存储 三角矩阵也是一个n阶方阵，有上三角和下三角矩阵。下(上)三角矩阵是主对角线以上（下）元素均为零的n阶矩阵。设以一维数组Sb0n(n+1)/2作为n阶三角矩阵B的存储结构，仍采用按行存储方案，则B中任一元素bi,j和Sbk之间存在着如下对应关系：,其中，Sbn(n+1)/2中存放常数c或0。,2019/9/8,23,3对角矩阵的压缩存储 对角方阵(或称带状矩阵)是指所有的非零元素(简称非零元)都集中在以主对角线为中心的带状区域中，即除了主对角线上和紧靠着主对角线上下方若干条对角线上的元素外，所有其它元素皆为零的矩阵。常见的有三对角矩阵、五对角矩阵、七对角矩阵等。下图是一个具有3(1mn)条非零元素带的n阶对角矩阵。,具有3条非零对角线的对角矩阵,2019/9/8,24,对于n阶有m (m必为奇数，因为副对角线关于主对角线对称) 条非零元素带的对角矩阵，只需存放对角区域内的所有非零元素即可。 在n阶对角矩阵A中，主对角线元素数最多（n个），然后向两边依次减少，每隔一条元素带元素数就减少1个，最外端的对角线有n-(m-1)/2个元素，所以非零元素总数u为： u=mn-2(m-1)/2+(m-1)/2-1)+l =mn-(m2-1)/4 设以一维数组Sau+l为对角矩阵A的存储结构，若按行存储非零元，则A中任一元素ai,j和Sak之间存在着如下对应关系：,结论：对特殊矩阵的压缩存储实质上就是将二维矩阵中的部分元素按照某种方案排列到一维数组中，不同的排列方案也就对应不同的存储方案。,2019/9/8,25,5.2.2 稀疏矩阵的压缩存储方法 如果一个矩阵中非零元较零元少，且分布没有一定规律，称该矩阵为稀疏矩阵。 根据存储时所附加信息的不同，稀疏矩阵的顺序存储方法包括：三元组表示法、带辅助行向量的二元组表示法和伪地址表示法，其中以三元组表示法最常用。 三元组表示法就是在存储非零元的同时，存储该元素所对应的行下标和列下标。稀疏矩阵中的每一个非零元素由一个三元组(i，j，aij)唯一确定。矩阵中所有非零元素存放在由三元组组成的数组中。 由线性表的两种不同存储结构可以得到稀疏矩阵压缩的不同的存储方法。,2019/9/8,26,假设有一个67阶稀疏矩阵A，其元素情况以及非零元对应的三元组表（以行序为主序）如图所示。,(a) 稀疏矩阵 (b) 三元组表示,三元组表中的第一行分别表示稀疏矩阵A的行数、列数和非零元的个数。显然，非零元素的三元组是按行号递增的顺序、相同行号的三元组按列号递增的顺序排列的。,图5-4,2019/9/8,27,1三元组顺序表 假设以行序为主序，且以一维数组作为三元组表的存储结构，可以得到稀疏矩阵的一种压缩存储方法，称为三元组顺序表。三元组顺序表的数据结构定义如下： #define NUM 100 /矩阵中非零元素最大个数 typedef struct /三元组结构 int r, c; /行(列)号 ElemType d; /元素值 tupletype; /三元组定义 typedef struct int rows; /矩阵行数值 int cols; /矩阵列数值 int nums; /非零元素个数 tupletype dataNUM; /三元组表 table; /三元组顺序表定义,2019/9/8,28,1稀疏矩阵的转置运算 转置是矩阵中最简单的一种运算。 对于一个mn的矩阵其转置矩阵是一个nm的矩阵，设为Bnm 且满足ai ,j=bj,i 即：aij=bji，其中：0im-1，0jn-1 即A的行是B的列，A的列是B的行。,稀疏矩阵的三元组表,2019/9/8,29,三元组表示的稀疏矩阵的转置常用的算法有以下两种： 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的列数,2019/9/8,30,mb.cols; /转置矩阵B的行数 mb.nums=t; /转置矩阵中的非零元素个数 for(i=0;in;i+) /按矩阵A的列序扫描 for(j=0;jt;j+) if(ma.dataj.c=i) /判断第j个三元组是不是第i列的 mb.datak.r=ma.dataj.c; mb.datak.c=ma.dataj.r; mb.datak+.d=ma.dataj.d; return(1); /成功完成矩阵转置,以上算法的时间复杂度分析：若n为转置矩阵的列数，t为矩阵中非零元素个数，则算法的时间花费主要在两个循环上，所以若时间复杂度为O(nt)。也就是说，时间的花费和矩阵A的列数和非零元素个数的乘积成正比。若用mn的二维数组表示矩阵，则相应的矩阵转置算法的循环为： for ( i=0；in；i+ ) for (j=0；jm；j+ ) bij=aji； 此时，时间复杂度为O(mn) 。,2019/9/8,31,2）快速转置算法： 三元组顺序表虽然节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，其效率低的原因是算法要从A的三元组表中寻找第一列、第二列、，要反复搜索A表，若能直接确定A中每一三元组在B中的位置，则对A的三元组表扫描一次即可。这是可以做到的，因为A中第一列的第一个非零元素一定存储在B.data1，如果还知道第一列的非零元素的个数，那么第二列的第一个非零元素在B.data中的位置便等于第一列的第一个非零元素在B.data中的位置加上第一列的非零元素的个数，如此类推，因为A中三元组的存放顺序是先行后列，对同一行来说，必定先遇到列号小的元素，这样只需扫描一遍A.data即可。,2019/9/8,32,为此，需要设置两个一维数组num0n和rpos0n： num0n：统计M中每列非零元素的个数。 rpos0n：M中的每列第一个非零元素在T中的位置。 算法通过rpos数组建立位置对应关系： rpos0=0 ； rposcol=rposcol-1+numcol-1 0colM.rows； 例如图5-4(a) 所示的稀疏矩阵的三元组表对应的num0n-1和rpos0n-1如图5-5所示。,（算法5.2见教科书P100）,图5-5 矩阵的num和rpos 数组值,2019/9/8,33,快速转置算法如下： void fasttranstri(tritupletable b,tritupletable a) int p,q,col,k; int num0a.n,copt0a.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) numcol=0; for(k=1;k=a.t;+k) +numa.datak.j; cpot0=1; for(col=2;col=a.t;+col) cpotcol=cpotcol-1+numcol-1;,for(p=1;p=a.t;+p) col=a.datap.j; q=cpotcol; b.dataq.i=a.datap.j; b.dataq.j=a.datap.i; b.dataq.v=a.datap.v; +cpotcol; ,2019/9/8,34,2行逻辑链接的顺序表(带行表的三元组) 有时为了方便某些矩阵运算，在按行优先存储的三元组中，加入一个行表来记录稀疏矩阵中每行的非零元素在三元组表中的起始位置。当将行表作为三元组表的一个新增属性加以描述时，就得到了稀疏矩阵的另一种顺序存储结构：带行表的三元组表。称这种“带行链接信息”的三元组表为行逻辑链接的顺序表。 其类型描述如下： #define maxrow 100 typedef struct triple datamaxsize; int rposmaxrow; int n,m,t; rtripletable,2019/9/8,35,下面讨论两个稀疏矩阵相乘的例子，容易看出这种表示方法的优越性： 若设 Q=M*N 其中，M是m1*n1矩阵，N是m2*n2矩阵。 当n1=m2时有： for(i=1;i=m1;+i) for(j=1;j=n2;+j) qij=0 for(k=1;k=n1;+k) qij+=mik*nkj; 此算法的复杂度为O(m1*n1*n2)。,2019/9/8,36,5.3.2 稀疏矩阵的十字链表存储,三元组表可以看作稀疏矩阵顺序存储，但是在做一些操作（如加法、乘法）时，非零元个数及位置在操作过程中变化较大时，这种表示就十分不便。 在这节中，我们介绍稀疏矩阵的一种链式存储结构十字链表，它具备链式存储的特点，因此，在某些情况下，采用十字链表表示三元组的线性表更为恰当。,2019/9/8,37,下图是一个稀疏矩阵的十字链表。,2019/9/8,38,用十字链表表示稀疏矩阵的基本思想是：对每个非零元素存储为一个结点，结点由5个域组成，其结构如图表示，其中：i域存储非零元素的行号，j域存储非零元素的列号，value域存储本元素的值，right向右域，用以链接同一行中下一个非零元素；down向下域，用以链接同一列中下一个非零元素。 next域,用以各行(列)表头结点与其下一结点之间的链接。 算法思想：同一行的非零元素通过right域链接成一个链表，同一列的非零元素通过down域链接成一个链表，每一个非零元既是某个行链表中的结点，同时又是某个列链表中的结点。整个矩阵构成了一个十字交叉的链表。故称为十字链表。,(a) 结点结构 (b) 头结点结构 图5-6 十字链表结点结构,2019/9/8,39,结点的结构定义如下: typedef struct olnode int i, j; Elemtype e; struct olnode * right, * down; olnode; * olink; typedef struct olink * rhead, * chead; int mu,nu,tu; CrossList;,2019/9/8,40,5.3 广义表的定义,5.3.1 广义表的定义 1广义表的定义 广义表也是线性表的推广，是一种多层次的线性结构，线性表中的元素仅限于原子项，即不可以再分； 而广义表中的元素既可以是原子项，也可以是子表（另一个线性表）。主要用于人工智能领域的表处理语言LISP语言。 广义表是n0个元素a1，a2，an的有限序列，其中每一个ai或者是原子，或者是一个子表。广义表通常记为LS=(a1,a2,an)，其中LS为广义表的名字，n为广义表的长度， 每一个ai为广义表的元素。但在习惯中，一般用大写字母表示广义表，小写字母表示原子。 若n=0时为空表。记作：L=( )。,2019/9/8,41,当广义表L非空(n0)时，第一个数据元素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/9/8,42,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/9/8,43,广义表中数据元素的最大层次为表的深度。数据元素的层次就是包括该元素的 括号对 的数目。例如广义表G=(a，b，(c，(d)中，数据元素a，b在第一层，数据元素c在第二层，数据元素d在第三层，广义表G的深度为3。,图 5-8 广义表的图形表示,从图5-8可以看出：广义表的图形表示像倒着画的一棵树，树根结点代表整个广义表，各层树枝结点代表相应的子表，树叶结点代表单元素或空表（如A表）。,2019/9/8,44,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/9/8,45,5广义表的分类 （1）线性表：元素全部是原子的广义表。 （2）纯表：与树对应的广义表，见图5-8的(c) 、(d)、 (e) 。 （3）再入表：与图对应的广义表(允许结点共享)， （4）递归表：允许有递归关系的广义表，例如E=(a,E)。 这四种表的关系满足：递归表再入表 纯表 线性表,再入表,2019/9/8,46,广义表基本运算 广义表有两个重要的基本操作，即取头操作（Head）和取尾操作（Tail）。 根据广义表的表头、表尾的定义可知，对于任意一个非空的列表，其表头可能是单元素也可能是列表，而表尾必为列表。例如： 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）（） 此外，在广义表上可以定义与线性表类似的一些操作，如建立、插入、删除、拆开、连接、复制、遍历等。,2019/9/8,47,CreateLists(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。 Head(ls)：返回广义表ls的头部。 Tail(ls)：返回广义表的尾部。 ,2019/9/8,48,5.3.2 广义表的存储结构 由于广义表的元素类型不一定相同，表中的数据元素可以是单元素（原子项），也可以是广义表，因此，难以用顺序结构存储表中元素，通常采用链接存储方法来存储广义表中元素，并称之为广义链表。需要两种结构的结点： (1) 表结点：用以表示广义表。由三个域组成：标志域tag、指向表头的指针域sublist和指向下一个结点的指针域link。如图5-9(a)所示。 (2) 原子结点：用以表示原子项。由三个域组成：标志域tag、值域data和指向下一个元素结点的指针域link。如图5-9(b)所示。,2019/9/8,49,每个数据元素都可用表结点或原子结点表示。它们的主要区别在于从不同的角度反映广义表的构成。 例如，广义表C的链表存储结构如图5-10所示。,图 5-10 广义表(a,(b,c,d)的链表存储结构图,二叉树,2019/9/8,50,广义表的链式结构描述如下： typedef char ElemType; typedef struct glnode int tag; union ElemType data; struct glnode *sublist; val; struct glnode *link; GListNode;,可将一个广义表看成一棵树，为了方便存储，通常将其转换成一棵二叉树 。广义表C转换成二叉树过程 如图5-11所示：,2019/9/8,51,广义表C,图5-11 广义表的转换过程,2019/9/8,52,5.3.3 广义表的基本操作 广义表的基本操作主要有： 求广义表的长度和深度、向广义表插入元素和从广义表中查找或删除元素、建立广义表的存储结构、输出广义表和复制广义表等。 由于广义表是一种递归的数据结构，所以对广义表的运算一般采用递归的算法。,1求广义表的深度 广义表深度的递归定义是：它等于所有子表中表的最大深度加1。若一个表为空或仅由单元素所组成，则深度为l。求广义表深度的递归函数GListDepth()如下：,2019/9/8,53,1 LS为空表 时 GListDepth(LS)= 0 LS为原子时 maxGListDepth(ai)|sh为h的子表+1 其它情况,int GListDepth(GList L) /采用头尾链表存储结构，求广义表L的深度。 if(!L) return 1; /空表深度为1 if(L-tag=ATOM) return 0; /原子深度为0 for(max=0,pp=L;pp;pp=pp-ptr.tp) dep=GListDepth(pp-ptr.hp); /求以pp-ptr.hp为头指针的子表深度 if(depmax)max=dep; return max+1; /非空表的深度是各元素的深度的最大值加1 /GListDepth,2019/9/8,54,2广义表的复制 复制一个广义表的过程如下：对于广义表的头结点*p，若为空，则返回空指针；若为表结点，则递归复制子表；否则，复制单元素结点，然后再递归复制后续表。返回复制后的广义表链表的指针。其算法如下：,GList