《数据结构组广义表精品文稿.ppt》由会员分享，可在线阅读，更多相关《数据结构组广义表精品文稿.ppt（80页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构组广义表第1页，本讲稿共80页 数组和广义表可以看成是线性表在以下含义上的扩展：表中的数据元素本身也是一个数据结构。第2页，本讲稿共80页5.1 数组数组 数组是大家都已经很熟悉的一种数据类型，几乎所有高级程序设计语言中都设定了数组类型。在此，我们仅简单地讨论数组的逻辑结构及在计算机内的存储方式。第3页，本讲稿共80页一一.多维数组的概念多维数组的概念1 1一维数组一维数组 一维数组可以看成是一个线性表或一个向量，它在计算机内存放在一块连续的存储单元中，适合于随机查找。这在第2章的线性表的顺序存储结构中已经讨论。第4页，本讲稿共80页2 2二维数组二维数组 二维数组可以看成是向量的推广
2、。例如，设A是一个有m行n列的二维数组，则A可以表示为：在此，可以将二维数组A看成是由m个行向量X0，X1，Xm-1T组 成，其 中，Xi=(ai0,ai1,.,ain-1)，0im-1；也可以将二维数组A看成是由n个列向量Y0,Y1,Yn-1组成，其中 Yj=(a0j,a1j,.,am-1j)，0jn-1。由此可知二维数组中的每一个元素最多可有两个直接前驱和两个直接后继（边界除外）。第5页，本讲稿共80页3 3多维数组多维数组 同理，三维数组最多可有三个直接前驱和三个直接后继，三维以上数组可以作类似分析。可以把三维以上的数组称为多维数组，多维数组可有多个直接前驱和多个直接后继。第6页，本讲稿
3、共80页二二.多维数组在计算机内的存放多维数组在计算机内的存放 高级语言对数组的存储都是采取顺序存储的方式，由于计算机内存结构是一维的（线性的），因此，用一维内存存放多维数组就必须按某种次序将数组元素排成一个线性序列，然后将这个线性序列顺序存放在存储器中，具体实现方法在下面介绍。第7页，本讲稿共80页5.1.1 数组的类型定义数组的类型定义5.1.3 矩阵的压缩存储矩阵的压缩存储 5.1.2 数组的顺序表示和实现数组的顺序表示和实现（数组）提要（数组）提要第8页，本讲稿共80页ADT Array 数据对象数据对象：Daj1,j2,.,jn|ji=0,.,bi-1,i=1,2,.,n(n0),a
4、j1,j2,.,jn ElemSet 数据关系数据关系：RR1,R2,.,Rn Ri|0 jk bk-1,1 k n 且k i,0 ji bi-2,i=2,.,n ADT Array 基本操作基本操作:5.1.1 数组的类型定义数组的类型定义第9页，本讲稿共80页数据对象数据对象:D=aij|0ib1-1,0 jb2-1,aijElemSet数据关系数据关系:R=ROW,COL ROW=|0ib1-2,0jb2-1 COL=|0ib1-1,0 jb2-2二维数组的定义二维数组的定义:第10页，本讲稿共80页基本操作基本操作：InitArray(&A,n,bound1,.,boundn)Dest
5、royArray(&A)Value(A,&e,index1,.,indexn)Assign(&A,e,index1,.,indexn)第11页，本讲稿共80页操作结果：操作结果：若维数 n 和各维长度合法，则构造相应的数组A，并 返回OK。InitArray(&A,n,bound1,.,boundn)第12页，本讲稿共80页 DestroyArray(&A)操作结果：操作结果：销毁数组A。第13页，本讲稿共80页初始条件：初始条件：A是n维数组，e为元素变量，随后是n 个下标值。操作结果：操作结果：若各下标不超界，则e赋值为 所指定的A 的元素值，并返 回OK。Value(A,&e,index
6、1,.,indexn)第14页，本讲稿共80页初始条件：初始条件：A是n维数组，e为元素变量，随后是n 个下标值。操作结果：操作结果：若下标不超界，则将e的值赋 给所指定的A的元素，并返回 OK。Assign(&A,e,index1,.,indexn)第15页，本讲稿共80页 类型特点类型特点:数组是多维的结构，而存储空间是一维的结构。有两种顺序映象的方式有两种顺序映象的方式:1)以行序为主序(行优先，低下标优先)；2)以列序为主序(列优先，高下标优先)。5.1.2 数组的顺序表示和实现数组的顺序表示和实现 由于一旦建立了数组，则结构中的数组元素个数和元素之间的关系就已确定，即它们的逻辑结构就
7、固定下来了，不再发生变化；数组一般不作插入或删除操作。因此，采用顺序存储结构表示数组是顺理成章的事了。第16页，本讲稿共80页例如：例如：称为基地址基地址或基址。二维数组A中任一元素ai,j 的存储位置 LOC(i,j)=LOC(0,0)+(nij)L L 以以“行序为主序行序为主序”的存储映象的存储映象 按行号从小到大的顺序，先将第一行中元素全部存放完，再存放第二行元素，第三行元素，依次类推二维数组Amn a0,0 a0,1 a0,n-1am-1,0am-1,1 am-1,n-1第17页，本讲稿共80页 同理，三维数组Almn按行优先存放的地址计算公式为：LOC(i,j,k)=LOC(0,0
8、,0)+(imn+jn+k)L0l-1m-1n-1ijk第18页，本讲稿共80页行序为主序行序为主序排列规律：最左边下标变化最慢，最右边下标变化最快，右边下标变化一遍，与之相邻的左边下标才变化一次。第19页，本讲稿共80页 称为 n 维数组的映象函数。数组元素数组元素的存储位置是其下标的线性函数。的存储位置是其下标的线性函数。推广到一般情况，可得到 n 维数组数据元素存储位置的映象关系:其中 cn=L，ci-1=bi ci,1 i n。LOC(j1,j2,.,jn)=LOC(0,0,.,0)+ci ji i=1n见教材P.93第20页，本讲稿共80页例如：例如：基地址基地址或基址。二维数组A中
9、任一元素ai,j 的存储位置 LOC(i,j)=LOC(0,0)+(mji)L L 以以“列序为主序列序为主序”的存储映象的存储映象 按列号从小到大的顺序，先将第一列中元素全部存放完，再存放第二列元素，第三列元素，依次类推二维数组Amn a0,0 a1,0 am-1,0a0,n-1a1,n-1 am-1,n-1第21页，本讲稿共80页列序为主序列序为主序排列规律：最右边下标变化最慢，最左边下标变化最快，左边下标变化一遍，与之相邻的右边下标才变化一次。第22页，本讲稿共80页5.1.3 矩阵的压缩存储矩阵的压缩存储1.特殊矩阵特殊矩阵2.稀疏矩阵稀疏矩阵第23页，本讲稿共80页1.特殊矩阵特殊矩
10、阵非零元在矩阵中的分布有一定的规律。例如:对称矩阵 三角矩阵 对角矩阵a11 a12 a1na21 a22 a2n an1 an2 annA=第24页，本讲稿共80页以对称矩阵为例，n阶对称矩阵A满足：aij=aji 1i,jn 可为每一对对称元分配一个存储空间。若以行序为主序存储其下三角中的元，以一维数组sn(n+1)/2作为其存储结构，则sk和矩阵元aij之间的对应关系为：k=i(i-1)/2+j-1 (i j)j(j-1)/2+i-1 (i j)第25页，本讲稿共80页2.稀疏矩阵稀疏矩阵假设 m 行 n 列的矩阵含 t 个非零元素，则称 为稀疏因子稀疏因子。通常认为通常认为 0.05
11、的矩阵为稀疏矩阵。的矩阵为稀疏矩阵。何谓稀疏矩阵？非零元在矩阵中随机出现。第26页，本讲稿共80页1)零值元素占了很大空间零值元素占了很大空间;2)计算中进行了很多和零值的运算，计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零。遇除法，还需判别除数是否为零。以常规方法，即以二维数组表示高阶的稀疏矩阵时会产生的问题问题:例如：0 12 9 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 015 0 0 -7 0 0 0M=第27页，本讲稿共80页1)尽可能少存或不存零值元素；2)尽可能减少没有实际意义的运
12、算；3)操作方便。即：尽可能快地找到与下标值(i，j)对应的元素，尽可能快地找到同一行或同一列的非零元素。解决问题的原则解决问题的原则:第28页，本讲稿共80页一、三元组顺序表一、三元组顺序表二、行逻辑链接的顺序表二、行逻辑链接的顺序表三、三、十字链表十字链表稀疏矩阵的压缩存储方法稀疏矩阵的压缩存储方法:第29页，本讲稿共80页#define MAXSIZE 12500 typedef struct int i,j;/该非零元的行下标和列下标 ElemType e;/该非零元的值 Triple;/三元组类型三元组类型typedef struct Triple dataMAXSIZE+1;/da
13、ta0未用 int mu,nu,tu;TSMatrix;/稀疏矩阵类型稀疏矩阵类型一、三元组顺序表一、三元组顺序表第30页，本讲稿共80页矩阵M可表示为：0 12 9 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 015 0 0 -7 0 0 0M=12 121 3 931 -33 6 1443 2452 1861 156 4 -7i j eM.data:M.mu=6M.nu=7M.tu=8(TSMatrix M)例如：第31页，本讲稿共80页三元组顺序表表示的稀疏矩阵的转置运算。转置是矩阵中最简单的一种运算。
14、对于一个mn的矩阵A，它的转置矩阵B是一个nm的矩阵，且Bij=Aji，1in,1jm。第32页，本讲稿共80页 在三元组表表示的稀疏矩阵中，怎样求得它的转置呢?从转置的性质知道，将A转置为B，就是将A的三元组表a.data变为B的三元组表b.data，这时可以将a.data中i和j的值互换，则得到的b.data是一个按列序为主序排列的三元组表，再将它的顺序适当调整，变成行序为主序排列，即得到转置矩阵B。下面将用两种方法处理：(1)按照A的列序进行转置 由于A的列即为B的行，在a.data中，按列扫描，同一列的元素必按行序递增，因此得到的b.data必按行优先存放。但为了找到A的每一列中所有的
15、非零元素，每次都必须从头到尾扫描A的三元组表（有多少列，则扫描多少遍）。第33页，本讲稿共80页1 2 141 5 -52 2 -73 1 363 4 282 1 145 1 -52 2 -71 3 364 3 28例如：第34页，本讲稿共80页void transposeSMatrix(TSMatrix M,TSMatrix&T)/采用三元组表存储表示，求稀疏矩阵M的转置矩阵T T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)q=1;for(col=1;col=M.nu;+col)/按列号扫描 for(p=1;p=M.tu;+p)/对三元组扫描 if (M.dat
16、ap.j=col)/进行转置 T.dataq.j=M.datap.i;T.dataq.i=M.datap.j;T.dataq.e=M.datap.e;+q;/transposeSMatrix算法的时间复杂度：O(nutu)第35页，本讲稿共80页 其时间复杂度为其时间复杂度为:O(munu)for(col=1;col=nu;+col)for(row=1;row=mu;+row)Tcolrow=Mrowcol;用常规的二维数组表示时的算法：相比较后可以发现，当非零元的个数tu与munu同数量级时，transposeSMatrix算法的时间复杂度就成为O(munu2)了，比不压缩存储时的时间复杂度
17、要大。因此，该算法仅适于tumunu的情况。第36页，本讲稿共80页（2）按照A的行序进行转置(快速转置)即按a.data中三元组的次序进行转置，并将转置后的三元组放入b中恰当的位置。首先，在转置前求出矩阵A的每一列col（即B中每一行）的第一个非零元转置后在b.data中的正确位置cpotcol(1cola.nu)，然后，在对a.data的三元组依次作转置时，只要将三元组按列号col放置到b.datacpotcol中，之后将cpotcol内容加1，以指示第col列的下一个非零元的正确位置。为了求得位置向量cpot，要先求出A的每一列中非零元个数numcol，然后利用下面公式：cpot1=1
18、cpotcol=potcol-1+numcol-1 (2cola.nu)第37页，本讲稿共80页cpot1=1;for(col=2;col=a.nu;+col)cpotcol=cpotcol-1+numcol-1;例如：2 1 153 5 1 -56 2 2 -74 1 3 362 4 3 2851234512345第38页，本讲稿共80页T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)for(col=1;col=M.nu;+col)numcol=0;for(t=1;t=M.tu;+t)+numM.datat.j;cpot1=1;for(col=2;col=M.nu
19、;+col)cpotcol=cpotcol-1+numcol-1;for(p=1;p=M.tu;+p)/if return OK;/FastTransposeSMatrix 转置矩阵元素转置矩阵元素 Status FastTransposeSMatrix(TSMatrix M,TSMatrix&T)col=M.datap.j;q=cpotcol;T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;+cpotcol第39页，本讲稿共80页时间复杂度为时间复杂度为:O(M.nu+M.tu)for(col=1;col=M.nu;+c
20、ol)for(t=1;t=M.tu;+t)for(col=2;col=M.nu;+col)for(p=1;p=M.tu;+p)分析算法FastTransposeSMatrix的时间复杂度：第40页，本讲稿共80页 三元组顺序表又称有序的双下标法有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便便于进行依行顺序处理的矩阵运算于进行依行顺序处理的矩阵运算。然而，若需存取某一行中的非零元，则需从头开始进行查找。二、行逻辑链接的顺序表二、行逻辑链接的顺序表第41页，本讲稿共80页 修改前述的稀疏矩阵的结构定义，增加一个数据成员rpos，其各分量的值为对应各行第一个非零元的位置(下标)（在稀
21、疏矩阵的初始化函数中确定）。#define MAXMN 500 typedef struct Triple dataMAXSIZE+1;int rposMAXMN+1;int mu,nu,tu;RLSMatrix;/行逻辑链接顺序表类型第42页，本讲稿共80页ElemType value(RLSMatrix M,int r,int c)p=M.rposr;while(p=M.tu&M.datap.i=r&M.datap.jc)p+;if(p=M.tu&M.datap.i=r&M.datap.j=c)return M.datap.e;else return 0;/value例如：给定一组下标，求
22、矩阵的元素值第43页，本讲稿共80页for(i=1;i=m1;+i)for(j=1;j=n2;+j)Qij=0;for(k=1;k=n1;+k)Qij+=Mik*Nkj;其时间复杂度为其时间复杂度为:O(m1n2n1)矩阵乘法的精典算法矩阵乘法的精典算法:第44页，本讲稿共80页 Q初始化；if Q是非零矩阵 /逐行求积 for(arow=1;arow=M.mu;+arow)/处理M的每一行 ctemp=0;/累加器清零 计算Q中第arow行的积并存入ctemp 中；将ctemp 中非零元压缩存储到Q.data；/for arow /if 两个稀疏矩阵相乘（两个稀疏矩阵相乘（Q M N）的过程
23、可大致描述如下：的过程可大致描述如下：第45页，本讲稿共80页 if(M.nu!=N.mu)return ERROR;Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;if(M.tu*N.tu!=0)/Q是非零矩阵 for(arow=1;arow=M.mu;+arow)/处理M的每一行 /for arow /if return OK;/MultSMatrixStatus MultSMatrix (RLSMatrix M,RLSMatrix N,RLSMatrix&Q)第46页，本讲稿共80页 ctemp=0;/当前行各元素累加器清零 Q.rposarow=Q.tu+1;for(p=M.rp
24、osarow;pM.rposarow+1;+p)/对当前行中每一个非零元 brow=M.datap.j;if(brow N.nu)t=N.rposbrow+1;else t=N.tu+1 for(q=N.rposbrow;q t;+q)ccol=N.dataq.j;/乘积元素在Q中列号 ctempccol+=M.datap.e*N.dataq.e;/for q /求得Q中第crow(=arow)行的非零元 for(ccol=1;ccol MAXSIZE)return ERROR;Q.dataQ.tu=arow,ccol,ctempccol;/if处理的每一行M第47页，本讲稿共80页累加器ct
25、emp初始化的时间复杂度为(M.muN.nu)，求Q的所有非零元的时间复杂度为(M.tuN.tu/N.mu)，进行压缩存储的时间复杂度为(M.muN.nu)，总的时间复杂度就是总的时间复杂度就是(M.mu N.nu+M.tu N.tu/N.mu)。若M是m行n列的稀疏矩阵，N是n行p列的稀疏矩阵，则M中非零元的个数 M.tu=Mmn，N中非零元的个数 N.tu=Nnp，相乘算法的时间复杂度就是(mp(1+nMN)，当M0.05 和N0.05及 n 1000时，相乘算法的时间复杂度就相当于(mp)。分析上述算法的时间复杂度分析上述算法的时间复杂度第48页，本讲稿共80页 当稀疏矩阵中非零元的位置
26、或个数经常变动时，三元组就不适合于作稀疏矩阵的存储结构，此时，采用链表作为存储结构更为恰当。三、三、十字链表十字链表第49页，本讲稿共80页 十字链表是稀疏矩阵的链式存储方法，在该方法中，每一个非零元用一个结点表示，结点形式为：ijedownright其中 i,j,e表示非零元所在的行、列和值的三元组；right：行指针域，用来指向本行中下一个非零元素；down：列指针域，用来指向本列中下一个非零元素。稀疏矩阵中同一行的非零元通过right指针链接成一个带表头结点的链表。同一列的非零元通过down指针链接成一个带表头结点的链表。因此，每个非零元既是第i行链表中的一个结点，又是第j列链表中的一个
27、结点，相当于处在一个十字交叉路口，故称链表为十字链表。第50页，本讲稿共80页十字链表的类型定义typedef struct OLNode int i,j;ElemType e;struct OLNode *down,*right;OLNode;*Olink;typedef struct Olink *rhead,*chead;/行、列链表头指针向量基址 int mu,nu,tu;CrossList;第51页，本讲稿共80页3 0 0 50-1 0 02 0 0 01 1314522-13 12 例：M.mu=3M.nu=4M.tu=4第52页，本讲稿共80页5.2 广义表广义表广义表的概念
28、广义表是线性表的推广，也称为列表。线性表中的元素仅限于原子，即从结构上是不可以再分的，而广义表中的元素既可以是原子，也可以是广义表。LISP语言把广义表作为基本的数据结构，就连程序也表示为一系列的广义表。第53页，本讲稿共80页1.广义表广义表一般记作：LS=(1,2,n)其中,LS为广义表的名字，n为广义表的长度，每一个i为广义表的元素。i可以是原子(或称单元素)，也可以是广义表(称为子表)。在习惯中，一般用大写字母表示广义表，小写字母表示原子。2.广义表的长度广义表的长度长度定义为最外层包含元素个数。第54页，本讲稿共80页若广义表LS非空，则称第一个元素1为LS的表头，其余元素组成的表(
29、2,n)为LS的表尾。4.表头和表尾广义表的深度深度定义为所含括弧的重数。注意：“原子”的深度为 0 “空表”的深度为 1 3.广义表的深度任一非空的广义表，均可分解为表头和表尾；一对确定的表头和表尾，可唯一确定一个广义表。第55页，本讲稿共80页5.广义表举例（1）A=(e)GetHead(A)=e,GetTail(A)=()（2）B=(a,(b,c),d)GetHead(B)=a,GetTail(B)=(b,c),d)（3）C=()无表头、也无表尾广义表A只有一个单元素，其长度为1，深度为1。B是长度为3的广义表，其深度为2。C是一个空表，其长度为0，深度为1。第56页，本讲稿共80页广义
30、表举例（5）E=(a,E)（4）D=(A,B,C)GetHead(D)=(e),GetTail(D)=(a,(b,c),d),()GetHead(E)=a,GetTail(E)=(E)（6）F=()GetHead(F)=(),GetTail(F)=()D是长度为3的广义表，每一项都是上面提到的子表,即:D=(e),(a,(b,c),d),()，其深度为3。E是长度为2的广义表，第一项为原子，第二项为它本身。即：E=(a,(a,(a,),其深度为无穷。F是长度为1的广义表，其元素为空表，其深度为2。第57页，本讲稿共80页（广义表）提要5.2.1 广义表的类型定义广义表的类型定义5.2.2 广义
31、表的表示方法广义表的表示方法第58页，本讲稿共80页ADT Glist 数据对象数据对象：Dei|i=1,2,.,n;n0;eiAtomSet 或 eiGList,AtomSet为某个数据对象 数据关系：数据关系：LR|ei-1,eiD,2in ADT Glist基本操作基本操作:5.2.1 广义表的类型定义广义表的类型定义第59页，本讲稿共80页 LS=(1,2,n)其中：i 或为原子 或为广义表广义表广义表 LS=(1,2,n)的结构特点的结构特点:2)广义表是递归递归定义的线性结构线性结构1)广义表中的数据元素有相对次序次序；第60页，本讲稿共80页例如：例如：D=(E,F)其中:E=(
32、a,(b,c)F=(d,(e)DEFa()d()bce3)广义表是一个多层次多层次的线性结构线性结构第61页，本讲稿共80页4)广义表可以共享共享；5)广义表可以是一个递归递归的表。例如：A=(e)B=(a,(b,c),d)C=(A,B)D=(d,A,f,B)例如：E=(a,E)递归表的深度是无穷值，长度是有限值。第62页，本讲稿共80页 结构的创建和销毁结构的创建和销毁 InitGList(&L);DestroyGList(&L);CreateGList(&L,S);CopyGList(&T,L);状态函数状态函数 GListLength(L);GListDepth(L);GListEmpt
33、y(L);GetHead(L);GetTail(L);插入和删除操作插入和删除操作 InsertFirst_GL(&L,e);DeleteFirst_GL(&L,&e);遍历遍历 Traverse_GL(L,Visit();基基本本操操作作第63页，本讲稿共80页 由于广义表中的数据元素可以是原子，也可以是列表，即其中的元素可以有不同的结构，难以用顺序存储结构表示，因此，通常采用链式存储结构。在用链式结构时，需要两种结构的结点：(1)表结点，用以表示列表；(2)原子结点，用以表示原子。5.2.2 广义表的表示方法广义表的表示方法第64页，本讲稿共80页有两种具体的表示方法：(1)头尾链表存储表
34、示(2)扩展线性链表存储表示第65页，本讲稿共80页typedef enum ATOM,LIST ElemTag;/枚举类型 /ATOM=0:原子,LIST=1:子表typedef struct GLNode ElemTag tag;/公共部分，标志域 union /联合部分 AtomType atom;/原子结点的数据域 struct struct GLNode*hp,*tp;ptr;/表结点的指针域 ;*GList(1)广义表的头尾链表存储表示：广义表的头尾链表存储表示：表结点表结点:tag=1 hp tpptrtag=0 atom原子结点：原子结点：第66页，本讲稿共80页空表空表非空表
35、非空表tag=1 指向表头的指针指向表尾的指针LSLS=NULL第67页，本讲稿共80页例如例如:第68页，本讲稿共80页L 1 0 a 1 1 0 x 1 1 1 0 x 1 0 y(a,(x,y),(x)a(x,y),(x)(x,y)(x)x(y)y(x)(x)xL=(a,(x,y),(x)第69页，本讲稿共80页再看几个例子（1）A=(e)（2）B=(a,(b,c),d)（3）C=()（4）D=(A,B,C)1e0A1 111 1d0c0b0a0BC=NULLD11 1第70页，本讲稿共80页（5）E=(a,E)（6）F=()1a0E 1 1F 第71页，本讲稿共80页该存储结构的特点
36、由图中，我们可以容易地得到广义表的长度，深度，原子和子表所在的层数，也容易求表头和表尾，给广义表的某些操作（特别是递归操作）带来方便。但这种结构也存在这缺点：表结点多，与广义表中括号对数不匹配，占用存储空间较多。第72页，本讲稿共80页(2)(2)广义表的扩展线性链表存储表示广义表的扩展线性链表存储表示typedef enum ATOM,LIST ElemTag;/枚举类型 /ATOM=0:原子,LIST=1:子表typedef struct GLNode ElemTag tag;/公共部分，标志域 union /联合部分 AtomType atom;/原子结点的数据域 struct GLNo
37、de *hp;/表结点的表头指针 ;struct GLNode *tp；/指向下一个元素结点*GList第73页，本讲稿共80页 1 ls空表空表 非空表非空表指向表头的指针 表结点表结点:原子结点：原子结点：tag=1 hp tptag=0 atom tpls 1 指向下一个元素结点的指针(同一层的结点以tp相连)第74页，本讲稿共80页例如例如:L=(a,(x,y),(x)L 1 0 a 1 1 0 x 0 y 1 0 x 第75页，本讲稿共80页再看几个例子（1）A=(e)（2）B=(a,(b,c),d)（3）C=()（4）D=(A,B,C)1A e0 d011Ba0b0 c0 1C D
38、11 1 1第76页，本讲稿共80页该存储结构的特点表结点个数少，且和广义表中的括号对数一致；但写递归算法不方便。要求：主要掌握前一种存储结构。第77页，本讲稿共80页1.1.了了解解数数组组的的两两种种存存储储表表示示方方法法，并并掌掌握握数数组组在在以行为主的存储结构中的地址计算方法。以行为主的存储结构中的地址计算方法。2.2.掌掌握握对对特特殊殊矩矩阵阵进进行行压压缩缩存存储储时时的的下下标标变变换换公式。公式。3.3.了了解解稀稀疏疏矩矩阵阵的的两两类类压压缩缩存存储储方方法法(三三元元组组顺顺序序表表和和十十字字链链表表)的的特特点点和和适适用用范范围围，领领会会以以三三元元组组顺顺序序表表表表示示稀稀疏疏矩矩阵阵时时进进行行矩矩阵阵运运算算采采用用的的处处理理方方法法。本章学习要点第78页，本讲稿共80页4.4.掌握广义表的结构特点及其存储表示方法，掌握广义表的结构特点及其存储表示方法，熟练掌握第一种结构的链表，学会对非空广义熟练掌握第一种结构的链表，学会对非空广义表进行分解的方法：即可将一个非空广义表分表进行分解的方法：即可将一个非空广义表分解为表头和表尾两部分。解为表头和表尾两部分。第79页，本讲稿共80页本章作业：5.15.65.235.105.125.13第80页，本讲稿共80页