Chap3算法与数据结构-C语言描述(第2版)张乃孝编课件

3.1字符串及其抽象数据类型

1定义字符串简称串，是一种特殊的线性表，其特殊性主要在于表中的每个元素是一个字符。由零个或多个字符组成的有限序列，一般记为 s=“a1a2…an”(n0)其中，s是串名，用单引号〔或双引号〕括起来的字符序列是串的值。ai可以是字母、数字或其他字符；串中字符的个数n成为串的长度。例如：A="123"(长度=3)

B="ABBABBC"(长度=7)

C="BB"(长度=2)

D="BB"(长度=3)第三章串E=""(注意区分空串""与空格串""区别)T=“ABBABBCA”t=“ABBABBCA”(T和t不等)P=“BBC”(P是T的子串,在T的位置是5)

子串：串中任意个连续的字符组成的子序列。主串：包含子串的串相应地称为主串。特别地，空串是任意串的子串。任意串s都是s本身的子串。除s本身之外，s的其它子串称为s的真子串。位置：字符在序列中的序号。子串在主串中的位置那么以子串的第一个字符在主串中的位置来表示。相等：两个串的长度相等，并且对应位置的字符都相等。

2抽象数据类型ADTStringisoperationsStringcreateNullStr(void)//创立一个空串。intIsNullStr(Strings)//判断串s是否为空串，假设为空串，那么返回1，否那么返回0。intlength(Strings)//返回串s的长度。Stringconcat(Strings1,Stings2)//返回将串s1和s2拼接在一起构成的一个新串。StringsubStr(Strings,inti,intj)//在串s中，求从串的第i个字符开始连续j个字符所构成的子串。intindex(Strings1,Strings2)//如果串s2是s1的子串，那么可求串s2在串s1中第一次出现的位置。endADTString3.2字符串的实现顺序表示链接表示

1顺序表示字符串的顺序表示，就是把串中的字符，顺序地存储在一组地址连续的存储单元中。其类型定义为：structSeqString{ /*顺序串的类型*/intMAXNUM; /*串允许的最大字符个数*/intn; /*串的长度，n

MAXNUM*/char*c;};typedefstructSeqString*PSeqString; s=“abcdef”s是structSeqString类型的变量字符串运算1：创立空顺序串创立空串的方法与创立空顺序表类似。PSeqStringcreateNullStr_seq(intm)程序pstr－－>m=70MAXNUMnc———————>字符串运算2：求顺序表示的串的子串

PSeqStringsubStr_seq(PSeqStrings,inti,intj)求从s所指的顺序串中第i(i>0)个字符开始连续取j个字符所构成的子串。如：subStr_seq(s,5,3)程序实现

s1－－>jjMAXNUMnc———————>epnksubStr_seq(s,5,5)时if(s->n<i+j-1)j=s->n-i+1;s－－>m=107MAXNUMnc———————>iamaepniPSeqStringsubStr_seq(PSeqStrings,inti,intj){ PSeqString s1; int k; s1=createNullStr_seq(); /*创立一空串*/ if(s1==NULL)returnNULL; if(i>0&&i<=s->n&&j>0) { /*假设从i开始取不了j个字符,那么能取几个就取几个*/ if(s->n<i+j-1)j=s->n-i+1; for(k=0;k<j;k++) s1->c[k]=s->c[i+k-1]; s1->n=j; } return(s1);}算法3.2求顺序表示的串的子串2链接表示

在串的链接表示中，每个结点包含两个字段：字符和指针，分别用于存放字符和指向下一个结点的指针。这样一个串就可用一个单链表来表示，其类型定义为：structStrNode; /*链串的结点*/ typedefstructStrNode*PStrNode; /*结点指针类型*/ structStrNode{ /*链串的结点结构*/ charc; PStrNodelink; }; typedefstructStrNode*LinkString; /*链串的类型*/例如：串s="abcdef"，按单链表存储时，假设s是LinkString类型的变量，那么它的存储结构如图3.2(a)所示。同样为了方便处理，可在第一个结点之前增加一个头结点，如图3.2(b)所示。也可以采用循环表的形式存储串，具体形式请看图3.2(c)。字符串运算1：创立带头结点的空链串

创立空串的方法与创立空链表类似，可有如下程序实现：LinkStringcreateNullStr_link(void)字符串运算2：求单链表示的串的子串LinkStringsubStr_link(LinkStrings,inti,intj)

求从s所指的带头结点的链串中第i(i>0)个字符开始连续取j个字符所构成的子串。这里首先要为链串结构和头结点申请空间，创立一个空链表，这由算法3.3实现。然后判断所给参数i，j的值是否合理，i，j的取值应为i>0，j>0。接着从s->head开始找第i个结点，找到后，就从该结点开始，为子串中的结点申请空间，并将元素值拷过去。程序实现LinkStringcreateNullStr_link(){LinkStringpst;pst=(LinkString)malloc(sizeof(structStrNode));if(pst!=NULL) pst->link=NULL;return(pst);}算法3.3创立空链串PLinkStringsubStr_link(PLinkStrings,inti,intj)/*求从s所指的链串中第i(i>0)个字符开始 连续j个字符所构成的子串*/{ PLinkStrings1; PStrNodep,q,t; intk; s1=createNullStr_link();/*创立空链串*/ if(s1==NULL) { printf("Outofspace!\n"); returnNULL; } if(i<1||j<1)return(s1); /*i,j值不适宜， 返回空串*/ p=s->head; for(k=1;k<i;k++)/*找开始字符*/ if(p!=NULL) p=p->link;算法3.4求单链表示的串的子串

else return(s1); if(p==NULL)return(s1); t=(PStrNode)malloc(sizeof(structStrNode)); s1->head=t; for(k=1;k<=j;k++)/*连续取j个字符*/ { t->c=p->c; if(p->link!=NULL&&k<j) {q=(PStrNode)malloc(sizeof(structStrNode)); p=p->link; t->link=q; t=q; } elsebreak; } t->link=NULL; return(s1);}3.3模式匹配设有两个串t和p：

t=t0t1…tn-1

p=p0p1…pm-1

其中1＜m≤n〔通常有m<<n〕。我们的任务是要在t中找出一个与p相同的子串。

通常把t称为目标，把p称为模式。从目标t中查找与模式p完全相同的子串的过程叫作模式匹配。匹配结果有两种：如果t中存在等于p的子串，就指出该子串在t中的位置，称为匹配成功；否那么称为匹配失败。

1朴素的模式匹配

根本思想：用p中的字符依次与t中的字符比较〔见图3.3-(a)〕，如果t0=p0，t1=p1，…，tm-1=pm-1，那么匹配成功，返回第一次出现的位置是从第一个字符t0开始。否那么必有某个i〔0≤i≤m-1〕，使得ti≠pi，这时可将p右移一个字符，用p中字符从头p0开始与t中字符t1依次比较〔见图3.3-b〕，如此反复执行，直到下面两种情况之一：或者到达某步时，ti=p0，ti+1=p1，…，ti+m-1=pm-1，匹配成功，返回第一次出现的位置是从t中第i+1个字符ti开始，即是找到的〔第一个〕与模式p相同的子串；或者一直将p移到无法与t继续比较为止，那么匹配失败。程序实现设目标串以t＝"abbaba"和p＝"aba"为例，s的长度为n〔n=6〕，t的长度为m〔m=3〕该算法简单，易于理解，但效率不高，一旦比较不等，就将p所指的串右移一个字符，并从p0〔算法中用p->c[0]表示〕开始比较。在最坏的情况下，每趟比较都在最后出现不等，最多比较n－m＋1趟，总比较次数为m*(n－m＋1)，由于在一般情况下m＜＜n，所以算法运行时间为O(m*n)。当模式串和主串为如下的情形时，这种匹配算法效率就很低。主串：“000000000000000000000000000000000000000000001”(n=45)模式串：“00000001”(m=8)比较次数：m×(n-m+1)intindex(PSeqStringt,PSeqStringp)/*求p所指的串在t所指的串中第一次出现时，*//*p所指串的第一个元素在t所指的串中的序号*/{ inti,j; i=0;j=0; /*初始化*/ while(i<p->n&&j<t->n) /*反复比较*/ if(p->c[i]==t->c[j]) {i++;j++;} else { j=j-i+1; i=0; } if(i>=p->n) return(j-p->n+1); /*匹配成功*/ else return(0); /*匹配失败*/}算法3.5朴素的模式匹配算法由与和同时发现的。简称KMP算法。

设主串S=“ababcabcacbab”,模式串T=“abcac”那么普通算法的匹配过程如下：2无回溯的模式匹配

第一趟匹配第二趟匹配第三趟匹配第四趟匹配第五趟匹配第六趟匹配ababcabcacbabababcabcacbabababcabcacbabababcabcacbabababcabcacbabababcabcacbababcacabcacabcacabcacabcacabcac未改进时的匹配情况：第一趟匹配第二趟匹配第三趟匹配ababcabcacbabababcabcacbabababcabcacbababcacabcac(a)bcac改进后的匹配情况：改进算法的一般情况：设主串为“t1t2…tn”，模式串为“p1p2…pm”，从上例分析可知，为了实现改进算法，需要解决如下问题：当产生“失配”情况〔tjpi〕时，模式串应向右滑动多远的距离。即当tj与pi失配时，tj〔j指针不回溯〕应与模式串的哪一个字符比较。假设此时tj应与模式串的第k〔k<i〕个字符比较，那么有如而失配时已经得到的局部匹配结果是：“p0p1…pi-1”=“tj-itj-i+1…tj-1”而其中一局部就是下式：“pi-kpi-k+1…pi-1”=“tj-ktj-k+1…tj-1”于是有：“p0p1…pk-1”=“pi-kpi-k+1…pi-1”反之，假设模式串中存在满足上式的两个子串，那么当主串中第j个与模式串中第i个字符不等时，仅需t0t1……tj-itj-i+1……tj-1tj…p0p1……pk-1pk…pi-1pi应滑动的位置：t0t1……tj-itj-i+1………tj-1tj…p0p1…pk-1pk…pi-1pi…失配时的位置：设主串:abcababbcaab,模式串:ababbc

匹配过程:第一次匹配:abcababbcaabababbc第二次匹配:abcababbcaabababbc第二次匹配:abcababbcaabababbc将模式串向右滑动至第k个字符和主串中第i个字符比较即可。假设令next[i]=k,那么next[i]说明当模式中第j个字符与主串中相应字符“失配”时，在模式串中需重新和主串中该字符进行比较的字符的位置。由此可以得出next函数的定义：当i=0时其他情况当此集合不空时i01234567模式串abaabcacnext[i]-10011201ïîïíì=<<-=---0}'...''...'0|{1][110ikikppppikkMaxinext且前后缀最大相同字母个数abcabcdefabcabbe1abcabbeabcabcdefabcabbeabcabbe2设主串:abcababbcaab,模式串:ababbc

匹配过程:第一次匹配:abcababbcaabababbc第二次匹配:abcababbcaabababbc第二次匹配:abcababbcaabababbc图3.5发现pi≠tj时的状态图3.6p0…pｉ-1的前缀与后缀比较↓j=1第一趟匹配：主串acabaabaabcacaabc模式串

a

baabc↑i=1next[1]=0↓j=1第二趟匹配：主串acabaabaabcacaabc模式串abaabc↑i=0next[0]=-1

↓j=2→

↓j=7第三趟匹配：主串acabaabaabcacaabc模式串abaab

c↑i=0→

↑i=5next[5]=2↓j=7→

↓j=11第四趟匹配：主串acabaabaabcacaabc模式串(ab)aabc

↑i=2→↑i=6KMP算法例子i012345

模式串abaabcnext[i]-100112此时不必从i=l，j=0重新开始第二次匹配。因为t.str[0]≠t.str[1]，s.str[1]=t.str[1]，必有s.str[1]≠t.str[0]，又因t.str[0]=t.str[2]，s.str[2]=t.str[2]，所以必有s.str[2]=t.str[0]。因此，第二次匹配可直接从i=3，j=1开始。进一步分析，t.str[1]=t.str[3]，s.str[3]≠t.str[3]，必定s.str[3]≠t.str[1]，所以第二次匹配也不必进行，可以直接进行第三次匹配，即i=3，j=0。由此可见，当s.str[i]和t.str[j]比较不相等时，串s的指针i不必回溯。KMP算法的根本思想：P(80)设目标串为s，模式串为ti、j分别为指示s和t的指针，i、j的初值均为0。假设有si=tj，那么i和j分别增1；否那么，i不变，j退回至j=next[j]的位置(也可理解为串s不动，模式串t向右移动到si与tnext[j]对齐)；比较si和tj。假设相等那么指针各增1；否那么j再退回到下一个j=next[j]的位置(即模式串继续向右移动)，再比较si和tj。依次类推，直到以下两种情况之一：1)j退回到某个j=next[j]时有si=tj，那么指针各增1，继续匹配；2)j退回至j=-1，此时令指针各增l，即下一次比较si+1和t0。一般的模式匹配算法(回溯法)的时间复杂度为O(m*n),m和n分别为两串的长度.改进的KMP算法的时度复杂度可减小到O(m+n)数量级,大大提高了算法效率.设主串为s=“s0s1…sn-1”,模式串为t=“t0t1…tm-1”,求t在s中的位置.定义：next[j]的函数为max{k|0<k<j,且=“t0t1…tm-1”=“tj-ktj-k+1…tj-1}当此集合非空时Next[j]=0其他情况-1当j=时例：主串s=“abcaabccacabcabcaaaabc“,模式串t=“abcabcaaa“,求出t的next数组，并用KMP算法求出子串位置过程.解：Next数组：j012345678模式tabcabcaaaNext[j]-100012341固定值过程如下：第一次：abcaabccacabcabcaaaabcabcabcaaa第二次：abcaabccacabcabcaaaabcabcabcaaaabcabcaaaabcabcaaa第三次：abcaabccacabcabcaaaabc第四次：abcaabccacabcabcaaaabc此时:i=4,j=4,匹配失败，而next[j]=next[4]=1,那么下次从i=4,j=1开始此时:i=4,j=1,匹配失败，而next[j]=next[1]=0,那么下次从i=4,j=0开始此时:i=7,j=3,匹配失败，而next[j]=next[3]=0,那么下次从i=7,j=0开始此时:i=7,j=0,匹配失败，而next[j]=next[0]=-1,那么下次从i++,j++开始,即下次i=8,j=0abcabcaaaabcabcaaaabcabcaaa第五次：abcaabccacabcabcaaaabc第六次：abcaabccacabcabcaaaabc第七次：abcaabccacabcabcaaaabc此时:i=9,j=1,匹配失败，而next[j]=next[1]=0,那么下次从i=9,j=0开始此时:i=9,j=0,匹配失败，而next[j]=next[0]=-1,那么下次从i++,j++开始〔i=10,j=0)此时:i=19,j=9,匹配成功，返回v=i-t.curlen=19-9=10KMP算法的:优点：不需回溯。这对于从外设读入的庞大文件很有效，可以边读入边匹配，无须回头重读。前面定义的next函数的缺陷：例如模式串“aaaab”和“aaabaaaaaaaaaaaaaaaaaaaaaaab”匹配时，就会出现重复比较的问题。实际上，当模式串的第4个字符‘a’(i=3)和主串字符‘b’比较不等时，应该滑动至next[i]，即3处与主串的相应字符比较。由于‘a’和串中前三个字符都相等，因此可以直接让模式串第一个字符与主串的第五个字符进行比较。也就是说，如果next[i]=k，而pj=pk，那么当sipj时，显然也不在需要让si与pnext[j]，即pk进行比较了，而只需让si与pnext[k]进行比较。也就是说此时的next[j]值应和next[k]值相同。由此，可得到如下的修改算法。i01234模式串aaaabnext[i]-10123new[i]-1-1-1-13改进KMP算法例子t＝"aabcbabcaabcaababc"n＝18，p＝“abcaababc”,m＝9。KMP算法缺陷：子串：aaaab主串：aaabaaaabj01234子串aaaabnext[j]-10123第一次：aaabaaaabaaaab第二次：aaabaaaab第三次：aaabaaaab第四次：aaabaaaab第五次：aaabaaaabaaaabaaaabaaaabaaaabNext[j]=next[3]=2,下次j=2开始Next[j]=next[2]=1,下次j=1开始Next[j]=next[1]=0,下次j=0开始Next[j]=next[-1]=-1,下次从i++,j++开始〔i=4,j=0)改进的KMP算法：j01234子串aaaabnext[j]-10123Nextval[j]-1-1-1-13第一次：aaabaaaabaaaab第二次：aaabaaaabaaaabi=3,j=3时失败，Nextval[j]=-1,下次j++,i++〔i=4,j=4)开始匹配成功用改进的KMP算法求前例的匹配过程：j012345678模式tabcabcaaaNext[j]-100012341Nextval[j]-100-100-141过程如下：第一次：abcaabccacabcabcaaaabcabcabcaaa第二次：abcaabccacabcabcaaaabcabcabcaaaabcabcaaaabcabcaaa第三次：abcaabccacabcabcaaaabc第四次：abcaabccacabcabcaaaabc此时:i=4,j=4,匹配失败，而nextval[j]=nextval[4]=0,那么下次从i=4,j=0开始此时:i=7,j=3,匹配失败，而nextval[j]=nextval[3]=-1,那么下次从i++,j++开始(i=8,j=0)此时:i=9,j=1,匹配失败，而nextval[j]=0,那么下次从i=9,j=0开始此时:i=9,j=0,匹配失败，而nextval[j]=nextval[0]=-1,那么下次从i++,j++开始,即下次i=10,j=0第五次：abcaabccacabcabcaaaabcabcabcaaa此时:i=19,j=9,匹配成功，返回v=i-t.curlen=19-9=10例：模式串t=“abcaabbabcab”的next函数值序列为___________,nextval函数值序列为_______________.j01234567891011模式tabcaabbabcabNext[j]Nextval[j]intIndex_KMP(SeqStringt,SeqStringp,intpos){ int i,j,*next; next=(int*)malloc(sizeof(int)*(p.n+1)); assert(next); GetNext(p,next); j=pos; i=0; while(i<p.n&&j<t.n) { if(i==-1||p.c[i]==t.c[j]) {/* ‘i==-1’意味着失配且无两个相同子串*/ ++i; ++j; } elsei=next[i]; } free(next); if(i>=p.n)return(j–p.n+1); /*Found*/ else