數(shù)據(jù)結(jié)構(gòu)第4章 串

1、第第4章章 串串 4.1 串的基本概念串的基本概念 4.1.1 什么是串什么是串串（或字符串）是由零個(gè)或多個(gè)字符組成的有限序列。串（或字符串）是由零個(gè)或多個(gè)字符組成的有限序列。記作記作str=a1a2an（n0），其中），其中str是串名，用雙引號(hào)括是串名，用雙引號(hào)括起來的字符序列為串值，引號(hào)是界限符，起來的字符序列為串值，引號(hào)是界限符，ai（1in）是一）是一個(gè)任意字符（字母、數(shù)字或其他字符），它稱為串的元素，個(gè)任意字符（字母、數(shù)字或其他字符），它稱為串的元素，是構(gòu)成串的基本單位，串中所包含的字符個(gè)數(shù)是構(gòu)成串的基本單位，串中所包含的字符個(gè)數(shù)n稱為串的稱為串的長度，當(dāng)長度，當(dāng)n=0時(shí)，稱為時(shí)，

2、稱為空串空串。一個(gè)串中任意連續(xù)的字符組成的子序列稱為該串的一個(gè)串中任意連續(xù)的字符組成的子序列稱為該串的子子串串，例如，例如，a、ab、abc和和abcd等都是等都是abcde的的子串。包含子串的串相應(yīng)地稱為主串。子串。包含子串的串相應(yīng)地稱為主串。 若兩個(gè)串的長度相等且對(duì)應(yīng)字符都相等，則稱兩個(gè)若兩個(gè)串的長度相等且對(duì)應(yīng)字符都相等，則稱兩個(gè)串是相等串是相等的。當(dāng)兩個(gè)串不相等時(shí)，可按的。當(dāng)兩個(gè)串不相等時(shí)，可按“字典順序字典順序”區(qū)區(qū)分大小。分大小?！纠纠?.1】 設(shè)設(shè)str是一個(gè)長度為是一個(gè)長度為n的串，其中的字符各不相的串，其中的字符各不相同，則同，則str中的所有子串個(gè)數(shù)是多少？中的所有子串個(gè)數(shù)

3、是多少？解：解：對(duì)于這樣的串對(duì)于這樣的串str，有：，有：空串是其子串，計(jì)空串是其子串，計(jì)1個(gè)個(gè)每個(gè)字符構(gòu)成的串是其子串，計(jì)每個(gè)字符構(gòu)成的串是其子串，計(jì)n個(gè)個(gè)每每2個(gè)連續(xù)的字符構(gòu)成的串是其子串，計(jì)個(gè)連續(xù)的字符構(gòu)成的串是其子串，計(jì)n-1個(gè)個(gè)每每3個(gè)連續(xù)的字符構(gòu)成的串是其子串，計(jì)個(gè)連續(xù)的字符構(gòu)成的串是其子串，計(jì)n-2個(gè)個(gè)每每n-1個(gè)連續(xù)的字符構(gòu)成的串是其子串，計(jì)個(gè)連續(xù)的字符構(gòu)成的串是其子串，計(jì)2個(gè)個(gè)str是其自身的子串，計(jì)是其自身的子串，計(jì)1個(gè)個(gè)所有子串個(gè)數(shù)所有子串個(gè)數(shù)=1+n+(n-1)+2+1=n(n+1)/2+1。例如，。例如，str=software的子串個(gè)數(shù)的子串個(gè)數(shù)=(89)/2+1=

4、37。4.1.2 串的抽象數(shù)據(jù)類型串的抽象數(shù)據(jù)類型ADT String數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象：D=ai | 1in,n0,ai為為char類型類型數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：R=rr= | ai,ai+1D, i=1,n-1基本運(yùn)算：基本運(yùn)算：void StrAssign(cstr)：由字符串常量：由字符串常量cstr創(chuàng)建一個(gè)串，即生成其值等于創(chuàng)建一個(gè)串，即生成其值等于cstr的串。的串。void StrCopy(t)：串復(fù)制，由串：串復(fù)制，由串t復(fù)制產(chǎn)生一個(gè)串。復(fù)制產(chǎn)生一個(gè)串。int StrLength()：求串長，返回當(dāng)前串中字符個(gè)數(shù)。：求串長，返回當(dāng)前串中字符個(gè)數(shù)。String Concat(t)：

5、串連接，返回一個(gè)當(dāng)前串和串：串連接，返回一個(gè)當(dāng)前串和串t連接后的結(jié)果。連接后的結(jié)果。String SubStr(i,j)：求子串，返回當(dāng)前串中從第：求子串，返回當(dāng)前串中從第i個(gè)字符開始的個(gè)字符開始的j個(gè)連續(xù)字個(gè)連續(xù)字符組成的子串。符組成的子串。String InsStr(i,s)：串插入，返回串：串插入，返回串s插入到當(dāng)前串的第插入到當(dāng)前串的第i個(gè)位置后的子串。個(gè)位置后的子串。String DelStr(i,j)：串刪除，返回當(dāng)前串中刪去從第：串刪除，返回當(dāng)前串中刪去從第i個(gè)字符開始的個(gè)字符開始的j個(gè)字個(gè)字符后的結(jié)果。符后的結(jié)果。String RepStr(i,j,s)：串替換，返回用串：串替

6、換，返回用串s替換當(dāng)前串中第替換當(dāng)前串中第i個(gè)字符開始的個(gè)字符開始的j個(gè)字符后的結(jié)果。個(gè)字符后的結(jié)果。DispStr()：串輸出，輸出當(dāng)前串的所有元素值。：串輸出，輸出當(dāng)前串的所有元素值。4.2 串的存儲(chǔ)結(jié)構(gòu)串的存儲(chǔ)結(jié)構(gòu)4.2.1 串的順序存儲(chǔ)結(jié)構(gòu)順序串串的順序存儲(chǔ)結(jié)構(gòu)順序串和順序表一樣，用一個(gè)和順序表一樣，用一個(gè)data數(shù)組（大小為數(shù)組（大小為MaxSize）和一）和一個(gè)整型變量個(gè)整型變量length來表示一個(gè)順序串，來表示一個(gè)順序串，length表示表示data數(shù)組中數(shù)組中實(shí)際字符的個(gè)數(shù)。實(shí)際字符的個(gè)數(shù)。設(shè)計(jì)順序串類設(shè)計(jì)順序串類SqStringClass如下：如下：const int Ma

7、xSize=100;class SqStringClass/順序串類順序串類 char *data;/存放串中元素存放串中元素int length;/串中字符個(gè)數(shù)串中字符個(gè)數(shù)public:SqStringClass();/構(gòu)造函數(shù)構(gòu)造函數(shù)SqStringClass();/析構(gòu)函數(shù)析構(gòu)函數(shù)SqStringClass &operator=(char *cstr);/重載賦值運(yùn)算符重載賦值運(yùn)算符,SqStringClass &operator=(SqStringClass &t);/重載賦值運(yùn)算符重載賦值運(yùn)算符int StrLength();/求串長度求串長度SqString

8、Class &operator+(SqStringClass &t);/串連接串連接SqStringClass &SubStr(int i,int j);/求子串求子串SqStringClass &InsStr(int i,SqStringClass &s);/串插入串插入SqStringClass &DelStr(int i,int j);/串刪除串刪除SqStringClass &RepStr(int i,int j,SqStringClass &s); /串替換串替換void DispStr();/串輸出串輸出;說明：說明：

9、在在C+語言中提供了字符數(shù)組來存放字符串，以空字語言中提供了字符數(shù)組來存放字符串，以空字符符0標(biāo)識(shí)字符串結(jié)束標(biāo)識(shí)字符串結(jié)束,并包含了前面列出的大部分串運(yùn)算功并包含了前面列出的大部分串運(yùn)算功能，本節(jié)主要是通過能，本節(jié)主要是通過自已組織和實(shí)現(xiàn)串自已組織和實(shí)現(xiàn)串來介紹數(shù)據(jù)結(jié)構(gòu)算法來介紹數(shù)據(jù)結(jié)構(gòu)算法的一般設(shè)計(jì)方法。的一般設(shè)計(jì)方法。下面討論在順序串上實(shí)現(xiàn)串基本運(yùn)算的算法。下面討論在順序串上實(shí)現(xiàn)串基本運(yùn)算的算法。（1）順序串的初始化和銷毀）順序串的初始化和銷毀順序串的初始化和銷毀分別通過構(gòu)造函數(shù)和析構(gòu)函數(shù)來順序串的初始化和銷毀分別通過構(gòu)造函數(shù)和析構(gòu)函數(shù)來實(shí)現(xiàn)，對(duì)應(yīng)的算法如下：實(shí)現(xiàn)，對(duì)應(yīng)的算法如下：SqSt

10、ringClass:SqStringClass()/構(gòu)造函數(shù)構(gòu)造函數(shù) data=new charMaxSize;length=0;SqStringClass:SqStringClass()/析構(gòu)函數(shù)析構(gòu)函數(shù) delete data; （2）建立串）建立串StrAssign(cstr)由一個(gè)字符串常量由一個(gè)字符串常量cstr建立一個(gè)順序串對(duì)象，即生成一建立一個(gè)順序串對(duì)象，即生成一個(gè)其值等于個(gè)其值等于cstr的順序串對(duì)象，這里采用重載的順序串對(duì)象，這里采用重載“=”運(yùn)算符實(shí)運(yùn)算符實(shí)現(xiàn)的。對(duì)應(yīng)的算法如下：現(xiàn)的。對(duì)應(yīng)的算法如下：SqStringClass &SqStringClass:oper

11、ator=(char *cstr) /重載賦值運(yùn)算符重載賦值運(yùn)算符 int i;for (i=0;icstri!=0;i+)datai=cstri;length=i;return *this;例如，例如，cstr為為C+的字符串的字符串a(chǎn)bcdef，s為為SqStringClass類類對(duì)象，執(zhí)行對(duì)象，執(zhí)行s=cstr的結(jié)果如圖的結(jié)果如圖4.2所示所示 （3）串復(fù)制）串復(fù)制StrCopy(t)將順序串將順序串t復(fù)制給當(dāng)前串對(duì)象，這里也是采用重載復(fù)制給當(dāng)前串對(duì)象，這里也是采用重載“=”運(yùn)算符實(shí)現(xiàn)的。對(duì)應(yīng)的算法如下：運(yùn)算符實(shí)現(xiàn)的。對(duì)應(yīng)的算法如下：SqStringClass &SqString

12、Class:operator=(SqStringClass &t)/重載賦值運(yùn)算符重載賦值運(yùn)算符 int i;for (i=0;it.length;i+)datai=t.datai;length=t.length;return *this;（4）求串長度）求串長度StrLength()返回當(dāng)前順序串中的字符個(gè)數(shù)。對(duì)應(yīng)的算法如下：返回當(dāng)前順序串中的字符個(gè)數(shù)。對(duì)應(yīng)的算法如下：int SqStringClass:StrLength()/求串長度求串長度 return length; （5）串連接）串連接Concat(t)將當(dāng)前順序串和串對(duì)象將當(dāng)前順序串和串對(duì)象t的所有字符連接在一起形成新順的

13、所有字符連接在一起形成新順序串，并返回這個(gè)新串對(duì)象，并不改變當(dāng)前串對(duì)象和串對(duì)象序串，并返回這個(gè)新串對(duì)象，并不改變當(dāng)前串對(duì)象和串對(duì)象t的內(nèi)容，這里采用重載的內(nèi)容，這里采用重載“+”運(yùn)算符實(shí)現(xiàn)的。對(duì)應(yīng)的算法如下：運(yùn)算符實(shí)現(xiàn)的。對(duì)應(yīng)的算法如下：SqStringClass &SqStringClass:operator+(SqStringClass &t) /串連接串連接 static SqStringClass nstr;/新建一個(gè)空串新建一個(gè)空串int i;nstr.length=length+t.length;for (i=0;ilength;i+)/將當(dāng)前串將當(dāng)前串data0.

14、str.length-1nstrnstr.datai=datai;for (i=0;it.length;i+)/將將t.data0.t.length-1nstrnstr.datalength+i=t.datai;return nstr;/返回新串返回新串nstr例如，串對(duì)象例如，串對(duì)象s和和t連接產(chǎn)生新串對(duì)象連接產(chǎn)生新串對(duì)象s1的結(jié)果如圖的結(jié)果如圖4.3所示。所示。（6）求子串）求子串SubStr(i,j)產(chǎn)生由當(dāng)前順序串中第產(chǎn)生由當(dāng)前順序串中第i個(gè)字符開始的、連續(xù)個(gè)字符開始的、連續(xù)j個(gè)字符組個(gè)字符組成的子順序串，并返回這個(gè)子串對(duì)象。當(dāng)參數(shù)成的子順序串，并返回這個(gè)子串對(duì)象。當(dāng)參數(shù)i、j不正確時(shí)

15、不正確時(shí)返回一個(gè)空串。對(duì)應(yīng)的算法如下：返回一個(gè)空串。對(duì)應(yīng)的算法如下：SqStringClass &SqStringClass:SubStr(int i,int j) /求子串求子串 static SqStringClass nstr;/新建一個(gè)空串新建一個(gè)空串int k;if (ilength | jlength)return nstr;/參數(shù)不正確時(shí)返回空串參數(shù)不正確時(shí)返回空串for (k=i-1;ki+j-1;k+)/將將str.datai.i+j-1nstrnstr.datak-i+1=datak;nstr.length=j;return nstr;/返回新建的順序串返回新建的順

16、序串例如例如，由順序串，由順序串s產(chǎn)生子串產(chǎn)生子串t對(duì)象的結(jié)果如圖對(duì)象的結(jié)果如圖4.4所示。所示。（7）串插入）串插入InsStr(i,s)將順序串將順序串s的所有字符插入到當(dāng)前串對(duì)象的第的所有字符插入到當(dāng)前串對(duì)象的第i個(gè)位置中個(gè)位置中產(chǎn)生一個(gè)新順序串，并返回這個(gè)新串對(duì)象。當(dāng)參數(shù)不正確時(shí)產(chǎn)生一個(gè)新順序串，并返回這個(gè)新串對(duì)象。當(dāng)參數(shù)不正確時(shí)返回一個(gè)空串對(duì)象。對(duì)應(yīng)的算法如下：返回一個(gè)空串對(duì)象。對(duì)應(yīng)的算法如下：SqStringClass &SqStringClass:InsStr(int i,SqStringClass &s) int j;static SqStringClass n

17、str;/新建一個(gè)空串新建一個(gè)空串if (ilength+1)/參數(shù)不正確時(shí)返回空串參數(shù)不正確時(shí)返回空串return nstr;for (j=0;ji-1;j+)/將當(dāng)前串將當(dāng)前串data0.i-2nstrnstr.dataj=dataj;for (j=0;js.length;j+)/將將s.data0.s.length-1nstrnstr.datai+j-1=s.dataj;for (j=i-1;jlength;j+)/將當(dāng)前串將當(dāng)前串datai-1.length-1nstrnstr.datas.length+j=dataj;nstr.length=length+s.length;retur

18、n nstr;/返回新建的順序串返回新建的順序串 例如，將順序串例如，將順序串s插入到順序串插入到順序串t中產(chǎn)生順序串對(duì)象中產(chǎn)生順序串對(duì)象t1的結(jié)果的結(jié)果如圖如圖4.5所示。所示。（8）串刪除）串刪除DelStr(i,j)從當(dāng)前順序串中刪去第從當(dāng)前順序串中刪去第i個(gè)字符開始的連續(xù)個(gè)字符開始的連續(xù)j個(gè)字符產(chǎn)生一個(gè)字符產(chǎn)生一個(gè)子順序串，并返回這個(gè)子串對(duì)象。當(dāng)參數(shù)不正確時(shí)返回一個(gè)子順序串，并返回這個(gè)子串對(duì)象。當(dāng)參數(shù)不正確時(shí)返回一個(gè)空串對(duì)象。對(duì)應(yīng)的算法如下：個(gè)空串對(duì)象。對(duì)應(yīng)的算法如下：SqStringClass &SqStringClass:DelStr(int i,int j) /串刪除串刪

19、除 int k;static SqStringClass nstr;/新建一個(gè)空串新建一個(gè)空串if (ilength | i+j-1length)/參數(shù)不正確時(shí)返回空串參數(shù)不正確時(shí)返回空串return nstr;for (k=0;ki-1;k+)/將當(dāng)前串將當(dāng)前串data0.i-2 nstrnstr.datak=datak;for (k=i+j-1;klength;k+)/將當(dāng)前串將當(dāng)前串datai+j-1.length-1nstrnstr.datak-j=datak;nstr.length=length-j;return nstr;/返回新建的順序串返回新建的順序串例如，刪除順序串例如，刪除

20、順序串s中的一個(gè)子串產(chǎn)生順序串對(duì)象中的一個(gè)子串產(chǎn)生順序串對(duì)象t的的結(jié)果如圖結(jié)果如圖4.6所示。所示。（9）串替換）串替換RepStr(i,j,s)將當(dāng)前順序串中第將當(dāng)前順序串中第i個(gè)字符開始的連續(xù)個(gè)字符開始的連續(xù)j個(gè)字符用串對(duì)象個(gè)字符用串對(duì)象s替替換而產(chǎn)生一個(gè)新順序串，并返回這個(gè)新串對(duì)象。當(dāng)參數(shù)不正確換而產(chǎn)生一個(gè)新順序串，并返回這個(gè)新串對(duì)象。當(dāng)參數(shù)不正確時(shí)返回一個(gè)空串。對(duì)應(yīng)的算法如下：時(shí)返回一個(gè)空串。對(duì)應(yīng)的算法如下：SqStringClass &SqStringClass:RepStr(int i,int j,SqStringClass &s) int k;static SqS

21、tringClass nstr;/新建一個(gè)空串新建一個(gè)空串if (ilength | i+j-1length)/參數(shù)不正確時(shí)返回空串參數(shù)不正確時(shí)返回空串return nstr;for (k=0;ki-1;k+)/將當(dāng)前串將當(dāng)前串data0.i-2nstrnstr.datak=datak;for (k=0;ks.length;k+)/將將s.data0.s.length-1nstrnstr.datai+k-1=s.datak;for (k=i+j-1;klength;k+)/將當(dāng)前串將當(dāng)前串datai+j-1.length-1nstrnstr.datas.length+k-j=datak;nst

22、r.length=length-j+s.length;return nstr;/返回新建的順序串返回新建的順序串例如，將順序串例如，將順序串t中某個(gè)子串替換為串對(duì)象中某個(gè)子串替換為串對(duì)象s產(chǎn)生產(chǎn)生t1串對(duì)象串對(duì)象的結(jié)果如圖的結(jié)果如圖4.7所示。所示。（10）串輸出）串輸出DispStr()輸出當(dāng)前順序串對(duì)象輸出當(dāng)前順序串對(duì)象s的所有字符。對(duì)應(yīng)的算法如下：的所有字符。對(duì)應(yīng)的算法如下：void SqStringClass:DispStr()/串輸出串輸出 int i;for (i=0;ilength;i+)cout datai;cout endl;【例【例4.2】 設(shè)計(jì)一個(gè)算法設(shè)計(jì)一個(gè)算法StrE

23、queal(s,t)比較兩個(gè)順序串比較兩個(gè)順序串s、t是否相等。是否相等。解：解：兩個(gè)順序串對(duì)象兩個(gè)順序串對(duì)象s、t相等的條件是它們的長度相等相等的條件是它們的長度相等且所有對(duì)應(yīng)位置上的字符均相同。對(duì)應(yīng)的算法如下：且所有對(duì)應(yīng)位置上的字符均相同。對(duì)應(yīng)的算法如下：#include SqString.cpp /包含順序串的基本運(yùn)算函數(shù)包含順序串的基本運(yùn)算函數(shù)bool StrEqueal(SqStringClass &s, SqStringClass &t) int i;if (s.length!=t.length)return false;for (i=0; inext=NULL;L

24、inkStringClass:LinkStringClass()/析構(gòu)函數(shù)析構(gòu)函數(shù) LinkNode *pre,*p;pre=head;p=pre-next;while (p!=NULL)/釋放鏈串所有結(jié)點(diǎn)空間釋放鏈串所有結(jié)點(diǎn)空間delete pre;pre=p; p=p-next;/pre、p同步后移同步后移delete pre;（2）建立串）建立串StrAssign(cstr)由一個(gè)字符串常量由一個(gè)字符串常量cstr建立一個(gè)鏈串對(duì)象，即生成一個(gè)建立一個(gè)鏈串對(duì)象，即生成一個(gè)其值等于其值等于cstr的串對(duì)象，這里采用重載的串對(duì)象，這里采用重載“=”運(yùn)算符實(shí)現(xiàn)的。運(yùn)算符實(shí)現(xiàn)的。對(duì)應(yīng)的算法如下：對(duì)

25、應(yīng)的算法如下：LinkStringClass &LinkStringClass:operator=(char *cstr)/重載賦值運(yùn)算符重載賦值運(yùn)算符 int i;LinkNode *r=head,*p;/r始終指向尾結(jié)點(diǎn)始終指向尾結(jié)點(diǎn)for (i=0;idata=cstri;r-next=p; r=p;/將將*p結(jié)點(diǎn)插入到尾部結(jié)點(diǎn)插入到尾部r-next=NULL;/尾結(jié)點(diǎn)的尾結(jié)點(diǎn)的next置為置為NULLreturn *this;本算法的思路是采用尾插法建立鏈串。例如，本算法的思路是采用尾插法建立鏈串。例如，cstr為為C+的字符串的字符串a(chǎn)bcdef，s為為LinkStringC

26、lass類對(duì)象，執(zhí)行類對(duì)象，執(zhí)行s=cstr的結(jié)果如圖的結(jié)果如圖4.10所示。所示。 （3）串復(fù)制）串復(fù)制StrCopy(t)將串對(duì)象將串對(duì)象t復(fù)制給當(dāng)前串對(duì)象，這里也是采用重載復(fù)制給當(dāng)前串對(duì)象，這里也是采用重載“=”運(yùn)運(yùn)算符實(shí)現(xiàn)的。對(duì)應(yīng)的算法如下：算符實(shí)現(xiàn)的。對(duì)應(yīng)的算法如下：LinkStringClass &LinkStringClass:operator=(LinkStringClass &t)/重載賦值運(yùn)算符重載賦值運(yùn)算符 LinkNode *p=t.head-next,*q,*r;r=head;/r始終指向尾結(jié)點(diǎn)始終指向尾結(jié)點(diǎn)while (p!=NULL)/將將t中結(jié)點(diǎn)

27、中結(jié)點(diǎn)*p復(fù)制產(chǎn)生結(jié)點(diǎn)復(fù)制產(chǎn)生結(jié)點(diǎn)*qq=new LinkNode();q-data=p-data;r-next=q; r=q;/將將*q結(jié)點(diǎn)插入到尾部結(jié)點(diǎn)插入到尾部p=p-next;r-next=NULL;/尾結(jié)點(diǎn)的尾結(jié)點(diǎn)的next置為置為NULLreturn *this;（4）求串長）求串長StrLength()返回當(dāng)前鏈串對(duì)象中的字符個(gè)數(shù)。對(duì)應(yīng)的算法如下：返回當(dāng)前鏈串對(duì)象中的字符個(gè)數(shù)。對(duì)應(yīng)的算法如下：int LinkStringClass:StrLength() /求串長度求串長度 int i=0;LinkNode *p=head-next;/p指向第一個(gè)字符結(jié)點(diǎn)指向第一個(gè)字符結(jié)點(diǎn)whi

28、le (p!=NULL)i+;p=p-next;/p移到下一個(gè)字符結(jié)點(diǎn)移到下一個(gè)字符結(jié)點(diǎn)return i;（5）串連接）串連接Concat(t)將當(dāng)前鏈串和鏈串將當(dāng)前鏈串和鏈串t的所有字符連接在一起形成新鏈串，并的所有字符連接在一起形成新鏈串，并返回這個(gè)新串對(duì)象，并不改變當(dāng)前串對(duì)象和串對(duì)象返回這個(gè)新串對(duì)象，并不改變當(dāng)前串對(duì)象和串對(duì)象t的內(nèi)容，這的內(nèi)容，這里采用重載里采用重載“+”運(yùn)算符實(shí)現(xiàn)的。對(duì)應(yīng)的算法如下：運(yùn)算符實(shí)現(xiàn)的。對(duì)應(yīng)的算法如下：LinkStringClass &LinkStringClass:operator+(LinkStringClass &t) static L

29、inkStringClass nstr; /新建一個(gè)空串新建一個(gè)空串LinkNode *p=head-next,*q,*r;r=nstr.head;while (p!=NULL)/將當(dāng)前鏈串的所有結(jié)點(diǎn)復(fù)制到將當(dāng)前鏈串的所有結(jié)點(diǎn)復(fù)制到nstrq=new LinkNode();q-data=p-data;r-next=q; r=q;/將將*q結(jié)點(diǎn)插入到尾部結(jié)點(diǎn)插入到尾部p=p-next;p=t.head-next;while (p!=NULL)/將鏈串將鏈串t的所有結(jié)點(diǎn)復(fù)制到的所有結(jié)點(diǎn)復(fù)制到nstrq=new LinkNode();q-data=p-data;r-next=q; r=q;/將將*q

30、結(jié)點(diǎn)插入到尾部結(jié)點(diǎn)插入到尾部p=p-next;r-next=NULL;/尾結(jié)點(diǎn)的尾結(jié)點(diǎn)的next置為置為NULLreturn nstr;/返回新建的鏈串返回新建的鏈串例如，鏈串對(duì)象例如，鏈串對(duì)象s和和t連接產(chǎn)生新串對(duì)象連接產(chǎn)生新串對(duì)象s1的結(jié)果如圖的結(jié)果如圖4.11所示。所示。（6）求子串）求子串SubStr(i,j)返回當(dāng)前鏈串中從第返回當(dāng)前鏈串中從第i個(gè)字符開始的連續(xù)個(gè)字符開始的連續(xù)j個(gè)字符組成的子個(gè)字符組成的子鏈串，并返回這個(gè)新子串。當(dāng)參數(shù)不正確時(shí)返回一個(gè)空串。以鏈串，并返回這個(gè)新子串。當(dāng)參數(shù)不正確時(shí)返回一個(gè)空串。以下采用尾插法建立鏈串下采用尾插法建立鏈串nstr并返回。對(duì)應(yīng)的算法如下：

31、并返回。對(duì)應(yīng)的算法如下：LinkStringClass &LinkStringClass:SubStr(int i,int j)/求子串求子串 static LinkStringClass nstr; /新建一個(gè)空串新建一個(gè)空串int k;LinkNode *p=head-next,*q,*r;r=nstr.head;/r指向新建鏈表的尾結(jié)點(diǎn)指向新建鏈表的尾結(jié)點(diǎn)if (iStrLength() | jStrLength()return nstr;/參數(shù)不正確時(shí)返回空串參數(shù)不正確時(shí)返回空串for (k=0;knext;for (k=1;kdata=p-data;r-next=q; r=q

32、;/將將*q結(jié)點(diǎn)插入到尾部結(jié)點(diǎn)插入到尾部p=p-next;r-next=NULL;/尾結(jié)點(diǎn)的尾結(jié)點(diǎn)的next置為置為NULLreturn nstr;/返回新建的鏈串返回新建的鏈串例如，由串對(duì)象例如，由串對(duì)象s產(chǎn)生子串產(chǎn)生子串t對(duì)象的結(jié)果如圖對(duì)象的結(jié)果如圖4.12所示。所示。（7）串插入）串插入InsStr(i,s)將鏈串將鏈串s插入到當(dāng)前鏈串中的第插入到當(dāng)前鏈串中的第i個(gè)位置產(chǎn)生一個(gè)新鏈串，個(gè)位置產(chǎn)生一個(gè)新鏈串，并返回這個(gè)新串對(duì)象。當(dāng)參數(shù)不正確時(shí)返回一個(gè)空串。以下采并返回這個(gè)新串對(duì)象。當(dāng)參數(shù)不正確時(shí)返回一個(gè)空串。以下采用尾插法建立鏈串用尾插法建立鏈串nstr并返回。對(duì)應(yīng)的算法如下：并返回。對(duì)應(yīng)

33、的算法如下：LinkStringClass &LinkStringClass:InsStr(int i,LinkStringClass &s) static LinkStringClass nstr;/新建一個(gè)空串新建一個(gè)空串int k;LinkNode *p=head-next,*p1=s.head-next,*q,*r;r=nstr.head;/r指向新建鏈表的尾結(jié)點(diǎn)指向新建鏈表的尾結(jié)點(diǎn)if (iStrLength()+1)/參數(shù)不正確時(shí)返回空串參數(shù)不正確時(shí)返回空串return nstr;for (k=1; kdata=p-data;r-next=q; r=q;/將將*q結(jié)

34、點(diǎn)插入到尾部結(jié)點(diǎn)插入到尾部p=p-next;while (p1!=NULL)/將將t中所有結(jié)點(diǎn)復(fù)制到中所有結(jié)點(diǎn)復(fù)制到nstrq=new LinkNode();q-data=p1-data;r-next=q; r=q;/將將*q結(jié)點(diǎn)插入到尾部結(jié)點(diǎn)插入到尾部 p1=p1-next;while (p!=NULL)/將將*p及其后的結(jié)點(diǎn)復(fù)制到及其后的結(jié)點(diǎn)復(fù)制到nstrq=new LinkNode();q-data=p-data;r-next=q; r=q;/將將*q結(jié)點(diǎn)插入到尾部結(jié)點(diǎn)插入到尾部p=p-next;r-next=NULL;/尾結(jié)點(diǎn)的尾結(jié)點(diǎn)的next置為置為NULLreturn nstr;/

35、返回新建的鏈串返回新建的鏈串例如，將串對(duì)象例如，將串對(duì)象s插入到串對(duì)象插入到串對(duì)象t中產(chǎn)生對(duì)象中產(chǎn)生對(duì)象t1的結(jié)果如圖的結(jié)果如圖4.13所示。所示。（8）子串刪除）子串刪除DelStr(i,j)從當(dāng)前鏈串中刪除從第從當(dāng)前鏈串中刪除從第i個(gè)字符開始連續(xù)個(gè)字符開始連續(xù)j個(gè)字符而產(chǎn)生一個(gè)字符而產(chǎn)生一個(gè)新鏈串，并返回這個(gè)新串對(duì)象。當(dāng)參數(shù)不正確時(shí)返回一個(gè)個(gè)新鏈串，并返回這個(gè)新串對(duì)象。當(dāng)參數(shù)不正確時(shí)返回一個(gè)空串。以下采用尾插法建立鏈串空串。以下采用尾插法建立鏈串nstr并返回。對(duì)應(yīng)的算法如下：并返回。對(duì)應(yīng)的算法如下：LinkStringClass &LinkStringClass:DelStr(i

36、nt i,int j)/串刪除串刪除 static LinkStringClass nstr;/新建一個(gè)空串新建一個(gè)空串int k;LinkNode *p=head-next,*q,*r;r=nstr.head;/r指向新建鏈表的尾結(jié)點(diǎn)指向新建鏈表的尾結(jié)點(diǎn)if (iStrLength() | jStrLength()return nstr;/參數(shù)不正確時(shí)返回空串參數(shù)不正確時(shí)返回空串for (k=0; kdata=p-data;r-next=q; r=q;/將將*q結(jié)點(diǎn)插入到尾部結(jié)點(diǎn)插入到尾部p=p-next;for (k=0;knext;while (p!=NULL)/將將*p及其后的結(jié)點(diǎn)復(fù)制

37、到及其后的結(jié)點(diǎn)復(fù)制到nstrq=new LinkNode();q-data=p-data;r-next=q; r=q;/將將*q結(jié)點(diǎn)插入到尾部結(jié)點(diǎn)插入到尾部p=p-next;r-next=NULL;/尾結(jié)點(diǎn)的尾結(jié)點(diǎn)的next置為置為NULLreturn nstr;/返回新建的鏈串返回新建的鏈串例如，刪除串對(duì)象例如，刪除串對(duì)象s中的一個(gè)子串產(chǎn)生串對(duì)象中的一個(gè)子串產(chǎn)生串對(duì)象t的結(jié)果如的結(jié)果如圖圖4.14所示。所示。（9）串替換）串替換RepStr(i,j,t) 將當(dāng)前鏈串中第將當(dāng)前鏈串中第i個(gè)字符開始的連續(xù)個(gè)字符開始的連續(xù)j個(gè)字符用串個(gè)字符用串t替換而產(chǎn)替換而產(chǎn)生一個(gè)新鏈串，并返回這個(gè)新串對(duì)象。當(dāng)

38、參數(shù)不正確時(shí)返回一生一個(gè)新鏈串，并返回這個(gè)新串對(duì)象。當(dāng)參數(shù)不正確時(shí)返回一個(gè)空串。以下采用尾插法建立鏈串個(gè)空串。以下采用尾插法建立鏈串nstr并返回。對(duì)應(yīng)的算法如并返回。對(duì)應(yīng)的算法如下：下：LinkStringClass &LinkStringClass:RepStr(int i,int j,LinkStringClass &s) static LinkStringClass nstr;/新建一個(gè)空串新建一個(gè)空串int k;LinkNode *p=head-next,*p1=s.head-next,*q,*r;r=nstr.head;/r指向新建鏈表的尾結(jié)點(diǎn)指向新建鏈表的尾結(jié)點(diǎn)i

39、f (iStrLength() | jStrLength()return nstr;/參數(shù)不正確時(shí)返回空串參數(shù)不正確時(shí)返回空串for (k=0; kdata=p-data;r-next=q; r=q;/將將*q結(jié)點(diǎn)插入到尾部結(jié)點(diǎn)插入到尾部p=p-next;for (k=0;knext;while (p1!=NULL)/將將t中所有結(jié)點(diǎn)復(fù)制到中所有結(jié)點(diǎn)復(fù)制到nstrq=new LinkNode();q-data=p1-data;r-next=q; r=q;/將將*q結(jié)點(diǎn)插入到尾部結(jié)點(diǎn)插入到尾部p1=p1-next;while (p != NULL)/將將*p及其后的結(jié)點(diǎn)復(fù)制到及其后的結(jié)點(diǎn)復(fù)制到n

40、strq=new LinkNode();q-data=p-data;r-next=q; r=q;/將將*q結(jié)點(diǎn)插入到尾部結(jié)點(diǎn)插入到尾部p=p-next;r-next=NULL;/尾結(jié)點(diǎn)的尾結(jié)點(diǎn)的next置為置為NULLreturn nstr;/返回新建的鏈串返回新建的鏈串例如，將串對(duì)象例如，將串對(duì)象t中某個(gè)子串替換為串對(duì)象中某個(gè)子串替換為串對(duì)象s產(chǎn)生產(chǎn)生t1串對(duì)象串對(duì)象的結(jié)果如圖的結(jié)果如圖4.15所示。所示。（10）DispStr()輸出當(dāng)前鏈串中的所有字符結(jié)點(diǎn)的值。對(duì)應(yīng)的算法如下：輸出當(dāng)前鏈串中的所有字符結(jié)點(diǎn)的值。對(duì)應(yīng)的算法如下：void LinkStringClass:DispStr()/

41、串輸出串輸出 LinkNode *p=head-next;/p指向鏈串的頭結(jié)點(diǎn)指向鏈串的頭結(jié)點(diǎn)while (p!=NULL)cout data;p=p-next;/p指向下一個(gè)結(jié)點(diǎn)指向下一個(gè)結(jié)點(diǎn)cout next;LinkNode *q=t.head-next;while (p!=NULL & q!=NULL)if (p-data!=q-data)return false;p=p-next; q=q-next;if (p=NULL & q=NULL) return true;else return false;4.3 串的模式匹配串的模式匹配4.4.1 Brute-Force算

42、法算法Brute-Force簡稱為簡稱為BF算法，亦稱簡單匹配算法，其基本算法，亦稱簡單匹配算法，其基本思路是：思路是：從從目標(biāo)串目標(biāo)串s=“s0s1sn-1”的第一個(gè)字符開始和的第一個(gè)字符開始和模式串模式串t=“t0t1tm-1”中的第一個(gè)字符比較，若相等，則繼續(xù)逐個(gè)比較中的第一個(gè)字符比較，若相等，則繼續(xù)逐個(gè)比較后續(xù)字符；否則從目標(biāo)串后續(xù)字符；否則從目標(biāo)串s的第二個(gè)字符開始重新與模式串的第二個(gè)字符開始重新與模式串t的第一個(gè)字符進(jìn)行比較。的第一個(gè)字符進(jìn)行比較。依次類推，若從模式串依次類推，若從模式串s的第的第i個(gè)字符開始，每個(gè)字符依次個(gè)字符開始，每個(gè)字符依次和目標(biāo)串和目標(biāo)串t中的對(duì)應(yīng)字符相等，

43、則匹配成功，該算法返回中的對(duì)應(yīng)字符相等，則匹配成功，該算法返回i；否；否則，匹配失敗，算法返回則，匹配失敗，算法返回-1。例如，設(shè)目標(biāo)串例如，設(shè)目標(biāo)串s=“aaaaab”，模式串，模式串t=“aaab”。s的長度為的長度為n（n=6），），t的長度為的長度為m（m=4）。用指針）。用指針i指示目標(biāo)串指示目標(biāo)串s的當(dāng)前的當(dāng)前比較字符位置，用指針比較字符位置，用指針j指示模式串指示模式串t的當(dāng)前比較字符位置。模式的當(dāng)前比較字符位置。模式匹配過程如下所示。匹配過程如下所示。對(duì)應(yīng)的對(duì)應(yīng)的BF算法如下：算法如下：int Index(SqStringClass &s,SqStringClass &

44、amp;t) int i=0, j=0;while (is.length & j=t.length) return (i-t.length);/返回匹配的第一個(gè)字符的下標(biāo)返回匹配的第一個(gè)字符的下標(biāo)else return (-1);/模式匹配不成功模式匹配不成功BF算法簡單，易于理解，但效率不高，主要原因是：算法簡單，易于理解，但效率不高，主要原因是：主串指針主串指針i在若干個(gè)字符序列比較相等后，若有一個(gè)字符比在若干個(gè)字符序列比較相等后，若有一個(gè)字符比較不相等，仍需回溯（即較不相等，仍需回溯（即i=i- -j+1）。）。BF算法在最好情況下的時(shí)間復(fù)雜度為算法在最好情況下的時(shí)間復(fù)雜度為O(

45、m)，即主串的，即主串的前前m個(gè)字符正好等于模式串的個(gè)字符正好等于模式串的m個(gè)字符。在最壞情況下的時(shí)個(gè)字符。在最壞情況下的時(shí)間復(fù)雜度為間復(fù)雜度為O(nm)?！纠纠?.6】 設(shè)主串設(shè)主串s=ababcabcacbab，模式串，模式串t=abcac。給出給出BF進(jìn)行模式匹配的過程。進(jìn)行模式匹配的過程。解：解：采用采用BF算法進(jìn)行模式匹配的過程如下：算法進(jìn)行模式匹配的過程如下： 4.3.2 KMP算法算法例如，目標(biāo)串例如，目標(biāo)串s=“aaaaab”，模式串，模式串t=“aaab”。當(dāng)進(jìn)行第。當(dāng)進(jìn)行第1趟匹配時(shí)，匹配失敗處為趟匹配時(shí)，匹配失敗處為i=3，j=3。盡管本次匹配失敗了，。盡管本次匹配失敗

46、了，但得到這樣的啟發(fā)信息：但得到這樣的啟發(fā)信息：s的前的前3個(gè)字符個(gè)字符s0s1s2與與t的前的前3個(gè)字符個(gè)字符t0t1t2相同，另外從相同，另外從t中看到，中看到，t0t1與與t1t2相同，所以有相同，所以有s1s2=t1t2=t0t1。下一趟匹配從。下一趟匹配從s1開始，由于開始，由于s1s2=t0t1，所以只，所以只需將需將s3與與t2開始比較即可，如下圖所示。開始比較即可，如下圖所示。 實(shí)際上，模式串中的實(shí)際上，模式串中的“部分匹配部分匹配”信息就是信息就是真子串真子串。所。所謂真子串就是指模式串謂真子串就是指模式串t存在某個(gè)存在某個(gè)k（0kj），使得），使得t0t1tk-1=tj-k

47、tj-k+1tj-1成立。例如成立。例如t=abcac就是包含有真子串的模就是包含有真子串的模式串。歸納起來，求模式式串。歸納起來，求模式t的的nextj數(shù)組的公式如下：數(shù)組的公式如下：void GetNext(SqStringClass &t,int next)/由模式串由模式串t求出求出next值值 int j=0,k=-1; next0=-1;while (jt.length-1)if (k=-1 | t.dataj=t.datak)/k為為-1或比較的字符相等時(shí)或比較的字符相等時(shí) j+;k+;nextj=k;else k=nextk;求模式串求模式串t的的next數(shù)組的算法如下：數(shù)組的算法如下：KMP算法如下：算法如下： int KMPIndex(SqStringClass &s,SqStringClass &t)/KMP算法算法 int nextMaxSize;int i=0,j=0;GetNext(t,next);/求出部分匹配信息求出部分匹配信息next數(shù)組數(shù)組while (is