《《数据结构串》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《数据结构串》PPT课件.ppt（40页珍藏版）》请在金锄头文库上搜索。
1、1第4章 串 一一、基本内容：基本内容： 本章的基本内容是：串的概念、串的存储结构和串的基本操作。二、学习要点：学习要点：1.熟悉串的基本操作的定义及利用这些操作实 现串的各种操作的方法.2.熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法.3.掌握串的堆存储结构以及在其上实现串操作的基本方法.4.理解串的模式匹配算法及其改进的KMP算法.24.1 串类型的定义 n串串（String）是由零个或多个字符组成的有限序列。通常记作：=c1 c2 cn(n0) 其中，是串名串名；串中的ci（i n）可以是字母、数字、空格或其他字符。用引号括起来的部分是串值串值，即串S的内容，注意引号本身不属于
2、串。串的有关概念如下： 34.1 串类型的定义n(1) 串的长度 串中字符的个数称为串的长度，如上面串的长度为n。n(2) 空串 不含有任何字符的串称为空串( ull String)，空串的长度为零。本教材用符号“”表示空串。 n(3) 空格串 由一个或多个空格构成的串称为空格串（Blank String）, 空格串长度为串中空格的个数。注意空格串不等于空串。44.1 串类型的定义n(4) 子串与主串 串中任意多个连续字符组成的子序列称为该串的子串；包含子串的串称为主串。n(5) 串中位置 字符在序列中的序号称为该字符在串中的位置。n(6) 串相等 两个字符串相等，是指两个字符串的值相等，也就
3、是说这两个字符串不仅长度相等，而且对应位置上的字符也相等。 54.1 串类型的定义n（）串比较 两个串的比较实际上是ASCII码的比较。两个串从第一个位置上的字符开始进行比较，当第一次出现ASCII码大的串为大，若比较过程中出现一个字符串结束的情况，则另一个串为较大者。6n注：注：串的操作是以“串的整体”为操作对象。n注：注：串值必须用一对单引号括起来，但单引号本身不属于串，它的作用只是为了避免与变量名或数的常量混淆而已。n注：注：子串在主串中的位置以子串的第一个字符在主串中的位置来表示。74.1 串类型的定义对于串的基本操作大致有如下几种：n（1）StrAssign (&T, chars)
4、串赋值，将串值chars赋值给串T。n（2）StrCopy(&T,S) 串复制，将一个串s赋给串T。n（3）StrEmpty(s) 判串空，判断串s是否为空。 84.1 串类型的定义n（4）StrCompare(s, t) 串比较，若st，则返回值0；若s= t， 则返回值=0；若st，则返回值0。n（5）StrLength(s) 求串长，返回串s的长度。n（6）StrEqual(s, t) 判断串相等，两个串s和t相等的时候返回1； 否则返回0。 94.1串类型的定义n（7）Concat(&T,s1, s2) 用T返回串s1和串s2连接的结果。n（8）SubString(&Sub,s, po
5、s,len) 用Sub返回串s的第pos个字符开始长度为len的子串。n（9）Index(s, t, pos) 返回子串t在主串S中第pos个字符之后第一次出现 的位置；若子串t不在主串S中，则函数值为0。n（10）StrInsert(&s,pos, t) 将串t插入到s的第pos个位置。104.1串类型的定义n（11）StrDelete(&s, pos, len) 子串删除，删除串s中第pos个字符开始为len的 子串。n（12）Replace(&s, t, v) 子串替换，将串s中所有串t出现的位置均替换 为v。n（13）ClearString(&s) 将s清为空串。n（14）Destro
6、yString(&s) 串s被销毁。114.2 串的表示和实现 因为串是特殊的线性表，故其存储结构与线性表的存储结构类似。只不过由于组成串的结点是单个字符。串有三种机内表示方法:定长顺序存储表示,堆分配存储表示,串的链式存储结构。124.2.1 定长顺序存储表示 定长顺序存储表示,也称为静态存储分配。它是用一组连续的存储单元来存放串中的字符序列。每个串预先分配一个固定长度的存储区域。所谓定长顺序存储结构，是直接使用定长的字符数组来定义，数组的上界预先给出： #define MAXSTRLEN 255 typedef unsigned char sstringMAXSTRLEN+1; sstri
7、ng s; /s是一个可容纳255个字符的顺序 串,0号单元存放串的长度。n实际串长可在所分配的固定长度区域内变动以下标为0的数组分量存放串的实际长度PASCAL；在串值后加入”0”表示结束，此时串长为隐含值C13串联结串联结Status Concat(sstring &t,sstring s1,sstring s2) if (s10+s20)=MAXSTRLEN t.1.s10=s11.s10; t.s10+1.s10+s20=s21.s20; t.0=s10+s20; uncut=TRUE; else if(s10)=MAXSTRLEN t.1.s10=s11.s10; t.s10+1.M
8、AXSTRLEN=s21. MAXSTRLEN-s10; t.0= MAXSTRLEN; uncut=FALSE; else t.1. MAXSTRLEN=s11.MAXSTRLEN; t.0= MAXSTRLEN ;uncut=FALSE; return uncut; 14求子串求子串Status Substring(sstring &sub,sstring s,int pos,int len) if(poss0 | lens.0-pos+1) return ERROR; sub1.len=spos.pos+len-1; sub0=len; return OK; 15 4.2.2 堆分配存储
9、表示n以一组地址连续的存储单元存放串值字符序列；n存储空间动态分配，用malloc()和free()来管理；nP75示例164.2.3 串的块链存储表示n串的链式存储方式n结点大小：一个或多个字符P78图4.2 (a) (b)存储密度=串值所占的存储位/实际分配的存储位17串的基本操作n串插入 Status StrInsert(HString &S,int pos,HString T)n串赋值 Status StrAssign(HString &S,char *chars)n求串长 int StrLength(HString S)n串比较 int StrCompare(HString S,HS
10、tring T)n串联接 Status Concat(HString &S,HString S1,HString S2)n求子串 Status SubString(HString &Sub,HString S,int pos,int len)n串清空 Status ClearString(HString &S)n串定位n删除n置换18Status StrInsert(HString &S,int pos,HString T)（75页）/在串在串S的第的第pos个位置前插入串个位置前插入串Sint i;if (posS.length+1) return ERROR;if (T.length)if
11、 (!(S.ch=(char*) realloc(S.ch,(S.length+T.length)*sizeof(char)exit(OVERFLOW);for (i=S.length-1;i=pos-1;-i)S.chi+T.length=S.chi;for (i=0; i=T.length-1;i+)S.chpos-1+i=T.chi;S.length+=T.length; return OK;19Status StrAssign(HString &S,char *chars)生成一个值等于chars的串S(76页) int i,j; char *c;for (i=0,c=chars;*c
12、;+i,+c);if (!i) S.ch=NULL; S.length=0;else if (!(S.ch=(char *)malloc(i * sizeof(char)exit(OVERFLOW);for (j=0;j=i-1;j+)S.chj=charsj;S.length=i;return OK;20int StrLength(HString S)求串的长度return S.length;21int StrCompare(HString S,HString T)比较两个串，若相等返回0int i;for (i=0;iS.length & iT.length; +i)if (S.chi !
13、= T.chi) return S.chi-T.chi;return S.length-T.length;22Status Concat(HString &S,HString S1,HString S2)用S返回由S1和S2联接而成的新串 int j;if (!(S.ch = (char*)malloc(S1.length+S2.length)*sizeof(char)exit(OVERFLOW);for (j=0;j=S1.length-1;j+) S.chj=S1.chj;S.length=S1.length+S2.length;for (j=0;j=S2.length-1;j+) S.c
14、hS1.length+j=S2.chj;return OK;23Status SubString(HString &Sub,HString S,int pos,int len)用Sub返回串S的第pos个字符开始长度为len的子串if (posS.length | lenS.length-pos+1)return ERROR;if (!len) Sub.ch=NULL; Sub.length=0;else Sub.ch=(char *)malloc(len*sizeof(char);for (int j=0;j=len-1;j+)Sub.chj=S.chpos-1+j;Sub.length=l
15、en;return OK;24Status ClearString(HString &S)将S清为空串if (S.ch) free(S.ch); S.ch=NULL;S.length=0;return OK;254.3 串的模式匹配算法n n定义定义 在串中寻找子串（第一个字在串中寻找子串（第一个字符）在串中的位置符）在串中的位置n n词汇词汇 在模式匹配中，子串称为在模式匹配中，子串称为模模式式，串称为，串称为目标目标。n n示例示例 目标目标 S : S : “BeijingBeijing” 模式模式 P : P : “jinjin” 匹配结果匹配结果 = 4 261.穷举模式匹配n设S=
16、s1,s2,sn(主串)P=p1,p2,pm(模式串)ni为指向S中字符的指针，j为指向P中字符的指针n匹配失败：sipj时，(si-j+1 si-1)=(p1 pj-1)n回溯： i=i-j+2 ; j=1n重复回溯太多，O(m*n)27n n第第第第1 1趟趟趟趟 S S a b b a b a a b b a b a 穷举的模式穷举的模式穷举的模式穷举的模式n n P P a b aa b a 匹配过程匹配过程匹配过程匹配过程n n n n第第第第2 2趟趟趟趟 S S a b b a b a a b b a b an n P P a b a a b an n n n第第第第3 3趟趟趟
17、趟 S S a b b a b a a b b a b an n P P a b a a b an nn n第第第第4 4趟趟趟趟 S S a b b a b aa b b a b an n P P a b aa b an n 28求子串位置的定位函数int Index(SString S, SString T,int pos) /穷举的模式匹配穷举的模式匹配int i=pos;int j=1;while (i=S0 & jT0) return i-T0; /匹配成功匹配成功匹配成功匹配成功else return 0;292.KMP快速模式匹配nD.E.Knuth, J.H.Morris, V
18、.R.Pratt同时发现n无回溯的模式匹配30nS s1 si-j-1 si-j si-j+1 si-j+2 si- -1 si si+1 snn n P p1 p2 pj- -1 pj pj+1 pm pmn n 则有则有则有则有 si-j+1 si-j+2 si-1 = p1 p2 pj-1 (1)n n 为使模式为使模式为使模式为使模式 P P 与目标与目标与目标与目标 S S 匹配，必须满足匹配，必须满足匹配，必须满足匹配，必须满足n p1 p2 pj-1 pj pm = si-j+1 si-j+2 si-1 si si-j+mn n 如果如果如果如果 p1 pj-2 p2 p3 pj
19、-1 (2)n n 由由由由(1)(2)(1)(2)则立刻可以断定则立刻可以断定则立刻可以断定则立刻可以断定n p1 pj-2 si-j+2 si-j+3 si-1n n 下一趟必不匹配下一趟必不匹配下一趟必不匹配下一趟必不匹配31n n同样，若同样，若同样，若同样，若 p1 p2 pj-3 p3 p4 pj-1n n则再下一趟也不匹配，因为有则再下一趟也不匹配，因为有则再下一趟也不匹配，因为有则再下一趟也不匹配，因为有n p1 pj-3 si-j+3 si-1n n直到对于某一个直到对于某一个直到对于某一个直到对于某一个“ “k” ”值，使得值，使得值，使得值，使得n p1 pk pj-k
20、pi-k+1 pj-1n n且且且且 p1 pk-1 = pj-k+1 pj-k+2 pj-1n n则则则则 p1 pk-1 = si-k+1 si-k+2 si-1n n pj-k+1 pj-k+3 pj-1n n模式右滑模式右滑模式右滑模式右滑j-kj-k位位位位32next数组值n n假设当模式中第假设当模式中第假设当模式中第假设当模式中第j j个字符与主串中相应字符个字符与主串中相应字符个字符与主串中相应字符个字符与主串中相应字符“ “失失失失配配配配” ”时，可以拿第时，可以拿第时，可以拿第时，可以拿第k k个字符来继续比较，则令个字符来继续比较，则令个字符来继续比较，则令个字符来继
21、续比较，则令nextj=knextj=kn nnextnext函数定义：函数定义：函数定义：函数定义： 0 0 当当当当j=1j=1时时时时 nextj= Maxk| 1kj nextj= Maxk| 1kj 且且且且 p p1 1p pk-1k-1 = = p pj-k+1j-k+1p pj-1j-1 当此集合不空时当此集合不空时当此集合不空时当此集合不空时 1 1 其他情况其他情况其他情况其他情况33手工求next数组的方法n n序号序号j 1 2 3 4 5 6 7 8n n模式模式P a b a a b c a cn n k 1 1 2 2 3 1 2n nPk=Pj = = = n
22、nnextj 0 1 1 2 2 3 1 2 n nNextvalj 0 1 0 2 1 3 0 234n n运用运用运用运用KMPKMP算法的匹配过程算法的匹配过程算法的匹配过程算法的匹配过程n n第第第第1 1趟趟趟趟 目标目标目标目标 a c a b a a b a a b c a c a a b cn 模式模式模式模式 a b a a b c a cn next(2) = 1 = 1n n第第第第2 2趟趟趟趟 目标目标目标目标 a c a b a a b a a b c a c a a b cn 模式模式模式模式 a b a a b c a c next(1)=0n n第第第第3 3
23、趟趟趟趟 目标目标目标目标 a c a b a a b a a b c a c a a b cn 模式模式模式模式 a b a a b c a cn next(6)next(6) = 3 = 3 n n第第第第4 4趟趟趟趟 目标目标目标目标 a c a b a a b a a b c a c a a b cn 模式模式模式模式 (a b) a a b c a cn 35KMP算法int Index_KMP(SString S, SString T, int *next)int i,j;i=1; j=1;while (i=S0 & jT0) return i-T0;else return 0;
24、36求next数组的步骤(1)next1=0 i=1; j=0; (2)设nexti=j 若j=0, nexti+1=1 若Pi=Pj, nexti+1=j+1=nexti+1 若Pi Pj, nexti+1=nextj+1 参看教材p8283递推过程37求next数组的函数void get_next(SString S, int *next)int i,j;i=1;next1=0; j=0;while (iS0) if (j=0 | Si=Sj) +i; +j; nexti=j;else j=nextj;38改进的求next数组方法设nexti=j若Pi=Pj, 则nextvali=next
25、valj39改进的求next数组的函数void get_nextval(SString S, int *nextval)int i,j;i=1;nextval1=0;j=0;while (iS0) if (j=0 |Si=Sj)+i;+j;if (Si!=Sj) nextvali=j;else nextvali=nextvalj;else j=nextvalj;40n n穷举的模式匹配算法时间代价：穷举的模式匹配算法时间代价：穷举的模式匹配算法时间代价：穷举的模式匹配算法时间代价：n n 最坏情况比较最坏情况比较最坏情况比较最坏情况比较n-mn-m+1+1趟，每趟，每趟，每趟，每趟比较趟比较趟
26、比较趟比较mm次，次，次，次，n n 总比较次数达总比较次数达总比较次数达总比较次数达( (n-m+n-m+1)*1)*mmn n 原因在于原因在于原因在于原因在于每趟重新比较时，目标串的检每趟重新比较时，目标串的检每趟重新比较时，目标串的检每趟重新比较时，目标串的检n n 测指针要回退。改进的模式匹配算法可测指针要回退。改进的模式匹配算法可测指针要回退。改进的模式匹配算法可测指针要回退。改进的模式匹配算法可n n 使目标串的检测指针每趟不回退。使目标串的检测指针每趟不回退。使目标串的检测指针每趟不回退。使目标串的检测指针每趟不回退。n n 改进的模式匹配改进的模式匹配改进的模式匹配改进的模式
27、匹配(KMP)(KMP)算法的时间代价：算法的时间代价：算法的时间代价：算法的时间代价：n n 若每趟第一个不匹配，比较若每趟第一个不匹配，比较若每趟第一个不匹配，比较若每趟第一个不匹配，比较n-mn-m+1+1趟，趟，趟，趟，总比较次总比较次总比较次总比较次数最坏达数最坏达数最坏达数最坏达( (n-mn-m)+)+m = nm = nn n 若每趟第若每趟第若每趟第若每趟第mm个不匹配，总比较次数最坏亦达到个不匹配，总比较次数最坏亦达到个不匹配，总比较次数最坏亦达到个不匹配，总比较次数最坏亦达到 n n n n求求求求nextnext函数的比较次数为函数的比较次数为函数的比较次数为函数的比较次数为m, m, 所以总的时间复杂度所以总的时间复杂度所以总的时间复杂度所以总的时间复杂度是是是是O(n+m)O(n+m)
