答是要 5.1及其操作 的定义 申的基本操作 5.2的表示和实现 °顺序存信表示 中的块链存储表示 5.3的模式匹配算法 求子中位置的定位函数 模式匹配的一种改进算法 5.4操作应用举例 °文本编瓣 °建立词索引表
内容提要 5.1 串及其操作 • 串的定义 • 串的基本操作 5.2 串的表示和实现 • 顺序存储表示 • 串的块链存储表示 5.3 串的模式匹配算法 • 求子串位置的定位函数 • 模式匹配的一种改进算法 5.4串操作应用举例 • 文本编辑 • 建立词索引表
51点现作 1、的逻辑结构定义 中( String(或字符:是军个或多个字符组成的有 限序列。一般记为:s=a1a2.an(20)其中,S是 的名,用单引号括起来的字符序列是的值;a(1≤≤ 1)可以是字母、数字或其他字符;中字符的数目称 为牛的长度。零个字符的称为空生( null string),它 的长度为零。(空与空格的区别) 子:库中在意个连续字符构成的子序列 相等:当且仅当这两个的值相等。也就是说,只 有当两个的长度相等,并且各个对应位置的字符 都相等时才相等 串值必须用一对单引号括起来,但单引号本身不 属于串,它的作用只是为了避免与变量名或数的 常量混淆而已
5.1 串及其操作 1、串的逻辑结构定义 串(String)(或字符串)：是由零个或多个字符组成的有 限序列。一般记为：s=‘a1a2…an’ (n0) 其中，s是串 的名，用单引号括起来的字符序列是串的值；ai(1 i n)可以是字母、数字或其他字符；串中字符的数目n称 为串的长度。零个字符的串称为空串(null string)，它 的长度为零。（空串与空格串的区别） 子串：串中任意个连续字符构成的子序列 串相等：当且仅当这两个串的值相等。也就是说，只 有当两个串的长度相等，并且各个对应位置的字符串 都相等时才相等。 串值必须用一对单引号括起来，但单引号本身不 属于串，它的作用只是为了避免与变量名或数的 常量混淆而已
2.的基本操作 串的基本操作 赋值 复制 比较 求长度 牢连接 子库定位 歌子申 插入 牛删除 牢替换 普通线性表操作的最基本单位是结点, 而字符串操作的基本单位是串或子串
串及其操作(cont’d) 2. 串的基本操作 串的基本操作： 赋值 复制 比较 求长度 串连接 子串定位 取子串 串插入 串删除 串替换 普通线性表操作的最基本单位是结点， 而字符串操作的基本单位是串或子串
52与的表别现 1、字符的存储表示 (1)顺序存储 利用静态数组存放字符串 (2)堆分配存储 利用动态分配的内存存放字符 (3)链式存储 块链结构:#1eN5加决定存储密度 ypedef struct strode tchar sdata N, struct strode *next JSTRNODE, ①合
5.2 串的表示和实现 1、字符串的存储表示 (1)顺序存储 利用静态数组存放字符串 (2)堆分配存储 利用动态分配的内存存放字符串 (3)链式存储 块链结构：#define N 5 //N决定存储密度 typedef struct strnode {char sdata[N]; struct strnode *next; }STRNODE;
的表示别实nt (3)链式存储 块链结构:#1neN5加决定存储密度 typedef struct strode tchar satan; struct strode * next /STRNODE 在D后面插入"OOO"后: ④XEFG一国 ①合
串的表示和实现(cont’d) (3)链式存储 块链结构：#define N 5 //N决定存储密度 typedef struct strnode {char sdata[N]; struct strnode *next; }STRNODE; ABCDE FGH ^ 在D后面插入"OOO"后： ABCDO OOEFG H ^
的表示别实nt 2、字符基本操作的实现 (1)的联接 利用截尾法进行处理 (2)求两个的最长公共子 ①合
串的表示和实现(cont’d) 2、字符串基本操作的实现 (1)串的联接 利用截尾法进行处理 (2) 求两个串的最长公共子串
(2)求两个的最长公共子 ++ y/while( print("最长子串:" for(k=0; k<length, k++)printf("%oc" s[index+k)) printf("n");
void maxcomstr(char s[],char t[])//串采用顺序存储结构 {int index=0,lens,lent,length=0,length1,i=0,j,k; lens=strlen(s);lent=strlen(t); while(ilength){index=i;length=length1;} /*记下最长子串的位置和长度*/ j+=length1;/*从位置j开始找下一个公共子串*/ }//if else j++; }//while (j 串的表示和实现(cont’d) (2)求两个串的最长公共子串 i++; }//while(i printf("最长子串："); for(k=0;k<length;k++)printf("%c",s[index+k]);printf("\n"); }
5.3的模式地算法 1、字符模式匹配 普通算法二 int strindex(char *s, char *t, int beginpos) {/s是主串,t是模式串,从s的 begins处开始查找t的位置 char *n* while(1) ip=s+beginpos q=t Whle(*p&&*q&&*p=*q){p+;q+;} f*q0 )return begins;∥匹配,返回模式串的位置 else if(*p=0) return-1;∥找到模式串,匹配不成功 else begins++;/人 begins+1处开始重新匹配 )//while(1
int strindex(char *s,char *t,int beginpos) {//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)return beginpos; //匹配，返回模式串的位置 else if(*p==0) return -1; //未找到模式串，匹配不成功 else beginpos++;//从beginpos＋1处开始重新匹配 }//while(1 } 5.3 串的模式匹配算法 1、字符串模式匹配 普通算法
的式算法cc 2.字符串模式匹配的KMP算法 第一趟匹配 a ba bca a b 算法思想 a b c 每当一趟匹配过程中出现字 符比较不等时,不需回湧 7 指针,而是利用已经得到的 第二趟匹配 a ba bca bcac ba b a bc ac “部分匹配”的结果将模式 向右“滑动”进可能远的 5 段距离后,继续进行比较。 第三趟匹配 a ba bca bcac b a b (a)bc c 2 6 ①合
算法思想： 每当一趟匹配过程中出现字 符比较不等时，不需回溯i 指针，而是利用已经得到的 “部分匹配”的结果将模式 向右“滑动”进可能远的一 段距离后，继续进行比较。 串的模式匹配算法(cont’d) 2. 字符串模式匹配的KMP算法 第一趟匹配 a b a b c a b c a c b a b a b c i = 3 j = 3 i 第二趟匹配 a b a b c a b c a c b a b a b c a c i = 7 j = 1 j = 5 第三趟匹配 a b a b c a b c a c b a b (a) b c a c i i = 11 j = 2 j = 6
的式算法cc 2.字符串模式匹配的KMP算法 (4)关键一点是滑动到哪里比较合适,也就是说, 如何确定m的值。m被称为k的next值 (5)如果已知k的next值是m,k+1的next值如何 求?这是解决问题的突破口,因为我们已知0 的next值是-1,1的next值是0. 能者为之 ①合
算法思想： (1)对于象"1234abcd"这样的模式串，KMP算法 与普通算法没有什么不同，但对于"123a123b" 这样的模式串，KMP的算法就尽显优势。也就 是说，如果模式串本身包含有自身重复子串， KMP算法会更快。 (2)与普通算法相比，KMP算法在比较失败时， 并没有一切推倒重来，而是巧妙利用的模式串 “包含重复子串”的特征，减少了比较的次数。 串的模式匹配算法(cont’d) (3)用大写字母表示子串，小写字母表示串中的 字符，假设当比较操作进行到主串S的下标j处 时，比较失败。这是模式串T的当前字符的下 标时k，并且T[0..k]=P(T[m])P(T[k]),T[m]!=T[k], 也就是说，比较失败之前的模式串具有重复子 串。这时我们可以将S看成是S=XPaP(S[j])。 面要做的不是将beginpos++，推倒重来，而是 直接将T[m]与S[j]进行比较。这种操作称为模 式串的滑动。每当比较失败就滑动一次，这样 可以有效减少比较次数。 (4)关键一点是滑动到哪里比较合适，也就是说， 如何确定m的值。m被称为k的next值。 (5)如果已知k的next值是m，k+1的next值如何 求？这是解决问题的突破口，因为我们已知0 的next值是－1，1的next值是0. 能者为之 2. 字符串模式匹配的KMP算法