數(shù)據(jù)結(jié)構(gòu)-字符串操作原理

CH4串4.1串類型的定義4.2串的表示和實(shí)現(xiàn)4.3串的模式匹配算法教學(xué)目標(biāo)熟悉串的有關(guān)概念，串和線性表的關(guān)系。掌握串的各種存儲(chǔ)結(jié)構(gòu)，比較它們的優(yōu)、缺點(diǎn)，從而學(xué)會(huì)在何時(shí)選用何種存儲(chǔ)結(jié)構(gòu)為宜。熟練掌握串的七種基本運(yùn)算，并能利用這些基本運(yùn)算實(shí)現(xiàn)串的其它各種運(yùn)算。教學(xué)難點(diǎn)串運(yùn)算的實(shí)現(xiàn)，特別是順序串上子串定位的運(yùn)算（又稱串的模式匹配或串匹配）。4.1串類型的定義一、串的基本概念串(String)的定義

s＝“a1a2…an”其中：s為串的名字，串的值ai(1≤i≤n)一般是字母、數(shù)學(xué)、標(biāo)點(diǎn)符號(hào)等可屏幕顯示的字符。串的長度n。4.1串類型的定義字符串與一般的線性表的區(qū)別：串的數(shù)據(jù)元素約束為字符集；串的基本操作通常針對串的整體或串的一個(gè)部分進(jìn)行。問題：為何要單獨(dú)討論“串”類型？字符串操作比其他數(shù)據(jù)類型更復(fù)雜（如拷貝、連接操作）程序設(shè)計(jì)中，處理對象很多都是串類型。4.1串類型的定義空串和空白串：長度為零的串稱為空串(EmptyString)，它不包含任何字符?？崭瘢ò祝┐?僅由一個(gè)或多個(gè)空格組成的串稱為空白串(BlankString)子串和主串eg:

A＝“Thisisastring”

B＝“is”特別地：空串是任意串的子串，任意串是其自身的子串。串的相等二、串的抽象數(shù)據(jù)類型定義ADTString{數(shù)據(jù)對象：D＝{ai|ai∈CharacterSet,i＝1,2,…,n;n≥0}數(shù)據(jù)關(guān)系：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語言的串函數(shù)用C處理字符串時(shí)，要調(diào)用標(biāo)準(zhǔn)庫函數(shù)#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串的表示和實(shí)現(xiàn)串的機(jī)內(nèi)表示方法：定長順序存儲(chǔ)表示（靜態(tài)數(shù)組結(jié)構(gòu)）堆分配存儲(chǔ)表示（動(dòng)態(tài)數(shù)組結(jié)構(gòu)）串的塊鏈存儲(chǔ)表示順序存儲(chǔ)：鏈?zhǔn)酱鎯?chǔ)：4.2串的表示和實(shí)現(xiàn)4.2.1定長順序存儲(chǔ)表示用一組連續(xù)的存儲(chǔ)單元來存放串，直接使用定長的字符數(shù)組來定義，數(shù)組的上界預(yù)先給出，故稱為靜態(tài)存儲(chǔ)分配。存儲(chǔ)表示一：#defineMAXSTRLEN255typedefcharSString[MAXSTRLEN+1];SStrings;

串的結(jié)束標(biāo)志的設(shè)置（1）一般可使用一個(gè)不會(huì)出現(xiàn)在串中的特殊字符在串值的尾部來表示串的結(jié)束。例如：C語言中以字符‘\0’表示串值的終結(jié)。（2）可以不設(shè)終結(jié)符

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

（3）還可以用數(shù)組的0號(hào)單元存儲(chǔ)串的長度。 算法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小結(jié)：1.串的定長順序存儲(chǔ)結(jié)構(gòu)又稱為串的靜態(tài)存儲(chǔ)結(jié)構(gòu)，即用一段連續(xù)的存儲(chǔ)單元來存儲(chǔ)串的字符序列。2.串的存儲(chǔ)結(jié)構(gòu)必須預(yù)先定義允許存放串的最大字符個(gè)數(shù)，容易造成系統(tǒng)空間浪費(fèi)或運(yùn)行出錯(cuò)。3.串的某些操作（如：串的連接、串的替換等）受到限制。4.2.2堆分配存儲(chǔ)表示特點(diǎn)：仍用一組連續(xù)的存儲(chǔ)單元來存放串，但存儲(chǔ)空間是在程序執(zhí)行過程中動(dòng)態(tài)分配而得。思路：利用malloc函數(shù)合理預(yù)設(shè)串長空間。串的動(dòng)態(tài)數(shù)組結(jié)構(gòu)體定義如下：

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串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(1)單字符結(jié)點(diǎn)鏈

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

A

B

C

I

^head特點(diǎn)：一個(gè)鏈串由頭指針唯一確定。這種結(jié)構(gòu)便于進(jìn)行插入和刪除運(yùn)算，但存儲(chǔ)空間利用率太低。（2）串的塊鏈結(jié)構(gòu)引入目的：提高存儲(chǔ)密度headABCDEFGHI###NULL存儲(chǔ)表示的定義：#defineCHUNKSIZE80typedefstructnode{chardata[CHUNKSIZE];structnode*next;}*LString;4.3串的模式匹配算法一、基本概念模式匹配（子串定位）設(shè)有主串S和子串T（將S稱為目標(biāo)串，將T稱為模式串），在主串S中，從位置start開始查找，如若在主串S中找到一個(gè)與子串T相等的子串，則返回T的第一個(gè)字符在主串中的位置，否則返回-1。算法目的確定主串中所含子串第一次出現(xiàn)的位置（定位）算法種類BF算法（又稱古典的、經(jīng)典的、樸素的、窮舉的）KMP算法二、Brute-Force算法1.算法的設(shè)計(jì)思想：將主串S的第一個(gè)字符和模式T的第1個(gè)字符比較，若相等，繼續(xù)逐個(gè)比較后續(xù)字符；若不等，從主串S的下一字符起，重新與T第一個(gè)字符比較。直到:主串S的一個(gè)連續(xù)子串字符序列與模式T相等。返回值為S中與T匹配的子序列第一個(gè)字符的序號(hào)，即匹配成功。否則，匹配失敗，返回值–1。2.下面以定長的順序串類型作為存儲(chǔ)結(jié)構(gòu)，給出具體的串匹配算法。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;}顯然，該算法在最壞情況下的時(shí)間復(fù)雜度為O((n-m)×m)。3.BF算法的時(shí)間復(fù)雜度若n為主串長度，m為子串長度，最好情況：一配就中！只比較了m次。最壞情況：則串的BF匹配算法最壞的情況下需要比較字符的總次數(shù)為(n－m＋1)×m。4.BF（Brute-Force）算法的特點(diǎn)：

簡單，易于理解，效率較高；算法的時(shí)間復(fù)雜度O((n－m)×m)。(其中n,m分別為主串和模式串的長度）

實(shí)際運(yùn)行中，時(shí)間近似于O（n＋m)。注意：當(dāng)遇到一次si≠tj,主串要回退到i－j+2的位置，而模式串要回到第一個(gè)位置（即j＝1的位置)；但當(dāng)一次比較出現(xiàn)si≠tj時(shí)，則應(yīng)該有：

"si-j+1si-j+2……si-1"="t1t2……tj-2tj-1"改進(jìn)：每當(dāng)一趟匹配過程出現(xiàn)si≠tj時(shí)，主串指示器i不用回溯，而是利用已經(jīng)得到的“部分匹配”結(jié)果，將模式串向右“滑動(dòng)”盡可能遠(yuǎn)的一段距離后，繼續(xù)進(jìn)行比較。4.3.2模式匹配的改進(jìn)算法（KMP算法）一、分析與示例1趟ababcabcacbababc2趟ababcabcacbababcac3趟ababcabcacbababcac二、討論一般情況設(shè):主串S="s1s2……si……sn"，

模式串T="p1p2…pj…pm"問：當(dāng)某趟比較發(fā)生“失配”（即si≠pj）時(shí)，模式串應(yīng)該向“右”滑動(dòng)的可行距離為多長？解：設(shè)某趟匹配發(fā)生si≠pj時(shí)，

si應(yīng)該與pk（k＜j）繼續(xù)比較。根據(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

當(dāng)j=1Max{k|1＜k＜j且“p1p2…pk-1”＝“pj-k+1pj-k+2…pj-1”}

當(dāng)此集合非空

1

其他情況j12345Pjabcacnext(j)01112例1：計(jì)算如下模式串的next函數(shù)值。例2：計(jì)算如下模式串的next函數(shù)值。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函數(shù)值的求解由定義知：next[1]=0，設(shè)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

",則應(yīng)將模式向右滑動(dòng)至模式中的next[k]=k’個(gè)字符比較，重復(fù)上述過程直至Pj

和模式中的某個(gè)字符匹配成功或不存在任何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串的應(yīng)用舉例文本編輯文本編輯程序是一個(gè)面向用戶的系