《數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯（71頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、第3章 串與文本編輯3.1 串的類型定義3.2 串的存儲表示3.3 串的模式匹配算法3.4 文本編輯3.5 小結(jié) 0數(shù)據(jù)結(jié)構(gòu)與算法 3.1 串的類型定義1. 串的相關(guān)術(shù)語串是由零個或多個字符組成的有限序列，記為：s= s1s2sn 。其中s是串名；雙引號內(nèi)的字符序列s1s2sn是串值；n(n=0)表示串的長度。 1 數(shù)據(jù)結(jié)構(gòu)與算法 3.1 串的類型定義例如：s1= “data structure” /串，長度為14 串長度為零的串稱為空串。例如：s= “” /空串，長度為0 組成串的字符均為空格的串稱為空格串或空白串。 例如：s= “ ” /空格串，長度為4 2數(shù)據(jù)結(jié)構(gòu)與算法 3.1 串的類型
2、定義一個串中任意個連續(xù)字符組成的子序列稱為該串的子串?？沾侨魏未淖哟?。例如：s1 = “data structure” s2= “data” /s2是s1的子串 s3= “structure” /s3是s1的子串 s4= “datastructure” /s4不是s1的子串包含子串的串稱為主串。上例中s1為主串。 3 數(shù)據(jù)結(jié)構(gòu)與算法 3.1 串的類型定義子串的序號是該子串的第一個字符在主串中的序號。在上例子串s2在s1中的序號為1，s3在s1中的序號為6。S4不是s1的子串，也可以說，s4在s1中的序號為0。當(dāng)且僅當(dāng)串的長度相等并且對應(yīng)位置上的字符都相同時，稱這兩個字符串是相等的。例如：s
3、1= “data structure” s2= “data structure” s3= “datastructure ” /s1與s2相等，s3與s1和s2均不相等 4 數(shù)據(jù)結(jié)構(gòu)與算法 3.1 串的類型定義按照串中字符的次序，逐一比較兩個字符串中字符的大小，以確定兩個串的大小關(guān)系的操作，稱為串的比較。例如：s5=data，s6= DATA，則有s5 s6的比較結(jié)果為1，s5 =0Structure:S=| ai-1,ai D, i=2,3,noPerations:ConstructString()/操作結(jié)果：創(chuàng)建一個空的串sDestructString()/操作條件：已有串s/操作結(jié)果：銷毀
4、當(dāng)前串s StringLen() /操作條件：已有串s/操作結(jié)果：得到當(dāng)前串s的實(shí)際長度9數(shù)據(jù)結(jié)構(gòu)與算法 3.1 串的類型定義StringCpy(t)/操作條件：已有串s和參數(shù)串t/操作結(jié)果：將t復(fù)制到當(dāng)前串s中OutputString()/操作條件：已有串s/操作結(jié)果：輸出當(dāng)前串sSubString(pos, len, 11數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲表示3.2.1 串的順序存儲將串所占用空間的大小稱為串容量，實(shí)際存在的元素個數(shù)稱為串長，如圖3-1所示。 12 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲表示為了表示串的結(jié)束，可在串內(nèi)容最后一個有效字符后，再多開辟一個存儲空間，存放結(jié)束標(biāo)志0 （C/
5、C+語言中的字符串就采用這種方法），如圖3-2所示。 13 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲表示借助于順序存儲時數(shù)組的0號下標(biāo)存儲串長，即有效地利用了空間，又使得串中字符的位序與其存放位置（下標(biāo)）一致，如圖3-3所示。 14 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲表示定義順序串：#define MAX 100class SqStringpublic:char *base;/存儲串的字符數(shù)組/base0表示串的實(shí)際長度,不另設(shè)結(jié)束標(biāo)志int maxlen;/表示串的最大長度public:SqString();/構(gòu)造函數(shù)SqString(char *s); /構(gòu)造函數(shù) SqString(SqString
6、 /構(gòu)造函數(shù)SqString();/析構(gòu)函數(shù)15數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲表示bool InsertString(int pos,SqString /在串的指定位置pos插入一個子串tbool DelSubString(int pos,int len,SqString /刪除當(dāng)前串的子串,并由t返回void OutputString() ;/輸出串中所有字符void ConnectString(SqString /在當(dāng)前串尾連接串tbool SubString(int pos,int len,SqString /求當(dāng)前串從pos開始長度為len的子串int Indexof(SqStrin
7、g /求模式串t在當(dāng)前串中第一次出現(xiàn)的位置int Indexof_KMP(SqString /KMP法求模式串t在當(dāng)前串中第一次出現(xiàn)的位置 void GetNext(int next);/KMP模式匹配算法輔助函數(shù)/其他操作; 16數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲表示順序串的構(gòu)造與析構(gòu) 串的構(gòu)造有三種方法，分別是構(gòu)造空串、由基本類型的字符串構(gòu)造一個新串以及使用串對象來構(gòu)造串。下面給出三種方法構(gòu)造串的實(shí)現(xiàn)過程。（1）構(gòu)造空的順序串?！舅惴?-1-1】SqString:SqString()maxlen=MAX; base=new charmaxlen+1; /0下標(biāo)留作記錄長度base0=0; 1
8、7數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲表示（2）由基本字符串構(gòu)造一個新串。【算法3-1-2】SqString:SqString(char *s)/由機(jī)內(nèi)標(biāo)準(zhǔn)串構(gòu)造 maxlen=MAX;base= new charmaxlen+1;base0=strlen(s);for(int i=0;si!=0;i+)basei+1=si; 18 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲表示（3）使用串對象來構(gòu)造串?！舅惴?-1-3】SqString:SqString(SqStringbase=new charmaxlen+1;base0=t.base0;for(int i=1;i=base0;i+)basei=t.b
9、asei; 19 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲表示（4）析構(gòu)函數(shù)【算法3-1-4】SqString:SqString() delete base; 20 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲表示順序串插入操作順序串插入操作的功能是將一個指定的串插入到當(dāng)前串中的指定位置之前，以s串和t串分別表示當(dāng)前串和待插入串，則插入前后s串與t串的狀態(tài)如圖3-4（a）和圖3-4（b）所示。 21 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲表示 22 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲表示順序串插入操作實(shí)現(xiàn)算法為：檢查插入位置的合法性，即當(dāng)插入位置posbase0，或base0+t.base0 maxlen（沒有足夠空間插
10、入t）時，提示錯誤信息，終止程序；從pos指向的位置開始，一直到最后的字符，每個字符都要向后移動，移動的長度為t串的長度；插入t串，修改s的串長，操作成功，結(jié)束。 23 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲表示【算法3-2】bool SqString:InsertString(int pos,SqStringi-) basei+t.base0=basei; /元素后移24數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲表示for(i=1;i=t.base0;i+)basepos-1+i=t.basei; /插入元素base0+=t.base0;return true; 25 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲表示順
11、序串刪除操作順序串刪除操作的功能是刪除s串中從第pos個位置開始的長度為len的子串。如圖3-5所示。 26 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲表示 27 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲表示順序串刪除操作實(shí)現(xiàn)算法為： 檢查參數(shù)的合法性，有兩種不合法的操作條件：一是pos的值不在串s的長度范圍內(nèi)，即posbase0；二是從串s第pos個位置開始不存在長度為len的子串，即pos+len-1base0； 將待刪除的子串復(fù)制給t； 在s中刪除指定的子串，修改s的串長，操作成功，結(jié)束。 28 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲表示【算法3-3】bool SqString:DelSubString(int
12、 pos,int len,SqStringreturn false;else for(int i=pos;i=pos-1+len;i+) /刪除的元素復(fù) 制給t t.basei-pos+1=basei;t.base0=len; 29數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲表示for(i=pos+len;i=base0;i+) /元素前移 basei-len=basei;base0-=len;return true; 30 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲表示輸出順序串操作順序串輸出操作的功能是將串中的字符全部輸出。順序串輸出操作實(shí)現(xiàn)算法為：檢查串時否為空串，若為空，輸出空串信息；若串非空，則利用循環(huán)輸
13、出串的內(nèi)容；操作成功，結(jié)束。 31 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲表示【算法3-4】void SqString:OutputString() if(base0=0) /判斷串是否為空串cout空串endl;else for(int i=1;i=base0;i+)coutbasei;coutmaxlen) char *p=new charbase0+t.base0;for(int i=1;i=base0;i+)pi=basei;delete base;base=p;maxlen=base0+t.base0; for(int i=1;i=t.base0;i+)basebase0+i=t.base
14、i;base0+=t.base0; 35數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲表示6. 求子串（非空子串）求子串的定義為將串s中的第pos個字符開始長度為len的子串，復(fù)制到串t中。如圖3-7所示。 36 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲表示順序串中求子串的實(shí)現(xiàn)算法為：檢查參數(shù)的合法性，當(dāng)posbase0，或lenbase0時，操作失??；將當(dāng)前串從pos指向位置開始的長度為len的子串復(fù)制到串t中；操作成功，結(jié)束。 37 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲表示【算法3-6】bool SqString:SubString(int pos,int len,SqString return false;els
15、e for(int i=pos;i=len;i+)t.basei-pos+1=basei; t.base0=len;return true; 38數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲表示3.2.2 串的鏈?zhǔn)酱鎯Υ捻樞虼鎯Ψ绞焦?jié)約了系統(tǒng)開銷，但是如果需要經(jīng)常對串執(zhí)行插入、刪除子串等操作，就需要頻繁移動串中的字符，因此，我們引入串的另一種存儲方式鏈?zhǔn)酱鎯?，又稱動態(tài)存儲。這樣就可以避免頻繁的插入、刪除操作帶來的效率低下等問題。 39 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲表示在鏈?zhǔn)酱鎯Y(jié)構(gòu)下，存儲空間被分成一系列大小相同的結(jié)點(diǎn)，每個結(jié)點(diǎn)包含兩個域：字符域data和指針域next。其中，字符域用來存放字符，指
16、針域則用來存放指向下一個結(jié)點(diǎn)的指針。一個串可用一個單鏈表來存儲。鏈表中的結(jié)點(diǎn)數(shù)目等于串的長度。例如，一個字符串s=“ABCDEFGHI”，那么它的單鏈表存儲方式如圖3-8所示。 40 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲表示 41 數(shù)據(jù)結(jié)構(gòu)與算法為了提高串的鏈?zhǔn)酱鎯Φ拇鎯γ芏?，?jié)省空間，可以將鏈串的結(jié)點(diǎn)大小設(shè)置為4。那么串s=“ABCDEFGHI”在結(jié)點(diǎn)大小為4的鏈串存儲結(jié)構(gòu)如圖3-9所示。 3.2 串的存儲表示鏈串的存儲結(jié)構(gòu)可定義如下：#define N 4struct LStringNode char dataN;struct LStringNode *next;class LinkStrin
17、g LStringNode *head;int length; 42 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲表示public:LinkString();LinkString(char *t);LinkString(LinkString LinkString();bool InsertString(int pos,LinkString bool DelSubString(int pos,int len,LinkString void OutputString() ;/其他操作; 43 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲表示鏈串的插入操作與單鏈表的插入過程相似，但又有明顯的區(qū)別，單鏈表中每一個結(jié)點(diǎn)都是一個
18、單獨(dú)的元素，而塊鏈?zhǔn)降拇忻恳粔K有若干個獨(dú)立的元素，如圖3-10（a）所示，當(dāng)插入位置不是剛好位于每一塊的起始處時，插入子串的處理相對要復(fù)雜。為盡量減少插入時字符的移動，可采用犧牲一定存儲空間的辦法，將插入點(diǎn)所在塊的串拆分成兩個塊，無效字符的位置用“#”填充，如圖3-10（b）所示，這樣，待插入的串就可以直接進(jìn)行鏈接。 44 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲表示 45 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲表示鏈串插入操作實(shí)現(xiàn)算法為：判斷插入位置是否有效，無效立即結(jié)束；否則繼續(xù)；找到插入位置，以指針p指向pos所在塊或其前一塊；若pos對塊長取余不為0，p指向pos所在塊，生成新結(jié)點(diǎn)，對該塊進(jìn)行拆分
19、；否則，p指向pos所在塊的前一塊；將t串鏈接到s串中； 操作成功，結(jié)束?！舅惴?-7】46數(shù)據(jù)結(jié)構(gòu)與算法 3.3 串的模式匹配算法設(shè)s和t是給定的兩個串，其長度分別為n和m，且有nm，在串s中找到等于子串t的過程稱為模式匹配，其中，串s稱為主串，t稱為模式。如果在s中找到等于t的子串，則稱匹配成功，函數(shù)返回t在s中的首次出現(xiàn)的存儲位置(或序號)，否則匹配失敗，返回0。 47 數(shù)據(jù)結(jié)構(gòu)與算法 3.3 串的模式匹配算法Brute-Force算法簡稱為BF算法，亦稱簡單匹配算法，設(shè)主串s=s1sn，模式串t=t1tm，其基本思想是：1. 從主串s的第一個字符s1開始和模式串t=t1tm中的第一個字
20、符t1比較；2. 若相等，則繼續(xù)逐個比較后續(xù)字符，s2和t2；3. 若不相等，從主串s的第二個字符s2開始重新與模式串t的第一個字符t 1進(jìn)行比較。4. 重復(fù)上述過程，如果在主串s中找到一個與串t相同的子串，則匹配成功，返回模式串t在主串s主的序號；如果比較完主串s的所有字符序列，沒有和模式串t相等的子串，則匹配失敗返回0。48數(shù)據(jù)結(jié)構(gòu)與算法 3.3 串的模式匹配算法設(shè)主串s=“ababcabcacba”模式串t=“abcac”。s的長度為n(n=12)，t的長度為m（m=5）。指針i、j分別為主串s、模式串t當(dāng)前比較字符的下標(biāo)。模式匹配的過程如圖3-11所示。 49 數(shù)據(jù)結(jié)構(gòu)與算法 3.3
21、串的模式匹配算法 50 數(shù)據(jù)結(jié)構(gòu)與算法 3.3 串的模式匹配算法 51 數(shù)據(jù)結(jié)構(gòu)與算法 3.3 串的模式匹配算法上述匹配過程中，可以得出以下結(jié)果：（1）若在前k-1(k1)次比較過程中未匹配成功，則第k次比較是從s串的第k個字符sk開始和t中的第一個字符t1比較；（2）設(shè)某次匹配有sitj，其中1in，1jm，ij，則應(yīng)有si-1=tj-1，. si-j+1=t1。再由（1）可知，下一次匹配串t右移一個位置，使得與字符t1對應(yīng)的s的開始位置是i-j+2，即主串的字符s i-j+2與模式串的第一個字符t1進(jìn)行比較。如圖3-12所示。52數(shù)據(jù)結(jié)構(gòu)與算法 3.3 串的模式匹配算法 53 數(shù)據(jù)結(jié)構(gòu)與算
22、法 3.3 串的模式匹配算法【算法3-8】int SqString:Indexof(SqString int i=1,j=1 ;while(i=base0 /掃描完畢，匹配成功elsereturn 0;/匹配失敗 55 數(shù)據(jù)結(jié)構(gòu)與算法 3.3 串的模式匹配算法 56 數(shù)據(jù)結(jié)構(gòu)與算法 3.3 串的模式匹配算法限于篇幅，不再分析圖3-13所示的串在后續(xù)階段的匹配過程，可按KMP算法的思想繼續(xù)推導(dǎo)。【算法3-9】 57 數(shù)據(jù)結(jié)構(gòu)與算法 3.4 文本編輯3.4.1 問題描述與算法分析文本編輯是指利用計算機(jī)進(jìn)行編輯工作，修改字符數(shù)據(jù)的形式或格式，包括串的查找、插入、刪除等基本操作。在進(jìn)行文本編輯時，我們
23、把整個文本看成是一個字符串，稱為文本串，為了便于處理，進(jìn)一步地將文本串拆分成若干子串，即頁是文本串的子串，行又是頁的子串。 58 數(shù)據(jù)結(jié)構(gòu)與算法 3.4 文本編輯例如有下列一段英文： Night-Song in the JungleNow Rann the Kite brings home the nightThat Mang the Bat sets freeThe herds are shut in barn and hutFor loosed till dawn are we把這首小詩看成是一個文本串，輸入到內(nèi)存后如圖3-14所示。 59 數(shù)據(jù)結(jié)構(gòu)與算法 3.4 文本編輯 60 數(shù)據(jù)結(jié)構(gòu)
24、與算法 3.4 文本編輯其相應(yīng)的行表如表3-1所示，每一個行表項(xiàng)包含行號、該行的起始地址、長度。 61 數(shù)據(jù)結(jié)構(gòu)與算法 3.4 文本編輯為實(shí)現(xiàn)文本編輯問題的求解，我們定義一個文本編輯類Editer如下（其中串的存儲類型采用3.2.1節(jié)的順序串SqString）：#define MAX 50typedef struct Text_Row_Table/行表元素結(jié)構(gòu)定義int iRow;SqString *iStartAddress;int iLength;Text_Row_Table;class Editer /文本編輯類的定義Text_Row_Table RTableMAX; /行表int Ro
25、w_Count; /行數(shù)62數(shù)據(jù)結(jié)構(gòu)與算法 3.4 文本編輯public:Editer()Row_Count=0;void InputText(); /“輸入文本”處理函數(shù)void SearchText(); /“查找文本”處理函數(shù)/其他功能，略; 63 數(shù)據(jù)結(jié)構(gòu)與算法 3.4 文本編輯3.4.2 算法實(shí)現(xiàn)1. 輸入文本由于各行的文本子串以行表項(xiàng)為標(biāo)識，因此輸入階段的處理，主要完成的就是每輸入一行文本子串就為其建立一個行表項(xiàng)，記錄行號、起始地址與行內(nèi)串長度。如算法3-10所示。 64 數(shù)據(jù)結(jié)構(gòu)與算法 3.4 文本編輯【算法3-10】 void Editer:InputText() char i
26、n_strMAX; while(cin.getline(in_str,MAX,n) RTableRow_Count.iRow=Row_Count+1; RTableRow_Count.iLength=pstr-base0; RTableRow_Count.iStartAddress=pstr; Row_Count+; 65數(shù)據(jù)結(jié)構(gòu)與算法 3.4 文本編輯2. 查找文本【算法3-11】void Editer:SearchText() cout請輸入要查找的文本串str;SqString s(str);for(int i=0,j;iIndexof_KMP(s) 66 數(shù)據(jù)結(jié)構(gòu)與算法 3.4 文本編
27、輯 cout找到了，行號RTablei.iRow 位置j=Row_Count)cout未找到！endl; 67 數(shù)據(jù)結(jié)構(gòu)與算法 3.4 文本編輯3. 主程序與測試#include iostreamusing namespace std;void main() Editer t1;t1.InputText();t1.SearchText(); 68 數(shù)據(jù)結(jié)構(gòu)與算法 運(yùn)行結(jié)果：Night-Song in the JungleNow Rann the Kite brings home the nightThat Mang the Bat sets free請輸入要查找的文本串Kite brings找到了，行號2 位置14 69 數(shù)據(jù)結(jié)構(gòu)與算法 3.5 小結(jié)串是一種數(shù)據(jù)類型受到限制的特殊線性表，規(guī)定表中的每一個元素類型只能為字符型。串雖然是線性表，但又有它特殊的地方，即表中元素為單個字符，但串結(jié)構(gòu)通常不是單個處理某一個字符元素，通常是整串進(jìn)行討論。串的存儲方式與線性表類似，也具有順序存儲和鏈?zhǔn)酱鎯煞N方式。串的插入、刪除等操作較線性表上的操作要復(fù)雜一些。在順序串中給出了串的構(gòu)造、插入、刪除、串的輸出和串的連接等算法。在鏈?zhǔn)酱薪o出了串的插入、刪除等算法。 70 數(shù)據(jù)結(jié)構(gòu)與算法
數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯
