4其他線性結構4.1串4.2數(shù)組4.3廣義表4.4在線題目求解學習目標1.記憶和理解串的基礎知識。2.掌握數(shù)組的存儲及其地址計算。3.記憶和理解廣義表的基礎知識。4.學會運用串求解具體問題。4其他線性結構4.1串串的基礎知識串是0個或多個字符構成的有限序列，記為：S='a1a2…an'，其中S是串名，'a1a2…an'是串值，n是串長，當n=0時，S稱為空串。若串T在串S中出現(xiàn)，則T稱為S的子串，稱S為T的主串。a='BEI'b='JING'c='BEIJINGBEIJING'd='BEIJING'則a、b既是c的子串，又是d的子串，而c、d都是a、b的主串字符位置是字符在串中的位序，例如在上面的d串中，字符B的字符位置為1，字符J的字符位置為5。4.1串串的基礎知識子串位置是子串在主串中首次出現(xiàn)時，子串的首字符在主串中的位置，例如，在主串d中，子串a(chǎn)的位置為1，子串b的位置為5，在主串c中，子串a(chǎn)的位置為1，子串b的位置為4。若兩個串的長度相等，且串中逐個字符對應相等，則稱這兩個串相等?？崭翊侵复抵兄荒馨崭袂抑辽侔粋€空格的串。注意空格串與空串的區(qū)別，空串中不包含任何字符。串可采用順序存儲結構或鏈式存儲結構。串的基本操作較多，STL之string封裝了串的基本操作，可以直接調(diào)用。建議使用STL之string求解字符串相關問題。a='BEI'b='JING'c='BEIJINGBEIJING'd='BEIJING'4.1串STL之stringSTL之string的頭文件是string，使用string類型定義字符串變量。對于string類型的字符串，使用cin或getline函數(shù)輸入，若輸入的字符串中包含空格，則使用getline函數(shù)進行輸入；使用cout或printf函數(shù)輸出。使用下標運算符[]取串中元素（字符）。使用賦值運算符=為string類型變量的賦值。使用連接運算符+實現(xiàn)兩個字符串的連接或一個字符串與一個字符的連接。使用關系運算符完成string類型字符串的比較。4.1串STL之stringSTL之string的部分常用成員函數(shù)如表4-1所示4.1串STL之stringstring成員函數(shù)的使用示例strings="abcecdefg",t="cde";cout<<s.size()<<endl;//

輸出s的串長9cout<<t.length()<<endl;//

輸出t的串長3intj=s.find(t);//

在s中查找t，若找不到則j=-1if(j!=-1)//

如果j!=-1表示找到

cout<<j<<endl;

//

輸出在s中找到t時t首字符在s中的下標4intk=s.find('');//

查找空格符，返回7if(k!=-1)//

找到空格則以其為界把輸入串分為左、右兩個子串

cout<<s.substr(0,k)<<endl;

//

從0開始取長度為k的子串cout<<s.substr(k+1)<<endl;//

從k+1開始取子串，取完為止reverse(t.begin(),t.end());//

reverse逆置字符串，頭文件algorithm4.1串串的模式匹配算法串的模式匹配是指在主串（正文串）S中查找子串（模式串）T是否出現(xiàn)的操作。設主串S的長度為n，模式串T的長度為m。串的模式匹配算法：BF算法、KMP算法BF算法：從頭開始逐個比較兩個串中的字符，若相等則繼續(xù)比較下一個字符，否則主串起始位置較之前一個起始位置加1，子串從頭開始繼續(xù)比較，直到成功找到子串或最終查找失敗。BF算法最壞時間復雜度為O(n×m)。4.1串串的模式匹配算法BF算法實現(xiàn)intBF(strings,stringt){

inti=0,j=0,n=s.length(),m=t.length();

while(i<n&&j<m){

if(s[i]==t[j]){//

若相等，則繼續(xù)比較下一個字符

i++,j++;

}

else{

//

若不等

i=i-j+1;

//

i回退到本趟比較的開始位置的下一個位置

j=0;

//

j回退到開始位置

}

}

if(j==m)returni-j+1;//

若比完子串中所有字符，則返回子串位置

elsereturn0;

//

未找到，返回特殊值0}4.1串串的模式匹配算法KMP算法較之BF算法的改進之處在于：當每趟匹配過程中出現(xiàn)字符不相等時，不回退i指針，而是利用已經(jīng)得到的“部分匹配”的結果將模式串向右盡可能遠的“滑動”再繼續(xù)進行比較。真前綴：對于當前位置（下標）i，從0~k（0≤k<i）位置上的字符構成的子串；例如：'abcd'的真前綴有'a','ab','abc'。真后綴：對于當前位置（下標）i，從k~i（1≤k≤i）位置上的字符構成的子串；例如：'abcd'的真后綴有'bcd','cd','d'。最長公共前后綴：長度最大的真前綴，且它與真后綴相同；例如：'aaaa'的最長公共前后綴為'aaa'，長度為3；'abab'的最長公共前后綴為'ab'，長度為2。4.1串串的模式匹配算法KMP算法根據(jù)模式串得到一個next數(shù)組，其中next[i]的含義：存放i之前子串（0~i-1共i個字符構成）的最長公共前后綴的長度。對于模式串'ababaabab'，可按上述含義求得next數(shù)組有了next數(shù)組之后，就可以根據(jù)其元素值來“滑動”模式串。4.1串串的模式匹配算法KMP算法//在主串s中查找模式串t首次出現(xiàn)的位置，若不存在，則返回-1int

KMP(strings,stringt){//O(n)

inti=0,j=0,n=s.size(),m=t.size();while(i<n)

{

if(j==-1||s[i]==t[j]){

i++,j++;

if(j==m)returni-m;//

返回t在s中首次出現(xiàn)的位置

}

elsej=Next[j];//

j回退到Next[j]對應的位置

}

return-1;}4.1串串的模式匹配算法KMP算法中，若s[i]==t[j]，則繼續(xù)比較，即i++,j++，若j==m則匹配成功，首次成功時i-m為t在s中的子串位置；若s[i]!=t[j]，則j回退到next[j]的位置，相當于t右滑使得下次j位置上的字符與i位置上的字符比較計算next數(shù)組的算法getNext類似于KMP算法4.1串串的模式匹配算法getNext算法vector<int>Next;

//

外部變量不取名next以免出現(xiàn)編譯錯voidgetNext(stringt){

//O(m)，計算Next數(shù)組的方法

inti=0,j=-1,m=t.size();Next[0]=-1;while(i<m-1){

if(j==-1||t[i]==t[j]){

//

從頭比或相等則繼續(xù)比較

i++;

j++;

Next[i]=j; //

i之前的最長公共前后綴長度為j

}

else

j=Next[j];//

j回退到Next[j]的位置

}}4.1串串的模式匹配算法KMP算法算法時間復雜度為O(n+m)getNext函數(shù)的改進：

“Next[i]=j;”

改為

“if(t[i]!=t[j])Next[i]=j;

elseNext[i]=Next[j];”4.2數(shù)組一維數(shù)組一維數(shù)組元素之間具有線性關系，第一個元素沒有前驅(qū)，最后一個元素沒有后繼，其他元素僅有一個前驅(qū)和一個后繼。數(shù)組在內(nèi)存中占用一段連續(xù)的存儲單元，可以根據(jù)數(shù)組元素之間的相對關系，計算數(shù)組元素的存儲地址。數(shù)組名代表數(shù)組的首地址，若用LOC(i)表示一維數(shù)組a中下標為i的元素的存儲地址，則有：其中，c為一個元素所占的存儲單元長度。4.2數(shù)組二維數(shù)組二維數(shù)組在內(nèi)存中的兩種順序存儲方式：行主序和列主序。行主序是指以行序為主序，即先存放第一行的元素，再存放第二行的元素，……，最后存放最后一行的元素。列主序是指以列序為主序，即先存放第一列的元素，再存放第二列的元素，……，最后存放最后一列的元素。設有二維數(shù)組定義：inta[2][3];

則行、列主序存儲示意圖如下：行主序：列主序：4.2數(shù)組二維數(shù)組對于m行n列的二維數(shù)組a，以LOC(0,0)表示二維數(shù)組的基地址或基址。設每個數(shù)組元素所占的存儲單元長度為c，a[i][j]的存儲地址表示為LOC(i,j)，則行、列主序存儲對應的地址計算公式如下：行主序：列主序：4.2數(shù)組二維數(shù)組例4.2.1二維數(shù)組元素存儲地址的計算已知a是一個9行10列的二維數(shù)組，設a[0][0]的存儲地址為2000，每個元素在內(nèi)存中占用4個字節(jié)的存儲單元，分別以行主序和列主序存儲時，元素a[5][8]的存儲地址是多少？行主序：LOC(5,8)=LOC(0,0)+(10×5+8)×4=2000+232=2232。列主序：LOC(5,8)=LOC(0,0)+(9×8+5)×4=2000+308=2308。4.3廣義表基礎知識廣義表也稱列表，是n（n≥0）個表元素組成的有限序列，記作LS=(a1,a2,…,an)；其中，LS是表名，ai是表元素，它可以是表（稱為子表），也可以是數(shù)據(jù)元素（稱為原子）；n為表的長度，若n=0，則該廣義表為空表。廣義表是遞歸定義的線性結構，其表元素又可以是一個廣義表。廣義表的例子：A=()F=(d,(e))D=((a,(b,c)),F)C=(A,D,F)B=(a,B)=(a,(a,(a,......)))4.3廣義表基礎知識廣義表是一個多層次的線性結構。廣義表LS=(a1,a2,…,an)的結構特點：（1）廣義表中的數(shù)據(jù)元素有相對次序；（2）廣義表的長度定義為最外層所包含元素的個數(shù)；（3）廣義表的深度定義為所含括弧的重數(shù)；（4）廣義表可以是一個遞歸的表；（5）任何一個非空廣義表LS=(a1,a2,…,an)均可分解為表頭Head(LS)=a1和表尾Tail(LS)=(a2,…,an)兩部分。4.3廣義表基礎知識原子的深度為0，空表的深度為1。遞歸表的深度是無窮值，長度是有限值。例如，廣義表B=(a,B)=(a,(a,(a,......)))是一個遞歸的表，長度為2，深度為無窮值。4.3廣義表廣義表的基本操作廣義表的基本操作主要是兩個，即求表頭和求表尾。設廣義表為LS，求表頭和求表尾的操作描述如下：（1）求表頭GetHead(LS)：取得非空廣義表的第一個元素。廣義表的表頭可以是一個原子，也可以是一個子表。（2）求表尾GetTail(LS)：取得非空廣義表除去表頭元素以外的其他元素所構成的表。注意，廣義表的表尾一定是一個表。例4.3.1從廣義表中取原子

設廣義表D=(E,F)=((a,(b,c)),F)，請用廣義表的基本操作取出c。因Head(D)=E=(a,(b,c))，Tail(E)=((b,c))，Head(((b,c)))=(b,c)，Tail((b,c))=(c)；Head((c))=c；故D中取c的操作序列為GetHead(GetTail(GetHead(GetTail(GetHead(D)))))4.4在線題目求解例4.4.1統(tǒng)計子串

編寫算法，統(tǒng)計子串t在主串s中的出現(xiàn)次數(shù)，輸出t在s中的子串位置和總的出現(xiàn)次數(shù)。輸入:

首先輸入一個整數(shù)T，表示測試數(shù)據(jù)的組數(shù)，然后是T組測試數(shù)據(jù)。每組測試數(shù)據(jù)在第一行輸入主串s，在第二行輸入子串t。s和t中都不包含空格。輸出:

對于每組測試，若子串t在主串s中出現(xiàn)，則輸出t在s中的子串位置和總的出現(xiàn)次數(shù)，否則輸出“00”。引號不必輸出。4.4在線題目求解例4.4.1統(tǒng)計子串輸入樣例:2abbbbcdebbbbabcdebb輸出樣例:2400解析：用KMP算法求解本題。前述KMP算法返回模式串在主串中首次出現(xiàn)的位置（下標），本題需統(tǒng)計模式串的出現(xiàn)次數(shù)，把模式串在主串中首次出現(xiàn)的位置（下標）通過引用參數(shù)返回。為統(tǒng)計出現(xiàn)次數(shù)，增加一個計數(shù)器，在每次找到模式串時計數(shù)器增1。4.4在線題目求解例4.4.1統(tǒng)計子串#include<iostream>#include<string>#include<vector>usingnamespacestd;strings,t;

//

s主串，t模式串vector<int>Next;

//

外部數(shù)組、變量不取名為next以免編譯錯intn,m;

//

s主串長度：n，t模式串長度：m4.4在線題目求解例4.4.1統(tǒng)計子串voidgetNext(){

//

稍作改進的計算Next數(shù)組的方法

inti=0,j=-1;

Next[0]=-1;

while(i<m){

if(j==-1||t[i]==t[j]){

i++;

j++;

if(t[i]!=t[j])Next[i]=j;

elseNext[i]=Next[j];

}

else

j=Next[j];

}}4.4在線題目求解例4.4.1統(tǒng)計子串intKMP(int&pos){

//

稍作改進的KMP算法

inti=0,j=0,cnt=0;

while(i<n){

if(j==-1||s[i]==t[j]){

i++,j++;

if(j==m){

if(pos==-1)pos=i-m;//

記錄t在s中首次出現(xiàn)的位置

cnt++;

//

計數(shù)器加1

j=Next[j];//

對齊i位置的字符和j位置的字符，便于下次比較

}

}

else

j=Next[j];

//

j回退到Next[j]對應的下標

}

returncnt;}4.4在線題目求解例4.4.1統(tǒng)計子串voidrun(){

cin>>s>>t;

//

輸入模式串和主串

n=s.size();

//

主串長度

m=t.size();

//

模式串長度

Next.resize(m+1);

//

Next數(shù)組大小重定義為m+1

getNext();

//

計算Next值

intpos=-1;

//

pos保存子串位置-1，初值置為-1

intres=KMP(pos);//

調(diào)用KMP返回t的出現(xiàn)次數(shù)和首次出現(xiàn)下標pos

cout<<pos+1<<""<<res<<endl;}intmain(){

intT;

cin>>T;

while(T--)run();

return0;}4.4在線題目求解例4.4.2最長公共子串

要求輸入兩個字符串，求它們的最長公共子序列（最長公共子串）及其長度。輸入:

首先輸入一個整數(shù)T，表示測試數(shù)據(jù)的組數(shù)，然后是T組測試數(shù)據(jù)。每組測試數(shù)據(jù)在第一行輸入主串s，在第二行輸入子串t。s和t中都不包含空格。輸出:

對于每組測試，輸出兩行，第一行是最長公共子串的長度，第二行是最長公共子串（以第一個串中字符的出現(xiàn)次序優(yōu)先，參看輸出樣例）。4.4在線題目求解例4.4.2最長公共子串輸入樣例:2abcfbcabfcababfcababcfbc輸出樣例:4abcb4abfc4.4在線題目求解例4.4.2最長公共子串解析：本題求最長公共子串（LongestCommonSubstring，LCS）的長度及LCS。設兩個字符串分別為a和b，長度分別為m和n，把a[0]~a[i-1]的子串記為a(i)，a[0]~a[i-2]的子串記為a(i-1)，把b[0]~b[j-1]的子串記為b(j)，b[0]~b[j-2]的子串記為b(j-1)。LCS的長度采用動態(tài)規(guī)劃的方法求解。（1）狀態(tài)：用f(i,j)表示a(i)和b(j)的LCS的長度。（2）初值：（3）狀態(tài)轉(zhuǎn)移方程：（4）最終結果：f(m,n)。4.4在線題目求解例4.4.2最長公共子串LCS可在求得其長度（設為k）之后構造，用一個i（初值為m）指向串a(chǎn)，用一個j（初值為n）指向串b，當k>0時反復執(zhí)行：若a去掉最后一個字符不影響當前的LCS長度則i--，若b去掉最后一個字符不影響當前的LCS長度則j--，否則把i、j所指的相同字符連接到結果串（初始化為空串）之前。#include<iostream>#include<string>#include<vector>usingnamespacestd;stringa;

//

串a(chǎn)intm;

//

串a(chǎn)長度stringb;

//

串bintn;

//

串b長度//f[i][j]記錄a(i)與b(j)的LCS的長度vector<vector<int>>f;//LCS的長度記錄在f[m][n]中4.4在線題目求解例4.4.2最長公共子串voidlenOfLCS(){

//

求串a(chǎn)、b的LCS的長度

for(inti=1;i<=m;i++){

for(intj=1;j<=n;j++){

if(a[i-1]==b[j-1])