數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯(存儲版)
【正文】 制給 t [ipos+1]=base[i]。順序串輸出操作實(shí)現(xiàn)算法為： ?① 檢查串時否為空串，若為空，輸出空串信息； ?② 若串非空，則利用循環(huán)輸出串的內(nèi)容； ?③ 操作成功，結(jié)束。 33 數(shù)據(jù)結(jié)構(gòu)與算法 串的存儲表示 ?順序串連接操作實(shí)現(xiàn)算法為： ?① 計算連接后的串長，如果超出順序串的maxlen，重新分配空間； ?② 否則，從當(dāng)前串的第 base[0]+1個位置起，依次將 t串中每一個字符復(fù)制到 s； ?③ 更新當(dāng)前串長，操作成功，返回。 maxlen=base[0]+[0]。 37 數(shù)據(jù)結(jié)構(gòu)與算法 串的存儲表示 【 算法 36】 bool SqString::SubString(int pos,int len,SqString amp。 } } 38 數(shù)據(jù)結(jié)構(gòu)與算法 串的存儲表示 ? 串的鏈?zhǔn)酱鎯? ?串的順序存儲方式節(jié)約了系統(tǒng)開銷，但是如果需要經(jīng)常對串執(zhí)行插入、刪除子串等操作，就需要頻繁移動串中的字符，因此，我們引入串的另一種存儲方式 ——鏈?zhǔn)酱鎯Γ址Q動態(tài)存儲。那么串s=“ ABCDEFGHI”在結(jié)點(diǎn)大小為 4的鏈串存儲結(jié)構(gòu)如圖 39所示。 LinkString(LinkString amp。 //其他操作 }。 48 數(shù)據(jù)結(jié)構(gòu)與算法 串的模式匹配算法 ?設(shè)主串 s= “ababcabcacba”模式串t= “abcac”。t) { if((base[0]==0)||([0]==0)) //為空 return 0。 } } if(j[0]) return [0]。 SqString *iStartAddress。 //“查找文本”處理函數(shù) //其他功能，略 }。in_str[0]!=39。 ? RTable[Row_Count].iLength=pstrbase[0]。iRow_Count。 ()。在鏈?zhǔn)酱薪o出了串的插入、刪除等算法。 void main() { Editer t1。 SqString s(str)。為文本串輸入完畢 ? SqString *pstr=new SqString(in_str)。)amp。} void InputText()。 59 數(shù)據(jù)結(jié)構(gòu)與算法 文本編輯 60 數(shù)據(jù)結(jié)構(gòu)與算法 文本編輯 ?其相應(yīng)的行表如表 31所示，每一個行表項(xiàng)包含行號、該行的起始地址、長度。 } 54 數(shù)據(jù)結(jié)構(gòu)與算法 串的模式匹配算法 else { i=ij+2。如圖 312所示。 47 數(shù)據(jù)結(jié)構(gòu)與算法 串的模式匹配算法 ?BruteForce算法簡稱為 BF算法，亦稱簡單匹配算法，設(shè)主串 s=s1…s n，模式串t=t1…t m，其基本思想是： 1. 從主串 s的第一個字符 s1開始和模式串 t=t1…t m中的第一個字符 t1比較； 2. 若相等，則繼續(xù)逐個比較后續(xù)字符， s2和 t2； 3. 若不相等，從主串 s的第二個字符 s2開始重新與模式串 t的第一個字符 t1進(jìn)行比較。t) 。 42 數(shù)據(jù)結(jié)構(gòu)與算法 串的存儲表示 public: LinkString()。例如，一個字符串s=“ ABCDEFGHI”，那么它的單鏈表存儲方式如圖 38所示。 [0]=len。如圖 37所示。 delete []base。 } } 32 數(shù)據(jù)結(jié)構(gòu)與算法 串的存儲表示 ?串的連接 ?串的連接，顧名思義，是指將兩個已有的串連接成為一個串。 return true。 } else { for(int i=pos。 //插入元素 base[0]+=[0]。 t) { if(pos1||posbase[0]+1||pos1+[0]maxlen) { cout插入失敗 endl。 base[0]=[0]。 for(int i=0。 ?（ 1）構(gòu)造空的順序串。//求當(dāng)前串從 pos開始長度為 len的子串 int Indexof(SqString amp。t)。 14 數(shù)據(jù)結(jié)構(gòu)與算法 串的存儲表示 ?定義順序串： define MAX 100 class SqString { public: char *base。例如： eye、mum、 refer、 level等。 ?例如： s1= “data structure” s2= “data structure” s3= “datastructure ” //s1與 s2相等， s3與 s1和 s2均不相等 4 數(shù)據(jù)結(jié)構(gòu)與算法 串的類型定義 ?按照串中字符的 次序 ， 逐一 比較兩個字符串中字符的大小，以確定兩個串的大小關(guān)系的操作，稱為 串的比較 。 ?例如： s= “ ” //空格串，長度為 4 2 數(shù)據(jù)結(jié)構(gòu)與算法 串的類型定義 ?一個串中任意個連續(xù)字符組成的子序列稱為該串的 子串 。 ?例如： s= “” //空串，長度為 0 組成串的字符均為空格的串稱為 空格串 或空白串。 ?當(dāng)且僅當(dāng) 串的 長度相等并且對應(yīng)位置上的字符都相同 時，稱這兩個 字符串是相等的 。單個英文單詞的回文符合狹義回文。 13 數(shù)據(jù)結(jié)構(gòu)與算法 串的存儲表示 ?借助于順序存儲時數(shù)組的 0號下標(biāo)存儲串長，即有效地利用了空間，又使得串中字符的位序與其存放位置（下標(biāo)）一致，如圖 33所示。//析構(gòu)函數(shù) 15 數(shù)據(jù)結(jié)構(gòu)與算法
畢業(yè)設(shè)計相關(guān)推薦
鄂ICP備17016276號-1