數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯

《數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯（71頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第3章 串與文本編輯3.1 串的類型定義3.2 串的存儲(chǔ)表示3.3 串的模式匹配算法3.4 文本編輯3.5 小結(jié) 0數(shù)據(jù)結(jié)構(gòu)與算法 3.1 串的類型定義1. 串的相關(guān)術(shù)語串是由零個(gè)或多個(gè)字符組成的有限序列，記為：s= s1s2sn 。其中s是串名；雙引號(hào)內(nèi)的字符序列s1s2sn是串值；n(n=0)表示串的長(zhǎng)度。 1 數(shù)據(jù)結(jié)構(gòu)與算法 3.1 串的類型定義例如：s1= “data structure” /串，長(zhǎng)度為14 串長(zhǎng)度為零的串稱為空串。例如：s= “” /空串，長(zhǎng)度為0 組成串的字符均為空格的串稱為空格串或空白串。 例如：s= “ ” /空格串，長(zhǎng)度為4 2數(shù)據(jù)結(jié)構(gòu)與算法 3.1 串的類型

2、定義一個(gè)串中任意個(gè)連續(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 串的類型定義子串的序號(hào)是該子串的第一個(gè)字符在主串中的序號(hào)。在上例子串s2在s1中的序號(hào)為1，s3在s1中的序號(hào)為6。S4不是s1的子串，也可以說，s4在s1中的序號(hào)為0。當(dāng)且僅當(dāng)串的長(zhǎng)度相等并且對(duì)應(yīng)位置上的字符都相同時(shí)，稱這兩個(gè)字符串是相等的。例如：s

3、1= “data structure” s2= “data structure” s3= “datastructure ” /s1與s2相等，s3與s1和s2均不相等 4 數(shù)據(jù)結(jié)構(gòu)與算法 3.1 串的類型定義按照串中字符的次序，逐一比較兩個(gè)字符串中字符的大小，以確定兩個(gè)串的大小關(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)建一個(gè)空的串sDestructString()/操作條件：已有串s/操作結(jié)果：銷毀

4、當(dāng)前串s StringLen() /操作條件：已有串s/操作結(jié)果：得到當(dāng)前串s的實(shí)際長(zhǎng)度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 串的存儲(chǔ)表示3.2.1 串的順序存儲(chǔ)將串所占用空間的大小稱為串容量，實(shí)際存在的元素個(gè)數(shù)稱為串長(zhǎng)，如圖3-1所示。 12 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲(chǔ)表示為了表示串的結(jié)束，可在串內(nèi)容最后一個(gè)有效字符后，再多開辟一個(gè)存儲(chǔ)空間，存放結(jié)束標(biāo)志0 （C/

5、C+語言中的字符串就采用這種方法），如圖3-2所示。 13 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲(chǔ)表示借助于順序存儲(chǔ)時(shí)數(shù)組的0號(hào)下標(biāo)存儲(chǔ)串長(zhǎng)，即有效地利用了空間，又使得串中字符的位序與其存放位置（下標(biāo)）一致，如圖3-3所示。 14 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲(chǔ)表示定義順序串：#define MAX 100class SqStringpublic:char *base;/存儲(chǔ)串的字符數(shù)組/base0表示串的實(shí)際長(zhǎng)度,不另設(shè)結(jié)束標(biāo)志int maxlen;/表示串的最大長(zhǎng)度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 串的存儲(chǔ)表示bool InsertString(int pos,SqString /在串的指定位置pos插入一個(gè)子串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開始長(zhǎng)度為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 串的存儲(chǔ)表示順序串的構(gòu)造與析構(gòu) 串的構(gòu)造有三種方法，分別是構(gòu)造空串、由基本類型的字符串構(gòu)造一個(gè)新串以及使用串對(duì)象來構(gòu)造串。下面給出三種方法構(gòu)造串的實(shí)現(xiàn)過程。（1）構(gòu)造空的順序串?！舅惴?-1-1】SqString:SqString()maxlen=MAX; base=new charmaxlen+1; /0下標(biāo)留作記錄長(zhǎng)度base0=0; 1

8、7數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲(chǔ)表示（2）由基本字符串構(gòu)造一個(gè)新串?！舅惴?-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 串的存儲(chǔ)表示（3）使用串對(duì)象來構(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 串的存儲(chǔ)表示（4）析構(gòu)函數(shù)【算法3-1-4】SqString:SqString() delete base; 20 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲(chǔ)表示順序串插入操作順序串插入操作的功能是將一個(gè)指定的串插入到當(dāng)前串中的指定位置之前，以s串和t串分別表示當(dāng)前串和待插入串，則插入前后s串與t串的狀態(tài)如圖3-4（a）和圖3-4（b）所示。 21 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲(chǔ)表示 22 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲(chǔ)表示順序串插入操作實(shí)現(xiàn)算法為：檢查插入位置的合法性，即當(dāng)插入位置posbase0，或base0+t.base0 maxlen（沒有足夠空間插

10、入t）時(shí)，提示錯(cuò)誤信息，終止程序；從pos指向的位置開始，一直到最后的字符，每個(gè)字符都要向后移動(dòng)，移動(dòng)的長(zhǎng)度為t串的長(zhǎng)度；插入t串，修改s的串長(zhǎng)，操作成功，結(jié)束。 23 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲(chǔ)表示【算法3-2】bool SqString:InsertString(int pos,SqStringi-) basei+t.base0=basei; /元素后移24數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲(chǔ)表示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 串的存儲(chǔ)表示順

11、序串刪除操作順序串刪除操作的功能是刪除s串中從第pos個(gè)位置開始的長(zhǎng)度為len的子串。如圖3-5所示。 26 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲(chǔ)表示 27 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲(chǔ)表示順序串刪除操作實(shí)現(xiàn)算法為： 檢查參數(shù)的合法性，有兩種不合法的操作條件：一是pos的值不在串s的長(zhǎng)度范圍內(nèi)，即posbase0；二是從串s第pos個(gè)位置開始不存在長(zhǎng)度為len的子串，即pos+len-1base0； 將待刪除的子串復(fù)制給t； 在s中刪除指定的子串，修改s的串長(zhǎng)，操作成功，結(jié)束。 28 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲(chǔ)表示【算法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 串的存儲(chǔ)表示for(i=pos+len;i=base0;i+) /元素前移 basei-len=basei;base0-=len;return true; 30 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲(chǔ)表示輸出順序串操作順序串輸出操作的功能是將串中的字符全部輸出。順序串輸出操作實(shí)現(xiàn)算法為：檢查串時(shí)否為空串，若為空，輸出空串信息；若串非空，則利用循環(huán)輸

13、出串的內(nèi)容；操作成功，結(jié)束。 31 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲(chǔ)表示【算法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 串的存儲(chǔ)表示6. 求子串（非空子串）求子串的定義為將串s中的第pos個(gè)字符開始長(zhǎng)度為len的子串，復(fù)制到串t中。如圖3-7所示。 36 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲(chǔ)表示順序串中求子串的實(shí)現(xiàn)算法為：檢查參數(shù)的合法性，當(dāng)posbase0，或lenbase0時(shí)，操作失?。粚?dāng)前串從pos指向位置開始的長(zhǎng)度為len的子串復(fù)制到串t中；操作成功，結(jié)束。 37 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲(chǔ)表示【算法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 串的存儲(chǔ)表示3.2.2 串的鏈?zhǔn)酱鎯?chǔ)串的順序存儲(chǔ)方式節(jié)約了系統(tǒng)開銷，但是如果需要經(jīng)常對(duì)串執(zhí)行插入、刪除子串等操作，就需要頻繁移動(dòng)串中的字符，因此，我們引入串的另一種存儲(chǔ)方式鏈?zhǔn)酱鎯?chǔ)，又稱動(dòng)態(tài)存儲(chǔ)。這樣就可以避免頻繁的插入、刪除操作帶來的效率低下等問題。 39 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲(chǔ)表示在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下，存儲(chǔ)空間被分成一系列大小相同的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)包含兩個(gè)域：字符域data和指針域next。其中，字符域用來存放字符，指

16、針域則用來存放指向下一個(gè)結(jié)點(diǎn)的指針。一個(gè)串可用一個(gè)單鏈表來存儲(chǔ)。鏈表中的結(jié)點(diǎn)數(shù)目等于串的長(zhǎng)度。例如，一個(gè)字符串s=“ABCDEFGHI”，那么它的單鏈表存儲(chǔ)方式如圖3-8所示。 40 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲(chǔ)表示 41 數(shù)據(jù)結(jié)構(gòu)與算法為了提高串的鏈?zhǔn)酱鎯?chǔ)的存儲(chǔ)密度，節(jié)省空間，可以將鏈串的結(jié)點(diǎn)大小設(shè)置為4。那么串s=“ABCDEFGHI”在結(jié)點(diǎn)大小為4的鏈串存儲(chǔ)結(jié)構(gòu)如圖3-9所示。 3.2 串的存儲(chǔ)表示鏈串的存儲(chǔ)結(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 串的存儲(chǔ)表示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 串的存儲(chǔ)表示鏈串的插入操作與單鏈表的插入過程相似，但又有明顯的區(qū)別，單鏈表中每一個(gè)結(jié)點(diǎn)都是一個(gè)

18、單獨(dú)的元素，而塊鏈?zhǔn)降拇忻恳粔K有若干個(gè)獨(dú)立的元素，如圖3-10（a）所示，當(dāng)插入位置不是剛好位于每一塊的起始處時(shí)，插入子串的處理相對(duì)要復(fù)雜。為盡量減少插入時(shí)字符的移動(dòng)，可采用犧牲一定存儲(chǔ)空間的辦法，將插入點(diǎn)所在塊的串拆分成兩個(gè)塊，無效字符的位置用“#”填充，如圖3-10（b）所示，這樣，待插入的串就可以直接進(jìn)行鏈接。 44 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲(chǔ)表示 45 數(shù)據(jù)結(jié)構(gòu)與算法 3.2 串的存儲(chǔ)表示鏈串插入操作實(shí)現(xiàn)算法為：判斷插入位置是否有效，無效立即結(jié)束；否則繼續(xù)；找到插入位置，以指針p指向pos所在塊或其前一塊；若pos對(duì)塊長(zhǎng)取余不為0，p指向pos所在塊，生成新結(jié)點(diǎn)，對(duì)該塊進(jìn)行拆分

19、；否則，p指向pos所在塊的前一塊；將t串鏈接到s串中； 操作成功，結(jié)束?！舅惴?-7】46數(shù)據(jù)結(jié)構(gòu)與算法 3.3 串的模式匹配算法設(shè)s和t是給定的兩個(gè)串，其長(zhǎng)度分別為n和m，且有nm，在串s中找到等于子串t的過程稱為模式匹配，其中，串s稱為主串，t稱為模式。如果在s中找到等于t的子串，則稱匹配成功，函數(shù)返回t在s中的首次出現(xiàn)的存儲(chǔ)位置(或序號(hào))，否則匹配失敗，返回0。 47 數(shù)據(jù)結(jié)構(gòu)與算法 3.3 串的模式匹配算法Brute-Force算法簡(jiǎn)稱為BF算法，亦稱簡(jiǎn)單匹配算法，設(shè)主串s=s1sn，模式串t=t1tm，其基本思想是：1. 從主串s的第一個(gè)字符s1開始和模式串t=t1tm中的第一個(gè)字

20、符t1比較；2. 若相等，則繼續(xù)逐個(gè)比較后續(xù)字符，s2和t2；3. 若不相等，從主串s的第二個(gè)字符s2開始重新與模式串t的第一個(gè)字符t 1進(jìn)行比較。4. 重復(fù)上述過程，如果在主串s中找到一個(gè)與串t相同的子串，則匹配成功，返回模式串t在主串s主的序號(hào)；如果比較完主串s的所有字符序列，沒有和模式串t相等的子串，則匹配失敗返回0。48數(shù)據(jù)結(jié)構(gòu)與算法 3.3 串的模式匹配算法設(shè)主串s=“ababcabcacba”模式串t=“abcac”。s的長(zhǎng)度為n(n=12)，t的長(zhǎng)度為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個(gè)字符sk開始和t中的第一個(gè)字符t1比較；（2）設(shè)某次匹配有sitj，其中1in，1jm，ij，則應(yīng)有si-1=tj-1，. si-j+1=t1。再由（1）可知，下一次匹配串t右移一個(gè)位置，使得與字符t1對(duì)應(yīng)的s的開始位置是i-j+2，即主串的字符s i-j+2與模式串的第一個(gè)字符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)?！舅惴?-9】 57 數(shù)據(jù)結(jié)構(gòu)與算法 3.4 文本編輯3.4.1 問題描述與算法分析文本編輯是指利用計(jì)算機(jī)進(jìn)行編輯工作，修改字符數(shù)據(jù)的形式或格式，包括串的查找、插入、刪除等基本操作。在進(jìn)行文本編輯時(shí)，我們

23、把整個(gè)文本看成是一個(gè)字符串，稱為文本串，為了便于處理，進(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把這首小詩看成是一個(gè)文本串，輸入到內(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所示，每一個(gè)行表項(xiàng)包含行號(hào)、該行的起始地址、長(zhǎng)度。 61 數(shù)據(jù)結(jié)構(gòu)與算法 3.4 文本編輯為實(shí)現(xiàn)文本編輯問題的求解，我們定義一個(gè)文本編輯類Editer如下（其中串的存儲(chǔ)類型采用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)識(shí)，因此輸入階段的處理，主要完成的就是每輸入一行文本子串就為其建立一個(gè)行表項(xiàng)，記錄行號(hào)、起始地址與行內(nèi)串長(zhǎng)度。如算法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請(qǐng)輸入要查找的文本串str;SqString s(str);for(int i=0,j;iIndexof_KMP(s) 66 數(shù)據(jù)結(jié)構(gòu)與算法 3.4 文本編

27、輯 cout找到了，行號(hào)RTablei.iRow 位置j=Row_Count)cout未找到！endl; 67 數(shù)據(jù)結(jié)構(gòu)與算法 3.4 文本編輯3. 主程序與測(cè)試#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請(qǐng)輸入要查找的文本串Kite brings找到了，行號(hào)2 位置14 69 數(shù)據(jù)結(jié)構(gòu)與算法 3.5 小結(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)與算法