計(jì)算機(jī)科學(xué)系：王嵐市公開課金獎(jiǎng)市賽課一等獎(jiǎng)?wù)n件

第四章串4.1串類型定義4.2串表示和實(shí)現(xiàn)4.2.1定長(zhǎng)次序存放表示4.2.2堆分配存放表示4.2.3串塊鏈存放表示計(jì)算機(jī)科學(xué)系：王嵐第1頁(yè)

4.1串類型定義一、串和基本概念串(String)是零個(gè)或多個(gè)字符組成有限序列。普通記作S=“a1a2a3…an”，其中S是串名，雙引號(hào)括起來字符序列是串值；ai(1≦i≦n)能夠是字母、數(shù)字或其它字符；串中所包含字符個(gè)數(shù)稱為該串長(zhǎng)度。長(zhǎng)度為零串稱為空串(EmptyString)，它不包含任何字符。通常將僅由一個(gè)或多個(gè)空格組成串稱為空白串(BlankString)

注意：空串和空白串不一樣，比如“”和“”分別表示長(zhǎng)度為1空白串和長(zhǎng)度為0空串。第2頁(yè)

串中任意個(gè)連續(xù)字符組成子序列稱為該串子串，包含子串串對(duì)應(yīng)地稱為主串。通常將子串在主串中首次出現(xiàn)時(shí)該子串首字符對(duì)應(yīng)主串中序號(hào)，定義為子串在主串中序號(hào)（或位置）。比如，設(shè)A和B分別為A=“Thisisastring”B=“is”則B是A子串，A為主串。B在A中出現(xiàn)了兩次，其中首次出現(xiàn)所對(duì)應(yīng)主串位置是3。所以，稱B在A中序號(hào)（或位置）為3。尤其地，空串是任意串子串，任意串是其本身子串。

第3頁(yè)通常在程序中使用串可分為兩種：串變量和串常量。串常量和整常數(shù)、實(shí)常數(shù)一樣，在程序中只能被引用但不能改變其值，即只能讀不能寫。通常串常量是由直接量來表示，比如語(yǔ)句Error(“overflow”)中“overflow”是直接量。但有語(yǔ)言允許對(duì)串常量命名，以使程序易讀、易寫。如C++中，可定義constcharpath[]=“dir/bin/appl”;這里path是一個(gè)串常量，對(duì)它只能讀不能寫。串變量和其它類型變量一樣，其取值是能夠改變。兩個(gè)串相等：長(zhǎng)度相等，對(duì)應(yīng)位置字符都相等。二、串抽象數(shù)據(jù)定義串抽象數(shù)據(jù)類型定義見書P71第4頁(yè)三、串基本操作對(duì)于串基本操作，許多高級(jí)語(yǔ)言均提供了對(duì)應(yīng)運(yùn)算或標(biāo)準(zhǔn)庫(kù)函數(shù)來實(shí)現(xiàn)。下面僅介紹幾個(gè)在C語(yǔ)言中慣用串運(yùn)算，其它串操作見書P71。定義以下幾個(gè)變量：chars1[20]=“dirtreeformat”,s2[20]=“file.mem”;chars3[30],*p;intresult;求串長(zhǎng)(length)intstrlen(chars);//求串長(zhǎng)度比如：printf(“%d”,strlen(s1));輸出13第5頁(yè)（2）串復(fù)制(copy)char*strcpy(charto,charfrom);該函數(shù)將串from復(fù)制到串to中，而且返回一個(gè)指向串to開始處指針。比如：strcpy(s3,s1);//s3=“dirtreeformat”(3)聯(lián)接(concatenation)charstrcat(charto,charfrom)該函數(shù)將串from復(fù)制到串to末尾，而且返回一個(gè)指向串to開始處指針。比如：strcat(s3,”/”)strcat(s3,s2);//s3=“dirtreeformat/file.mem”第6頁(yè)(4)串比較（compare)intstrcmp(chars1,chars2);該函數(shù)比較串s1和串s2大小，當(dāng)返回值小于0，等于0或大于0時(shí)分別表示s1<s2\s1=s2或s1>s2比如：result=strcmp(“baker”,”Baker”)result>0result=strcmp(“12”,”12”);result=0result=strcmp(“Joe”,”Joseph”);result<0（5）字符定位(strchr)charstrchr(chars,charc);該函數(shù)是找c在字符串s中第一次出現(xiàn)位置，若找到則返回該位置，不然返回NULL。比如：p=strchr(s2,”.”);p指向“file”之后位置if(p)strcpy(p,”.cpp”);s2=“file.cpp”第7頁(yè)上述串操作是最基本，其中后四個(gè)還有變種形式：strncpy，strncat，strncmp，strnchr。串其余操作可由這些基本操作組合而成。例1、求子串

求子串過程即為復(fù)制字符序列過程，將串S中第pos個(gè)字符開始長(zhǎng)度為len字符復(fù)制到串sub中。voidsubstr(stringsub,strings,intpos,intlen){if(pos<0||pos>strlen(s)-1||len<0)error(“parametererror”)strncpy(sub,&s[pos],len);}第8頁(yè)例2、串定位index(s,t,pos)

算法思想？算法思想：1、在主串中取從第i個(gè)字符起長(zhǎng)度和串t相等子串和t比較2、若相等，則求得函數(shù)值為i，3、不然i值增1直至s中不存在和串t相等子串為止。第9頁(yè)intindex(strings,stringt,intpos){if(pos>0){n=strlen(s);m=strlen(t);i=pos;while(i<n-m+1){substr(sub,s,i,m);if(strcmp(sub,t)!=0)++i;elsereturn(i);}}return(0);}第10頁(yè)

4.2串表示和實(shí)現(xiàn)

因?yàn)榇翘厥饩€性表，故其存放結(jié)構(gòu)與線性表存放結(jié)構(gòu)類似。只不過因?yàn)榻M成串結(jié)點(diǎn)是單個(gè)字符。串?dāng)?shù)據(jù)對(duì)象約束為字符集。串有三種機(jī)內(nèi)表示方法，下面分別介紹。4.2.1定長(zhǎng)次序存放表示

定長(zhǎng)次序存放表示,也稱為靜態(tài)存放分配次序表。它是用一組連續(xù)存放單元來存放串中字符序列。所謂定長(zhǎng)次序存放結(jié)構(gòu)，是直接使用定長(zhǎng)字符數(shù)組來定義，數(shù)組上界預(yù)先給出：#definemaxstrlen256typedefcharsstring[maxstrlen];sstrings;//s是一個(gè)可容納255個(gè)字符次序串。0號(hào)單元存放串長(zhǎng)度第11頁(yè)1.串聯(lián)接Concat(&T,S1,S2)Statusconcat(Sstring&T,SstringS1,SstringS2){if(S1[0]+S2[0]<=MAXSTRLEN)//未截?cái)鄘T[1..s1[0]]=S1[1..S1[0]];T[S1[0]+1..S1[0]+S2[0]]=S2[1..S2[0]];T[0]=S1[0]+S2[0];uncut=TRUE;}elseif(S1[0]<MAXSTRSIZE)//截?cái)鄘T[1..S1[0]]=S1[1..S1[0]];T[S1[0]+1..MAXSTRLEN]=S2[1..MAXSTRLEN-S1[0]];T[0]=MAXSTRLEN;uncut=FALSE;}else{T[0..MAXSTRLEN]=S1[0..MAXSTRLEN];//截?cái)?僅取S1)uncut=FALSE;}returnuncut;}第12頁(yè)求子串：SubString(&Sub,S,pos,len)StatusSubString(Sstring&Sub,SstringS,intpos,intlen){if(pos<1||pos>S[0]||len<0||len>S[0]-pos+1)returnERROR;Sub[1..len]=S[pos..pos+len-1];Sub[0]=len;returnOK;}第13頁(yè)

4.2.2堆分配存放表示

這種存放表示特點(diǎn)是，仍以一組地址連續(xù)存放單元存放串值字符序列，但它們存放空間是在程序執(zhí)行過程中動(dòng)態(tài)分配而得。所以也稱為動(dòng)態(tài)存放分配次序表。在C語(yǔ)言中，利用動(dòng)態(tài)存放管理函數(shù)，來依據(jù)實(shí)際需要?jiǎng)討B(tài)分配和釋放字符數(shù)組空間。這么定義次序串類型也有兩種形式。typedefchar*string;//c中串庫(kù)相當(dāng)于這類型定義typedefstruct{char*ch;//若是非空串，則按串長(zhǎng)分配存放區(qū)，不然ch為NULL.intlength;}hsring;第14頁(yè)

普通可使用一個(gè)不會(huì)出現(xiàn)在串中特殊字符在串值尾部來表示串結(jié)束。比如，C語(yǔ)言中以字符‵\0′表示串值終止，這就是為何在上述定義中，串空間最大值maxstrlen為256，但最多只能存放255個(gè)字符原因，因?yàn)楸仨毩粢粋€(gè)字節(jié)來存放‵\0′字符。若不設(shè)終止符，可用一個(gè)整數(shù)來表示串長(zhǎng)度，那么該長(zhǎng)度減1位置就是串值最終一個(gè)字符位置。此時(shí)次序串類型定義和次序表類似：typedefstruct{charch[maxstrlen];intlength;}hstring;//其優(yōu)點(diǎn)是包括到串長(zhǎng)操作時(shí)速度快。

第15頁(yè)

statussinsert(hstrings,intpos,hstringt){

if(pos<1||pos>s.length+1)returnerror;if(t.length){if(!(s.ch=(char*)realloc(s.ch,(s.length+t.length)*sizeof(char)))exit(overflow);for(i=s.length-1;i>pos-1;--i)s.ch[i+t.length]=s.ch[i];//每個(gè)字符都移動(dòng)t長(zhǎng)度s.ch[pos-1..pos+t.length-2]=t.ch[0..t.length-1];s.length+=t.length;}returnok;}第16頁(yè)intstrlen(hstrings){returns.length;}statusclearstring(hstrings){if(s.ch){free(s.ch);s.ch=NULL;}s.length=0;}第17頁(yè)statusstrassign(hstringt,char*chars){//生成一個(gè)其值等于串常量chars串tif(t.ch)free(t.ch);for(i=0,c=chars;c;++i,++c);//求chars長(zhǎng)度iif(!i){t.ch=null;t.length=0;}else{if(!(t.ch=(char*)malloc(i*sizeof(char))))exit(overflow);

第18頁(yè)t.ch[0..i-1]=chars[0..i-1];t.length=i;}}

第19頁(yè)intstrcmp(hstrings,hstringt){//若S>T，則返回值>0；若S=T，則返回值=0；//若S<T，則返回值<0;for(i=0;i<s.length&&i<t.length;++i)if(s.ch[i]!=t.ch[i]return(s.ch[i]-t.ch[i]);returns.length-t.length;}第20頁(yè)statusconcat(hstringt,hstrings1,hstrings2){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];t.length=s1.length+s2.length;t.ch[s1.length..t.length-1]=s2.ch[0..s2.length-1];}第21頁(yè)Statussubstr(hstringsub,hstrings,intpos,intlen){if(pos<1||pos>s.length||len<0||len>s.length-pos+1)returnerror;if(sub.ch)free(sub.ch);if(!len){sub.ch=null;sub.length=0;}第22頁(yè)else{sub.ch=(char*)malloc(len*sizeof(char));sub.ch[0..len-1]=s[pos-1..pos+len-2];

s.length=len;}returnok;}//SubString第23頁(yè)4.2.3串鏈?zhǔn)酱娣沤Y(jié)構(gòu)次序串上插入和刪除操作不方便，需要移動(dòng)大量字符。所以，我們可用單鏈表方式來存放串值，串這種鏈?zhǔn)酱娣沤Y(jié)構(gòu)簡(jiǎn)稱為鏈串。typedefstructnode{chardata;structnode*next;}lstring;

一個(gè)鏈串由頭指針唯一確定。這種結(jié)構(gòu)便于進(jìn)行插入和刪除運(yùn)算，但存放空間利用率太低。第24頁(yè)為了提升存放密度，可使每個(gè)結(jié)點(diǎn)存放多個(gè)字符。通常將結(jié)點(diǎn)數(shù)據(jù)域存放字符個(gè)數(shù)定義為結(jié)點(diǎn)大小，顯然，當(dāng)結(jié)點(diǎn)大小大于1時(shí)，串長(zhǎng)度不一定恰好是結(jié)點(diǎn)整數(shù)倍，所以要用特殊字符來填充最終一個(gè)結(jié)點(diǎn)，以表示串終止。對(duì)于結(jié)點(diǎn)大小不為1鏈串，其類型定為義只需對(duì)上述結(jié)點(diǎn)類型做簡(jiǎn)單修改即可。#definenodesize80typedefstructnode{chardata[nodesize];structnode*next;}lstring;第25頁(yè)

4.3串模式匹配算法

子串定位運(yùn)算又稱為模式匹配(PatternMatching)或串匹配(StringMatching)，此運(yùn)算應(yīng)用非常廣泛。比如，在文本編輯程序中，我們經(jīng)常要查找某一特定單詞在文本中出現(xiàn)位置。顯然，解此問題有效算法能極大地提升文本編輯程序響應(yīng)性能。在串匹配中，普通將主串稱為目標(biāo)串，子串稱之為模式串。設(shè)S為目標(biāo)串，T為模式串，且不妨設(shè)：S=“s0s1s2…sn-1”T=“t0t1…tm-1”

串匹配實(shí)際上是對(duì)于正當(dāng)位置0≦i≦n-m依次將目標(biāo)串中子串s[i..i+m-1]和模式串t[0..m-1]進(jìn)行比較，若s[i..i+m-1]=t[0..m-1]，第26頁(yè)則稱從位置i開始匹配成功，亦稱模式t在目標(biāo)s中出現(xiàn)；若s[i..i+m-1]≠t[0..m-1]，，則稱從位置i開始匹配失敗。上述位置i又稱為位移，當(dāng)s[i..i+m-1]=t[0..m-1]時(shí)，i稱為有效位移；當(dāng)s[i..i+m-1]≠t[0..m-1]時(shí)，i稱為無效位移。這么，串匹配問題可簡(jiǎn)化為是找出某給定模式T在一給定目標(biāo)S中首次出現(xiàn)有效位移。串匹配算法很多，這里我們只討論一個(gè)最簡(jiǎn)單稱為樸素串匹配算法。其基本思想是用一個(gè)循環(huán)來依次檢驗(yàn)n-m+1個(gè)正當(dāng)位移i(0≦i≦n-m)是否為有效位移第27頁(yè)intindex1(chars[],chart[],intstart){//返回在主串s第start個(gè)字符后子串t位置。若不存在，則函數(shù)值為-1。inti,j,m,n;m=strlen(s);n=strlen(t);if(start<0||n==0||start+n>m)return(-1);i=start;j=1;while(i<m&&j<n)if(s[i]=t[j]){i++;j++;}//相等,繼續(xù)比較后繼字符else{i=i-j+2;j=1;}//不等,指針i后退(至當(dāng)前匹配起始位置//下一位置）重新開始匹配if(j==n)return(i-n);//匹配成功，返回子串T位置elsereturn(-1);}例s=“ababcabcacbab”t=“abcac”start=1index1(s,t,start)返回值為6第28頁(yè)s=“aaaaaaaaaaaaaaaba”

t=“aaaaaaaba”4.3串模式匹配第29頁(yè)

匹配算法2一個(gè)改進(jìn)算法是由D.E.Knuth,J.H.Morris,andV.R.Pratt.基本思想abcdaba?\0sabc\0tdabcacbabctdab設(shè)t=“t0t1

tn是模式,函數(shù)next()定義以下:=<<==---1

}suchthat

0largest|{1...................