數(shù)據(jù)結(jié)構(gòu)——串學(xué)生講解反轉(zhuǎn)課堂PPT課件

1、目錄content03040201串及其運算串的存儲結(jié)構(gòu)及實現(xiàn)串的模式匹配實例分析第1頁/共45頁串的應(yīng)用程序設(shè)計中的源程序、目標(biāo)程序事物處理程序中，顧客姓名、地址、貨物的產(chǎn)地、名稱軟件系統(tǒng)方面的字符編輯、情報檢索、詞法分析等多入侵檢測系統(tǒng) DNA序列檢測 第2頁/共45頁串的定義 由零個或多個字符組成的有限序列，一般記作：S=a1a2a3an(1) S為串的名字(2) 單引號括起來的字符序列為串的值將串值括起來的單引號本身不屬于串，它的作用是避免串與常數(shù)或與標(biāo)識符混淆123 123La La(3) ai(1in)可以是字母、數(shù)字或其他字符(4) n為串中字符的個數(shù)，稱為串的長度特殊的線性表，

2、數(shù)據(jù)元素限制為字符集第3頁/共45頁(1)空串(2)空白串(3)子串(4)主串 (7)位置(8)相等串(5)前綴子串、真前綴子串(6)后綴子串、真后綴子串(9)模式匹配長度為0的串，不包含任何字符僅由一個或多個空格組成的串，長度1是長度為0的空串 長度為1的空白串串中任意個連續(xù)字符組成的子序列包含子串的串空串 ？ 自身 ？B=datastructureA=dataC=data structure字符在串中的序號 子串在主串中的位置？兩個串的長度相等 每個對應(yīng)位置字符相等子串從主串的某一位置開始，其在主串中首次出現(xiàn)的位置ddadatadatadataatataD=structure主串：A=ab

3、caabcaaabc 子串：B=bca 子串B在主串中，從第1個位置開始的位置是：子串B在主串中，從第2個位置開始的位置是：26第4頁/共45頁串的基本運算串的抽象數(shù)據(jù)類型定義：ADT String數(shù)據(jù)對象：數(shù)據(jù)關(guān)系：基本操作：ADT StringD=ai|aiCharacterSet，i=1,2,n,n0R=| ai-1,aiD ，i=2,3,nStrAssign(S,chars) StrCopy(S,T) StrLength(S) StrInsert(S,pos,T) StrDelete(S,pos,len) StrCompare(S,T) StrCat(S,T) SubString(T,

4、S,pos,len)StrIndex(S,pos,T) StrReplace(S,T,V) StrEmpty(S) StrClear(S) StrDestory(S) 這些串的基本操作通常以“串的整體”“串的一部分”作為操作對象第5頁/共45頁串的基本運算 對于以上串的基本操作，C語言的函數(shù)庫文件 string.h 包括其中幾個字符串操作函數(shù)：gets(S) 輸入字符串puts(S) 輸出字符串strcat(S1,S2) 連接字符串S2至S1后strcmp(S1,S2) 比較字符串S1和S2strcpy(S1,S2) 復(fù)制字符串S2至S1strlen(S) 求字符串S的有效長度第6頁/共45頁

5、串的基本運算StrInsert(S,pos,T)例:S=chater,T=rac,運行StrInsert(S,4,T)在字符串S的第pos個字符之前插入字符串T串S和串T存在，1posStrLength(S)+1操作結(jié)果：初始條件：結(jié)果： S=character第7頁/共45頁串的基本運算StrDelete(S,pos,len)例:S=chapter, 運行StrDelete(S,5,3)從串S中刪除從第pos個字符開始連續(xù)len個字符后形成的子串串S存在，1posStrLength(S)-len+1操作結(jié)果：初始條件：結(jié)果： S=chap第8頁/共45頁串的基本運算StrCat(S,T)例:

6、S=man,運行StrCat(S, kind)將字符串T的值連接在串S的后面串S和串T存在操作結(jié)果：初始條件：結(jié)果： S=mankind第9頁/共45頁串的基本運算SubString(T,S,pos,len)例:S=commander,運行SubString(T1,S,4,3)截取字符串S中從第pos個字符開始連續(xù)len個字符形成的子串，并賦值給串T串S存在，1posStrLength(S)且0lenStrLength(S)-pos+1操作結(jié)果：初始條件：結(jié)果： T1=man運行SubString(T2,S,5,0)運行SubString(T3,S,4,7)結(jié)果： T2=結(jié)果 T3無結(jié)果，函數(shù)

7、返回錯誤第10頁/共45頁串的基本運算StrIndex(S,pos,T)例:S=abcaabcaaabc,T=bca,運行StrInsert(S,1,T)若字符串S從第pos個字符后存在與字符串T相等的子串，則返回字符串T在串S中第pos個字符后首次出現(xiàn)的位置，否則返回0串S和串T存在，1posStrLength(S)操作結(jié)果：初始條件：結(jié)果： 2運行StrInsert(S,4,T)結(jié)果： 6第11頁/共45頁串的基本運算StrReplace(S,T,V)例:S=abcaabcaaabca,T=bca,若V=x運行StrReplace(S,T,V)用字符串V替換字符串S中出現(xiàn)的所有與串T相等的

8、不重疊的子串串S和串V存在，且串T為非空串操作結(jié)果：初始條件：結(jié)果： S=axaxaax若V=bc運行StrReplace(S,T,V)結(jié)果： S=abcabcaabc第12頁/共45頁串的存儲結(jié)構(gòu)及實現(xiàn)1.定長順序串2.堆串3.塊鏈串 與線性表的順序存儲結(jié)構(gòu)類似，使用一組地址連續(xù)的與線性表的順序存儲結(jié)構(gòu)類似，使用一組地址連續(xù)的存儲單元存儲串的字符序列，也稱為存儲單元存儲串的字符序列，也稱為靜態(tài)存儲分配靜態(tài)存儲分配的順的順序串。直接使用序串。直接使用定長的字符數(shù)組定長的字符數(shù)組來定義。來定義。 與定長順序串類似，都是用一組地址連續(xù)的存儲單元與定長順序串類似，都是用一組地址連續(xù)的存儲單元存儲串的

9、字符序列，存儲串的字符序列，不同不同的是：其存儲空間是的是：其存儲空間是動態(tài)分配動態(tài)分配的的 采用采用鏈?zhǔn)芥準(zhǔn)酱鎯Y(jié)構(gòu)，鏈表的每個節(jié)點可存放一個或多存儲結(jié)構(gòu)，鏈表的每個節(jié)點可存放一個或多個字符，每個節(jié)點稱為個字符，每個節(jié)點稱為塊塊第13頁/共45頁串的存儲結(jié)構(gòu)及實現(xiàn)定長順序串#define MAXLEN 50typedef struct char chMAXLEN+1 ; char chMAXLEN+1 ; int len ; int len ; SString; SString;存儲結(jié)構(gòu)截斷 串的實際長度在預(yù)定義長度MAXLEN的范圍內(nèi)隨意變動時，超過MAXLEN，串值被舍去的情況字符串長度

10、 0 或者 len ，此時0號單元格不用第14頁/共45頁串的存儲結(jié)構(gòu)及實現(xiàn)定長順序串串插入函數(shù)Case 1 插入后串長MAXLEN 在進(jìn)行串的插入時，插入位置pos將位置分為兩部分，記為A、B,長度分別為LA、LB，記插入部分為T,長度為LTCase 2 插入后串長MAXLEN，且pos+LTMAXLENCase 3 插入后串長MAXLEN，且pos+LTMAXLEN第15頁/共45頁串的存儲結(jié)構(gòu)及實現(xiàn)定長順序串串插入函數(shù)int SStrInsrt (SString * S , int pos , const SString T ) int i ; if(NULL=S|NULL=S-ch|N

11、ULL=T.ch|pos S-len+1) return 0 ;return 1;if(S-len+T.lenlen+T.len ; i pos+T.len ; i - - ) S-chi=S-chi-T.len; for(i=pos ; i chi=T.chi-pos+1; S-len=S-len+T.len; else if(pos+T.lenMAXLEN; i pos+T.len;i - ) S-chi=S-chi-T.len; for(i = pos; i chi=T.chi-pos+1; S-len=MAXLEN; else for(i=pos; ichi=T.chi-pos+1;

12、S-len=MAXLEN; #define MAXLEN 50typedef struct char chMAXLEN+1 ; char chMAXLEN+1 ; int len ; int len ; SString; SString;第16頁/共45頁串的存儲結(jié)構(gòu)及實現(xiàn)定長順序串串刪除函數(shù)int SStrDelete (SString * S , int pos , int len ) int i = 1 ; if( NULL=S | NULL=S-ch | len 0 | pos S-len-len+1) return 0 ; return 1;for( i=pos;ilen-len;i

13、+) S-chi=S-chi+len;S-len=S-len-len;#define MAXLEN 50typedef struct char chMAXLEN+1 ; char chMAXLEN+1 ; int len ; int len ; SString; SString;第17頁/共45頁串的存儲結(jié)構(gòu)及實現(xiàn)定長順序串串連接函數(shù)Case 1 連接后串長MAXLEN 在進(jìn)行串的連接時，假設(shè)原始串為S,長度為LS，待連接串為T,長度為LTCase 2 連接后串長MAXLEN，且LAch|NULL=T.ch) return 0 ; else return 0;if(S-len+T.lenlen

14、+1;ilen+T.len;i+) S-chi=T.chi-S-len; S-len=S-len+T.len; return 1 ; else if(S-lenlen+1;ichi=S-chi-S-len; S-len=MAXLEN; return 0 ; #define MAXLEN 50typedef struct char chMAXLEN+1 ; char chMAXLEN+1 ; int len ; int len ; SString; SString;第19頁/共45頁串的存儲結(jié)構(gòu)及實現(xiàn)定長順序串求子串函數(shù)int SubSString (SString * T, SString S

15、 , int pos , int len ) int i = 1 ; if( NULL=T | NULL=T-ch | len 0 | pos S-len|NULL=S.ch|lenS.len pos+1) return 0 ; for(i=1;ichi=S.chpos+i-1; T-len=len; return 1;弊端：截斷問題第20頁/共45頁串的存儲結(jié)構(gòu)及實現(xiàn)堆串 不限定串的最大長度，動態(tài)地分配串值的存儲空間，只要存儲空間能分配成功，則在操作的過程中就不會出現(xiàn)“截斷”的情況。存儲結(jié)構(gòu)： typedef struct char *ch; int len; HString;串初始化函數(shù)：

16、void HStrInt(HString *S) S-ch=NULL; S-len=0;第21頁/共45頁串的存儲結(jié)構(gòu)及實現(xiàn)堆串串賦值函數(shù)： typedef struct char *ch; int len; HString;int HStrAssign(HString *S,const char * chars) int i=0; if(NULL=chars|NULL=S) return 0; while( charsi!=0) i+; S-len=i; if(0!=S-len) if(S-ch!=NULL) free(S-ch); S-ch=(char*)malloc(S-len+1)*s

17、izeof(char); if(NULL=S-ch) return 0; for(i=1;ilen;i+) S-chi=charsi-1; else S-ch=NULL; return 1 ; 第22頁/共45頁串的存儲結(jié)構(gòu)及實現(xiàn)堆串 typedef struct char *ch; int len; HString;串插入函數(shù)：int HStrInsert(HString *S,int pos,const HString T) int i; char *temp; if(NULL=S|NULL=S-ch|NULL=T.ch|posS-len|poslen+T.len+1)*sizeof(ch

18、ar); if(NULL=temp) return 0; for(i=1;ichi; for(i=pos;ipos+T.len;i+) tempi=T.chi-pos+1; for(i=pos+T.len;ilen+T.len;i+) tempi=S-chi-T.len; free(S-ch); S-ch=temp; S-len=S-len+T.len; return 1; 第23頁/共45頁串的存儲結(jié)構(gòu)及實現(xiàn)堆串 typedef struct char *ch; int len; HString;串刪除函數(shù)：int HStrDelete(HString *S,int pos ,int len

19、) int i;char *temp; if(NULL=S|NULL=S-ch|len0|posS-len-len+1) return 0; temp=(char*)malloc(S-len-len+1)*sizeof(char); if(NULL=temp) return 0; for(i=1;ichi; for(i=pos;ilen-len;i+) tempi=S-chi+len; free(S-ch); S-ch=temp; S-len=S-len-len; return 1;第24頁/共45頁串的存儲結(jié)構(gòu)及實現(xiàn)堆串 typedef struct char *ch; int len; H

20、String;串連接函數(shù)：int HStrCat(HString *S,const HString T) int i=1; if(NULL=S|NULL=S-ch|NULL=T.ch) return 0; S-ch=(char *)realloc(S-ch,(S-len+T.len+1)*sizeof(char); if(NULL=S-ch) return 0; for(i=S-len+1;ilen;i+) S-chi=T.chi-S-len; S-len=S-len+T.len; return 1;第25頁/共45頁串的存儲結(jié)構(gòu)及實現(xiàn)堆串 typedef struct char *ch; i

21、nt len; HString;求子串函數(shù)：int SubHString(HString *THString S,int pos,int len) int i=1; if(NULL=T|NULL=T-ch|NULL=S.ch|lenS.len-pos+1|posS.le) return 0; T-len =len; if(NULL!=T-ch) free(T-ch); T-ch=(char*)malloc(T-len+1)*sizeof(char); if(NULL=T-ch) return 0; for(i=1;ilen;i+) T-chi=S.chpos+i-1; return 1;第26

22、頁/共45頁串的存儲結(jié)構(gòu)及實現(xiàn)塊鏈串塊鏈的存儲結(jié)構(gòu)#define BLOCK_SIZE 4typedef struct block char chBLOCK_SIZE; struct block *next;Block;typedef structBlock *head;Block *tail;int len;LString;因需要連接字符串，設(shè)置尾指針可便于操作，注意連接時需要處理第一個串的最后一個結(jié)點中的無效字符塊大小，指塊鏈表中結(jié)點存放字符的個數(shù)。在這種存儲方式中，塊大小直接影響到串處理的效率，因此就需要考慮串值的存儲密度。第27頁/共45頁串的存儲結(jié)構(gòu)及實現(xiàn)塊鏈串存儲密度=串值所占的存

23、儲位實際分配的存儲位當(dāng)BLOCK_SIZE1：當(dāng)BLOCK_SIZE=1：此時塊鏈表結(jié)構(gòu)同線性鏈表其存儲密度為 1/3由于串長不一定是塊大小的整數(shù)倍，則鏈表的最后一個結(jié)點不一定完全被串值所占滿，此時需補(bǔ)上#或其他字符塊大小為4的塊鏈表，其存儲密度為1/2ABCDI#EFGHheadtail第28頁/共45頁串的模式匹配定義：找字串在主串中從第pos個字符后首次出現(xiàn)的位置應(yīng)用：文本編輯軟件中的查找電子字典中查閱英文單詞S a c a b a b a a c b a b a aT a b a a從S的第1個字符開始，T首次出現(xiàn)的位置為：從S的第7個字符開始，T首次出現(xiàn)的位置為：511第29頁/共4

24、5頁串的模式匹配算法：BF模式匹配算法KMP模式匹配算法目標(biāo)串：主串S模式串：子串Ta c a b a b a a c b a ba b a a第30頁/共45頁串的模式匹配BF算法Brute-Force 算法，蠻力匹配算法a c a b a b a a c b a ba b a a第一趟匹配第一趟匹配第二趟匹配第二趟匹配第三趟匹配第三趟匹配第四趟匹配第四趟匹配第五趟匹配第五趟匹配a c a b a b a a c b a b a b a a a c a b a b a a c b a b a b a aa c a b a b a a c b a b a b a aa c a b a b a

25、a c b a b a b a ai=1j=1i=2j=2i=2i=3i=6i=4i=9i=5j=1j=1j=1j=4j=1j=5字符相等i+ ; j+;字符不相等 j=1; i 回溯 i =2-2+2 i =2-1+2 i =6-4+2 i =4-1+2 匹配成功的條件 規(guī)律：i=i-j+2 jT.len,返回i-T.len第31頁/共45頁串的模式匹配BF算法int Index(SString S，int pos , SString T) int i=pos,j=1; while ( i=S.len & j T.len) return i-T.len;else return 0 ;

26、else i=i-j+2; j=1; BF算法的時間復(fù)雜度第32頁/共45頁串的模式匹配KMP模式匹配算法由D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的改進(jìn)算法KMP算法與BF算法的不同之處： 消除 主串S的指針 回溯a b a b c a b c a c b a ba b c a c第一趟匹配第一趟匹配i=1j=3第二趟匹配第二趟匹配第三趟匹配第三趟匹配a b a b c a b c a c b a b a b c a ca b a b c a b c a c b a b a b c a ci=3i=3i=7i=11i=7j=1j=1j=2j=5j=6第33頁/共4

27、5頁串的模式匹配KMP模式匹配算法S=S1S2 Si-j+1S i-j+2 Si-k+1 Si-1 Si SnT= T1 T2 Tj-k+1 Tj-1 Tj T= T1 Tk-1Tk 0 當(dāng)當(dāng)j=1nextj= Max1kj且且T1 Tk-1=T j-k+1 Tj-1 當(dāng)此集合不為空時當(dāng)此集合不為空時 1 其他情況其他情況第34頁/共45頁串的模式匹配KMP模式匹配算法模式串模式串a(chǎn)baabcac的的next值推導(dǎo)過程值推導(dǎo)過程當(dāng)j=1時，next1=0當(dāng)j=2時，next2=1j值子串真前綴子串真后綴子串結(jié)果 3 ab 串不等串不等 a b ab 串不等串不等 a a ba aba 串長度為

28、串長度為14 j12345678 串a(chǎn)baabcacnextj011221 235子串長度為1串不等ab串不等abaabaabaaaaaa子串長度為2串不等ababaaabaab6baabab串不等aababaabaabc7abaabbaabc串不等abaaaabc串不等abaabc串不等abbc串不等串不等ac8abaabcaabaabcabaabbaabcaaabcaabaaabcaababcaabcaaa串不等串不等串不等串不等子串長度為1串不等繼而討論如何用算法求已知模式串next函數(shù)值：第35頁/共45頁串的模式匹配KMP模式匹配算法T= T1 Tk-1 Tk T=T= T1 Tj-

29、k+1 Tj-1 Tj Tm = (1) nextj+1 = k+1 = nextj+1Tj-k,+1 Tj-1 Tj TmTj-k,+1 Tk-1 Tk T1 Tk,-1 Tk,=nextk (2) 若若Tj=Tk, ,則則nextj = k+1 = nextk+1 若若Tj Tk, ,則繼續(xù)比較則繼續(xù)比較Tj和和Tnextk，即比較，即比較Tj和和Tnextnextk 然后一直重復(fù)下去，若直到最后然后一直重復(fù)下去，若直到最后j=0時都一直比較時都一直比較不成功，則不成功，則nextj=1 .第36頁/共45頁串的模式匹配KMP模式匹配算法void Get_Next(SString T，in

30、t next ) int j=1 , k=0 ; next 1=0 ; while ( j=T.len) if ( k=0 | T.ch j =T.chk) +j ; +k ; nextj=k; else k = next k ;第37頁/共45頁串的模式匹配KMP模式匹配算法a c a b a a b a a b c a c a a b ca b a a b c a c 第一趟匹配第一趟匹配i=1j=2第二趟匹配第二趟匹配第三趟匹配第三趟匹配i=2i=2i=8i=14i=8j=1j=1j=3j=1j=9在求得模式串的next函數(shù)之后，匹配可按如下方式進(jìn)行 j12345678 串a(chǎn)baabca

31、cnextj01122312a c a b a a b a a b c a c a a b c a b a a b c a c a c a b a a b a a b c a c a a b c a b a a b c a c a c a b a a b a a b c a c a a b c a b a a b c a c 第四趟匹配第四趟匹配next2=1next1=0next6=3j=6i=3第38頁/共45頁串的模式匹配KMP模式匹配算法int Index_KMP(SString S，int pos , SString T) int i = pos , j = 1 ; while ( i=S.len & j T.len ) return i T.len ; else return 0 ;KMP