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

3.1字符串及其抽象数据类型1定义字符串简称串，是一种特殊的线性表，其特殊性主要在于表中的每个元素是一个字符。由零个或多个字符组成的有限序列，一般记为s=“a1a2…an”(n0)其中，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(i0)个字符开始连续取j个字符所构成的子串。如：subStr_seq(s,5,3)程序实现s1－－jjMAXNUMnc———————epnksubStr_seq(s,5,5)时if(s-ni+j-1)j=s-n-i+1;s－－m=107MAXNUMnc———————iamaepniPSeqStringsubStr_seq(PSeqStrings,inti,intj){PSeqStrings1;intk;s1=createNullStr_seq();/*创建一空串*/if(s1==NULL)returnNULL;if(i0&&i=s-n&&j0){/*若从i开始取不了j个字符,则能取几个就取几个*/if(s-ni+j-1)j=s-n-i+1;for(k=0;kj;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(i0)个字符开始连续取j个字符所构成的子串。这里首先要为链串结构和头结点申请空间，创建一个空链表，这由算法3.3实现。然后判断所给参数i，j的值是否合理，i，j的取值应为i0，j0。接着从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(i0)个字符开始连续j个字符所构成的子串*/{PLinkStrings1;PStrNodep,q,t;intk;s1=createNullStr_link();/*创建空链串*/if(s1==NULL){printf(Outofspace!\n);returnNULL;}if(i1||j1)return(s1);/*i,j值不合适，返回空串*/p=s-head;for(k=1;ki;k++)/*找开始字符*/if(p!=NULL)p=p-link;算法3.4求单链表示的串的子串elsereturn(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&&kj){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-1p=p0p1…pm-1其中1＜m≤n（通常有mn）。我们的任务是要在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(ip-n&&jt-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);/*匹配成功*/elsereturn(0);/*匹配失败*/}算法3.5朴素的模式匹配算法由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现的。简称KMP算法。设主串S=“ababcabcacbab”,模式串T=“abcac”则普通算法的匹配过程如下：2无回溯的模式匹配第一趟匹配第二趟匹配第三趟匹配第四趟匹配第五趟匹配第六趟匹配ababcabcacbabababcabcacbabababcabcacbabababcabcacbabababcabcacbabababcabcacbababcacabcacabcacabcacabcacabcac未改进时的匹配情况：第一趟匹配第二趟匹配第三趟匹配ababcabcacbabababcabcacbabababcabcacbababcacabcac(a)bcac改进后的匹配情况：改进算法的一般情况：设主串为“t1t2…tn”，模式串为“p1p2…pm”，从上例分析可知，为了实现改进算法，需要解决如下问题：当产生“失配”情况（tjpi）时，模式串应向右滑动多远的距离。即当tj与pi失配时，tj（j指针不回溯）应与模式串的哪一个字符比较。假设此时tj应与模式串的第k（ki）个字符比较，则有如而失配时已经得到的部分匹配结果是：“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}'...''...'