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

第3章串與文本編輯3.1串的類型定義3.2串的存儲表示3.3串的模式匹配算法3.4文本編輯3.5小結(jié)

0數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第1頁!3.1串的類型定義1.串的相關(guān)術(shù)語串是由零個或多個字符組成的有限序列，記為：s=s1s2…sn

。其中s是串名；雙引號內(nèi)的字符序列s1s2…sn是串值；n(n>=0)表示串的長度。1數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第2頁!3.1串的類型定義例如：s1=“datastructure”//串，長度為14串長度為零的串稱為空串。例如：s=“”//空串，長度為0組成串的字符均為空格的串稱為空格串或空白串。例如：s=“”//空格串，長度為42數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第3頁!3.1串的類型定義一個串中任意個連續(xù)字符組成的子序列稱為該串的子串?？沾侨魏未淖哟＠纾簊1=“datastructure”s2=“data”//s2是s1的子串s3=“structure”//s3是s1的子串s4=“datastructure”//s4不是s1的子串包含子串的串稱為主串。上例中s1為主串。3數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第4頁!3.1串的類型定義按照串中字符的次序，逐一比較兩個字符串中字符的大小，以確定兩個串的大小關(guān)系的操作，稱為串的比較。例如：s5=data，s6=DATA，則有s5>s6的比較結(jié)果為1，s5<s6的比較結(jié)果為0。4數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第5頁!3.1串的類型定義英文中的回文具有廣義和狹義之分，廣義的回文是指串中的空格字符不計入內(nèi)，比如串“tenanimalsIslaminanet”去掉空格字符后是一個回文。狹義的回文是指將空格字符計入在內(nèi)，比如題目中的“Liveonnoevil.”不過濾掉空格就是回文字符串。單個英文單詞的回文符合狹義回文。例如：eye、mum、refer、level等。5數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第6頁!3.1串的類型定義ADTString{Data: D={ai｜

aiElemSet,i=1,2,...,n,n>=0}Structure: S={<ai-1,ai>|ai-1,ai

D,i=2,3,…,n}oPerations: ConstructString() //操作結(jié)果：創(chuàng)建一個空的串s DestructString() //操作條件：已有串s //操作結(jié)果：銷毀當前串s StringLen()//操作條件：已有串s //操作結(jié)果：得到當前串s的實際長度6數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第7頁!3.1串的類型定義InsertSubString(pos,t)//操作條件：已有串s和參數(shù)串t//操作結(jié)果：將t插入到當前串第pos個位置前ConnectString(t)//操作條件：已有串s和參數(shù)串t//操作結(jié)果：將t連接到當前串s之后ClearString()//操作條件：已有串s//操作結(jié)果：將當前串s清空ReplaceString(pos,len,t)//操作條件：已有串s和參數(shù)串t//操作結(jié)果：將當前串s中第pos個字符開始的長度為len的子串，替換為t}ADTString;7數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第8頁!3.2串的存儲表示為了表示串的結(jié)束，可在串內(nèi)容最后一個有效字符后，再多開辟一個存儲空間，存放結(jié)束標志’\0’（C/C++語言中的字符串就采用這種方法），如圖3-2所示。8數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第9頁!3.2串的存儲表示定義順序串：#defineMAX100classSqString{public: char*base;//存儲串的字符數(shù)組 //base[0]表示串的實際長度,不另設結(jié)束標志 intmaxlen;//表示串的最大長度public: SqString();//構(gòu)造函數(shù)① SqString(char*s);//構(gòu)造函數(shù)② SqString(SqString&t);//構(gòu)造函數(shù)③ ~SqString();//析構(gòu)函數(shù)9數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第10頁!3.2串的存儲表示順序串的構(gòu)造與析構(gòu)

串的構(gòu)造有三種方法，分別是構(gòu)造空串、由基本類型的字符串構(gòu)造一個新串以及使用串對象來構(gòu)造串。下面給出三種方法構(gòu)造串的實現(xiàn)過程。（1）構(gòu)造空的順序串?！舅惴?-1-1】SqString::SqString(){

maxlen=MAX; base=newchar[maxlen+1]; //0下標留作記錄長度 base[0]=0;}10數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第11頁!3.2串的存儲表示（3）使用串對象來構(gòu)造串。【算法3-1-3】SqString::SqString(SqString&t){ maxlen=t.maxlen; base=newchar[maxlen+1]; base[0]=t.base[0]; for(inti=1;i<=base[0];i++) base[i]=t.base[i];}11數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第12頁!3.2串的存儲表示順序串插入操作順序串插入操作的功能是將一個指定的串插入到當前串中的指定位置之前，以s串和t串分別表示當前串和待插入串，則插入前后s串與t串的狀態(tài)如圖3-4（a）和圖3-4（b）所示。12數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第13頁!3.2串的存儲表示順序串插入操作實現(xiàn)算法為：①檢查插入位置的合法性，即當插入位置pos<1或pos>base[0]，或base[0]+t.base[0]>maxlen（沒有足夠空間插入t）時，提示錯誤信息，終止程序；②從pos指向的位置開始，一直到最后的字符，每個字符都要向后移動，移動的長度為t串的長度；③插入t串，修改s的串長，操作成功，結(jié)束。13數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第14頁!3.2串的存儲表示for(i=1;i<=t.base[0];i++) base[pos-1+i]=t.base[i];//插入元素 base[0]+=t.base[0]; returntrue;

} }14數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第15頁!3.2串的存儲表示15數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第16頁!3.2串的存儲表示【算法3-3】boolSqString::DelSubString(intpos,intlen,SqString&t){ if((pos<1)||(pos>base[0])||pos-1+len>base[0]) { cout<<"刪除失敗"<<endl; returnfalse; } else { for(inti=pos;i<=pos-1+len;i++) //刪除的元素復制給t t.base[i-pos+1]=base[i]; t.base[0]=len;

16數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第17頁!3.2串的存儲表示輸出順序串操作順序串輸出操作的功能是將串中的字符全部輸出。順序串輸出操作實現(xiàn)算法為：①檢查串時否為空串，若為空，輸出空串信息；②若串非空，則利用循環(huán)輸出串的內(nèi)容；③操作成功，結(jié)束。17數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第18頁!3.2串的存儲表示串的連接串的連接，顧名思義，是指將兩個已有的串連接成為一個串。例如，有兩個串s和t都是類SqString的對象，那么兩個串連接后為s=s+t，如圖3-6所示。18數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第19頁!3.2串的存儲表示【算法3-5】voidSqString::ConnectString(SqString&t){ if(base[0]+t.base[0]>maxlen) { char*p=newchar[base[0]+t.base[0]]; for(inti=1;i<=base[0];i++) p[i]=base[i]; delete[]base; base=p; maxlen=base[0]+t.base[0]; } for(inti=1;i<=t.base[0];i++) base[base[0]+i]=t.base[i]; base[0]+=t.base[0];}19數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第20頁!3.2串的存儲表示順序串中求子串的實現(xiàn)算法為：①檢查參數(shù)的合法性，當pos<1或pos>base[0]，或len<1或pos+len-1>base[0]時，操作失?。虎趯斍按畯膒os指向位置開始的長度為len的子串復制到串t中；③操作成功，結(jié)束。20數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第21頁!3.2串的存儲表示3.2.2串的鏈式存儲串的順序存儲方式節(jié)約了系統(tǒng)開銷，但是如果需要經(jīng)常對串執(zhí)行插入、刪除子串等操作，就需要頻繁移動串中的字符，因此，我們引入串的另一種存儲方式——鏈式存儲，又稱動態(tài)存儲。這樣就可以避免頻繁的插入、刪除操作帶來的效率低下等問題。21數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第22頁!3.2串的存儲表示22數(shù)據(jù)結(jié)構(gòu)與算法為了提高串的鏈式存儲的存儲密度，節(jié)省空間，可以將鏈串的結(jié)點大小設置為4。那么串s=“ABCDEFGHI”在結(jié)點大小為4的鏈串存儲結(jié)構(gòu)如圖3-9所示。數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第23頁!3.2串的存儲表示public: LinkString(); LinkString(char*t); LinkString(LinkString&t); ~LinkString(); boolInsertString(intpos,LinkString&t); boolDelSubString(intpos,intlen,LinkString&t); voidOutputString() ; //其他操作};23數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第24頁!3.2串的存儲表示24數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第25頁!3.3串的模式匹配算法設s和t是給定的兩個串，其長度分別為n和m，且有n≥m，在串s中找到等于子串t的過程稱為模式匹配，其中，串s稱為主串，t稱為模式。如果在s中找到等于t的子串，則稱匹配成功，函數(shù)返回t在s中的首次出現(xiàn)的存儲位置(或序號)，否則匹配失敗，返回0。25數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第26頁!3.3串的模式匹配算法設主串s=

“ababcabcacba”模式串t=

“abcac”。s的長度為n(n=12)，t的長度為m（m=5）。指針i、j分別為主串s、模式串t當前比較字符的下標。模式匹配的過程如圖3-11所示。26數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第27頁!3.3串的模式匹配算法27數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第28頁!3.3串的模式匹配算法28數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第29頁!3.3串的模式匹配算法else { i=i-j+2; j=1; } } if(j>t.base[0]) returni-t.base[0];//掃描完畢，匹配成功 else return0;//匹配失敗}29數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第30頁!3.3串的模式匹配算法限于篇幅，不再分析圖3-13所示的串在后續(xù)階段的匹配過程，可按KMP算法的思想繼續(xù)推導?！舅惴?-9】30數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第31頁!3.4文本編輯例如有下列一段英文：Night-SongintheJungleNowRanntheKitebringshomethenightThatMangtheBatsetsfreeTheherdsareshutinbarnandhutForloosedtilldawnarewe把這首小詩看成是一個文本串，輸入到內(nèi)存后如圖3-14所示。31數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第32頁!3.4文本編輯其相應的行表如表3-1所示，每一個行表項包含行號、該行的起始地址、長度。32數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第33頁!3.4文本編輯public: Editer(){Row_Count=0;} voidInputText(); //“輸入文本”處理函數(shù) voidSearchText(); //“查找文本”處理函數(shù) //其他功能，略};33數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第34頁!3.4文本編輯【算法3-10】voidEditer::InputText(){ charin_str[MAX]; while(cin.getline(in_str,MAX,'\n')&&in_str[0]!='\\') {//約定以'\n'為換行，'\\'為文本串輸入完畢

SqString*pstr=newSqString(in_str); RTable[Row_Count].iRow=Row_Count+1; RTable[Row_Count].iLength=pstr->base[0]; RTable[Row_Count].iStartAddress=pstr; Row_Count++; }}34數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第35頁!3.4文本編輯{ cout<<"找到了，行號"<<RTable[i].iRow<<"位置"<<j<<endl; break; } } if(i>=Row_Count) cout<<"未找到！"<<endl;}35數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第36頁!運行結(jié)果：Night-SongintheJungle↙NowRanntheKitebringshomethenight↙ThatMangtheBatsetsfree↙\↙請輸入要查找的文本串Kitebrings↙找到了，行號2位置1436數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第37頁!3.1串的類型定義子串的序號是該子串的個字符在主串中的序號。在上例子串s2在s1中的序號為1，s3在s1中的序號為6。S4不是s1的子串，也可以說，s4在s1中的序號為0。當且僅當串的長度相等并且對應位置上的字符都相同時，稱這兩個字符串是相等的。例如：s1=“datastructure”s2=“datastructure”s3=“datastructure”//s1與s2相等，s3與s1和s2均不相等

37數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第38頁!3.1串的類型定義2.串的ADT定義在引入串的ADT定義前我們先來看一個字符串應用的例子?！纠?-1】有一個字符串“l(fā)iveonnoevil”，檢查它是否為“回文”。當一個字符串順讀和逆讀都一樣，就可以稱這個字符串是回文。38數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第39頁!3.1串的類型定義判斷一個字符串s是否為回文（狹義的），需要進行如下操作：（1）存儲串s，并以相反順序存儲為串t；（2）比較s與t；（3）得出字符串s是否為回文串的判斷；（4）輸出回文串s例3-1是一個串的實際應用問題，為解決問題所需要的有關(guān)串的操作，即串類型應該提供的應用接口都是以串為單位，而不是串中的單個字符為單位。下面給出串的ADT定義：39數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第40頁!3.1串的類型定義StringCpy(t)

//操作條件：已有串s和參數(shù)串t//操作結(jié)果：將t復制到當前串s中OutputString()//操作條件：已有串s//操作結(jié)果：輸出當前串sSubString(pos,len,&t)//操作條件：已有串s//操作結(jié)果：取串s中從第pos個字符開始的，長度為len的子串，由t返回DelSubString(pos,len,&t)//操作條件：已有串s和一個參數(shù)串t//操作結(jié)果：刪除當前串從第pos個字符開始，長度為len的子串//并由t返回被刪除的子串

40數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第41頁!3.2串的存儲表示3.2.1串的順序存儲將串所占用空間的大小稱為串容量，實際存在的元素個數(shù)稱為串長，如圖3-1所示。41數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第42頁!3.2串的存儲表示借助于順序存儲時數(shù)組的0號下標存儲串長，即有效地利用了空間，又使得串中字符的位序與其存放位置（下標）一致，如圖3-3所示。42數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第43頁!3.2串的存儲表示boolInsertString(intpos,SqString&t);//在串的指定位置pos插入一個子串t boolDelSubString(intpos,intlen,SqString&t);//刪除當前串的子串,并由t返回 voidOutputString() ;//輸出串中所有字符 voidConnectString(SqString&t);//在當前串尾連接串t boolSubString(intpos,intlen,SqString&t);//求當前串從pos開始長度為len的子串 intIndexof(SqString&t);//求模式串t在當前串中次出現(xiàn)的位置 intIndexof_KMP(SqString&t);//KMP法求模式串t在當前串中次出現(xiàn)的位置 voidGetNext(intnext[]);//KMP模式匹配算法輔助函數(shù) //其他操作};43數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第44頁!3.2串的存儲表示（2）由基本字符串構(gòu)造一個新串?！舅惴?-1-2】SqString::SqString(char*s)//由機內(nèi)標準串構(gòu)造{ maxlen=MAX; base=newchar[maxlen+1]; base[0]=strlen(s); for(inti=0;s[i]!='\0';i++) base[i+1]=s[i]; }44數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第45頁!3.2串的存儲表示（4）析構(gòu)函數(shù)【算法3-1-4】SqString::~SqString(){ delete[]base;}45數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第46頁!3.2串的存儲表示46數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第47頁!3.2串的存儲表示【算法3-2】boolSqString::InsertString(intpos,SqString&t){

if(pos<1||pos>base[0]+1||pos-1+t.base[0]>maxlen) { cout<<"插入失敗"<<endl; returnfalse; } else { for(inti=base[0];i>=pos;i--) base[i+t.base[0]]=base[i];//元素后移

47數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第48頁!3.2串的存儲表示順序串刪除操作順序串刪除操作的功能是刪除s串中從第pos個位置開始的長度為len的子串。如圖3-5所示。

48數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第49頁!3.2串的存儲表示順序串刪除操作實現(xiàn)算法為：①檢查參數(shù)的合法性，有兩種不合法的操作條件：一是pos的值不在串s的長度范圍內(nèi)，即pos<1或pos>base[0]；二是從串s第pos個位置開始不存在長度為len的子串，即pos+len-1>base[0]；②將待刪除的子串復制給t；③在s中刪除指定的子串，修改s的串長，操作成功，結(jié)束。49數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第50頁!3.2串的存儲表示for(i=pos+len;i<=base[0];i++) //元素前移 { base[i-len]=base[i];

} base[0]-=len; returntrue; } }50數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第51頁!3.2串的存儲表示【算法3-4】voidSqString::OutputString(){ if(base[0]==0)//判斷串是否為空串 cout<<"空串"<<endl; else { for(inti=1;i<=base[0];i++) cout<<base[i]; cout<<endl;

}}51數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第52頁!3.2串的存儲表示順序串連接操作實現(xiàn)算法為：①計算連接后的串長，如果超出順序串的maxlen，重新分配空間；②否則，從當前串的第base[0]+1個位置起，依次將t串中每一個字符復制到s；③更新當前串長，操作成功，返回。52數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第53頁!3.2串的存儲表示6.求子串（非空子串）求子串的定義為將串s中的第pos個字符開始長度為len的子串，復制到串t中。如圖3-7所示。53數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第54頁!3.2串的存儲表示【算法3-6】boolSqString::SubString(intpos,intlen,SqString&t){ if((pos<1)||(pos>base[0])||pos-1+len>base[0]) { cout<<"操作失敗"<<endl; returnfalse; } else { for(inti=pos;i<=len;i++) t.base[i-pos+1]=base[i]; t.base[0]=len; returntrue; } }54數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第55頁!3.2串的存儲表示在鏈式存儲結(jié)構(gòu)下，存儲空間被分成一系列大小相同的結(jié)點，每個結(jié)點包含兩個域：字符域data和指針域next。其中，字符域用來存放字符，指針域則用來存放指向下一個結(jié)點的指針。一個串可用一個單鏈表來存儲。鏈表中的結(jié)點數(shù)目等于串的長度。例如，一個字符串s=“ABCDEFGHI”，那么它的單鏈表存儲方式如圖3-8所示。55數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第56頁!3.2串的存儲表示鏈串的存儲結(jié)構(gòu)可定義如下：#defineN4structLStringNode{ chardata[N]; structLStringNode*next;};classLinkString{ LStringNode*head; intlength;56數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第57頁!3.2串的存儲表示鏈串的插入操作與單鏈表的插入過程相似，但又有明顯的區(qū)別，單鏈表中每一個結(jié)點都是一個單獨的元素，而塊鏈式的串中每一塊有若干個獨立的元素，如圖3-10（a）所示，當插入位置不是剛好位于每一塊的起始處時，插入子串的處理相對要復雜。為盡量減少插入時字符的移動，可采用犧牲一定存儲空間的辦法，將插入點所在塊的串拆分成兩個塊，無效字符的位置用“#”填充，如圖3-10（b）所示，這樣，待插入的串就可以直接進行鏈接。57數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第58頁!3.2串的存儲表示鏈串插入操作實現(xiàn)算法為：①判斷插入位置是否有效，無效立即結(jié)束；否則繼續(xù)；②找到插入位置，以指針p指向pos所在塊或其前一塊；若pos對塊長取余不為0，p指向pos所在塊，生成新結(jié)點，對該塊進行拆分；否則，p指向pos所在塊的前一塊；③將t串鏈接到s串中；④操作成功，結(jié)束?！舅惴?-7】58數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第59頁!3.3串的模式匹配算法Brute-Force算法簡稱為BF算法，亦稱簡單匹配算法，設主串s="s1…sn"，模式串t="t1…tm"，其基本思想是：1.從主串s的個字符s1開始和模式串t="t1…tm"中的個字符t1比較；2.若相等，則繼續(xù)逐個比較后續(xù)字符，s2和t2；3.若不相等，從主串s的第二個字符s2開始重新與模式串t的個字符t1進行比較。4.重復上述過程，如果在主串s中找到一個與串t相同的子串，則匹配成功，返回模式串t在主串s主的序號；如果比較完主串s的所有字符序列，沒有和模式串t相等的子串，則匹配失敗返回0。59數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第60頁!3.3串的模式匹配算法60數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第61頁!3.3串的模式匹配算法上述匹配過程中，可以得出以下結(jié)果：（1）若在前k-1(k≥1)次比較過程中未匹配成功，則第k次比較是從s串的第k個字符sk開始和t中的個字符t1比較；（2）設某次匹配有si≠tj，其中1≤i≤n，1≤j≤m，i≥j，則應有si-1=tj-1，...si-j+1=t1。再由（1）可知，下一次匹配串t右移一個位置，使得與字符t1對應的s的開始位置是i-j+2，即主串的字符si-j+2與模式串的個字符t1進行比較。如圖3-12所示。61數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第62頁!3.3串的模式匹配算法【算法3-8】intSqString::Indexof(SqString&t){ if((base[0]==0)||(t.base[0]==0))//為空 return0; inti=1,j=1; while(i<=base[0]&&j<=t.base[0]) { if(base[i]==t.base[j])

{ i++; j++; }

62數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：第3章串與文本編輯共71頁，您現(xiàn)在瀏覽的是第63頁!3.3串的模式匹配算法63數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)