数据结构第5章 数组和广义表.ppt

《数据结构第5章 数组和广义表.ppt》由会员分享，可在线阅读，更多相关《数据结构第5章 数组和广义表.ppt（66页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第 1 页第 2 页第五章第五章数组和广义表数组和广义表第五章第五章数组和广义表数组和广义表5.1数组的定义、运算数组的定义、运算5.2数组的顺序存储结构数组的顺序存储结构5.2矩阵的压缩存储矩阵的压缩存储5.3广义表广义表第 3 页前4章介绍的数据结构共同特点：（1）都属于线性数据结构；（2）每种数据结构中的数据元素，都作为原子数据，不再进行分解；本章讨论的两种数据结构：数组和广义表，其共同特点是：1）从逻辑结构上看它们，可看成是线性结构的一种扩展；2）数据元素本身也是一个数据结构；第五章第五章数组和广义表数组和广义表第 4 页5 51 1 数组的定义、运算数组的定义、运算一数组的概念 数组

2、是由一组个数固定，类型相同的数据元素组成阵列。以二维数组为例：二维数组中的每个元素都受两个线性关系的约束 即行关系和列关系，在每个关系中，每个元素aij都有且仅有一个直接前趋，都有且仅有一个直接后继。Amn=a00 a01 a0 n-1a10 a11 a1 n-1am-1 0 am-1 1 am-1 n-1在行关系中 aij直接前趋是 aij-1 aij直接后继是 aij+1在列关系中 aij直接前趋是 ai-1j aij直接后继是 ai+1j第 5 页5 51 1 数组的定义、运算数组的定义、运算二维数组也可看作这样的线性表：其每一个数据元素也是一个线性表A=（0,1 ,2,3,4,p)其中

3、每一个数据元素 j 是一个列向量的线性表j=（a0j,a1j ,a2j,a3j,am-1j)或 i 是一个行向量的线性表 i=（ai0 ,ai1 ,ai2,ai3,ain-1)第 6 页5 51 1 数组的定义、运算数组的定义、运算二、数组的基本操作1读元素操作2写元素操作操作方法根据其存储结构决定第 7 页5 52 2 数组的顺序存贮结构数组的顺序存贮结构 一维数组在内存中的存放很简单，只要顺序存放在连续的内存单元即可。二维数组，如何用顺序结构表示？内存地址是一维的，而数组是二维的，要将二维数组挤入一维的地址中，有两个策略：以行为主序（C语言使用）以列为主序a00 a01 a0n-1a10

4、a11 a1n-1am-10 am-11 am-1n-1第 8 页5 52 2 数组的顺序存贮结构数组的顺序存贮结构 设A是一个具有m 行n列的元素的二维数组:Amn=以行为主序的方式：a00 a01 a0n-1 a10 a11 a1n-1 am-11 am-1n-10 1 n-1 n n+1 2n-1 mn-1a00 a01 a0n-1a10 a11 a1n-1am-10 am-11 am-1n-1a00 a10 am-10 a01 a11 am-11 a0n-1 a1n-1 am-1n-10 1 m-1 m m+1 2m-1 nm-1以列为主序的方式：第 9 页5 52 2 数组的顺序存贮

5、结构数组的顺序存贮结构数组元素存储地址的计算数组元素存储地址的计算假设二维数组假设二维数组A每个元素占用每个元素占用s个存储单元，个存储单元，Loc(a aijij)为元素为元素a aijij的存储地址，的存储地址，Loc(a a0000)是是a a0000存储位置存储位置,也是二维数组也是二维数组A的基址的基址。若以行序为主序的方式存储二维数组，则元素若以行序为主序的方式存储二维数组，则元素a aijij的存储位置的存储位置可可由下式确定：由下式确定：Loc(a aijij)=Loc(a a0000)+（n i+j)s若以列序为主序的方式存储二维数组，则元素若以列序为主序的方式存储二维数组，

6、则元素a aijij的存储位置的存储位置可可由下式确定：由下式确定：Loc(a aijij)=Loc(a a0000)+（m j+i)s一般在程序设计过程中，一维数组和二维数组使用较普遍，超一般在程序设计过程中，一维数组和二维数组使用较普遍，超过二维以上的多维数组使用相对较少，对于高维数组的顺序存储方过二维以上的多维数组使用相对较少，对于高维数组的顺序存储方法，可以将二维的情形加以推广便能够得到。法，可以将二维的情形加以推广便能够得到。第 10 页5 53 3 矩阵的压缩存储矩阵的压缩存储5.3矩阵的压缩存储矩阵的压缩存储 一一 特殊矩阵的压缩存储特殊矩阵的压缩存储二二 稀疏矩阵的压缩存储稀疏

7、矩阵的压缩存储 1 1 三元组表的存储结构三元组表的存储结构 2 2 十字链表的存储结构十字链表的存储结构第 11 页5 53 3 矩阵的压缩存储矩阵的压缩存储 矩阵是许多科学与工程计算问题中常常涉及到的一种运算对象。一个m行n列的矩阵是一平面阵列，有mn个元素。可以对矩阵作加、减、乘等运算。只有少数程序设计语言提供了矩阵运算。通常程序员是用二维数组存储矩阵。由于这种存储方法可以随机地访问矩阵的每个元素，因而能较为容易地实现矩阵的各种运算。Amn =a00 a01 a0n-1a10 a11 a1n-1am-10 am-11 am-1n-1第 12 页 应用中常遇到一些阶数很高的矩阵，矩阵中有许

8、多值相同的元素或零元素。二维数组存储矩阵会浪费很多的存储单元。例如，设一个1000 1000的矩阵中有800个非零元素，若用二维数组存储需要106个存储单元。因此，需要使用高效的存储方法，减少数据的存储量，即对原矩阵，根据数据分布特征进行压缩存储。本章将讨论两类矩阵的压缩存储：1 特殊矩阵的压缩存储 2 稀疏矩阵的压缩存储5 53 3 矩阵的压缩存储矩阵的压缩存储Amn =a00 a01 a0n-1a10 a11 a1n-1am-10 am-11 am-1n-1第 13 页5 53 3 矩阵的压缩存储矩阵的压缩存储一 特殊矩阵值相同元素或者零元素分布有一定规律的矩阵称为特殊矩阵 例 对称矩阵、

9、上（下）三角矩阵都是特殊矩阵a00 a10 a20 an-10 a10 a11 a21an-10 an-11 an-1 n-1a00 a01 a0n-10 a11 a1n-10 0 0 an-1 n-1第 14 页5 53 3 矩阵的压缩存储矩阵的压缩存储 特殊矩阵压缩存储 (以对称矩阵为例)对称矩阵是满足下面条件的n 阶矩阵:aij=aji 0 i,j n-1 a00 a01 a0n-1a10 a11 a1n-1an-10 an-11 an-1n-1对称矩阵元素可以只存储下三角部分，共需 n(n+1)/2 个单元的空间(三角矩阵的存储方式类似）a00 a10 a11 a20 a21 a22

10、an-10 an-11 an-1n-1a00 a10 a11 a20 a21 a22 an-10 an-11 an-1n-1k=0 1 2 3 4 5 n(n+1)/2-1 第 15 页5 53 3 矩阵的压缩存储矩阵的压缩存储k=i(i+1)/2 +j 当 i jj(j+1)/2 +i 当 i j 以一维数组sa 作为n 阶对称矩阵A的存储结构，A中任意一元素 aij与它的存储位置 sak 之间存在着如下对应关系：a00 a10 a11 a20 a21 a22 an-10 an-11 an-1n-1k=0 1 2 3 4 5 n(n+1)/2-1 例如，a a53 53 在 sa 中的存储位

11、置是：k=5*(5+1)/2+3=18 sa18=a a5353第 16 页5 53 3 矩阵的压缩存储矩阵的压缩存储 压缩存储的对称矩阵的取值算法压缩存储的对称矩阵的取值算法intget_M(inti,intj)if(i=j)return(sai*(i+1)/2+j)elsereturn(saj*(j+1)/2+i);压缩存储的对称矩阵的压缩存储的对称矩阵的赋值算法赋值算法voidassign_M(inti,intj,intvalue)if(i=j)sai*(i+1)/2+j=value;elsesaj*(j+1)/2+i=value;第 17 页5 53 3 矩阵的压缩存储矩阵的压缩存储

12、带状矩阵带状矩阵 所有非0元素都集中在以主对角线为中心的带状区域，半带宽为d时,非0元素有(2d+1)*n-(1+d)*d个a a00 00 a a01 01 a a 02 02 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 a a10 10 a a11 11 a a12 12 a a13 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0a a20 20 a a21 21 a a22 22 a a23 23 a a24 24 0 0 00 0 0 0 0 0 0 0 0 0 00 0 a a31 31 a a32 32 a a33 33 a a34

13、 34 a a35 35 0 00 0 0 0 0 0 0 0 0 00 0 0 0 a a42 42 a a43 43 a a44 44 a a45 45 a a46 46 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 a a53 53 a a54 54 a a55 55 a a56 56 a a57 57 0 00 0 0 0 0 0 0 0 0 0 0 00 0 a a64 64 a a65 65 a a66 66 a a67 67 a a68 68 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 a a75 75 a a76 76 a a77 77 a a

14、78 78 a a79 79 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 a a86 86 a a87 87 a a88 88 a a89 89 a a810810 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 a a9797 a a98 98 a a99 99 a a910 910 a a9119110 00 0 0 0 0 0 0 0 0 0 0 0 0 0 a a108 108 a a109 109 a a1010 1010 a a1011 1011 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 a a119 119 a a111

15、0 1110 a a11111111d第 18 页5 53 3 矩阵的压缩存储矩阵的压缩存储0 a a0000 a a0101 a a1010 a a11 11 a a12 12 a a21 21 a a22 22 a a23 23 a a32 32 a a33 33 a a34 34 a a43 43 a a44 44 0 0K=0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 a 00 a01 0 0 0 a10 a11 a12 0 0 0 a21 a22 a23 00 0 a32 a33 a340 0 0 a43 a44 为计算方便，认为每一行都有2d+1个非0元素，

16、若少则用0补足，所以，存放矩阵的数组sa 有 n(2d+1)个元素 数组元素sak与矩阵元素aij 之间有关系 k=i*(2d+1)+d+(j-i)a00前为何放一个0？你会放d=2,n=6的带状矩阵吗？第 19 页5 53 3 矩阵的压缩存储矩阵的压缩存储 压缩存储的带状矩阵的取值算法压缩存储的带状矩阵的取值算法intget_Md(inti,intj)if(abs(i-j)=d）return(sai*(2*d+1)+d+(j-i)；elsereturn(0);压缩存储的压缩存储的带状矩阵的带状矩阵的赋值算法赋值算法voidassign_Md(inti,intj,intvalue)if(abs

17、(i-j)=d）sai*(i+1)/2+j=value;第 20 页5 53 3 矩阵的压缩存储矩阵的压缩存储二稀疏矩阵 1 什么是稀疏矩阵 有较多值相同元素或较多零元素，且值相同元素或者零元素分布没有一定规律的矩阵称为稀疏矩阵。例A =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 0A有42（67）个元素有8个非零元素如何进行稀疏矩阵的压缩存储？第 21 页5 53 3 矩阵的压缩存储矩阵的压缩存储2 稀疏矩阵的压缩存储（只讨论有较多零元素矩阵的压缩存储）1）三元组表

18、（i,j,aij)A=(0,1,12),(0,2,9),(2,0,-3),(2,5,14),(3,2,24),(4,1,18),(5,0,15),(5,3,-7)加上行、列数6，7 A =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 0表示非零元的三元组第 22 页5 53 3 矩阵的压缩存储矩阵的压缩存储2）三元组顺序表 假设以顺序存储结构来表示三元组表，则可得稀疏矩阵的一种压缩存储方式我们称之为三元组顺序表。稀疏矩阵的三元组顺序表的类型定义structnodeint

19、row,col;/非零元的行下标和列下标 intvalue;/非零元值;typedefstructnodeNODE;NODEmaMAX；ma0用于存储矩阵行数、列数、非零元个数用于存储非零元三元组的结构第 23 页5 53 3 矩阵的压缩存储矩阵的压缩存储 A的三元组顺序表图示 A=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 0row col value0123456782 0 -32 0 -35 0 155 0 150 1 120 1 124 1 184 1 180

20、 2 90 2 93 2 243 2 245 3 -75 3 -72 5 142 5 146 7 86 7 8例如 ma1.row=0,ma1.col=1,ma1.value=12第 24 页5 53 3 矩阵的压缩存储矩阵的压缩存储 3)转置运算算法 转置运算是一种最常用的矩阵运算。对于一个 m 行 n 列的矩阵 A，它的转置矩阵 B是一个n行m列的矩阵。例如，下图中的矩阵A和B互为转置矩阵。A=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 0 B=0 0-3 0 0

21、 1512 0 0 0 18 0 9 0 0 24 0 0 0 0 0 0 0-7 0 0 0 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0 第 25 页5 53 3 矩阵的压缩存储矩阵的压缩存储 A第第0 0 列列第一列第一列 第二列第二列第三列第三列 第四列第四列第五列第五列 第六列第六列.B B第第0 0 行行第一行第一行 第二行第二行第三行第三行 第四行第四行第五行第五行 第六行第六行.转置运算算法第 26 页5 53 3 矩阵的压缩存储矩阵的压缩存储矩阵 B矩阵 Arow col value0123456782 0 -32 0 -35 0 155 0 150 1 12

22、0 1 124 1 184 1 180 2 90 2 93 2 243 2 245 3 -75 3 -72 5 142 5 146 7 86 7 8row colv alue 0123456781 0 121 0 123 5 -73 5 -70 2 -30 2 -32 3 242 3 240 5 150 5 152 0 92 0 95 2 145 2 141 4 181 4 187 6 87 6 8分析：分析：（1 1）将矩阵的行列数的）将矩阵的行列数的值交换值交换（2 2）将每一个三元组的将每一个三元组的i i 和和 j j相互调换相互调换（3 3）重排三元组之间的）重排三元组之间的次序次序

23、第 27 页5 53 3 矩阵的压缩存储矩阵的压缩存储转置运算算法按照A的列序来进行转换的基本思想 对 ma 从头至尾扫描：第一次扫描时，将 ma 中列号为0的所有元组交换行列值后，依次赋值到 mb 中 第二次扫描时，将 ma 中列号为1的所有元组交换行列值后，依次赋值到 mb 中 依此类推，直至将 ma 的所有三元组赋值到 mb 中第 28 页i j v0 1 120 2 92 0 -32 5 143 2 244 1 185 0 155 3 -7i j v2 0 -31 4 180 2 -35 0 150 5 150 1 121 0 124 1 180 2 92 0 93 2 242 3 2

24、45 3 -73 5 -72 5 145 2 14A矩阵B矩阵对A六次扫描完成转置运算第一次扫描查找第一次扫描查找第第0 0列元素列元素第一次扫第一次扫描结束描结束第二次扫第二次扫描结束描结束第二次扫描查找第二次扫描查找第第1 1列元素列元素5 53 3 矩阵的压缩存储矩阵的压缩存储第三次扫描查找第三次扫描查找第第2 2列元素列元素第四次扫描查找第四次扫描查找第第3 3列元素列元素第五次扫描查找第五次扫描查找第第4 4列元素列元素第六次扫描查找第六次扫描查找第第5 5列元素列元素转置运算算法图示0123456786 7 87 6 8第 29 页5 53 3 矩阵的压缩存储矩阵的压缩存储转置算法

25、:采用三元组表存储表示，求稀疏矩阵A的转置矩阵Bint transpose(NODE ma,NODE mb)int i,j,k;if(ma0.value=0)return(0);mb0.row=ma0.col;mb0.col=ma0.row;mb0.value=ma0.value;k=1;/k为当前三元组在mb 存储位置(下标)for(i=0;ima0.col;i+)/找 ma 中第 i 列所有非0元素 for(j=1;j=ma0.value;j+)/j为扫描ma 的“指示器”/j“指向”三元组称为当前三元组 if(maj.col=i)mbk.row=maj.col;mbk.col=maj.r

26、ow;mbk.value=maj.value;k+;return(1);算法5.7第 30 页5 53 3 矩阵的压缩存储矩阵的压缩存储时间复杂度分析 算法的基本操作为将 ma 中的三元组赋值到 mb，是在两个循环中完成的，故算法的时间复杂度为 O(n t),其中n 为A矩阵的列数,t为非0元素个数。当非零元的个数t 和矩阵元素个数mn 同数量级时，即 tm n，转置运算算法的时间复杂度为O（n n m m n）。由此可见：在这种情况下，用三元组顺序表存储矩阵，虽然可能节省了存储空间，但时间复杂度提高了，因此算法仅适于 t m m n n 的情况。该算法效率不高的原因是：对为实现 A 到 B

27、的转置，该算法对 ma 进行了多次扫描。其特点是：以B矩阵的三元组为中心，在 A 矩阵的三元组中通盘查找合适的结点置入 mbk 中 能否在对 ma 一次扫描的过程中，完成 A 到 B 的转置？第 31 页5 53 3 矩阵的压缩存储矩阵的压缩存储下面介绍的转置运算算法称为 快速转置算法快速转置算法 方法是：以A矩阵的三元组为中心,依次取出 ma 中的每一个三元组，交换行列后，直接将其写入mb 合适的位置中 A=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 0如果能先求得

28、A各列第一个非零元三元组在 mb 中的位置就能在对ma 一次扫描的过程中，完成A到B 的转置row col value2 0 -35 0 150 1 124 1 180 2 93 2 245 3 -72 5 146 7 8row col value 0123456781 0 123 5 -70 2 -32 3 240 5 152 0 95 2 141 4 187 6 8第 32 页5 53 3 矩阵的压缩存储矩阵的压缩存储i j vma i j v012345678 7 6 82 3 240 5 152 0 95 2 141 4 18 mb 各列第一个非零元三元组按先前求出的位置，放至mb 中

29、各列后续的非零元三元组，顺序放到对应列元素的后面0 2 -30123456782 0 -35 0 156 7 84 1 180 2 93 2 245 3 -72 5 140 1 121 0 123 5 -7第 33 页5 53 3 矩阵的压缩存储矩阵的压缩存储引入辅助数组 num、pos numcol：存储 A 矩阵第 col 列非零元个数 poscol：存储第 col 列第一个非零元三元组在 mb 中的位置 例 矩阵 Acolnumcolposcol0 1 2 3 4 5 622811001352784539poscol的计算方法：pos0=1posj=posj-1+numj-11 j n-

30、1第 34 页5 53 3 矩阵的压缩存储矩阵的压缩存储快速转置算法主要步骤：1 求 A 中各列非零元个数num;2 求 A 中各列第一个非零元在 mb 中的下标 pos;3 对 ma 进行一次扫描，遇到 col 列的第一个非零元三元组时，按poscol 的位置，将其放至 mb 中，当再次遇到 col 列的非零元三元组时，只须顺序放到 col 列元素的后面;第 35 页colnumcolposcol0 1 2 3 4 5 6228110013527890 1 120 2 92 0 -32 5 143 2 244 1 185 0 155 3 -7i j vi j vA 矩阵0 1 121 0 1

31、2第1列第一个非零元在mb中的位置0 2 9第2列第一个非零元在mb中的位置2 0 92 0 -30 2 -32 5 145 2 143 2 242 3 244 1 181 4 185 0 150 5 155 3 -73 5 -74第1列第二个非零元在mb中的位置65快速转置算法图示第3列第一个非零元在mb中的位置第0列第一个非零元在mb中的位置2793第5 列第一个非零元在mb中的位置求各列第1个非零元在mb中位置求各列非零元个数扫描ma 实现A到B 的转置5 53 3 矩阵的压缩存储矩阵的压缩存储B 矩阵12345678第 36 页5 53 3 矩阵的压缩存储矩阵的压缩存储快速转置算法快速

32、转置算法int transpose1(NODE ma,NODE mb )int i,j,k,numMAX,posMAX;if(ma0.value=0)return(0);mb0.row=ma0.col;mb0.col=ma0.row;mb0.value=ma0.value;for(i=0;ima0.col;i+)numi=0;for(i=1;i=ma0.value;i+)nummai.col+;/统计第i 列非0元个数 for(pos0=1,i=1;ima0.col;i+)posi=posi-1+numi-1;/计算 pos 数组 for(i=1;irow,&head-(%d,%d,%dn,&

33、head-row,&head-colcol,&head-,&head-valval););row col valdown right 445head第 42 页5 53 3 矩阵的压缩存储矩阵的压缩存储for(pre=head,i=0;irow;i+)for(pre=head,i=0;irow;i+)p=(NODE*)p=(NODE*)mallocmalloc(sizeofsizeof(NODE);(NODE);p-p-valval=p-row=p-=p-row=p-colcol=0;=0;p-right=p;pre-down=p;pre=p;p-right=p;pre-down=p;pre=

34、p;p-down=head;p-down=head;4 4 54 4 5head0 0 00 0 00 0 00 0 0for(pre=head,i=0;icol;i+)p=(NODE*)malloc(sizeof(NODE);p-val=p-row=p-col=0;p-down=p;pre-right=p;pre=p;p-right=head;第 43 页5 53 3 矩阵的压缩存储矩阵的压缩存储4 4 54 4 5head0 0 00 0 00 0 00 0 00 0 00 0 00 0 00 0 01 1 -11 1 -1newrow_pcol_p第 44 页5 53 3 矩阵的压缩存储

35、矩阵的压缩存储count=0;while(countval)count+;new=(NODE*)malloc(sizeof(NODE);scanf(%d,%d,%dn,&new-row,&new-col,&new-val);for(row_p=head,i=0;irow;i+)row_p=row_p-down;p=row_p;while(p-right!=row_p&p-right-colcol)p=p-right;new-right=p-right;p-right=new;第 45 页5 53 3 矩阵的压缩存储矩阵的压缩存储for(col_p=head,i=0;icol;i+)col_p=

36、col_p-right;p=col_p;while(p-down!=col_p&p-down-rowrow)p=p-down;new-down=p-down;p-down=new;return(head);第 46 页5 53 3 矩阵的压缩存储矩阵的压缩存储A A=3 23 2 0 0 5 5 0 0 -1-1 0 00 0 2 2 0 0 00 0 0 0 0 0 00 0 0 04 4 54 4 50 0 00 0 00 0 00 0 00 3 50 3 50 1 20 1 20 0 30 0 30 0 00 0 00 0 00 0 02 0 22 0 21 1-11 1-1head第

37、47 页 小 结 1 矩阵压缩存储是指为多个值相同的元素分配一个 存储空间，对零元素不分配存储空间；2 特殊矩阵的压缩存储是根据元素的分布规律，确定 元素的存储位置与元素在矩阵中的位置的对应关系；3 稀疏矩阵的压缩存储除了要保存非零元素的值外，还 要保存非零元素在矩阵中的位置；5 53 3 矩阵的压缩存储矩阵的压缩存储第 48 页习题习题5（P62P62）5.1 5.1，5.2 5.2，5.3 5.3预习预习 ：广义表广义表 第五章第五章习习题与预习题与预习第 49 页54广义表广义表5.4广义表5.3.1广义表的概念5.3.2广义表的存储结构5.3.2广义表的基本操作第 50 页5.4.1广

38、义表的概念广义表的概念1什么是广义表什么是广义表广义表也称为列表，是线性表的一种扩展，也是数据元素的有限序列。记作：LS=(d0,d1,d2,.dn-1)。其中di既可以是单个元素，也可以是广义表。说明 1）广义表的定义是一个递归定义，因为在描述广义表时又用到了广义表；2）在线性表中数据元素是单个元素，而在广义表中，元素可以是单个元素,称为单元素(原子)，也可以是广义表，称为广义表的子表；3）n 是广义表长度；54广义表广义表第 51 页54广义表广义表4）下面是一些广义表的例子；A=()空表，表长为0；B=(a,(b,c,d)B的表长为2，两个元素分别为 a 和子表（b,c,d)；C=(e)

39、C中只有一个元素e，表长为1；D=(A,B,C,f)D 的表长为4，它的前三个元素 A，B，C 广义表,第四个 是单元素；E=(a,E)递归表.第 52 页54广义表广义表5）若广义表不空，则可分成表头和表尾，反之，一对表头和表尾可唯一确定广义表 对非空广义表：称第一个元素为L的表头，其余元素组成的表称为LS的表尾；B=(a,(b,c,d)表头：a 表尾(b,c,d)即 HEAD（B）=a,TAIL(B)=(b,c,d),C=(e)表头：e 表尾()D=(A,B,C,f)表头：A 表尾(B,C,f)运算可以嵌套，如：HEAD（TAIL（B）=b,TAIL(TAIL(B)=(c,d)。第 53

40、页54广义表广义表广义表的元素之间除了存在次序关系外，还存在层次关系。如：DABCfaDebcd第 54 页2广义表的基本操作广义表的基本操作 1）创建广义表L；2）销毁广义表L；3）已有广义表L，由L复制得到广义表T；4）求广义表L的长度；5）求广义表L的深度；6）判广义表L是否为空；7）取广义表L的表头；8）取广义表L的表尾；9）在L中插入元素作为L的第i个元素；10）删除广义表L的第i个元素；11）遍历广义表L，用函数 traverse()处理每个元素；54广义表广义表第 55 页5.4.2广义表的存储结构广义表的存储结构 由于广义表中数据元素可以具有不同结构，故难以用顺序结构表示广义表

41、。通常采用链表存储方式 如何设定链表结点？广义表中的数据元素可能为单元素(原子)或子表，由此需要两种结点：一种是表结点，用以表示广义表；一种是单元素结点，用以表示单元素（原子）。54广义表广义表tag chil next表结点1 0 tag val next单元素结点第 56 页54广义表广义表链表结点的类型定义如下：structnodeinttag;/标志域：用于区分原子结点和表结点标志域：用于区分原子结点和表结点unionintval;/原子结点的值域原子结点的值域structnode*child;/表结点的子表指针域，表结点的子表指针域，content;structnode*next;/

42、指向下一个元素的指针指向下一个元素的指针;typedefstructnodeNODE;第 57 页广义表的存储结构示例54广义表广义表A=（）,B=(a,(b,c,d)C=(e),D=(A,B,C,f)E=(a,E)1A1C0e0B110 c0aD110bd101fE110 a0B110 c0aD110bd101f第 58 页54广义表广义表5.3.4广义表的基本操作的递归算法广义表的基本操作的递归算法 广义表是递归结构，所以广义表的许多操作可以用递归算法实现，1求广义表的深度 int depth(NODE*head)广义表 L=(1,2。n)的深度=广义表中括号重数例 A=（）B=(e)C=

43、(a,(b,c,d)D=(A,B,C)depth(A)=1 depth(B)=1 depth(C)=2 depth(D)=3 广义表的深度=1+MAX(depth(i)第 59 页54广义表广义表depth(i)的递归定义：基本项：L 为空表，depth(i)=1 L 为原子结点指针，depth(i)=0 递归项：i 为非空表，depth(L)=1+MAX(depth(i)L110a0b0c0dL=(a,(b,c,d)第 60 页54广义表广义表求广义表L的深度。int depth(NODE*head)NODE *p;int max,deth1;p=head;max=0;/空表深度为1 whi

44、le(p!=NULL)if(p-tag=0)depth1=0;/原子深度为原子深度为0elsedepth1=depth(p-content.child);/求以求以p-content.childif(depth1max)max=depth1;/为头指针的子表深度为头指针的子表深度p=p-next;return(max+1);/非空表的深度是各元素的深度的最大值加1 第 61 页54广义表广义表建立广义表算法建立广义表算法NODE*create()NODE*p;charch;ch=stri;i+;switch(ch)case(:p=(NODE*)malloc(sizeof(NODE);p-tag

45、=1;p-content.child=create();p-next=create();break;第 62 页54广义表广义表casea:caseb:casec:cased:casee:p=(NODE*)malloc(sizeof(NODE);p-tag=0;p-content.val=ch;p-next=create();break;case,:p=create();break;case):case0:p=NULL;return(p);第 63 页54广义表广义表遍历广义表算法遍历广义表算法voidtraverse(NODE*head)NODE*p;for(p=head;p!=NULL;p=p-next)if(p-tag=1)printf();traverse(p-content.child);printf(b),);elseprintf(%c,p-content.val);第 64 页5广义表广义表 小 结 1 广义表是数据元素的有限序列。其数据元素 可以单个元素，也可以是广义表；2 广义表，通常采用链式存储结构3 分解非空广义表的方法：将非空广义表分解为表头和表尾两部分；第 65 页 P62 5.4,5.5,5.6 第五章第五章习习题题第 66 页