數(shù)據(jù)結(jié)構(gòu)與算法 課件 第4章 串

第4章串串（又稱字符串）是一種特殊的線性表，它的每個元素僅由一個字符組成。在文字編輯中的查找和替換，匯編和編譯程序中的詞法掃描，事務(wù)處理程序中的文本類型字段的處理等方面都是串的應(yīng)用。1【本章重點】①串的定義和串的基本運算；②串的順序和鏈式存儲結(jié)構(gòu)及基本運算的實現(xiàn)；③簡單的模式匹配算法。2【本章難點】①改進的模式匹配算法；②串的應(yīng)用。3【本章內(nèi)容】串的概念及基本運算串的順序存儲結(jié)構(gòu)及基本運算的實現(xiàn)串的模式匹配算法習題444.1串的概念及基本運算串的定義：串是由多個或零個字符組成的有限序列，記作S="c1c2c3…cn"(n≥0)。其中，S是串名，由雙引號括起來的字符序列稱為串值。說明：（1）ci（1≤i≤n）是串中字符，i是字符在串中的位置序號；n是串的長度，表示串中字符的個數(shù)，不包含任何字符的串稱為空串，例如""是長度為0的空串。5（2）串中任意個連續(xù)的字符組成的子序列稱為該串的子串，包含子串的串相應(yīng)的稱為主串。子串在主串中的序號定義為子串在主串中首次出現(xiàn)的位置序號。例如，設(shè)S1和S2分別為： S1="Thisisastring"S2="is"則S2是S1的子串，S1是S2的主串。S2在S1中出現(xiàn)了兩次，首次出現(xiàn)在主串的第3個位置上，因此S2在S1中的序號是3。（3）串可以分為串變量和串常量。例如使用C語言可以有如下定義：charstr[]="string";constcharstr_const[]="string";str是串變量，而str_const是串符號常量。（4）只含有空格的串稱為空格串，例如"凵凵凵"是空格串，長度為36串的常用基本運算（1）StrLength(S)求串長。計算并返回串的長度。（2）StrCopy(S1,S2)串賦值。將S2賦給S1。S1是串變量，S2是串常量或者是串變量。（3）StrCat(S1,S2)串連接。將S2連接在S1的后面。S1是串變量，S2是串常量或者是串變量。例如，S1="ABCD"，S2="1234"，StrCat(S1,S2)運算的結(jié)果是S1="ABCD1234"，而S2="1234"。（4）StrCmp(S1,S2)串比較。若S1=S2，則結(jié)果為0；若S1>S2，則運算結(jié)果大于0；若S1<S2，則結(jié)果小于0。兩個串的比較，實際上比較的是字符的ASCII碼值。從第一個位置上的字符開始逐個字符進行比較，當?shù)谝淮纬霈F(xiàn)字符不等的情況，即可得到比較的結(jié)果。例如"abcd"等于"abcd"，"abc"大于"aBc"，"abc"小于"abcd"。7（5）StrIndex(S,T)子串定位。若串T是串S的子串，則結(jié)果為T在S中首次出現(xiàn)的位置，否則運算結(jié)果為0。例如StrIndex("DataStructures","ruct")的結(jié)果為8。（6）SubStr(Sub,S,i,len)求子串。串S非空，且1≤i≤StrLength(S)，0≤len≤StrLength(S)，運算結(jié)果是得到S串從第i個字符開始的長度為len的子串，并將其賦給T。如果len為0，則賦給Sub的是空串。例如SubStr(Sub,"student",4,3)的結(jié)果是Sub="den"。（7）StrInsert(S,i,T)串插入。串S和T均為非空串，且1≤i≤StrLength(S)+1。結(jié)果是將串T插入到串S的第i個字符位置上，串S的值被改變。例如S="Youareastudent"，T="rteacher"，StrInsert(s,4,t)的運算結(jié)果是S="Yourteacherareastudent"。（8）StrDelete(S,i,len)串刪除。串S非空，且1≤i≤StrLength(S)，0≤len≤StrLength(S)，運算結(jié)果是刪除S串中從第i個字符開始的長度為len的子串，串S的值被改變。8（9）StrRep(S,T,R)串替換。串S、T、R均非空，運算結(jié)果是用串R替換串S中所有子串T，串S的值被改變。以上是串的基本運算，其中前5個運算是最基本的，而其余的串運算一般可以由這些最基本的串運算組合而成。94.2

串的順序存儲結(jié)構(gòu)及基本運算的實現(xiàn)1、串的順序存儲結(jié)構(gòu)串的順序存儲結(jié)構(gòu)即順序串，順序串用一組地址連續(xù)的存儲單元（一維字符數(shù)組）存儲串值的字符序列，其中每個結(jié)點是單個字符。串的定長順序存儲

直接使用定長的字符數(shù)組來定義，數(shù)組的上界預(yù)先給出。一般有三種方法表示串的長度：（1）用一個整型變量來表示串的長度。順序串的類型定義和順序表類似，其定義如下：#defineMAXSIZE256typedefstruct{charch[MAXSIZE];intlength;}SeqString;SeqStrings; //s為結(jié)構(gòu)體變量順序串的長度表示為s.length10（2）在串的末尾設(shè)置串結(jié)束符，例如C語言用轉(zhuǎn)義字符'\0'作為串結(jié)束符。這種方式不能直接得到串的長度，而是通過判斷當前字符是否為'\0'來確定串是否結(jié)束，從而求得串的長度。順序串的定義如下：#defineMAXSIZE256typedefcharsstring[MAXSIZE];sstrings;//s是一個可容納255個字符的順序串。這就是為什么在上述定義中，串空間最大值maxstrlen為256，但最多只能存放255個字符的原因，因為必須留一個字節(jié)來存放'\0'字符作為串結(jié)束符。11注意：串中字符的位序從1開始，字符數(shù)組從下標0開始存放字符串（3）順序串存儲空間：chars[MAXSIZE+1];用s[0]存放串的實際長度，而串值存放在s[1]~s[MAXSIZE]中。優(yōu)點：字符的序號與存儲位置的下標一致12串的實際長度在后面的算法中，順序串采用第2種存儲方式，即從數(shù)組下標0開始存放字符，并且在串尾存儲串結(jié)束符'\0'。1、求串長13順序串基本運算的實現(xiàn)算法4.1 求順序串的長度，即統(tǒng)計串中字符的個數(shù)。intStrLength(char*s){ i=0; while(s[i]!='\0') i++; returni;}2、串賦值（串復(fù)制）14算法4.2 將串s2復(fù)制給串s1。voidStrCopy(char*s1,char*s2){ i=0; while(s2[i]!='\0') { s1[i]=s2[i]; i++; } //逐個字符賦值 s1[i]='\0'; //置串結(jié)束標志}3、串比較15算法4.3 比較兩個串s1和s2的大小。若s1>s2，返回值大于0；若s1=s2，返回值等于0；若s1<s2，返回值小于0。intStrCmp(char*s1,char*s2){ i=0; while(s1[i]==s2[i]&&s1[i]!='\0')//兩個串對應(yīng)位置上的字符進行比較 i++; returns1[i]-s2[i];}4、串連接16算法4.4 將兩個串s1和s2首尾連接成一個新的串s1。intStrCat(char*s1,char*s2){ len1=StrLength(s1); len2=StrLength(s2); if(len1+len2>MAXSIZE-1) return0; //串s1的存儲空間不夠，返回錯誤代碼0 i=0;j=0; while(s1[i]!='\0') //找到串s1的串尾 i++; while(s2[j]!='\0') //將串s2的串值復(fù)制到串s1的串尾 s1[i++]=s2[j++]; s1[i]='\0'; //置串s1結(jié)束標志 return1; //連接成功，返回代碼1}復(fù)習：常用的C語言字符串處理庫函數(shù)。教材P79【例4.1】利用C語言的庫函數(shù)完成取子串運算。取主串s中pos起始的len個字符作為子串sub。例如，主串s=“d:\\user\\wang\\”，pos=8，len=5，sub=“\\wang”17voidSubStr(char*sub,char*s,intpos,intlen){ if(pos<1||pos>strlen(s)||len<0)printf("parametererror!\n"); else{ strncpy(sub,s+pos-1,len);//復(fù)制子串字符

strcpy(sub+len,"\0");//添加子串的串結(jié)束符 }}4.4串的模式匹配算法子串定位又稱為串的模式匹配。設(shè)主串稱為目標串，子串稱為模式串，所謂模式匹配，就是在目標串中查找模式串的出現(xiàn)位置，例如在文本中查找是否存在給定的單詞及出現(xiàn)的位置。簡單的模式匹配算法（樸素的模式匹配算法，BF算法）

假設(shè)T為目標串（主串），P為模式串（子串）。

T="t1,t2,…,tn"P="p1,p2,…,pm"其中0＜m≤n1819算法4.5順序串簡單的模式匹配。intIndex(seqstring*T,seqstring*P,intpos)//順序串的樸素模式匹配，串的位序從1開始{i=pos;j=1;//目標串從第pos個字符開始與模式串的第一個字符開始進行比較while(i<=T->length&&j<=P->length)if(T->ch[i-1]==P->ch[j-1])//串從數(shù)組的0元素開始存放{i++;j++;}//繼續(xù)比較后面的字符else{i=i-j+2;j=1;}//本趟不匹配，設(shè)置下一趟匹配的起始位序if(j>P->length)return(i-P->length);//匹配成功elsereturn(0);//匹配不成功}算法的基本思想是：從目標串T的第pos個字符開始與模式串P的第一個字符進行比較，若相等，則繼續(xù)比較后面的字符；否則從目標串的下一個字符開始與模式串的第一個字符進行下一趟比較。重復(fù)此過程，直至模式串中的每個字