第4章 串、数组和广义表

1、 2021年年12月月15日日 可表示为可表示为：（：（a a1 1 , a, a2 2 , , , a, an n） 线性结构线性结构 第第2 2章章 线性表线性表 第第3 3章章 栈和队列栈和队列 第第4 4章章 串、数组和广串、数组和广义表义表 2021年年12月月15日日 串比较，串比较，strcmp(char s1,char s2) strcmp(char s1,char s2) 串复制，串复制，strcpy(char to,char from)strcpy(char to,char from)串连接，串连接，strcat(char to,char from) strcat(char

2、 to,char from) 求串长，求串长，strlen(char s) strlen(char s) 调用标准库函数调用标准库函数 #include#include补充：补充：C C语言中常用的串运算语言中常用的串运算 2021年年12月月15日日 第第4 4章串、数组和广义表章串、数组和广义表 4.1 4.1 串串4.2 4.2 数组数组4.3 4.3 广义表广义表 教学内容教学内容 2021年年12月月15日日 1. 1. 掌握串的存储方法，理解串的两种模式匹掌握串的存储方法，理解串的两种模式匹配算法配算法；2. 2. 明确数组和广义表这两种数据结构的特点明确数组和广义表这两种数据结构

3、的特点，掌握数组存储时地址计算方法，了解几种，掌握数组存储时地址计算方法，了解几种特殊矩阵的压缩存储方法。特殊矩阵的压缩存储方法。 教学目标教学目标1. 1. 了解串的存储方法，理解串的两种模式匹配了解串的存储方法，理解串的两种模式匹配算法，重点掌握算法，重点掌握BFBF算法算法。2. 2. 明确数组和广义表这两种数据结构的特点，明确数组和广义表这两种数据结构的特点，掌握掌握数组地址计算方法数组地址计算方法，了解几种特殊矩阵，了解几种特殊矩阵的压缩存储方法。的压缩存储方法。 3. 3.掌握广义表的定义、性质及其掌握广义表的定义、性质及其GetHeadGetHead和和GetTailGetTai

4、l的操作的操作。 2021年年12月月15日日 4.1 4.1 串的定义串的定义串串(String)-(String)-零个或多个字符组成的有限序列零个或多个字符组成的有限序列21naaas串名串名串值串值串长串长n空串空串n=0 2021年年12月月15日日 a=a=BEIBEI, , b=b=JINGJING c=c=BEIJINGBEIJING d=d=BEI JINGBEI JING子串子串字符位置字符位置主串主串子串位置子串位置串相等串相等空格串空格串4.2 4.2 案例引入案例引入案例案例4.1 4.1 ：病毒感染检测：病毒感染检测研究者将人的研究者将人的DNADNA和病毒和病毒D

5、NADNA均表示成由一些字母组成的均表示成由一些字母组成的字符串序列。字符串序列。然后检测某种病毒然后检测某种病毒DNADNA序列是否在患者的序列是否在患者的DNADNA序列中出现序列中出现过，如果出现过，则此人感染了该病毒，否则没有感染。过，如果出现过，则此人感染了该病毒，否则没有感染。例如，假设病毒的例如，假设病毒的DNADNA序列为序列为baabaa，患者，患者1 1的的DNADNA序列为序列为aaabbbaaaabbba，则感染，患者，则感染，患者2 2的的DNADNA序列为序列为babbbababbba，则未感染。，则未感染。（注意，人的（注意，人的DNADNA序列是线性的，而病毒的

6、序列是线性的，而病毒的DNADNA序列是环序列是环状的状的) ) 4.3 4.3 串的类型定义、存储结构及运算串的类型定义、存储结构及运算0n , 2 , 1,|nietCharacterSaaDii数据对象数据对象: :数据关系数据关系: :, 2 , 1,| ,111niDaaaaRiiii基本操作基本操作: :(1) StrAssign (&T,chars) /串赋值串赋值(2) StrCompare (S,T) /串比较串比较(3) StrLength (S) /求串长求串长(4) Concat(&T,S1,S2) /串联串联 ADT String 2021年年12月月

7、15日日 北京林业大学信息学院北京林业大学信息学院 (5) SubString(&Sub,S,pos,len) /求子串求子串 (6) StrCopy(&T,S) /串拷贝串拷贝 (7) StrEmpty(S) /串判空串判空 (8) ClearString (&S) /清空串清空串 (9) Index(S,T,pos) /子串的位置子串的位置 (11) Replace(&S,T,V) /串替换串替换 (12) StrInsert(&S,pos,T) /子串插入子串插入 (12) StrDelete(&S,pos,len) /子串删除子串删除 (

8、13) DestroyString(&S) /串销毁串销毁ADT String 2021年年12月月15日日 顺序存储顺序存储链式存储链式存储串的存储结构串的存储结构typedef structtypedef struct char char * *ch; /ch; /若串非空若串非空, ,则按串长分配存储区则按串长分配存储区, , / /否则否则chch为为NULLNULL int length; / int length; /串长度串长度 HString;HString; 顺序存储表示顺序存储表示ABCDEFGHI#headABCIhead.链式存储表示链式存储表示 2021年年1

9、2月月15日日 #define CHUNKSIZE 80 /可由用户定义的块大小可由用户定义的块大小typedef struct Chunk char chCHUNKSIZE; struct Chunk *next;Chunk;typedef struct Chunk *head,*tail; /串的头指针和尾指针串的头指针和尾指针 int curlen; /串的当前长度串的当前长度LString; ; 链式存储表示链式存储表示 2021年年12月月15日日 可将多个字符存放在一个结点中，以克服其缺点可将多个字符存放在一个结点中，以克服其缺点优点：操作方便优点：操作方便缺点：存储密度较低缺点：

10、存储密度较低实际分配的存储位实际分配的存储位串值所占的存储位串值所占的存储位存储密度存储密度 ABCDEFGHI#headABCIhead.链式存储表示链式存储表示 2021年年12月月15日日 算法目的：算法目的：BFBF算法算法（又称古典的、经典的、朴素的、穷举的）（又称古典的、经典的、朴素的、穷举的）KMPKMP算法（特点：速度快）算法（特点：速度快）算法种类：算法种类：确定主串中所含子串第一次出现的位置（定位）确定主串中所含子串第一次出现的位置（定位）即如何实现教材即如何实现教材P72 Index(S,T,pos)函数函数串的模式匹配算法串的模式匹配算法 BFBF算法设计思想算法设计思

11、想 将主串的第将主串的第pospos个字符和模式的第一个字符比较，个字符和模式的第一个字符比较， 若若相等相等，继续逐个比较后续字符；，继续逐个比较后续字符； 若若不等不等，从主串的下一字符起，重新与模式的，从主串的下一字符起，重新与模式的第一个字符比较。第一个字符比较。 直到主串的一个连续子串字符序列与模式相等直到主串的一个连续子串字符序列与模式相等 。返回值为返回值为S S中与中与T T匹配的子序列匹配的子序列第一个字符的序号第一个字符的序号，即匹配成功。即匹配成功。 否则，匹配失败，返回值否则，匹配失败，返回值 0 0BFBF算法设计思想算法设计思想Index(S,T,pos)int I

12、ndex(Sstring S,Sstring T,int pos) i=pos; j=1; while (i=S 0 & j T 0 ) return iT0; else return 0;BFBF算法描述（算法算法描述（算法4.14.1）若若n n为主串长度，为主串长度，m m为子串长度，最坏情况是为子串长度，最坏情况是BFBF算法时间复杂度算法时间复杂度主串前面主串前面n-mn-m个位置都部分匹配到子串的最后一个位置都部分匹配到子串的最后一位，即这位，即这n-mn-m位各比较了位各比较了m m次次最后最后m m位也各比较了位也各比较了1 1次次总次数为：总次数为：(n-m)*m+m

13、(n-m+1)*m若若mn，则算法复杂度，则算法复杂度O(n*m)例：例： S=S=00000000010000000001，T=T=00010001，pos=1pos=1 2021年年12月月15日日 KMPKMP（KnuthKnuth Morris Pratt Morris Pratt）算法）算法/knuth/计算机程序设计艺术计算机程序设计艺术 第第1卷卷 基本算法基本算法 计算机程序设计艺术计算机程序设计艺术 第第2卷卷 半数值算法半数值算法计算机程序设计艺术计算机程序设计艺术 第第3卷卷 排序与查找排序与查找利用已经利

14、用已经部分匹配部分匹配的结果而加快模式串的滑动速度？的结果而加快模式串的滑动速度？且主串且主串S S的指针的指针i i不必回溯不必回溯！可提速到！可提速到O(n+m)O(n+m)！S=a b a b c a b c a c b a bT=T=a b c a cS=a b a b c a b c a c b a bT=T=a b c a cS=a b a b c a b c a c b a bT=T=a b c a ci ii ii ik kk k a b aa b ck ki ii iKMPKMP算法设计思想算法设计思想 第第 1 次匹配次匹配 s s=abacaba=abacabab b i

15、=4 p p=abab=abab j=4 失败失败 p p=abab=abab j=2 因因p p1 1pp2 2,s,s2 2=p=p2 2, ,必有必有s s2 2pp1 1, ,又因又因p p1 1=p=p3 3,s,s3 3=p=p3 3, ,所以必有所以必有s s3 3=p=p1 1。因此。因此, ,第二次匹配可直接从第二次匹配可直接从i=4, j=2i=4, j=2开始。开始。 改进：改进：每趟匹配过程中出现字符比较不等时，不回溯每趟匹配过程中出现字符比较不等时，不回溯主指针主指针i，利用已得到的，利用已得到的“部分匹配部分匹配”结果将模式向结果将模式向右滑动尽可能远的一段距离，继

16、续进行比较。右滑动尽可能远的一段距离，继续进行比较。s s1 1 s s2 2 s s3 3ssi-j+1i-j+1 s si-j+2i-j+2ssi-2i-2 s si-1i-1 s si i s si+1i+1 p p1 1 p p2 2 p pj-2j-2 p pj-1j-1 p pj j p pj+1j+1 p p1 1 p pk-1k-1 p pk k p pk+1k+1 “p1p2pk-1” = “si-k+1si-k+2si-1” “pj-k+1pj-k+2pj-1” = “si-k+1si-k+2si-1”（部分匹配部分匹配） “p1p2pk-1” = “pj-k+1pj-k+

17、2pj-1” (真子串真子串） max k|1kj,且且“p1pk-1”=“pj-k+1pj-1” 当此集合非空时当此集合非空时 0 0 当当j=1j=1时时 1 1 其他情况其他情况nextj=为此为此,定义定义nextj函数，表明当模式中第函数，表明当模式中第j个字符与主个字符与主串中相应字符串中相应字符“失配失配”时，在模式中需重新和主串时，在模式中需重新和主串中该字符进行比较的字符的位置。中该字符进行比较的字符的位置。int Index_KMP (SString S,SString T, int pos) i= pos,j =1; while (iS0 & jT0) retur

18、n i-T0; /*匹配成功匹配成功*/ else return 0; /*返回不匹配标志返回不匹配标志*/ l如何求如何求next函数值函数值1. next1 = 0;表明主串从下一字符表明主串从下一字符si+1起和模式串重新起和模式串重新开始匹配。开始匹配。i = i+1; j = 1;2. 设设nextj = k，则，则nextj+1 = ?若若pk=pj，则有，则有“p1pk-1pk”=“pj-k+1pj-1pj” ，如果，如果在在 j+1发生不匹配，说明发生不匹配，说明nextj+1 = k+1 = nextj+1。若若pkpj，可把求，可把求next值问题看成是一个模式匹配问值问题

19、看成是一个模式匹配问 题，整个模式串既是主串，又是子串。题，整个模式串既是主串，又是子串。 p p1 1 p p2 2p pj-k+1j-k+1ppj-1j-1 p pj j p pj+1 j+1 nextj=knextj=k p p1 1 p pk-1k-1 p pk k p pk+1 k+1 nextk=knextk=k p p1 1 p pk k p pk k+1 +1 nextknextk=k=k” p p1 1 p pk k p pk k+1 +1 nextknextk=k=k l若若pk=pj，则有，则有“p1pk”=“pj-k+1pj”， nextj+1=k+1=nextk+1=

20、nextnextj+1. l若若pk”=pj ，则有，则有“p1pk”=“pj-k”+1pj”， nextj+1=k”+1=nextk+1=nextnextk+1.lnextj+1=1. j 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17模式串模式串 a b c a a b b c a b c a a b d a b 0nextj1 1 1 2 2 3 1 1 23 45 67 1 2l void get_next(SString T, int &next) i= 1; next1 = 0; j = 0; while( iT0) if(j=0 | T

21、i = Tj) +i; +j; nexti = j; else j = nextj; lKMPKMP算法的时间复杂度算法的时间复杂度 设主串设主串s s的长度为的长度为n,n,模式串模式串t t长度为长度为m,m,在在KMPKMP算算法中求法中求nextnext数组的时间复杂度为数组的时间复杂度为O(m),O(m),在后面的匹在后面的匹配中因主串配中因主串s s的下标不减即不回溯的下标不减即不回溯, ,比较次数可记为比较次数可记为n,n,所以所以KMPKMP算法总的时间复杂度为算法总的时间复杂度为O(n+m)O(n+m)。lnext函数的改进函数的改进 j 1 2 3 4 5 模式模式 a a

22、 a a bnextj 0 1 2 3 4nextvalj 0 0 0 0 4 a a a b a a a a b a a a a a a a a a a a a a a b i = 5; j = 1i=4j=4j=3j=1j=2nextj = k，而，而pj=pk，则则 主串中主串中si和和pj不等时不等时，不需再和，不需再和pk进行比较进行比较，而直接和，而直接和pnextk进行进行比较。比较。 j 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17模式串模式串 a b c a a b b c a b c a a b d a b nextj 0 1 1 1

23、2 2 3 1 1 2 3 4 5 6 7 1 2 0nextvalj1 1 0 2 1 3 1 0 1 10 2 1 7 01l void get_nextval(SString T, int &nextval) i= 1; nextval1 = 0; j = 0; while( i 0 a, i = 0 a+i*lamnmmnnnmaaaaaaaaaA212222111211mnmmnnnmaaaaaaaaaA212222111211naaamjjjjj1 ),(21miaaainiii1 ),(21n)m(p ),(21或pA二维数组二维数组以行序为主序以行序为主序C, PASC

24、AL数组的顺序存储数组的顺序存储 以列序为主序FORTRAN 111101121202111101101000mnananamaaamaaamaaaa设数组开始存放位置设数组开始存放位置 LOC( 0, 0 ) = a LOC ( j, k ) = a + j * m + k二维数组的行序优先表示二维数组的行序优先表示l1u1l2u2l3u3三维数组三维数组按页按页/ /行行/ /列存放，页优先的顺序存储列存放，页优先的顺序存储各维元素个数为各维元素个数为 m1, m2, m3F 下标为下标为 i1, i2, i3的数组元素的存储位置：的数组元素的存储位置： LOC ( i1, i2, i3

25、) = a + i1* m2 * m3 + i2* m3 + i3前前i1页总页总元素个数元素个数第第i1页的页的前前i2行行总总元素个数元素个数第第 i2 行前行前 i3 列列元素个数元素个数三维数组三维数组各维元素个数为各维元素个数为 m1, m2, m3, , mnF 下标为下标为 i1, i2, i3, , in 的数组元素的存储位置：的数组元素的存储位置： nnjnjkkjnnnnnnimiimimmmimmmiiiiLOC111143232121 a a),(n n维数组维数组 L0 , 0 , 0,121niiinjcLOCjjjLOCni1 ,1iiincbcLcn n维数组维

26、数组设有一个二维数组设有一个二维数组A A m mn n 按行优先按行优先顺序存储顺序存储，假设假设A A0000存放位置在存放位置在644644(10)(10)，A A2222存放位存放位置 在置 在 6 7 66 7 6( 1 0 )( 1 0 )， 每 个 元 素 占 一 个 空 间 ， 问， 每 个 元 素 占 一 个 空 间 ， 问A A3333(10)(10)存放在什么位置？脚注存放在什么位置？脚注(10)(10)表示用表示用1010进进制表示。制表示。设数组元素设数组元素Aij存放在起始地址为存放在起始地址为Loc ( i, j ) 的存储单元中的存储单元中 Loc ( 2, 2

27、 ) = Loc ( 0, 0 ) + 2 * n + 2 = 644 + 2 * n + 2 = 676. n = ( 676 - 2 - 644 ) / 2 = 15 Loc ( 3, 3 ) = Loc ( 0, 0 ) + 3 * 15 + 3 = 644 + 45 + 3 = 692.练习练习设有二维数组设有二维数组A10,20A10,20，其每个元素占两个字节，其每个元素占两个字节， A A0000存储地址为存储地址为100100，若，若按行优先按行优先顺序存储，则元顺序存储，则元素素A6,6A6,6的存储地址为的存储地址为 ，按列优先按列优先顺序存顺序存储，元素储，元素A6,6A

28、6,6的存储地址为的存储地址为 。 练习练习352352232232(6(6* *20+6)20+6)* *2+100=3522+100=352(6(6* *10+6)10+6)* *2+100=2322+100=2321. 什么是压缩存储？什么是压缩存储？若多个数据元素的若多个数据元素的值都相同值都相同，则只分配一个元素值的，则只分配一个元素值的存储空间，且零元素不占存储空间。存储空间，且零元素不占存储空间。2. 什么样的矩阵能够压缩？什么样的矩阵能够压缩？ 一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。稀疏矩阵等。3. 什么叫稀

29、疏矩阵？什么叫稀疏矩阵？矩阵中非零元素的个数较少（一般小于矩阵中非零元素的个数较少（一般小于5%5%）特殊矩阵的压缩存储特殊矩阵的压缩存储1. 对称矩阵对称矩阵特点特点 在nn的矩阵a中，满足如下性质：aij=aji (1 i, j n)存储方法存储方法 只存储下(或者上)三角(包括主对角线)的数据元素。共占用n(n+1)/2个元素空间。k= i(i-1)/2+j 当ij j(j-1)/2+i 当ij n(n+1)/2+1 ijCC上三角矩阵上三角矩阵下三角矩阵下三角矩阵特点特点 在nn的方阵中，非零元素集中在主对角线及其两侧共L(奇数)条对角线的带状区域内 L对角矩阵。存储方法存储方法 以对

30、角线的顺序存储以对角线的顺序存储 8 2 3 0 0 0 4 2 0 3 0 0 5 7 7 6 8 0 0 9 6 9 1 5 0 0 6 1 4 2 0 0 0 2 8 3五对角矩阵五对角矩阵3 3 8 5 2 0 6 1 2 8 2 7 9 4 3 4 7 6 1 8 5 9 6 2s-2.2; 1.6-2-1 0 1 2 1 2 3 4 5 6i1=i-jj1=j|i-j| (L-1)/2k 1 n*Lsa|i-j| (L-1)/2 只存储带状区内的元素只存储带状区内的元素 除首行和末行，按每行 L个元素，共(n-2)L+(L+1)个元素。sa1.(n-1)L+1 k=(i-1)L+1

31、+(j-i) |i-j|(L-1)/2 8 2 3 0 0 0 4 2 0 3 0 0 5 7 7 6 8 0 0 9 6 9 1 5 0 0 6 1 4 2 0 0 0 2 8 38 2 3 4 2 0 3 5 77 6 8 9 6 9 1 5 6 1 4 2 2 8 3sak 1 2 3 4 5 6 7 8 9 1011 12 13 14 15 16 17 18 19 2021 22 23 24 25 26特点特点 大多数元素为零。常用存储方法常用存储方法 只记录每一非零元素(i,j,aij ) 节省空间，但丧失随机存取功能 顺序存储：三元组表 链式存储：十字(正交)链表 15 0 0 2

32、2 0 -15 0 11 3 0 0 0 0 0 0 -6 0 0 0 0 0 0 0 0 91 0 0 0 0 0 0 0 28 0 0 06 6 4.5 4.5 广义表广义表n 广义表（列表）：广义表（列表）： n ( 0 )个表元素组成的有限序列个表元素组成的有限序列， 记作记作LS = (a0, a1, a2, , an-1) LS是表名，是表名，ai是表元素，它可以是表是表元素，它可以是表 (称为称为子表子表)，可以是，可以是数据元素数据元素(称为称为原子原子)。n n为表的长度。为表的长度。n = 0 的广义表为空表。的广义表为空表。线性表的成分都是结构上不可分的单元素线性表的成分

33、都是结构上不可分的单元素广义表的成分可以是单元素，也可以是有结构的表广义表的成分可以是单元素，也可以是有结构的表线性表是一种特殊的广义表线性表是一种特殊的广义表广义表不一定是线性表，也不一定是线性结构广义表不一定是线性表，也不一定是线性结构广义表与线性表的区别？广义表与线性表的区别？广义表的基本运算广义表的基本运算（1）求表头）求表头GetHead(L)：非空广义表的第一个元：非空广义表的第一个元素，可以是一个单元素，也可以是一个子表素，可以是一个单元素，也可以是一个子表（2）求表尾）求表尾GetTail(L)：非空广义表除去表头元素：非空广义表除去表头元素以外其它元素所构成的表。表尾一定是一

34、个表以外其它元素所构成的表。表尾一定是一个表练习练习A=( ) GetHead和和GetTail均无定义均无定义A=(a,b) GetHead(A)=a GetTail(A)=(b) A=(a) GetHead(A)=a GetTail(A)=( ) A=(a) GetHead(A)=(a) GetTail(A)=( ) GetHead(GetTail(GetHead(GetTail(GetTail(A) A=(a,b,(c,d),(e,(f,g) d 有次序性有次序性 有长度有长度 有深度有深度 可递归可递归 可共享可共享一个直接前驱和一个直接后继一个直接前驱和一个直接后继表中元素个数表中元

35、素个数表中括号的重数表中括号的重数自己可以作为自己的子表自己可以作为自己的子表可以为其他广义表所共享可以为其他广义表所共享广义表的特点广义表的特点E=(a,E)=(a,(a,E)= (a,(a,(a,.)，E为递归表为递归表1）A =( )2）B = ( e ) 3）C =( a ,( b , c , d ) ) 4）D=( A , B ,C )5）E=(a, E)n=0，因为因为A是空表是空表n=1，表中元素，表中元素e是原子是原子n=2，a 为原子，为原子，(b,c,d)为子表为子表n=3，3个元素都是子表个元素都是子表n=2，a 为原子，为原子，E为子表为子表D=(A,B,C)=( ),

36、(e),(a,(b,c,d)，共享表共享表练习：求下列广义表的长度练习：求下列广义表的长度4.6 4.6 案例分析与实现案例分析与实现案例案例4.1 4.1 ：病毒感染检测：病毒感染检测【案例分析案例分析】l因为患者的因为患者的DNADNA和病毒和病毒DNADNA均是由一些字母组成的字符串均是由一些字母组成的字符串序列，要检测某种病毒序列，要检测某种病毒DNADNA序列是否在患者的序列是否在患者的DNADNA序列中出序列中出现过，实际上就是字符串的模式匹配问题。现过，实际上就是字符串的模式匹配问题。l可以利用可以利用BFBF算法，也可以利用更高效的算法，也可以利用更高效的KMPKMP算法。算法。l但与一般的模式匹配问题不同的是，此案例中病毒的但与一般的模式匹配问题不同的是，此案例中病毒的DNADNA序列是环状的。序列是环状的。l这样需要对传统的这样需要对传统的BFBF算法或算法或KMPKMP算法进行改进。算法进行改进。【案例实现案例实现】l对于每一个待检测的任务，假设病毒对于每一个待检测的任务，假设病毒DNADNA序列的长度是序列的长度是m m，因为病毒因为病毒DNADNA序列是环状的，为了线性取到每个可行的长序列是环状的，为了线性取到每个可行的长度为度为m m的模式串，可将存储病毒的模