數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯-資料下載頁
2025-05-13 00:11本頁面
【正文】 55 數(shù)據(jù)結(jié)構(gòu)與算法 串的模式匹配算法 56 數(shù)據(jù)結(jié)構(gòu)與算法 串的模式匹配算法 ?限于篇幅，不再分析圖 313所示的串在后續(xù)階段的匹配過程，可按 KMP算法的思想繼續(xù)推導(dǎo)。 ?【 算法 39】 57 數(shù)據(jù)結(jié)構(gòu)與算法 文本編輯 ? 問題描述與算法分析 ?文本編輯是指利用計(jì)算機(jī)進(jìn)行編輯工作，修改字符數(shù)據(jù)的形式或格式，包括串的查找、插入、刪除等基本操作。 ?在進(jìn)行文本編輯時(shí)，我們把整個(gè)文本看成是一個(gè)字符串，稱為文本串，為了便于處理，進(jìn)一步地將文本串拆分成若干子串，即頁是文本串的子串，行又是頁的子串。 58 數(shù)據(jù)結(jié)構(gòu)與算法 文本編輯 ?例如有下列一段英文： ? NightSong in the Jungle ?Now Rann the Kite brings home the night ?That Mang the Bat sets free ?The herds are shut in barn and hut ?For loosed till dawn are we ?把這首小詩看成是一個(gè)文本串，輸入到內(nèi)存后如圖 314所示。 59 數(shù)據(jù)結(jié)構(gòu)與算法 文本編輯 60 數(shù)據(jù)結(jié)構(gòu)與算法 文本編輯 ?其相應(yīng)的行表如表 31所示，每一個(gè)行表項(xiàng)包含行號(hào)、該行的起始地址、長(zhǎng)度。 61 數(shù)據(jù)結(jié)構(gòu)與算法 文本編輯 ?為實(shí)現(xiàn)文本編輯問題的求解，我們定義一個(gè)文本編輯類 Editer如下（其中串的存儲(chǔ)類型采用 SqString）： define MAX 50 typedef struct Text_Row_Table {//行表元素結(jié)構(gòu)定義 int iRow。 SqString *iStartAddress。 int iLength。 }Text_Row_Table。 class Editer {//文本編輯類的定義 Text_Row_Table RTable[MAX]。 //行表 int Row_Count。 //行數(shù) 62 數(shù)據(jù)結(jié)構(gòu)與算法 文本編輯 public: Editer(){Row_Count=0。} void InputText()。 //“輸入文本”處理函數(shù) void SearchText()。 //“查找文本”處理函數(shù) //其他功能，略 }。 63 數(shù)據(jù)結(jié)構(gòu)與算法 文本編輯 ? 算法實(shí)現(xiàn) ?1. 輸入文本 ?由于各行的文本子串以行表項(xiàng)為標(biāo)識(shí)，因此輸入階段的處理，主要完成的就是每輸入一行文本子串就為其建立一個(gè)行表項(xiàng)，記錄行號(hào)、起始地址與行內(nèi)串長(zhǎng)度。如算法 310所示。 64 數(shù)據(jù)結(jié)構(gòu)與算法 文本編輯 ? 【 算法 310】 ? void Editer::InputText() ? { ? char in_str[MAX]。 ? while((in_str,MAX,39。\n39。)amp。amp。in_str[0]!=39。\\39。) ? {//約定以 39。\n39。為換行， 39。\\39。為文本串輸入完畢 ? SqString *pstr=new SqString(in_str)。 ? RTable[Row_Count].iRow=Row_Count+1。 ? RTable[Row_Count].iLength=pstrbase[0]。 ? RTable[Row_Count].iStartAddress=pstr。 ? Row_Count++。 ? } ? } 65 數(shù)據(jù)結(jié)構(gòu)與算法 文本編輯 ?2. 查找文本 【 算法 311】 void Editer::SearchText() { cout請(qǐng)輸入要查找的文本串 endl。 char str[MAX]。 cinstr。 SqString s(str)。 for(int i=0,j。iRow_Count。i++) { SqString *p=RTable[i].iStartAddress。 if(j=pIndexof_KMP(s)) 66 數(shù)據(jù)結(jié)構(gòu)與算法 文本編輯 { cout找到了，行號(hào) RTable[i].iRow 位置 jendl。 break。 } } if(i=Row_Count) cout未找到！ endl。 } 67 數(shù)據(jù)結(jié)構(gòu)與算法 文本編輯 ?3. 主程序與測(cè)試 include iostream using namespace std。 void main() { Editer t1。 ()。 ()。 } 68 數(shù)據(jù)結(jié)構(gòu)與算法 ?運(yùn)行結(jié)果： NightSong in the Jungle↙ Now Rann the Kite brings home the night↙ That Mang the Bat sets free↙ \↙ ?請(qǐng)輸入要查找的文本串 ?Kite brings↙ ?找到了，行號(hào) 2 位置 14 69 數(shù)據(jù)結(jié)構(gòu)與算法 小結(jié) ?串是一種數(shù)據(jù)類型受到限制的特殊線性表，規(guī)定表中的每一個(gè)元素類型只能為字符型。串雖然是線性表，但又有它特殊的地方，即表中元素為單個(gè)字符，但串結(jié)構(gòu)通常不是單個(gè)處理某一個(gè)字符元素，通常是整串進(jìn)行討論。 ?串的存儲(chǔ)方式與線性表類似，也具有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種方式。串的插入、刪除等操作較線性表上的操作要復(fù)雜一些。在順序串中給出了串的構(gòu)造、插入、刪除、串的輸出和串的連接等算法。在鏈?zhǔn)酱薪o出了串的插入、刪除等算法。 70 數(shù)據(jù)結(jié)構(gòu)與算法
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1