第四章 字符串

1、 第四章第四章 串串4.1 4.1 串類型的定義串類型的定義 4.2 4.2 串的表示和實現(xiàn)串的表示和實現(xiàn)4.3 4.3 應用舉例應用舉例教學目的：教學目的： （1）了解串的定義； （2）理解和領(lǐng)會串的存儲方式； （3）掌握常用的串運算。教學重點：教學重點： （1）串的基本概念、基本運算； （2）串的兩種存儲方式。 （3）串的模式匹配算法。教學難點：教學難點： （1）串的模式匹配算法； （2）串的基本運算的綜合應用學時安排：學時安排： 4學時（其中實驗2學時） 串的邏輯結(jié)構(gòu)和線性表極為相似，區(qū)別僅在于串的數(shù)據(jù)對象約束為字符集。然而，串的基本操作和線性表有很大差別。在線性表的基本操作中，大多以“

2、單個元素”作為操作對象，如：在線性表中查找某個元素、求取某個元素、在某個位置上插入一個元素和刪除一個元素等；而在串的基本操作中，通常以“串的整體”作為操作對象，如：在串中查找某個子串、求取一個子串、在串的某個位置上插入一個子串以及刪除一個子串等。4.1 4.1 串類型的定義串類型的定義 串串是字符串的簡稱。它是一種在數(shù)據(jù)元素的組成上具有一定約束條件的線性表，即要求組成線性表的所有數(shù)據(jù)元素都是字符，所以，人們經(jīng)常又這樣定義串：串是一個有窮字符序列。串一般記作： s= “a1a2.an” (n0) 其中，s是串的名稱，用雙引號（“”）括起來的字符序列是串的值；ai可以是字母、數(shù)字或其他字符；串中字

3、符的數(shù)目n被稱作串的長度。 當n=0時，串中沒有任何字符，其串的長度為0，通常被稱為空串空串。 s1= “”s2= “ ” s1中沒有字符，是一個空串；而s2中有兩個空格字符，它的長度等于2，它是由空格字符組成的串，一般稱此為空格串空格串。 子串、主串子串、主串：串中任意連續(xù)的字符組成的子序列被稱為該串的子串。包含子串的串又被稱為該子串的主串。例如，有下列四個串a(chǎn)，b，c，d： a= “Welcome to Beijing” b= “Welcome” c= “Bei” d= “welcome to” b，c，d都是a的子串。 子串的位置子串的位置：子串在主串中第一次出現(xiàn)的第一個字符的位置。 兩

4、個串相等兩個串相等：兩個串的長度相等，并且各個對應的字符也都相同。 例如，有下列四個串a(chǎn)，b，c，d： a= “program” b= “Program” c= “pro” d= “program ”相等不等 對于串的基本操作集可以有不同的定義方法，讀者在使用高級程序設計語言中的串類型時，應以該語言的參考手冊為準。在上述抽象數(shù)據(jù)類型定義的13種操作中：1、串賦值StrAssign2、串復制Strcopy3、串比較StrCompare4、求串長StrLength5、串聯(lián)接Concat6、求子串SubString 這六種操作構(gòu)成串類型的最小操作子集。即：這些操作不可能利用其他串操作來實現(xiàn)，反之，其

5、他串操作（除串清除ClearString和串銷毀DestroyString外）可在這個最小操作子集上實現(xiàn)。int Index (String S, String T, int pos) if (pos 0) n = StrLength(S); m = StrLength(T); i = pos; while ( i = n-m+1) SubString (sub, S, i, m); if (StrCompare(sub,T) != 0) +i ; else return i ; / while / ifreturn 0; / Index例如，可利用判等、求串長和求子串等操作實現(xiàn)定位函數(shù)Ind

6、ex(S,T,pos)。 算法的基本思想為：在主串S中取從第i ( i的初值為pos)個字符起、長度和串T相等的子串和串T比較，若相等，則求得函數(shù)值為i，否則i值增1直至串S中不存在和串T相等的子串為止。4.2 4.2 串的表示和實現(xiàn)串的表示和實現(xiàn) 如果在程序設計語言中，串只是作為輸入或輸出的常量出現(xiàn)，則只需存儲此串的串值，即字符序列即可。但在多數(shù)非數(shù)值處理的程序中，串也以變量的形式出現(xiàn)。串有3種機內(nèi)表示方法。一、串的定長順序存儲表示一、串的定長順序存儲表示 #define MAXSTRLEN 255 / 用戶可在255以內(nèi)定義最大串長 typedef unsigned char SStrin

7、gMAXSTRLEN + 1; /同C語言,最后一個單元中存字符串結(jié)束符 串的實際長度可在這個予定義長度的范圍內(nèi)隨意設定，超過予定義長度的串值則被舍去，稱之為“截斷” 。按這種串的表示方法實現(xiàn)的串的運算時，其基本操作為“字符序列的復制”。1、串的聯(lián)接concat（&t，s1，s2）void concat(sstring &T,sstring S1,sstring S2) int i,n,m; n=strlen(S1);m=strlen(S2); if(n+m=255) strcpy(T,S1); for(i=0;im;i+) Tn+i=S2i; Tn+m=0; else if(n255) st

8、rcpy(T,S1); for(i=0;i0&i0&m=n-i+1) for(j=i-1;j0&pos=strlen(S) n=strlen(S);m=strlen(T);i=pos;while(i=n-m+1) substring(sub,S,i,m); if(strcmp(sub,T)=0)return i; i+;return 0; 二、串的堆分配存儲表示二、串的堆分配存儲表示 基本思想：“按需分配”。 當字符串有效內(nèi)容的長度發(fā)生變化，原來的空間就會釋放掉，同時重新開辟一個和新內(nèi)容長度一樣的字符數(shù)組來存儲新的字符串。 typedef structchar *ch; / 若是非空串，則按串

9、長分配存儲區(qū)，否 則ch為NULLint length; / 串長度HString; 通常，C語言中提供的串類型就是以這種存儲方式實現(xiàn)的。系統(tǒng)利用函數(shù)malloc( )和free( )進行串值空間的動態(tài)管理，為每一個新產(chǎn)生的串分配一個存儲區(qū)，稱串值共享的存儲空間為“堆”。C語言中的串以一個空字符為結(jié)束符，串長是一個隱含值。1 1、插入、插入void StrInsert(hstring &S1,int i,hstring S2) int j,n; n=S1.length+S2.length; if(iS1.length+1) exit(-2); if(S2.length)S1.ch=(char

10、*)realloc(S1.ch,n*sizeof(char); if(!S1.ch) exit(-2); for(j=S1.length-1;j=i-1;j-) S1.chj+S2.length=S1.chj; for(j=0;jS2.length;j+) S1.chi-1+j=S2.chj;S1.length=S1.length+S2.length;2 2、復制、復制void concpy(hstring &S1,hstring S2) int i; /*if(S1.ch) free(S1.ch);*/ S1.ch=(char *)malloc(S2.length*sizeof(char);

11、 if(!S1.ch ) exit(-2); S1.length=S2.length; for(i=0;iS2.length;i+) S1.chi=S2.chi; 3 3、字符串比較、字符串比較int concmp(hstring S1,hstring S2)int i;for(i=0;iS1.length&iS2.length;i+) if(S1.chi!=S2.chi) return S1.chi-S2.chi;return S1.length-S2.length;4 4、連接、連接void concat(hstring &T,hstring S1,hstring S2) int i; i

12、f(T.ch) free(T.ch); T.ch=(char *)malloc(S1.length+S2.length)*sizeof(char); T.length=S1.length+S2.length; for(i=0;iS1.length;i+) T.chi=S1.chi; for(i=0;i0&i0&m=S.length-i+1) if(sub.ch) free(sub.ch);sub.ch=(char *)malloc(m*sizeof(char);sub.length=m;for(j=i-1;ji+m-1;j+) sub.chj-i+1=S.chj; 三、串的塊鏈存儲表示三、串的

13、塊鏈存儲表示 由于串結(jié)構(gòu)中每個數(shù)據(jù)元素為一個字符，所以最直接的鏈式存儲結(jié)構(gòu)是每個結(jié)點的數(shù)據(jù)域存放一個字符。 優(yōu)點是操作方便；不足之處是存儲密度較低。所謂存儲密度為：存儲密度= 若要將多個字符存放在一個結(jié)點中，就可以緩解這個問題。串值所占的存儲單元實際分配的存儲單元string head 由于串中的字符個數(shù)不一定是每個結(jié)點存放字符個數(shù)的整倍數(shù)，所以，需要在最后一個結(jié)點的空缺位置上填充特殊的字符。 這種存儲形式優(yōu)點是存儲密度高于結(jié)點大小為1 的存儲形式；不足之處是做插入、刪除字符的操作時，可能會引起結(jié)點之間字符的移動，算法實現(xiàn)起來比較復雜。s t r in g head上機實驗作業(yè)：上機實驗作業(yè)：已知一個由字母組成的長度為n的字符串，其存儲結(jié)構(gòu)為帶頭結(jié)點的單鏈表，頭指針為L，結(jié)點的數(shù)據(jù)類型為：（1）設計一個刪除函數(shù)void DeleteX(linklsi