数组和广义表ppt课件

1、 数据结构课程本章内容5.1 数组的定义5.2 数组的顺序表示和实现5.3 矩阵的紧缩存储5.4 广义表的定义5.5 广义表的存储构造新联学院数据结构5-3 经过本章学习，要求掌握如下内容：1多维数组的定义及在计算机中的存储表示；2对称矩阵、三角矩阵、对角矩阵等特殊矩阵在计算机中的紧缩存储表示及地址计算公式；3稀疏矩阵的三元组表示及转置算法实现；4稀疏矩阵的十字链表表示及相加算法实现；5广义表存储构造表示及根本运算。重点难点新联学院数据结构5-4 数组是我们最熟习的数据类型，在早期的高级言语数组是我们最熟习的数据类型，在早期的高级言语中，数组是独一可供运用的数据类型。由于数组中各中，数组是独一

2、可供运用的数据类型。由于数组中各元素具有一致的类型，并且数组元素的下标普通具有元素具有一致的类型，并且数组元素的下标普通具有固定的上界和下界，因此，数组的处置比其它复杂的固定的上界和下界，因此，数组的处置比其它复杂的构造更为简单。多维数组是向量的推行。例如，二维构造更为简单。多维数组是向量的推行。例如，二维数组：数组： 5.1 数组的定义Amn=a11 a12 a1na21 a22 a2n am1 am2 amn新联学院数据结构5-5 5.1 数组的定义 数组可以看成是一种特殊的线性表，即线性表数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表。中数据元素本身也是一个线性表。

3、 数组是数组是n nn0n0个一样数据类型数据元素构个一样数据类型数据元素构成的有限序列。成的有限序列。新联学院数据结构( )mnmmnnnmaaaaaaaaaA.212222111211( )( )( )( )mnmmnnnmaaaaaaaaaA.212222111211( )( )( )( )二维数组同样满足数组的定义。二维数组可以看成一个特殊二维数组同样满足数组的定义。二维数组可以看成一个特殊的一维数组，其中的每个元素又是一个一维数组。的一维数组，其中的每个元素又是一个一维数组。5.1 数组的定义新联学院数据结构5-7 5.1 数组的定义新联学院数据结构5.1 数组的笼统数据类型ADT5

4、-8 新联学院数据结构一维数组存储构造表示图存储地址存储地址 内存空间状态内存空间状态 逻辑地址逻辑地址 Loc(a1) a11 Loc(a1)+(2-1)L a2 2 loc(a1)+(i-1)Lai i loc(a1)+(n-1)L an n 地址映像的计算公式：假设线性表中每个元素占地址映像的计算公式：假设线性表中每个元素占L L个单元，个单元，第一个元素的地址为第一个元素的地址为loc(a1)loc(a1)，那么第，那么第i i个元素的地址为：个元素的地址为： loc(ai) =loc(a1)+(i-1) loc(ai) =loc(a1)+(i-1)L L 新联学院数据结构5.2 数组

5、的顺序表示和实现p问问 题：计算机的存储构造是一维的，而数组普通是多维的，怎样题：计算机的存储构造是一维的，而数组普通是多维的，怎样存放？存放？p处理方法：事先商定按某种次序将数组元素排成一列序列，然后将这处理方法：事先商定按某种次序将数组元素排成一列序列，然后将这个线性序列存入存储器中。个线性序列存入存储器中。p留意：留意：p用一组延续的存储单元来表示数组；用一组延续的存储单元来表示数组；p假设规定好了次序，那么数组中恣意一个元素的存放地址便有规律可假设规定好了次序，那么数组中恣意一个元素的存放地址便有规律可寻，可构成地址计算公式；寻，可构成地址计算公式；p商定的次序不同，那么计算元素地址的

6、公式也有所不同；商定的次序不同，那么计算元素地址的公式也有所不同；pC和和PASCAL中普通采用行优先顺序；中普通采用行优先顺序；FORTRAN采用列优先采用列优先5-10 新联学院数据结构5-11 5.2 数组的顺序表示和实现p设一3维数组A423，存贮在一个顺序线性表S中，构造如下所示：A312A311A310A302A301A300A212A211A210A202A201A200A112A111A110A102A101A100A012A011A010A002A001A000A312A311A310A302A301A300A212A211A210A202A201A200A112A111A1

7、10A102A101A100A012A011A010A002A001A00001234567.2223A000A001A002A010A011A012A100A101.A311A312新联学院数据结构5.2 数组的顺序表示和实现p 以行为主:对二维数组进展“按行切分，即将数组中的数据元素“按行依次排放在存储器中；p 以列为主：对二维数组进展“按列切分，即将数组中的数据元素“按列依次排放在存储器中。5-12 新联学院数据结构 按行序为主序存放LOC(i,j)=LOC(0,0)+(i*n+j)*L新联学院数据结构 按列序为主序存放LOC(i,j)=LOC(0,0)+(j*m+i)*L新联学院数据结

8、构例题 无论规定行优先或列优先，只需知道以下三要素便可随时求出任无论规定行优先或列优先，只需知道以下三要素便可随时求出任一元素的地址：一元素的地址：开场结点的存放地址即基地址开场结点的存放地址即基地址维数和每维的上、下界；维数和每维的上、下界；每个数组元素所占用的单元数每个数组元素所占用的单元数5-15 新联学院数据结构例题【例【例5-1】对于给定的二维数组】对于给定的二维数组float a34，计算：，计算：(1) 数组数组a中的数组元素上界、下界、元素数目；中的数组元素上界、下界、元素数目；(2) 假设数组假设数组a的起始地址为的起始地址为1000，且每个数组元素长度为，且每个数组元素长度

9、为32位位(即即4个个字节字节)，数组元素，数组元素a23的内存地址。的内存地址。【解】【解】(1)由于由于C言语中数组的行、列下标值的下界均为言语中数组的行、列下标值的下界均为0，该数组行上，该数组行上界为界为3-1=2，列上界为，列上界为4-1=3，所以该数组的元素数目共有，所以该数组的元素数目共有3*4=12个。个。(2)由于由于C言语采用行序为主序的存储方式，有：言语采用行序为主序的存储方式，有：LOC(a2,3)=LOC(a0,0)+(i*n+j)*L =1000+(2*4+3)*4 =10445-16 新联学院数据结构例题p【例【例5-2】一个二维数组】一个二维数组A，行下标的范围

10、是，行下标的范围是1到到6，列下标的范围是，列下标的范围是0到到7，每个数组元素用相邻的，每个数组元素用相邻的6个字节存储，存储器按字节编址。个字节存储，存储器按字节编址。那么，这个数组的体积是那么，这个数组的体积是 个字节。个字节。 p 【解】【解】 Volume=m*n*L=(6-1+1)*(7- 0 +1)*6=48*6=288p【例【例5-3】 设数组设数组a160, 170的基地址为的基地址为2048，每个元素占，每个元素占2个存储单元，假设以列序为主序顺序存储，那么元素个存储单元，假设以列序为主序顺序存储，那么元素a32,58的存的存储地址为储地址为 。5-17 根据列优先公式根据

11、列优先公式 Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*L得：得：LOC(a32,58)=2048+(58-1)*60+(32-1)*28950想一想：假设数组是想一想：假设数组是a059, 069，结果能否仍为，结果能否仍为8950？新联学院数据结构5-18 5.3 矩阵的紧缩存储p在高级言语编制程序时，将一个矩阵描画为一个二维数组。在高级言语编制程序时，将一个矩阵描画为一个二维数组。p矩阵在这种存储表示之下，可以对其元素进展随机存取，各种矩阵矩阵在这种存储表示之下，可以对其元素进展随机存取，各种矩阵运算也非常简单，并且存储的密度为运算也非常简单，并且存储的密度为1 1。

12、但是在矩阵中非零元素呈。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储密度仍为密度仍为1 1，但实践上占用了许多单元去存储反复的非零元素或零，但实践上占用了许多单元去存储反复的非零元素或零元素，这对高阶矩阵会呵斥极大的浪费元素，这对高阶矩阵会呵斥极大的浪费. .新联学院数据结构5.3 矩阵的紧缩存储5-19 新联学院数据结构5-20 5.3 矩阵的紧缩存储5.3.1 特殊矩阵特殊矩阵值一样的元素或者值一样的元素或者0 0元素在矩阵中的分布有一定规律。元素在矩阵中的分布有一定规律。新联学院数据结构5-21

13、 5.3 矩阵的紧缩存储p对称矩阵对称矩阵p仅存储仅存储下三角下三角jiijjjijiik, 12/ ) 1(, 12/ ) 1(新联学院数据结构 下三角矩阵下三角矩阵5.3 矩阵的紧缩存储新联学院数据结构5.3 矩阵的紧缩存储 对角矩阵对角矩阵新联学院数据结构5-24 5.3 矩阵的紧缩存储5.3.2 稀疏矩阵稀疏矩阵定义：设矩阵定义：设矩阵A中有中有t个非零元素，假设个非零元素，假设s远远小于矩阵元素的总数即远远小于矩阵元素的总数即smn，那么称，那么称A为稀疏矩阵。为稀疏矩阵。设在的矩阵设在的矩阵A中，有中，有t个非零元素。令个非零元素。令 e=t/(m*n)，称，称e为矩阵为矩阵的稀疏

14、因子。通常以为的稀疏因子。通常以为e0.05时称之为稀疏矩阵。时称之为稀疏矩阵。以常规方法，即以二维数组表示的高阶的稀疏矩阵时产生的问题：以常规方法，即以二维数组表示的高阶的稀疏矩阵时产生的问题：1.零值元素占的空间很大；零值元素占的空间很大；2.计算中进展了很多和零值的运算；计算中进展了很多和零值的运算；新联学院数据结构5.3 矩阵的紧缩存储p处理问题的原那么处理问题的原那么p1. 尽量少存或不存尽量少存或不存0元；元；p2. 尽量减少没有意义的运算；尽量减少没有意义的运算；p3. 运算要方便。运算要方便。p 能尽能够快地找到与下标值能尽能够快地找到与下标值i，j对应的运对应的运算；算；p

15、能尽能够快地找到同一行或同一列的非能尽能够快地找到同一行或同一列的非0值元值元。p紧缩存储方法：三元组顺序表、行逻辑衔接和紧缩存储方法：三元组顺序表、行逻辑衔接和十字链表。十字链表。5-25 新联学院数据结构 存储特点存储特点 三元组顺序表 对于矩阵中每个非对于矩阵中每个非0 0元素，用它的行号、列号、元素元素，用它的行号、列号、元素值，即值，即i, j, aiji, j, aij表示。表示。 将表示稀疏矩阵的一切非将表示稀疏矩阵的一切非0 0元素的三元组按行优先顺元素的三元组按行优先顺序陈列，那么可得到一个其结点均是三元组的线性表，序陈列，那么可得到一个其结点均是三元组的线性表，称为三元组表

16、。称为三元组表。 以顺序存储构造来表示三元组。以顺序存储构造来表示三元组。 要独一确定一个稀疏矩阵，还必需存储该矩阵的行要独一确定一个稀疏矩阵，还必需存储该矩阵的行数和列数。数和列数。新联学院数据结构5-27 p三元组法存储0 12 9 0 0 00 0 0 0 0 0 -3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 015 0 0 -7 0 0( 1,2,12) ( 1,2,12) ，(1,3,9)(1,3,9)， (3,1,-3) (3,1,-3)， (3,5,14) (3,5,14)， (4,3,24) (4,3,24)， (5,2,18) (5,2,18) ，(

17、6,1,15)(6,1,15)， (6,4,-7) (6,4,-7)6 6行行6 6列，列，8 8个非零元个非零元 三元组顺序表新联学院数据结构p三元组法存储5-28 8552635531143742551221datacolrow0 2 0 0 5 00 0 0 7 0 00 0 0 11 5 20 0 0 0 0 00 0 0 0 8 0 三元组顺序表新联学院数据结构 数据类型定义# define MAXSIZE 12500 三元组结点：三元组结点：typedef struct int i, j; /行号，列号行号，列号 ElemType e; Triple;稀疏矩阵：稀疏矩阵：typed

18、ef struct Triple dataMAXSIZE+1 ; int mu, nu, tu; /*行、列、非零元素个数行、列、非零元素个数*/ TSMatrix ; 三元组顺序表新联学院数据结构5-30 p例子：三元组法表示的矩阵转置例子：三元组法表示的矩阵转置pM T0 2 0 0 5 00 0 0 7 0 00 0 0 11 5 20 0 0 0 0 00 0 0 0 8 0 0 0 0 0 02 0 0 0 00 0 0 0 00 7 11 0 00 5 0 80 0 2 0 0 知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表。常规算法：常规算法：for(col=1;col=n

19、u;col+)for(col=1;col=nu;col+) for(row=1;row=mu;row+) for(row=1;row=mu;row+) Tcolrow=Mrowcol; Tcolrow=Mrowcol;时间复杂度：时间复杂度：O(munu) 三元组顺序表新联学院数据结构5-31 处理思绪：处理思绪： 将矩阵行、列维数互换；将矩阵行、列维数互换； 将每个三元组中的将每个三元组中的i i和和j j互相互换；互相互换； 重排三元组次序；重排三元组次序； 三元组顺序表新联学院数据结构5-32 M.data12315-522-131634841-44570 3 0 0 -50 -1 0

20、0 06 0 0 8 0-4 0 0 0 7M0 0 6 -43 -1 0 00 0 0 00 0 8 0 -5 0 0 7TT.data2 1 35 1 -52 2 -11 3 64 3 81 4 -45 4 72 1 35 1 -52 2 -15 1 -5 三元组顺序表新联学院数据结构5-33 M.data12315-522-131634841-44570 3 0 0 -50 -1 0 0 06 0 0 8 0-4 0 0 0 7M0 0 6 -43 -1 0 00 0 0 00 0 8 0 -5 0 0 7TT.data2 1 35 1 -52 2 -11 3 64 3 81 4 -45

21、 4 7 三元组顺序表新联学院数据结构5-34 M.data12315-522-131634841-4457T.data2 1 35 1 -52 2 -11 3 64 3 81 4 -45 4 7Col12345NumcPot00000+1+1+1+1+1+1+1 三元组顺序表新联学院数据结构5-35 M.data12315-522-131634841-4457T.data2 1 35 1 -52 2 -11 3 64 3 81 4 -45 4 7Col12345Num22012cPot12345567 三元组顺序表新联学院数据结构5-36 三元组顺序表新联学院数据结构 优点：优点： 非零元在

22、表中按行序有序存储，便于进展依行非零元在表中按行序有序存储，便于进展依行序处置的矩阵运算。序处置的矩阵运算。 缺陷：缺陷： 假设需按行号存取某一行的非零元，那么需从假设需按行号存取某一行的非零元，那么需从头开场查找。头开场查找。 三元组顺序表新联学院数据结构 为了便于随机存储恣意一行的非零元，需求知为了便于随机存储恣意一行的非零元，需求知道每一行的第一个非零元在三元组表中的位置。道每一行的第一个非零元在三元组表中的位置。3.行逻辑衔接的顺序表# define MAXSIZE 12500 三元组结点：三元组结点：typedef struct int i, j; ElemType e; Tripl

23、e;稀疏矩阵：稀疏矩阵：typedef struct Triple dataMAXSIZE+1 ; int rposMAXRC+1; /*各行第一个非零元的位置表各行第一个非零元的位置表 int mu, nu, tu; /*行、列、非零元素个数行、列、非零元素个数*/ TSMatrix ;新联学院数据结构5-39 3.行逻辑衔接的顺序表p带行向量的三元组法的矩阵乘法带行向量的三元组法的矩阵乘法新联学院数据结构5-40 3.行逻辑衔接的顺序表0 2 0 0 30 -1 5 0 04 0 0 7 60 0 -3 0 0M(4,5)0 32 41 00 0 0 -2 N(5,2)=4 23 -40

24、0-3 0 Q(4,2)M.data12215322-123531434735643-3N.data12321222431152-2新联学院数据结构 问题描画：问题描画：知两个稀疏矩阵知两个稀疏矩阵M和和N的三元组表，求两个矩阵相的三元组表，求两个矩阵相乘的结果矩阵乘的结果矩阵Q。常规算法：常规算法：for(i=1;i=m1;i+)for(i=1;i=m1;i+) for(j=1;j=n2;j+) for(j=1;j=n2;j+) Qij=0; Qij=0; for(k=1;k=n1;k+) for(k=1;k=n1;k+) Qij += Qij += MikMik* * Nkj; Nkj;1

25、 1、只对、只对M M和和N N的非零元进展计算；的非零元进展计算；2 2、M M中列号与中列号与N N中行号相等的非零元相乘即可；中行号相等的非零元相乘即可；3 3、Q Q与与M M的行号对齐的，且的行号对齐的，且QijQij是累加的结果。是累加的结果。3.行逻辑衔接的顺序表新联学院数据结构3.行逻辑衔接的顺序表Q初始化；初始化；if Q是非零矩阵是非零矩阵 for(arrow=1;arrow=M.mu;arrow+) ctemp=0; 计算计算Q中第中第arrow行的积并存入行的积并存入ctemp中；中； 将将ctemp中非零元紧缩存储到中非零元紧缩存储到Q.data； 5-42 新联学院

26、数据结构处置M的每一行新联学院数据结构分析上述算法的时间复杂度分析上述算法的时间复杂度例子例子: :求矩阵乘法求矩阵乘法1、累加器、累加器ctemp初始化的时间复杂度为初始化的时间复杂度为O(M.muN.nu)2、求、求Q的一切非零元的时间复杂度为的一切非零元的时间复杂度为O(M.tuN.tu/N.mu)3、进展紧缩存储的时间复杂度为、进展紧缩存储的时间复杂度为O(M.muN.nu)总的时间复杂度总的时间复杂度O(M.muO(M.muN.nu+M.tuN.nu+M.tuN.tu/N.mu)N.tu/N.mu)假设假设M M是是m m行行n n列的稀疏矩阵，列的稀疏矩阵，N N是是n n行行p

27、p列的稀疏矩阵，那么：列的稀疏矩阵，那么： M M中非零元的个数：中非零元的个数：M.tu=M M.tu=M m mn n N N中非零元的个数：中非零元的个数： M.tu=N M.tu=N n np p 相乘算法的时间复杂度就是相乘算法的时间复杂度就是O(mO(mn n(1+nMN)(1+nMN)，当：，当： M 0.05 M 0.05和和N 0.05N 1000n1000时，时，算法的时间复杂度相当于算法的时间复杂度相当于O(mO(mp)p)。新联学院数据结构 引入缘由引入缘由 当矩阵的非零元的个数发生变化时，不宜采用三元当矩阵的非零元的个数发生变化时，不宜采用三元组表。如组表。如A=A+

28、B，非零元的插入或删除将会引起，非零元的插入或删除将会引起A.data中的数据挪动，这是顺序构造三元组的弱势。中的数据挪动，这是顺序构造三元组的弱势。 数据类型定义数据类型定义结点：结点：typedef struct OLNode int i, j; ElemType e; struct OLNode *right， *down；/*该非零元所在行的后继链域该非零元所在行的后继链域*/ OLNode; *OLink；稀疏矩阵：稀疏矩阵：typedef struct OLink *rhead，*chead； int mu，nu，tu； Crosslist;ijkdownright新联学院数据结构

29、5-46 4. 十字链表p十字链表结点定义：每一个非零元用一个结点表示，结点包括五个十字链表结点定义：每一个非零元用一个结点表示，结点包括五个域：除了表示非零元所在的行、列和值的三元组域：除了表示非零元所在的行、列和值的三元组i, j, vi, j, v外，外，还需添加两个链域：行指针域还需添加两个链域：行指针域rightright，用来指向本行中下一个，用来指向本行中下一个非零元素；列指针域非零元素；列指针域downdown，用来指向本列中下一个非零元素。，用来指向本列中下一个非零元素。ijrightdownv新联学院数据结构5-47 4. 十字链表p十字链表法：为稀疏矩阵中的链接存储中的一

30、种较好的存储方法十字链表法：为稀疏矩阵中的链接存储中的一种较好的存储方法稀疏矩阵及其十字交叉链表稀疏矩阵及其十字交叉链表0 12 0 0 00 0 0 0 -40 5 0 0 00 0 3 0 0A=(a) 稀疏矩阵稀疏矩阵A.cheadA.rchead 1 2 12 3 2 5 2 5 -4 4 3 3 新联学院数据结构5-48 4. 十字链表p十字链表类型定义十字链表类型定义p稀疏矩阵中同一行的非零元经过向右的稀疏矩阵中同一行的非零元经过向右的rightright指针链指针链接成一个带表头结点的线性链表。同一列的非零元也经过接成一个带表头结点的线性链表。同一列的非零元也经过downdown

31、指针指针链接成一个带表头结点的线性链表。链接成一个带表头结点的线性链表。p 因此，每个非零元既是第因此，每个非零元既是第i i行循环链表中的一个结点，又是行循环链表中的一个结点，又是第第j j列循环链表中的一个结点，相当于处在一个十字交叉路口，故列循环链表中的一个结点，相当于处在一个十字交叉路口，故称链表为十字链表。可用两个分别存储行链表的头指针和列链表的称链表为十字链表。可用两个分别存储行链表的头指针和列链表的头指针的一维数组表示之。头指针的一维数组表示之。新联学院数据结构5-49 5.4 广义表新联学院数据结构5-50 5.4 广义表p恣意一个非空广义表，均可分解为表头和表尾。恣意一个非空

32、广义表，均可分解为表头和表尾。p对于一个非空广义表，其表头能够是原子，也能够是子表；而表尾对于一个非空广义表，其表头能够是原子，也能够是子表；而表尾一定是子表。一定是子表。p广义表举例广义表举例pA=A= / / 空表，长度空表，长度n = 0n = 0pB=B=e e / n=1, / n=1, 只需一个原子只需一个原子e epC=C=a, (b, c, d) ) / n=2, a, (b, c, d) ) / n=2, 有两个元素，分别为原子有两个元素，分别为原子a a和子表和子表(b,c,d)(b,c,d)pD=D=A A，B B，C C / n=3, / n=3,有有3 3个元素个元素

33、pE= (a , EE= (a , E / n=2, / n=2,无限循环列表递归无限循环列表递归新联学院数据结构5-51 5.4 广义表p性质性质p广义表是一个多层次构造广义表是一个多层次构造;p广义表的深度广义表的深度 d 定义为所含括弧的重数展开后所含括号的层数定义为所含括弧的重数展开后所含括号的层数;p “原子的深度为原子的深度为0 ;p “空表的深度为空表的深度为1p 广义表可以共享广义表可以共享;也可以是一个递归的表也可以是一个递归的表;广广 义义 表表表长表长n表深表深hA=()00B=(e)11C=(a,(b,c,d)22D=(A,B,C)33E=(a,E)2F=()12abe

34、cdABCD新联学院数据结构 广义表有两个重要的根本操作，即取头操作广义表有两个重要的根本操作，即取头操作Head和取尾操作和取尾操作Tail。 根据广义表的表头、表尾的定义可知，对于恣意一个非空的列表，根据广义表的表头、表尾的定义可知，对于恣意一个非空的列表，其表头能够是单元素也能够是列表，而表尾必为列表。例如：其表头能够是单元素也能够是列表，而表尾必为列表。例如：B=e HeadB e TailB C=a, (b, c, d) ) HeadC a TailCb，c，d D=A，B，C HeadD A TailDB，C E= (a , EHeadE a TailEE F=() HeadF T

35、ailF LS= ( (a, b), (a, b), (u, (x, y, z), ( ) ) )，求，求LS的深度的深度5.4 广义表新联学院数据结构5-53 5.5 广义表的存储构造1LS表头表头表尾表尾LS = NULL 新联学院数据结构5-54 5.5 广义表的存储构造新联学院数据结构5-55 5.5 广义表的存储构造typedef enumatom,listelemtag;typedef struct GLnode Elemtag tag; union AtomType atom; struct GLnode *hp; /表结点的表头指针 ; struct GLnode *tp; /

36、 指向下一个元素结点 *GList;新联学院数据结构5-56 5.5 广义表的存储构造p广义表的运算广义表的运算p创建空的广义表创建空的广义表: initGList(&L);p销毁广义表销毁广义表: destroyGList(&L);p复制广义表复制广义表: copyGList(&T, L);p求广义表的长度求广义表的长度: length(L);p求广义表的深度求广义表的深度: depth(L);p求广义表的表头求广义表的表头: getHead(L);p求广义表的表尾求广义表的表尾: getTail(L);p插入一个元素使其成为新的表头插入一个元素使其成为新的表头: insertFirst(&L, e);p删除表头元素删除表头元素: deleteFirst(&L, &e);p判别表能否空判别表能否空: isEmpty(L);新联学院数据结构5-57 5.5 广义表的存储构造p广义表作为广义表作为ADTADT Glist 数据对象数据对象: D=ei |i=1,2,