字符串及线性结构的扩展课件.ppt

1、2023-4-26数据结构讲义1第4章 字符串及线性结构的扩展 教学内容：4.1 字符串 4.2 数组 4.3 广义表教学目的：(1)了解串、数组、广义表几中特殊的线形表的定义；(2)理解和领会串的存储方式和掌握常用的串运算；(3)理解多维数组的结构特点和在内存中的两种顺序存储方式；(4)领会稀疏矩阵的压缩方式和简单运算。2023-4-26数据结构讲义2 教学重点：(1)串和数组的逻辑结构、基本运算 (2)串的两种存储方式 (3)串的模式匹配算法 (4)多维数组的两种顺序存储方式 (5)对称矩阵、三角矩阵的压缩存储方式 (6)稀疏矩阵的三元组表表示方法教学难点：(1)串的模式匹配 (2)串的综

2、合应用 (3)稀疏矩阵压缩存储表示下的运算实现学时安排：4学时2023-4-26数据结构讲义34.1 字符串4.1.1 字符串的基本概念4.1.2 顺序串4.1.3 模式匹配2023-4-26数据结构讲义44.1.1 字符串的基本概念 字符串(简称为串)是数据元素为字符的线性表，它的是由零个或多个任意字符组成的字符序列。一般记作：s=”s1 s2 sn”。其中s 是串名；在本书中，用双引号作为串的定界符，引号引起来的字符序列为串值，引号本身不属于串的内容；si(1=iMAXSIZE1)return 0;/*MAXSIZE为 s长度,不够长时*/i=0;while(s1i!=0)si=s1i;i

3、+;j=0;while(s2j!=0)si=s2j;i+;j+;si=0;/*置串结束标志*/return 1;/*连接成功*/2023-4-26数据结构讲义12(3)求子串【算法 4-3】求子串算法int StrSub(char*t,char*s,int i,int len)/*用t返回串s中第i个字符开始的长度为len 的子串1i串长*/int slen;slen=StrLength(s);if(islen|lenslen-i+1)printf(参数不对n);return 0;for(j=0;js2返回大于0的数否则返回小于0的数*/int i=0;while(s1i=s2i&s1i!=0

4、)i+;return(s1i-s2i);许多程序设计语言为用户提供了大量的字符串函数，如在C语言中的“string.h”库中提供了若干处理字符串的函数，通过这些函数用户很方便的构架字符串的操作，故不再这里赘述。2023-4-26数据结构讲义144.1.3 模式匹配 串的模式匹配即子串定位是一种重要的串运算。设s和t是给定的两个串，在主串s中查找子串t的过程称为模式匹配，如果在s中找到等于t的子串，则称匹配成功，函数返回t在s中的首次出现的存储位置(或序号)，否则匹配失败，返回0。t也称为模式。为了运算方便，设字符串采用定长存储，且用第3种方式表示串长，即串的长度存放在0号单元，串值从1号单元存

5、放，这样字符序号与存储位置一致。2023-4-26数据结构讲义15 算法思想如下：首先将s1与t1进行比较，若不同，就将s2与t1进行比较，.，直到s的某一个字符si和t1相同，再将它们之后的字符进行比较，若也相同，则如此继续往下比较，当s的某一个字符si与t的字符tj不同时，则s返回到本趟开始字符的下一个字符，即si-j+2，t返回到t1，继续开始下一趟的比较，重复上述过程。若t中的字符全部比完，则说明本趟匹配成功，本趟的起始位置是i-j+1或i-t0，否则，匹配失败。设主串s=acabaabaabcacaabc，模式t=abaabcac，匹配过程如图所示。2023-4-26数据结构讲义16

6、【算法 4-5】简单模式匹配算法int StrIndex_BF(char s,char t)/*从串s的第一个字符开始找第一个与串t相等的子串*/int i=1,j=1;while(i=s0&jt0)return(i-t0);/*匹配成功，返回存储位置*/else return 0;2023-4-26数据结构讲义17 下面分析它的时间复杂度，设串s长度为n，串t长度为m。匹配成功的情况下，考虑两种极端情况：在最好情况下，每趟不成功的匹配都发生在第一对字符比较时：例如：s=”aaaaaaaaaabc”，t=”bc”设匹配成功发生在si处，则字符比较次数在前面i-1趟匹配中共比较了i-1次，第i趟

7、成功的匹配共比较了m次，所以总共比较了i-1+m次，所有匹配成功的可能共有n-m+1种，设从si开始与t串匹配成功的概率为pi，等概率情况下pi=1/(n-m+1)，因此最好情况下平均比较的次数是：即最好情况下的时间复杂度是O(n+m)。2023-4-26数据结构讲义18 在最坏情况下，每趟不成功的匹配都发生在t的最后一个字符：例如：s=”aaaaaaaaaaab”，t=”aaab”设匹配成功发生在si处，则在前面i-1趟匹配中共比较了(i-1)*m次，第i趟成功的匹配共比较了m次，所以总共比较了i*m次，因此最坏情况下平均比较的次数是：即最坏情况下的时间复杂度是O(n*m)。2023-4-2

8、6数据结构讲义19 上述算法中匹配是从s串的第一个字符开始的，有时算法要求从指定位置开始，这时算法的参数表中要加一个位置参数pos：StrIndex(shar*s,int pos,char*t)，比较的初始位置定位在pos处。算法4-5是pos=1的情况。2023-4-26数据结构讲义20 4.2 数组 4.2.1 数组的逻辑结构及内存映象 4.2.2 特殊矩阵 4.2.3 稀疏矩阵2023-4-26数据结构讲义214.2.1 数组的逻辑结构及内存映像 数组是我们熟悉的一种数据结构。数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型，比如：一维数组可以看作

9、一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，三维数组可以看作“数据元素是二维数组”的一维数组，依此类推，所以可以看作是线性表的推广。2023-4-26数据结构讲义221数组的逻辑结构 数组是一个具有固定格式和数量的数据有序集，每一个数据元素有唯一的一组下标来标识。在数组上不能做插入、删除数据元素的操作。通常在各种高级语言中数组一旦被定义，每一维的大小及上下界都不能改变。在数组中通常做下面两种操作：(1)取值操作：给定一组下标，读其对应的数据元素。(2)赋值操作：给定一组下标，存储或修改与其相对应的数据元素。我们着重研究二维和三维数组，因为它们的应用是广泛的，尤其是二维数组。2

10、023-4-26数据结构讲义23 2 数组的内存映象 通常，数组在内存被映象为向量，这是因为内存的地址空间是一维的，数组的行列固定后，通过一个映象函数，则可根据数组元素的下标得到它的存储地址。对于一维数组按下标顺序分配即可。对多维数组分配时，要把它的元素映象存储在一维存储器中，一般有两种存储方式：一是以行为主序（或先行后列）的顺序存放，如BASIC、PASCAL、COBOL、C等程序设计语言中用的是以行为主的顺序分配，即一行分配完了接着分配下一行。另一种是以列为主序（先列后行）的顺序存放，如FORTRAN语言中，用的是以列为主序的分配顺序，即一列一列地分配。2023-4-26数据结构讲义24

11、以行为主序的分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变，从右向左，最后是左下标。以列为主序分配的规律恰好相反：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变，从左向右，最后是右下标。2023-4-26数据结构讲义25 设二维数组Amn，按元素的下标求其地址的计算：以“以行为主序”的分配为例：设数组的基址为LOC(a11)，每个数组元素占据l个地址单元，那么aij 的物理地址可用一线性寻址函数计算：LOC(aij)=LOC(a11)+(i-1)*n+j-1)*l 在C语言中，数组中每一维的下界定义为0，则：LOC(aij)=LOC(

12、a00)+(i*n+j)*l 推广到一般的二维数组：Ac1.d1 c2.d2，则aij的物理地址计算函数为：LOC(aij)=LOC(a c1 c2)+(i-c1)*(d2-c2+1)+(j-c2)*l2023-4-26数据结构讲义26 同理对于三维数组Amnp，即mnp数组，对于数组元素aijk其物理地址为：LOC(aijk)=LOC(a111)+(i-1)*n*p+(j-1)*p+k-1)*l 推广到一般的三维数组：Ac1.d1 c2.d2 c3.d3，则aijk的物理地址为：LOC(i,j)=LOC(a c1 c2 c3)+(i-c1)*(d2-c2+1)*(d3-c3+1)+(j-c2

13、)*(d3-c3+1)+(k-c3)*l2023-4-26数据结构讲义27三维数组的逻辑结构和以行为主序的分配示意图如图所示。2023-4-26数据结构讲义28例4-1 若矩阵Amn 中存在某个元素aij满足：aij是第i行中最小值且是第j列中的最大值，则称该元素为矩阵A的一个鞍点。试编写一个算法，找出A中的所有鞍点。实现的基本思想：在矩阵A中求出每一行的最小值元素，然后判断该元素它是否是它所在列中的最大值，是则打印出，接着处理下一行。矩阵A用一个二维数组表示。2023-4-26数据结构讲义29【算法4-8】求矩阵鞍点#define M/*矩阵的行*/#define N/*矩阵的列*/void

14、 saddle(int A N)int i,j,k,p,min;for(i=0;iM;i+)/*按行处理*/min=Ai0;for(j=1;jN;j+)if(Aijmin)min=Aij;/*找第i行最小*/for(j=0;jN;j+)/*检测该行中的每一个最小值是否是鞍点*/if(Aij=min)k=j;p=0;while(pM&Apj=M)printf(%d,%d,%dn,i,k,min);对任意mn的矩阵，算法的时间性能为O(m(n+mn)。2023-4-26数据结构讲义304.2.2 特殊矩阵 对于一个矩阵结构显然用一个二维数组来表示是非常恰当的，但在有些情况下，比如常见的一些特殊矩阵

15、，如三角矩阵、对称矩阵、带状矩阵、稀疏矩阵等，从节约存储空间的角度考虑，这种存储是不太合适的。下面从这一角度来考虑这些特殊矩阵的存储方法。2023-4-26数据结构讲义311.对称矩阵对称矩阵的特点是：在一个n阶方阵中，有aij=aji，其中1i,jn2023-4-26数据结构讲义32 对称矩阵关于主对角线对称，因此只需存储上三角或下三角部分即可。比如，只存储下三角中的元素aij，其特点是中ji且1in，对于上三角中的元素aij，它和对应的aji相等，因此当访问的元素在上三角时，直接去访问和它对应的下三角元素即可，这样，原来需要n*n个存储单元，现在只需要n(n+1)/2个存储单元了，节约了n

16、(n-1)/2个存储单元，当n较大时，这是可观的一部分存储资源。2023-4-26数据结构讲义33 如何只存储下三角部分？对下三角部分,以行为主序顺序存储到一个向量中去，在下三角中共有n*(n+1)/2个元素，因此，不失一般性，设存储到向量SAn(n+1)/2中，存储顺序可用下图示意，这样，原矩阵下三角中的某一个元素aij则具体对应一个sak，下面的问题是要找到k与i、j之间的关系。2023-4-26数据结构讲义34 在上面的排列顺序中，aij是第i*(i-1)/2+j个元素，因此它在SA中的下标k与i、j的关系为：k=i*(i-1)/2+j-1 (kn*(n+1)/2)当访问的元素在上三角中

17、时(ij)，因为aij=aji，因此访问和它对应的aji即可，因此将上式中的行列下标交换就是上三角中的元素aij在SA中的对应关系：k=j*(j-1)/2+i-1 (kn*(n+1)/2)综上所述，对于对称矩阵中的任意元素aij，若令I=max(i,j)，J=min(i,j)，则将上面两个式子综合起来得到：k=I*(I-1)/2+J-12023-4-26数据结构讲义35 2.三角矩阵 形如下图的矩阵称为三角矩阵，其中c为某个常数。其中(a)为下三角矩阵：主对角线以上均为同一个常数；(b)为上三角矩阵，主对角线以下均为同一个常数；下面讨论它们的压缩存储方法。2023-4-26数据结构讲义36(1

18、)下三角矩阵 与对称矩阵类似，不同之处在于存完下三角中的元素之后，紧接着存储对角线上方的常量，因为是同一个常数，所以存一个即可，这样一共存储了n*(n+1)+1个元素，设存入向量：SAn*(n+1)+1中，这种的存储方式可节约n*(n-1)-1个存储单元，sak 与aji 的对应关系为：2023-4-26数据结构讲义37(2)上三角矩阵 对于上三角矩阵，存储思想与下三角类似，以行为主序顺序存储上三角部分，最后存储对角线下方的常量。对于第1行，存储n个元素，第2行存储n-1个元素，第p行存储(n-p+1)个元素，aij的前面有i-1行，共存储：个元素，aij 是它所在的行中要存储的第（j-i+1

19、）个也就是上三角存储顺序中的第(i-1)*(2n-i+2)/2+(j-i+1)个，因此它在SA中的下标为：k=(i-1)*(2n-i+2)/2+j-i。综上，sak 与aji 的对应关系为：2023-4-26数据结构讲义38 3.带状矩阵 n阶矩阵A称为带状矩阵，如果存在最小正数m，满足当 i-j m 时，aij=0，这时称w=2m-1为矩阵A的带宽。下图是一个w=3(m=2)的带状矩阵。带状矩阵也称为对角矩阵。由下图可看出，在这种矩阵中，所有非零元素都集中在以主对角线为中心的带状区域中，即除了主对角线和它的上下方若干条对角线的元素外，所有其他元素都为零(或同一个常数c)。2023-4-26数

20、据结构讲义39 一种压缩方法是将A压缩到一个n行w列的二维数组B中，如下图所示，当某行非零元素的个数小于带宽w时，先存放非零元素后补零。那么aij 映射为b ij，映射关系为：2023-4-26数据结构讲义40 另一种压缩方法是将带状矩阵压缩到向量C中去，按以行为主序，顺序的存储其非零元素，如下图所示，按其压缩规律，找到相应的映象函数。如当w=3时，映象函数为：k=2*i+j-32023-4-26数据结构讲义414.2.3 稀疏矩阵 设m*n矩阵中有t个非零元素且tmu=Anu;Bnu=Amu;Btu=Atu;/*行、列、元素个数*/if(Btu0)q=1;for(col=1;colnu);c

21、ol+)/*按A的列序转换*/for(p=1;ptu);p+)/*扫描整个三元组表*/if(Adatap.j=col)Bdataq.i=Adatap.j;Bdataq.j=Adatap.i;Bdataq.v=Adatap.v;q+;return B;/*返回的是矩阵B的指针*/2023-4-26数据结构讲义47算法分析：其时间主要耗费在col和p的二重循环上，所以时间复杂性为O(n*t)，(设m、n是原矩阵的行、列，t是稀疏矩阵的非零元素个数)。显然当非零元素的个数t和m*n同数量级时，算法的时间复杂度为O(m*n2)，和通常存储方式下矩阵转置算法相比，可能节约了一定量的存储空间，但算法的时间

22、性能更差一些。2023-4-26数据结构讲义48转置算法的改进：上述算法效率低的原因是算法要从A的三元组表中寻找第一列、第二列、，要反复搜索A表，若能直接确定A中每一三元组在B中的位置，则对A的三元组表扫描一次即可。这是可以做到的，因为A中第一列的第一个非零元素一定存储在B.data1，如果还知道第一列的非零元素的个数，那么第二列的第一个非零元素在B.data中的位置便等于第一列的第一个非零元素在B.data中的位置加上第一列的非零元素的个数，如此类推，因为A中三元组的存放顺序是先行后列，对同一行来说，必定先遇到列号小的元素，这样只需扫描一遍A.data即可。2023-4-26数据结构讲义49

23、 (1)引入两个向量：int numn+1,cpotn+1;numcol表示矩阵A中第col列的非零元素的个数（为了方便均从1单元用起）;cpotcol初始值表示矩阵A中的第col列的第一个非零元素在B.data中的位置。(2)cpot的初始值为：cpot1=1；cpotcol=cpotcol-1+numcol-1；2coln 2023-4-26数据结构讲义50 (3)算法实现：依次扫描A.data，当扫描到一个col列元素时，直接将其存放在B.data的cpotcol位置上，cpotcol加，cpotcol中始终是下一个col列元素在B.data中的位置。例如对于矩阵A的num 和cpot的

24、值如下：2023-4-26数据结构讲义51 算法分析：这个算法中有四个循环，分别执行n，t，n-1，t次，在每个循环中，每次迭代的时间是一常量，因此总的计算量是O（n+t）。当然它所需要的存储空间比前一个算法多了两个向量。【算法4-10】改进的稀疏矩阵转置算法SPMatrix*TransM2(SPMatrix*A)SPMatrix*B;int i,j,k;int numn+1,cpotn+1;B=new SPMatrix;/*申请存储空间*/B-mu=A-nu;B-nu=A-mu;B-tu=A-tu;/*稀疏矩阵的行、列、元素个数*/if(B-tu0)/有非零元素则转换 for(i=1;inu

25、;i+)numi=0;for(i=0;itu;i+)/*求矩阵A中每一列非零元素的个数*/j=A-datai.j;numj+;2023-4-26数据结构讲义522稀疏矩阵的乘积 已知稀疏矩阵A(m1 n1)和B(m2 n2)，n1=m2，求乘积C(m1 n2)。稀疏矩阵A、B、C及它们对应的三元组表A.data、B.data、C.data如图所示。2023-4-26数据结构讲义53由矩阵乘法规则知：C（i，j）=A(i,1)B(1,j)+A(i,2)B(2,j)+A(i,n)B(n,j)矩阵用二维数组表示时，传统的矩阵乘法是：A的第一行与B的第一列对应相乘累加后得到c11，A的第一行再与B的第

26、二列对应相乘累加后得到c12，因为现在按三元组表存储，三元组表是按行为主序存储的，在B.data中，同一行的非零元素其三元组是相邻存放的，同一列的非零元素其三元组并未相邻存放，因此在B.data中反复搜索某一列的元素是很费时的，因此改变一下求值的顺序。2023-4-26数据结构讲义54以求c11和c12为例，因为：即a11只有可能和B中第1行的非零元素相乘，a12只有可能和B中第2行的非零元素相乘，而同一行的非零元是相邻存放的，所以求c11和c12同时进行：求a11*b11累加到c11，求a11*b12累加到c12，再求a12*b21累加到c11，再求a12*b22累加到c22.，当然只有ai

27、k和bkj(列号与行号相等)且均不为零（三元组存在）时才相乘，并且累加到cij当中去。2023-4-26数据结构讲义55 (1)设一个累加器：datatype tempn+1；用来存放当前行中cij的值，当前行中所有元素全部算出之后，再存放到C.data中去。(2)引入num和rpot两个向量:numk表示矩阵B中第k行的非零元素的个数；rpotk表示第k行的第一个非零元素在B.data中的位置。其初值：rpot1=1 rpotk=rpotk-1+numk-1 2kn 例如，对于矩阵B的num和rpot如图所示。2023-4-26数据结构讲义56(3)算法实现：(a)初始化。清理一些单元，准备

28、按行顺序存放乘积矩阵;(b)求B的num，rpot;(c)做矩阵乘法。将A.data中三元组的列值与B.data中三元组的行值相等的非零元素相乘，并将具有相同下标的乘积元素相加。2023-4-26数据结构讲义57【算法4-11稀疏矩阵的乘积算法SPMatrix*MulSMatrix(SPMatrix*A,SPMatrix*B)/*稀疏矩阵A(m1 n1)和B(m2 n2)用三元组表存储，求AB*/SPMatrix *C;/*乘积矩阵的指针*/int p,q,i,j,k,r;DataType tempn+1;int numB-nu+1,rpotB-nu+1;if(A-nu!=B-mu)retur

29、n NULL;/*A的列与B的行不相等，错误，返回空指针*/C=new SPMatrix;/*申请C矩阵的存储空间*/C-mu=A-mu;C-nu=B-nu;if(A-tu*B-tu=0)C-tu=0;return C;/*A、B均为零矩阵，C亦为零矩阵*/for(i=1;imu;i+)2023-4-26数据结构讲义58上述算法的时间性能分析：（1）求num的时间复杂度为O(B-nu+B-tu)；（2）求rpot 时间复杂度为O(B-mu)；（3）求temp时间复杂度为O(A-mu*B-nu)；（4）求C的所有非零元素的时间复杂度为：O(A-tu*B-tu/B-mu)；（5）压缩存储时间复杂度

30、为O(A-mu*B-nu)；所以总的时间复杂度为：O(A-mu*B-nu+(A-tu*B-tu)/B-nu)。2023-4-26数据结构讲义59*2.稀疏矩阵的十字链表存储 三元组表可以看作稀疏矩阵顺序存储，但是在做一些操作（如加法、乘法）时，非零项数目及非零元素的位置会发生变化，这时这种表示就十分不便。在这节中，我们介绍稀疏矩阵的一种链式存储结构十字链表，它同样具备链式存储的特点，因此，在某些情况下，采用十字链表表示稀疏矩阵是很方便的。2023-4-26数据结构讲义60(1)十字链表表示稀疏矩阵的基本思想：对每个非零元素存储为一个结点，结点由5个域组成，其结构如图表示，其中：row域存储非零

31、元素的行号，col域存储非零元素的列号，v域存储本元素的值，right，down是两个指针域。2023-4-26数据结构讲义61下图是一个稀疏矩阵的十字链表。2023-4-26数据结构讲义62(2)结点的结构定义如下:typedef struct node int row,col;struct node*down,*right;union v_next datatype v;struct node *next;MNode，*MLink;2023-4-26数据结构讲义63*4.3 广义表 顾名思义，广义表是线性表的推广。也有人称其为列表（Lists，用复数形式以示与统称的表List的区别）。4.

32、3.1 广义表的逻辑结构 4.3.2 广义表的存储2023-4-26数据结构讲义644.3.1 广义表的逻辑结构1.广义表的定义 广义表（Generalized Lists）是n（n0）个数据元素a1,a2,ai,an的有序序列，一般记作：ls（a1,a2,ai,an）（4-21）其中：ls是广义表的名称，n是它的长度。ai（1in）是ls的成员，它可以是单个元素，也可以是一个广义表，分别称为广义表ls的单元素和子表。当广义表ls非空时，称第一个元素a1为ls的表头（head），称其余元素组成的子表（a2,ai,an）为ls的表尾（tail）。显然，广义表的定义是递归的。2023-4-26数据

33、结构讲义65 为书写清楚起见，通常用大写字母表示广义表，用小写字母表示单个数据元素，广义表用括号括起来，括号内的数据元素用逗号分隔开。下面是一些广义表的例子：A（）B（e）C（a，（b，c，d）D（A，B，C）E（a，E）F（）2023-4-26数据结构讲义66广义表的性质 从上述广义表的定义和例子可以得到广义表的下列重要性质：广义表是一种多层次的数据结构。广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表，。广义表可以是递归的表。广义表的定义并没有限制元素的递归，即广义表也可以是其自身的子表。例如表E就是一个递归的表。广义表可以为其他表所共享。例如，表A、表B、表C是表D的共享

34、子表。在D中可以不必列出子表的值，而用子表的名称来引用。2023-4-26数据结构讲义67广义表基本运算 广义表有两个重要的基本操作，即取头操作（Head）和取尾操作（Tail）。根据广义表的表头、表尾的定义可知，对于任意一个非空的列表，其表头可能是单元素也可能是列表，而表尾必为列表。例如：Head（B）e Tail（B）（）Head（C）a Tail（C）（b，c，d）Head（D）A Tail（D）（B，C）Head（E）a Tail（E）（E）Head（F）（）Tail（F）（）此外，在广义表上可以定义与线性表类似的一些操作，如建立、插入、删除、拆开、连接、复制、遍历等。2023-4-2

35、6数据结构讲义68CreateLists(ls)：根据广义表的书写形式创建一个广义表ls。IsEmpty(ls)：若广义表ls空，则返回True；否则返回False。Length(ls)：求广义表ls的长度。Depth(ls)：求广义表ls的深度。Locate(ls，x)：在广义表ls中查找数据元素x。Merge(ls1，ls2)：以ls1为头、ls2为尾建立广义表。CopyGList(ls1，ls2)：复制广义表，即按ls1建立广义表ls2。Head(ls)：返回广义表ls的头部。Tail(ls)：返回广义表的尾部。2023-4-26数据结构讲义694.3.2 广义表的存储 由于广义表中的数

36、据元素可以具有不同的结构，因此难以用顺序的存储结构来表示。而链式的存储结构分配较为灵活，易于解决广义表的共享与递归问题，所以通常都采用链式的存储结构来存储广义表。在这种表示方式下，每个数据元素可用一个结点表示。按结点形式的不同，广义表的链式存储结构又可以分为不同的两种存储方式。一种称为头尾表示法，另一种称为孩子兄弟表示法。2023-4-26数据结构讲义70头尾表示法 若广义表不空，则可分解成表头和表尾；反之，一对确定的表头和表尾可惟一地确定一个广义表。头尾表示法就是根据这一性质设计而成的一种存储方法。由于广义表中的数据元素既可能是列表也可能是单元素，相应地在头尾表示法中结点的结构形式有两种：一

37、种是表结点，用以表示列表；另一种是元素结点，用以表示单元素。在表结点中应该包括一个指向表头的指针和指向表尾的指针；而在元素结点中应该包括所表示单元素的元素值。为了区分这两类结点，在结点中还要设置一个标志域，如果标志为1，则表示该结点为表结点；如果标志为0，则表示该结点为元素结点。2023-4-26数据结构讲义71其形式定义说明如下：typedef enum ATOM,LIST Elemtag;/*ATOM=0：单元素；LIST=1：子表*/typedef struct GLNode Elemtag tag;/*标志域，用于区分元素结点和表结点*/union /*元素结点和表结点的联合部分*/d

38、atatype data;/*data是元素结点的值域*/struct struct GLNode *hp,*tp ptr;/*ptr是表结点的指针域，ptr.hp和ptr.tp分别指向表头和表尾*/;*GList;/*广义表类型*/2023-4-26数据结构讲义72头尾表示法的结点形式如图所示。2023-4-26数据结构讲义73 对于4.3.1所列举的广义表A、B、C、D、E、F，若采用头尾表示法的存储方式，其存储结构如图所示。2023-4-26数据结构讲义74 从上述存储结构示例中可以看出，采用头尾表示法容易分清列表中单元素或子表所在的层次。例如，在广义表D中，单元素a和e在同一层次上，而

39、单元素b、c、d在同一层次上且比a和e低一层，子表B和C在同一层次上。另外，最高层的表结点的个数即为广义表的长度。例如，在广义表D的最高层有三个表结点，其广义表的长度为3。2023-4-26数据结构讲义75孩子兄弟表示法 广义表的另一种表示法称为孩子兄弟表示法。在孩子兄弟表示法中，也有两种结点形式：一种是有孩子结点，用以表示列表；另一种是无孩子结点，用以表示单元素。在有孩子结点中包括一个指向第一个孩子（长子）的指针和一个指向兄弟的指针；而在无孩子结点中包括一个指向兄弟的指针和该元素的元素值。为了能区分这两类结点，在结点中还要设置一个标志域。如果标志为1，则表示该结点为有孩子结点；如果标志为0，

40、则表示该结点为无孩子结点。2023-4-26数据结构讲义76其形式定义说明如下：typedef enum ATOM,LIST Elemtag;/*ATOM=0：单元素；LIST=1：子表*/typedef struct GLENode Elemtag tag;/*标志域，用于区分元素结点和表结点*/union /*元素结点和表结点的联合部分*/datatype data;/*元素结点的值域*/struct GLENode *hp;/*表结点的表头指针*/;struct GLENode *tp;/*指向下一个结点*/*EGList;/*广义表类型*/2023-4-26数据结构讲义77孩子兄弟表示

41、法的结点形式如图所示。2023-4-26数据结构讲义78 对于4.3.1节中所列举的广义表A、B、C、D、E、F，若采用孩子兄弟表示法的存储方式，其存储结构如图所示。2023-4-26数据结构讲义79从图的存储结构示例中可以看出，采用孩子兄弟表示法时，表达式中的左括号“（”对应存储表示中的tag=1的结点，且最高层结点的tp域必为NULL。2023-4-26数据结构讲义80 字符串是一种数据元素类型是字符型的特殊线性表。字符串的应用很广泛，在很多的高级语言系统中都有较强的串处理能力。在本章中介绍了串的有关概念、常用的存储方法、以及串的基本运算。数组结构可以看成线性结构的一种推广，它在内存中的存储采用的是顺序存储形式，在绝大多数高级语言中都有数组这样的数据类型，有的采用行优先方式存储，有的采用列优先方式存储。在应用中应用最多的是一维数组和二维数组。对矩阵的压缩存储主要是为了节约存储空间，因此只对那些特殊矩阵和稀疏矩阵才有意义，压缩存储的关键是要处理好数据元素在原矩阵中的位置与压缩到向量之后的对应关系，采用压缩存储后，节省了存储空间，但使得原本简单的一些运算变得复杂化，我们可以根据问题的具体情况决定采用怎样的存储方法。广义表是一种复杂的数据结构，可以视为线性表的推广，本章只是简单介绍了广义表的定义、存储。小结