第4章(串).ppt

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

2、的串稱為空格串(Blank String)。,串中任意個連續(xù)字符組成的子序列稱為該串的子串，包含子串的串相應地稱為主串。字符在序列中的位置序號為該字符在串中的位置。,一、串和基本概念,子串在主串中的位置：子串的第一個字符在主串中的位置，如果子串多次出現(xiàn)，則為第一次的位置。,例如，設a、b、c、d為如下的四個串： 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。,特別地，空串是任意串的子串,任意串是其自身的子串。,當且僅當兩個串的值相等，稱

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

4、aracterSet,i=1,2,.,n, 0 ,數(shù)據(jù)關系：,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）個字符起、取長度和串T相等的子串和T比較，若相等，則求得函數(shù)值為i，否則i的值增1直至S中不存在和串T相等的子

5、串為止。,int Index (String S, String T, int pos) / T為非空串。若主串S中第pos個字符之后存在與 T相等的子串， / 則返回第一個這樣的子串在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）串復制(copy),char *strcpy(char to,char from);,三、串的基本操作,char s120=“dirtreeformat”,s220=“file.mem”; char s330,*p; int result;,該函數(shù)將串from復制到串to中，并且返回一個指向串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復制到串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的大小，當返回值小于0，等于0或大于0時，分別表示s1s2,例如：result=strcmp(“baker”,”bake”) result0,result=strcmp(“12”,”12”); result=0,result=strcmp(“Joe”, “Joseph”); result0,因為串是特殊的線性表，故其存儲結構與線性表的存儲結構類似。只不過由于組成串的元素是單個字符。串有三種存儲表示方

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

10、終結.串長為隱含值。,4.2.1定長順序存儲表示,串a(chǎn)bc 串長的兩種表示方法,1、串聯(lián)接Concat ( 結果？ Concat(T, S2 ,S1); 結果？,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( /指向存放串的存儲區(qū),空串時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、堆分配存儲表示,在這種存儲結構中，S.ch0存放字符,S.length+=T.length; Return OK; /StrInsert,只含最小操作子集的,按堆存儲表示的HString類型串的模塊說明見P7677。,2、堆分配存儲表示,以上兩種存儲表示通常為高級程序設計語言所采用,由于堆分配存儲結構的串既有順序存儲結構的特點，處理方便，操作中對串長沒有任何限制，更顯靈活，因此在串處理的應用程序中也常被選用。,用鏈表方式存儲串值，由于串中的每個元素是一個字符，所以就有一個“結點大小”的問題，（1）每個結點可以存放

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

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

15、存儲結構寫出單獨的匹配算法。,1、簡單算法,模式匹配的最簡單的做法是：用模式串T中的字符依次與主串S的字符比較：,t1 t2 t3 tm,t1 t2 t3 tm,如此反復比較，直至主串S中找到模式串t，或者確定t不在s中為止。,S1 S2 S3 Sm Sn,如果t1=s1，t2=s2,，tm=sm則匹配成功。否則必有某個i(1im)，使得ti不等于si，這時可從主串s中與t1比較的字符的下一個字符起（將串t右移一個字符）再重新與模式串t中字符依次比較：,S1 S2 S3 Sm Sm+1 Sn,設S=“abbaba”，T=“aba”，用上述做法進行模式匹配的過程見下圖：,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個字符之后的位置。若不存在，則函數(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模式匹配的一種改進算法 看10天，比較注重技巧，為提高算法效率，如少一次循環(huán)，不惜增加難度，不提倡。,1、掌握串的相關概念 2、掌握串的存儲結構及基本運算的實現(xiàn) 3、熟練掌握簡單的模式匹配思想及匹配過程,第四章 學習要點,第四章 作業(yè),一、選擇題 1、空