【正文】 第4章 串存儲與基本操作的實現(xiàn)第四章 串存儲與基本操作的實現(xiàn)本章學習要點◆熟悉串的相關(guān)概念以及串與線性表的關(guān)系◆重點掌握串的定長存儲、堆分配存儲的表示方法與基本操作的實現(xiàn)◆了解串的各種存儲結(jié)構(gòu)，能根據(jù)需要合理選用串的存儲結(jié)構(gòu)解決實際問題“串”(string)，是字符串的簡稱，它是一種特殊的線性表，其特殊性在于組成線性表的數(shù)據(jù)元素是單個字符。字符串在計算機處理實際問題中使用非常廣泛，比如人名、地名、商品名、設(shè)備名等均為字符串。同樣在文字編輯、自然語言理解和翻譯、源程序的編輯和修改等方面，都離不開對字符串的處理。1．串的定義串(string) 是由n個字符組成的有限序列，記為：S=”a0a1a2…an1” (n≥0)。其中，S是串的名字，字符序列a0a1a2…an1是串的值，ai(0≤i≤n1)可以是字母、數(shù)字或其他字符元素；由于在C語言系統(tǒng)中數(shù)組元素的下標是從0開始的，所以串中所含元素的序號等于該元素的下標值加1；串中所含字符的個數(shù)n稱為該串的長度，長度為0的字符串稱為空串（null string）。從串的定義可以看出，串實際上是數(shù)據(jù)元素為字符的特殊的線性表。例如：（1）A=“X123” (長度為4的串)（2）B=“12345654321” (長度為11的串)（3）C=“Bei Jing” (長度為8的串)（4）D=“” (長度為0的空串)（5）E=“This is a string” (長度為16的串)（6）F=“ is a ” (長度為6的串)2．子串、主串和位置串中任意連續(xù)的字符組成的子序列稱為該串的子串；相應(yīng)地，包含子串的串稱為主串。串中的字符在串序列中的序號稱為該字符在該串中的位置；子串的第一個字符在主串中的位置稱為子串在主串中的位置。顯然，串為其自身的子串，并規(guī)定空串為任何串的子串。顯然，在不考慮空子串的情況下，一個長度為n的字符串具有n(n+1)/2個子串。例如：在上例的(6)中串F就是(5)中串E的子串，且子串F在主串E中的位置是5。由于空格符也是一個字符，所以在串G=“abc defghne”中包含有子串“c def”,而串 “cdef”不是串G的子串。串G中第一個字符‘e’的位置是6，第二個字符‘e’的位置是11。3．串的比較如果兩個串的長度相等且對應(yīng)位置上的字符相同，則稱這兩個串相等。兩個串A、B的比較過程是：從前往后逐個比較對應(yīng)位置上的字符的ASCII碼值，直到不相等或有一個字符串結(jié)束為止，此時的情況有以下幾種：（1）兩個串同時結(jié)束，表示A等于B；（2）A中字符的ASCII碼值大于B中相應(yīng)位置上字符的ASCII碼值或B串結(jié)束，表示A大于B；（3）B中字符的ASCII碼值大于A中相應(yīng)位置上字符的ASCII碼值或A串結(jié)束，表示A小于B。例如：“abc”=“abc”，“abc”“abcd”，“abxy”“abcdefg”，“132”“123456”，“ABab”“abAB”，“3+2”“2+3”。4．空格串由一個或多個空格字符組成的串稱為空格串，空格串的長度為串中所含空格字符的個數(shù)。在串操作中不要將空格串和空串混淆。盡管串的定義和線性表極為相似，但是串的基本操作和線性表有很大差別。在線性表的基本操作中，大多以單個元素作為操作對象，比如對線性表的查找、訪問、插入、刪除和排序等；而在串的基本操作中，通常以串整體或串的一部分（子串）作為操作對象，比如子串的查找、截取子串、刪除一個子串、插入子串和子串替換等操作。串的基本操作主要有：（1）初始化串StrAssign(amp。T,chars) 由字符串常量chars生成字符串T的操作。（2）串復制StrCopy(amp。T,S) 由串S復制生成串T的操作。（3）串比較StrCompare(S,T) 若S=T返回0，ST返回正數(shù)，ST返回負數(shù)。（4）求串長度StrLength(S) 返回串S的長度。（5）串連接Concat(amp。T,S1,S2) 將串S1和S2連接起來生成串T的操作。（6）求子串SubString(amp。Sub,S,pos,len) 以串S中pos位置開始的len個字符生成子串Sub的操作。（7）串查找Index(S,T,pos) 返回子串T在S中pos個字符以后出現(xiàn)的位置。（8）串替換Replace(amp。S,T,V) 將串S中所有不重疊子串T替換為串V的操作。（9）串插入StrInsert(amp。S,pos,T) 在串S中第pos個字符前插入串T的操作。（10）刪除子串StrDelete(amp。S,pos,len) 刪除串S中第pos個字符開始的len個字符的操作。既然串是線性表的特例，所以線性表的兩種存儲結(jié)構(gòu)對于串也是適用的。在應(yīng)用中具體選用何種存儲結(jié)構(gòu)與串的操作有關(guān)，比如對串進行插入和刪除操作運算時選用鏈存儲結(jié)構(gòu)較好，對串進行查找和求子串運算時選用順序存儲結(jié)構(gòu)較好。本章主要介紹串的3種存儲表示方法：（1）串的定長順序存儲表示法（2）串的堆分配存儲表示法（3）串的塊鏈式存儲表示法串的定長順序存儲表示是用一組地址連續(xù)的存儲單元來存儲串中的字符序列。在串的定長順序存儲表示中，按照預定義的大小，為每個定長的串變量分配一個固定長度的存儲區(qū)，所以可以用定長字符數(shù)組來表示。1．定長順序存儲結(jié)構(gòu)在C++運行環(huán)境中，定長順序結(jié)構(gòu)定義為：includeincludedefine MAXLEN 255 //定義串的最大長度為255typedef char SString[MAXLEN+1]。 //定義定長順序存儲類型SString2．基本操作的C++程序?qū)崿F(xiàn)（1）求串長度操作int Length_SS(SString S)操作返回串S中所含字符的個數(shù)，即串的長度；如果S為空串則返回0。int Length_SS(SString S) { int i=0。 while(S[i])i++。 return(i)。}（2）串連接操作int Concat_SS(SString amp。T,SString S1,SString S2)該操作將串SS2連接生成串T，如果在連接過程中產(chǎn)生了截斷（即S1的長度加上S2的長度大于MAXLEN）則返回0，否則返回1。int Concat_SS(SString amp。T,SString S1,SString S2){ int i,j,k。 i=j=k=0。 while(T[i++]=S1[j++])。 i。 while(iMAXLENamp。amp。(T[i]=S2[k])){ i++。k++。 } T[i]=0。 if((i==MAXLEN)amp。amp。S2[k]) return(0)。 /*判斷是否產(chǎn)生截斷*/ else return(1)。}（3）求子串操作int SubString_SS(SString amp。Sub,SString S,int pos,int len)該操作截取串S中從第pos個字符開始的連續(xù)的len個字符生成子串Sub，如果位置pos和長度len合理則返回1，否則返回0.int SubString_SS(SString amp。Sub,SString S,int pos,int len){ int i=0。 if(pos1||len0||pos+lenLength_SS(S)+1) return 0。 /*判斷位置和長度是否合理*/ while(ilen) {Sub[i]=S[i+pos1]。 i++。 } Sub[i]=39。\039。 return 1。 }（4）初始化串操作int StrAssign_SS(SString amp。T,char *s)該操作用字符數(shù)組s，初始化定長順序串T。如果不產(chǎn)生截斷（長度合理）返回1，否則返回0。int StrAssign_SS(SString amp。T,char *s){ int i=0。 while(iMAXLENamp。amp。(T[i]=s[i]))i++。 T[i]=0。 if((i==MAXLEN)amp。amp。s[i]) return 0。 /*判斷是否產(chǎn)生截斷*/ else return 1。}（5）串復制操作void StrCopy_SS(SString amp。T,SString S)該操作將定長順序串S，復制到定長順序串T。void StrCopy_SS(SString amp。T,SString S){ int i=0。 while(T[i]=s[i])i++。}（6）串比較操作int StrCompare_SS(SString S,SString T)該操作比較順序串S、T的大小，如果ST則返回正數(shù),如果S=T則返回0,否則返回負數(shù)。int StrCompare_SS(SString S,SString T){ int i=0。 while(S[i]amp。amp。T[i]amp。amp。(S[i]==T[i]))i++。 return (int)(S[i]T[i])。}（7）串的替換操作int Replace_SS(SString amp。S,int n,int m,SString T)該操作將串S中從第n個字符開始的連續(xù)的m個字符替換成串T中的字符，如果n和m的選取合理則返回1，否則返回0。int Replace_SS(SString amp。S,int n,int m,SString T){ SString S1。 int len=Length_SS(T)。 int i=n1,j=0,k=n+m1。 /*i為開始替換位置，j指向第一個替換字符，k為剩余字符的開始位置*/ if(n1||m0||n+mLength_SS(S)+1||Length_SS(S)+lenmMAXLEN) return(0)。/*判斷位置是否合理*/ StrCopy_SS(S1,S)。 /*將剩余部分復制到S1中*/ while(S[i++]=T[j++])。 /*替換S中指定部分的字符*/ i。 while(S[i++]=S1[k++])。 /*將剩余部分復制到S中*/ return(1)。}（8）主函數(shù)演示程序main()void main_SS(){ SString s1,s2,s3,sub,T。 char str1[100],str2[100]。 int l1,l2,l3,pos,len,n。 while(1) { cout(1)串初始化操作：\n輸入兩個字符串:\n。 (str1,sizeof(str1))。/*表示從鍵盤輸入一個可以含有空格字符的長度小于100的字符串到str1中，語句 “cinstr1”不能輸入空格字符（空格符表示輸入結(jié)束）且對串的長度不做檢查。*/ (str2,sizeof(str2))。 StrAssign_SS(s1,str1)。 StrAssign_SS(s2,str2)。 l1=Length_SS(s1)。 l2=Length_SS(s2)。 cout(2)求串長操作：\ns1的長度=l1，s2的長度=l2endl。 n=StrCompare_SS(s1,s2)。 cout(3)串比較操作：\n比較結(jié)果為: 。 if(n0)couts1s2\n。 else if(n==0)couts1=s2\n。 e