串市公開課一等獎省賽課獲獎?wù)n件

第四章串串第1頁第四章串學(xué)習(xí)關(guān)鍵點

1了解串基本操作，了解利用這些基本操作實現(xiàn)串其它操作方法；

2掌握在串堆分配存放結(jié)構(gòu)下，串基本操作算法；

串也叫字符串，它是由零個或多個字符組成字符序列?；緝?nèi)容

1串相關(guān)概念串基本操作

2串定長次序存放結(jié)構(gòu)，堆分配存放結(jié)構(gòu)；

3串基本操作算法；

串第2頁一、串定義

1什么是串

串是一個特殊線性表，它是由零個或多個字符組成有限序列，普通記作s=“a1,a2,a3,...an”其中s----串名，a1,a2,a3,...an----串值串應(yīng)用非常廣泛，許多高級語言中都把串作為基本數(shù)據(jù)類型。在事務(wù)處理程序中，用戶姓名、地址貨物名稱、產(chǎn)地可作為字符串處理，文本文件中每一行字符等也可作為字符串處理。4.1串類型定義串第3頁下面是一些串例子：

（1）a=‘LIMING’

（2）b=‘PEJINGUNIUERCITY’

（3）c=‘DATASTRUCTURE’

（4）d=‘’

（5）e=‘’

說明：1)串中包含字符個數(shù)，稱為串長度。

長度為0串稱為空串，它不包含任何字符，上面（4）中串d是空串，(5)中e是包含一個空格符空格串；

2）串中所包含字符能夠是字母、數(shù)字或其它字符，這依賴于詳細(xì)計算機所允許字符集。串第4頁2串相關(guān)術(shù)語1）子串

串中任意連續(xù)字符組成子序列稱為該串子串

例：c=‘DATASTRUCTURE’，f=‘DATA’f是c子串2）子串位置子串T在主串S中位置是指主串S中第一個與T相同子串首字母在主串中位置。例：S=‘a(chǎn)babcabcac’,T=‘a(chǎn)bc’子串T在主串S中位置為33）串相等

兩個串相等，當(dāng)且僅當(dāng)兩個串長度相同，而且各個對應(yīng)位置字符都相同；串第5頁3串基本操作

串邏輯結(jié)構(gòu)與線性表一樣，都是線性結(jié)構(gòu)。主要區(qū)分在于串?dāng)?shù)據(jù)對象約束為字符集。但因為串應(yīng)用與線性表不一樣，串基本操作與線性表有很大差異。1）串賦值操作StrAssign(&T,chars)

功效：將串常量char值賦給串變量T；2）復(fù)制串操作

StrCopy(&T,S)

功效：由串變量S復(fù)制得到串變量T；3）判空操作

StrEmpty(S)功效：若為空串，則返回TRUE，不然返回FALSE4）串比較操作StrCompare(S,T)

功效若S>T，則返回值>0；若S=T，則返回值=0；若S<T，則返回值<05）串置空操作ClearString(&S)

功效：將S清為空串串第6頁6）求串長操作

StrLenght(&S)

功效：求串S長度7）串連接操作

Concat(&T,S1,S2)

功效：由S1和S2連接組成新串，用T返回新串；

8）求子串操作SubString(&Sub,S,pos,len)

功效：用Sub返回串S第pos個字符起長度len為子串；

9）求子串位置操作Index(S,T,pos)

功效：返回S中第pos個字符之后與T相同子串位置，若不存在返回010)串插入操作

StrInsert(&S,pos,T)

功效：將串T插入到串S第pos字符之前11）串刪除操作

StrDelete(&S,pos,len)

功效：從串S中刪除第pos個字符起長度為len子串串第7頁4.2串表示和實現(xiàn)一、串存放（三種）1定長次序存放結(jié)構(gòu)

定長次序存放結(jié)構(gòu)類似于C語言字符數(shù)組，以一組地址連續(xù)存放單元存放串值字符序列，其類型說明以下：

#defineMAXSTRLEN255TypedefunsignedcharSString[MAXSTRLEN+1]

//0號單元存放串長度2、堆分配存放

堆分配存放類似于線性表次序存放結(jié)構(gòu)，以一組地址連續(xù)存放單元存放串值字符序列，其存放空間是在程序執(zhí)行過程中動態(tài)分配。在C語言中，存在一個稱之為“堆”自由存放區(qū)，并由C語言動態(tài)分配函數(shù)管理。利用函數(shù)malloc()為每個新產(chǎn)生串分配一塊實際串長所需存放空間，若分配成功，則返回一個指向起始地址指針，作為串基址，同時，為了以后處理方便，將串長也作為存放結(jié)構(gòu)一部分。串這種存放結(jié)構(gòu)本教材中稱為堆分配存放

串第8頁

在這種存放結(jié)構(gòu)下，串操作仍是基于“字符序列復(fù)制”進行。比如，如串插入操作StrInsert(S,pos,T)（將串T插入到串S第pos字符之前）算法是，為串S重新分配大小等于串S和串T長度之和存放空間，然后進行將S和T串值復(fù)制到新分配存放空間中算法4.4。

以上兩種存放表示通常為高級程序設(shè)計語言所采取。因為堆分配存放結(jié)構(gòu)串現(xiàn)有次序存放結(jié)構(gòu)特點，處理方便，操作中對串長又沒有任何限制，更顯靈活，所以在串處理應(yīng)用程序中常被采取。

以下我們給出在堆分配存放結(jié)構(gòu)下，串部分基本操作算法。堆分配存放類型說明Typedefstruct{char*ch;//指針域，指向存放串值存放空間基址intlength;//整型域：存放串長}Hstring;串第9頁串插入算法

StrInsert(HString&S,intpos,HStringT){//為串S重新分配大小等于串S和串T長度之和存放空間，將S和//T串值復(fù)制到新分配存放空間中;在串S第pos個字符前插入串Tif(pos<1||pos>S.length+1)returnERROR;//參數(shù)不正當(dāng)if(T.lenght){//若T非空，為串S重新分配存放空間,并插入Tif(!(S.ch=(char*)realloc((S.ch,S.length+T.length)*sizeof(char))));exit(OVERFLOW);for(i=S.length-1;i>=pos-1;--i)//將S第pos個字符及后面字符后

S.ch[i+T.length]=S.ch[i];//移，為插入T騰出T.length位置S.ch[pos-1..pos+T.length-2]=T.ch[0..T.length-1];//插入TS.length+=T.length;//修改串長為S與T長之和}returnOK;}SubString

算法4.4

串第10頁S.lengthnS.ch01pos-1n-1n+m-1S.lengthn+mS.lengthn01pos-1n-1S.chT.chT.lengthm0

1m-1為串S重新分配存放空間,并將S復(fù)制到新空間將S第pos個字符及后面字符后移，為插入T騰出位置插入T修改串長串第11頁二串基本操作算法串賦值算法StatusStrAssign(HString&T,char*chars){//生成一個其值等于串常量chars串Tif(T.ch)free(T.ch);//若原T.ch非空，釋放T.ch所指向舊存放空間for(i=0,c=chars;c;++i,++c);//求chars長度iif(!i){T.ch=NULL;T.length=0;}//若i=0,生成空串Telse{if(!(T.ch=(char*)malloc(i*sizeof(char))))//分配存放空間exit(OVERFLOW);T.ch[0..i-1]=chars[0..i-1];T.length=i;}returnOK;}//StrAssign串第12頁串常量依據(jù)串常量長度動態(tài)分配存放空間a1a2anchars01n-1傳遞數(shù)據(jù)T.chT.length01n-1a1a2an串賦值操作圖示n串第13頁串比較算法intStrCompare(HStringS,HStringT){//若S>T，則返回值>0；若S=T，則返回值=0；若S<T，則返回值<0for(i=0;i<S.length&&i<T.length;++i)if(S.ch[i]!=T.ch[i])returnS.ch[i]-T.ch[i];returnS.length-T.length;}//StrCompare

串置空算法StatusClearString(HString&S){//將S清為空串。if(S.ch){free(S.ch);S.ch=NULL;}//若S.ch非空，釋放S.ch所指向

//存放空間，而且S.ch=nullS.length=0;returnOK;}//ClearString

串第14頁串連接算法StatusConcat(HString&T,HstringS1,HStringS2){//用T返回由S1和S2連接而成新串。if(T.ch)free(T.ch);//若T.ch非空，釋放T.ch所指向舊存放空間if(!(T.ch=(char*)malloc((S1.Length+S2.length）*sizeof(char))))exit(OVERFLOW);T.ch[0..S1.length-1]=S1.ch[0..S1.length-1];//先復(fù)制S1串?dāng)?shù)據(jù)T.length=S1.length+S2.length;T.ch[S1.length..T.length-1]=S2.ch[0..S2.length-1];//接著復(fù)制S2串?dāng)?shù)據(jù)returnOK;}//Concat

串第15頁s1.ch01n1-1s1.lengthn1s2.ch01n2-1s2.lengthn2串s1串s2進行串合并s.ch01n1-1n1n1+n2-1

s.lengthn1+n2

串連接圖示串第16頁求子串算法StatusSubString(HString&Sub,HStringS,intpos,intlen){//用Sub返回串S第pos個字符起長度為len子串。//其中，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。if(pos<1||pos>S.length||len<0||len>S.length-pos+1)returnERROR;//參數(shù)不正當(dāng)if(Sub.ch)free(Sub.ch);//若Sub.ch非空，釋放Sub.ch所指向存放空間if(!len){Sub.ch=NULL;Sub.length=0;}//若len=0，Sub為空子串else{//復(fù)制子串Sub.ch=(char*)malloc(len*sizeof(char));Sub.ch[0..len-1]=S[pos-1..pos+len-2];Sub.length=len;}returnOK;}SubString串第17頁01Sub.chLen-1Sub.lengthlen動態(tài)分配存放空間01pos-1n-1S.lengthnS.ch01Sub.chLen-1Sub.lengthlen串第18頁三串其它操作能夠利用串基本操作實現(xiàn)串其它操作，參見P72算法4.1,實現(xiàn)定位函數(shù)Index(S,T,pos),算法:在主串S中取從第i(i初值為pos)個字符起、長度和串T相等子串和串T比較,若相等,則求得函數(shù)值i,不然i值增1直到串S中不存在和串T相等子串為止。串第19頁4.2.3串塊鏈?zhǔn)酱娣沤Y(jié)構(gòu)

次序串上插入和刪除操作不方便，需要移動大量字符。所以，我們可用單鏈表方式來存放串值，串這種鏈?zhǔn)酱娣沤Y(jié)構(gòu)簡稱為鏈串。

typedefstructChunk{chardata;structChunk*next;}Chunk;

一個鏈串由頭指針唯一確定。

這種結(jié)構(gòu)便于進行插入和刪除運算，但存放空間利用率太低。串第20頁

為了提升存放密度，可使每個結(jié)點存放多個字符。通常將結(jié)點數(shù)據(jù)域存放字符個數(shù)定義為結(jié)點大小，顯然，當(dāng)結(jié)點大小大于1時，串長度不一定恰好是結(jié)點整數(shù)倍，所以要用特殊字符來填充最終一個結(jié)點，以表示串終止。還可設(shè)一尾指針,并給出當(dāng)前串長度,此串存放結(jié)構(gòu)為塊鏈結(jié)構(gòu),對于結(jié)點大小不為1鏈串，其類型定為義只需對上述結(jié)點類型做簡單修改即可。#defineCHUNKSIZE80//可由用戶定義塊大小

typedefstructChunk{chardata[CHUNKSIZE];structChunk*next;}Chunktypedefstruct{Chunk*head,*tail;//串頭和尾指針intcurlen;//串當(dāng)前長度}LString串第21頁4.3串模式匹配算法

求子串位置定位函數(shù)

子串定位操作通常稱作串模式匹配（其中T被稱為模式串），是各種串處理系統(tǒng)中最主要操作之一。下面給出一個模式匹配算法，在本算法中，串采取定長次序存放結(jié)構(gòu)，其類型說明以下：

#defineMAXSTRLEN255TypedefunsignedcharSstring[MAXSTRLEN+1]

本算法中，分別利用計數(shù)指針i和j指示主串S和模式串T中當(dāng)前正待比較字符位置。算法基本思想是：從主串S第一個字符起和模式第一個字符比較之，若相等，則繼續(xù)逐一比較后續(xù)字符，不然從主串下一個字符起再重新和模式字符比較之。依次類推，直至模式T中每個字符依次和主串S中一個連續(xù)字符序列相等，則稱匹配成功，函數(shù)值為模式T中第一個了符相等字符在主串S中序號，不然稱匹配不成功，函數(shù)值為零。圖4.3展示了模式和主串S匹配過程。串第22頁intIndex(SStringS,SStringT,int