第四章 字符串

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

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

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

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

5、他串操作（除串清除ClearString和串銷毀DestroyString外）可在這個(gè)最小操作子集上實(shí)現(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例如，可利用判等、求串長(zhǎng)和求子串等操作實(shí)現(xiàn)定位函數(shù)Ind

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

7、gMAXSTRLEN + 1; /同C語(yǔ)言,最后一個(gè)單元中存字符串結(jié)束符 串的實(shí)際長(zhǎng)度可在這個(gè)予定義長(zhǎng)度的范圍內(nèi)隨意設(shè)定，超過(guò)予定義長(zhǎng)度的串值則被舍去，稱之為“截?cái)唷?。按這種串的表示方法實(shí)現(xiàn)的串的運(yùn)算時(shí)，其基本操作為“字符序列的復(fù)制”。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; 二、串的堆分配存儲(chǔ)表示二、串的堆分配存儲(chǔ)表示 基本思想：“按需分配”。 當(dāng)字符串有效內(nèi)容的長(zhǎng)度發(fā)生變化，原來(lái)的空間就會(huì)釋放掉，同時(shí)重新開(kāi)辟一個(gè)和新內(nèi)容長(zhǎng)度一樣的字符數(shù)組來(lái)存儲(chǔ)新的字符串。 typedef structchar *ch; / 若是非空串，則按串

9、長(zhǎng)分配存儲(chǔ)區(qū)，否 則ch為NULLint length; / 串長(zhǎng)度HString; 通常，C語(yǔ)言中提供的串類型就是以這種存儲(chǔ)方式實(shí)現(xiàn)的。系統(tǒng)利用函數(shù)malloc( )和free( )進(jìn)行串值空間的動(dòng)態(tài)管理，為每一個(gè)新產(chǎn)生的串分配一個(gè)存儲(chǔ)區(qū)，稱串值共享的存儲(chǔ)空間為“堆”。C語(yǔ)言中的串以一個(gè)空字符為結(jié)束符，串長(zhǎng)是一個(gè)隱含值。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、復(fù)制、復(fù)制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; 三、串的塊鏈存儲(chǔ)表示三、串的

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