《數(shù)據(jù)結構(嚴蔚敏)課件第4章.ppt》由會員分享，可在線閱讀，更多相關《數(shù)據(jù)結構(嚴蔚敏)課件第4章.ppt（90頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、 第四章 串 【 課前思考 】 1. 串就是線性表 的結論是否正確？ 從數(shù)據(jù)結構的觀點來說，串是一種特殊的 線性表 ;但就數(shù)據(jù)類型而言，串不是線性表。 2. 串和線性表的主要差別是什么？ 希望你帶著這個問題開始這一章的學習， 并能在學完這一章的內容之后能得出正確 的結論。 【 學習目標 】 1. 理解“串”類型定義中各基本操作的特 點，并能正確利用它們進行串的其它操作。 2. 理解串類型的各種存儲表示方法。 3. 理解串匹配的各種算法。 【 重點和難點 】 相對于其它各個知識點而言，本章非整個課程 的重點，鑒于串已是多數(shù)高級語言中已經(jīng)實現(xiàn)的數(shù) 據(jù)類型，因此
2、本章重點僅在于了解串類型定義中各 基本操作的定義以及串的實現(xiàn)方法，并學會利用這 些基本操作來實現(xiàn)串的其它操作。本章的 難點 是理 解實現(xiàn) 串匹配的 KMP算法 的思想，但它不屬本章學 習的基本要求，更不是重點學習內容。 【 知識點 】 串的類型定義、串的存儲表示、串匹配、 KMP算法 【 學習指南 】 雖然目前各常用的高級語言中都已經(jīng)實 現(xiàn)了串類型，但由于它是通過軟件實現(xiàn)的， 因此作為一個軟件工作者還是應該了解串的 實現(xiàn)方法。本章沒有必須完成的算法設計題， 如果有興趣可以試試以下幾個題 :4.10， 4.11， 4.13， 4.17， 4.18， 4.23， 4.28,4.30
3、。其中前 6個是練習串的基本操作的應用，后 2個是和 KMP算法相關的練習。 4.1 串類型的定義 4.2 串的表示和實現(xiàn) 4.3 串的模式匹配算法 4.1串的類型定義 一、 基本概念 1 串的定義 串 ( string) 是由零個或多個字符組成的有限序列 ， 記作 s=a1a2 an， 其中 s為串的名字 ， 用成對的單引號括起 來的字符序列為串的值 ， 但兩邊的引號不算串值 ， 不包 含在串中 。 ai(1in)可以是字母 、 數(shù)字或其它字符 。 n為串中字符的個數(shù) ， 稱為串的長度 。 2 空串 不含任何字符的串稱為空串，它的長度 n=0，記為 s=。 3 空格串
4、 含有一個或多個空格的串 ， 稱為空格串 ， 它的長度 n為 空格的個數(shù) ， 一般用符號 “ ” 表示空串 。 串是有限長的字符序 列，由一對單引號相 括，如 : a string 4 子串 、 主串 通常將字符在串中的序號稱為該字符在串中的位置 。 子串在主串中的位置則以子串的第一個字符在主串中的 位置來表示 。 若一個串是另一個串中連續(xù)的一段 ， 則這個串稱為另一 個串的子串 ， 而另一個串相對于該串稱為主串 。 例如 ,串 s1=“ abcdefg” ， s2=“ fabcdefghxyz” ， 則 s1為 s2的子串 ， s2相對于 s1為主串 。 另外 ， 空串是任
5、意串的子串 ， 任意串是自身的子串 。 若一個串的長度為 n， 則它的子串數(shù)目為 +1， 真子串 個數(shù)為 (除串本身以外的子串都稱為真子串 )。 當且僅當兩個串的值相等時 ,稱這兩個串是相等的，即 只有當兩個串的長度相等 , 并且每個對應位置的字符都相 等時才相等。 2 )1( nn 2 )1( nn 二、串的抽象數(shù)據(jù)類型的定義如下： ADT String 數(shù)據(jù)對象 ： D ai |ai CharacterSet, i=1,2,...,n, n0 數(shù)據(jù)關系 ： R1 | ai-1, ai D, i=2,
6、...,n 基本操作 ： StrAssign ( m = 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 又如串的置換函數(shù) ： Replace( // 0號單元存放串的長度 或： typedef struct /* 串結構定
7、 義 */ char chMAXLEN ; int len; SString; 按這種串的表示方法實現(xiàn)的串的 運算時，其基本操作為 “ 字符序列 的復制”。 串 的實際長度可在這個予定義長 度的范圍內隨意設定，超過予定義 長度的串值則被舍去，稱之為 “截斷” 。 特點 : Status Concat(SString S1, SString S2, SString // Concat 例如： 串的聯(lián)接算法中需分三種情況處理： T1..S10 = S11..S10; TS10+1..S10+S20 = S21..S20; T0 = S10+S20;
8、 uncut = TRUE; if (S10+S20 <= MAXSTRLEN) // 未截斷 else if (S10
9、TRLEN uncut = FALSE; (1) 串插入函數(shù) 。 StrInsert(s, pos, t) /*在串 s中序號為 pos的字符之前插入串 t */ SString *s, t; int pos; int i; if (poss-len) return(0); /* 插入位置不合法 */ if (s-len + t.lenlen + t.len-1;i=t.len + pos;i--) s-ch i =s-ch i-t.len ; for (i=0;ich i+pos =t.ch i ; s-len=s-len+t.len;
10、 定長順序存儲的操作實施： 【 算法 串插入函數(shù) 】 a b x y z c d e f x y z a b c d e f x y z T 串 S 串 T 串 S 串 ( a ) 插入前 圖 4 1 順序串的插入 ( b ) 插入后 ( i = 3 ) else if (pos+t.lenMAXLEN, 但串 t的字符序列可以全部插入 */ for (i=MAXSTRLEN-1;
11、it.len+pos-1;i--) s-ch i =s-ch i-t.len ; for (i=0;ich i+pos =t.ch i ; s-len=MAXLEN; else /* 串 t的部分字符序列要舍棄 */ for (i=0;ich i+pos =t.ch i ; s-len=MAXSTRLEN; return(1); (2) StrDelete(s, pos, len) /* 在串 s中刪除從序號 pos起 len個字符 */ SString *s; int pos, len; int i; if (pos(s-l
12、en-len)) return(0); for (i=pos+len;ilen;i++) s-ch i-len =s-ch i ; s-len=s-len - len; return(1); 【 算法 串刪除函數(shù) 】 a b c i j k a b c d e f g h i j k ( a ) 刪除前 圖 4 - 2 順序串的刪除 ( i = 4 , j = 5 ) ( b ) 刪
13、除后 (3) StrCopy(s, t) /* 將串 t的值復制到串 s中 */ SString *s, t; int i; for (i=0;ich i =t.ch i ; s-len=t.len; 【 算法 串復制函數(shù) 】 (4) StrEmpty(s) /* 若串 s為空 (即串長為 0), 則返回 1, 否則返回 0 */ SString s; if (s.len==0) return(1); else return(0); 【 算法 判空函數(shù) 】 (5) 串比較函數(shù) 。 StrCompare(s, t) /* 若串 s和 t相等 ,
14、則返回 0；若 st， 則返回 1；若 s
15、lenlen;ich i =t.ch i-s-len ; s-len=MAXSTRLEN;flag=0; else flag=0;/* 串 s的長度等于 MAXLEN, 串 t不被連接 */ return(flag); 【 算法 連接函數(shù) 】 (9) 求子串函數(shù)。 SubString(sub, s, pos, len) /* 將串 s中序號 pos起 len個字符復制到 sub中 */ SString *sub, s; int pos, len; int i; if (poss.len || lens.len-pos) sub-len=0;re
16、turn(0); else for (i=0;ich i =s.ch i+pos ; sub-len=len;return(1); 【 算法 求子串函數(shù) 】 (10) 定位函數(shù) 。 StrIndex(s, pos, t) /* 求串 t在串 s中的位置 */ SString s, t; int pos; int i, j; if (t.len==0) return(0); i=pos;j=0; while (i
17、h; // 若是非空串，則按串長分配存儲區(qū) ， // 否則 ch為 NULL int length; // 串長度 HString; 二、串的堆分配存儲表示 特點：仍用一組地址連續(xù)的存儲單元 存儲串的字符序列，但其存儲空間是 在程序執(zhí)行過程中動態(tài)分配而得。 通常， C語言中提供的串類型就是以這種 存儲方式實現(xiàn)的。系統(tǒng)利用函數(shù) malloc( )和 free( )進行串值空間的動態(tài)管理，為每一個新 產生的串分配一個存儲區(qū)，稱串值共享的存 儲空間為 “堆”。 C語言中的串以一個空字符為結束符， 串長是一個隱含值。 這類串操作 實現(xiàn)的算法 為
18、： 先為新生成的串分配一個存儲空間，然后 進行串值的復制。 Status Concat(HString // 釋放舊空間 if (!(T.ch = (char *) malloc((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;
19、 return OK; // Concat Status SubString(HString if (Sub.ch) free (Sub.ch); // 釋放舊空間 if (!len) Sub.ch = NULL; Sub.length = 0; // 空子串 else // 完整子串 return OK; // SubString Sub.ch = (char *)malloc(len*sizeof(char)); Sub.ch0..len-1 = Spos-1..pos+len-2
20、; Sub.length = len; 三、串的塊鏈存儲表示 也可用鏈表來存儲串值，由于串的數(shù)據(jù) 元素是一個字符，它只有 8 位二進制數(shù)， 因此用鏈表存儲時，通常一個結點中存 放的不是一個字符，而是一個子串。 存儲密度 = 數(shù)據(jù)元素所占存儲位 實際分配的存儲位 #define CHUNKSIZE 80 // 可由用戶定義的塊大小 typedef struct Chunk // 結點結構 char chCHUNKSIZE; struct Chunk *next; Chunk; typedef struct // 串的鏈表結構 Chunk *head, *ta
21、il; // 串的 頭和尾指針 int curlen; // 串的 當前長度 LString; 例如 : 在編輯系統(tǒng)中，整個文本編輯區(qū) 可以看成是一個串，每一行是一個子串， 構成一個結點。即 : 同一行的串用定長結構 (80個字符 ), 行和行之間用指針相聯(lián)接。 實際應用時，可以根據(jù)問題所需來 設置結點的大小。 這是串的一種重要操作，很多 軟件，若有 “編輯” 菜單項的話， 則其中必有 “查找” 子菜單項。 4.3 串的模式匹配算法 子串的定位操作通常稱為串的 模式匹 配 ，是各種串處理系統(tǒng)中最重要的操作 之一。 初始條件： 串 S和 T
22、存在 ， T是非空串 ， 1posStrLength(S)。 操作結果： 若主串 S中存在和串 T值相 同的子串返回它在主串 S中 第 pos個字符之后第一次出 現(xiàn)的位置；否則函數(shù)值為 0。 首先，回憶一下 串匹配 (查找 )的定義 : INDEX (S, T, pos) 下面討論以定長順序結構 表示串時的幾種算法。 一、簡單算法 二、 首尾匹配算法 三、 KMP(D.E.Knuth, V.R.Pratt, J.H.Morris) 算法 一、簡單算法 Bru
23、te-Force算法 例如 ,設目標串 s=“ cddcdc” ,模式串 t=“ cdc” 。 s 的長度為 n(n=6),t的長度為 m(m=3)。用指針 i指示目 標串 s的當前比較字符位置 ,用指針 j指示模式串 t的當 前比較字符位置。 BF模式匹配過程如下所示。 第 1 次匹配 s = c d d c d c i = 2 t = c d c j = 2 失敗 第 2 次匹配 s = c d d c d c i = 1 t = c d c j = 0 失敗 第 3 次匹配 s = c d d c d c i = 2 t = c d c j = 0 失敗
24、 第 4 次匹配 s = c d d c d c i = 5 t = c d c j = 2 成功 這個算法簡單 ,易于理解 ,但效率不高 ,主要原因是 : 主串指針 i在若干個字符序列比較相等后 ,若有一個字 符比較不相等 ,仍需回溯 (即 i=i-j+1)。該算法在最好情 況下的時間復雜度為 O(m),即主串的前 m個字符正好 等于模式串的 m個字符。在最壞情況下的時間復雜度 為 O(n*m)。 int index(SqString s,SqString t) int i=0,j=0,k; while (i
25、 else k=-1; /*模式匹配不成功 */ return k; 先 比較模式串的第一個字符， 再 比較模式串的最后一個字符， 最后 比較模式串中從第二個到 第 n-1個字符。 二、 首尾匹配算法 int Index_FL(SString S, SString T, int pos) sLength = S0; tLength = T0; i = pos; patStartChar = T1; patEndChar = TtLength; while (i <= sLength tLength
26、 + 1) if (Si != patStartChar) ++i; //重新查找匹配起始點 else if (Si+tLength-1 != patEndChar) ++i; // 模式串的“尾字符”不匹配 else return 0; // 檢查中間字符的匹配情況 k = 1; j = 2; while ( j < tLength ++j; if ( j == tLength ) return i; else ++i;
27、// 重新開始下一次的匹配檢測 三、模式匹配的改進算法 （ KMP算法） 此方法由克努特 (D.E.Knuth)莫里斯 (J.H.Morris)普拉特 (V.R.Pratt)同時發(fā)現(xiàn)。 1.基本思想： 每當一趟匹配過程中出現(xiàn)字符不等時，不 需回溯 i指針，而是利用已得到的部分匹配結果，將模 式串向右滑動盡可能遠的一段距離后繼續(xù)進行比較。 避免多余的、不必要的比較，從而提高算法性能。算法 總在 0(n+m)的時間數(shù)量級上完成匹配操作。 a b a b c a b c a c b a b ab c ( a ) 第一趟匹配 s 3 t 3 ( b ) 第二趟匹配
28、 s 7 t 5 ( c ) 第三趟匹配成功 圖 K M P 模式匹配過程 a b a b c a b c a c b a b ab cac a b a b c a b c a c b a b a b cac 2.KMP算法匹配實例： (1)模式串 t中沒有真子串 真子串 是指模式串 t存在某個 k(0 k j),使得 “ t0t1 tk” =“ tj-ktj-k+1 tj” 成立 。 例如 t=cdc就是這樣的模式串 。 在圖 4.6中的第一 次回溯 ,當 s0=t0,s1=t1,s2t2時 ,算法中取 i=1,j=0,使主串指 針回溯一個位置
29、 ,比較 s1和 t0。 因 t0t1,所以一定有 s1t0。 另外 ,因有 t0=t2,s0=t0,s2t2,則一定可推出 s2t0,所以也不 必取 i=2,j=0去比較 s2和 t0。 可直接在第二次比較時取 i=3,j=0,比較 s3和 t0。 這樣 ,模式匹配過程主串指針 i就可 不必回溯 。 (2)模式串中存在真子串 例如 t=“ abab” ,由于“ t0t1” =“ t2t3” (這里 k=1,j=3),則存在真子串。設 s=“ abacabab” ,t=“ abab” ,第一次匹配過程如下所 示。 第 1 次匹配 s = a ba c a ba b i= 3
30、 t = a ba b j= 3 失敗 此時不必從 i=1(i=i-j+1=1),j=0重新開始第二次匹 配。因 t0t1,s1=t1,必有 s1t0,又因 t0 =t2,s2=t2,所以必有 s2=t0。因此 ,第二次匹配可直接從 i=3,j=1開始。 現(xiàn)在我們討論一般情況。 設 s=s0s1s n-1,t=t0t1t m-1,當 sitj (0in-m,0j m)時 ,存在 : t0t1 tj-1=si-jsi-j+1 si-1 (4.1) 若模式串中存在的真子串滿足 : t0t1 tk=tj-ktj-k+1 tj (0 k
31、j) (4.2) 由 (4.1)式說明模式串中的子串 t0t1 tk-1已和主串 si-ksi-k+1 si-1匹配 ,下一次可直接比較 si和 tk,若不存在 (4.2) 式 ,則結合 (4.1)式說明在 t0t1 tj-1中不存在任何以 t0為首 字符子串與 si-j+1si-j+2 si-1中以 si-1為末字符的匹配子串 , 下一次可直接比較 si和 t0。 為此 ,定義 nextj函數(shù)如下 : maxk|0
32、 當此集合非空時 -1 當 j=0時 0 其他情況 nextj= j 0 1 2 3 tj a b a b nextj -1 0 0 1 t=“ abab” 對應的 next數(shù)組如下 : 由模式串 t求出 next值的算法如下 : void GetNext(SqString t,int next) int j,k; j=0;k=-1;next0=-1; while (j
33、 /*k為 -1或比較的字符相等時 */ j++;k++; nextj=k; else k=nextk; int KMPIndex(SqString s,SqString t) /*KMP算法 */ int nextMaxSize,i=0,j=0,v; GetNext(t,next); while (i
34、串 t長度為 m,在 KMP算法 中求 next數(shù)組的時間復雜度為 O(m),在后面的匹配 中因主串 s的下標不減即不回溯 ,比較次數(shù)可記為 n, 所以 KMP算法總的時間復雜度為 O(n+m)。 例如 ,設目標串 s=“ aaabaaaab” ,模式串 t=“ aaaab” 。 s的長度為 n(n=9),t的長度為 m(m=5)。 用指針 i指示目標串 s的當前比較字符位置 ,用指針 j指 示模式串 t的當前比較字符位置。 KMP模式匹配過 程如下所示。 第 1 次匹配 s = a a a b a a a a b i = 3 t = aaaab j = 3 , j = n
35、 e x t 3 = 2 失敗 第 2 次匹配 s = a a a b a aaab i = 3 t = aaaab j = 2 , j = n e x t 2 = 1 失敗 第 3 次匹配 s = a a a b a a a a b i = 3 t = aaaab j = 1 , j = n e x t 1 = 0 失敗 第 4 次匹配 s = a a a b a a a a b i = 3 t = aaaab j = 0 , j = n e x t 0 = - 1 失敗 第 5 次匹配 s = a a a b a a a a b i = 9 t
36、 = aaaab j = 4 ,返回 9 - 5 = 4 成功 j 0 1 2 3 4 tj a a a a b nextj -1 0 1 2 3 上述定義的 next在某些情況下尚有缺陷。例如 , 模式“ aaaab” 在和主串“ aaabaaaab” 匹配時 ,當 i=3,j=3時 ,s.ch3t.ch3,由 nextj的指示還需進行 i=3、 j=2,i=3、 j=1,i=3、 j=0等三次比較。實際上 ,因為模式 中的第 1、 2、 3個字符和第 4個字符都相等 ,因此 ,不需 要再和主串中第 4個字符相比較 ,而可以將模式一次向 右滑動 4個字符的位置直接進行 i=4,
37、j=0時的字符比較。 KMP算法的改進： 這就是說 ,若按上述定義得到 nextj=k,而模式 中 pj=pk,則為主串中字符 si和 pj比較不等時 ,不需要 再和 pk進行比較 ,而直接和 pnextk進行比較 ,換句話 說 ,此時的 nextj應和 nextk相同。為此將 nextj 修正為 nextvalj。 由模式串 t求出 nextval值 : void GetNextval(SqString t,int nextval) int j=0,k=-1; nextval0=-1; while (jnext，再設一 個對尾指針 q-rear指向鏈
38、隊列尾部。 隊列的鏈式存儲結構可定義如下： typedef struct node typedef struct char data; slnode *h; struct node *next; slnode ; slnode *rear;lqtype; 四、思考題 1、 比較鏈隊列與鏈棧的相同點與不同點。 2、在鏈隊列中， q-rear指針能否省 去 ？若能，怎樣才能找到隊
39、尾？ 實驗六 串的模式匹配 一、實驗目的 熟悉串的有關概念，掌握串的存儲結構及串的模式匹配算法。 二、實驗內容 由用戶隨意輸入兩個串：主串 S和模式串 T，設 S= s1s2s n ， T= t1t2t m ，且 0
數(shù)據(jù)結構(嚴蔚敏)課件第4章.ppt
