数据结构第4章串

计算机学院第2章线性表第3章栈和队列第4章串第5章数组和广义表

可表示为：（a1,a2,……,an）线性结构计算机学院串比较，strcmp(chars1,chars2)串复制，strcpy(charto,charfrom)串连接，strcat(charto,charfrom)求串长，strlen(chars)

……调用标准库函数#include<string.h>补充：C语言中常用的串运算计算机学院第4章串4.1串类型的定义4.2串的表示和实现4.3串的模式匹配算法

4.3.1求子串位置的定位函数

教学内容计算机学院1.理解串的基本操作的定义，并能利用这些基本操作来实现串的其它各种操作的方法；2.了解在串的顺序存储结构上实现的各种操作的方法；3.掌握串的模式匹配的算法4.了解串操作的应用方法和特点

教学目标计算机学院4.1串类型的定义串(String)----零个或多个字符组成的有限序列串名串值串长n空串n=0计算机学院a=‘BEI’,b=‘JING’

c=‘BEIJING’

d=‘BEIJING’子串字符位置主串子串位置串相等空格串计算机学院数据对象:数据关系:基本操作:(1)

StrAssign(&T,chars)//串赋值(2)StrCompare(S,T)//串比较(3)StrLength(S)//求串长(4)Concat(&T,S1,S2)//串联ADTString{串的抽象数据类型计算机学院

(5)SubString(&Sub,S,pos,len)//求子串

(6)StrCopy(&T,S)//串拷贝

(7)StrEmpty(S)//串判空

(8)ClearString(&S)//清空串

(9)Index(S,T,pos)//子串的位置

(11)Replace(&S,T,V)//串替换

(12)StrInsert(&S,pos,T)//子串插入

(12)StrDelete(&S,pos,len)//子串删除

(13)DestroyString(&S)//串销毁}ADTString计算机学院4.2串的表示和实现定长顺序表示堆分配存储表示串的块链存储表示计算机学院定长顺序表示#defineMAXSTRLEN255//用户可在255以内定义最大串长typedefunsignedcharSString[MAXSTRLEN+1];//0号单元存放串长计算机学院串连接的实现（a)S1[0]+S2[0]MAXSTRLEN计算机学院串连接的实现（b)S1[0]<MAXSTRLEN而

S1[0]+S2[0]>MAXSTRLEN计算机学院串连接的实现（c)S1[0]=MAXSTRLEN

计算机学院串连接（算法4.2）--了解计算机学院求子串计算机学院求子串（算法4.3）--了解计算机学院typedefstruct{char*ch;//若串非空,则按串长分配存储区,//否则ch为NULLintlength;//串长度}HString;

堆分配存储表示相关算法（75－77页）--了解计算机学院串的块链存储表示计算机学院#defineCHUNKSIZE80//可由用户定义的块大小typedefstructChunk{charch[CHUNKSIZE];structChunk*next;}Chunk;typedefstruct{Chunk*head,*tail;//串的头指针和尾指针

intcurlen;//串的当前长度}LString;

串的块链存储表示计算机学院可将多个字符存放在一个结点中，以克服其缺点优点：操作方便缺点：存储密度较低实际分配的存储位串值所占的存储位存储密度=串的块链存储表示计算机学院4.3串的模式匹配算法

算法目的：BF算法（又称古典的、经典的、朴素的、穷举的）KMP算法（特点：速度快）算法种类：确定主串中所含子串第一次出现的位置（定位）即如何实现教材P71Index(S,T,pos)函数计算机学院

S:ababcabcacbabT:abcijS:ababcabcacbab T:abcS:ababcabcacbabT:abci指针回溯BF算法设计思想计算机学院将主串的第pos个字符和模式的第一个字符比较，若相等，继续逐个比较后续字符；若不等，从主串的下一字符起，重新与模式的第一个字符比较。直到主串的一个连续子串字符序列与模式相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。否则，匹配失败，返回值0BF算法设计思想Index(S,T,pos)计算机学院例：S=‘ababcabcacbab’，T=‘abcac’，pos=1，

求：串T在串S中第pos个字符之后的位置图4.3，可利用演示系统看BF算法执行过程BF算法示例计算机学院intIndex(SstringS,SstringT,intpos){i=pos;j=1;while(i<=S[0]&&j<=T[0]){if(S[i]==T[j]){++i;++j;}else{i=i-j+2;j=1;}if(j>T[0])returni－T[0];elsereturn0;}BF算法描述（算法4.5）计算机学院若n为主串长度，m为子串长度，最坏情况是BF算法时间复杂度主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位各比较了m次最后m位也各比较了1次总次数为：(n-m)*m+m＝(n-m+1)*m若m<<n，则算法复杂度O(n*m)例：S=‘0000000001’，T=‘0001’，pos=1计算机学院KMP（KnuthMorrisPratt）算法/~knuth/《计算机程序设计艺术第1卷基本算法》

98元《计算机程序设计艺术第2卷半数值算法》98元《计算机程序设计艺术第3卷排序与查找》98元KMP算法（特点：速度快）①KMP算法设计思想②KMP算法的推导过程③KMP算法的实现

（关键技术:计算next[j]）④KMP算法的时间复杂度能否利用已经部分匹配的结果而加快模式串的滑动速度？能！而且主串S的指针i不必回溯！可提速到O(n+m)！例：①KMP算法设计思想：(参见教材P80-84）S=‘ababcabcacbab’T=‘abcac’S=‘ab

abca

bcacbab’T=‘abca

c’S=‘ab

abca

bcacbab’T=‘a

bcac’Index_kmp的返回值应为i=6需要讨论两个问题：①如何“记忆”部分匹配结果？②如何由“记忆”结果计算出主串S第i个字符应该与模式T中哪个字符再比较？即确定模式T中的新比较起点k.iiikk

a

b

aa

b

c②KMP算法的推导过程：（见教材P81）抓住部分匹配结果的两个特征：两式联立可得：‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’注意：j为当前已知的失配位置，我们的目标是计算新起点k，仅剩一个未知数k，理论上已可解，且k仅与模式串T有关！则S前i-1～i-(k-1)位＝T的j-1～j-(k-1)位即(4-3）式含义S=‘ababca

b

cacbab’T=‘a

b

cac’ik则T的k-1～1位＝S前i-1～i-(k-1)位

即(4-2）式含义ikjS=‘ababca

bcacbab’T=‘abca

c’刚才肯定是在S的i处和T的第j字符处失配设目前应与T的第k字符开始比较②KMP算法的推导过程(续）：根据模式串T的规律：‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’和已知的当前失配位置j，可以归纳出计算新起点k的表达式。令k=next[j]，则next[j]＝0当j＝1时max{k|1<k<j且‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’}1其他情况讨论：①next[j]有何意义？一旦失配，应从模式串T中第next[j]个字符开始与S的失配点i重新匹配!②next[j]怎么求？后面会举例（参见教材P81）第一步，先把模式T所有可能的失配点j所对应的next[j]计算出来；第二步：执行定位函数index_kmp（与BF算法模块非常相似）③KMP算法的实现—即Index()操作的实现（见教材P82）

IntIndex_KMP(SStringS,SStringT,intpos){i=pos;j=1;while(i<=S[0]&&j<=T[0]){if(j==0||S[i]==T[j]){++i,++j}//不失配则继续比较后续字符

else{j=next[j];}//S的i指针不回溯，从T的k位置开始匹配

}if(j>T[0])returni-T[0];//子串结束，说明匹配成功

elsereturn0;}//Index_KMP怎样计算模式T所有可能的失配点j所对应的next[j]？例：模式串T：abaabcac

可能失配位

j：12345678新匹配位next[j]:next[j]＝0当j＝1时max{k|1<k<j且‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’}1其他情况01122312讨论：j=1时,next[j]≡

0；因为属于“j=1”;j=2时,next[j]≡

1；因为属于“其他情况”；刚才已归纳：j=3时,k={2}，只需查看‘T1’=‘T2’；j=4时,k={2，3}，要查看‘T1’=‘T3’和‘T1T2’=‘T2T3’j=5时,k={2，3，4}，要查看‘T1’=‘T4’、‘T1T2’=‘T3T4’和‘T1T2T3’=‘T2T3T4’以此类推，可得后续next[j]值。讨论两个有关next[j]的问题：①怎样简捷计算next[j]？可用递推法编程实现！（参见P83简捷算法）计算next[j]的时间为O(m)voidget_next(SStringT,int&next[]){//next函数值存入数组nexti=1;next[1]=0;j=0;while(i<T[0]){if(j==0||T[i]==T[j]){++i;++j;next[i]=j;}elsej=next[j];}}//get_nextvoidget_nextval(SStringT,int&nextval[]){//next函数修正值存入数组nextvali=1;nextval[1]=0;j=0;while(i<T[0]){if(j==0||T[i]==T[j]){++i;++j;If(T[i]!=T[j])nextval[i]=j;elsenextval[i]=nextval[j];}elsej=nextval[j];}}//get_nextval②next[j]是否完美无缺？答：未必，例如当S=‘abaaaab’,T=‘aaaab’时仍有多余动作（参见P84改进算法,

称为nextval[j]）i=1;j=0next[1]=0i<T[0]j==0||T[i]==T[j]++i;++j;next[j]=j;j=next[j];ENDYYNN附：求解next[j]算法流程图:例如：求abaabcac模式串的next函数next[1]=0next[2]=1pnex