第4章(串).ppt

1、第4章 串,4.1 串類型的定義,4.2 串的表示和實(shí)現(xiàn) 1 定長順序存儲(chǔ)表示 2 堆分配存儲(chǔ)表示 3 串的塊鏈存儲(chǔ)表示,4.3 串的模式匹配算法,4.4 串操作應(yīng)用舉例,一、串和基本概念,4.1 串類型的定義,1、串(String),串是零個(gè)或多個(gè)字符組成的有限序列。一般記作S= a1a2a3an，其中S 是串名，單引號括起來的字符序列是串值；ai(1in)可以是字母、數(shù)字或其它字符；串中所包含的字符個(gè)數(shù)稱為串的長度。,長度為零的串稱為空串(NULL String)，它不包含任何字符。,注意：空串和空格串的不同，例如 和分別表示長度為1的空格串和長度為0的空串。,通常將僅由一個(gè)或多個(gè)空格組成

2、的串稱為空格串(Blank String)。,串中任意個(gè)連續(xù)字符組成的子序列稱為該串的子串，包含子串的串相應(yīng)地稱為主串。字符在序列中的位置序號為該字符在串中的位置。,一、串和基本概念,子串在主串中的位置：子串的第一個(gè)字符在主串中的位置，如果子串多次出現(xiàn)，則為第一次的位置。,例如，設(shè)a、b、c、d為如下的四個(gè)串： a=BEI ， b=JING， c=BEIJING， d=BEI JING,則它們的長度分別為3、4、7、8；并且a和b都是c和d的子串，a在c和d中的位置都是1，而b在 c的位置是4，在d中的位置則是5。,特別地，空串是任意串的子串,任意串是其自身的子串。,當(dāng)且僅當(dāng)兩個(gè)串的值相等，稱

3、兩個(gè)串是相等。也就是說，只有兩個(gè)串的長度相等，并且各對應(yīng)位置上的字符都相等時(shí)才相等。例如上例中的串a(chǎn)、b、c和d彼此都不是相等。,一、串和基本概念,一、串和基本概念,串的邏輯結(jié)構(gòu)和線性表極為相似，區(qū)別僅在于串的數(shù)據(jù)對象約束為字符集。然而，串的基本操作和線性表有很大差別。,在線性表中的基本操作中，大多數(shù)以“單個(gè)元素”作為操作對象。例如在線性表中查找某個(gè)元素、求取某個(gè)元素、在某個(gè)位置上插入一個(gè)元素和刪除一個(gè)元素等；,而在串的基本操作中，通常以“串的整體”作為操作對象，例如在串中查找某個(gè)子串、求取一個(gè)子串、在串的某個(gè)位置上插入一個(gè)子串以及刪除一個(gè)子串等。,ADT String ,D ai |aiCh

4、aracterSet,i=1,2,.,n, 0 ,數(shù)據(jù)關(guān)系：,R1 | ai-1, ai D, i=2,.,n ,二、串的抽象數(shù)據(jù)定義,基本操作:,1、StrAssign (,Index(S, T, 3) = 6;,Index(S, T, 8) = 0;,算法的基本思想為：,StrCompare(SubString(S, i, StrLength(T), T ),S 串,T 串,T 串,i,pos,n-m+1,? 0,例2、串的定位,算法的基本思想：在主串S中從第i（i的初值為pos）個(gè)字符起、取長度和串T相等的子串和T比較，若相等，則求得函數(shù)值為i，否則i的值增1直至S中不存在和串T相等的子

5、串為止。,int Index (String S, String T, int pos) / T為非空串。若主串S中第pos個(gè)字符之后存在與 T相等的子串， / 則返回第一個(gè)這樣的子串在S中的 位置，否則返回0,If (pos0) n = StrLength(S); m = StrLength(T); i = pos;,while ( i = n-m+1) ,SubString (sub, S, i, m);,return 0; / S中不存在與T相等的子串 / Index,if (StrCompare(sub，T) != 0) +i ;,else return i ; / while / i

6、f,StrInsert(,StrDelete(,思考：Replace( char s330,*p; int result;,（1）求串長(length) int strlen(char s); /求串的長度 例如：printf(“%d”,strlen(s1); 輸出13,（2）串復(fù)制(copy),char *strcpy(char to,char from);,三、串的基本操作,char s120=“dirtreeformat”,s220=“file.mem”; char s330,*p; int result;,該函數(shù)將串from復(fù)制到串to中，并且返回一個(gè)指向串to的開始處的指針。,例如：

7、strcpy(s3,s1); /s3=“dirtreeformat”,（3）聯(lián)接(concatenation),char s120=“dirtreeformat”,s220=“file.mem”; char s330,*p; int result;,三、串的基本操作,char strcat(char to,char from),該函數(shù)將串from復(fù)制到串to的末尾，并且返回一指向串to的開始處的指針。,例如：strcat(s3,”/”),strcat(s3,s2); /s3=“dirtreeformat/file.mem”,(4)串比較（compare),三、串的基本操作,char s120=

8、“dirtreeformat”,s220=“file.mem”; char s330,*p; int result;,int strcmp(chars1,char s2);,該函數(shù)比較串s1和串s2的大小，當(dāng)返回值小于0，等于0或大于0時(shí)，分別表示s1s2,例如：result=strcmp(“baker”,”bake”) result0,result=strcmp(“12”,”12”); result=0,result=strcmp(“Joe”, “Joseph”); result0,因?yàn)榇翘厥獾木€性表，故其存儲(chǔ)結(jié)構(gòu)與線性表的存儲(chǔ)結(jié)構(gòu)類似。只不過由于組成串的元素是單個(gè)字符。串有三種存儲(chǔ)表示方

9、法，下面分別介紹。,4.2 串的表示和實(shí)現(xiàn),4.2.1定長順序存儲(chǔ)表示,定長順序存儲(chǔ)表示：用一組地址連續(xù)的、長度固定的存儲(chǔ)單元存儲(chǔ)串中的字符序列。用定長數(shù)組來描述。,#define MAXSTRLEN 255 /用戶可在255以內(nèi)定義最大串長 typedef unsigned char SStringMAXSTRLEN+1; /0號單元存放串長,串的實(shí)際長度可在這預(yù)定義長度的范圍內(nèi)變化，超過預(yù)定義長度的值則被舍去，稱之為“截?cái)唷薄?對于串長有兩種辦法：,一是如上述定義描述的那樣以下標(biāo)為0的數(shù)組分量存放串的實(shí)際長度；,二是在串值后面加入一個(gè)不計(jì)入串長的結(jié)束標(biāo)記符，例如，C語言中以字符0表示串值的

10、終結(jié).串長為隱含值。,4.2.1定長順序存儲(chǔ)表示,串a(chǎn)bc 串長的兩種表示方法,1、串聯(lián)接Concat ( 結(jié)果？ Concat(T, S2 ,S1); 結(jié)果？,else T0.MAXSTRLEN=S10.MAXSTRLEN; uncut=FALSE; return uncut; ,Status Concat(SString ,else if(S10MAXSTRSIZE) T1.S10=S11.S10; TS10+1.MAXSTRLEN=S21.MAXSTRLEN-S10; T0=MAXSTRLEN;uncut=FALSE;,1、串聯(lián)接Concat (,Sub1.len=Spos.pos+le

11、n-1;, / SubString,Sub0=len return OK;,2、求子串SubString( /指向存放串的存儲(chǔ)區(qū),空串時(shí)ch為NULL int length;/串長度 HString; StrAssign (/pos不合法,If (T.length) /T非空，則重新分配空間，插入T,If(!(S.ch=(char*)realloc(S.ch,(S.length+T.length)*sizeof(char) exit (OVERFLOW);,S.chpos-1.posT.length-2=T.ch0.T.length-1; /插入T,for(i=S.length-1;i=pos

12、-1;-i)/為插入T而騰出位置 S.chi+T.length=S.chi;,2、堆分配存儲(chǔ)表示,在這種存儲(chǔ)結(jié)構(gòu)中，S.ch0存放字符,S.length+=T.length; Return OK; /StrInsert,只含最小操作子集的,按堆存儲(chǔ)表示的HString類型串的模塊說明見P7677。,2、堆分配存儲(chǔ)表示,以上兩種存儲(chǔ)表示通常為高級程序設(shè)計(jì)語言所采用,由于堆分配存儲(chǔ)結(jié)構(gòu)的串既有順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)，處理方便，操作中對串長沒有任何限制，更顯靈活，因此在串處理的應(yīng)用程序中也常被選用。,用鏈表方式存儲(chǔ)串值，由于串中的每個(gè)元素是一個(gè)字符，所以就有一個(gè)“結(jié)點(diǎn)大小”的問題，（1）每個(gè)結(jié)點(diǎn)可以存放

13、一個(gè)字符：“ABCDEFGHI” （2）也可以存放多個(gè)字符，當(dāng)結(jié)點(diǎn)大小大于1時(shí)，串長不一定是結(jié)點(diǎn)大小的整數(shù)倍，最后一個(gè)結(jié)點(diǎn)加上特殊符號。 如存放字符串“ABCDEFGHI”,可以用結(jié)點(diǎn)大小為1的鏈表存儲(chǔ)，也可以用結(jié)點(diǎn)大小為4的鏈表存儲(chǔ)，存儲(chǔ)示意圖見教材p78,圖4.2,3、串的鏈?zhǔn)剑▔K鏈）存儲(chǔ)表示,顯然，存儲(chǔ)密度?。ㄈ绻?jié)點(diǎn)大小為1時(shí)），運(yùn)算處理方便，然而，存儲(chǔ)占用量大。,在鏈?zhǔn)酱鎯?chǔ)方式中，節(jié)點(diǎn)大小的選擇直接影響著串處理的效率。在各種串的處理系統(tǒng)中，所處理的串往往很長或很多，串值的存儲(chǔ)密度是我們考慮的重要方面。存儲(chǔ)密度可定義為：,3、串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),串值的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)對某些操作，如對結(jié)點(diǎn)大小為

14、1時(shí)，串聯(lián)接、串插入、串刪除操作等有一定方便之處，但總的說來不如另外兩種存儲(chǔ)結(jié)構(gòu)靈活，它占用存儲(chǔ)量大且操作復(fù)雜。,3、串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),子串的定位操作，又叫模式匹配操作，是串的一種重要操作，很多軟件，都有“查找”功能。首先，回憶一下串匹配(查找、子串定位)的定義:,4.3串的模式匹配算法,INDEX (S, T, pos),初始條件：串 S 和 T 存在，T 是非空串， 1posStrLength(S)。,操作結(jié)果：若串T在主串S的第pos個(gè)字符之后出現(xiàn),則返回它在主串S中第pos個(gè)字符之后第一次出現(xiàn)的位置，否則函數(shù)值為0。,主串,模式串,在4.1中講過用其他操作實(shí)現(xiàn)的方法，也可以采用定長順序

15、存儲(chǔ)結(jié)構(gòu)寫出單獨(dú)的匹配算法。,1、簡單算法,模式匹配的最簡單的做法是：用模式串T中的字符依次與主串S的字符比較：,t1 t2 t3 tm,t1 t2 t3 tm,如此反復(fù)比較，直至主串S中找到模式串t，或者確定t不在s中為止。,S1 S2 S3 Sm Sn,如果t1=s1，t2=s2,，tm=sm則匹配成功。否則必有某個(gè)i(1im)，使得ti不等于si，這時(shí)可從主串s中與t1比較的字符的下一個(gè)字符起（將串t右移一個(gè)字符）再重新與模式串t中字符依次比較：,S1 S2 S3 Sm Sm+1 Sn,設(shè)S=“abbaba”，T=“aba”，用上述做法進(jìn)行模式匹配的過程見下圖：,S：a b b a b

16、a,S:a b b a b a,(a) T3 S3 3-3+2,S：a b b a b a,T： a b a,(b) T1 S2 2-1+2,(C)T1 S3 3-1+2,(d)找到模式串 6-3+1,T：a b a,S: a b b a b a(6),T: a b a,T: a b a,int Index(SString S, SString T, int pos) / 返回子串T在主串S中第pos個(gè)字符之后的位置。若不存在，則函數(shù)值為0。 其中，T非空，0posStrLength(S)。 i = pos; j = 1;,while (i = S0 +j; / 繼續(xù)比較后繼字符,else i = i-j+2; j = 1; / 指針后退重新開始匹配 ,if (j T0) return i-j+1; /或i-T0; else return 0; / Index,簡單算法,2、簡單模式算法分析,4.3.2模式匹配的一種改進(jìn)算法 看10天，比較注重技巧，為提高算法效率，如少一次循環(huán)，不惜增加難度，不提倡。,1、掌握串的相關(guān)概念 2、掌握串的存儲(chǔ)結(jié)構(gòu)及基本運(yùn)算的實(shí)現(xiàn) 3、熟練掌握簡單的模式匹配思想及匹配過程,第四章 學(xué)習(xí)要點(diǎn),第四章 作業(yè),一、選擇題 1、空