《數(shù)據(jù)結(jié)構(gòu)串》PPT課件.ppt

1、第四章 串,4.1 串的類型定義,4.2 串的表示和實現(xiàn),4.3 串的模式匹配算法,串(String)是零個或多個字符組成的有限序列。一般記作 S= “a1a2a3an”，其中 S 是串名，雙引號括起來的字符序列是串值；ai(1in) 可以是字母、數(shù)字或其它字符；串中所包含的字符個數(shù)稱為該串的長度。長度為零的串稱為 空串(Empty String)，它不包含任何字符。,4.1 串類型的定義 一、串的基本概念,注意：空串和空格串不同，如“ ”和“”分別表示長度為1的空格串和長度為0的空串（）。,特別地， 空串是任意串的子串，任意串是其自身的子串。,串中任意個連續(xù)字符組成的子序列稱為該串的子串，包

2、含子串的串相應(yīng)地稱為主串。通常將子串在主串中首次 出現(xiàn)時，該子串的首字符在主串中對應(yīng)的序號，定義為 子串在主串中的位置（或序號）。,例如：A = “This is a string ”，B = “is ” 則 B 是 A 的子串，A 為主串。B 在 A 中出現(xiàn)了兩次，其中首次出現(xiàn)所對應(yīng)的主串位置是 3 。因此，B 在 A 中的位置為 3 。,二、串的抽象數(shù)據(jù)類型定義如下：,ADT String ,數(shù)據(jù)對象：,D ai |aiCharacterSet, i=1,2,.,n, n0 ,數(shù)據(jù)關(guān)系：,R1 | ai-1, ai D, i=2,.,n ,基本操作：,StrAssign (,SubStri

3、ng( sub, commander , 1, 9),求得 sub = commander ,SubString(sub, commander, 4, 7) sub = ?,SubString(sub, beijing, 7, 2) = ? sub = ?,SubString(student, 5, 0) = ,起始位置和子串長度之間存在約束關(guān)系,長度為 0 的子串為“合法”串,1posStrLength(S) ，0lenStrLength(S)-pos+1。,Index (S, T, pos)初始條件：串S和T存在，T是非空串， 1posStrLength(S)。操作結(jié)果： 若主串 S 中存

4、在和串 T 值相同 的子串, 則返回它在主串 S 中 第pos個字符之后第一次出現(xiàn) 的位置;否則函數(shù)值為0。,假設(shè) S = abcaabcaaabc , T = bca ,Index(S, T, 1) = 2;,Index(S, T, 3) =？;,Index(S, T, 8) =？;,“子串在主串中的位置”意指子串 中的第一個字符在主串中的位序。,6,0,bca,bca,Replace ( / S中不存在與T相等的子串 / Index,n = StrLength(S); m = StrLength(T); i = pos;,while ( i = n-m+1) / while,SubStri

5、ng (sub, S, i, m); if (StrCompare(sub,T) != 0) +i ; else return i ;,又如串的置換函數(shù)：,S 串(n),T 串(m),V 串,V 串,pos,pos,sub,i,news 串,sub,= i+m,pos,=n-m+1,m,void replace(String / 剩余串 Concat( S, news, sub );,n=StrLength(S); m=StrLength(T); pos = 1; StrAssign(news, NullStr); i=1;,作業(yè),串的邏輯結(jié)構(gòu)和線性表極為相似，區(qū)別 僅在于串的數(shù)據(jù)對象約束為字

6、符集。,串的基本操作和線性表有很大差別。 在線性表的基本操作中，大多以“單個元素”作為操作對象； 在串的基本操作中，通常以“串的整體”作為操作對象。,在程序設(shè)計語言中，若串只是 作為輸入或輸出的常量出現(xiàn)，則只 需存儲此串的串值，即字符序列即 可。但在多數(shù)非數(shù)值處理的程序中， 串也以變量的形式出現(xiàn)。,4.2 串的表示和實現(xiàn),串有三種機內(nèi)表示方法：,一、串的定長順序存儲表示,二、串的堆分配存儲表示,三、串的塊鏈存儲表示,#define MAXSTRLEN 255 / 用戶可在255以內(nèi)定義最大串長 typedef unsigned char SString MAXSTRLEN + 1; / 0號單

7、元存放串的長度,一、串的定長順序存儲表示,用一組地址連續(xù)的存儲單元存儲串值的字符序列。,按這種串的表示方法實現(xiàn)的串的運算時，其基本操作為 “字符序列的復(fù)制”。,串的實際長度可在這個予定義長度的范圍內(nèi)隨意設(shè)定，超過予定義長度的串值則被舍去，稱之為“截斷” 。,特點:,Status Concat(SString S1, SString S2, SString / Concat,例1.串的聯(lián)接算法中需分三種情況處理：,T1.S10 = S11.S10; TS10+1.S10+S20 = S21.S20; T0 = S10+S20; uncut = TRUE; ,if (S10+S20 = MAXST

8、RLEN) / 未截斷,else if (S10 MAXSTRLEN) / s2截斷,s1未截斷,else / s1截斷(僅取S1),T1.S10 = S11.S10; TS10+1.MAXSTRLEN = S21.MAXSTRLENS10; T0 = MAXSTRLEN; uncut = FALSE; ,T1.MAXSTRLEN = S11.MAXSTRLEN; T0 = MAXSTRLEN uncut = FALSE; ,Status SubString(SString / 若是非空串，則按串實際長度分配 /存儲區(qū)，否則 ch 為NULL int length; / 串長度 HString

9、;,二、串的堆分配存儲表示,以一組地址連續(xù)的存儲單元存放串值字符序列，但它們的存儲空間是在程序執(zhí)行過程中動態(tài)分配而得。通常，C語言中提供的串類型就是以這種存儲方式實現(xiàn)的。系統(tǒng)利用函數(shù)malloc( ) 和 free( ) 進(jìn)行串值空間的動態(tài)管理，為每一個新產(chǎn)生的串分配一個存儲區(qū)，稱串值共享的存儲空間為“堆”。 C語言中的串以一個空字符為結(jié)束符，串長是一個隱含值。,這類串操作實現(xiàn)的算法為: 先為新生成的串分配一個存儲空間，然后 進(jìn)行串值的復(fù)制。,Status Concat(HString / Concat,Status SubString(HString / SubString, ,if(!(S

10、ub.ch = new charlen) return ERROR; Sub.ch0.len-1 = S.chpos-1.pos+len-2; Sub.length = len;,三、串的塊鏈存儲表示,可用鏈表來存儲串值，由于串的每個數(shù)據(jù)元素是一個字符，因此用鏈表存儲時，通常一個結(jié)點中存放的不是一個字符，而是一個子串。,為了提高存儲密度，可使每個結(jié)點存放多個字符。通常將結(jié)點數(shù)據(jù)域存放的字符個數(shù)定義為結(jié)點的大小，顯然，當(dāng)結(jié)點大小大于 1時，串的長度不一定正好是結(jié)點的整數(shù)倍，因此要用特殊字符(如#) ，來填充最后一個結(jié)點，以表示串的結(jié)束。,#define CHUNKSIZE 80 / 可由用戶定義

11、的塊大小 typedef struct Chunk / 結(jié)點結(jié)構(gòu) char chCUNKSIZE; struct Chunk *next; Chunk; typedef struct / 串的鏈表結(jié)構(gòu) Chunk *head, *tail; / 串的頭和尾指針 int curlen; / 串的當(dāng)前長度 LString;,例如: 在編輯系統(tǒng)中，整個文本編輯區(qū)可以看成是一個串，每一行是一個子串，構(gòu)成一個結(jié)點。即: 同一行的串用定長結(jié)構(gòu)(80個字符), 行和行之間用指針相聯(lián)接。,實際應(yīng)用時，可以根據(jù)問題所需來設(shè)置結(jié)點的大小。,這是串的一種重要操作，很多 軟件，若有“編輯”菜單項的話， 則其中必有“查

12、找”子菜單項。,4.3串的模式匹配算法,初始條件：串 S 和 T 存在，T 是非空串， 1posStrLength(S)。,首先，回憶一下查找(串匹配)操作的定義:,INDEX (S, T, pos),操作結(jié)果：若主串 S 中存在和串 T 值 相同的子串,則返回它在主串 S 中 第 pos 個字符之后第一次出現(xiàn) 的位置; 否則函數(shù)值為0。,int Index (String S, String T, int pos) / T為非空串。若主串S中第pos個字符之后存在與 T相等的子串，則返回第一個 這樣的子串在S中的 位置，否則返回0 if (pos 0) n = StrLength(S); m

13、 = StrLength(T); i = pos; while ( i = n-m+1) SubString (sub, S, i, m); if (StrCompare(sub,T) != 0) +i ; else return i ; / while / if return 0; / S中不存在與T相等的子串 / Index,下面討論以定長順序結(jié)構(gòu) 表示串時的幾種算法。,一、簡單算法,三、KMP算法( D.E.Knuth, J.H.Morris , V.R.Pratt ),二、首尾匹配算法,S 串,T 串,T 串,i,pos,S 串,T 串,T 串,i,j,jm (j=m+1),T 串,一

14、、簡單算法,j=1,i=i-j+2,返回？,匹配不成功！,:(i-m),int Index(SString S, SString T, int pos) / 返回子串T在主串S中第pos個字符之后的位置。若不存在，則函數(shù)值為0。 / 其中，T非空，1posStrLength(S)。 i = pos; j = 1; while (i T0) return i-T0; else return 0; / Index,先比較模式串的第一個字符， 再比較模式串的最后一個字符， 最后比較模式串中從第二個 到第 n-1 個字符。,二、首尾匹配算法,int Index_FL(SString S, SStrin

15、g T, int pos) sLength = S0; tLength = T0; i = pos; patStartChar = T1; patEndChar = TtLength; while (i = sLength tLength + 1) if (Si != patStartChar) +i; /重新查找匹配起始點 else if (Si+tLength-1 != patEndChar) +i; / 模式串的“尾字符”不匹配 else return 0; ,檢查中間字符的匹配情況,k = 1; j = 2; while ( j tLength / 重新開始下一次的匹配檢測,KMP算法

16、的時間復(fù)雜度可以達(dá)到O(m+n),三、KMP(D.E.Knuth, J.H.Morris, V.R.Pratt) 算法,每當(dāng)一趟匹配過程中出現(xiàn)字符比較不等時，不需回溯 i 指針，而是利用已經(jīng)得到的“部分匹配”的結(jié)果將模式串向右“滑動”盡可能遠(yuǎn)的一段距離后，繼續(xù)進(jìn)行比較。,當(dāng) Si Tj 時， 已經(jīng)得到的結(jié)果: Si-j+1.i-1 = T1.j-1 若已知 T1.k-1 = Tj-k+1.j-1 則有 Si-k+1.i-1 = T1.k-1,k j,主串：S1 Sn,子串：P1 Pm,i,i,j,j,定義：模式串的next函數(shù),0,1,1,2,2,3,1,2,int Index_KMP(SSt

17、ring S, SString T, int pos) / 1posStrLength(S) i = pos; j = 1; while (i T0) return i-T0; / 匹配成功 else return 0; / Index_KMP,這實際上也是一個匹配的過程， 不同在于：主串和模式串是同一個串.,求 next 函數(shù)值的過程是一個遞推過程， 分析如下:,已知：next1 = 0；,(1)若： Tj = Tk ,則： nextj+1 = k+1,(2)若： Tj Tk , 則 需往前回朔,假設(shè)：nextj = k;,0,1,1,2,2,3,1,?,如何求next6?,當(dāng)前j=5,next5=2, 考察 p5 與 p2 ：p5 = p2 ，所以next6=next5+1，,如何求next7?,當(dāng)前j=6,next6=3, 考察 p6 與 p3 ：p6 p3 ，next3=1，繼續(xù) 考察 p6 與 p1 ：p6 p1 ，next1=0，則 next7=1，從頭開始比較。,void get_next(SString / get_next,還有一種特殊情況需要考慮： 例如： S = aaabaaabaaabaaabaaab T = aaaab nextj= 01234,nextvalj= 00004 (調(diào)整后的next值),若 pj = pnext