【正文】 x()。串的反轉(zhuǎn)：void Strrev()。復(fù)制：void Strcopy()。比較：int Compare(String s)。返回子串：bool substring (String amp。sub)。聯(lián)結(jié)：bool Concat(String s)。返回子串：bool Substring (String amp。sub)。計(jì)算元音個(gè)數(shù)：int count_Vowel(const char *s)。轉(zhuǎn)換函數(shù)小寫(xiě)：char*Mytolower(char *src)。已知串 char：bool StrAssign(char *chars)類(lèi)String圖 21 設(shè)計(jì)流程圖 塔里木大學(xué)信息工程學(xué)院課程設(shè)計(jì)第 3 頁(yè) 共 14 頁(yè)2．3．3 設(shè)計(jì)內(nèi)容 在各種高級(jí)語(yǔ)言的編譯程序中，源程序和目標(biāo)程序都被處理成字符串?dāng)?shù)據(jù)，各種源程序編輯器的功能強(qiáng)弱有差異，但其基本操作是一致的，一般都包括串的查找、插入、刪除、轉(zhuǎn)換等 [4]。本設(shè)計(jì)中，整個(gè)程序分為三個(gè)獨(dú)立的文檔。其中包括：頭文件 ，源文件 和。頭文件包括一個(gè)類(lèi) class String，里面是對(duì)各個(gè)函數(shù)進(jìn)行聲明。類(lèi)的私有成員有一維數(shù)組str1[40]。字符串的最大長(zhǎng)度 maxlen；字符串的當(dāng)前長(zhǎng)度 curlen。串是一種特殊的線性表，它的每一個(gè)元素僅有一個(gè)字符所組成。因此可以用線性表的存儲(chǔ)方法來(lái)存儲(chǔ)串。串的實(shí)現(xiàn)方式大致分為三種：；；。串的順序存儲(chǔ)是用一組地址連續(xù)的儲(chǔ)存單元存儲(chǔ)字符串的字符序列，這樣的存儲(chǔ)結(jié)構(gòu)訪問(wèn)一組連續(xù)字符非常方便，體現(xiàn)了順序表的優(yōu)點(diǎn)：隨機(jī)存儲(chǔ) [6]。串的塊鏈豐儲(chǔ)類(lèi)似線性表中的鏈表，不過(guò)在一個(gè)結(jié)點(diǎn)中它儲(chǔ)存的并不是一個(gè)字符，而是一個(gè)字符串，一般來(lái)說(shuō)，以塊鏈作為存儲(chǔ)結(jié)構(gòu)時(shí)實(shí)現(xiàn)串的操作比較麻煩。串的堆分配存儲(chǔ)的特點(diǎn)是串變量的存儲(chǔ)空間是程序執(zhí)行過(guò)程中動(dòng)態(tài)分配而得，程序中出現(xiàn)的所有串變量可用的存儲(chǔ)空間是一個(gè)稱之為“堆”的共享空間。在本設(shè)計(jì)中，運(yùn)用的是已知一個(gè)字符串再建立一個(gè)字符串。 [8]存儲(chǔ)方式的代碼如下：bool SString::StrAssign(char *chars) //生成一個(gè)值為 chars 的串{if(strlen(chars)maxsize) //判斷 chars 的長(zhǎng)度是否比串的長(zhǎng)度大return false。 //大，則錯(cuò)誤 else{curlen=strlen(chars)。 //令串的長(zhǎng)度等于 chars 的長(zhǎng)度f(wàn)or(int i=1。i=curlen。i++) str1[i1]=chars[i1]。 //串的內(nèi)容等于 chars 里面的內(nèi)容}return true。}經(jīng)過(guò)從鍵盤(pán)輸出 chars 里面的數(shù)據(jù)，能得到字符串。調(diào)試結(jié)果如下圖：圖 22 建立字符串確定建立串的程序正確之后，就可以逐漸加入其它程序段了。串的長(zhǎng)度是求該字符串的當(dāng)前長(zhǎng)度。因?yàn)樗凶约旱漠?dāng)前長(zhǎng)度 curlen，所以 return curlen 就可以求出字符串的長(zhǎng)度。 [11]插入和刪除是字符串中兩個(gè)常見(jiàn)的操作。插入操作是指將一個(gè)指定的串插入到當(dāng)前串中的指定位置。插入的算法是：（1）當(dāng)插入位置超出合法的范圍，即當(dāng) pos0 或 poscurlen 時(shí)，顯示出錯(cuò)信息并終止。 （2）當(dāng)插入后的新串長(zhǎng)度超出當(dāng)前串的最大值，即 curlen+tlen=maxlen1 時(shí)，重新分配空間。 （3）將當(dāng)前串中從 pos 開(kāi)始至串尾的一些字符后移留出 tlen 個(gè)空位，然后將子串插入到對(duì)應(yīng)的空位中。 （4）更新當(dāng)前串的長(zhǎng)度為 curlen+tlen，返回當(dāng)前串。刪除操作是指刪除當(dāng)前串中指定范圍內(nèi)的串值。刪除的算法是：（1）輸出所要?jiǎng)h除的子串的位置 pos 及子串的長(zhǎng)度 塔里木大學(xué)信息工程學(xué)院課程設(shè)計(jì)第 4 頁(yè) 共 14 頁(yè)tlen。 （2）檢查位置的合法性。即當(dāng) poscurlen1 或 pos0 或 tlen1，顯示出錯(cuò)信息并終止。（2）若長(zhǎng)度超出最大可供刪除的長(zhǎng)度，即當(dāng) tlencurlenpos 時(shí)，則按截尾法對(duì) tlen 進(jìn)行調(diào)整。（3）確定新串的長(zhǎng)度為 curlentlen，刪除當(dāng)前串中從 pos 開(kāi)始的長(zhǎng)度為 tlen 的子串，即重新形成當(dāng)前串中 pos 開(kāi)始至新串串尾 cluren1 的一些字符，這些字符分別由相隔 tlen 個(gè)位置的對(duì)應(yīng)字符前移而來(lái)。 （5）返回當(dāng)前串。子串的定位操作通常稱為字符串的模式匹配，是指在當(dāng)前串中查找與子串，若查找成功則返回該子串的位置。 [13]定位操作的基本思想是：(1)設(shè)主串S=s1,s2,…sn，子串 P=p1,p2,…pm。 （2）i 為指向 S 中字符的指針，j 為指向 P 中字符的指針，從主串 S 中第 pos 個(gè)字符起和模式中第一個(gè)字符比較。若相等，則繼續(xù)逐個(gè)比較后續(xù)字符；否則從主串的下個(gè)字符起再重新和模式字符比較。 （3）匹配失?。簊i!=pj 時(shí)，(sij+1 … si1)=(p1 … pj1)。 （4）回溯：i=ij+1。j=，所以時(shí)間復(fù)雜度是 O(m*n)。[9]改進(jìn)后的模式匹配算法稱作 KMP 算法。這個(gè)算法是同 , , 同時(shí)發(fā)現(xiàn)的。在該算法中指針 i 沒(méi)有回溯。它的核心思想是利用已經(jīng)得到的部分匹配信息來(lái)進(jìn)行后面的匹配過(guò)程 。改進(jìn)后的算法如下：int String::Index_KMP(char *t,int k) //KMP 算法{ int i,j,tlen。 i=k。j=0。tlen=strlen(t)。 while((icurlen)amp。amp。(jtlen)) if(str[i]==t[j]){i++。j++} //如果子串和主串相等，兩個(gè)下標(biāo)均自增 else j=next[j]。 if(j==tlen) return (itlen)。 else return 1。}復(fù)制字符串是指將一個(gè)已知的字符串復(fù)制，定義一個(gè) char 型指針 T，并開(kāi)辟一塊空間。令 T等于已被定義的 str 即可。 [16]串的比較的算法是：在兩個(gè)串的當(dāng)前長(zhǎng)度范圍內(nèi)，逐個(gè)取出字符進(jìn)行比較，一旦發(fā)現(xiàn)不相等，立即根據(jù)大于或小于的關(guān)系返回位置值。串的聯(lián)結(jié)是指把第二個(gè)串直接放到第一個(gè)串的尾部，再修改第一個(gè)串的長(zhǎng)度?；舅惴ㄊ牵合扰袛鄡蓚€(gè)串 S1，S2 連接起來(lái)是否大于串 S，若不大，則先把串 S1 的所有字符放入串 S 中，然后將串 S2 的所有字符放在串 S1 的后面依次放入串 S 中，并返回邏輯真。若兩個(gè)串的長(zhǎng)度大于串 S，S 的當(dāng)前長(zhǎng)度就等于 S 的最大長(zhǎng)度，并返回邏輯假。 [7]返回子串操作的功能是：在當(dāng)前串中截取從 pos 開(kāi)始的長(zhǎng)為 tlen 的子串，并返回該子串。過(guò)程是：（1）輸入所要返回的子串的位置 pos 及長(zhǎng)度 tlen。 （2）檢查位置是否合適，當(dāng) poscurlen1 或 pos0 或 len1，則返回邏輯假。 （2）若長(zhǎng)度超過(guò)最大可供截取長(zhǎng)度，則將長(zhǎng)度調(diào)整為最大可截取的長(zhǎng)度。 （3）生成一個(gè)字符串，將當(dāng)前串中從 pos 開(kāi)始的長(zhǎng)度為 tlen的內(nèi)容復(fù)制到該串中并返回字符串。串的反轉(zhuǎn)操作是將串倒置輸出。找出字符串中元音字符的個(gè)數(shù)。在