串類型的定義串的表示與實現(xiàn)的模式匹配算法串操作應(yīng)用舉例課件

1、串類型的定義串的表示和實現(xiàn)串的模式匹配算法串操作應(yīng)用舉例第四章 串第1頁，共55頁。1、了解串的概念；學(xué)習(xí)要點2、熟悉串的基本運算的定義 及實現(xiàn)方法；3、掌握基本串匹配算法。第2頁，共55頁。 在較早的程序設(shè)計語言中，字符串（簡稱串）是作為輸入或輸出的常量（是直接量，不參加運算）出現(xiàn)，而非數(shù)值處理的對象基本上是字符串?dāng)?shù)據(jù)。這就要求字符串也能以變量的形式出現(xiàn)，能進(jìn)行一系列字符串操作（運算） 。目前大多數(shù)程序設(shè)計語言都支持串這種數(shù)據(jù)類型。第3頁，共55頁。 1、串 2、串長：串中所包含的字符個數(shù)。 3、空串 ：長度為零的串，它不包含任何字符。 記作“” 4、子串：串中任意個連續(xù)的字符組成的子序列。

2、 5、主串：包含子串的串。 4.1 串類型的定義 基本概念 ：零個或多個字符組成的有限序列，即數(shù) 據(jù)元素為字符的線性表。一般記為 S=a1a2. an ，其中，S是串名， 單引號括起的字符序列是串值。 第4頁，共55頁。7、子串在主串中的位置 ：子串在主串中第一次出現(xiàn)時，子串的第一個字符在主串中的位置。6、字符在串中的位置：字符在序列中的序號。 8、兩個串相等 ：兩個串的長度相等，并且各 個對應(yīng)位置的字符都相等時才相等。9、空格串 ： 由一個或多個空格組成的串，其長度為串中空格字符的個數(shù)。它與空串是不同的概念。 第5頁，共55頁。 串的邏輯結(jié)構(gòu)和線性表極為相似，區(qū)別僅在于串的數(shù)據(jù)對象為字符集。

3、 串的基本操作和線性表有很大差別： 在線性表的基本操作中，大多以“單個元素”作為操作對象； 在串的基本操作中，通常以“串的整體”作為操作對象 。第6頁，共55頁。 ADT String 數(shù)據(jù)對象：D ai |aiCharacterSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系：R1 | ai-1, ai D, i=2,.,n 基本操作： ADT StringADT串的定義第7頁，共55頁。StrAssign (&T, chars) /串賦值 初始條件：chars 是字符串常量。 操作結(jié)果：把 chars 賦為 T 的值。 StrCopy (&T, S) /串復(fù)制 初始條件：串 S 存在。 操作

4、結(jié)果：由串 S 復(fù)制得串 T。DestroyString (&S) /串銷毀 初始條件：串 S 存在。 操作結(jié)果：串 S 被銷毀。第8頁，共55頁。 StrEmpty(S) /串判空初始條件：串S存在。操作結(jié)果：若 S 為空串，則返TRUE， 否則返回 FALSE。StrCompare(S,T) /串比較例如：StrCompare(data, state) 0初始條件：串 S 和 T 存在。操作結(jié)果：若S T，則返回值 0； 若S T，則返回值 0； 若S T，則返回值 0第9頁，共55頁。StrLength (S) /求串長初始條件：串 S 存在。操作結(jié)果：返回 S 的元素個數(shù)， 稱為串的長

5、度。Concat (&T, S1, S2) /串聯(lián)接例如： Concate( T, man, kind) 求得 T = mankind初始條件：串 S1 和 S2 存在。操作結(jié)果：用 T 返回由 S1 和 S2 聯(lián)接而成的新串。第10頁，共55頁。 SubString (&Sub, S, pos, len) /求子串 初始條件： 串 S 存在，1posStrLength(S) 且0lenStrLength(S)-pos+1。 操作結(jié)果：用 Sub 返回串 S 的第 pos 個字符起長度為 len 的子串。子串為“串”中的一個字符子序列。第11頁，共55頁。 SubString( sub, co

6、mmander, 1, 9) 求得 sub = commander SubString( sub, commander, 9, 1) 求得 sub = r 例如： SubString( sub, commander, 4, 3) 求得 sub = man;第12頁，共55頁。SubString(sub , student, 5, 0) 得sub= 關(guān)于參數(shù)len（子串長度）的說明：長度為 0 的子串為“合法”串空串。事實上對任何串S和位置pos 都有：SubString(sub, commander, 4, 7) 得sub = manderSubString(sub , S, pos, 0)得

7、sub= ；有時對len放寬到lenStrLength(S)-pos+1，此時規(guī)定 SubString(sub ,S, pos, len) 的值取S的第pos個字符到S的最后一個字符作為子串（長為StrLength(S)-pos+1）。第13頁，共55頁。Index (S, T, pos) /(子)串(位置)定位 初始條件：串S和T存在，T是非空串， 1posStrLength(S)。 操作結(jié)果：若主串 S 中存在和串T值相同 的子串, 則返回它在主串S中第 pos個字符之后第一次出現(xiàn)的位 置;否則函數(shù)值為0。第14頁，共55頁。假設(shè) S = abcaabcaaabc, T = bca Ind

8、ex(S, T, 1) =Index(S, T, 3) = Index(S, T, 8) = “子串在主串中的位置”意指子串中的第一個字符在主串中的位序。2;6;0;第15頁，共55頁。Replace (&S, T, V) /串替換初始條件：串S, T和 V 均已存在， 且 T 是非空串。操作結(jié)果：用V替換主串S中出現(xiàn)的所有與 （模式串） T相等的不重疊的子串。 例如：假設(shè)S=abcaabcaaabca, T = bca若V=x,則經(jīng)置換后得到S=axaxaax若V=bc,則經(jīng)置換后得到S=abcabcaabc 第16頁，共55頁。 StrInsert (&S, pos, T) /串插入例如：

9、S = chater，T = rac， 則執(zhí)行 StrInsert(S, 4, T)之后得到 S = character初始條件：串S和T存在， 1posStrLength(S)1。操作結(jié)果：在串S的第pos個字符之前插入 串T。 第17頁，共55頁。StrDelete (&S, pos, len) /串刪除 初始條件：串S存在 ， 1posStrLength(S)-len+1。 操作結(jié)果：從串S中刪除第pos個字符 起長度為len的子串。 ClearString(&S) /串清除初始條件：串S存在。操作結(jié)果：將S清為空串。第18頁，共55頁。在上述抽象數(shù)據(jù)類型定義的13種操作中， 串賦值St

10、rAssign、串復(fù)制Strcopy、 串比較StrCompare、求串長StrLength、 串聯(lián)接Concat以及求子串SubString 等六種操作構(gòu)成串類型的最小操作子集。 這些操作不可能利用其他串操作來實現(xiàn)， 反之，其他串操作（除串清除ClearString和串 銷毀DestroyString外）可在這個最小操作子 集上實現(xiàn)。第19頁，共55頁。 例如，可利用串比較、求串長和求子串等操作實現(xiàn)定位函數(shù)Index(S,T,pos)。 StrCompare(SubString(S, i, StrLength(T),T ) T 串 T 串iposStrLength(S) StrLength(

11、T) +1算法的基本思想：? = 0S 串 在pos到StrLength(S) StrLength(T) +1范圍內(nèi)尋求使下式成立的i值 T 串ipos+1第20頁，共55頁。int Index (String S, String T, int pos) / T為非空串。若主串S中第pos個字符之后存在與 T相等的/子串，則返回第一個這樣的子串在S中的 位置，否則返回0 if (pos 0) n = StrLength(S); m = StrLength(T); i = pos; while ( i = n-m+1) SubString (sub, S, i, m); if (StrCompa

12、re(sub,T) != 0) +i ; else return i ; return 0; / S中不存在與T相等的子串 / Index第21頁，共55頁。 利用最小操作子集中的操作也可實現(xiàn) 串判空 StrEmpty(S) 、 串替換 Replace (&S, T, V) 、 串刪除 StrDelete (&S, pos, len) 、 串插入 StrInsert (&S, pos, T) 等操作。留作習(xí)題第22頁，共55頁。 若在程序設(shè)計語言中，串只是作為輸入或輸出的常量出現(xiàn)，則只需存儲此串的串值，即字符序列即可。但在多數(shù)非數(shù)值處理的程序中，串也以變量的形式出現(xiàn)。4.2 串的表示和實現(xiàn) 串

13、有三種機內(nèi)表示方法: 一、串的定長順序存儲表示二、串的堆分配存儲表示三、串的塊鏈存儲表示第23頁，共55頁。 用一組地址連續(xù)的存儲單元存儲串值的字符序列。該結(jié)構(gòu)可用定長數(shù)組描述如下： #define MAXSTRLEN 255 /可在255以內(nèi)定義最大串長 typedef unsigned char Sstring MAXSTRLEN + 1; / 0號單元存放串的長度一、串的定長順序存儲表示第24頁，共55頁。 對串的長度有兩種表示方法: 1.以下標(biāo)為0的數(shù)組分量存放串的實際長度 (如 PASCAL語言) ,特點是便于進(jìn)行某些操作； 2.在串值后面加不計入串長的結(jié)束標(biāo)記字符(如C 語言采用“

14、0” ) ,此時的串長為隱含值,特點是 訪問容易,但刪除或插入麻煩。說明： 串的實際長度可在預(yù)定義長度的范圍內(nèi)隨意設(shè)定， 超過預(yù)定義長度的串值則被 “截斷” 。 對超長部分實施截斷操作正是串的定長順序存儲 表示的弊端。為克服此弊端，惟有不限定最大串 長，即動態(tài)分配串值的存儲空間。第25頁，共55頁。 以下以串聯(lián)接為例進(jìn)行討論在這種存儲結(jié)構(gòu)表示下如何實現(xiàn)串的操作： 假設(shè)T, S1, S2都是 Sstring型變量, T為S1聯(lián)結(jié)S2后所得之串,則聯(lián)接運算Concat (&T, S1, S2) 是將S1和S2的值分別傳送到T的相應(yīng)位置上,超過MAXSTRLEN的部分截斷之。 其運算結(jié)果可能有三種情

15、況： 1) S10+ S20 MAXSTRLEN 2) S10+ S20 MAXSTRLEN 3) S10 MAXSTRLEN第26頁，共55頁。1) S10+ S20 MAXSTRLEN串S1串S2串 TS10S20S10+ S20MAXSTRLENMAXSTRLENMAXSTRLEN第27頁，共55頁。2) S10+ S20 MAXSTRLEN串 S1串 S2串 TS10S20MAXSTRLENMAXSTRLENMAXSTRLEN截去第28頁，共55頁。 串S2被全部截去。3) S10 MAXSTRLEN串 S1串 S2串 TS10S20S10MAXSTRLENMAXSTRLENMAXST

16、RLEN第29頁，共55頁。Status Concat(SString &T, SString S1, SString S2) if (S10+S20 = MAXSTRLEN) / 不截斷 T1.S10 = S11.S10; TS10+1.S10+S20 = S21.S20; T0 = S10+S20; uncut = TRUE; else / 截斷 if ( S10 MAXSTRSIZE ) T1.S10 = S11.S10;TS10+1.MAXSTRLEN = S21.MAXSTRLENS10;T0 = MAXSTRLEN; uncut = FALSE; 第30頁，共55頁。 else T

17、0.MAXSTRLEN = S10.MAXSTRLEN; / T0 = S10 = MAXSTRLEN uncut = FALSE; return uncut; / Concat 在串的順序存儲結(jié)構(gòu)中，實現(xiàn)串操作的原操作為“字符序列的復(fù)制”，操作的時間復(fù)雜度基于字符序列的長度。第31頁，共55頁。二、串的堆分配存儲表示 堆分配存儲類似于線性表的順序存儲結(jié)構(gòu)，仍以一組地址連續(xù)的存儲單元存儲串值的字符序列，但它們的存儲空間是在程序執(zhí)行過程中動態(tài)分配而得的。在C語言中是由動態(tài)分配函數(shù)malloc()和free()來管理一個稱之為“堆（heap）”的自由存儲區(qū)的。該存儲結(jié)構(gòu)類型描述如下：typedef

18、 struct char *ch ; / 若是非空串，則按串長分配存儲區(qū)， /否則ch為NULL int length; / 串長度 一個串值的確定是通過串在堆中的起始位置和串的長度實現(xiàn)的。HString;第32頁，共55頁。 這類串操作實現(xiàn)的算法為: 先為新生成的串（若該串已存在,則先釋放其所占空間）分配一個長度適當(dāng)?shù)拇鎯臻g，然后進(jìn)行串值的復(fù)制。這種存儲結(jié)構(gòu)表示時的串操作仍基于 “字符序列的復(fù)制” 進(jìn)行的。為此，串名與串值之間要建立一個對照表。 0 1 2 3 4 5 6 7 8 9 HString a,b ;串名 基址 ch 長度 length a 2000 4 b 2012 4 D a

19、 t a S t r u c t u r e B o o k 16 2000第33頁，共55頁。 串插入算法Status StrInsert (Hstring &S, int pos, Hstring T) /在串S的第pos個字符之前插入串T S.ch0 1 pos-1T.lengthif (pos S.length+1) return ERROR； if ( T.length ) /T非空，則重新分配空間，插入Tif(!(S.ch=(char *) ralloc(S.ch , (S.length +T.length) *sizeof(char) exit(OVERELOW) ； for(

20、i=S.length-1;i pos - 1;-i ) /插入T而騰出位置 S.chi +T.length= S.chi ；第34頁，共55頁。 S.chpos - 1. pos +T.length - 2= T.ch0. T.length - 1; /插入T S.length = T.length; return OK ; 第35頁，共55頁。堆分配存儲結(jié)構(gòu)表示時的（只含最小操作子集）基本操作的算法描述Status StrAssign(HString &T,char *chars) /生成一個其值等于串常量chars的串Tif(T.ch) free(T.ch); /若串T已存在,釋放其所占空

21、間for ( i=0, c=chars ; c ; +i, +c );if ( ! i ) T.ch=null; T.length=0; else if( ! ( T.ch = ( char * )malloc(i*sizeof(char) exit(OVERFLOW); T.ch0.i-1=chars0.i-1; T.length=i; return OK ; 第36頁，共55頁。int StrLength(HString s) return s.length; int StrCmpare(HString S , HString T) for(i=0; iS.length & iT.leng

22、th; +i) if(S.chi!=T.chi ) return(S.chi T.chi); return S.lengthT.length; Status ClearString(HString &S) if(S.ch) free(S.ch); s.ch=null; S.length=0; return OK; 第37頁，共55頁。Status Concat(HString &T, HString S1, HString S2) / 用T返回由S1和S2聯(lián)接而成的新串 if (T.ch) free(T.ch); / 釋放舊空間 if (!(T.ch = (char *) malloc ( (

23、S1.length+S2.length)*sizeof(char) exit (OVERFLOW); T.ch0.S1.length-1 = S1.ch0.S1.length-1; T.length = S1.length + S2.length; T.chS1.length.T.length-1 = S2.ch0.S2.length-1; return OK; / Concat第38頁，共55頁。 Status SubString(HString &Sub, HString S, int pos, int len) if (pos S.length | len S.length-pos+1)

24、 return ERROR;if ( Sub.ch ) free ( Sub.ch ); / 釋放舊空間 if ( ! len ) Sub.ch = NULL; Sub.length = 0; / 空子串 else / 完整子串 Sub.ch = (char *)malloc(len*sizeof(char); Sub.ch0.len-1 = Spos-1.pos+len-2; Sub.length = len; return OK; / SubString第39頁，共55頁。三、串的塊鏈存儲表示 可采用鏈表方式存儲串值，每個結(jié)點可以存放一個字符，也可以存放多個字符 （如圖所示）。 為便于進(jìn)行

25、串的操作，當(dāng)以鏈表存儲串值時，還需增設(shè)尾指針指示鏈表中的最后一個結(jié)點，并給出當(dāng)前串的長度，如此定義的結(jié)構(gòu)就稱為塊鏈結(jié)構(gòu).描述如下：A B C DE F G HI # # #head head A B C I 第40頁，共55頁。#define CHUNKSIZE 80 / 可由用戶定義的塊大小typedef struct Chunk / 結(jié)點結(jié)構(gòu) char chCHUNKSIZE; struct Chunk *next; Chunk;typedef struct / 串的鏈表結(jié)構(gòu) Chunk *head, *tail; / 串的頭和尾指針 int curlen; / 串的當(dāng)前長度 LStrin

26、g;第41頁，共55頁。 在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，結(jié)點大小的選擇直接影響著串處理的效率。在各種串的處理系統(tǒng)中，所要處理的串往往很長或很多。因此需考慮串的存儲密度。存儲密度 = 數(shù)據(jù)元素所占存儲位實際分配的存儲位 鏈?zhǔn)酱鎯Y(jié)構(gòu)類似線性鏈表，由于串結(jié)構(gòu)的特殊性, 要考慮每個結(jié)點是存放一個字符還是多個字符。一個字符的，插入、刪除、求長度非常方便，但存儲效率低。 多個字符的，改善了效率，在處理不定長的大字符串時很有效，但插入、刪除不方便，可用特殊符號來填滿未充分利用的結(jié)點。 第42頁，共55頁。 例如: 在編輯系統(tǒng)中，整個文本編輯區(qū)可以看成是一個串，每一行是一個子串，構(gòu)成一個結(jié)點。即: 同一行的串用定長結(jié)構(gòu)

27、(80個字符), 行和行之間用指針相聯(lián)接。 實際應(yīng)用時，可以根據(jù)問題所需來設(shè)置結(jié)點的大小。第43頁，共55頁。4.3串的模式匹配算法 子串位置定位操作Index( S , T , pos )通常稱作串的模式匹配（其中T被稱為模式串）,是各種串處理系統(tǒng)中最重要的操作之一。很多軟件若有“編輯”菜單項的話，則其中必有“查找”子菜單項。查找即為模式匹配。第44頁，共55頁。INDEX (S, T, pos)初始條件：串S和T存在，T是非空串， 1posStrLength(S)。操作結(jié)果：若主串S中存在和串T值相同的 子串返回它在主串S中第pos個字符之后 第一次出現(xiàn)的位置; 否則函數(shù)值為0 。 回憶一

28、下串定位操作的定義:第45頁，共55頁。模式匹配的算法的基本思想: 從主串S的第 pos個字符起和模式串T的第一個字符比較，若相等，則逐個比較后續(xù)字符;否則從S的下一個字符起再重新和T的字符比較。依此類推,直至T中的每個字符依次和S 中一個連續(xù)的字符序列相等為止,則稱匹配成功,返回與T中第一個字符相等的字符在S中的序號;否則稱匹配不成功,返回零。 為此,設(shè)置主串指針i和模式串指針j指示當(dāng)前兩串對應(yīng)位置上的 (待比較的)字符。 以下展示模式T=abcac和主串S=ababcabcacbab的匹配過程:第46頁，共55頁。a b a b c a b c a c b a b第一趟匹配 i=1.a b

29、 c a ca b a b c a b c a c b a b第三趟匹配 i=3.第四趟匹配 i=4.第五趟匹配 i=5.第六趟匹配 i=6.匹配成功第二趟匹配 i=2.a b a b c a b c a c b a ba b a b c a b c a c b a ba b a b c a b c a c b a ba b a b c a b c a c b a ba b c a ca b c a ca b c a ca b c a ca b c a c327411j=1.j=1.j=1.j=1.j=1.j=1.3111655T0第47頁，共55頁。以定長順序結(jié)構(gòu)表示串時的簡單算法（不依賴于

30、其它串操作）int Index(SString S, SString T, int pos) i = pos; j = 1; while ( i S0 & j T0) /匹配成功( T0 個對應(yīng)位置上的字符相同） return i-T0; /返回子串在主串中的位置 else return 0; / Index 本算法思路簡單，匹配過程易于理解，通常稱作樸素的匹配算法。在某些應(yīng)用場合，如文本編輯，效率也較高。但當(dāng)主串中存在多個與模式串“部分匹配”的子串時，就引起主串指針i的多次回溯，從而降低匹配效率。以下介紹的KMP算法就是一種改進(jìn)算法，其改進(jìn)在于：不需回溯i指針，而是利用已得“部分匹配”的結(jié)果將模式串盡可能遠(yuǎn)地向右“滑動”。第49頁，共55頁。 以模式T=abcac和主串S=ababcabcacbab的匹配過程為例簡但介紹KMP算法：a b a b c a b c a c b a b第一趟匹配 i=1.a b c a c第三趟匹配 i=3.第四趟匹配 i=4.第五趟匹配 i=5.第六趟匹配 i=6.匹配成功a b a b c a b c a c b a ba b a b c a b c a c b a ba b a b c a b c a c b a ba b a b c a b c a c b a ba b c a ca b c a ca