中国科学技术大学：《数据结构及其算法》课程教学资源（课件讲稿）Ch5 数组和广义表

2014/47 S5.1多维数组 数据结构 ■多维数组 是最易处理的非线性结构。因为各元素类型一 Ch.5数组和广义表 致，各维上下界固定，所以它最容易线性化， 故可看做是线性表的拓广。例如：二维数组可 以看做是由列向量组成的线性表。 计算机学院 肖明军 Email:xiaomj@ustc.edu.cn http://staff.ustc.edu.cn/~xiaomj §5.1多维数组 §5.1多维数组 1.结构特性 ■非线性特征 例：二维数组A. ith行：前驱a1,后继a+ g,eA它属于两个向量；ith行和h列。 jh列：前驱a,后继a- 除边界外，每个a,恰有两个直接前驱和两个直 仅有一个开始结点：a 接后继。 仅有一个终端节点：am 其他边界上的结点只有一个直接前驱或 一个直接后继，类似的m维数组A,~的 每一个元素都属于m个向量。 S5.1多维数组 85.1多维数组 存储 ②列优先（列主序）方法 44…0,442…02,…,A4n…0 一般均采用顺序方式存储，原因是结构 特点行下标变化最快，先排最左下标（可推广 中的结点不变动，内存是一维的，必须 至多维)。Fortan是用此方法。 将多维数组线性化。 ③地址计算 ①行优先（行主序）方式： 马，→一维存储地址（内部实现）。 将(i+I)h行向量紧接在ih行向量之后： ·基地址一开始结点存储地址Loc(a 444n,4424,…,a4a 。维数—一每维的上下界（若下界固定，则只须 特点：列下标变化快。Pascal、C等均是此方 知道维长度) 法。先排最右下标（多维）。 每个元素占用的单元数（元素大小）：L

2014/4/7 1 数据结构 Ch.5数组和广义表 计 算 机 学 院 肖明军 Email: xiaomj@ustc.edu.cn http://staff.ustc.edu.cn/~xiaomj §5.1 多维数组 多维数组 是最易处理的非线性结构。因为各元素类型一 致，各维上下界固定，所以它最容易线性化， 故可看做是线性表的拓广。例如：二维数组可 以看做是由列向量组成的线性表 2 。 §5.1 多维数组 1. 结构特性 例：二维数组 ，它属于两个向量；i th行和j th列。 3 ，它属于两个向量；i th行和j th列。 除边界外，每个aij恰有两个直接前驱和两个直 接后继。 §5.1 多维数组  非线性特征 i th行：前驱aij-1，后继aij+1 j th列：前驱ai-1j，后继ai-1j 4 仅有一个开始结点：a11 仅有一个终端节点：amn 其他边界上的结点只有一个直接前驱或 一个直接后继，类似的m维数组 的 每一个元素都属于m个向量。 §5.1 多维数组 2. 存储 一般均采用顺序方式存储，原因是结构 中的结点不变动，内存是一维的，必须 将多维数组线性化。 5 ① 行优先（行主序）方式： 将(i+1)th行向量紧接在i th行向量之后： 特点：列下标变化快。Pascal、C等均是此方 法。先排最右下标（多维）。 §5.1 多维数组 ② 列优先（列主序）方法 特点行下标变化最快，先排最左下标（可推广 至多维）。Fortan是用此方法。 ③ 地址计算 6 一维存储地址（内部实现）。  基地址——开始结点存储地址Loc(a11).  维数——每维的上下界（若下界固定，则只须 知道维长度）  每个元素占用的单元数（元素大小）：L

2014/47 §5.1多维数组 S5.1多维数组 例：行主序Ax,·A1m,1.可 ·多维推广：以C为例，行主序。 原理：a,的地址=基址+排在a,之前的元素个数×每 444→40.4-1,0.4-1，，0.d.-1] 个元素的大小 Lacta)=Loc(an)+(hxdxd.xd+jxdx.xd++jxd+j)xL Loc(a,)=Loc(an)+[(i-1)xnt(i]XL 。思考：Acd,cd] 前一1行结点总数第行上4之前的结点数 Loc(a,FLoc(aeaH匹.slX(d-c+lt-c】XL 在C语言中，Anx是[0m-1,0m-l],故有： 1山行前行数第2维长度 1h行0，之前结点数 Loc(a)=Loc(apo)+[ixnj]XL 。特点：随机存取。 S5.2矩阵的压缩存储 S5.2矩阵的压缩存储 用二维数组表示的特点：随机存取，存储密 1,对称阵 度为1。但对特殊和稀琉矩阵的存储则浪费空 n阶方阵4，若ay=a:0≤i,j≤n-L,则称4为对称阵。 间，尤其是大规模科学与工程计算。 因为矩阵元素关于主对角线对称，故只存上三角或 下三角元素即可，节约近一半空间。 55.2.1特殊矩阵 不失一般性，存储下三角（包括主对角线），以行 主序存储： 有规建：压缩后可找到地址变换公式，保持 随机存取功能。 元素个数 艺e+=a+D/2 承复元素 分布有规律 yam au an 零元素 →a0 a 85.2矩阵的压缩存储 s5.2矩阵的压缩存储 。压缩存佛： ②上三角中有1<】 将其存于向量sa0.mt1)y2一1]中。 :a:=ay,只需交换上式的和即可得 如何访问a,?必须将其与sak的对应关系找出来。 k=jU+1)/2+1 地址计算： 令=max(i,0,=min(,),则k和i,j之关系可统 ①下三角中有j≤i 一表示为：k=11+)/2+J 4y之前有行(0~-1) 2 三角矩阵 元米个数=克e+D=0+0/2 压缩方式同上，在3中多增加一个单元： sa[0..n(n+1y2] 第行上a之前元素个数为0-~1)， 将C存于最后一个分量中。 .k=i(i+0/2+j 2

2014/4/7 2 §5.1 多维数组 例：行主序 。 A[1..m,1..n] 原理：aij的地址=基址+排在aij之前的元素个数×每 个元素的大小 Loc(aij)=Loc(a11)+[(i-1)×n+(j-1)] ×L 7 前i-1行结点总数 第i行上aij之前的结点数 在C语言中， 是A[0..m-1 , 0..n-1]，故有： Loc(aij)=Loc(a00)+[i×n+j] ×L §5.1 多维数组  多维推广：以C为例，行主序。  思考：A[c1..d1 , c2..d2] 8 Loc(aij)=Loc(ac1c2)+[(i-c1) ×(d2-c2+1)+(j-c2)] ×L i th行前行数 第2维长度 i th行aij之前结点数  特点：随机存取。 §5.2 矩阵的压缩存储  用二维数组表示的特点：随机存取，存储密 度为1。但对特殊和稀疏矩阵的存储则浪费空 间，尤其是大规模科学与工程计算。 §5 2 1 特殊矩阵 9 §5.2.1 特殊矩阵  有规律：压缩后可找到地址变换公式，保持 随机存取功能。 §5.2 矩阵的压缩存储 1. 对称阵 n阶方阵A，若 则称A为对称阵。 因为矩阵元素关于主对角线对称，故只存上三角或 下三角元素即可，节约近一半空间。 不失一般性，存储下三角（包括主对角线），以行 10 不失 般性，存储下 角 包括 对角线 ，以行 主序存储： 元素个数 §5.2 矩阵的压缩存储  压缩存储： 将其存于向量sa[0..n(n+1)/2－1]中。 如何访问aij？必须将其与sa[k]的对应关系找出来。  地址计算： ① 下三角中有j ≤ i 11 ① 下三角中有j ≤ i. aij之前有i行（0 ~ i-1） 第i行上aij之前元素个数为j(0 ~ j-1). §5.2 矩阵的压缩存储 ② 上三角中有i < j ,只需交换上式的j和i即可得： 令I=max (i , j)，J=min (i , j)，则k和i，j之关系可统 一表示为： 12 2. 三角矩阵 压缩方式同上，在sa中多增加一个单元： sa[0..n(n+1)/2] 将C存于最后一个分量中

201447 §5.2矩阵的压缩存储 §5.2矩阵的压缩存储 3.对角矩阵 85.2.2稀疏矩阵 ■，定义：设A中有r个非零元素，若t<m×n,称A为 稀琉矩阵。 稀疏因子：6=兰≤05一般非零元素分布无规律性 mXR 总结：这类矩阵压缩存储后能找到地址计算公式， 。:压缩存储： 使其保持随机存取的功能。 只存储非零元，故须存储辅助信息，才能确 定其位置。 D隐提年线.行号列号，非零元的 当用三元组表示非零元时，有两种压缩方式： 顺序和链式。 §5.2矩阵的压缩存储 §5.2矩阵的压缩存储 1.三元组顺序表（三元组表） typedef struct(//3三元组表 以行主序（或列主序）的顺序存储非零元，跳 TripleNode data[MaxSize]: 过零元。得到一个其节点均是三元组的线性表， intm,n,t/行数，列数，非零元总数 称此顺序存储结构为三元组表。 )TripleTable: #define MaxSize 10000 设a,b是TripleTable型变量。 typedef int DataType 0106 [05008 50-20 typedef struct/E元组 10300 030 A-0-2000 000 inti,j月 60000 DataType v: 。转里运算 )TripleNode: An→B 4[门=L[时0≤1≤m-1,0≤j≤m-1 §5.2矩阵的压缩存储 s5.2矩阵的压缩存储 用 ①方法一：按B的次序或按A的列序转置。 800 ,A的列是B的行，故按A的列序转置，所得B是按 行主序存放的。 基本思想：对A中每列，从头至尾扫描a.data,找出 所有列号为co的三元组(0scos-1),将它们的行、 列号互换后依次放入b.data,即可得行主序表示的B 2 的三元组。 2 √正确性：按A的列号递增序转置，保证B按行号增 序排列，B中同一行号的三元组，扫描A时所得三元 组G,eo,》,(,eol,v2必有，转置后保证按B的列 号增序排列。 √例，上图。 MaxSize-l 3

2014/4/7 3 §5.2 矩阵的压缩存储 3. 对角矩阵 总结：这类矩阵压缩存储后能找到地址计算公式 13 ， 使其保持随机存取的功能。 §5.2 矩阵的压缩存储 § 5.2.2 稀疏矩阵  定义：设Amn中有t个非零元素，若 ，称A为 稀疏矩阵。  稀疏因子： 一般非零元素分布无规律性  压缩存储： 14 只存储非零元，故须存储辅助信息，才能确 定其位置。 三元组(i，j，aij)：（行号，列号，非零元的 值）唯一确定一个非零元。 当用三元组表示非零元时，有两种压缩方式： 顺序和链式。 §5.2 矩阵的压缩存储 1. 三元组顺序表（三元组表） 以行主序（或列主序）的顺序存储非零元，跳 过零元。得到一个其节点均是三元组的线性表， 称此顺序存储结构为三元组表。 #define MaxSize 10000 15 typedef int DataType typedef struct{//三元组 int i, j； DataType v; }TripleNode; §5.2 矩阵的压缩存储 typedef struct{//三元组表 TripleNode data[MaxSize]; int m, n, t; //行数，列数，非零元总数 }TripleTable; 设a，b是TripleTable型变量。 16  转置运算 §5.2 矩阵的压缩存储 17 §5.2 矩阵的压缩存储 ① 方法一：按B的次序或按A的列序转置。 ∵A的列是B的行，故按A的列序转置，所得B是按 行主序存放的。  基本思想：对A中每列，从头至尾扫描a.data，找出 所有列号为col的三元组(0≤col≤n-1)，将它们的行、 列号互换后依次放入b.data，即可得行主序表示的B 18 列号互换后依次放入 的三元组。  正确性：∵按A的列号递增序转置，保证B按行号增 序排列，B中同一行号的三元组，扫描A时所得三元 组 必有i<j，转置后保证按B的列 号增序排列。  例，上图

2014/47 §5.2矩阵的压缩存储 s5.2矩阵的压缩存储 void TransMatrix (TripleTable &a,TripleTable &b)(A=>B int p.q.col ①方法二：按A的行序转置。 if (a.t==0)Error(A is empty ) 若简单的变换a.data的行和列，则b.data为列主序存储， b.m=a.n:b.n=a.m;b.t=a.t:l行列数互换 要重排。但若预先确定A中每一列（即B中每一行）的 q=0:指示转置过的三元组 第一个非零元在b.data中应有的位置，则可正确转置。 for(cal=0:col<a.n;col++Yl对A的每一列号 位置向量： for(p=0:psa.tpt+)M扫描A的三元组表 f(a.data[p],.j=col{l找A的列号为col的三元组 [po0=0∥的第0列起址 b.data[gl.i=a.data[p].j: poffcol]=po4col-]+第col-1列非零元个数0≤col≤an-1 b.data[q].j=a.data[p].i: 时同0口)一般矩阵转 b.data[q]v=a.data[p].v 程时间Omm.面cm,款 时间一般大于普差转 q++: 置，当m时为0am) S5.2矩阵的压缩存储 §5.2矩阵的压缩存储 ■思想 void FastTransMatrix(TripleTable&a,Tripletable&b)/po[o..a.n，小比n多t if(a.t=0)Emor(代./lA全零 先求出A中每一列的非零元个数，可将第c0列 b.m =a.n;b.n a.n;b.t=a.t; 的非零元个数记入poco41]中。 for(col=0,col<=a.n:col++)potfcol]=0://step1初始化 for(p=0:p<a.tpt+)∥step2扫描a.data √step1:初始化将所有pot中元素清0. 1/O( pola.data[pl.j+1++:∥设a.datalp]」=col potfa.nj是哨兵 √step2:扫描adata,将列号为col的非零元个数累加到 for(col=1:col<a.n;col++)sep3.po叫a.nj抚用，但第二个循环须统计 pot[col41]中。 /o) pot[col]pot[col -1]+potfcol]: step3:potfcol]=pot[col-1]+pot[col]I<col<a.n-1 for (p=0:p<a.t:p++)(//step4 1O(n) cd=a.data[p小：/当前三元组列号 q=pot[col++; √step4:扫描a.data,.将(i,col,y)转置后放于b.data[pot co b.data[q]i=a.data[p] 中，pot[col]++. l0(D b.datalq]j=a.datalpli 时间Ontt),快速 b.data[q]-v=a.datalp].v. kcy:pot1a.n-第0-an-1列的非零元个数。 85.2矩阵的压缩存储 s5.2矩阵的压缩存储 以上图为例，A 3 十字链表 p时 0 ·前和列1个 上两种方式是顺序存储，若非零元位置或个数经常发生 变化，会引起结点移动，效率降低。此时宜用链式存储 2 2 埋元及领 例：A-A+B 篇1中零元个量 2 1 第1中军元个慧 3 稀疏矩阵的链接存储方式有多种，这里仅介绍十字链表 0 第3列零元个 ·结点结构 第4列件半元个数（无用】 1 一行向品上下一半等元 带行表的三元组表。（顺序方式） 。存储结构 列上下一中零元 在行优先存储的三元组表中，加入一个行 分别设两个指针数组作为各行、列单链表的头指针。 表来记录稀疏矩阵压缩后每行非零元在三元组表 中的起始位置

2014/4/7 4 §5.2 矩阵的压缩存储 void TransMatrix（TripleTable &a, TripleTable &b) {//A=>B int p, q, col; if (a.t == 0) Error(“A is empty”); b.m = a.n; b.n = a.m; b.t = a.t ; //行列数互换 q=0; //指示转置过的三元组 for( col = 0; col < a.n ; col++)//对A的每一列号 f ( 0 )//扫描 的三元组表 19 for( p = 0; p < a.t; p++)//扫描A的三元组表 if (a.data[p].j == col) {//找A的列号为col的三元组 b.data[q].i = a.data[p].j ; b.data[q].j = a.data[p].i ; b.data[q].v = a.data[p].v ; q++; } } §5.2 矩阵的压缩存储 ① 方法二：按A的行序转置。 若简单的变换a.data的行和列，则b.data为列主序存储， 要重排。但若预先确定A中每一列（即B中每一行）的 第一个非零元在b.data中应有的位置，则可正确转置。 位置向量： 20 §5.2 矩阵的压缩存储  思想 先求出A中每一列的非零元个数，可将第col列 的非零元个数记入pot[col+1]中。  step1：初始化将所有pot中元素清0. //O(n)  step2：扫描a.data，将列号为col的非零元个数累加到 pot[col+1]中。 //O(t) 21 pot[col+1]中。 //O(t)  step3：令pot[col]=pot[col-1]+pot[col] 1≤col≤a.n-1 //O(n)  step4：扫描a.data，将(i,col,v)转置后放于b.data[pot[col]] 中，pot[col]++. //O(t) 时间O(n+t)，快速。 key：pot[1..a.n]=第0~a.n-1列的非零元个数。 §5.2 矩阵的压缩存储 void FastTransMatrix(TripleTable &a , Tripletable &b) {//pot[0..a.n]，比n多1 if (a.t == 0) Error(“…”);//A全零 b.m = a.n; b.n = a.n; b.t = a.t; for ( col = 0; col<=a.n ; col++) pot[col] = 0; //step1初始化 for ( p = 0; p < a.t; p++) // step2扫描a.data pot[a.data[p].j + 1]++; //设a.data[p].j = col pot[a.n]是哨兵 for ( col = 1; col < a.n; col++)//step3. pot[a.n]无用，但第二个循环须统计 pot[col] = pot[col 1] + pot[col]; 22 pot[col] = pot[col – 1] + pot[col]; for ( p = 0; p < a.t; p++) {//step4 col = a.data[p].j; //当前三元组列号. q = pot[col]++; b.data[q].i = a.data[p].j; b.data[q].j = a.data[p].i; b.data[q].v = a.data[p].v; } } §5.2 矩阵的压缩存储 以上图为例， 23 2. 带行表的三元组表。（顺序方式） 在行优先存储的三元组表中，加入一个行 表来记录稀疏矩阵压缩后每行非零元在三元组表 中的起始位置。 §5.2 矩阵的压缩存储 3. 十字链表 上两种方式是顺序存储，若非零元位置或个数经常发生 变化，会引起结点移动，效率降低。此时宜用链式存储。 例：A←A+B 稀疏矩阵的链接存储方式有多种，这里仅介绍十字链表  结点结构 24  存储结构 分别设两个指针数组作为各行、列单链表的头指针

2014/47 §5.2矩阵的压缩存储 §5.2矩阵的压缩存储 typedef struct CLNode( inti,j; DataType v. struct CLNode right,*down; )CLNode; typedef struct{ 123 CLNode*head[MaxRow]:行链表头指针，MaxRow在前定义 每个结点是在”十 CLNode *chead[MaxCol]: int m,n,t; )CrossList; CrossListA: s5.3广义表(Lists) s5.3广义表(Lists) 1概念 。例： 是线性表的推广，如将线性表中元素放宽到可以是自 E=()—空表，长度n=0,深度d=1. 身的结构。 L=(a,b)一一n=2,d=1.(线性表) 。 定义：LS=(g,4,,4)n之0，它由n个元素构成的有限 序列，其中，或是原子，或是广义表（字子表）。 A=(x,L=(x,(a,b》一n=2,d=2.a,为原子，a2为子表 LS-名字，n-长度，n=0为空表。 B=(Ay=(x,(a,b,y)一n=2,d=3. 一般用小写字母表示原子。大写字母表示子表。 C=A,B=(x(a,b(x,(a,b》y—n=2,d=4. 表头、表尾、深度 D=(a,D=(a(a,(a(m》—n=2,d=o 若LS≠D,则，成为衰头（首），剩余元素构成的表 ·若规定任何衰都有名字，则可在每个夜前冠名。 (4,…,a)为表尾。广义表是地归定义的，展开到每 E()L(a,b)A(x,L(a,b)) 元素均为原字时括号的量大层数为深度。 85.3广义表(Lists) 85.3广义表(Lists) ,图示 。运算 求表头、表尾。 head(A)=x,taA)=(a,b)表尾是表，表头不一定 head(tail(A》=(ab)—表 纯表（与衬树应） 编归表〔允许地) head(head(ta(A》=a—原子 tail(head(tail(A)》=b一表 再入表（允许结点共享） 。各种表之关系 head(tail(head(tail(A》=b—原子 ti(il(hcad(tail(A)》=()表 递归表一再入表一纯表一线性表 Noter()和()》不同. ()为空表m0,不能求表头和表属。 ()为非空表，1.可求表头和具： head()月=(，t(=() 5

2014/4/7 5 §5.2 矩阵的压缩存储 typedef struct CLNode{ int i, j ; DataType v; struct CLNode * right, *down; }CLNode; t d f t t{ 25 typedef struct { CLNode *rhead[MaxRow]; //行链表头指针，MaxRow在前定义 CLNode *chead[MaxCol]; //列… int m,n, t; }CrossList; CrossList A; §5.2 矩阵的压缩存储 26 §5.3 广义表（Lists） 1. 概念 是线性表的推广，如将线性表中元素ai 放宽到可以是自 身的结构。  定义： ，它由n个元素构成的有限 序列，其中ai 或是原子，或是广义表（子表）。 LS-名字，n-长度，n=0为空表。 27 一般用小写字母表示原子，大写字母表示子表。  表头、表尾、深度 若 ，则a1成为表头（首），剩余元素构成的表 为表尾。广义表是递归定义的，展开到每一 元素均为原子时括号的最大层数为深度。 §5.3 广义表（Lists）  例： E=( ) ——空表，长度n = 0，深度d = 1. L=(a, b) ——n = 2，d = 1. （线性表） A=(x, L)=(x, (a, b)) ——n=2, d=2. a1为原子，a2为子表 B=(A, y)=((x, (a, b)), y) ——n = 2, d = 3. C (A B) (( ( b)) (( ( b)) )) 2d 4 28 C=(A, B)=((x, (a, b)), ((x, (a, b)), y)) ——n = 2, d = 4. D=(a, D)=(a, (a, (a, (…)))) ——n = 2, d = ∞ .  若规定任何表都有名字，则可在每个表前冠名。 E( ) L(a, b) A(x, L(a, b)) §5.3 广义表（Lists）  图示 29  各种表之关系 §5.3 广义表（Lists）  运算 求表头、表尾。 head(A) = x, tail(A) = ((a, b)) //表尾是表，表头不一定 head(tail(A)) = (a, b) ——表 30 Note： 和 不同。 为空表n=0，不能求表头和表尾。 为非空表，n=1. 可求表头和尾：

2014/47 s5.3广义表(Lists) s5.3广义表(Lists) 2存储结构 ·图示 因为广义表数据元素可具有不同结构，故难以用顺序方 E=NIL 式存储。一般用链接方式存储，称之为广义链表。 )广义表的头尾链表表示方法。 ·表结点吧→表 →aomhpp 。原子结点： tag-0 stom 1表结点，使用p和p 菊二服 邮一0原子结点，使用am 使用Uo0说明 存储结构见书上说明 §5.3广义表(Lists) s5.3广义表(Lists) ②单链表示法 ·特点 模仿战性表的单链表结构，当所有元素为原子时，等价于单链表 ①除空表的表头指针为空外，头指针均指向表结点。 ·结点结构： ②任一表结点的p均指向表头部（原子结点或表结点】 tom dats/slink limk-一→闸层后继（当无系鞋时为） 任一表结点的p均指向表尾部（当表尾部为空表时， 0本结点为子表《业指向子表的第一个结点) 【本结点为原子(4山) tp=NL,否则必指向表结点) ,图示：E=NL ③易分清表中原子和子表所在层次， C=(A,B)=((x,(a,b)),((x,(a,b)),y)) 如x、L在第一层，a、b在第二层。 =(A(x,L(a,b)),B(A(x,L(a,b)),y)) ④最高层的表结点数即为广义表的长度。 DHAD四 ⑤浪费空间，易求表长和表深度。 00□ O□N B G立□a四 g立□-b闪 §5.3广义表(Lists) s5.3广义表(Lists) ·存储结构说明 。缺点： typedef struct GLNode{ ①若要在某一表中开始处插入或删除一个结点，则要找 int atom:亦可定义为枚举类型，标志域 出所有指向该结点的指针，逐一加以修改。 struct GLNode*slink,指向同层后继 例如，上图中，删除A表中的x,修改A的头指针 union 外，须修改来自于B、C表的指针，引用来源点不易 知道。 struct GLNode*slink:指向子表的第一个结点 删除一个表可能导致错误 DataType data;I原子结点数据域 例如，删除A表时，A的所有结点释放后，会引起 optval;I候选值 B、C表的错误。 )*GList; 6

2014/4/7 6 §5.3 广义表（Lists） 2. 存储结构 因为广义表数据元素可具有不同结构，故难以用顺序方 式存储。一般用链接方式存储，称之为广义链表。 (1) 广义表的头尾链表表示方法。  表结点： 31  原子结点： 存储结构见书上说明 §5.3 广义表（Lists）  图示 E=NIL 32 §5.3 广义表（Lists）  特点 ① 除空表的表头指针为空外，头指针均指向表结点。 ② 任一表结点的hp均指向表头部（原子结点或表结点） 任一表结点的tp均指向表尾部（当表尾部为空表时， tp=NIL，否则必指向表结点） ③ 易分清表中原子和子表所在层次。 33 如x、L在第一层，a、b在第二层。 ④ 最高层的表结点数即为广义表的长度。 ⑤ 浪费空间，易求表长和表深度。 §5.3 广义表（Lists） (2) 单链表示法 模仿线性表的单链表结构，当所有元素为原子时，等价于单链表。  结点结构：  图示：E=NIL C (A B) (( ( b)) (( ( b)) )) 34 C=(A, B)=((x, (a, b)), ((x, (a, b)), y)) =(A(x, L(a, b)), B(A(x, L(a, b)), y)) §5.3 广义表（Lists）  存储结构说明 typedef struct GLNode{ int atom; //亦可定义为枚举类型，标志域 struct GLNode *slink; //指向同层后继 union { struct GLNode *slink; //指向子表的第一个结点 35 struct GLNode slink; //指向子表的第一个结点 DataType data； //原子结点数据域 }optval; //候选值 } *GList; §5.3 广义表（Lists）  缺点： ① 若要在某一表中开始处插入或删除一个结点，则要找 出所有指向该结点的指针，逐一加以修改。 例如，上图中，删除A表中的x，修改A的头指针 外，须修改来自于B、C表的指针，引用来源点不易 知道。 36 ② 删除一个表可能导致错误。 例如，删除A表时，A的所有结点释放后，会引起 B、C表的错误

2014/47 §5.3广义表(Lists) s5.3广义表(Lists) 3)双链表示法 引入表头结点，使子表内部的变化不会涉及外部元素的变化， 插删第一个结点方便。头结点和其他结点结构相同，只是以示 该方法类似于第6章的二叉链表。 区别： 。结点结构 「一1表头结点，m域指向表中第一个结点：d血域为引用计数 m一{0本结点为子表 指向同层后继 1本结点为原子 删除表时，头结点引用计数减1，仅当引用计数为0时，才释放 指向子表中第一个结点 表中所有结点。 结点为原子台imk1m EG西 。存储说明 cGa@配o typedef struct GLNodef BO- 起@西 DataType data;∥子表名字或原子数据 如G西 struct GLNode "link1."link2: 】GLst 何加工N §53广义表(Lists) s5.3广义表(Lists) 图示beadB-A 例子 (姓名，工资收入（盖本工资，午餐补助，津贴，扣除（公积金水电贵其它，实发工资） heac-A□BA 工癸收入 扣除 实发 headBG 名红竹餐神指公积脸水电爽其蛇正变 headA☐ x正 catC-姓名肛效以扫除-h发r钢 headL □Ab囚 公发a一炮共起囚 特点 江补粘☒ 角霞洁方便、类似于二又链表。可倍于二又随表表示处星易求长度深 在表结点中保存了子表的名字信总，有时子表名字和原子信息同样要要、 运算：略

2014/4/7 7 §5.3 广义表（Lists）  改进 引入表头结点，使子表内部的变化不会涉及外部元素的变化， 插删第一个结点方便。头结点和其他结点结构相同，只是以示 区别： 删除表时，头结点引用计数减1，仅当引用计数为0时，才释放 37 删除表时，头结点引用计数减 ，仅当引用计数为0时，才释放 表中所有结点。 §5.3 广义表（Lists） (3) 双链表示法 该方法类似于第6章的二叉链表。  结点结构 38  存储说明 typedef struct GLNode{ DataType data; //子表名字或原子数据 struct GLNode *link1, *link2; } *GList; §5.3 广义表（Lists）  图示 39  特点 ① 简洁方便，类似于二叉链表，可借助于二叉链表表示处理，易求长度深 度。 ② 在表结点中保存了子表的名字信息，有时子表名字和原子信息同样重要。 §5.3 广义表（Lists）  例子 (姓名,工资收入(基本工资,午餐补助,津贴),扣除(公积金,水电费,其它),实发工资) 3. 运算：略 40