數(shù)據(jù)結(jié)構(gòu)-C語言描述（第三版）課件：串

串4.1串的基本概念4.2串的存儲(chǔ)實(shí)現(xiàn)

4.2.1定長順序串

4.2.2堆串

4.2.3塊鏈串4.3串的應(yīng)用舉例：簡單的行編輯器4.4總結(jié)與提高返回主目錄4.1串的基本概念串(String)是零個(gè)或多個(gè)字符組成的有限序列。一般記為：S=‘a(chǎn)1a2…an’(n≥0)子串：串中任意個(gè)連續(xù)的字符組成的子序列稱為該串的子串。主串：包含子串的串相應(yīng)地稱為主串。其中S為串名，用單引號括起來的為串值，n為串的長度。通常將字符在串中的序號稱為該字符在串中的位置?？崭翊河梢粋€(gè)或多個(gè)稱為空格的特殊字符組成的串?？沾簄=0時(shí)的串為空串返回主目錄4.1串的定義串(String)是零個(gè)或多個(gè)字符組成的有限序列。一般記為：S=‘a(chǎn)1a2…an’(n≥0)子串：串中任意個(gè)連續(xù)的字符組成的子序列稱為該串的子串。主串：包含子串的串相應(yīng)地稱為主串。其中S為串名，用單引號括起來的為串值，n為串的長度。通常將字符在串中的序號稱為該字符在串中的位置?？崭翊河梢粋€(gè)或多個(gè)稱為空格的特殊字符組成的串?？沾簄=0時(shí)的串為空串串相等：當(dāng)且僅當(dāng)兩個(gè)串的值相等時(shí),稱這兩個(gè)串是相等的

串的抽象數(shù)據(jù)類型定義：ADTString{數(shù)據(jù)對象:D={ai|ai∈CharacterSet,i=1,2,…,n;n≥0}數(shù)據(jù)關(guān)系:R={<ai-1,ai>|ai-1,ai∈D,i=2,…,n;n≥0}基本操作：

（1）

StrAsign(S,chars)

初始條件:chars是字符串常量操作結(jié)果:生成一個(gè)值等于chars的串S返回主目錄（2）StrInsert(S,pos,T)

初始條件:串S和T存在,1≤pos≤StrLength(S)+1

操作結(jié)果:在串S的第pos個(gè)字符之前插入串T（3）StrDelete(S,pos,len)

初始條件:串S存在,1≤pos≤StrLength(S)-len+1

操作結(jié)果:從串S中刪除第pos個(gè)字符起長度為len的子串（4）StrCopy(S,T)

初始條件:串S存在操作結(jié)果:由串T復(fù)制得串S返回主目錄（5）StrEmpty(S)

初始條件:串S存在操作結(jié)果:若串S為空串,則返回TRUE,否則返回FALSE（6）StrCompare(S,T)

初始條件:串S和T存在操作結(jié)果:若S>T,則返回值>0;若S=T,則返回值=0;若S<T,則返回值<0（7）StrLength(S)

初始條件:串S存在操作結(jié)果:返回串S的長度,即串S中的元素個(gè)數(shù)返回主目錄（8）StrClear(S)

初始條件:串S存在操作結(jié)果:將S清為空串（9）StrCat(S,T)

初始條件:串S和T存在操作結(jié)果:將串T的值連接在串S的后面（10）SubString(Sub,S,pos,len)

初始條件:串S存在,1≤pos≤StrLength(S)且1≤len≤StrLength(S)-pos+1

操作結(jié)果:用Sub返回串S的第pos個(gè)字符起長度為len的子串

返回主目錄（11）StrIndex(S,T,pos)

初始條件:串S和T存在,T是非空串,1≤pos≤StrLength(S)

操作結(jié)果:若串S中存在與串T相同的子串,則返回它在串S中第pos個(gè)字符之后第一次出現(xiàn)的位置;否則返回0（12）StrReplace(S,T,V)

初始條件:串S,T和V存在,且T是非空串操作結(jié)果:用V替換串S中出現(xiàn)的所有與T相等的不重疊子串（13）StrDestroy(S)

初始條件:串S存在操作結(jié)果:銷毀串S返回主目錄4.2串的存儲(chǔ)實(shí)現(xiàn)定長順序串堆串塊鏈串常用的實(shí)現(xiàn)方法有：4.2.1定長順序串定長順序串是將串設(shè)計(jì)成一種靜態(tài)結(jié)構(gòu)類型，串的存儲(chǔ)分配是在編譯時(shí)完成的。

1.定長順序串存儲(chǔ)結(jié)構(gòu)#defineMAXLEN20typedefstruct{/*串結(jié)構(gòu)定義*/charch[MAXLEN];intlen;}SString;返回主目錄2.定長順序串基本操作的實(shí)現(xiàn)

（1）串插入函數(shù)有三種情況：

(1)插入后串長(LA+LC+LB)≤MAXLEN，則將B后移LC個(gè)元素位置，再將C插入。(2)插入后串長>MAXLEN且pos+LC<MAXLEN，則B后移時(shí)會(huì)有部分字符被舍棄。(3)插入后串長>MAXLEN且pos+LC>MAXLEN，則

B的全部字符被舍棄（不需后移），并且C在插入時(shí)也有部分字符被舍棄。StrInsert(SString*s,intpos,SStringt)/*在串s中下標(biāo)為pos的字符之前插入串t*/{inti;if(pos<0||pos>s->len)return(0);/*插入位置不合法*/if(s->len+t.len<=MAXLEN){/*插入后串長≤MAXLEN*/for(i=s->len+t.len-1;i>=t.len+pos;i--) s->ch[i]=s->ch[i-t.len];for(i=0;i<t.len;i++)s->ch[i+pos]=t.ch[i];s->len=s->len+t.len;}elseif(pos+t.len<=MAXLEN){/*插入后串長>MAXLEN,但串t的字符序列可以全部插入*/for(i=MAXLEN-1;i>t.len+pos-1;i--)s->ch[i]=s->ch[i-t.len];for(i=0;i<t.len;i++)s->ch[i+pos]=t.ch[i];s->len=MAXLEN;}else{/*插入后串長>MAXLEN,并且串t的部分字符也要舍棄

for(i=0;i<MAXLEN-pos;i++)s->ch[i+pos]=t.ch[i];s->len=MAXLEN;}return(1);}順序串插入函數(shù)算法

（2）串刪除函數(shù)StrDelete(SString*s,intpos,intlen)/*在串s中刪除從下標(biāo)pos起len個(gè)字符*/{inti;if(pos<0||pos>(s->len-len))return(0);/*刪除參數(shù)不合法*/for(i=pos+len;i<s->len;i++)s->ch[i-len]=s->ch[i];/*從pos+len開始至串尾依次向前移動(dòng)，實(shí)現(xiàn)刪除len個(gè)字符*/s->len=s->len-len;/*s串長減len*/return(1);}（3）串復(fù)制函數(shù)StrCopy(SString*s,SStringt)/*將串t的值復(fù)制到串s中*/{inti;for(i=0;i<t.len;i++)s->ch[i]=t.ch[i];s->len=t.len;}（4）判空函數(shù)StrEmpty(SStrings)/*若串s為空則返回1，否則返回0*/{if(s.len==0)return(1);elsereturn(0);}返回主目錄（5）串比較函數(shù)StrCompare(SStrings,SStringt)/*若串s和t相等則返回0；若s>t則返回正數(shù)；若s<t則返回負(fù)數(shù)*/{inti;for(i=0;i<s.len&&i<t.len;i++)if(s.ch[i]!=t.ch[i])return(s.ch[i]-t.ch[i]);return(s.len-t.len);}返回主目錄（6）求串長函數(shù)StrLength(SStrings)/*返回串s的長度*/{return(s.len);}返回主目錄（7）清空函數(shù)StrClear(SString*s)/*將串s置為空串*/{s->len=0;}返回主目錄（8）連接函數(shù)(3)連接后串長>MAXLEN且LA=MAXLEN，則B的全部字符被舍棄（不需連接）。

(1)連接后串長≤MAXLEN，則直接將B加在A的后面。(2)連接后串長>MAXLEN且LA<MAXLEN，則B會(huì)有部分字符被舍棄。StrCat(SString*s,SStringt)/*將串連接在串s的后面*/{inti,flag;if(s->len+t.len<=MAXLEN)/*連接后串長小于MAXLEN*/{for(i=s->len;i<s->len+t.len;i++)s->ch[i]=t.ch[i-s->len];s->len+=t.len;flag=1;}elseif(s->len<MAXLEN)/*連接后串長大于MAXLEN，但串s的長度小于MAXLEN，

{即連接后串t的部分字符序列被舍棄*/for(i=s->len;i<MAXLEN;i++)s->ch[i]=t.ch[i-s->len];s->len=MAXLEN;flag=0;}elseflag=0;/*串s的長度等于MAXLEN,串t不被連接*/return(flag);}串連接函數(shù)算法（9）求子串函數(shù)SubString(SString*sub,SStrings,intpos,intlen)/*將串s中下標(biāo)pos起len個(gè)字符復(fù)制到sub中*/{inti;if(pos<0||pos>s.len||len<1||len>s.len-pos){sub->len=0;return(0);}else{for(i=0;i<len;i++)sub->ch[i]=s.ch[i+pos];sub->len=len;return(1);}}

（10）定位函數(shù)T為目標(biāo)串（主串），S為模式串(子串)，在主串T中找子串S的過程為模式匹配（patternmatching）。用定位函數(shù)實(shí)現(xiàn)求子串T在主串S中從pos的位置開始第一次出現(xiàn)的位置序號，定位函數(shù)也叫串的模式匹配。

【問題分析】3.串的簡單模式匹配Brute-Force（布魯特-福斯）算法

簡單的模式匹配算法是一種帶回溯的匹配算法，算法的基本思想是：從主串S的第pos個(gè)字符開始，和模式串T的第一個(gè)字符開始比較，如果相等，就繼續(xù)比較后續(xù)字符，如果不等，則從（回溯到）主串S的第pos+1個(gè)字符開始重新和模式串T比較，直到模式串T中的每一個(gè)字符和主串S中的一個(gè)連續(xù)字符子序列全部相等，則稱匹配成功，返回和T中第一個(gè)字符相等的字符在主串T中的位置；或者主串中沒有和模式串相等的字符序列，則稱匹配不成功。

【算法思想】實(shí)現(xiàn)時(shí)設(shè)i、j、start三個(gè)指示器：i——指向主串T中當(dāng)前比較的字符，起始指向T的首字符，此后，每比較一步，后移一步，一趟匹配失敗時(shí)，回溯到該趟比較起點(diǎn)的下一位置。j——指向子串S中當(dāng)前比較的字符，起始指向S的首字符，此后，每比較一步，后移一步，一趟匹配失敗時(shí)，回溯到S的首字符處。start——記錄每趟比較時(shí)在主串T中的起點(diǎn)，每趟比較后，后移一步，以便確定下一趟的起始位置。

【算法描述】StrIndex(SStrings,intpos,SStringt)/*求從主串s的下標(biāo)pos起，串t第一次出現(xiàn)的位置，成功返回位置序號，不成功返回-1*/{inti,j,start;if(t.len==0)return(0);/*模式串為空串時(shí)，是任意串的匹配串

*/start=pos;i=start;j=0;/*主串從pos開始，模式串從頭（0）開始

*/while(i<s.len&&j<t.len)if(s.ch[i]==t.ch[j]){i++;j++;}/*當(dāng)前對應(yīng)字符相等時(shí)推進(jìn)

*/else{start++;/*當(dāng)前對應(yīng)字符不等時(shí)回溯

*/i=start;j=0;/*主串從start+1開始，模式串從頭（0）開始*/}if(j>=t.len)return(start);/*匹配成功時(shí)，返回匹配起始位置

*/elsereturn(-1);/*匹配不成功時(shí)，返回-1*/}順序串的簡單模式匹配（定位）函數(shù)算法

4.2.2堆串字符串包括串名與串值兩部分，而串值采用堆串存儲(chǔ)方法存儲(chǔ)，串名用符號表存儲(chǔ)。堆串存儲(chǔ)方法：仍以一組地址連續(xù)的存儲(chǔ)單元存放串的字符序列，但它們的存儲(chǔ)空間是在程序執(zhí)行過程中動(dòng)態(tài)分配的。系統(tǒng)將一個(gè)地址連續(xù)、容量很大的存儲(chǔ)空間作為字符串的可用空間，每當(dāng)建立一個(gè)新串時(shí)，系統(tǒng)就從這個(gè)空間中分配一個(gè)大小和字符串長度相同的空間存儲(chǔ)新串的串值。堆串存儲(chǔ)表示：在C語言中，已經(jīng)有一個(gè)稱為“堆”的自由存儲(chǔ)空間，并可用函數(shù)malloc（）和函數(shù)free（）完成動(dòng)態(tài)存儲(chǔ)管理。因此，我們可以直接利用C語言中的“堆”來實(shí)現(xiàn)堆串。此時(shí)堆串可定義如下：

typedefstruct{char*ch；

intlen；

}HString；

其中l(wèi)en域指示串的長度，ch域指示串的起始地址。

串名符號表：所有串名的存儲(chǔ)映像構(gòu)成一個(gè)符號表。借助此結(jié)構(gòu)可以在串名和串值之間建立一個(gè)對應(yīng)關(guān)系，稱為串名的存儲(chǔ)映像。

堆串：heap[MAXSIZE]free=23

堆串：heap[MAXSIZE]free=23符號表aprogramstringprocess符號名lenstarta90b79c716堆串的存儲(chǔ)映象示例a='aprogram'，b='string'，c='process'，free=23。堆串的基本操作(1)堆串賦值函數(shù)StrAssign(HString*s,char*tval)/*將字符常量tval的值賦給串s*/{intlen，i=0;if(s->ch!=NULL)free(s->ch);while(tval[i]!='\0')i++;len=i;if(len){s->ch=(char*)malloc(len);if(s->ch==NULL)return(0);for(i=0;i<len;i++)s->ch[i]=tval[i];}elses->ch=NULL;s->len=len;return(1);}(2)堆串插入函數(shù)StrInsert(HString*s，intpos，HString*t)/*在串s中下標(biāo)為pos的字符之前插入串t*/{inti;char*temp;if(pos<0||pos>s->len||s->len==0)return(0);temp=(char*)malloc(s->len+t->len);if(temp==NULL)return(0);for(i=0;i<pos;i++)temp[i]=s->ch[i];for(i=0;i<t->len;i++)temp[i+pos]=t->ch[i];for(i=pos;i<s->len;i++)temp[i+t.->len]=s->ch[i];s->len+=t->len;free(s->ch);s->ch=temp;return(1);}(3)堆串刪除函數(shù)StrDelete(HString*s，intpos，intlen)/*在串s中刪除從下標(biāo)pos起len個(gè)字符*/{inti;char*temp;if(pos<0||pos>(s->len-len))return(0);temp=(char*)malloc(s->len-len);if(temp==NULL)return(0);for(i=0;i<pos;i++)temp[i]=s->ch[i];for(i=pos;i<s->len-len;i++)temp[i]=s->ch[i+len];s->len=s->len-len;free(s->ch);s->ch=temp;return(1);}4.2.3塊鏈串#defineBLOCK_SIZE4/*每結(jié)點(diǎn)存放字符個(gè)數(shù)*/typedefstructBlock{charch[BLOCK_SIZE];structBlock*next;}Block;

typedefstruct{Block*head;Block*tail;intlength;}BLString;塊鏈結(jié)構(gòu)的定義4.3串的應(yīng)用舉例:文本編輯文本編輯程序用于源程序的輸入和修改，公文書信、報(bào)刊和書籍的編輯排版等。常用的文本編輯程序有Edit，WPS，Word等。為了編輯方便，可以用分頁符和換行符將文本分為若干頁，每頁有若干行。我們把文本當(dāng)作一個(gè)字符串，稱為文本串，頁是文本串的子串，行是頁的子串。我們采用堆存儲(chǔ)結(jié)構(gòu)來存儲(chǔ)文本，同時(shí)設(shè)立頁指針、行指針和字符指針，分別指向當(dāng)前操作的頁、行和字符，同時(shí)建立頁表和行表存儲(chǔ)每一頁、每一行的起始位置和長度。

假設(shè)有如下Pascal源程序：FUNCmax(x，y：integer)：integer;VARz：integer;BEGINIFx>yTHENz:=x;ELSEz:=y;RETURN(z);END;

頁號起始位置長度10107行號

起始位置

長度

103123115346645221573146871471015FUNC

max(x，y:integer):integer;↙VAR

z:integer;↙BEGIN↙

IF

x<y

THEN

z:=x;↙

ELSE

z:=y;↙

RETURN(z);↙END;↙

4.5總結(jié)與提高4.5.1主要知識點(diǎn)

字符串是一種特定的線性表，其特殊性就在于組成線性表的每個(gè)元素就是一個(gè)單字符。字符串常用的存儲(chǔ)方式有三種：順序串、堆串和塊鏈串。順序串以一維數(shù)組作為存儲(chǔ)結(jié)構(gòu)，運(yùn)算實(shí)現(xiàn)類同順序表。塊鏈串以鏈表作為存儲(chǔ)結(jié)構(gòu)，運(yùn)算實(shí)現(xiàn)類同鏈表。串的模式匹配算法是本章的重點(diǎn)，簡單的模式匹配算法處理思路簡單，由于進(jìn)行了帶回溯的處理，時(shí)間復(fù)雜度較高。改進(jìn)的KMP模式匹配算法計(jì)算滑動(dòng)位置，因而失配后無回溯，匹配速度較高。4.5.2典型題例

要求編寫一個(gè)用帶頭結(jié)點(diǎn)的單鏈表實(shí)現(xiàn)串的模式匹配算法，每個(gè)結(jié)點(diǎn)存放一個(gè)字符（結(jié)點(diǎn)大小為1）。

【問題分析】該算法類同順序串的簡單模式匹配，實(shí)現(xiàn)匹配過程需考慮鏈表