数据结构第4章课件

1、第4章 数组、串与广义表24 七月 2022本章概述数组是一种常用的数据结构，它是线性结构的推广。本章将首先介绍数组的基本概念、顺序存储和运算，然后介绍特殊矩阵和稀疏矩阵的压缩存储。矩阵一般采用二维数组存储。字符串是非数值处理中的主要对象。本章将介绍串的有关概念、存储结构和基本操作的实现。广义表是线性表的另一种推广，也是较常用的数据结构，本章后面的部分将介绍广义表的基本概念、取表头和取表尾运算及其存储结构。24 七月 20224.1 数组的基本概念与特性 多维数组是一维数组在维数上的扩张，是一种“同构”的数据元素。 多维数组可以看做是线性表中的元素又是一个线性表。 数组是由下标和值组成的序对的

2、有限集合。 数组中的每个数据元素都对应一组下标(j1,j2,jn)，每个下标的取值范围是0jibi-1，bi称为第i维的长度(i=1,2,n)。当n=1时，n维数组就退化为定长的线性表。24 七月 2022下面是一个mn的二维数组Amn：当把二维数组看成是线性表时，它的每一个结点又是一个向量（一维数组）。24 七月 2022例如，上述二维数组A可以看成是如下的线性表：(A0,A1,Am1)即A中的每一行是线性表的一个元素，其中，每个Ai(0im-1)都是一个向量： (ai0,ai1,ai,n1)也可以将上述二维数组A看成如下的线性表：(A0,A1,An1)24 七月 2022A中的每一列是线性

3、表的一个元素，其中，每一个Aj(0jn-1)都是一个向量：(a0j,a1j,am1,j)可见二维数组A中的每一个元素aij都同时属于两个向量，即第i+1行的行向量和第j+1列的列向量，因此每个元素aij最多有两个前驱结点，也最多有两个后继结点。由此可以看出多维数组是线性表的推广，而线性表是多维数组的特例。24 七月 20224.2 数组的顺序存储结构及其操作 二维数组可以有以下两种顺序存储方式： 行序优先存储方式 列序优先存储方式。 行序优先存储的基本思想为：从第1行的元素开始按顺序存储，第1行元素存储完成后，再按顺序存储第2行的元素，然后依次存储第3行直到最后一行的所有元素存储完毕为止，如下

4、图(a)所示。24 七月 202224 七月 2022 列序优先存储的基本思想为： 依次按顺序存储第1列、第2列直到最后一列的所有元素存储完毕为止，如上图(b)所示。 一旦确定了数组的维数和各维的长度，便可以为它分配存储空间；当规定了数组元素的存储次序后，便可根据给定的一组下标值求得相应数组元素的存储位置。24 七月 2022 假设数组中每个元素占用L个存储单元： 考虑行序优先存储方式：上述二维数组中任何一个元素的存储位置可以按以下公式确定： Loc(aij )=Loc(a00 )+(in+j) L (4-1) 考虑列序优先的存储方式：数组中任何一个元素aij存储位置的地址计算公式为： Loc

5、(aij )=Loc(a00 )+(jm+i)L (4-2)24 七月 2022 多维数组存在也行序优先和列序优先两种存储方式。 多维数组中数据元素的地址计算公式相对复杂些，但和二维数组采用的原理是相同的。 【例4-1】对于二维数组A2.123.10，计算： (1)数组A中的元素个数。 (2)若数组A的起始地址为1000，每个数组元素所占的存储空间为4字节，分别采用行序优先和列序优先方式存储时，数组元素A58的存储地址各是多少?24 七月 2022 解：(1)已知二维数组A2.123.10，则该数组的行数为12-2+1=11；该数组的列数为10-3+1=8，所以数组A中的元素个数为118=88

6、。(2)按行序优先方式存储时，A58的地址为：Loc(a58 )=Loc(a00)+(in+j)L =1000+(5-2)(10-3+1)+(8-3)4=1116按列序优先方式存储时，A58的地址为：Loc(a58 )=Loc(a00)+(jm+i)L=1000+(8-3)(12-2+1)+(5-2)4=123224 七月 2022二维数组的顺序存储表示及实现。typedef structElemType *base;数组存储区首地址指针int index2;存放二维数组各维长度Array;Array包含两个域：指针域base指向数组存储区首地址；两个元素的数组index存放二维数组各维长度。

7、24 七月 2022(1)数组初始化操作InitArray(&A,b1,b2)。具体实现过程如算法4.1所示。Status InitArray(Array &A,int b1,int b2)二维数组初始化操作if(b1=0b2=0)处理各维长度非法的情况return ERROR;A.index0=b1; 将b1、b2的值写入index数组A.index1=b2;elemtotal=b1*b2;计算数组元素个数A.base=(ElemType *)malloc(elemtotal*sizeof(ElemType);分配存储空间return OK;算法4.124 七月 2022(2)取数组元素值操

8、作Value(A,&e,i,j)。具体实现过程如算法4.2所示。Status Value(Array A,ElemType &e,int i,int j) 将数组元素Aij的值赋值给eif(i=A.index0j=A.index1)检查i、j的合法性 return ERROR;off=i*A.index1+j;计算出对应数组元素的偏移量e=*(A.base+off);赋值给ereturn OK;算法4.224 七月 2022(3)数组元素赋值操作Assign(&A,e,i,j)。具体实现过程如算法4.3所示。Status Assign(Array &A,ElemType e,int i,int

9、 j)将e的值赋值给数组元素Aijif(i=A.index0j=A.index1)检查i、j的合法性 return ERROR;off=i*A.index1+j;计算出对应数组元素的偏移量*(A.base+off)=e;赋值给数组元素return OK;算法4.324 七月 20224.3 矩阵的压缩存储 压缩存储的原则：对多个值相同的元素只存储一次，对零元素不分配存储空间。 特殊矩阵：相同的元素或零元素在矩阵中的分布有一定的规律的矩阵。 稀疏矩阵：矩阵中零元素占绝大部分的矩阵。24 七月 20224.3.1 特殊矩阵的压缩存储 1对称矩阵 方阵：矩阵的行数和列数相等。 在一个n阶方阵A中，若

10、元素满足下述性质：aij=aji（1i,jn） 则称A为对称矩阵。 A中值相等的元素之间存在对称性，因此只需存储对角线以上或对角线以下的部分，未存储部分可以利用元素之间的对称性来访问。24 七月 2022 以一个一维数组SAn(n+1)/2作为一个n阶对称矩阵A的存储结构，以行序为主序来存取矩阵的下三角(包括对角线)上的元素。24 七月 2022 容易得到下三角中数组元素aij的地址计算公式为：Loc( aij ) = Loc( a00 ) + i(i-1)/2 + (j-1) L (ij) (4-3) 即对称矩阵A中下三角上元素aij与数组SAk之间的对应关系为：k= i(i-1)/2 +

11、j-1 (ij) (4-4) 访问对称矩阵A中上三角的元素，只需将关系式(4-4)中的i、j对换，即k=j(j-1)2+i-1(ij) (4-5)24 七月 2022 n阶对称矩阵A中的数据元素在一维数组SA中的压缩存储如图所示。 上述关系式中数组元素的下标默认是从1,1开始的，若下标从0,0开始，则关系式应改写为：（4-6）24 七月 2022 2三角矩阵 三角矩阵有上三角和下三角两种。上三角矩阵的下三角（不包括主对角线）中的元素均为常数。下三角矩阵正好相反，它的主对角线上方的元素均为常数。在大多数情况下，三角矩阵常数为0。 下三角矩阵一般形式如下：24 七月 2022 由于A为下三角矩阵，

12、根据压缩存储的原则，对A只需存储对角线以下的部分。 用按行序优先方式存储，则其数学映射关系为： （4-7） 上三角矩阵一般形式如下：上三角矩阵，只需考虑存储对角线及其以上的部分按行序优先存储方式，其数学映射关系为：（4-8）24 七月 2022 3对角矩阵 对角矩阵：矩阵中所有的非零元素都集中在以主对角线为中心的带状区域。 对角矩阵一般形式如下：24 七月 2022 对角矩阵进行压缩存储时，只存储带状区域内部的元素，对于带状区域以外的元素均不分配存储空间。 以三对角矩阵为例，分析其按行序优先的压缩存储。在带状区域内部，并非每行都包含3个元素，第一行和最后一行均只有两个元素，所以要分析元素下标i

13、、j与对应存储空间下标k的关系。 对角线之下的元素只有一条，元素下标i、j满足关系j=i-1。 对角线上的元素下标i、j满足关系j=i。 对角线之上的元素也有一条，元素下标i、j满足关系j=i+1。 综上所述，三对角矩阵中元素aij的下标i、j和一维数组SA的下标k之间的数学映射关系为：k=2i+j (4-9)24 七月 2022稀疏矩阵： 矩阵中非零元素的个数远远小于矩阵元素的总数。稀疏因子： 设m行n列的矩阵含t个非零元素，令=t /(mn)，称为矩阵的稀疏因子。 通常认为0.05的矩阵为稀疏矩阵。4.3.2 稀疏矩阵的压缩存储24 七月 2022 1三元组表 矩阵中的每个非零元素可以采用

14、如下三元组的形式表示：(i,j,v)其中，i表示非零元素所在的行号；j表示非零元素所在的列号；v表示非零元素的值。 采用三元组表示法表示一个稀疏矩阵： 首先将它的每一个非零元素表示成上述的三元组形式；然后按行号递增的次序，同一行的非零元素按列号递增的次序将所有非零元素的三元组存放到连续的存储单元中。24 七月 2022 例如，已知稀疏矩阵M如下图(a)所示，其对应的三元组表为：(1,2,8),(1,5,4),(3,4,5),(4,3,7),(5,1,2),(5,6,6), (6,3,9)加上其存储序号，如下图(b)所示。24 七月 2022 稀疏矩阵的三元组表存储表示的定义：#define M

15、AXSIZE 256 最大非零元素个数typedef struct三元组类型int i,j;该非零元素的行下标和列下标ElemType v;Triple;typedef struct三元组表类型Triple dataMAXSIZE+1;三元组表存储空间int mu,nu,tu;矩阵的行数、列数和非零元素个数TSMatrix;24 七月 2022实现三元组表状态下的矩阵转置(1)三元组表的建立。具体实现过程如算法4.4所示。void CreatSMatrix(TSMatrix &M,int Amn)m、n为要转换矩阵的行、列数，定义为常量k=0;三元组表中的数组下标for(row=1;row=m

16、;row+)逐行扫描每个元素 for(col=1;colT，则返回值0;若S=T，则返回值=0;若ST，则返回值=1 & i0) n=StrLength(S);m=StrLength(T);i=pos;求S和T的串长 while(i =n-m+1) SubString(sub,S,i,m); 从S中第i个位置取长度与T相等的串 if(StrCompare(sub,T)!=0) +i;与T不相等，i加1再次比较 else return i; 与T相等则返回i的值 return 0; S中不存在与T相等的子串则返回0 Index算法4.924 七月 2022 串的存储结构也分为顺序存储结构和链式存

17、储结构两种。静态顺序存储： 用静态内存分配的方法定义的数组，数组元素的个数是在编译时确定的，在运行时是不可改变的。动态顺序存储： 用动态内存分配的方法定义的数组，数组元素的个数是在程序运行时用户申请确定的。4.4.3 串的存储及基本操作实现24 七月 2022 1串的静态顺序存储及基本操作实现 串的静态顺序存储使用静态数组存放字符。 静态数组的长度是预先设计的，每个字符串分配一个长度固定的存储区，存储区的大小在程序运行时不可改变。具体类型定义如下：24 七月 2022#define MAXSIZE 100 字符串的最大存储长度typedef char StringMAXSIZE+1; 使用0号

18、单元存储字符串长度静态顺序存储方式下字符串部分操作的具体实现。1)StrInsert(&S,pos,T)：插入操作实现过程如算法4.10所示。24 七月 2022Status StrInsert(String &S,int pos,String T)在串S的第pos个字符之前插入串Tif(posS0+1S0+T0MAXSIZE)非法情况的处理 return ERROR;Spos+T0.S0+T0=Spos.S0;将S中元素从第pos个字符开始后移T0个位置Spos.pos+T0-1=T1.T0; 将T插入到S中第pos个字符之前的位置S0=S0+T0;串长的处理return OK;算法4.10

19、24 七月 2022 2)StrDelete(&S,pos,len)：删除操作具体实现过程如算法4.11所示。Status StrDelete(String &S,int pos,int len) 从串S中删除第pos个字符起长度为len的子串if(posS0pos+len-1S0) 非法情况的处理 return ERROR;Spos.S0-len=Spos+len.S0;将S中从下标从pos+len开始的元素前移len位S0=S0-len; 串长的处理return OK;算法4.1124 七月 2022 3)Concat(&T,S1,S2)：连接操作具体实现过程如算法4.12所示。Statu

20、s Concat(String &T,String S1,String S2) 用T返回由S1和S2连接而成的新串if(S10+S20MAXSIZE) 处理字符数组空间不够使用的情况return ERROR;T1.S10=S11.S10; 将S1复制到T的前端TS10+1.S10+S20=S21.S20; 将S2复制到T的后端T0=S10+S20; 串长的处理return OK;算法4.1224 七月 2022 4)SubString(&Sub,S,pos,len)：求子串操作具体实现过程如算法4.13所示。Status SubString(String &Sub,String S,int p

21、os,int len)用Sub返回串S的第pos个字符起长度为len的子串i=pos;if(iS0i+len-1S0)非法情况的处理return ERROR;Sub1.len=Spos.pos+len-1;复制子串到串Sub中Sub0=len;串长的处理return OK;算法4.1324 七月 2022 【例4-4】假定字符串采用静态顺序存储方式存储，试将字符串S中的所有字符按照相反的次序仍然放到S中。 算法的基本思想：将字符串S中的第一个元素与最后一个元素交换，第二个元素与倒数第二个元素交换，如此下去，就可以得到一个反序的字符序列。在交换的过程中要考虑好终止条件，在此用i从前向后指示每个元

22、素，用j从后向前指示每个元素，当ij时说明反转结束。24 七月 2022具体实现过程如算法4.14所示。Status InvertString(String &S)将字符串S中字符反序排列i=1;j=S0; 初始i指向第一个字符，j指向最后一个字符while(ij) Si Sj交换元素的位置 i+;j-;指针i向后移动，j向前移动return OK;InvertString算法4.1424 七月 2022 2串的动态顺序存储及基本操作实现 动态顺序存储能够根据所要存储串的长度动态地分配存储空间。 串的动态顺序存储结构定义为：typedef structchar *ch;若是非空串，则按串长分配

23、存储区，否则ch为NULLint length; 串的长度String;24 七月 2022 使用动态顺序存储结构实现串的基本操作时要考虑分配存储空间和释放存储空间。 动态顺序存储结构下串操作实现的算法思想为：先为新生成的串分配一个存储空间，然后进行串值的复制。 以下给出在动态顺序存储方式下字符串基本操作的具体实现。 24 七月 2022 1)StrAssign(&T,chars)：赋值操作具体实现过程如算法4.15所示。Status StrAssign(String &T,char *chars)生成一个其值等于串常量chars的串Tif(T.ch) free(T.ch);释放T原有空间c=

24、chars;i=0;使字符指针c指向chars的基址while(ci!=0)i+;求chars的长度i if(!i)T.ch=NULL;T.length=0;空子串 elseT.ch=(char *)malloc(i*sizeof(char);按i为T分配空间T.ch0.i-1=chars0.i-1;复制字符T.length=i;置T的长度为i return OK; StrAssign算法4.1524 七月 2022 2)Concat(&T,S1,S2)：连接操作具体实现过程如算法4.16所示。Status Concat(String &T,String S1,String S2)用T返回由S

25、1和S2连接而成的新串if(T.ch) free(T.ch); 释放旧空间T.ch=(char *)malloc(S1.length+S2.length)*sizeof(char);分配新空间T.ch0.S1.length-1=S1.ch0.S1.length-1;复制S1中字符到T中T.length=S1.length+S2.length;重新计算T的长度T.chS1.length.T.length-1=S2.ch0.S2.length-1;复制S2到T中的S1之后return OK; Concat算法4.1624 七月 2022 3)SubString(&Sub,S,pos,len)：求子

26、串操作具体实现过程如算法4.17所示。Status SubString(String &Sub,String S,int pos,int len) 用Sub返回串S的第pos个字符起长度为len的子串if(pos S.lengthlenS.length-pos+1) 非法情况的处理return ERROR;if(Sub.ch) free(Sub.ch); 释放旧空间if(!len)Sub.ch=NULL; Sub.length=0; 空子串else 完整子串Sub.ch=(char *)malloc(len*sizeof(char);Sub.ch0.len-1=Spos-1.pos+len-2

27、;Sub.length=len;return OK; SubString算法4.1724 七月 2022 4)StrInsert(&S,pos,T)：插入操作具体实现过程如算法4.18所示。Status StrInsert(String &S,int pos,String T) 在串S的第pos个字符之前插入串TS.ch=(char*)realloc(S.ch,(S.length+T.length)*sizeof(char);重新分配空间S.chpos+T.length-1.S.length+T.length-1=S.chpos-1.S.length-1; 将S中从第pos个元素开始后移T.l

28、ength个位置S.chpos-1.pos+T.length-2=T.ch0.T.length-1;将T复制到S中从第pos个字符之后的位置S.length+=T.length; 串长的处理return OK; 算法4.1824 七月 2022 【例4-5】编写一个算法，将字符串S1中的前i个字符复制到字符串S2中。字符串采用动态顺序存储结构。算法的基本思想：首先要判断i是否合法，即在S1中是否有i个字符，然后把S2的原有空间释放，并为其分配一个大小为i的存储空间，再把S1中的前i个字符复制到S2中，最后重新设置S2的长度。 具体实现过程如算法4.19所示。24 七月 2022Status C

29、opyPart(String &S2,String S1,int i) 将字符串S1中的前i个字符复制到S2中if(i S1.length) return ERROR;判断i是否合法if(S2.ch) free(S2.ch); 释放旧空间S2.ch=(char *)malloc(i*sizeof(char);分配新空间for(k=0;ki;+k)S2.chk=S1.chk;复制S2.length=i;置S2的串长return OK; CopyPart算法4.1924 七月 2022 3串的链式存储 串的链式存储结构中，每个结点所占的空间存放若干个字符，这样可提高此单链表的存储空间利用率，这种结

30、构称为块链，如下图所示。24 七月 2022 如果块链的最后一个结点无法被串值占满，可补上0或其他的非串值字符。 串的块链式存储形式定义如下：#define blocksize 3 用户自定义块的大小typedef structchar chblocksize; 存储块struct BNode *next;BNode,*BLinkString;24 七月 2022 块链结构要比一个结点只存放一个字符的单链表结构节省空间，但当在串中插入或删除字符时，可能要大量移动字符，这就会使操作复杂起来。 串的3种存储结构，在实际操作前，要根据不同情况为串选择适当的存储表示方式。虽然串的链式存储结构在做某些操

31、作时比较方便，但总体来说不如两种顺序存储结构方便，其占用的存储空间大并且操作复杂，因此使用不多。24 七月 2022 串定位操作：假设串S=a1a2an，串T=b1b2bm(mn)，串定位操作是要在主串S中找出一个与子串T相同的子串。 模式匹配：通常把主串S称为目标串，把子串T称为模式串，把从目标串S中查找模式为T的子串的过程称为模式匹配。4.4.4 串的模式匹配24 七月 2022 匹配有两种结果出现： 若S中有模式为T的子串，就返回该子串在S中的位置，当S中有多个模式为T的子串，通常只要找出第一个子串即可，这种情况称为匹配成功； 若S中无模式为T的子串，返回值为零，称为匹配失败。24 七月

32、 2022 1朴素的模式匹配算法 基本思想：将主串S的第pos个字符和模式T的第一个字符比较，若相等继续逐个比较后续字符；若不等从主串的下一个字符(pos+1)起重新与模式串T的第一个字符比较。如此不断继续，直到主串S的一个连续子串字符序列与模式串T相等，则匹配成功，返回值为S中与T匹配的子序列第一个字符的序号。若比较完主串S的所有字符序列，都不存在一个与模式串T相等的子串，则匹配失败，返回0。24 七月 2022 通过一个实例来说明朴素的模式匹配过程： 已知S是主串，T是模式串，从pos=5的位置开始匹配。模式匹配过程如下图所示。图中的双竖线表示两个字符相匹配，如果加上斜线，表示两个字符不匹

33、配。24 七月 2022 朴素的模式匹配算法见算法4.20。int Index(SString S,SString T,int pos)返回T在S中第pos个字符后首次出现的位置，若不存在则返回0i=pos; j=1;while(i =S0 & j T0) return i-T0; 匹配成功，返回T在S中第pos个字符后首次出现的位置else return 0;Index算法4.2024 七月 2022 上述算法的执行是带有回溯的，一旦不匹配就将模式串T右移一个字符，并从T的第一个字符开始再比较。 设主串S的长度为n，模式串T的长度为m。 最好情况下，每趟与第一个字符的匹配都不成功。最好情况下

34、平均比较的次数：即最好情况下的时间复杂度是O(n+m)。24 七月 2022 最坏情况下，每趟不成功的匹配都发生在模式串T的最后一个字符。最坏情况下平均比较的次数是： 即最坏情况下的时间复杂度是O(nm)。 二进制计算机中实际处理的都是01串，如果模式串为001主串为00000000000000001时，朴素的模式匹配算法的效率不高。24 七月 2022 2KMP模式匹配算法 朴素的模式匹配算法工作的效率很低的原因是有回溯。 改进的模式匹配算法要消除回溯，利用已得到的“部分匹配”的结果将模式串T向右移动尽可能远的距离后继续比较。 当SiTj时，设位置为k，即Si和Tj匹配失败后，指针i不动，模

35、式串T向右滑动，使Tk和Si对齐继续向右进行比较，如下图所示。24 七月 2022 可得到如下关系： T1T2Tk-1 = Tj-k+1Tj-k+2Tj-1 某趟在Si和Tj匹配失败后，如果模式串中有满足上述关系的子串存在，模式串T就可以向右滑动至使Tk和Si对准，继续向右进行比较。 模式串中的每一个Tj都对应一个k值，由上关系式可知，这个k值仅依赖于模式串T本身字符序列的构成，而与主串S无关。24 七月 2022 用nextj表示Tj对应的k值，next函数有如下性质：（1）nextj是一个整数，并且0nextjj。（2）为了使T的右移不丢失任何匹配成功的可能，当存在多个满足上述关系式的k值

36、时，应取最大的，这样向右滑动的距离最短，滑动距离为j-nextj。（3）如果在Tj前不存在满足上述关系式的子串，此时若T1Tj，则k=1;若T1=Tj，则k=0;这时滑动最远，为j个字符，即用T1和Si+1继续比较。24 七月 2022 知道next的值后，便知道了当SiTj时，主串中的第i个字符应和模式串中的第nextj个字符比较。 这种改进是由D.E.Knuth与J.H.Morris和V.R.Pratt同时发现的，因此称为KMP算法。Nextj= 0 maxk|1kj且“T1T2Tk-1”=“Tj-kTj-k+2Tj-1”1 j=1集合不空其他情况引出next函数的定义为：24 七月 20

37、22 具体的KMP实现过程如算法4.21所示。int Index_KMP(String S,String T,int pos)利用模式串T的next函数求T在主串S中第pos个字符之后的位置i=pos;j=1;while(i =S0 & j T0) return i-T0;匹配成功else return 0;Index_KMP算法4.2124 七月 2022 KMP算法是在已知模式串的next函数值基础上执行的，需要求出模式串的next函数值。 next函数值完全取决于模式串，与主串无关，可以把求next函数值看成一个模式匹配过程。由next函数的定义可知：next1=0。设nextj=k这表

38、明： T1T2Tk-1=Tj-k+1Tj-k+2Tj-1 “ k值就等于“T1T2Tj-1”这个串中相同的前缀子串和后缀子串的长度加1，所以求k 值的过程就是一个模式匹配的过程，只是匹配的主串和模式串都是串T。24 七月 2022 求nextj+1，因为nextj=k，所以可能有以下两种情况： (1)若Tk=Tj，则表明：T1T2Tk=Tj-k+1Tj-k+2Tj 且不可能存在kk满足上式，即 nextj+1=nextj+1=k+1。 (2)若TkTj，则表明：“T1T2Tk” “Tj-k+1Tj-k+2Tj ” 应将模式串向右滑动至模式中的第nextk个字符和主串的第j个字符比较。24 七月

39、 2022 应当注意的是，主串和模式串均为串T。若nextk=k且Tj=Tk，则表明：T1T2Tk=Tj-k+1Tj-k+2Tj 也就是说nextj+1=k+1=nextk+1。同理若TjTk，则模式继续向右滑动至模式中第nextk个字符与Tj比较，以此类推，直至Tj与模式串中某个字符匹配成功或不存在k满足，则nextj+1=1。 根据上述分析结果，可得到求next函数值算法，如算法4.22所示。24 七月 2022void get_next(String T,int *next)求模式串T的next值并存入next数组中next1=0;i=1;j=0;while(itp);长度等于1加上其后

40、继链表长度else return 0;算法4.2324 七月 2022 2)求广义表的深度 算法思想：广义表深度的递归定义是它等于所有子表中表的最大深度加1,也就是嵌套括号最多的层次数。设dep表示任一子表的深度，max表示所有子表中表的最大深度，depth表示广义表的深度，则有depth=max+1 一个表为空或仅由单元素所组成，则深度为1，所以max的初值应该为0。24 七月 2022 具体实现如算法4.24所示。int GListDepth(GList GL)递归的方法求广义表GL的深度max=0;max初值为0while(GL!=NULL)遍历最上层的每个结点 if(GL-tag=1)

41、求每个结点的深度dep=GListDepth(GL-hp);递归调用if(depmax)max=dep; GL=GL-tp;指向同层下一个结点 return max+1;算法4.2424 七月 20224.6 实例解析与编程实现 【例4-7】假设有二维数组AM,N设A0,0在内存中的存储地址为644，A2,2 在内存中的存储地址为676。每个元素占一个存储空间，则A4,5的地址为多少？以行序为主序存储。 解：以行序为主序存储数组元素地址的计算公式为：Loc(aij )=Loc(a00 )+(in+j)L24 七月 2022但由于公式中的n为未知数，所以不能直接使用。可以根据A2,2 在内存中的

42、存储地址676这一条件首先求得n的值，代入公式得到：676=644+(2n+2)1 容易得到n为15，再把n代入公式可得：Loc(a45 )=Loc(a00 )+(in+j)L=644+(415+5)1=70924 七月 2022 【例4-8】画出对称矩阵A的压缩存储结构。 解：根据对称矩阵压缩存储的计算公式：24 七月 2022 可得A的压缩存储如下：【例4-9】编制一个程序打印3行4列的二维数组A。数组使用4.2节定义的二维数组结构。24 七月 2022 算法思想：4.2节定义的二维数组结构不能使用Aij的形式直接存取数组元素。因为定义的结构是采用一维数组来表示二维数组。所以在打印前要先进

43、行转换，根据i、j的值算出要打印元素在一维数组中的偏移量，再进行打印。 具体实现过程如算法4.25所示。24 七月 2022void Print(Array A)转换过后逐行打印二维数组中的元素for(i=0;iA.index0;i+)逐行扫描 for(j=0;jtag & GL-tp) 若是原子或空表不需要逆转 p=GL-hp; 交换表头和表尾 GL-hp=GL-tp; GL-tp=p; GListRevert(GL-hp); 逆转表头和表尾 GListRevert(GL-tp);算法4.2624 七月 2022 【例4-12】若串S=software，其子串的数目是多少? 解：串S中共有8

44、个字符，1个字符的子串有8个，两个字符的子串有7个，3个字符的子串有6个，4个字符的子串有5个，5个字符的子串有4个，6个字符的子串有3个，7个字符的子串有2个，另有一个空串和其本身。因此，子串的数目为：8+7+6+5+4+3+2+1+1=3724 七月 2022 【例4-13】字符串采用静态顺序存储方式存储，试编写一个函数计算一个子串T在一个字符串S中出现的次数，如果该子串不出现则返回0。 算法思想：把主串S中每个长度为T0的子串都拿来与T相比较，若相等则计数器count加1，直到整个主串检查完毕。 具体实现过程见算法4.27。24 七月 2022int StrCount(String S,String T)统计S中T出现的次数count=0; 计数器清零for(i=1;i=S0-T0+1;i+) for(j=i,k=1;Sj=Tk;j+,k+)用S中第i个位置开始的