【大学数据结构课件】串

《【大学数据结构课件】串》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、内容提要5.1串及其操作串的定义串的基本操作5.2串的表示和实现顺序存储表示串的块链存储表示5.3串的模式匹配算法求子串位置的定位函数模式匹配的一种改进算法5.4串操作应用举例文本编辑建立词索引表5.1串及其操作1、串的逻辑结构定义串(String)(或字符串)：是由零个或多个字符组成的有限序列。一般记为：s=‘a1a2…an’(n0)其中，s是串的名，用单引号括起来的字符序列是串的值；ai(1in)可以是字母、数字或其他字符；串中字符的数目n称为串的长度。零个字符的串称为空串(nullstring)，

2、它的长度为零。（空串与空格串的区别）子串：串中任意个连续字符构成的子序列串相等：当且仅当这两个串的值相等。也就是说，只有当两个串的长度相等，并且各个对应位置的字符串都相等时才相等。串值必须用一对单引号括起来，但单引号本身不属于串，它的作用只是为了避免与变量名或数的常量混淆而已。串及其操作(cont’d)2.串的基本操作串的基本操作：赋值复制比较求长度串连接子串定位取子串串插入串删除串替换普通线性表操作的最基本单位是结点，而字符串操作的基本单位是串或子串5.2串的表示和实现1、字符串的存储表示(1)顺序存储利用

3、静态数组存放字符串(2)堆分配存储利用动态分配的内存存放字符串(3)链式存储块链结构：#defineN5//N决定存储密度typedefstructstrnode{charsdata[N];structstrnode*next;}STRNODE;串的表示和实现(cont’d)(3)链式存储块链结构：#defineN5//N决定存储密度typedefstructstrnode{charsdata[N];structstrnode*next;}STRNODE;ABCDEFGH^在D后面插入"OOO"后：ABCDO

4、OOEFGH^串的表示和实现(cont’d)2、字符串基本操作的实现(1)串的联接利用截尾法进行处理(2)求两个串的最长公共子串voidmaxcomstr(chars[],chart[])//串采用顺序存储结构{intindex=0,lens,lent,length=0,length1,i=0,j,k;lens=strlen(s);lent=strlen(t);while(i

5、)//遇到相等的字符,继续找相等字符构成子串{length1=1;for(k=1;s[i+k]==t[j+k];k++)length1++;if(length1>length){index=i;length=length1;}/*记下最长子串的位置和长度*/j+=length1;/*从位置j开始找下一个公共子串*/}//ifelsej++;}//while(j串的表示和实现(cont’d)(2)求两个串的最长公共子串i++;}//while(iprintf("最长子串：");for(k=0;k

6、k++)printf("%c",s[index+k]);printf("");}intstrindex(char*s,char*t,intbeginpos){//s是主串，t是模式串，从s的beginpos处开始查找t的位置char*p,*q;while(1){p=s+beginpos;q=t;while(*p&&*q&&*p==*q){p++;q++;}if(*q==0)returnbeginpos;//匹配，返回模式串的位置elseif(*p==0)return-1;//未找到模式串，匹配不成功els

7、ebeginpos++;//从beginpos＋1处开始重新匹配}//while(1}5.3串的模式匹配算法1、字符串模式匹配普通算法算法思想：每当一趟匹配过程中出现字符比较不等时，不需回溯i指针，而是利用已经得到的“部分匹配”的结果将模式向右“滑动”进可能远的一段距离后，继续进行比较。串的模式匹配算法(cont’d)2.字符串模式匹配的KMP算法第一趟匹配ababcabcacbababci=3j=3i第二趟匹配ababcabcacbababcaci=7j=1j=5第三趟匹配ababcabcacbab(a)b

8、cacii=11j=2j=6算法思想：(1)对于象"1234abcd"这样的模式串，KMP算法与普通算法没有什么不同，但对于"123a123b"这样的模式串，KMP的算法就尽显优势。也就是说，如果模式串本身包含有自身重复子串，KMP算法会更快。(2)与普通算法相比，KMP算法在比较失败时，并没有一切推倒重来，而是巧妙利用的模式串“包含重复子串”的特征，减少了比较的次数。串的模式匹配算法(cont’d