数据结构第五章学习教案.pptx

《数据结构第五章学习教案.pptx》由会员分享，可在线阅读，更多相关《数据结构第五章学习教案.pptx（36页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、会计学1数据结构数据结构(sh j ji u)第五章第五章第一页，共36页。2数组：数组： 由一组名字相同、下标不同的变量由一组名字相同、下标不同的变量(binling)构成构成注意：注意： 本章本章(bn zhn)所讨论的数组与高级语言中的数组有所区别：高级语言中的数组是顺序结构；而本章所讨论的数组与高级语言中的数组有所区别：高级语言中的数组是顺序结构；而本章(bn zhn)的数组既可以是顺序的，也可以是链式结构，用户可根据需要选择。的数组既可以是顺序的，也可以是链式结构，用户可根据需要选择。答：答：对的对的。因为：。因为： 数组中各元素具有数组中各元素具有统一的类型统一的类型； 数组元素的

2、下标一般具有数组元素的下标一般具有固定的上界和下界固定的上界和下界，即数组一旦被定义，它的维数和维界就不再改变。，即数组一旦被定义，它的维数和维界就不再改变。数组的数组的基本操作比较简单基本操作比较简单，除了结构的初始化和销毁之外，只有存取元素和修改元素值的操作。，除了结构的初始化和销毁之外，只有存取元素和修改元素值的操作。讨论：讨论：“数组的处理比其它复杂的结构要简单数组的处理比其它复杂的结构要简单”，对吗？，对吗？第1页/共36页第二页，共36页。3一维数组的特点一维数组的特点(tdin)(tdin)：1 1个下标个下标(xi bio)(xi bio)，ai ai 是是ai+1ai+1的直

3、接前驱的直接前驱2 2个下标，个下标，每个元素每个元素ai,j受到两个关系（行关系和列关系）的约束：受到两个关系（行关系和列关系）的约束：一个一个mn的二维数组可以看成是的二维数组可以看成是m行的一维数组，或者行的一维数组，或者n列的一维数组。列的一维数组。N N维数组的特点：维数组的特点：n n个下标，个下标，每个元素受到每个元素受到n n个关系约束个关系约束一个一个n维数组可以看成是维数组可以看成是由若干个由若干个n1维数组组成的线性表。维数组组成的线性表。 a11 a12 a1n a21 a22 a2n am1 am2 amn Amn=第2页/共36页第三页，共36页。4n_ARRAY

4、= (D, R)其中(qzhng)： Ri = | aj1,j2,jijn , aj1,j2,ji+1jn D 数据数据(shj)关系：关系：R = R1 ,R2，. Rn 数据对象：数据对象：D = aj1,j2jn| ji为数组元素的第为数组元素的第i 维下标维下标 ，aj1,j2jn Elemset数组的抽象数据类型定义数组的抽象数据类型定义略略，参见教材参见教材P90P90构造数组、销毁数组、读数组元素、写数组元素构造数组、销毁数组、读数组元素、写数组元素基本操作：基本操作：第3页/共36页第四页，共36页。5问题：计算机的存储结构是一维的，而数组一般问题：计算机的存储结构是一维的，而

5、数组一般(ybn)(ybn)是多维的，怎样存放？是多维的，怎样存放？解决办法：事先约定按某种次序将数组元素排成一列序列，然后将这个线性序列存入存储器中。解决办法：事先约定按某种次序将数组元素排成一列序列，然后将这个线性序列存入存储器中。例如：在二维数组中，我们既可以规定按行存储，也可以规定按列存储。例如：在二维数组中，我们既可以规定按行存储，也可以规定按列存储。注意：注意：若规定好了次序，则数组中任意一个元素的存放地址便有规律可寻，可形成地址计算公式；若规定好了次序，则数组中任意一个元素的存放地址便有规律可寻，可形成地址计算公式；约定的次序不同约定的次序不同(b tn)(b tn)，则计算元素

6、地址的公式也有所不同，则计算元素地址的公式也有所不同(b tn)(b tn)；C C和和PASCALPASCAL中一般采用行优先顺序；中一般采用行优先顺序；FORTRANFORTRAN采用列优先。采用列优先。第4页/共36页第五页，共36页。6无论无论(wln)(wln)规定行优先或列优先，只要知道以下三要素便可随时求出任一元素的地址（这样数组中的任一元素便可以随机存取！规定行优先或列优先，只要知道以下三要素便可随时求出任一元素的地址（这样数组中的任一元素便可以随机存取！) )二维数组列优先二维数组列优先(yuxin)(yuxin)存储的通式为：存储的通式为：LOC(aij)=LOC(ac1L

7、OC(aij)=LOC(ac1，c2)+(j-c2)c2)+(j-c2)* *(d1-c1+1)+i-c1)(d1-c1+1)+i-c1)* *L L ac1,c2 ac1,d2 aij ad1,c2 ad1,d2 Amn=单个元素长单个元素长度度aij之前的行之前的行数数数组基址数组基址总列数，即第总列数，即第2 2维长度维长度aij本行前面的元本行前面的元素个数素个数开始结点的存放地址（即基地址）开始结点的存放地址（即基地址）维数和每维的上、下界；维数和每维的上、下界；每个数组元素所占用的单元数每个数组元素所占用的单元数则则行优先行优先存储时的地址公式为：存储时的地址公式为：LOC(aij

8、)=LOC(ac1，c2)+(i-c1)*(d2-c2+1)+j-c2)*L第5页/共36页第六页，共36页。7例例1软考题：一个二维数组软考题：一个二维数组A，行下标的范围是，行下标的范围是1到到6，列下标的范围是，列下标的范围是0到到7，每个数组元素用相邻的，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个个字节存储，存储器按字节编址。那么，这个(zh ge)数组的体积是数组的体积是 个字节。个字节。 288例例3：00年计算机系考研题年计算机系考研题设数组设数组a160, 170的基地的基地址为址为2048，每个元素占，每个元素占2个存储单元，若以列序为主序顺序存储，个存储

9、单元，若以列序为主序顺序存储，则元素则元素a32,58的存储地址为的存储地址为 。8950LOC(aij)=LOC(ac1，c2)+(j-c2)*(d1-c1+1)+i-c1)*L得：得：LOC(a32,58)=2048+(58-1)*(60-1+1)+32-1)*28950答：请注意审题！答：请注意审题！利用列优先通式：利用列优先通式：答：答： Volume=m*n*L=(6-1+1)*(7- 0 +1)*6=48*6=288第6页/共36页第七页，共36页。8niii1jC其中其中(qzhng)Cn=L, Ci-1=biCi， 1in一个一个(y (y )元元素长度素长度数组基址数组基址前

10、面若干元素占用前面若干元素占用的地址字节总数的地址字节总数第第i i维长度维长度与所存元素个数有关的系数与所存元素个数有关的系数，可用递推法求出，可用递推法求出教材已给出教材已给出低维低维优先的地址计算公式，优先的地址计算公式，见见P93P93（5-25-2）式）式该式称为该式称为n n维数组的映像函数维数组的映像函数：容易看出，数组元素的存储位置是其下标的线性函数，一旦确定了数组的各维的长度，则Ci就是常数！第7页/共36页第八页，共36页。9讨论：讨论：1. 什么是压缩存储？什么是压缩存储？若多个数据元素的值都相同，则只分配一个元素值的存储空间，且零元素不占存储空间。若多个数据元素的值都相

11、同，则只分配一个元素值的存储空间，且零元素不占存储空间。2. 所有二维数组（矩阵）都能压缩吗？所有二维数组（矩阵）都能压缩吗？未必，要看矩阵是否具备未必，要看矩阵是否具备(jbi)以上压缩条件。以上压缩条件。3. 什么样的矩阵具备什么样的矩阵具备(jbi)以上压缩条件？以上压缩条件？ 一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。4. 什么叫稀疏矩阵？什么叫稀疏矩阵？矩阵中非零元素的个数较少（一般小于矩阵中非零元素的个数较少（一般小于5%）重点介绍重点介绍(jisho)稀疏矩阵的压缩和相应的操作。稀疏矩阵的压缩和相应的操

12、作。第8页/共36页第九页，共36页。10问题：问题：如果只存储稀疏矩阵如果只存储稀疏矩阵(j zhn)中的非零元素，那这中的非零元素，那这些元素的位置信息该如何表示？些元素的位置信息该如何表示？解决思路：解决思路：对每个非零元素增开若干存储单元，例如存放其所对每个非零元素增开若干存储单元，例如存放其所在的行号和列号，便可准确反映该元素所在位置。在的行号和列号，便可准确反映该元素所在位置。实现方法：实现方法：将每个非零元素用一个三元组（将每个非零元素用一个三元组（i，j，aij）来表示）来表示，则每个稀疏矩阵，则每个稀疏矩阵(j zhn)可用一个三元组表来表可用一个三元组表来表示。示。二、稀疏

13、二、稀疏(xsh)(xsh)矩阵矩阵的操作的操作第9页/共36页第十页，共36页。11行下标行下标(xi bio)列下标列下标(xi bio)元素值元素值例例2 2：写出右图所示稀疏矩写出右图所示稀疏矩阵的压缩存储形式。阵的压缩存储形式。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,1

14、8) ，(6,1,15)(6,1,15)， (6,4,-7)(6,4,-7) )法法1 1：用线性表表示：用线性表表示：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第10页/共36页第十一页，共36页。12法法2 2：用三元组矩阵：用三元组矩阵(j (j zhn)zhn)表示：表示：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 0121213931-3351443245218611564-7注

15、意：为更可靠描述，通常再加一行注意：为更可靠描述，通常再加一行“总体总体”信息：即总行信息：即总行(zn xn)(zn xn)数、总列数、非零元素总个数数、总列数、非零元素总个数668ijvalue稀疏稀疏(xsh)矩阵压缩存储的缺点：将失去随机存取功矩阵压缩存储的缺点：将失去随机存取功能能 ！第11页/共36页第十二页，共36页。1376531211202NUM( i)6543POS( i )21i0 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-7461516182524341453-313

16、9311221866vji0123456783用途：通过三元组高效访问稀疏矩阵用途：通过三元组高效访问稀疏矩阵(j zhn)中任一非零元素。中任一非零元素。规律：规律：POS(1)1 POS(i)POS(i-1)+NUM(i-1)第12页/共36页第十三页，共36页。14 #define MAXSIZE 125000 / #define MAXSIZE 125000 /设非零元素最大个数设非零元素最大个数125000125000 typedef struct typedef struct int i; / int i; /元素行号元素行号 int j; / int j; /元素列号元素列号 E

17、lemType e; / ElemType e; /元素值元素值Triple; Triple; typedef structtypedef struct Triple dataMAXSIZE+1; / Triple dataMAXSIZE+1; /三元组表，以行为主序存入一维三元组表，以行为主序存入一维向量向量 data data 中中 int mu; / int mu; /矩阵总行矩阵总行(zn xn)(zn xn)数数 int nu; / int nu; /矩阵总列数矩阵总列数 int tu; / int tu; /矩阵中非零元素总个数矩阵中非零元素总个数TsMatrix; TsMatri

18、x; 三元组表的顺序存储表示三元组表的顺序存储表示(biosh)(biosh)（见教材（见教材P98P98）：）：/一个一个(y )(y )结点的结构定义结点的结构定义/整个三元组表的定义整个三元组表的定义第13页/共36页第十四页，共36页。150 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 00 0 3 0 0 1512 0 0 0 18 0 9 0 0 24 0 00 0 0 0 0 -70 0 14 0 0 00 0 0 0 0 0(1, 2, 12)(1, 3, 9 )(3, 1, -3)

19、(3, 5, 14)(4, 3, 24)(5, 2, 18)(6, 1, 15)(6, 4, -7)(1, 3, -3)(1, 6, 15)(2, 1, 12)(2, 5, 18)(3, 1, 9)(3, 4, 24)(4, 6, -7)(5, 3, 14)三三元元组组表表a.data三三元元组组表表b.data转置后转置后MT（以转置（以转置(zhun zh)(zhun zh)运算为例）运算为例）目的目的(md)(md)：第14页/共36页第十五页，共36页。16答：肯定不正确！答：肯定不正确！除了：除了： （1 1）每个元素）每个元素(yun s)(yun s)的行下标和列下标互换（即三元

20、组中的的行下标和列下标互换（即三元组中的i i和和j j互换）；互换）；还应该：（还应该：（2 2）T T的总行数的总行数mumu和总列数和总列数nunu与与M M值不同（互换）；值不同（互换）； （3 3）重排三元组内元素）重排三元组内元素(yun s)(yun s)顺序，使转置后的三元组也按行（或列）为主序有规律的排列。顺序，使转置后的三元组也按行（或列）为主序有规律的排列。上述（上述（1 1）和（）和（2 2）容易实现）容易实现(shxin)(shxin)，难点在（，难点在（3 3）。）。 若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算若

21、采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算(yn sun)(yn sun)，这种说法正确吗？，这种说法正确吗？ 有两种实现方法有两种实现方法压缩转置压缩转置( (压缩压缩) )快速转置快速转置提问：提问：第15页/共36页第十六页，共36页。17思路：反复思路：反复(fnf)(fnf)扫描扫描a.dataa.data中的列序，从小到大依次中的列序，从小到大依次进行转置。进行转置。三三元元组组表表a.data三三元元组组表表b.data(1, 3, -3)(1, 6, 15)(2, 1, 12) (2, 5, 18)(3, 1, 9) (3,

22、4, 24) (4, 6, -7) (5, 3, 14)(1, 2, 12)(1, 3, 9 )(3, 1, -3)(3, 5, 14)(4, 3, 24)(5, 2, 18)(6, 1, 15)(6, 4, -7)11 22col q1234 p1234第16页/共36页第十七页，共36页。18Status TransPoseSMatrix(TSMatrix M, TSMatrix &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.d

23、atap.j=col) T.dataq.i=M.datap.j; T.dataq.j=M.datap.i; T.dataq.value=M.datap.value; q+; return OK; /TranposeSMatrix;压缩转置算法描述压缩转置算法描述(mio sh)：（见教材：（见教材P99）/用三元组表存放稀疏用三元组表存放稀疏(xsh)(xsh)矩阵矩阵M M，求，求M M的转置矩阵的转置矩阵T T/q/q是转置是转置(zhun zh)(zhun zh)矩阵矩阵T T的结点编号的结点编号/colcol是扫描是扫描M M三元表列序的变量三元表列序的变量/p是是M M三元表中结点编

24、号三元表中结点编号第17页/共36页第十八页，共36页。191 1、主要时间消耗在查找、主要时间消耗在查找M.datap.j=colM.datap.j=col的元素，由两重循环完成的元素，由两重循环完成: for(col=1; col=M.nu; col+) : for(col=1; col=M.nu; col+) 循环次数循环次数nunu for(p=1; p=M.tu; p+) for(p=1; p=M.tu; p+) 循环次循环次数数tutu所以该算法的时间复杂度为所以该算法的时间复杂度为O(nuO(nu* *tu)tu) - -即即M M的列数与的列数与M M中非零元素的个数之积中非零

25、元素的个数之积最恶劣情况：最恶劣情况：M M中全是非中全是非(shfi)(shfi)零元素，此时零元素，此时tu=mutu=mu* *nunu， 时间复杂度为时间复杂度为 O(nu2 O(nu2* *mu )mu )注：若注：若M M中基本上是非中基本上是非(shfi)(shfi)零元素时，即使用非压缩传统转置零元素时，即使用非压缩传统转置算法的时间复杂度也不过是算法的时间复杂度也不过是O(nuO(nu* *mu) mu) （程序见教材（程序见教材P99P99）结论：压缩转置算法不能滥用。结论：压缩转置算法不能滥用。前提：仅适用于非零元素个数很少（即前提：仅适用于非零元素个数很少（即tumut

26、umu* *nunu）的情况。）的情况。压缩转置算法的效率压缩转置算法的效率(xio l)分析：分析：第18页/共36页第十九页，共36页。20思路：经过一次扫描能否思路：经过一次扫描能否(nn fu)(nn fu)确定每个元素转置后的位置确定每个元素转置后的位置三三元元组组表表a.data三三元元组组表表b.data(2, 1, 12)(3, 1, 9)(1, 2, 12)(1, 3, 9 )(3, 1, -3)(3, 5, 14)(4, 3, 24)(5, 2, 18)(6, 1, 15)(6, 4, -7)col q1234 p1234第19页/共36页第二十页，共36页。210 12

27、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 00 0 3 0 0 1512 0 0 0 18 0 9 0 0 24 0 00 0 0 0 0 -70 0 14 0 0 00 0 0 0 0 0转置后转置后MT(1, 2, 12)(1, 3, 9 )(3, 1, -3)(3, 5, 14)(4, 3, 24)(5, 2, 18)(6, 1, 15)(6, 4, -7)第20页/共36页第二十一页，共36页。第21页/共36页第二十二页，共36页。23col123456numcol222110cpotcol1

28、规律规律(gul)： cpot(1)1cpotcol cpotcol-1 + numcol-10 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 0M 3 5 7 8 8col 1 2 3 4 5 6第22页/共36页第二十三页，共36页。 0000280000000091039000000006000017000110150022000A76 a0 0 3 22a1 0 6 15a2 1 1 11a3 1 5 17a4 2 3 -6a5 3 5 39a6 4 0 91a7 5 2 28b0 0 4 9

29、1b1 1 1 11b2 2 5 28b3 3 0 22b4 3 2 -6b5 5 1 17b6 5 3 39b7 6 0 15C0 c1 c2 c3 c4 c5 c6=1 =2 =3 =4 =6 =6 =8 n0 n1 n2 n3 n4 n5 n6=1 =1 =1 =2 =0 =2 =1第23页/共36页第二十四页，共36页。25Status FastTransposeSMatrix（TSMatirx M, TSMatirx &T） T.mu = M.nu ;T .nu = M.mu ; T.tu = M.tu ; if ( T.tu ) for(col = 1; col =M.nu; co

30、l+) numcol =0; for( i = 1; i =M.tu; i +) col =M.data i .j ; +num col ; cpos 1 =1; for(col = 2; col =M.nu; col+) cposcol =cposcol-1+num col-1 ; for( p =1; p =M.tu ; p + ) col =M.data p . j ; q =cpos col ; T.dataq.i = M.datap. j; T.dataq.j = M.datap. i; T.dataq. value = M.datap. value; /for /ifreturn

31、OK; /FastTranposeSMatrix;快速快速(kui s)转置算法描述：转置算法描述：/M/M用顺序存储表示，求用顺序存储表示，求M M的转置的转置(zhun zh)(zhun zh)矩阵矩阵T T/先统计先统计(tngj)(tngj)每列非零元素个数每列非零元素个数/再生成每列首元位置辅助向量表再生成每列首元位置辅助向量表/p/p指向指向a.dataa.data，循环次数为非，循环次数为非0 0元素总个数元素总个数tutu/查辅助向量表得查辅助向量表得q q，即，即T T中位置中位置/重要语句！重要语句！修改向量表中列坐标值，供修改向量表中列坐标值，供同一列同一列下一非零元素定

32、位之用！下一非零元素定位之用！第24页/共36页第二十五页，共36页。261. 1. 与常规与常规(chnggu)(chnggu)算法相比，附加了生成辅助向量表的工作。增开了算法相比，附加了生成辅助向量表的工作。增开了2 2个长度为列长的数组个长度为列长的数组(num (num 和和cpos cpos ）。）。 传统转置：传统转置：O(muO(mu* *nu) nu) 压缩压缩(y su)(y su)转置：转置：O(muO(mu* *tu) tu) 压缩压缩(y su)(y su)快速转置：快速转置：O(nu+tu)O(nu+tu)牺牲空间效率换时间效率。牺牲空间效率换时间效率。快速转置快速转

33、置(zhun zh)算法的效率分析：算法的效率分析：2. 2. 从时间上，此算法用了从时间上，此算法用了4 4个并列的单循环，而且其中前个并列的单循环，而且其中前3 3个单循环都是用来产生辅助向量表的。个单循环都是用来产生辅助向量表的。 for(col = 1; col =M.nu; col+) 循环次数循环次数nu;nu; for( i = 1; i =M.tu; i +) 循环次数循环次数tu;tu; for(col = 2; col =M.nu; col+) 循环次数循环次数nu;nu; for( p =1; p =M.tu ; p + ) 循环次数循环次数tu;tu; 该算法的时间复杂

34、度该算法的时间复杂度(nu(nu* *2)+(tu2)+(tu* *2)=O(nu+tu2)=O(nu+tu）讨论：最恶劣情况是讨论：最恶劣情况是tu=nutu=nu* *mu(mu(即矩阵中全部是非零元素），即矩阵中全部是非零元素），而此时的时间复杂度也只是而此时的时间复杂度也只是O(muO(mu* *nu)nu)，并未超过传统转置算法的时间复杂度。，并未超过传统转置算法的时间复杂度。小结：小结：稀疏矩阵相乘的算法见教材稀疏矩阵相乘的算法见教材P101-103P101-103第25页/共36页第二十六页，共36页。27广义表是线性表的推广广义表是线性表的推广(tugung)，也称为列表，也称

35、为列表（lists）记为：记为： LS = ( a1 , a2 , ， an ) 广义广义(gungy)表名表名 表头表头(Head） 表尾表尾 (Tail)1、定义：、定义： 第一个元素是表头，而其余元素组成的表称为表尾；第一个元素是表头，而其余元素组成的表称为表尾； 用小写字母表示原子类型，用大写字母表示列表。用小写字母表示原子类型，用大写字母表示列表。n n是表长是表长在广义表中约定：在广义表中约定：讨论：讨论：广义表与线性表的区别和联系？广义表与线性表的区别和联系？ 广义表中元素既可以是原子类型，也可以是列表广义表中元素既可以是原子类型，也可以是列表；当每个元素都为原子且类型相同时，就

36、是线性表。当每个元素都为原子且类型相同时，就是线性表。第26页/共36页第二十七页，共36页。28一个直接前驱和一个直接后继一个直接前驱和一个直接后继表中元素个数表中元素个数表中括号的重数表中括号的重数自己自己(zj)可以作为自己可以作为自己(zj)的子的子表表可以为其他广义表所共享可以为其他广义表所共享特别提示：任何一个非空表，表头可能是原子，也可能是列表；但表尾一定是列表特别提示：任何一个非空表，表头可能是原子，也可能是列表；但表尾一定是列表。第27页/共36页第二十八页，共36页。29E=(a,E)=(a,(a,E)= (a,(a,(a,.)，E为递归表为递归表1）A =( )2）B =

37、 ( e ) 3）C =( a ,( b , c , d ) ) 4）D=( A , B ,C )5）E=(a, E)例例1：求下列：求下列(xili)广义表的长度广义表的长度。n=0，因为，因为A是空表是空表n=1，表中元素，表中元素(yun s)e是原子是原子n=2，a 为原子，为原子，(b,c,d)为子表为子表n=3，3个元素个元素(yun s)都是子表都是子表n=2，a 为原子，为原子，E为子表为子表D=(A,B,C)=( ),(e),(a,(b,c,d)，共享表共享表第28页/共36页第二十九页，共36页。30ABDCeabcd A=( a , (b, A) )例例2 2：试用图形表

38、示下列广义表：试用图形表示下列广义表. .（设（设 代表代表(dibio)(dibio)原子，原子， 代表代表(dibio)(dibio)子表）子表） e D=(A,B,C)=( ( ),(e),( a, (b,c,d) ) )Aab的长度的长度(chngd)为为3，深度为，深度为3的长度的长度(chngd)为为2，深度为，深度为深度括号的重数深度括号的重数 结点的层数结点的层数第29页/共36页第三十页，共36页。31介绍两种特殊介绍两种特殊(tsh)(tsh)的基本操作：的基本操作：GetHead( L) GetHead( L) 取表头取表头( (可能是原子或列表可能是原子或列表););G

39、etTail(L ) GetTail(L ) 取表尾取表尾( (一定是列表一定是列表) ) 。广义表的抽象数据类型定义广义表的抽象数据类型定义(dngy)(dngy)见教材见教材P107-108P107-108第30页/共36页第三十一页，共36页。321. GetTail【(b, k, p, h)】 ; 2. GetHead【( (a,b), (c,d) )】 ; 3. GetTail【( (a,b), (c,d) )】 ; 4. GetTail【 GetHead【(a,b),(c,d)】 ;例：求下列例：求下列(xili)广义表操作的结果（严题集广义表操作的结果（严题集5.10）(k, p

40、, h)（b）(a,b)5. GetTail【（e）】 ; 6. GetHead 【 ( ( ) )】 .7. GetTail【 ( ( ) ) 】 .( )(a,b)( )( )(c,d)第31页/共36页第三十二页，共36页。33由于广义表的元素可以是不同结构（原子或列表），难以用顺序存由于广义表的元素可以是不同结构（原子或列表），难以用顺序存储结构表示储结构表示(biosh) (biosh) ，通常用链式结构，每个元素用一个结点表，通常用链式结构，每个元素用一个结点表示示(biosh)(biosh)。链式存储结构链式存储结构: :1.1.表头表头(bio tu)(bio tu)表尾链存储

41、结构表尾链存储结构 有两类结点：表结点和单元素结点。有两类结点：表结点和单元素结点。表结点 单元素结点tagtag标志域，标志域，0 0表示结点为单元素结点，表示结点为单元素结点，1 1表示为表结点；表示为表结点；hphp：表头指针域；：表头指针域； tptp：表尾指针域；：表尾指针域； datadata： 值域。值域。tag=1hptptag=0data标志域标志域 表头指针表头指针 表尾指针表尾指针指向子表指向子表指向下一结点指向下一结点第32页/共36页第三十三页，共36页。34 A =( ) 10e C =( a ,( b , c , d ) ) 1110a0b0d0c11例例： B=( e ) A=NULL1第33页/共36页第三十四页，共36页。35 E=(a, E) D=( A , B ,C )( ),(e),(a,(b,c,d) 0a1110e111110a0b0d0c111（参见（参见(cnjin)教教材材P109图）图）这种存储结构的特点是：最上层的表结点数即为广义表的长度(chngd)； 层次清楚；表结点数目多，与广义表中括号对的数目不匹配。 第34页/共36页第三十五页，共36页。tag =1hptptag =0atomtp第35页/共36页第三十六页，共36页。