1、第1頁,每課一貼：一個人去買鸚鵡，看到一只鸚鵡前標：此鸚鵡會兩門語言，售價二百元。另一只鸚鵡前則標有：此鸚鵡會四門語言，售價四百元。該買哪只呢？兩只都毛色光鮮，非常靈活可愛。這人轉(zhuǎn)啊轉(zhuǎn)，拿不定主意。結(jié)果突然發(fā)現(xiàn)一只老掉了牙的鸚鵡，毛色暗淡散亂，標價八百元。這人趕緊將老板叫來：這只鸚鵡是不是會說八門語言？店主說：不。這人奇怪了：那為什么又老又丑，又沒有能力，會值這個數(shù)呢？店主回答：因為另外兩只鸚鵡叫這只鸚鵡老板。這故事告訴我們，真正的領導人，不一定自己能力有多強，只要懂信任，懂放權(quán)，懂珍惜，就能團結(jié)比自己更強的力量，從而提升自己的身價。相反許多能力非常強的人卻因為過于完美主義，事必躬親，什么人都

2、不如自己，最后只能做最好的攻關(guān)人員，銷售代表，成不了優(yōu)秀的領導人。,第2頁,數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容,第3頁,第4章 串（String）,1. 定義 2. 邏輯結(jié)構(gòu) 3. 存儲結(jié)構(gòu) 4. 運算規(guī)則 5. 實現(xiàn)方式,第4頁,記為： s =“ a1 , a2 , . , an” (n0 ),串中字符個數(shù)（n0）. n=0 時稱為空串 。 由一個或多個空格符組成的串。!= 串s中任意個連續(xù)的字符序列叫s的子串; S叫主串。 子串的第一個字符的序號。 字符在串中的序號。 串長度相等，且對應位置上字符相等。,串即字符串，是由零個或多個字符組成的有限序列，是數(shù)據(jù)元素為單個字符的特殊線性表。,4.1 串類型的定義

3、,若干術(shù)語： 串長： 空白串： 子串： 子串位置： 字符位置： 串相等：,隱含結(jié)束符0 ，即ASCII碼NUL,第5頁,練1：串是由 字符組成的序列，一般記為 。,練2：現(xiàn)有以下4個字符串： a =“show” , b =“me” , c = “show money” , d = “show me the money”,問： 它們各自的長度？ a是哪個串的子串？在主串中的位置是多少？,a =4，b =2，c = 10，d=17,a是c和d的子串，在c和d中的位置都是1,練3：空串和空白串有無區(qū)別？ 答：有區(qū)別?？沾?Null String)是指長度為零的串；而空白串(Blank String)

4、,是指包含一個或多個空白字符 (空格鍵)的字符串.,0個或多個,S=“a1a2an”,練4：空串是任意串的子串， 任意串是其自身的子串!,第6頁,ADT Sting Objects: D=ai | aiCharacterSet, i=1, 2,，n, n0 Relations: R1= | ai-1,ai D, i=2, ，n,串的抽象數(shù)據(jù)類型定義（參見教材P71）,functions: / 有13種之多 StrAssign( / StrLength Char * strcpy(char *s1,const char *s2); /StrCopy Char * strcat(char *s1,

5、 char *s2); / Concat int strcmp(const char *s1,const char *s2); /StrCompare,第8頁,串的其余操作可由這些最小操作子集中的操作組合而成。 例1、求子串定位函數(shù)Index（S，T，pos） 子串定位的過程即為依次取主串中與該子串長度相同的子串進行比較的過程。 void Index(string /Index,第9頁,設 s =“I AM A STUDENT”, t =“GOOD”, q=“WORKER”。求：,練習：,StrLength(s) StrLength(t) SubString(s, 8, 7)= SubStri

6、ng(t, 2, 1)= Index(s, A)= Index(s, t)= Replace(s, STUDENT,q)=,14 4 “STUDENT” “O” 3 0 （ s中沒有t?。?“I AM A WORKER”,再問：Concat(SubString(s,6,2), Concat(t,SubString(s,7,8) ？,第10頁,4.2串的表示和實現(xiàn),定長順序存儲表示 用一組地址連續(xù)的存儲單元存儲串值的字符序列 堆分配存儲表示 用一組地址連續(xù)的存儲單元存儲串值的字符序列,但存儲空間是在程序執(zhí)行過程中動態(tài)分配而得。 串的塊鏈存儲表示 鏈式方式存儲,首先強調(diào)：串與線性表的運算有所不同，

7、是以“串的整體”作為操作對象，例如查找某子串，在主串某位置上插入一個子串等。,串有三種物理存儲方法：,順序存儲,鏈式存儲,第11頁,定長順序存儲特點：用一組連續(xù)的存儲單元來存放串，直接使用定長的字符數(shù)組來定義，數(shù)組的上界預先給出，故稱為靜態(tài)存儲分配。,例如： #define Maxstrlen 255 /用戶可用的最大串長 typedef unsigned char SString Maxstrlen+1 ; SString s; /s是一個可容納255個字符的順序串。,注： 一般用SString0來存放串長信息； C語言約定在串尾加結(jié)束符 0，以利操作加速，但不計入串長； 若字符串超過Max

8、strlen 則自動截斷（因為靜態(tài)數(shù)組存不 進去）。,討論：想存放超長字符串怎么辦？靜態(tài)數(shù)組有缺陷！,實現(xiàn)方式：參見教材P105編程例，兩串連接和107求子串,改用動態(tài)分配的一維數(shù)組,“堆”！,第12頁,例：用順序存儲方式實現(xiàn)求子串函數(shù)SubString( / 若非空串,按串長分配空間; 否則 ch = NULL int length; /串長度 HString,堆分配存儲特點：仍用一組連續(xù)的存儲單元來存放串，但存儲空間是在程序執(zhí)行過程中動態(tài)分配而得。,約定：所有按堆存儲的串，其關(guān)鍵信息放置在：,第14頁,Status StrAssign(HString /StrAssign,指針變量C也可以

9、自增！即每次后移一個數(shù)據(jù)單元。,附：堆分配存儲表示P77,直到終值為“假”停止，串尾特征是 0NULL=0,第15頁,Status StrInsert ( HString /StrInsert,例：用“堆”實現(xiàn)串插入操作,第16頁,討論：法1存儲密度為 ；法2存儲密度為 ；,顯然，若數(shù)據(jù)元素很多，用法2存儲更優(yōu)稱為塊鏈結(jié)構(gòu),鏈式存儲特點 ：用鏈表存儲串值，易插入和刪除。,法1：鏈表結(jié)點（數(shù)據(jù)域）大小取1,法2：鏈表結(jié)點（數(shù)據(jù)域）大小取n(例如n=4),1/2,9/15=3/5,第17頁,#define CHUNKSIZE 80 /可由用戶定義的塊大小 typedef struct Chunk

10、/首先定義結(jié)點類型 char ch CHUNKSIZE ; /結(jié)點中的數(shù)據(jù)域 struct Chunk * next ; /結(jié)點中的指針域 Chunk;,塊鏈類型定義：,typedef struct /其次定義用鏈式存儲的串類型 Chunk *head; /頭指針 Chunk *tail; /尾指針 int curLen; /結(jié)點個數(shù) Lstring; /串類型只用一次，前面可以不加Lstring,第18頁,再次強調(diào)：串與線性表的運算有所不同，是以“串的整體”作為操作對象，例如查找某子串，在主串某位置上插入一個子串等。,這類操作中均涉及到定位問題，稱為串的模式匹配。它是串處理系統(tǒng)中最重要的操作

11、之一。,第19頁,4.3 串的模式匹配算法!,第20頁,4.3 串的模式匹配算法,串的模式匹配：子串定位運算（Index函數(shù)）。,算法目的：確定主串中所含子串第一次出現(xiàn)的位置（定位） 即如何實現(xiàn) Index(S,T,pos)函數(shù),模式(Pattern）: 存在于時間和空間種可觀察事物中的信息，我們可以區(qū)分它們是否相同或相似，都可以稱之為模式。,模式匹配(Pattern Matching) : 檢驗模式是否相同或相似的過程。,第21頁,初始條件：串S和T存在，T是非空串，1posS0 操作結(jié)果：若主串S中存在和串T值相同的子串，則返回它在主串S中第pos個字符之后第一次出現(xiàn)的位置；否則函數(shù)值為0

12、。,Index(S,T,pos)函數(shù),算法目的：確定主串中所含子串第一次出現(xiàn)的位置（定位） 即如何實現(xiàn) Index(S,T,pos)函數(shù)（見教材P71）,pos=5,主串S中從pos位置開始起搜索子串T第一次出現(xiàn)的位置是6,第22頁,基礎知識： 兩等長串是否相等的比較方法,int Is_Equal(SString S, SString T) int i=1; j=1; /定義i，j分別指示兩串當前比較字符位置，相當于“指針” while ( iT0) return 1; /匹配成功時jT0，即T串長度，返回1，匹配成功 else return0; /匹配失敗時jT0 ,返回0 / Is_Equ

13、al,第23頁,BF算法 （又稱古典或經(jīng)典的、樸素的、窮舉的） KMP算法（特點：速度快）,算法種類：,S=a b a b c a b c a c b a b,T=a b c a c,問：現(xiàn)在主S串比模式串T長，要找到其中是否包含子串T怎么辦？,答：可將主串S中和T串等長的子串與T進行比較，因此需要通過循環(huán)實現(xiàn)！,下面介紹兩種常用實現(xiàn)算法：,有兩種實現(xiàn)方法：T不動，取S的不同子串與其比較 S不動，T移動,第24頁, BF算法設計思想： 將主串的第i個字符和模式的第1個字符比較， 若相等，繼續(xù)逐個比較后續(xù)字符； 若不等，從主串的下一字符（i+1）起，重新與第一個字符比較。,直到主串的一個連續(xù)子串

14、字符序列與模式相等 。返回值為S中與T匹配的子序列第一個字符的序號，即匹配成功。 否則，匹配失敗，返回值 0 .,BF算法的實質(zhì)：依次將主串中和T串等長的子串與T進行比較，故需要進行一個循環(huán)！,如何采用BF算法實現(xiàn) Index(S,T)函數(shù)？,可借助演示系統(tǒng)單步執(zhí)行獲得感性認識！,第25頁,BF算法特例： S=ababcabcacbab，T=abcac，pos=1， 求：串T在串S中第pos個字符之后的位置。,解：因pos=1，可利用演示系統(tǒng)看BF算法執(zhí)行過程,int IndexBF(SString S,SString T)此題的BF算法： int i=1,j=1; / 初始“指針” whil

15、e(iT0) return i-T0; /子串結(jié)束，說明匹配成功 else return 0; /IndexBF 注意比較和Is_Equal(SString S, SString T)的異同,相當于子串向右滑動一個字符位置,S=a b a b c a b c a c b a b,T=a b c a c,pos=1,第26頁,Int Index(SString S, SString T, int pos) int i=pos, j=1; while ( iT0) return i-T0; /子串結(jié)束，說明匹配成功 else return0; /Index, BF算法的實現(xiàn)即Index（）操作的實

16、現(xiàn),相當于子串向右滑動一個字符位置,匹配成功后指針仍要回溯！因為要返回的是被匹配的首個字符位置。,此函數(shù)僅僅就是從第pos個位置開始比較而已!,第27頁,最惡劣情況分析： 例如：S=aaaaaaab; t=ab; n8，m2 （1）主串前面n-m個位置都部分匹配到子串的最后一位，即這n-m位都比較了m次， （2）別忘了最后m位也各比較了一次，還要加上m！,BF匹配算法的最壞時間復雜度？,(n-m+1)*m,O(n-m+1)*m)O(n*m),第28頁,設從si開始與t串匹配成功的概率為pi，在等概率情況下pi=1/(n-m+1)，因此最好情況下平均比較的次數(shù)是：,即最好情況下的時間復雜度是O(n+m)。,最好情況是： （1）主串前面n-m個位置比較時第一位就不等，即這n-m位都只比較了n-m次 （2）同樣最后m位也各比較了一次，還要加上m！ 總共比較次數(shù)：i1m (設T在S中出現(xiàn)位置是i）,S=a b a b c a b c m b c a c,T=m b c a c,第29頁