算法与数据结构：第四章 串

1、数据结构-第四章 串1第四章 串 串是特殊的线性表，数据元素是单个字符。线性表的操作通常以“数据元素”为操作对象；串的操作主要以“子串”为操作对象。4.1 串类型的定义4.2 串的存储结构和操作的实现4.3 串的模式匹配算法4.4 串应用示例文本编辑本章学习要点及习题数据结构-第四章 串24.1 串类型的定义4.1.1 串的概念 串（字符串）：是由零个或多个字符组成的有限序列。 记作：s = a1a2an (n0) 串长：串中字符的个数n。 子串和主串：串中任意个连续的字符组成的子序列称 为该串的子串。包含子串的串称为主串。 串相等：两个串长度相等，且对应位置的字符都相等。 空串和空白串：空串

2、不包含任何字符,表示为 ； 空白串由一个或多个空格组成，如 。数据结构-第四章 串34.1.2 串的常用基本操作 (1)用串常量赋值 StrAssign(&T, chars) 用串变量赋值 StrCopy(&T, S) (2)判定空串 StrEmpty(S) (3)两串比较 StrCompare(S, T) (4)求串长 StrLength(S) (5)串清空 ClearString(&S) (6)两串连接 Concat(&T, S1, S2) (7)求子串 SubString(&Sub, S, pos, len) (8)子串定位 Index(S, T, pos) (9)子串置换 Replac

3、e(&S, T, V) (10)插入子串 StrInsert(&S, pos, T) (11)删除子串 StrDelete(&S, pos, len) (12)串销毁 DestroyString(&S)串类型的最小操作子集数据结构-第四章 串4例 设s=I am a student. t=OK! p=student q=nurse r=good (1) Concat(newstr, s, t ) newstr= I am a student. OK! (2) Replace(s, p , q); s=I am a nurse. (3) StrInsert(s, 8, r) s=I am a g

4、ood nurse. 数据结构-第四章 串54.2 串的存储结构和操作的实现4.2.1 串的顺序存储结构（1）定长顺序存储表示7 s t u d e n t0 1 2 3 4 5 6 7 8MAXSTRLEN#define MAXSTRLEN 255 /予定义最大串长typedef unsigned char SStringMAXSTRLEN+1;存放串的长度存储定义B O O K 0C语言本身的串表示方式：不便于求串长等操作数据结构-第四章 串6基本操作实现示例约定：串值长度上溢时，用“截尾法”处理， 即 “截断”超过予定义长度的部分。int StrCompare(SString S, SS

5、tring T)/ST,返回值0；S=T，返回0；ST，返回值 0 for (i=1; i=S0 & i=T0; i+) if (Si != Ti ) return(Si - Ti ); return S0-T0 / StrCompare操作基于“字符序列复制”i数据结构-第四章 串7 Status Concat(SString &T, SString S1, SString S2) /用T返回串s1和s2联接而成的新串。 /若未截断，返回TRUE，否则返回FALSE if ( S10+S20 = MAXSTRLEN ) T1.S10 = S11.S10; Ts10+1.S10+S20 = S

6、21.S20; T0= S10+S20; uncut=TRUE; else if (S10MAXSTRLEN) T1.S10 = S11.S10; Ts10+1.MAXSTRLEN = S21.MAXSTRLEN-S10; T0= MAXSTRLEN; uncut=FALSE; else T0.MAXSTRLEN= S10.MAXSTRLEN; uncut= FALSE; return uncut; / Concat数据结构-第四章 串8 Status SubString(SString &Sub, SString S, int pos, int len) /用Sub返回串S从第pos个字符起

7、长度为len的子串 if ( (posS0 | len S0-pos+1 )return ERROR; Sub1.len= Spos.pos+len-1; Sub0= len return OK; / SubString0 1 poslenSSub数据结构-第四章 串9（2）堆分配存储表示动态分配串值存储空间，避免定长结构的截断现象。typedef struct char *ch; /串空间基址，按串长申请int length; /串长度HString;存储定义数据结构-第四章 串10基本操作实现示例int StrCompare(HString S, HString T) /ST,返回值0；S

8、=T，返回0；ST，返回值 0 for (i=0; iS.length & iT.length; i+) if (S.chi != T.chi ) return S.chi - T.chi ); return S.length-T.length ; / StrCompareS1S2数据结构-第四章 串11 Status Concat(HString &T, HString S1, HString S2) /返回串S1和S2联接而成的新串T if (T.ch) free(T.ch); /释放T原有空间 if ( ! (T.ch=(char *)malloc(S1.length+S2.length

9、)* sizeof(char) exit(OVERFLOW); T.length=S1.length+S2.length; T.ch0.s1.length-1=S1.ch0.s1.length-1; T.chS1.length. T.length-1=S2.ch0.S2.length-1; return OK; / ConcatS1S2T数据结构-第四章 串12 Status SubString(HString &Sub, HString S, int pos, int len) /求串S从第pos个字符起长度为len的子串Sub if ( (posS.length | len S.lengt

10、h-pos+1 )return ERROR; if (Sub.ch) free(Sub.ch); if ( !len ) Sub.ch=NULL; Sub.length=0; else if ( !(Sub.ch=(char *)malloc(len* sizeof(char) exit(OVERFLOW); Sub.ch0.len-1=S.chpos-1.pos+len-2; Sub.length=len; return OK; / SubStringpos-10lenS.length-1数据结构-第四章 串134.2.2 串的块链存储结构ABOOK S.headS.tailA B OO K

11、 # # S.headS.tail设置尾指针便于联结操作#define CHUNKSIZE 4 /由用户定义块大小typedef struct Chunk char chCHUNKSIZE; struct Chunk * next;Chunk;typedef struct Chunk * head， * tail; /串的、尾头指针 int curlen; /串的当前长度LString;占用存储量大且操作不便，实际应用很少。数据结构-第四章 串144.3 串的模式匹配算法模式匹配 即子串的定位操作。 是各种串处理系统中最重要的操作之一。操作定义 Index（S，T， pos） S主串，T子串

12、pos从该位序字符开始向后寻找匹配例 S=abcabcdefabcdmn T=efapq 匹配失败 T=bcd 匹配成功，有效位移 =5以定长顺序存储结构讨论算法实现。数据结构-第四章 串154.3.1 朴素的模式匹配算法主串S子串T1 posn(S0)m(T0)i=pos;j=1;1子串Ti=pos+1;j=1;失配1主串S子串T1nmiji-j+1回溯 ：i=i-j+2;j=1;失配ST1 n1n-m+1m数据结构-第四章 串16 int Index(SString S, SString T, int pos) /返回子串T在主串S中从第pos个字符开始的位置。 /若不存在，返回值为0。1

13、posStrLength(S) i=pos; j=1; /设定主串、子串字符开始比较的位置 while ( i=S0 & j T0 ) return i-T0 ; /匹配成功 else return 0; / Index最坏情况字符比较次数为：(n-m+1)m算法复杂度: O(mn)数据结构-第四章 串174.3.2 模式匹配的一种改进算法(KMP算法)改进之处 在比较过程中，主串的下标i只增不减，不回溯，可使算法复杂度提高到O(m+n) 。分析 1 2 3 4 5 6 7 8 9 10 11 12 13 主串s a b c d a b c d a b e g h s1s2sn 子串t a b

14、 c d a b e g p1p2pm mni=7j=7a b c d a b e gj=3本趟比较失配点：i=7, j=7 (即s7p7) 失配点处 p1p2=s5s6=p5p6 p1pk-1=pj-k+1pj-1下趟比较：i不变，j=k(此处即3)数据结构-第四章 串18引入next数组nextj=k：k是当模式(子串)中第j个字符与主串中相应字符“失配”时，在模式中需重新和主串中该字符进行比较的字符的位置。 0 当 j=1 时 代表下一趟比较i=i+1，j=1 maxk |1kj 且 p1pk-1=pj-k+1pj-1 当此集合不空时 1 其它情况(即j1且上述集合为空)例 a b c

15、d a b c d a b e g h a a a a a nextj 0 1 1 1 1 2 3 4 5 6 7 1 1 0 1 2 3 4nextj=下一趟比较i不变，j=k下一趟比较i不变，j=1kjk-1k-1k-1stik数据结构-第四章 串19KMP算法描述int index_KMP(SString S, SString T, int pos) i=pos; j=1; while (i = S0 & j T0) return i-T0; else return 0;/index_KMPposij数据结构-第四章 串20求next数组值算法思想：利用递推 即已知next1=0, ne

16、xtj=k; 求nextj+1 主串 p1 . pj-k+1pj-k+2 pj-1 pj pj+1 pm 子串 p1 p2 pk-1 pk . pm算法描述p1p2 . pnextk . . . pmvoid get_next(SString T, int &next ) j=1; k=0; next1=0; while ( jT0 ) if ( k=0 | Tj=Tk ) +j; +k; nextj=k; else k= nextk; /get_nextj j+1k-1数据结构-第四章 串21修正next数组Next数组的缺陷 s= a b c a b c a x a b c a b c a

17、 b b a c t= a b c a b c a b b a c next8=5 a b c a b c a b b a c next5=2 a b c a b c a b b a c next2=1 a b c a b c a b b a c 存在p8=p5=p2, 因此当s8p8时，s8与p5 、 p2的比较是无意义的。改进方法 用nextval数组代替next数组 求出Pj处的k值；若Pj=Pk，则nextvalj=nextvalk 否则nextvalj=kij数据结构-第四章 串22例 j 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 a b c a b c a

18、 b b a c a a a a b nextj 0 1 1 1 2 3 4 5 6 1 2 0 1 2 3 4 nextvalj 0 1 1 0 1 1 0 1 6 0 2 0 0 0 0 4算法描述void get_nextval(SString T, int &nextval ) j=1; k=0; nextval1=0; while ( jT0 ) if (k=0 | Tj=Tk) +j; +k; if ( Tj != Tk ) nextvalj=k; else nextvalj=nextvalk; else k=nextvalk; /get_nextval数据结构-第四章 串23KMP算法时间复杂度分析 get_nextval（）； index_KMP（）； 通常，模式串长度m主串长度n求next(nextval)数组：O(m) 主串与模式串匹配： O(n) 整个匹配算法O(m+n) 数据结构-第四章 串244.4 串应用示例文本编辑分析操作对象 文本串 （行是文本串的子串）基本操作查找插入删除轻轻的我走了，正如我轻轻的来；我轻轻的招手，作别西天的云彩。那河畔的金柳，是夕阳中的新娘波光里的艳影，在我的心头荡漾。软泥上的青荇，油油的在水底招摇；在康河的柔波里，我甘