《算法与数据结构 C语言版 第二版 陈守孔 第4章》由会员分享,可在线阅读,更多相关《算法与数据结构 C语言版 第二版 陈守孔 第4章(38页珍藏版)》请在金锄头文库上搜索。
1、第 4 章 串本章目录w4.1串类型的定义 w4.2串的表示和实现n4.2.1 串的顺序存储结构n4.2.2 串的链式存储结构 w4.3 串的模式匹配 n4.3.1 朴素的模式匹配算法n4.3.2 首尾匹配算法n4.3.3 KMP算法 w4.4 串的应用举例 w4.5 算法设计举例知识点和难点重点w知识点n基本概念n串操作n模式匹配 w难点重点n根据给定操作,编写其它操作的算法(如,根据前5个基本操作,编写index,replacen KMP算法l模式串的next和nextval函数值l手工模拟KMP算法的执行过程n串的其它算法。定义和概念w串(String):由零个或多个字符组成的有限序列。
2、记 为:s=a1a2an(n0) w概念:ns为串名na1a2an为串值nn为串的长度nai,字符nn=0,空串(Null String),记为:n若ai = ,则称为空格串(blank string)n子串:串中任意连续个字符组成的子序列被称 为该串的子串 ,包含子串的串又被称为该子串的主 串 n子串在主串中的位置:n串的相等:两个串的串值相等(两个串的长度 相等,并且各个对应的字符也都相同 )串的操作n串赋值:StringAssign(S,T) n求串长:StringLenth(S) n串判等:StringEqual(S,T) n串联接:StringConcat(S,T) n求子串:Sub
3、String(S,start,length) n子串定位:Index(S,T) n置换:Replace(S,T,V) n插入子串:StringInsert(S,start,T)n删除子串: StringDelete(S,start,length) (其中,前5个操作为基本操作。)串运算举例串运算的例子:长度分别为18、7、3、3;且b、c、d都是a的子串;b在a中的 位置是1,c在a中的位置是12;c和d两串相等 例: a= Welcome to Beijing b= Welcome c= Bei d= Bei 子串定位(index)的实现int Index(String S, String
4、T)若主串S第i个字符之后存在与T相等的子串,则返回T串在S中 的位置,否则返回0n=StringLength(S); m=StringLength(T); i=1;while(istr) free(S-str); 若s已经存在,将它占据的空间释放掉 len= T-length; T串的长度S-length=len; 赋予字符串长度if(!len) 空串S-str=(char*)malloc(sizeof(char); S-str0=0; else 非空串S-str=(char*)malloc(len+1)*sizeof(char);分配空间if(!S-str) return ERROR;fo
5、r(i=0;istri=T-stri; ifreturn OK;StringAssign 基本操作:串联接 int StringConcat(STRING *S,*T) 将串T联接到串S后STRING temp;StringAssign(temp,S); 将S原来的内容保留在temp中S-length=S-length+T-length; 计算S和T的长度之和为S的新长度free(S-str); 释放S原来占据的空间S-str=(char*)malloc(S-length+1)*sizeof(char);重新为S分配空间if(!S-str) return ERROR;else 连接两个串的内容
6、for(i=0;istri=temp.stri;for(j=0;jlength;j+,i+) 将T的值赋在S现有值之后S-stri=T-strj;free(temp.str); 释放为临时串temp分配的空间return OK;if StringConcat int Index(STRING *S,*T)返回子串T在主串S中的位置,若T非S的子串则返回0i=0; j=0; 设置两个扫描指针while(ilength j+; else 对应字符不相等时,重新比较i=i-j+1; j=0; if(j=T-length) return i-T-length+1;返回子串在主串中的位置else ret
7、urn 0; 子串不在主串中Index 基本操作的算法:子串定位定长顺序表示中的C表示方法w在C中,字符串的概念是:以0为结尾的 字符数组。 w初始化:nString s;nS0 = 0;串的链式存储结构w串作为一种特殊的线性表(数据元素为字 符),使用顺序表示时,做插入和删除运算 ,运算量很大,不方便。 w链式存储结构:s p r i n g SS s p r i n g # # # # 串的块链存储结构w直接使用线性链表来存储字符串:效率太低实际分配的存储单元串值所占的存储单元 存储密度 =w 块链式结构的定义#define CHUNKSIZE 80 可由用户定义的块大小 typedef
8、struct Chunk 结点结构char chCHUNKSIZE;struct Chunk *next; Chunk; typedef struct 串的链表结构Chunk *head, *tail; 串的头和尾指针int curlen; 串的当前长度 LString; 块链运算:插入H esi s de nuta# #.tHe is a student.He is a bright student.块链运算:插入H esi b gd eira.#tnhttus 串的模式匹配w子串定位算法Index n基本思想:先以主串S中第一个字符为S 子串的头一个字符,模式串T的长度作为S子 串的长度,
9、得到一个子串去与模式串T中的字 符逐个比较,若子串与模式串相同,即返回S 中子串的第一个字符位置作为模式串在主串S 中的位置;否则,取S中第二个字符为子串头 ,将其往后的字符再依次和模式串T比较判断 是否相等,以此类推直到找到子串位置或没 有一个子串与模式串相同为止 ,前者模式匹 配成功,后者模式匹配失败。朴素的模式匹配 w主串S=ababcabcacbab,模式串T= abcaci=2 第一趟匹配: a b a b c a b c a c b a ba b cj=2i=1 第二趟匹配: a b a b c a b c a c b a baj=0i=6 第三趟匹配: a b a b c a b
10、 c a c b a ba b c a cj=4i=3 第四趟匹配: a b a b c a b c a c b a baj=0i=4 第五趟匹配: a b a b c a b c a c b a baj=0i=10 第六趟匹配: a b a b c a b c a c b a ba b c a c(成功)j=5上面的模式匹配只需三趟w主串S=ababcabcacbab,模式串T= abcaci=3 第一趟匹配: a b a b c a b c a c b a ba b cj=3 (next3=1)i=3 第二趟匹配: a b a b c a b c a c b a ba b c a cj=5
11、 (next5=2 i=7 第三趟匹配: a b a b c a b c a c b a b(a) b c a cj=5 i=7怎么得来的呢?这就是KMP算法。首尾匹配 基本思想:先比较模式串的第一个字符,再比较模式串的最后一个字 符,最后比较模式串中从第二个到第n1个字符。 主串: a b a b c a b c a a a b c b a a b c 模式串: a a (2次)a (1次)a a (2次)a (1次)a (1次)a b c b a (5 次)a (1 次)a (1 次)a a (2 次)a a (2次) a b c b a (5 次)例如主串S=ababcabcaaabcb
12、aabc,模式串 T=abcba 首尾模式匹配int IndexFL(STRING *S,*T)返回子串T在主串S中的位置。若不存在,则函数值为0。其中,T非空。sLength=S-length; tLength=T-length; i=0; StartChar=T-str0; 模式串第一个字符EndChar=T-strT-length-1; 模式串最后一个字符while(istri!=StartChar) +i; 重新查找匹配起始点else if(S-stri+tLength-1!=EndChar) +i;模式串的“尾字符”不匹配,重新查找匹配起始点else 检查中间字符的匹配情况k=1;
13、j=1;while(jstri+k=Tj) +k; +j;if(j=tLength-1) return i+1;else +i; 重新开始下一次的匹配检测return 0;IndexFLKMP算法 wKMPKnuth, Morris, Pratt三人发明 w特点 n无需回溯n在O(nm)的时间量级上完成串的 模式匹配操作 KMP算法假设主串S为s1s2s3sn,模式串T为p1p2tm,若si与tj发生失配,则有:si-j+1si-1=p1pj-1 (1)由(1),若klength +j; 继续比较后继字符else j=nextj; 模式串向右移动whileif(jT-length) return i-T-length+1; 匹配成功else return 0; IndexKMP 对S=aabcbabcaabcaaba,T=bca,画出以T为模 式串,S为目标串的匹配过程。a a b c b a b c a a b c a a b abbb c ab cbb c abca的next值数为: 011利用KMP算法举例如何求next函数已知next1=0,假设nextj=k且 pj=pk,则有 nextj+1=k+1=nextj+1;若nextj=k且 pjpk,则需往 前回溯,检查 pj=p?。这实际上也是一个匹配的过程