《數(shù)據(jù)結(jié)構(gòu)（C++版）（第二版）》課件第04章

2023年11月28日1第4章串本章學(xué)習(xí)內(nèi)容4.1串的定義及運(yùn)算

4.2串的存儲(chǔ)結(jié)構(gòu)

4.3串運(yùn)算的實(shí)現(xiàn)

4.4串操作應(yīng)用舉例2023年11月28日24.1串的定義及運(yùn)算

4.1.1基本概念1．串的定義串（string）是由零個(gè)或多個(gè)字符組成的有限序列，記作s=“a1a2…an”，其中s為串的名字，用成對(duì)的雙引號(hào)括起來(lái)的字符序列為串的值，但兩邊的雙引號(hào)不算串值，不包含在串中。ai（1≤i≤n）可以是字母、數(shù)字或其他字符。n為串中字符的個(gè)數(shù)，稱為串的長(zhǎng)度。串s=“a1a2…an”，也可以表示為s=(a1,a2,…,an)，即線性表的形式。因此，串也是一種線性表，是一種數(shù)據(jù)類型受到限制（只能為字符型）的線性表。2．空串不含任何字符的串稱為空串，它的長(zhǎng)度n=0，記為s=“”。3．空白串含有一個(gè)空格的串，稱為空白串，它的長(zhǎng)度n=1，記為s=“”或s=“?”。2023年11月28日34．子串、主串若一個(gè)串是另一個(gè)串中連續(xù)的一段，則這個(gè)串稱為另一個(gè)串的子串，而另一個(gè)串相對(duì)于該串稱為主串。例如，串s1=“abcdefg”，s2=“fabcdefghxyz”，則s1為s2的子串，s2相對(duì)于s1為主串。另外，空串是任意串的子串，任意串是自身的子串。若一個(gè)串的長(zhǎng)度為n，則它的子串?dāng)?shù)目為，真子串個(gè)數(shù)為（除串本身以外的子串都稱為真子串）。4.1.2串的運(yùn)算為描述方便，假定用大寫字母表示串名，小寫字母表示組成串的字符。1．賦值assign(&S,T)表示將T串的值賦給S串。2．聯(lián)接concat(&S,T)表示將S串和T串聯(lián)接起來(lái)，使T串接入S串的后面。3．求串長(zhǎng)度length(T)求T串的長(zhǎng)度。2023年11月28日44．子串substr(S,i,j,&T)表示截取S串中從第i個(gè)字符開(kāi)始連續(xù)j個(gè)字符，作為S的一個(gè)子串，存入T串。5．串比較大小strcmp(S,T)比較S串和T串的大小，若S<T，函數(shù)值為負(fù)；若S=T，函數(shù)值為零；若S>T，函數(shù)值為正。6．串插入insert(&S,i,T)在S串的第i個(gè)位置插入T串。7．串刪除del(&S,i,j)刪除串S中從第i個(gè)字符開(kāi)始連續(xù)j個(gè)字符。8．求子串位置index(S,T)求T子串在S主串中首次出現(xiàn)的位置，若T串不是S串的子串，則得到的位置為-1（若在順序存儲(chǔ)中，數(shù)組的下標(biāo)從1開(kāi)始，則T串不是S串的子串時(shí)，得到的位置為0）。9．串替換replace(&S,i,j,T)將S串中從第i個(gè)位置開(kāi)始連續(xù)j個(gè)字符，用T串替換。2023年11月28日54.1.3串的抽象數(shù)據(jù)類型描述串的抽象數(shù)據(jù)類型可描述為：ADTstringsISData:含有n個(gè)字符a1,a2,a3,…,anOperation:voidassign(&S,T) //表示將T串的值賦給S串voidconcat(&S,T) //表示將S串和T串聯(lián)接起來(lái)，使T串接入S串的后面intlength(T) //求T串的長(zhǎng)度voidsubstr(S,i,j,&T) //表示截取S串中從第i個(gè)字符開(kāi)始連續(xù)j個(gè)字符，作為S的一個(gè)子串，存入T串中intstrcmp(S,T) //比較S串和T串的大小，若S<T，函數(shù)值為負(fù)，S=T，函數(shù)值為零，S>T，函數(shù)值為正voidinsert(&S,i,T) //在S串的第i個(gè)位置插入T串voiddel(&S,i,j) //刪除串S中從第i個(gè)字符開(kāi)始連續(xù)j個(gè)字符intindex(S,T) //求T子串在S主串中首次出現(xiàn)的位置，若T串不是S串的子串，則位置為零voidreplace(&S,i,j,T) //將S串中從第i個(gè)位置開(kāi)始連續(xù)j個(gè)字符，用T串替換Endstrings2023年11月28日64.2串的存儲(chǔ)結(jié)構(gòu)4.2.1順序存儲(chǔ)串的順序存儲(chǔ)結(jié)構(gòu)，也稱為順序串，與第2章介紹的順序表（線性表的順序存儲(chǔ)）類似。但由于串中的元素全部為字符，故順序串的存放形式與順序表有所區(qū)別。1．串的非緊縮存儲(chǔ)一個(gè)存儲(chǔ)單元中只存儲(chǔ)一個(gè)字符，和順序表中一個(gè)元素占用一個(gè)存儲(chǔ)單元類似。具體形式見(jiàn)圖4-1，設(shè)串S=“Howdoyoudo”。2．串的緊縮存儲(chǔ)根據(jù)各機(jī)器字的長(zhǎng)度，盡可能將多個(gè)字符存放在一個(gè)字中。假設(shè)一個(gè)字可存儲(chǔ)4個(gè)字符，則緊縮存儲(chǔ)具體形式見(jiàn)圖4-2。2023年11月28日7圖4-1S串的非緊縮存儲(chǔ)圖4-2S串的緊縮存儲(chǔ)（設(shè)一個(gè)字有4個(gè)字符位置）2023年11月28日8從上面介紹的兩種存儲(chǔ)方式可知，緊縮存儲(chǔ)能夠節(jié)省大量存儲(chǔ)單元，但對(duì)串的單個(gè)字符操作很不方便，需要花費(fèi)較多的處理時(shí)間。而非緊縮存儲(chǔ)的特點(diǎn)剛好相反，操作方便，但將占用較多的內(nèi)存單元。3．串的字節(jié)存儲(chǔ)前兩種存儲(chǔ)方法都是以字編址形式進(jìn)行的，而字節(jié)編址方式是一個(gè)字符占用一個(gè)字節(jié)，具體形式見(jiàn)圖4-3。圖4-3S串的字節(jié)編址存儲(chǔ)（一個(gè)字符占一個(gè)字節(jié)）2023年11月28日94．順序串的數(shù)據(jù)類型描述constintmaxsize=maxlen; //maxlen表示串的最大容量classseqstring{public:charch[maxsize]; //存放串的值的一維數(shù)組intcurlen; //當(dāng)前串的長(zhǎng)度voidassign(&S,T) //類中的成員函數(shù)voidconcat(&S,T) intlength(T) voidsubstr(S,i,j,&T) intstrcmp(S,T) voidinsert(&S,i,T) voiddel(&S,i,j) intindex(S,T) voidreplace(&S,i,j,T) }；2023年11月28日104.2.2鏈?zhǔn)酱鎯?chǔ)串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也稱為鏈串，與第2章介紹的鏈表（線性表的鏈?zhǔn)酱鎯?chǔ)）類似，但鏈串的特點(diǎn)是鏈表中的結(jié)點(diǎn)數(shù)據(jù)域只能是字符型。1．結(jié)點(diǎn)大小為1的鏈?zhǔn)酱鎯?chǔ)和前面介紹的單鏈表一樣，每個(gè)結(jié)點(diǎn)為一個(gè)字符，鏈表也可以帶頭結(jié)點(diǎn)。例如S=“abcdef”的存儲(chǔ)結(jié)構(gòu)具體形式見(jiàn)圖4-4。圖4-4S串的鏈?zhǔn)酱鎯?chǔ)示意圖2023年11月28日112．結(jié)點(diǎn)大小為K的鏈?zhǔn)酱鎯?chǔ)和緊縮存儲(chǔ)類似，假設(shè)一個(gè)字中可以存儲(chǔ)K個(gè)字符，則一個(gè)結(jié)點(diǎn)有K個(gè)數(shù)據(jù)域和一個(gè)指針域，若一個(gè)結(jié)點(diǎn)中數(shù)據(jù)域少于K個(gè)，用?代替。例如，串S=“abcdef”的存儲(chǔ)結(jié)構(gòu)具體形式如圖4-5所示。假設(shè)K=4，并且鏈表帶頭結(jié)點(diǎn)。圖4-5S串的結(jié)點(diǎn)大小為4的鏈?zhǔn)酱鎯?chǔ)2023年11月28日123．鏈串的數(shù)據(jù)類型描述（1）結(jié)點(diǎn)大小為1的鏈串與第2章單鏈表的定義類似，只需將data域的類型由元素類型elemtype改為字符類型char即可。classlink{public:chardata;link*next;……//類中的成員函數(shù)}2023年11月28日13（2）結(jié)點(diǎn)大小為k(k=4)的鏈串具體描述形式見(jiàn)圖4-5。數(shù)據(jù)類型描述為：classlink4{public:chardata[5];//僅使用data[1]到data[4]存儲(chǔ)空間

link4*next;};2023年11月28日144.2.3索引存儲(chǔ)該方法是用串變量的名字作為關(guān)鍵字組織名字表（索引表），該表中存儲(chǔ)的是串名和串值之間的對(duì)應(yīng)關(guān)系。名字表中包含的項(xiàng)目根據(jù)不同的需要來(lái)設(shè)置，只要為存取串值提供足夠的信息即可。如果串值是以鏈接方式存儲(chǔ)的，則名字表中只要存入串名及其串值的鏈表的頭指針即可。若串值是以順序方式存放的，則表中除了存入指示串值存放的起始地址首指針外，還必須有信息指出串值存放的末地址。末地址的表示方法有幾種：給出串長(zhǎng)、在串值末尾設(shè)置結(jié)束符、設(shè)置尾指針直接指向串值末地址等。具體介紹下面兩種：1．帶長(zhǎng)度的名字表在表中給出串名、串存放的起始位置及串長(zhǎng)度，具體形式見(jiàn)圖4-6。圖4-6帶長(zhǎng)度的名字表2023年11月28日15從圖4-6可知，S1的長(zhǎng)度為7，起始位置從a開(kāi)始，故S1=“abcdefg”，而S2的長(zhǎng)度為3，起始位置從g開(kāi)始，故S2=“gbc”。2．帶末指針的名字表在表中給出串的名字、頭指針及末指針，具體形式見(jiàn)圖4-7。圖4-7帶末指針的名字表從圖4-7可知，兩個(gè)串的名字分別為S1和S2，而S1的頭指針指向a，末指針指向g，故有S1=“abcdefg”，而S2的頭指針指向g，末指針指向c，故有S2=“gbc”。2023年11月28日164.3串運(yùn)算的實(shí)現(xiàn)4.3.1串插入1．順序串上的插入insert(&S,i,T)要將T串插入到S串中第i個(gè)位置，則S串中第i個(gè)位置開(kāi)始，一直到最后的字符，每個(gè)都要向后移動(dòng)若干位，移動(dòng)的位數(shù)為T串長(zhǎng)度。算法描述如下：voidseqstring::Insert(seqstring&S,inti,seqstringT){if(S.curlen+T.curlen>=maxsize)cout<<"overflow";else{for(intj=S.curlen-1;j>=i;j--)S.ch[j+T.curlen]=s.ch[j]; //元素后移T.curlen位

for(j=0;j<T.curlen;j++)S.ch[j+i]=T.ch[j]; //插入元素T到S中

S.curlen=S.curlen+T.curlen; //表長(zhǎng)度增加

}}設(shè)n為S串長(zhǎng)度，m為T串長(zhǎng)度，則該算法的時(shí)間復(fù)雜度為O(n+m)。2023年11月28日172．鏈串的插入insert(&S,i,T)僅考慮結(jié)點(diǎn)大小為1的鏈串，要在第i個(gè)位置插入，先用一個(gè)指針指向S串的第i-1個(gè)位置，然后在T串中用另一個(gè)指針指向最后，算法描述如下：voidlink::Insert(link*S,inti,link*T){link*P,*Q;intj=0;P=S;while(P!=NULL)&&(j<i-1) //查找S中第i-1個(gè)結(jié)點(diǎn)位置{j++;P=P->next;}Q=T;while(Q->next!=NULL)Q=Q->next; //查找T串最后一個(gè)元素if(P!=NULL) //插入{Q->next=P->next;P->next=T->next; //去掉T串的頭結(jié)點(diǎn)}elsecout<<"error!" //找不到插入位置}該算法花費(fèi)的時(shí)間主要在查找上，時(shí)間復(fù)雜度為O(n+m)。2023年11月28日184.3.2串刪除1．順序串的刪除del(&S,i,j)刪除S串中從第i個(gè)位置開(kāi)始連續(xù)j個(gè)字符，可以分成三種情形討論：（1）若i值不在串長(zhǎng)度范圍內(nèi)，不能刪除；（2）從i位置開(kāi)始到最后的字符數(shù)目不足j個(gè)，刪除時(shí)，不需移動(dòng)元素，只需修改串長(zhǎng)度即可；（3）i和j都可以滿足需求。算法描述如下：voidseqstring::delete(seqstring&s,inti,intj){if((i<0)||(i>=s.curlen))cout<<"error"; //i值不在串值范圍內(nèi)，不能刪除

elseif(s.curlen-i+1<j)s.curlen=i-1; //從i位置開(kāi)始到最后的字符數(shù)目不足j個(gè)，刪除時(shí)

//不需移動(dòng)元素，只修改串長(zhǎng)度即可else{for(intk=i+j;k<=s.curlen;k++)s.ch[k-j]=s.ch[k]; //元素前移j位

s.curlen=s.curlen–j; //表長(zhǎng)度減j}}該算法的時(shí)間復(fù)雜度為O(n)。2023年11月28日192．鏈串的刪除del(&S,i,j)和順序串的刪除一樣，也可以分三種情形來(lái)討論。算法描述如下：voidlink::delete(link*S,inti,intj){link*P,*Q;intk=0;P=S;while(P!=NULL)&&(k<i-1) //查找第i-1位置

{k++;P=P->next;}Q=P;while(Q!=NULL)&&(k<i+j) //查找第i+j位置{k++;Q=Q->next;}if(P!=NULL) //保證i合法{if(Q!=NULL)P->next=Q;elseP->next=NULL;}elsecout<<"error";}該算法的時(shí)間復(fù)雜度為O(n)。2023年11月28日204.3.3子串定位1．順序串上的子串定位運(yùn)算index(S,T)子串的定位運(yùn)算通常稱為串的模式匹配，是串處理中最重要的運(yùn)算之一。設(shè)串s=“a1a2…an”，串T=“b1b2…bm”（m≤n），子串定位是要在主串S中找出一個(gè)與子串T相同的子串。通常把主串S稱為目標(biāo)，把子串T稱為模式，把從目標(biāo)S中查找模式為T的子串的過(guò)程稱為“模式匹配”。匹配有兩種結(jié)果出現(xiàn)：若S中有模式為T的子串，就返回該子串在S中的位置，當(dāng)S中有多個(gè)模式為T的子串，通常只要找出第一個(gè)子串即可，這種情況稱為匹配成功，若S中無(wú)模式為T的子串，返回值為-1（若數(shù)組下標(biāo)從1開(kāi)始，返回值為0），稱為匹配失敗。模式匹配過(guò)程如下圖所示，假設(shè)S=“abababac”，T=“abac”。2023年11月28日21（a）第一趟匹配s3

t3（b）第二趟匹配s1

t0（c）第三趟匹配s5

t3（d）第四趟匹配s3

t0（e）第五趟匹配成功2023年11月28日22模式匹配算法如下：intseqstring::INDEX(seqstringS,seqstringT){inti=0,j=0;while((i<S.curlen)&&(j<T.curlen))if(S.ch[i]==T.ch[j]){i++;j++;}else{i=i-j+1; //將i指針回溯

j=0;}if(j>=T.curlen)return(i-T.curlen);elsereturn(-1); } //匹配失敗}該算法的最好時(shí)間復(fù)雜度為O(n+m)，最壞時(shí)間復(fù)雜度為O(n

m)。2023年11月28日232．鏈串上的子串定位運(yùn)算index(S,T)鏈串上的子串定位運(yùn)和順序串上的子串定位運(yùn)算類似，但返回的值不是位置，而是位置指針。若匹配成功，則返回T串在S串中的地址（指針），若匹配不成功，則返回空指針。算法描述如下：link*link::index(link*S,link*T) //假設(shè)兩個(gè)鏈串都帶頭結(jié)點(diǎn){link*P,*Q,*R;P=S->next;Q=T->next;R=P;while(P!=NULL)&&(Q!=NULL)if(P->data==Q->data){P=P->next;Q=Q->next;}else{R=R->next; //指針回溯

P=R;Q=T->next;}if(Q==NULL) //匹配成功

rerurnR;elsereturnNULL; //匹配失敗}該算法的時(shí)間復(fù)雜度與順序串上的運(yùn)算相同。2023年11月28日244.4串操作應(yīng)用舉例4.4.1文本編輯文本編輯程序是一個(gè)面向用戶的系統(tǒng)服務(wù)程序，廣泛用于源程序的輸入和修改，甚至用于報(bào)刊和書籍的編輯排版，以及辦公室的公文書信起草和潤(rùn)色。文本編輯的實(shí)質(zhì)是修改字符數(shù)據(jù)的形式或格式。雖然各種文本編輯程序的功能強(qiáng)弱不同，但是其基本操作是一致的，一般都包括串的查找、插入和刪除等。為了編輯的方便，用戶可以利用換頁(yè)符和換行符把文件劃分為若干頁(yè)