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

《數(shù)據(jù)結(jié)構(gòu)ppt：第3章串與文本編輯.ppt》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)ppt：第3章串與文本編輯.ppt（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、,2,數(shù)據(jù)結(jié)構(gòu)與算法,3.1 串的類型定義,一個串中任意個連續(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)且僅

3、當(dāng)串的長度相等并且對應(yīng)位置上的字符都相同時，稱這兩個字符串是相等的。 例如：s1= “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 < s6的比較結(jié)果為0。,5,數(shù)據(jù)結(jié)構(gòu)與算法,3.1 串的類型定義,2. 串的ADT定義 在引入串的ADT定義前我們先來看一

4、個字符串應(yīng)用的例子。 【例3-1】有一個字符串“l(fā)ive on no evil”，檢查它是否為“回文”。當(dāng)一個字符串順讀和逆讀都一樣，就可以稱這個字符串是回文。,6,數(shù)據(jù)結(jié)構(gòu)與算法,3.1 串的類型定義,英文中的回文具有廣義和狹義之分，廣義的回文是指串中的空格字符不計入內(nèi)，比如串“ten animals I slam in a net”去掉空格字符后是一個回文。狹義的回文是指將空格字符計入在內(nèi)，比如題目中的“Live on no evil.”不過濾掉空格就是回文字符串。單個英文單詞的回文符合狹義回文。例如：eye、mum、refer、level等。,7,數(shù)據(jù)結(jié)構(gòu)與算法,3.1 串的類型定義,判

5、斷一個字符串s是否為回文（狹義的），需要進(jìn)行如下操作： （1）存儲串s，并以相反順序存儲為串t； （2）比較s與t； （3）得出字符串s是否為回文串的判斷； （4）輸出回文串s 例3-1是一個串的實際應(yīng)用問題，為解決問題所需要的有關(guān)串的操作，即串類型應(yīng)該提供的應(yīng)用接口都是以串為單位，而不是串中的單個字符為單位。下面給出串的ADT定義：,8,數(shù)據(jù)結(jié)構(gòu)與算法,3.1 串的類型定義,ADT String Data: D=ai ai ElemSet, i=1,2,...,n,n=0 Structure: S=| ai-1,ai D, i=2,3,,n oPerations: ConstructStri

6、ng() //操作結(jié)果：創(chuàng)建一個空的串s DestructString() //操作條件：已有串s //操作結(jié)果：銷毀當(dāng)前串s StringLen() //操作條件：已有串s //操作結(jié)果：得到當(dāng)前串s的實際長度,9,數(shù)據(jù)結(jié)構(gòu)與算法,3.1 串的類型定義,StringCpy(t) //操作條件：已有串s和參數(shù)串t //操作結(jié)果：將t復(fù)制到當(dāng)前串s中 OutputString() //操作條件：已有串s //操作結(jié)果：輸出當(dāng)前串s SubString(pos, len, ,11,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲表示,3.2.1 串的順序存儲 將串所占用空間的大小稱為串容量，實際存在的元素個數(shù)稱

7、為串長，如圖3-1所示。,12,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲表示,為了表示串的結(jié)束，可在串內(nèi)容最后一個有效字符后，再多開辟一個存儲空間，存放結(jié)束標(biāo)志0 （C/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 100 class SqString public: char *base;//存儲串的字符數(shù)組 //base0表示串的實際長度,不

8、另設(shè)結(jié)束標(biāo)志 int maxlen;//表示串的最大長度 public: SqString();//構(gòu)造函數(shù) SqString(char *s); //構(gòu)造函數(shù) SqString(SqString //析構(gòu)函數(shù),15,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲表示,bool InsertString(int pos,SqString ,16,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲表示,順序串的構(gòu)造與析構(gòu) 串的構(gòu)造有三種方法，分別是構(gòu)造空串、由基本類型的字符串構(gòu)造一個新串以及使用串對象來構(gòu)造串。下面給出三種方法構(gòu)造串的實現(xiàn)過程。 （1）構(gòu)造空的順序串。 【算法3-1-1】 SqString::SqString

9、() maxlen=MAX; base=new charmaxlen+1;//0下標(biāo)留作記錄長度 base0=0; ,17,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲表示,（2）由基本字符串構(gòu)造一個新串。 【算法3-1-2】 SqString::SqString(char *s)//由機內(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)造串。 【算法3-1-3】 SqString::SqString(

10、SqString ,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 串的存儲表示,順序串插入操作實現(xiàn)算法為： 檢查插入位置的合法性，即當(dāng)插入位置posbase0，或base0+t.base0 m

11、axlen（沒有足夠空間插入t）時，提示錯誤信息，終止程序； 從pos指向的位置開始，一直到最后的字符，每個字符都要向后移動，移動的長度為t串的長度； 插入t串，修改s的串長，操作成功，結(jié)束。,23,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲表示,【算法3-2】 bool SqString::InsertString(int pos,SqString //元素后移,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 串

12、的存儲表示,順序串刪除操作 順序串刪除操作的功能是刪除s串中從第pos個位置開始的長度為len的子串。如圖3-5所示。,26,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲表示,27,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲表示,順序串刪除操作實現(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::DelS

13、ubString(int pos,int len,SqString,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 串的存儲表示,輸出順序串操作 順序串輸出操作的功能是將串中的字符全部輸出。順序串輸出操作實現(xiàn)算法為： 檢查串時否為空串，若為空，輸出空串信息； 若串非空，則利用循環(huán)輸出串的內(nèi)容； 操作成功，結(jié)束。,31,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲表示,【算法3-4】 void SqString::OutputSt

14、ring() if(base0==0) //判斷串是否為空串 cout<<空串<

15、次將t串中每一個字符復(fù)制到s； 更新當(dāng)前串長，操作成功，返回。,34,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲表示,【算法3-5】 void SqString::ConnectString(SqString ,35,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲表示,6. 求子串（非空子串） 求子串的定義為將串s中的第pos個字符開始長度為len的子串，復(fù)制到串t中。如圖3-7所示。,36,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲表示,順序串中求子串的實現(xiàn)算法為： 檢查參數(shù)的合法性，當(dāng)posbase0，或lenbase0時，操作失?。?將當(dāng)前串從pos指向位置開始的長度為len的子串復(fù)制到串t中； 操作成功，結(jié)束。,37,

16、數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲表示,【算法3-6】 bool SqString::SubString(int pos,int len,SqString ,38,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲表示,3.2.2 串的鏈?zhǔn)酱鎯?串的順序存儲方式節(jié)約了系統(tǒng)開銷，但是如果需要經(jīng)常對串執(zhí)行插入、刪除子串等操作，就需要頻繁移動串中的字符，因此，我們引入串的另一種存儲方式鏈?zhǔn)酱鎯Γ址Q動態(tài)存儲。這樣就可以避免頻繁的插入、刪除操作帶來的效率低下等問題。,39,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲表示,在鏈?zhǔn)酱鎯Y(jié)構(gòu)下，存儲空間被分成一系列大小相同的結(jié)點，每個結(jié)點包含兩個域：字符域data和指針域next。其中，

17、字符域用來存放字符，指針域則用來存放指向下一個結(jié)點的指針。 一個串可用一個單鏈表來存儲。鏈表中的結(jié)點數(shù)目等于串的長度。例如，一個字符串s=“ABCDEFGHI”，那么它的單鏈表存儲方式如圖3-8所示。,40,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲表示,41,數(shù)據(jù)結(jié)構(gòu)與算法,為了提高串的鏈?zhǔn)酱鎯Φ拇鎯γ芏?，?jié)省空間，可以將鏈串的結(jié)點大小設(shè)置為4。那么串s=“ABCDEFGHI”在結(jié)點大小為4的鏈串存儲結(jié)構(gòu)如圖3-9所示。,3.2 串的存儲表示,鏈串的存儲結(jié)構(gòu)可定義如下： #define N 4 struct LStringNode char dataN; struct LStringNode *nex

18、t; ; class LinkString LStringNode *head; int length;,42,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲表示,public: LinkString(); LinkString(char *t); LinkString(LinkString ,43,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲表示,鏈串的插入操作與單鏈表的插入過程相似，但又有明顯的區(qū)別，單鏈表中每一個結(jié)點都是一個單獨的元素，而塊鏈?zhǔn)降拇忻恳粔K有若干個獨立的元素，如圖3-10（a）所示，當(dāng)插入位置不是剛好位于每一塊的起始處時，插入子串的處理相對要復(fù)雜。為盡量減少插入時字符的移動，可采用犧牲一定存儲空間

19、的辦法，將插入點所在塊的串拆分成兩個塊，無效字符的位置用“#”填充，如圖3-10（b）所示，這樣，待插入的串就可以直接進(jìn)行鏈接。,44,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲表示,45,數(shù)據(jù)結(jié)構(gòu)與算法,3.2 串的存儲表示,鏈串插入操作實現(xiàn)算法為： 判斷插入位置是否有效，無效立即結(jié)束；否則繼續(xù)； 找到插入位置，以指針p指向pos所在塊或其前一塊；若pos對塊長取余不為0，p指向pos所在塊，生成新結(jié)點，對該塊進(jìn)行拆分；否則，p指向pos所在塊的前一塊； 將t串鏈接到s串中； 操作成功，結(jié)束。 【算法3-7】,46,數(shù)據(jù)結(jié)構(gòu)與算法,3.3 串的模式匹配算法,設(shè)s和t是給定的兩個串，其長度分別為n和m，

20、且有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中的第一個字符t1比較； 2. 若相等，則繼續(xù)逐個比較后續(xù)字符，s2和t2； 3. 若不相等，從主串s的第二個字符s2開始重新與模式串t的第一個字符t1進(jìn)行比較。 4. 重復(fù)上述過程，

21、如果在主串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 串的模式匹配算法,50,數(shù)據(jù)結(jié)構(gòu)與算法,3.3 串的模式匹配算法,51,數(shù)據(jù)結(jié)構(gòu)與算法,3.3 串的模式匹配算法,上述匹配過程中，可以得出以下結(jié)果： （1）若在前

22、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，即主串的字符si-j+2與模式串的第一個字符t1進(jìn)行比較。如圖3-12所示。,52,數(shù)據(jù)結(jié)構(gòu)與算法,3.3 串的模式匹配算法,53,數(shù)據(jù)結(jié)構(gòu)與算法,3.3 串的模式匹配算法,【算法3-8】 int SqString::Indexof(SqString ,54,數(shù)據(jù)結(jié)構(gòu)與算法,3.3 串的模式匹

23、配算法,else i=i-j+2; j=1; if(jt.base0) return i-t.base0;//掃描完畢，匹配成功 else return 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ìn)行編輯工作，修改字符數(shù)據(jù)的形式或格式，包括串的查找、插入、刪除等基本操作。 在進(jìn)行文本編輯時，我們把整個文本看成是一個字符串，

24、稱為文本串，為了便于處理，進(jìn)一步地將文本串拆分成若干子串，即頁是文本串的子串，行又是頁的子串。,58,數(shù)據(jù)結(jié)構(gòu)與算法,3.4 文本編輯,例如有下列一段英文： Night-Song 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 把這首小詩看成是一個文本串，輸入到內(nèi)存后如圖3-14所示。,59,數(shù)據(jù)結(jié)構(gòu)與算法,3.4 文本編輯,60,數(shù)據(jù)結(jié)構(gòu)與算法,3.4

25、 文本編輯,其相應(yīng)的行表如表3-1所示，每一個行表項包含行號、該行的起始地址、長度。,61,數(shù)據(jù)結(jié)構(gòu)與算法,3.4 文本編輯,為實現(xiàn)文本編輯問題的求解，我們定義一個文本編輯類Editer如下（其中串的存儲類型采用3.2.1節(jié)的順序串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 RTableMAX;//行表

26、 int Row_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 算法實現(xiàn) 1. 輸入文本 由于各行的文本子串以行表項為標(biāo)識，因此輸入階段的處理，主要完成的就是每輸入一行文本子串就為其建立一個行表項，記錄行號、起始地址與行內(nèi)串長度。如算法3-10所示。,64,數(shù)據(jù)結(jié)構(gòu)與算法,3.4 文本編輯,【算法3-10】 void Edite

27、r::InputText() char in_strMAX; while(cin.getline(in_str,MAX,n) ,65,數(shù)據(jù)結(jié)構(gòu)與算法,3.4 文本編輯,2. 查找文本 【算法3-11】 void Editer::SearchText() coutstr; SqString s(str); for(int i=0,j;iIndexof_KMP(s)),66,數(shù)據(jù)結(jié)構(gòu)與算法,3.4 文本編輯, cout=Row_Count) cout<<未找到！<

28、ace std; void main() Editer t1; t1.InputText(); t1.SearchText(); ,68,數(shù)據(jù)結(jié)構(gòu)與算法,,運行結(jié)果： Night-Song in the Jungle Now Rann the Kite brings home the night That 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)與算法,