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

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

s＝“a1a2…an”其中：s为串的名字，串的值ai(1≤i≤n)一般是字母、数学、标点符号等可屏幕显示的字符。串的长度n。4.1串类型的定义字符串与一般的线性表的区别：串的数据元素约束为字符集；串的基本操作通常针对串的整体或串的一个部分进行。问题：为何要单独讨论“串”类型？字符串操作比其他数据类型更复杂（如拷贝、连接操作）程序设计中，处理对象很多都是串类型。4.1串类型的定义空串和空白串：长度为零的串称为空串(EmptyString)，它不包含任何字符。空格（白）串:仅由一个或多个空格组成的串称为空白串(BlankString)子串和主串eg:

A＝“Thisisastring”

B＝“is”特别地：空串是任意串的子串，任意串是其自身的子串。串的相等二、串的抽象数据类型定义ADTString{数据对象：D＝{ai|ai∈CharacterSet,i＝1,2,…,n;n≥0}数据关系：S＝{<ai-1,ai>|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(S) Replace(&S,T,V)StrCompare(S,T) StrInsert(&S,pos,T)Concat(&T,S1,S2) StrDelete(&S,pos,len)}ADTString三、C语言的串函数用C处理字符串时，要调用标准库函数#include<string.h>串长度：intstrlen(char*s);串比较：intstrcmp(char*str1,char*str2);串拷贝：char*strcpy(char*str1,char*str2);串连接：char*strcat(char*str1,char*str2);子串T定位：char*strchr(char*str,charch);子串查找：char*strstr(char*s1,char*s2);

……4.2串的表示和实现串的机内表示方法：定长顺序存储表示（静态数组结构）堆分配存储表示（动态数组结构）串的块链存储表示顺序存储：链式存储：4.2串的表示和实现4.2.1定长顺序存储表示用一组连续的存储单元来存放串，直接使用定长的字符数组来定义，数组的上界预先给出，故称为静态存储分配。存储表示一：#defineMAXSTRLEN255typedefcharSString[MAXSTRLEN+1];SStrings;

串的结束标志的设置（1）一般可使用一个不会出现在串中的特殊字符在串值的尾部来表示串的结束。例如：C语言中以字符‘\0’表示串值的终结。（2）可以不设终结符

typedefstruct{charch[MAXSTRLEN];intlength;}SString;

（3）还可以用数组的0号单元存储串的长度。 算法4.2（串的连接算法）StatusConcat(SString&T,SStringS1,SStringS2){if(S1[0]+S2[0]<=MAXSTRLEN){T[1…S1[0]]=S1[1…S1[0]];T[S1[0]+1…S1[0]+S2[0]]=S2[1…S2[0]];T[0]=S1[0]+S2[0];uncut=TRUE;}elseif(S1[0]<MAXSTRLEN){T[1…S1[0]]=S1[1…S1[0]];T[S1[0]+1…MAXSTRLEN]=S2[1…MAXSTRLEN-S1[0]];T[0]=MAXSTRLEN;uncut=FALSE;} else{ T[0..MAXSTRLEN]=S1[0…MAXSTRLEN]; uncut=FALSE;}returnOK;}算法4.3（取子串）StatusSubString(SString&Sub,SStringS,intpos,intlen){if(pos<1||pos>S[0]||len<0||len>S[0]-pos+1)returnERROR;Sub[1…len]=S[pos…pos+len-1]Sub[0]=len;returnOK;}//SubString小结：1.串的定长顺序存储结构又称为串的静态存储结构，即用一段连续的存储单元来存储串的字符序列。2.串的存储结构必须预先定义允许存放串的最大字符个数，容易造成系统空间浪费或运行出错。3.串的某些操作（如：串的连接、串的替换等）受到限制。4.2.2堆分配存储表示特点：仍用一组连续的存储单元来存放串，但存储空间是在程序执行过程中动态分配而得。思路：利用malloc函数合理预设串长空间。串的动态数组结构体定义如下：

typedefstruct{char*ch;intlength;}HString;串的赋值算法

StatusStrAssign(HString&T,char*chars){if(T.ch)free(T.ch);for(i=0,c=chars;c;++i,++c);if(!i){T.ch=NULL;T.length=0;}else{T.ch=(char*)malloc(i*sizeof(char));if(!T.ch)exitOVERFLOW;T.ch[0…i-1]=chars[0…i-1];T.length=i;}returnOK;}串的比较算法

intStrCompare(HStringS,HStringT){for(i=0;i<S.length&&i<T.length;++i){if(S.ch[i]!=T.ch[i])returnS.ch[i]-T.ch[i];returnS.length-T.length;}串的连接算法StatusConcat(HString&T,HStringS1,HStringS2){if(T.ch)free(T.ch);T.ch=(char*)malloc(S1.length+S2.length)*sizeof(char))if(T.ch)exitOVERFLOW;T.ch[0…S1.length-1]=S1.ch[0…S1.length-1];T.length=S1.length+S2.length;T.ch[S1.length…T.length1]=S2.ch[0…S2.length-1];returnOK;}

取子串算法SubString(HString&Sub,HStringS,intpos,intlen){if(pos<1||pos>S.length||len<0||len>S.length-pos+1)returnERROR;if(Sub.ch)free(Sub.ch);if(!len){Sub.ch=NULL;Sub.length=0;}else{Sub.ch=(char*)malloc(len*sizeof(char));Sub.ch[0…len-1]=S[pos-1…pos+len-2];Sub.length=len;}returnOK;}4.2.3串的链式存储结构(1)单字符结点链

typedefstructnode{chardata;structnode*next;}*LString;

A

B

C

I

^head特点：一个链串由头指针唯一确定。这种结构便于进行插入和删除运算，但存储空间利用率太低。（2）串的块链结构引入目的：提高存储密度headABCDEFGHI###NULL存储表示的定义：#defineCHUNKSIZE80typedefstructnode{chardata[CHUNKSIZE];structnode*next;}*LString;4.3串的模式匹配算法一、基本概念模式匹配（子串定位）设有主串S和子串T（将S称为目标串，将T称为模式串），在主串S中，从位置start开始查找，如若在主串S中找到一个与子串T相等的子串，则返回T的第一个字符在主串中的位置，否则返回-1。算法目的确定主串中所含子串第一次出现的位置（定位）算法种类BF算法（又称古典的、经典的、朴素的、穷举的）KMP算法二、Brute-Force算法1.算法的设计思想：将主串S的第一个字符和模式T的第1个字符比较，若相等，继续逐个比较后续字符；若不等，从主串S的下一字符起，重新与T第一个字符比较。直到:主串S的一个连续子串字符序列与模式T相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。否则，匹配失败，返回值–1。2.下面以定长的顺序串类型作为存储结构，给出具体的串匹配算法。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;}显然，该算法在最坏情况下的时间复杂度为O((n-m)×m)。3.BF算法的时间复杂度若n为主串长度，m为子串长度，最好情况：一配就中！只比较了m次。最坏情况：则串的BF匹配算法最坏的情况下需要比较字符的总次数为(n－m＋1)×m。4.BF（Brute-Force）算法的特点：

简单，易于理解，效率较高；算法的时间复杂度O((n－m)×m)。(其中n,m分别为主串和模式串的长度）

实际运行中，时间近似于O（n＋m)。注意：当遇到一次si≠tj,主串要回退到i－j+2的位置，而模式串要回到第一个位置（即j＝1的位置)；但当一次比较出现si≠tj时，则应该有：

"si-j+1si-j+2……si-1"="t1t2……tj-2tj-1"改进：每当一趟匹配过程出现si≠tj时，主串指示器i不用回溯，而是利用已经得到的“部分匹配”结果，将模式串向右“滑动”尽可能远的一段距离后，继续进行比较。4.3.2模式匹配的改进算法（KMP算法）一、分析与示例1趟ababcabcacbababc2趟ababcabcacbababcac3趟ababcabcacbababcac二、讨论一般情况设:主串S="s1s2……si……sn"，

模式串T="p1p2…pj…pm"问：当某趟比较发生“失配”（即si≠pj）时，模式串应该向“右”滑动的可行距离为多长？解：设某趟匹配发生si≠pj时，

si应该与pk（k＜j）继续比较。根据："p1p2…pk-1"＝"si-k+1si-k+2…si-1"

"pj-k+1pj-k+2…pj-1"＝"si-k+1si-k+2…si-1"可以推出：“p1p2…pk-1”＝“pj-k+1pj-k+2…pj-1”示意图如下：主串Sikj模式串T令next(j)＝knext(j)＝

0

当j=1Max{k|1＜k＜j且“p1p2…pk-1”＝“pj-k+1pj-k+2…pj-1”}

当此集合非空

1

其他情况j12345Pjabcacnext(j)01112例1：计算如下模式串的next函数值。例2：计算如下模式串的next函数值。j12345678Pjabaabcacnext(j)01122312KMP算法（算法4.6）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;}elsej=next[j];}if(j>T[0])returni-T[0];elsereturn0;}//Index_KMP三、模式串的next函数值的求解由定义知：next[1]=0，设next[j]=k表明："p1p2…pk-1"="pj-k+1pj-k+2…pj-1

" （其中1＜k＜j,且不存在k’(k’＞k)满足上式）问：next[j+1]=k’=?

解：情况1：若pK=

Pj,即"p1p2…pk-1pk"="pj-k+1pj-k+2…pj-1pj"②则next[j+1]=next[j]+1=k+1；情况2：若pK≠Pj,即"p1p2…pk-1pk"≠"pj-k+1pj-k+2…pj-1pj",但"p1p2…pk-1"≠"pj-k+1pj-k+2…pj-1

",则应将模式向右滑动至模式中的next[k]=k’个字符比较，重复上述过程直至Pj

和模式中的某个字符匹配成功或不存在任何k’(1<k’<j)满足②，则令next[j+1]=1。算法4.7voidget_next(SStringT,int&next[]){i=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_next

4.4串的应用举例文本编辑文本编辑程序是一个面向用户的系