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

《字符串及线性结构的扩展.ppt》由会员分享，可在线阅读，更多相关《字符串及线性结构的扩展.ppt（80页珍藏版）》请在三一办公上搜索。

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

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

3、所包含的字符个数，当n=0时，称为空串，通常记为。,2023/11/13,数据结构讲义,5,几个概念：子串与主串：串中任意连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。子串的位置：子串的第一个字符在主串中的序号称为子串的位置。串相等：称两个串是相等的，是指两个串的长度相等且对应字符都相等。,2023/11/13,数据结构讲义,6,字符串的基本运算,求串长 StrLength(s)串赋值 StrAssign(s1,s2)连接操作 StrConcat(s1,s2,s)或 StrConcat(s1,s2)求子串 SubStr(s,i,len)串比较 StrCmp(s1,s2)子串

4、定位 StrIndex(s,t)串插入 StrInsert(s,i,t)串删除 StrDelete(s,i,len)串替换 StrRep(s,t,r),2023/11/13,数据结构讲义,7,4.1.2 顺序串,线性表的存储方式仍适用于串，如顺序存或链式存储，通常采用顺序存储的方法，称为顺序串。也因为字符的特殊性和字符串经常作为一个整体来处理的特点，串在存储时还有一些与一般线性表不同之处。,2023/11/13,数据结构讲义,8,1顺序存储一个字符串 通常用一组地址连续的存储单元存储串值中的字符序列，可以定长来指明最大的字符个数，也叫定长串。如：#define MAXSIZE 256 char

5、 sMAXSIZE;则字符串中的字符个数不能超过256。字符串是许多程序设计语言支持的数据类型，不同语言环境得到一个串的实际长度的方法不同，下面介绍几种标识串实际长度的方法。,类似顺序表，用一个指针来指向最后一个字符。在串尾存储一个不会在串中出现的特殊字符作为串的终结符，以此表示串的结尾。用s0存放串的实际长度，串值存放在s1sMAXSIZE，字符的序号和存储位置一致，应用更为方便。,2023/11/13,数据结构讲义,9,2 顺序串的基本运算,主要讨论定长串联接、求子串、串比较算法，顺序串的插入和删除等运算基本与顺序表相同，在此不在赘述。在下面的实现中，设串结束用0来标识。,2023/11/

6、13,数据结构讲义,10,(1)求串长算法【算法 4-1】求串s的长度 int StrLength(char s)int i=0;while(si!=0)i+;return i;,2023/11/13,数据结构讲义,11,(2)串联接【算法 4-2】两个串的连接算法int StrConcat1(char s1,char s2,char s)/*把两个串s1和s2首尾连接成一个新串s*/int i=0,j,len1,len2;len1=StrLength(s1);len2=StrLength(s2);if(len1+len2MAXSIZE1)return 0;/*MAXSIZE为 s长度,不够长

7、时*/i=0;while(s1i!=0)si=s1i;i+;j=0;while(s2j!=0)si=s2j;i+;j+;si=0;/*置串结束标志*/return 1;/*连接成功*/,2023/11/13,数据结构讲义,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;jlen;j+)tj=si+j-

8、1;tj=0;return 1;,2023/11/13,数据结构讲义,13,(4)串比较【算法 4-4】串比较算法int StrComp(char*s1,char*s2)/*若s1=s2返回0，若s1s2返回大于0的数否则返回小于0的数*/int i=0;while(s1i=s2i,许多程序设计语言为用户提供了大量的字符串函数，如在C语言中的“string.h”库中提供了若干处理字符串的函数，通过这些函数用户很方便的构架字符串的操作，故不再这里赘述。,2023/11/13,数据结构讲义,14,4.1.3 模式匹配,串的模式匹配即子串定位是一种重要的串运算。设s和t是给定的两个串，在主串s中查找

9、子串t的过程称为模式匹配，如果在s中找到等于t的子串，则称匹配成功，函数返回t在s中的首次出现的存储位置(或序号)，否则匹配失败，返回0。t也称为模式。为了运算方便，设字符串采用定长存储，且用第3种方式表示串长，即串的长度存放在0号单元，串值从1号单元存放，这样字符序号与存储位置一致。,2023/11/13,数据结构讲义,15,算法思想如下：首先将s1与t1进行比较，若不同，就将s2与t1进行比较，.，直到s的某一个字符si和t1相同，再将它们之后的字符进行比较，若也相同，则如此继续往下比较，当s的某一个字符si与t的字符tj不同时，则s返回到本趟开始字符的下一个字符，即si-j+2，t返回到

10、t1，继续开始下一趟的比较，重复上述过程。若t中的字符全部比完，则说明本趟匹配成功，本趟的起始位置是i-j+1或i-t0，否则，匹配失败。设主串s=acabaabaabcacaabc，模式t=abaabcac，匹配过程如图所示。,2023/11/13,数据结构讲义,16,【算法 4-5】简单模式匹配算法int StrIndex_BF(char s,char t)/*从串s的第一个字符开始找第一个与串t相等的子串*/int i=1,j=1;while(it0)return(i-t0);/*匹配成功，返回存储位置*/else return 0;,2023/11/13,数据结构讲义,17,下面分析它

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

12、个字符：例如：s=”aaaaaaaaaaab”，t=”aaab”设匹配成功发生在si处，则在前面i-1趟匹配中共比较了(i-1)*m次，第i趟成功的匹配共比较了m次，所以总共比较了i*m次，因此最坏情况下平均比较的次数是：即最坏情况下的时间复杂度是O(n*m)。,2023/11/13,数据结构讲义,19,上述算法中匹配是从s串的第一个字符开始的，有时算法要求从指定位置开始，这时算法的参数表中要加一个位置参数pos：StrIndex(shar*s,int pos,char*t)，比较的初始位置定位在pos处。算法4-5是pos=1的情况。,2023/11/13,数据结构讲义,20,4.2 数组

13、4.2.1 数组的逻辑结构及内存映象 4.2.2 特殊矩阵 4.2.3 稀疏矩阵,2023/11/13,数据结构讲义,21,4.2.1 数组的逻辑结构及内存映像,数组是我们熟悉的一种数据结构。数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型，比如：一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，三维数组可以看作“数据元素是二维数组”的一维数组，依此类推，所以可以看作是线性表的推广。,2023/11/13,数据结构讲义,22,1数组的逻辑结构 数组是一个具有固定格式和数量的数据有序集，每一个数据元素有唯一的一组下标来标识。在数

14、组上不能做插入、删除数据元素的操作。通常在各种高级语言中数组一旦被定义，每一维的大小及上下界都不能改变。在数组中通常做下面两种操作：(1)取值操作：给定一组下标，读其对应的数据元素。(2)赋值操作：给定一组下标，存储或修改与其相对应的数据元素。我们着重研究二维和三维数组，因为它们的应用是广泛的，尤其是二维数组。,2023/11/13,数据结构讲义,23,2 数组的内存映象,通常，数组在内存被映象为向量，这是因为内存的地址空间是一维的，数组的行列固定后，通过一个映象函数，则可根据数组元素的下标得到它的存储地址。对于一维数组按下标顺序分配即可。对多维数组分配时，要把它的元素映象存储在一维存储器中，

15、一般有两种存储方式：一是以行为主序（或先行后列）的顺序存放，如BASIC、PASCAL、COBOL、C等程序设计语言中用的是以行为主的顺序分配，即一行分配完了接着分配下一行。另一种是以列为主序（先列后行）的顺序存放，如FORTRAN语言中，用的是以列为主序的分配顺序，即一列一列地分配。,2023/11/13,数据结构讲义,24,以行为主序的分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变，从右向左，最后是左下标。以列为主序分配的规律恰好相反：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变，从左向右，最后是右下标。,2023/11/13,

16、数据结构讲义,25,设二维数组Amn，按元素的下标求其地址的计算：以“以行为主序”的分配为例：设数组的基址为LOC(a11)，每个数组元素占据l个地址单元，那么aij 的物理地址可用一线性寻址函数计算：LOC(aij)=LOC(a11)+(i-1)*n+j-1)*l 在C语言中，数组中每一维的下界定义为0，则：LOC(aij)=LOC(a00)+(i*n+j)*l 推广到一般的二维数组：Ac1.d1 c2.d2，则aij的物理地址计算函数为：LOC(aij)=LOC(a c1 c2)+(i-c1)*(d2-c2+1)+(j-c2)*l,2023/11/13,数据结构讲义,26,同理对于三维数组

17、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)*(d3-c3+1)+(k-c3)*l,2023/11/13,数据结构讲义,27,三维数组的逻辑结构和以行为主序的分配示意图如图所示。,2023/11/13,数据结构讲义,28,例4-1 若矩阵Amn 中存在某个元素aij满足：aij是第i行中最小值且

18、是第j列中的最大值，则称该元素为矩阵A的一个鞍点。试编写一个算法，找出A中的所有鞍点。实现的基本思想：在矩阵A中求出每一行的最小值元素，然后判断该元素它是否是它所在列中的最大值，是则打印出，接着处理下一行。矩阵A用一个二维数组表示。,2023/11/13,数据结构讲义,29,【算法4-8】求矩阵鞍点#define M/*矩阵的行*/#define N/*矩阵的列*/void saddle(int A N)int i,j,k,p,min;for(i=0;i=M)printf(%d,%d,%dn,i,k,min);对任意mn的矩阵，算法的时间性能为O(m(n+mn)。,2023/11/13,数据结

19、构讲义,30,4.2.2 特殊矩阵,对于一个矩阵结构显然用一个二维数组来表示是非常恰当的，但在有些情况下，比如常见的一些特殊矩阵，如三角矩阵、对称矩阵、带状矩阵、稀疏矩阵等，从节约存储空间的角度考虑，这种存储是不太合适的。下面从这一角度来考虑这些特殊矩阵的存储方法。,2023/11/13,数据结构讲义,31,1.对称矩阵,对称矩阵的特点是：在一个n阶方阵中，有aij=aji，其中1i,jn,2023/11/13,数据结构讲义,32,对称矩阵关于主对角线对称，因此只需存储上三角或下三角部分即可。比如，只存储下三角中的元素aij，其特点是中ji且1in，对于上三角中的元素aij，它和对应的aji相

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

21、序中，aij是第i*(i-1)/2+j个元素，因此它在SA中的下标k与i、j的关系为：k=i*(i-1)/2+j-1(kn*(n+1)/2)当访问的元素在上三角中时(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-1,2023/11/13,数据结构讲义,35,2.三角矩阵,形如下图的矩阵称为三角矩阵，其中c为某个常数

22、。其中(a)为下三角矩阵：主对角线以上均为同一个常数；(b)为上三角矩阵，主对角线以下均为同一个常数；下面讨论它们的压缩存储方法。,2023/11/13,数据结构讲义,36,(1)下三角矩阵 与对称矩阵类似，不同之处在于存完下三角中的元素之后，紧接着存储对角线上方的常量，因为是同一个常数，所以存一个即可，这样一共存储了n*(n+1)+1个元素，设存入向量：SAn*(n+1)+1中，这种的存储方式可节约n*(n-1)-1个存储单元，sak 与aji 的对应关系为：,2023/11/13,数据结构讲义,37,(2)上三角矩阵 对于上三角矩阵，存储思想与下三角类似，以行为主序顺序存储上三角部分，最后

23、存储对角线下方的常量。对于第1行，存储n个元素，第2行存储n-1个元素，第p行存储(n-p+1)个元素，aij的前面有i-1行，共存储：个元素，aij 是它所在的行中要存储的第（j-i+1）个也就是上三角存储顺序中的第(i-1)*(2n-i+2)/2+(j-i+1)个，因此它在SA中的下标为：k=(i-1)*(2n-i+2)/2+j-i。综上，sak 与aji 的对应关系为：,2023/11/13,数据结构讲义,38,3.带状矩阵 n阶矩阵A称为带状矩阵，如果存在最小正数m，满足当i-jm 时，aij=0，这时称w=2m-1为矩阵A的带宽。下图是一个w=3(m=2)的带状矩阵。带状矩阵也称为对

24、角矩阵。由下图可看出，在这种矩阵中，所有非零元素都集中在以主对角线为中心的带状区域中，即除了主对角线和它的上下方若干条对角线的元素外，所有其他元素都为零(或同一个常数c)。,2023/11/13,数据结构讲义,39,一种压缩方法是将A压缩到一个n行w列的二维数组B中，如下图所示，当某行非零元素的个数小于带宽w时，先存放非零元素后补零。那么aij 映射为b ij，映射关系为：,2023/11/13,数据结构讲义,40,另一种压缩方法是将带状矩阵压缩到向量C中去，按以行为主序，顺序的存储其非零元素，如下图所示，按其压缩规律，找到相应的映象函数。如当w=3时，映象函数为：k=2*i+j-3,2023

25、/11/13,数据结构讲义,41,4.2.3 稀疏矩阵,设m*n矩阵中有t个非零元素且tm*n，这样的矩阵称为稀疏矩阵。基本思想史志存非零元素：将非零元素所在的行、列以及它的值构成一个三元组（i,j,v），然后再按某种规律存储这些三元组，这种方法可以节约存储空间。下面讨论稀疏矩阵的压缩存储方法。,2023/11/13,数据结构讲义,42,1.稀疏矩阵的三元组表存储,将三元组按行优先的顺序，同一行中列号从小到大的规律排列成一个线性表，称为三元组表，采用顺序存储方法存储该表。如图(a)稀疏矩阵对应的三元组表为图(b)。,2023/11/13,数据结构讲义,43,存储设计如下：#define SMA

26、X 1024/*一个足够大的数*/typedef struct int i,j;/*非零元素的行、列*/datatype v;/*非零元素值*/SPNode;/*三元组类型*/typedef struct int mu,nu,tu;/*矩阵的行、列及非零元素的个数*/SPNode dataSMAX;/*三元组表*/SPMatrix;/*三元组表的存储类型*/这样的存储方法确实节约了存储空间，但矩阵的运算从算法上可能变的复杂些。,2023/11/13,数据结构讲义,44,(1)稀疏矩阵的转置 设SPMatrix A;表示一m*n的稀疏矩阵，其转置B则是一个n*m的稀疏矩阵，因此有 SPMatri

27、x B;。由A求B需：A的行、列转化成B的列、行；将A.data中每一三元组的行列交换后转到B.data中；以上两点完成之后，并没有完成B。因为我们前面规定三元组的是按一行一行且每行中的元素是按列号从小到大的规律顺序存放的，因此B也必须按此规律实现，A的转置B如图(a)所示，图(b)是它对应的三元组存储，就是说，在A的三元组存储基础上得到B的三元组表存储（为了运算方便，矩阵的行列都从1算起，三元组表data也从1单元用起）。,2023/11/13,数据结构讲义,45,算法思路：A的行、列转化成B的列、行；在A.data中依次找第一列的、第二列的、直到最后一列，并将找到的每个三元组的行、列交换后

28、顺序存储到B.data中即可。算法实现如下【算法4-9】。,2023/11/13,数据结构讲义,46,【算法4-9】稀疏矩阵转置算法SPMatrix*TransM1(SPMatrix*A)SPMatrix*B;int p,q,col;B=(SPMatrix*)malloc(sizeof(SPMatrix);/*申请存储空间*/Bmu=Anu;Bnu=Amu;Btu=Atu;/*行、列、元素个数*/if(Btu0)q=1;for(col=1;colnu);col+)/*按A的列序转换*/for(p=1;ptu);p+)/*扫描整个三元组表*/if(Adatap.j=col)Bdataq.i=Ad

29、atap.j;Bdataq.j=Adatap.i;Bdataq.v=Adatap.v;q+;return B;/*返回的是矩阵B的指针*/,2023/11/13,数据结构讲义,47,算法分析：其时间主要耗费在col和p的二重循环上，所以时间复杂性为O(n*t)，(设m、n是原矩阵的行、列，t是稀疏矩阵的非零元素个数)。显然当非零元素的个数t和m*n同数量级时，算法的时间复杂度为O(m*n2)，和通常存储方式下矩阵转置算法相比，可能节约了一定量的存储空间，但算法的时间性能更差一些。,2023/11/13,数据结构讲义,48,转置算法的改进：上述算法效率低的原因是算法要从A的三元组表中寻找第一列、

30、第二列、，要反复搜索A表，若能直接确定A中每一三元组在B中的位置，则对A的三元组表扫描一次即可。这是可以做到的，因为A中第一列的第一个非零元素一定存储在B.data1，如果还知道第一列的非零元素的个数，那么第二列的第一个非零元素在B.data中的位置便等于第一列的第一个非零元素在B.data中的位置加上第一列的非零元素的个数，如此类推，因为A中三元组的存放顺序是先行后列，对同一行来说，必定先遇到列号小的元素，这样只需扫描一遍A.data即可。,2023/11/13,数据结构讲义,49,(1)引入两个向量：int numn+1,cpotn+1;numcol表示矩阵A中第col列的非零元素的个数（

31、为了方便均从1单元用起）;cpotcol初始值表示矩阵A中的第col列的第一个非零元素在B.data中的位置。(2)cpot的初始值为：cpot1=1；cpotcol=cpotcol-1+numcol-1；2coln,2023/11/13,数据结构讲义,50,(3)算法实现：依次扫描A.data，当扫描到一个col列元素时，直接将其存放在B.data的cpotcol位置上，cpotcol加，cpotcol中始终是下一个col列元素在B.data中的位置。,例如对于矩阵A的num 和cpot的值如下：,2023/11/13,数据结构讲义,51,算法分析：这个算法中有四个循环，分别执行n，t，n-

32、1，t次，在每个循环中，每次迭代的时间是一常量，因此总的计算量是O（n+t）。当然它所需要的存储空间比前一个算法多了两个向量。,2023/11/13,数据结构讲义,52,2稀疏矩阵的乘积 已知稀疏矩阵A(m1 n1)和B(m2 n2)，n1=m2，求乘积C(m1 n2)。稀疏矩阵A、B、C及它们对应的三元组表A.data、B.data、C.data如图所示。,2023/11/13,数据结构讲义,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，

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

34、2累加到c22.，当然只有aik和bkj(列号与行号相等)且均不为零（三元组存在）时才相乘，并且累加到cij当中去。,2023/11/13,数据结构讲义,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/11/13,数据结构讲义,56,

35、(3)算法实现：(a)初始化。清理一些单元，准备按行顺序存放乘积矩阵;(b)求B的num，rpot;(c)做矩阵乘法。将A.data中三元组的列值与B.data中三元组的行值相等的非零元素相乘，并将具有相同下标的乘积元素相加。,2023/11/13,数据结构讲义,57,2023/11/13,数据结构讲义,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）压缩存储时间复杂度为O(A-

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

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

38、式以示与统称的表List的区别）。4.3.1 广义表的逻辑结构 4.3.2 广义表的存储,2023/11/13,数据结构讲义,64,4.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）。

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

40、归的表。广义表可以为其他表所共享。例如，表A、表B、表C是表D的共享子表。在D中可以不必列出子表的值，而用子表的名称来引用。,2023/11/13,数据结构讲义,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）（）此外，在广义表上可以定义与线性表

41、类似的一些操作，如建立、插入、删除、拆开、连接、复制、遍历等。,2023/11/13,数据结构讲义,68,CreateLists(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)：返回广

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

43、一种存储方法。由于广义表中的数据元素既可能是列表也可能是单元素，相应地在头尾表示法中结点的结构形式有两种：一种是表结点，用以表示列表；另一种是元素结点，用以表示单元素。在表结点中应该包括一个指向表头的指针和指向表尾的指针；而在元素结点中应该包括所表示单元素的元素值。为了区分这两类结点，在结点中还要设置一个标志域，如果标志为1，则表示该结点为表结点；如果标志为0，则表示该结点为元素结点。,2023/11/13,数据结构讲义,71,其形式定义说明如下：typedef enum ATOM,LIST Elemtag;/*ATOM=0：单元素；LIST=1：子表*/typedef struct GLNo

44、de Elemtag tag;/*标志域，用于区分元素结点和表结点*/union/*元素结点和表结点的联合部分*/datatype data;/*data是元素结点的值域*/struct struct GLNode*hp,*tp ptr;/*ptr是表结点的指针域，ptr.hp和ptr.tp分别指向表头和表尾*/;*GList;/*广义表类型*/,2023/11/13,数据结构讲义,72,头尾表示法的结点形式如图所示。,2023/11/13,数据结构讲义,73,对于所列举的广义表A、B、C、D、E、F，若采用头尾表示法的存储方式，其存储结构如图所示。,2023/11/13,数据结构讲义,74,

45、从上述存储结构示例中可以看出，采用头尾表示法容易分清列表中单元素或子表所在的层次。例如，在广义表D中，单元素a和e在同一层次上，而单元素b、c、d在同一层次上且比a和e低一层，子表B和C在同一层次上。另外，最高层的表结点的个数即为广义表的长度。例如，在广义表D的最高层有三个表结点，其广义表的长度为3。,2023/11/13,数据结构讲义,75,孩子兄弟表示法 广义表的另一种表示法称为孩子兄弟表示法。在孩子兄弟表示法中，也有两种结点形式：一种是有孩子结点，用以表示列表；另一种是无孩子结点，用以表示单元素。在有孩子结点中包括一个指向第一个孩子（长子）的指针和一个指向兄弟的指针；而在无孩子结点中包括

46、一个指向兄弟的指针和该元素的元素值。为了能区分这两类结点，在结点中还要设置一个标志域。如果标志为1，则表示该结点为有孩子结点；如果标志为0，则表示该结点为无孩子结点。,2023/11/13,数据结构讲义,76,其形式定义说明如下：typedef enum ATOM,LIST Elemtag;/*ATOM=0：单元素；LIST=1：子表*/typedef struct GLENode Elemtag tag;/*标志域，用于区分元素结点和表结点*/union/*元素结点和表结点的联合部分*/datatype data;/*元素结点的值域*/struct GLENode*hp;/*表结点的表头指针

47、*/;struct GLENode*tp;/*指向下一个结点*/*EGList;/*广义表类型*/,2023/11/13,数据结构讲义,77,孩子兄弟表示法的结点形式如图所示。,2023/11/13,数据结构讲义,78,对于节中所列举的广义表A、B、C、D、E、F，若采用孩子兄弟表示法的存储方式，其存储结构如图所示。,2023/11/13,数据结构讲义,79,从图的存储结构示例中可以看出，采用孩子兄弟表示法时，表达式中的左括号“（”对应存储表示中的tag=1的结点，且最高层结点的tp域必为NULL。,2023/11/13,数据结构讲义,80,字符串是一种数据元素类型是字符型的特殊线性表。字符串

48、的应用很广泛，在很多的高级语言系统中都有较强的串处理能力。在本章中介绍了串的有关概念、常用的存储方法、以及串的基本运算。数组结构可以看成线性结构的一种推广，它在内存中的存储采用的是顺序存储形式，在绝大多数高级语言中都有数组这样的数据类型，有的采用行优先方式存储，有的采用列优先方式存储。在应用中应用最多的是一维数组和二维数组。对矩阵的压缩存储主要是为了节约存储空间，因此只对那些特殊矩阵和稀疏矩阵才有意义，压缩存储的关键是要处理好数据元素在原矩阵中的位置与压缩到向量之后的对应关系，采用压缩存储后，节省了存储空间，但使得原本简单的一些运算变得复杂化，我们可以根据问题的具体情况决定采用怎样的存储方法。广义表是一种复杂的数据结构，可以视为线性表的推广，本章只是简单介绍了广义表的定义、存储。,小结,