第4章 字符串

1、1第第4章章 串串從數(shù)據(jù)結構的角度來看，從數(shù)據(jù)結構的角度來看，串是一種每個數(shù)據(jù)是一種每個數(shù)據(jù)元素僅由一個字符組成的元素僅由一個字符組成的特殊線性表線性表。 隨著數(shù)據(jù)處理技術的發(fā)展，隨著數(shù)據(jù)處理技術的發(fā)展，串在文字在文字編輯、符號處理、詞法分析、信息檢索、編輯、符號處理、詞法分析、信息檢索、自然語言翻譯等方面的自然語言翻譯等方面的應用越來越廣泛。越來越廣泛。越來越多的程序設計語言支持串作為一種越來越多的程序設計語言支持串作為一種變量類型，參加各種運算。本章將討論串變量類型，參加各種運算。本章將討論串的基本概念、基本操作及存儲方法的基本概念、基本操作及存儲方法2字符串 (String)字符串是 n

2、 ( 0 ) 個字符的有限序列， 記作 S : “c1c2c3cn” 其中，S 是串名字 “c1c2c3cn”是串值 ci 是串中字符 n 是串的長度。例如, S = “Tsinghua University” 3 串中任意個連續(xù)的字符組成的子序串中任意個連續(xù)的字符組成的子序列列稱為稱為該串的子串。包含子串的串相應。包含子串的串相應地稱為地稱為主串。通常稱字符在序列中的序。通常稱字符在序列中的序號為該號為該字符在串中的位置。子串在主串。子串在主串中的位置則以子串的第一個字符在主串中的位置則以子串的第一個字符在主串中的位置來表示。中的位置來表示。 4例 串名為串名為A、B、C、D的四個串如下：的

3、四個串如下： A=very good； B= ； C=； D=good；5 串串A的長度是的長度是9；串；串B的長度為的長度為3的空格串；串的空格串；串C中不包含任何字符，中不包含任何字符，是空串，長度為零；串是空串，長度為零；串D的長度是的長度是4，顯然串顯然串D是串是串A的子串，串的子串，串A是串是串D的主串，串的主串，串D在主串在主串A中的位置是中的位置是6。 當兩個串的長度相等，并且各當兩個串的長度相等，并且各個對應位置上的字符都相等時個對應位置上的字符都相等時，稱，稱兩個個串是是相等的。的。6字符串抽象數(shù)據(jù)類型定義字符串抽象數(shù)據(jù)類型定義ADT String 數(shù)據(jù)對象數(shù)據(jù)對象:D=ai

4、|ai CharacterSet, i=1,2,n,n0數(shù)據(jù)關系：數(shù)據(jù)關系：R1=|ai-1,ai D,i=2,n基本操作：基本操作：StrAssign(&T,chars)生成字符串生成字符串TStrCopy(&T,S)復制字符串復制字符串SStrEmpty(S)判斷判斷S是否為空串是否為空串StrCompare(S,T)比較字符串比較字符串S和和TStrLength(S)求字符串求字符串S長度長度ClearString(&S)清空字符串清空字符串SConcat(&T,S1,S2)連接字符串連接字符串S1和和S2SubString(&Sub,S,pos,

5、len)求求S長度為長度為len位置為位置為pos的子串的子串Index(S,T,pos)求子串在主串中的位置求子串在主串中的位置Replace(&S,T,V)在在S中用子串中用子串V替換子串替換子串TStrInsert(&S,pos,T)在在S中插入子串中插入子串TStrDelete(&S,pos,len)在在S中刪除長度為中刪除長度為len的子串的子串DestroyString(&S)銷毀串銷毀串S7int Index ( String S, String T, int pos ) if (pos 0) n=StrLength(S); m=StrLength

6、(T); i=pos;while (i=n-m+1) SubString (sub, S, i, m);if (StrCompare(sub,T)!=0) +i;else return i;/while/ifreturn 0;/Index8串的表示和實現(xiàn)串的表示和實現(xiàn)1.定長順序存儲表示定長順序存儲表示用一組地址連續(xù)的存儲單元存儲串值的字用一組地址連續(xù)的存儲單元存儲串值的字符序列。符序列。#define MAXSTRLEN 255typedef unsigned char SStringMAXSTRLEN+1;/0號單元存串號單元存串長長9(1)串連接串連接 Status Concat(SSt

7、ring &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 (S10MAXSTRLEN) T1.S10=S11.S10;TS10+1.MAXSTRLEN=S21.MAXSTRLEN-S10;T0=MAXSTRLEN; uncut=FALSE;else T0.MAXSTRLEN=S10.MAXSTRLEN; uncut=FALSE;return uncut

8、;/Concat10(2)求子串求子串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; return OK;/SubString使用順序存儲結構過程中可能出現(xiàn)串長度超過數(shù)使用順序存儲結構過程中可能出現(xiàn)串長度超過數(shù)組上限，經(jīng)過截斷的串已經(jīng)不完整，克服這個組上限，經(jīng)過截斷的串已經(jīng)不完整，克服這個問題可使用動態(tài)分配串值的存儲空間。問題可使用動態(tài)分配串值的存儲空間。11堆分配存儲表示

9、堆分配存儲表示堆是操作系統(tǒng)中為進程分配的自由存儲空間，在堆是操作系統(tǒng)中為進程分配的自由存儲空間，在C語言中用語言中用malloc()和和free()來管理。來管理。typedef struct char *ch;int length;HString;Status StrInsert(HString &S, int pos, HString T)/在串在串S的第的第pos個字符之前插入串個字符之前插入串Tif (posS.length+1) return ERROR;if(T.length)if(!(S.ch=(char *)realloc(S.ch,(S.length+T.length

10、)*sizeof(char)exit(OVERFLOW);for (i=S.length-1;i=pos-1;-i)S.chi+T.length=S.chi;S.chpos-1.pos+T.length-2=T.ch0.T.length-1;S.length+=T.length;return OK;/StrInsert12Status StrAssign(HString &T,char *chars)/生成值為生成值為chars的串的串Tif(T.ch) free(T.ch);for(i=0, c=chars;c;+i,+c);/求求chars長度長度iif(!i) T.ch=NULL

11、; T.length=0;else if(!(T.ch=(char *)malloc(i*sizeof(char)exit (OVERFLOW);T.ch0.i-1=chars0.i-1;T.length=I;return OK;/StrAssign13int StrLength(HString S) /求串長度求串長度return S.length;/StrLengthint StrCompare(HString S, HString T)/比較串比較串S和和Tfor (i=0;iS.length & iT.length;+i)if(S.chi!=T.chi) return S.ch

12、i-T.chi;return S.length-T.length;/StrCompareStatus ClearString(HString &S)/清空串清空串Sif(S.ch) free(S.ch); S.ch=NULL;S.length=0;return OK;/ClearString14Status Concat(HString &T,HString S1,HString S2) /連接串連接串S1和和S2if(T.ch) free(T.ch);if(!(T.ch=(char *)malloc(S1.length+S2.length)*sizeof(char)exit(

13、OVERFLOW);T.ch0.S1.length-1=S1.ch0.S1.length-1;T.length=S1.length+S2.length;T.chS1.length.T.length-1=S2.ch0.S2.length-1;return OK;/Concat15提取子串的算法示例pos+len - -1 pos+len - -1 length- -1 lengthi n f i n i t yi n f i n i t ypos = 2, len = 3pos = 5, len = 4f i ni t y16Status SubString(HString &Sub,H

14、String S,int pos,int len)/返回串返回串S中從中從pos位置起長度為位置起長度為len的子串的子串if (posS.length|lenS.length-pos+1)return ERROR;if(Sub.ch) free(Sub.ch);if(!len)Sub.ch=NULL; Sub.length=0;elseSub.ch=(char *)malloc(len*sizeof(char);Sub.ch0.len-1=Spos-1.pos+len-2;Sub.length=len;return OK;/SubString173.串的塊鏈存儲表示串的塊鏈存儲表示用鏈表存儲

15、串，每個結點存儲串的用鏈表存儲串，每個結點存儲串的n個字符，個字符，當串長不是當串長不是n的整數(shù)倍時最后一個結點剩的整數(shù)倍時最后一個結點剩余位置用空字符補齊。余位置用空字符補齊。如串如串ABCDEFGHI當當n=4時：時：當當n=1時：時：A B C DE F G HI # # # headABCI head18串的塊鏈存儲表示串的塊鏈存儲表示#define CHUNKSIZE 80typedef struct Chunkchar chCHUNKSIZE;struct Chunk *next;Chunk;typedef struct Chunk *head, *tail;/為指針便于連接操作為

16、指針便于連接操作int curlen;LString;塊鏈存儲方式便于連接操作，但占用存儲量大，塊鏈存儲方式便于連接操作，但占用存儲量大，操作復雜。操作復雜。19串的模式匹配定義 在串中尋找子串（第一個字符）在串中的位置詞匯 在模式匹配中，子串稱為模式，串稱為目標。示例 目標 T : “Beijing” 模式 P : “jin” 匹配結果 = 4 20第第1趟趟 T a b b a b a 窮舉的模式窮舉的模式 P a b a 匹配過程匹配過程 第第2趟趟 T a b b a b a P a b a 第第3趟趟 T a b b a b a P a b a第第4趟趟 T a b b a b a

17、P a b a i=1j=1i=2j=1i=3j=1i=4j=1匹配模式：匹配模式：aba21匹配算法匹配算法:int Index(SString S, SString T, int pos)/從串從串S中中pos位置開始搜索模式位置開始搜索模式Ti=pos; j=1;while (i=S0 & jT0) return i-T0;else return 0;/Index22模式匹配的改進算法：模式匹配的改進算法：匹配模式匹配模式abcac第第1趟趟 T a b a b c a b c a c b a b P a b c 第第2趟趟 T a b a b c a b c a c b a b

18、 P a b c a c 第第3趟趟 T a b a b c a b c a c b a b P a b c a c i=3j=3i=7j=5i=7j=2i=323第第1趟趟 T a b a b c a b c a c b a b P a b c 在第一趟中在第一趟中i=3,j=3時比較失敗，按窮舉法時比較失敗，按窮舉法i應變?yōu)槌跏贾导討優(yōu)槌跏贾导?，即，即i=2;j每次重新變?yōu)槊看沃匦伦優(yōu)?，再開始下一輪比較，但事實上，再開始下一輪比較，但事實上i=2時時已經(jīng)作過比較不需要再比較一次，所以已經(jīng)作過比較不需要再比較一次，所以i值不變，只需值不變，只需j變?yōu)樽優(yōu)?再開始比較即可。再開始比較即可。24第第2趟趟 T a b a b c a b c a c b a b P a b c a c在第二趟中在第二趟中i=7,j=5時比較失敗，按窮舉法時比較失敗，按窮舉法i應變?yōu)槌跏贾导討優(yōu)槌跏贾导?，即，即i=4;j變?yōu)樽優(yōu)?，再開，再開始下一輪比