《算法与数据结构 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?。这实际上也是一个匹配的过程
