数据结构_字符串操作原理

1、CH4 串串q4.1 串类型的定义串类型的定义q4.2 串的表示和实现串的表示和实现q4.3 串的模式匹配算法串的模式匹配算法n教学目标教学目标n熟悉串的有关概念，串和线性表的关系。熟悉串的有关概念，串和线性表的关系。n掌握串的各种存储结构，比较它们的优、缺点，从而学会掌握串的各种存储结构，比较它们的优、缺点，从而学会在何时选用何种存储结构为宜。在何时选用何种存储结构为宜。n熟练掌握串的七种基本运算，并能利用这些基本运算实现熟练掌握串的七种基本运算，并能利用这些基本运算实现串的其它各种运算。串的其它各种运算。n教学难点教学难点n串运算的实现，特别是顺序串上子串定位的运算（又称串串运算的实现，特

2、别是顺序串上子串定位的运算（又称串的模式匹配或串匹配）。的模式匹配或串匹配）。4.1 串类型的定义串类型的定义n一、串的基本概念一、串的基本概念n串串(String)的定义的定义 s“a1a2an”n其中：其中：ns为串的名字，为串的名字，n串的值串的值nai(1in)一般是字母、数学、标点符号等可屏幕显一般是字母、数学、标点符号等可屏幕显示的字符。示的字符。n串的长度串的长度n。4.1 串类型的定义串类型的定义n字符串与一般的线性表的区别：字符串与一般的线性表的区别：n串的数据元素约束为字符集；串的数据元素约束为字符集；n串的基本操作通常针对串的基本操作通常针对串的整体或串的一个部分串的整体

3、或串的一个部分进行。进行。n问题：为何要单独讨论问题：为何要单独讨论“串串”类型？类型？n字符串操作比其他数据类型更复杂（如拷贝、连接操作）字符串操作比其他数据类型更复杂（如拷贝、连接操作）n程序设计中，处理对象很多都是串类型。程序设计中，处理对象很多都是串类型。4.1 串类型的定义串类型的定义n空串和空白串：空串和空白串：n长度为零的串称为长度为零的串称为空串空串(Empty String)，它不包含任何字符。它不包含任何字符。n空格（白）串空格（白）串:仅由一个或多个空格组成的串称为仅由一个或多个空格组成的串称为空白串空白串(Blank String)n子串和主串子串和主串neg: A“T

4、his is a string” B“is”n特别地：特别地：n空串是任意串的子串，任意串是其自身的子串。空串是任意串的子串，任意串是其自身的子串。n串的相等串的相等二、串的抽象数据类型定义二、串的抽象数据类型定义ADT String数据对象：数据对象：Dai|aiCharacterSet,i1,2,n;n0数据关系：数据关系：S| ai-1， ai D, i 2,n基本操作：基本操作：StrAssign(&T,chars) StrLength(S)SubString(&Sub,S,pos,len)StrCopy(&T,S) Index(S,T,pos)StrEmpty

5、(S) Replace(&S,T,V)StrCompare(S,T) StrInsert(&S,pos,T)Concat(&T,S1,S2) StrDelete(&S,pos,len) ADT String三、三、C语言的串函数语言的串函数n用用C处理字符串时，要调用标准库函数处理字符串时，要调用标准库函数 #includen串长度：串长度：int strlen(char *s);n串比较：串比较：int strcmp(char *str1,char *str2); n串拷贝：串拷贝：char * strcpy(char *str1,char *str2);n串

6、连接：串连接：char * strcat(char *str1,char *str2); n子串子串T定位：定位：char *strchr(char *str,char ch); n子串查找子串查找 ： char *strstr(char *s1,char *s2); n 4.2 串的表示和实现串的表示和实现n串的机内表示方法：串的机内表示方法：定长顺序存储表示（静态数组结构）定长顺序存储表示（静态数组结构）堆分配存储表示（动态数组结构）堆分配存储表示（动态数组结构）串的块链存储表示串的块链存储表示顺序存储：顺序存储：链式存储：链式存储：4.2 串的表示和实现串的表示和实现n 4.2.1 定长

7、顺序存储表示定长顺序存储表示n用一组连续的存储单元来存放串，直接使用定长的字符数用一组连续的存储单元来存放串，直接使用定长的字符数组来定义，数组的上界预先给出，故称为组来定义，数组的上界预先给出，故称为静态存储分配静态存储分配。n存储表示一：存储表示一：#define MAXSTRLEN 255typedef char SStringMAXSTRLEN +1;SString s; n串的结束标志的设置串的结束标志的设置n（1）一般可使用一个不会出现在串中的特殊字符在串值的尾部来）一般可使用一个不会出现在串中的特殊字符在串值的尾部来表示串的结束。表示串的结束。 例如：例如：C语言中以字符语言中以

8、字符0表示串值的终结。表示串值的终结。n（2）可以不设终结符）可以不设终结符 typedef struct char chMAXSTRLEN; int length; SString; n（3）还可以用数组的）还可以用数组的0号单元存储串的长度号单元存储串的长度。算法算法4.2（串的连接算法）（串的连接算法）Status Concat(SString &T,SString S1,SString S2)if (S10+S20=MAXSTRLEN) T1 S10=S11 S10; TS10+1 S10+S20=S21 S20; T0=S10+S20; uncut=TRUE;else if

9、(S10MAXSTRLEN) T1 S10=S11 S10; TS10+1 MAXSTRLEN=S21MAXSTRLEN-S10; T0=MAXSTRLEN;uncut=FALSE; else T0.MAXSTRLEN=S10MAXSTRLEN; uncut=FALSE;return OK;算法算法4.3（取子串）（取子串）Status SubString(SString &Sub,SString S,int pos,int len) if (posS0 |lenS0-pos+1) return ERROR; Sub1 len=Spos pos+len-1 Sub0=len; retu

10、rn OK;/SubString小结：小结：n1.串的定长顺序存储结构又称为串的静态存储结构，即用串的定长顺序存储结构又称为串的静态存储结构，即用一段连续的存储单元来存储串的字符序列。一段连续的存储单元来存储串的字符序列。n2.串的存储结构必须预先定义允许存放串的最大字符个数，串的存储结构必须预先定义允许存放串的最大字符个数，容易造成系统空间浪费或运行出错。容易造成系统空间浪费或运行出错。n3.串的某些操作（如：串的连接、串的替换等）受到限制。串的某些操作（如：串的连接、串的替换等）受到限制。4.2.2 堆分配存储表示堆分配存储表示n特点：特点：n仍用一组连续的存储单元来存放串，但存储空间是在

11、程序仍用一组连续的存储单元来存放串，但存储空间是在程序执行过程中执行过程中动态分配动态分配而得。而得。n思路：思路：n利用利用malloc函数合理预设串长空间。函数合理预设串长空间。n串的动态数组结构体定义如下：串的动态数组结构体定义如下： typedef struct char *ch; int length; HString; 串的赋值算法串的赋值算法 Status StrAssign(HString &T,char *chars) if (T.ch) free (T.ch); for (i=0,c=chars;c;+i,+c); if (!i) T.ch=NULL; T.leng

12、th=0; else T.ch=(char*)malloc(i*sizeof(char); if (!T.ch) exit OVERFLOW; T.ch0i-1=chars0i-1; T.length=i; return OK;n串的比较算法串的比较算法 int StrCompare(HString S,HString T) for (i=0;iS.length& iT.length;+i) if (S.chi!=T.chi ) return S.chi-T.chi; return S.length-T.length; n串的连接算法串的连接算法Status Concat(HStrin

13、g &T,HString S1,HString S2)if (T.ch) free(T.ch);T.ch=(char*)malloc(S1.length+S2.length)*sizeof(char) if (T.ch) exit OVERFLOW;T.ch0S1.length-1=S1.ch0S1.length-1;T.length=S1.length+S2.length;T.chS1.lengthT.length1=S2.ch0S2.length-1;return OK; n取子串算法取子串算法SubString(HString &Sub,HString S,int pos

14、,int len) if (posS.length|lenS.length-pos+1) return ERROR; if (Sub.ch) free(Sub.ch); if (!len) Sub.ch=NULL;Sub.length=0; else Sub.ch=(char*)malloc(len*sizeof(char); Sub.ch0len-1=Spos-1pos+len-2; Sub.length=len; return OK;4.2.3 串的链式存储结构串的链式存储结构n(1)单字符结点链单字符结点链 typedef struct node char data; struct no

15、de *next; *LString; A B C I headn特点：特点：n一个链串由头指针唯一确定。一个链串由头指针唯一确定。n这种结构便于进行插入和删除运算，但存储空间利用率太这种结构便于进行插入和删除运算，但存储空间利用率太低。低。n（2）串的块链结构）串的块链结构n引入目的：提高存储密度引入目的：提高存储密度headA B C D E F G H I # # # NULLn存储表示的定义：存储表示的定义：#define CHUNKSIZE 80typedef struct node char dataCHUNKSIZE; struct node *next; *LString;4.

16、3 串的模式匹配算法串的模式匹配算法n一、基本概念一、基本概念n模式匹配（子串定位）模式匹配（子串定位）n设有主串设有主串S和子串和子串T（将（将S称为目标串，将称为目标串，将T称为模式串），在主串称为模式串），在主串S中，从位置中，从位置start开始查找，如若在主串开始查找，如若在主串S中找到一个与子串中找到一个与子串T相等相等的子串，则返回的子串，则返回T的第一个字符在主串中的位置，否则返回的第一个字符在主串中的位置，否则返回-1。n算法目的算法目的n确定主串中所含子串第一次出现的位置（定位）确定主串中所含子串第一次出现的位置（定位） n算法种类算法种类nBF算法算法 （又称古典的、经典

17、的、朴素的、穷举的）（又称古典的、经典的、朴素的、穷举的）nKMP算法算法n二、二、Brute-Force算法算法n1.算法的设计思想：算法的设计思想：将主串将主串S的第一个字符和模式的第一个字符和模式T的第的第1个字符比较，个字符比较，n若相等，继续逐个比较后续字符；若相等，继续逐个比较后续字符；n若不等，从主串若不等，从主串S的下一字符起，重新与的下一字符起，重新与T第一个字第一个字符比较。符比较。 n直到直到:n主串主串S的一个连续子串字符序列与模式的一个连续子串字符序列与模式T相等。返回相等。返回值为值为S中与中与T匹配的子序列第一个字符的序号，即匹匹配的子序列第一个字符的序号，即匹配

18、成功。配成功。n否则，匹配失败，返回值否则，匹配失败，返回值 1。n2.下面以定长的顺序串类型作为存储结构，给出具体的串下面以定长的顺序串类型作为存储结构，给出具体的串匹配算法。匹配算法。int index(SString S,SString T,int pos) i=pos; j=1; while (i=S0 &jT0) return i T0; else return 0;n显然，该算法在最坏情况下的时间复杂度为显然，该算法在最坏情况下的时间复杂度为O(n-m)m)。n3.BF算法的时间复杂度算法的时间复杂度n若若n为主串长度，为主串长度，m为子串长度，为子串长度，n最好情况：最好

19、情况：n一配就中！一配就中！ 只比较了只比较了m次。次。n最坏情况：最坏情况：n则串的则串的BF匹配算法最坏的情况下需要比较字符的总次匹配算法最坏的情况下需要比较字符的总次数为数为(nm1)m。n4.BF（Brute-Force）算法的特点：算法的特点：n 简单，易于理解，效率较高简单，易于理解，效率较高；n 算法的时间复杂度算法的时间复杂度O(n m)m) 。(其中其中n,m分别为主串分别为主串和模式串的长度）和模式串的长度）n 实际运行中，时间近似于实际运行中，时间近似于 O（nm)。n注意：注意：n当遇到一次当遇到一次sitj,主串要回退到主串要回退到ij+2的位置，而模式串要的位置，而

20、模式串要回到第一个位置（即回到第一个位置（即j1的位置的位置)；n但当一次比较出现但当一次比较出现sitj时，则应该有：时，则应该有： si-j+1si-j+2si-1=t1t2 tj-2tj-1 n改进：改进：n每当一趟匹配过程出现每当一趟匹配过程出现sitj时，主串指示器时，主串指示器i不用回溯，而不用回溯，而是利用已经得到的是利用已经得到的“部分匹配部分匹配”结果，将模式串向右结果，将模式串向右“滑滑动动”尽可能远的一段距离后，继续进行比较。尽可能远的一段距离后，继续进行比较。4.3.2 模式匹配的改进算法模式匹配的改进算法 （KMP算法）算法）n一、分析与示例一、分析与示例 1趟趟ab

21、abcabcacbababc2趟趟ababcabcacbababcac3趟趟ababcabcacbababcac二、讨论一般情况二、讨论一般情况n设设: 主串主串 S= s1s2sisn ， 模式串模式串T = p1p2pjpmn问：问：n当某趟比较发生当某趟比较发生“失配失配”（即（即sipj）时，模式串应该向时，模式串应该向“右右”滑动的可行距离为多长？滑动的可行距离为多长？n解：解：n设某趟匹配发生设某趟匹配发生sipj时，时， si应该与应该与pk（kj）继续比较。继续比较。 根据根据 ：p1p2pk-1 si-k+1si-k+2si-1 pj-k+1pj-k+2pj-1 si-k+1

22、si-k+2si-1 可以推出可以推出：“p1p2pk-1” “pj-k+1pj-k+2pj-1”n示意图如下：示意图如下：主串主串Si ik kj j模式串模式串T令令next(j)knext(j) 0 当当 j=1Maxk|1kj 且且“p1p2pk-1” “pj-k+1pj-k+2pj-1” 当此集合非空当此集合非空 1 其他情况其他情况j12345Pjabcacnext(j)01112例例1：计算如下模式串的：计算如下模式串的next函数值。函数值。n例例2：n计算如下模式串的计算如下模式串的next函数值。函数值。j12345678Pjabaabcacnext(j)01122312K

23、MP算法（算法算法（算法4.6）int Index_KMP(SString S,SString T,int pos) i=pos;j=1; while (i=S0&jT0) return i -T0; else return 0;/ Index_KMP三、模式串的三、模式串的next函数值的求解函数值的求解n由定义知：由定义知：next1=0，n设设nextj=kn表明：表明： p1p2pk-1= pj-k+1pj-k+2pj-1 （其中其中1kj, 且不存在且不存在k(kk)满足上式）满足上式）n问：问：next j+1= k=? 解：解：情况情况1：若若pK = Pj,即即 p1p

24、2 pk-1 pk= pj-k+1pj-k+2 pj-1 pj 则则nextj+1=nextj+1=k+1；情况情况2：若若pK Pj,即即p1p2 pk-1 pk pj-k+1pj-k+2 pj-1 pj,但但 p1p2 pk-1 pj-k+1pj-k+2 pj-1 ,则应将模式向右滑动至模式中的则应将模式向右滑动至模式中的nextk=k个字符比较，重复上述过程直个字符比较，重复上述过程直至至Pj 和模式中的某个字符匹配成功或不存在任何和模式中的某个字符匹配成功或不存在任何k(1kj)满足满足 ，则令则令nextj+1=1。n算法算法4.7void get_next(SString T,in

25、t &next ) i=1;next1=0;j=0; while (iT0) if (j=0&Ti=Tj) +i;+j;nextI=j; else j=nextj; / get_nextn 4.4 串的应用举例串的应用举例n文本编辑文本编辑n文本编辑程序是一个面向用户的系统服务程序，广泛应用文本编辑程序是一个面向用户的系统服务程序，广泛应用于文件的起草、录入、修改、存储、打印。于文件的起草、录入、修改、存储、打印。n在文本编辑器中，处理的对象主要是针对字符串的，所以在文本编辑器中，处理的对象主要是针对字符串的，所以文本编辑器的基本操作，一般包括串的插入、删除、查找、文本编辑器的基本操作，一般包括串的插入、删除、查找、替换、存储及打印等功能。替换、存储及打印等功能。n建立词索引表（信息检索）建立词索引表（信息检索）第第4章小结章小结s =“a1a2 .an”定长顺序存储结构定长顺序存储结构块链存储结构块链存储结构堆存储结构堆存储结构串串逻辑结构逻辑结构存储结构存储结构操作操作(或运算或运算)本章结束本章结束模式匹配算法模式匹配算法若干函数的实现若干函数的实现BF算法算法古典古典KMP算法算法