數(shù)據(jù)結(jié)構(gòu)嚴蔚敏第4章ppt課件.ppt

第四章串 課前思考 從數(shù)據(jù)結(jié)構(gòu)的觀點來說 串是一種特殊的線性表 但就數(shù)據(jù)類型而言 串不是線性表 希望你帶著這個問題開始這一章的學習 并能在學完這一章的內(nèi)容之后能得出正確的結(jié)論 學習目標 1 理解 串 類型定義中各基本操作的特點 并能正確利用它們進行串的其它操作 2 理解串類型的各種存儲表示方法 3 理解串匹配的各種算法 重點和難點 相對于其它各個知識點而言 本章非整個課程的重點 鑒于串已是多數(shù)高級語言中已經(jīng)實現(xiàn)的數(shù)據(jù)類型 因此本章重點僅在于了解串類型定義中各基本操作的定義以及串的實現(xiàn)方法 并學會利用這些基本操作來實現(xiàn)串的其它操作 本章的難點是理解實現(xiàn)串匹配的KMP算法的思想 但它不屬本章學習的基本要求 更不是重點學習內(nèi)容 知識點 串的類型定義 串的存儲表示 串匹配 KMP算法 學習指南 雖然目前各常用的高級語言中都已經(jīng)實現(xiàn)了串類型 但由于它是通過軟件實現(xiàn)的 因此作為一個軟件工作者還是應(yīng)該了解串的實現(xiàn)方法 本章沒有必須完成的算法設(shè)計題 如果有興趣可以試試以下幾個題 4 10 4 11 4 13 4 17 4 18 4 23 4 28 4 30 其中前6個是練習串的基本操作的應(yīng)用 后2個是和KMP算法相關(guān)的練習 4 1串類型的定義 4 2串的表示和實現(xiàn) 4 3串的模式匹配算法 4 1串的類型定義 一 基本概念 1 串的定義串 string 是由零個或多個字符組成的有限序列 記作s a1a2 an 其中s為串的名字 用成對的單引號括起來的字符序列為串的值 但兩邊的引號不算串值 不包含在串中 ai 1 i n 可以是字母 數(shù)字或其它字符 n為串中字符的個數(shù) 稱為串的長度 2 空串不含任何字符的串稱為空串 它的長度n 0 記為s 3 空格串含有一個或多個空格的串 稱為空格串 它的長度n為空格的個數(shù) 一般用符號 表示空串 串是有限長的字符序列 由一對單引號相括 如 astring 4 子串 主串通常將字符在串中的序號稱為該字符在串中的位置 子串在主串中的位置則以子串的第一個字符在主串中的位置來表示 若一個串是另一個串中連續(xù)的一段 則這個串稱為另一個串的子串 而另一個串相對于該串稱為主串 例如 串s1 abcdefg s2 fabcdefghxyz 則s1為s2的子串 s2相對于s1為主串 另外 空串是任意串的子串 任意串是自身的子串 若一個串的長度為n 則它的子串數(shù)目為 1 真子串個數(shù)為 除串本身以外的子串都稱為真子串 當且僅當兩個串的值相等時 稱這兩個串是相等的 即只有當兩個串的長度相等 并且每個對應(yīng)位置的字符都相等時才相等 二 串的抽象數(shù)據(jù)類型的定義如下 ADTString 數(shù)據(jù)對象 D ai ai CharacterSet i 1 2 n n 0 數(shù)據(jù)關(guān)系 R1 ai 1 ai D i 2 n 基本操作 StrAssign T chars StrCopy T S DestroyString S StrEmpty S StrCompare S T StrLength S Concat T S1 S2 SubString Sub S pos len Index S T pos Replace S T V StrInsert S pos T StrDelete S pos len ClearString S ADTString StrAssign T chars 初始條件 chars是字符串常量 操作結(jié)果 把chars賦為T的值 StrCopy T S 初始條件 串S存在 操作結(jié)果 由串S復制得串T DestroyString S 初始條件 串S存在 操作結(jié)果 串S被銷毀 StrEmpty S 初始條件 串S存在 操作結(jié)果 若S為空串 則返回TRUE 否則返回FALSE 表示空串 空串的長度為零 StrCompare S T 初始條件 串S和T存在 操作結(jié)果 若S T 則返回值 0 若S T 則返回值 0 若S T 則返回值 0 例如 StrCompare data state 0 StrLength S 初始條件 串S存在 操作結(jié)果 返回S的元素個數(shù) 稱為串的長度 Concat T S1 S2 初始條件 串S1和S2存在 操作結(jié)果 用T返回由S1和S2聯(lián)接而成的新串 例如 Concate T man kind 求得T mankind SubString Sub S pos len 初始條件 串S存在 1 pos StrLength S 且0 len StrLength S pos 1 操作結(jié)果 用Sub返回串S的第pos個字符起長度為len的子串 例如 SubString sub commander 4 3 求得sub man SubString sub commander 1 9 求得sub commander SubString sub commander 9 1 求得sub r 子串為 串 中的一個字符子序列 SubString sub commander 4 7 sub SubString sub beijing 7 2 sub SubString student 5 0 起始位置和子串長度之間存在約束關(guān)系 長度為0的子串為 合法 串 Index S T pos 初始條件 串S和T存在 T是非空串 1 pos StrLength S 操作結(jié)果 若主串S中存在和串T值相同的子串 則返回它在主串S中第pos個字符之后第一次出現(xiàn)的位置 否則函數(shù)值為0 假設(shè)S abcaabcaaabc T bca Index S T 1 2 Index S T 2 6 Index S T 8 0 子串在主串中的位置 意指子串中的第一個字符在主串中的位序 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 StrInsert S pos T 初始條件 串S和T存在 1 pos StrLength S 1 操作結(jié)果 在串S的第pos個字符之前插入串T 例如 S chater T rac 則執(zhí)行StrInsert S 4 T 之后得到S character StrDelete S pos len 初始條件 串S存在1 pos StrLength S len 1 操作結(jié)果 從串S中刪除第pos個字符起長度為len的子串 ClearString S 初始條件 串S存在 操作結(jié)果 將S清為空串 對于串的基本操作集可以有不同的定義方法 在使用高級程序設(shè)計語言中的串類型時 應(yīng)以該語言的參考手冊為準 gets str 輸入一個串 puts str 輸出一個串 strcat str1 str2 串聯(lián)接函數(shù) strcpy str1 str2 k 串復制函數(shù) strcmp str1 str2 串比較函數(shù) strlen str 求串長函數(shù) 例如 C語言函數(shù)庫中提供下列串處理函數(shù) 在上述抽象數(shù)據(jù)類型定義的13種操作中 串賦值StrAssign 串復制Strcopy 串比較StrCompare 求串長StrLength 串聯(lián)接Concat以及求子串SubString等六種操作構(gòu)成串類型的最小操作子集 即 這些操作不可能利用其他串操作來實現(xiàn) 反之 其他串操作 除串清除ClearString和串銷毀DestroyString外 可在這個最小操作子集上實現(xiàn) 例如 可利用串比較 求串長和求子串等操作實現(xiàn)定位函數(shù)Index S T pos StrCompare SubString S i StrLength T T 0 S串 T串 T串 i pos n m 1 算法的基本思想為 intIndex StringS StringT intpos T為非空串 若主串S中第pos個字符之后存在與T相等的子串 則返回第一個這樣的子串在S中的位置 否則返回0if pos 0 n StrLength S m StrLength T i pos while i n m 1 SubString sub S i m if StrCompare sub T 0 i elsereturni while ifreturn0 S中不存在與T相等的子串 Index 又如串的置換函數(shù) Replace S T V S串 T串 V串 V串 pos pos sub i news串 sub 串的邏輯結(jié)構(gòu)和線性表極為相似 區(qū)別僅在于串的數(shù)據(jù)對象約束為字符集 串的基本操作和線性表有很大差別 在線性表的基本操作中 大多以 單個元素 作為操作對象 在串的基本操作中 通常以 串的整體 作為操作對象 在程序設(shè)計語言中 串只是作為輸入或輸出的常量出現(xiàn) 則只需存儲此串的串值 即字符序列即可 但在多數(shù)非數(shù)值處理的程序中 串也以變量的形式出現(xiàn) 4 2串的表示和實現(xiàn) 一 串的定長順序存儲表示 二 串的堆分配存儲表示 三 串的塊鏈存儲表示 一 串的定長順序存儲表示 與前面所講的線性表的順序存儲結(jié)構(gòu)類似 用一組地址連續(xù)的存儲單元存儲串的字符序列 常常將定長順序串設(shè)計成一種結(jié)構(gòu)類型 串的存儲分配是在編譯時完成的 defineMAXSTRLEN255 用戶可在255以內(nèi)定義最大串長typedefunsignedcharSstring MAXSTRLEN 1 0號單元存放串的長度 或 typedefstruct 串結(jié)構(gòu)定義 charch MAXLEN intlen SString 按這種串的表示方法實現(xiàn)的串的運算時 其基本操作為 字符序列的復制 串的實際長度可在這個予定義長度的范圍內(nèi)隨意設(shè)定 超過予定義長度的串值則被舍去 稱之為 截斷 特點 StatusConcat SStringS1 SStringS2 SString Concat 例如 串的聯(lián)接算法中需分三種情況處理 T 1 S1 0 S1 1 S1 0 T S1 0 1 S1 0 S2 0 S2 1 S2 0 T 0 S1 0 S2 0 uncut TRUE if S1 0 S2 0 MAXSTRLEN 未截斷 elseif S1 0 MAXSTRSIZE 截斷 else 截斷 僅取S1 T 1 S1 0 S1 1 S1 0 T S1 0 1 MAXSTRLEN S2 1 MAXSTRLEN S1 0 T 0 MAXSTRLEN uncut FALSE T 0 MAXSTRLEN S1 0 MAXSTRLEN T 0 S1 0 MAXSTRLENuncut FALSE 1 串插入函數(shù) StrInsert s pos t 在串s中序號為pos的字符之前插入串t SString s t intpos inti 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 定長順序存儲的操作實施 算法串插入函數(shù) elseif pos t lenMAXLEN 但串t的字符序列可以全部插入 for i MAXSTRLEN 1 i t 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 串刪除函數(shù) StrDelete s pos len 在串s中刪除從序號pos起len個字符 SString s intpos len inti if pos s len len return 0 for i pos len ilen i s ch i len s ch i s len s len len return 1 算法串刪除函數(shù) 3 串復制函數(shù) StrCopy s t 將串t的值復制到串s中 SString s t inti for i 0 ich i t ch i s len t len 算法串復制函數(shù) 4 判空函數(shù) StrEmpty s 若串s為空 即串長為0 則返回1 否則返回0 SStrings if s len 0 return 1 elsereturn 0 算法判空函數(shù) 5 串比較函數(shù) StrCompare s t 若串s和t相等 則返回0 若s t 則返回1 若s t 則返回 1 SStrings t inti for i 0 i s len 算法串比較函數(shù) 6 求串長函數(shù) StrLength s 返回串s的長度 SStrings return s len 算法求串長函數(shù) 7 清空函數(shù) StrClear s 將串s置為空串 SString s s len 0 return 1 算法清空函數(shù) 8 連接函數(shù) Concat s t 將串t連接在串s的后面 SString s t inti flag if s len t lenlen ilen t len i s ch i t ch i s len s len t len flag 1 elseif s lenlen ich i t ch i s len s len MAXSTRLEN flag 0 elseflag 0 串s的長度等于MAXLEN 串t不被連接 return flag 算法連接函數(shù) 9 求子串函數(shù) SubString sub s pos len 將串s中序號pos起len個字符復制到sub中 SString sub s intpos len inti if poss len lens len pos sub len 0 return 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中的位置 SStrings t intpos inti j if t len 0 return 0 i pos j 0 while i t len return i t len elsereturn 0 算法定位函數(shù) typedefstruct char ch 若是非空串 則按串長分配存儲區(qū) 否則ch為NULLintlength 串長度 HString 二 串的堆分配存儲表示 特點 仍用一組地址連續(xù)的存儲單元存儲串的字符序列 但其存儲空間是在程序執(zhí)行過程中動態(tài)分配而得 通常 C語言中提供的串類型就是以這種存儲方式實現(xiàn)的 系統(tǒng)利用函數(shù)malloc 和free 進行串值空間的動態(tài)管理 為每一個新產(chǎn)生的串分配一個存儲區(qū) 稱串值共享的存儲空間為 堆 C語言中的串以一個空字符為結(jié)束符 串長是一個隱含值 這類串操作實現(xiàn)的算法為 先為新生成的串分配一個存儲空間 然后進行串值的復制 StatusConcat HString Concat StatusSubString HString SubString Sub ch char malloc len sizeof char Sub ch 0 len 1 S pos 1 pos len 2 Sub length len 三 串的塊鏈存儲表示 也可用鏈表來存儲串值 由于串的數(shù)據(jù)元素是一個字符 它只有8位二進制數(shù) 因此用鏈表存儲時 通常一個結(jié)點中存放的不是一個字符 而是一個子串 存儲密度 數(shù)據(jù)元素所占存儲位 實際分配的存儲位 defineCHUNKSIZE80 可由用戶定義的塊大小typedefstructChunk 結(jié)點結(jié)構(gòu)charch CHUNKSIZE structChunk next Chunk typedefstruct 串的鏈表結(jié)構(gòu)Chunk head tail 串的頭和尾指針intcurlen 串的當前長度 LString 例如 在編輯系統(tǒng)中 整個文本編輯區(qū)可以看成是一個串 每一行是一個子串 構(gòu)成一個結(jié)點 即 同一行的串用定長結(jié)構(gòu) 80個字符 行和行之間用指針相聯(lián)接 實際應(yīng)用時 可以根據(jù)問題所需來設(shè)置結(jié)點的大小 這是串的一種重要操作 很多軟件 若有 編輯 菜單項的話 則其中必有 查找 子菜單項 4 3串的模式匹配算法 子串的定位操作通常稱為串的模式匹配 是各種串處理系統(tǒng)中最重要的操作之一 初始條件 串S和T存在 T是非空串 1 pos StrLength S 操作結(jié)果 若主串S中存在和串T值相同的子串返回它在主串S中第pos個字符之后第一次出現(xiàn)的位置 否則函數(shù)值為0 首先 回憶一下串匹配 查找 的定義 INDEX S T pos 下面討論以定長順序結(jié)構(gòu)表示串時的幾種算法 一 簡單算法 二 首尾匹配算法 三 KMP D E Knuth V R Pratt J H Morris 算法 一 簡單算法Brute Force算法 例如 設(shè)目標串s cddcdc 模式串t cdc s的長度為n n 6 t的長度為m m 3 用指針i指示目標串s的當前比較字符位置 用指針j指示模式串t的當前比較字符位置 BF模式匹配過程如下所示 這個算法簡單 易于理解 但效率不高 主要原因是 主串指針i在若干個字符序列比較相等后 若有一個字符比較不相等 仍需回溯 即i i j 1 該算法在最好情況下的時間復雜度為O m 即主串的前m個字符正好等于模式串的m個字符 在最壞情況下的時間復雜度為O n m intindex SqStrings SqStringt inti 0 j 0 k while i t len k i t len 返回匹配的第一個字符的下標 elsek 1 模式匹配不成功 returnk 先比較模式串的第一個字符 再比較模式串的最后一個字符 最后比較模式串中從第二個到第n 1個字符 二 首尾匹配算法 intIndex FL SStringS SStringT intpos sLength S 0 tLength T 0 i pos patStartChar T 1 patEndChar T tLength while i sLength tLength 1 if S i patStartChar i 重新查找匹配起始點elseif S i tLength 1 patEndChar i 模式串的 尾字符 不匹配else return0 檢查中間字符的匹配情況 k 1 j 2 while j tLength 重新開始下一次的匹配檢測 三 模式匹配的改進算法 KMP算法 此方法由克努特 D E Knuth 莫里斯 J H Morris 普拉特 V R Pratt 同時發(fā)現(xiàn) 1 基本思想 每當一趟匹配過程中出現(xiàn)字符不等時 不需回溯i指針 而是利用已得到的部分匹配結(jié)果 將模式串向右滑動盡可能遠的一段距離后繼續(xù)進行比較 避免多余的 不必要的比較 從而提高算法性能 算法總在0 n m 的時間數(shù)量級上完成匹配操作 2 KMP算法匹配實例 1 模式串t中沒有真子串真子串是指模式串t存在某個k 0 k j 使得 t0t1 tk tj ktj k 1 tj 成立 例如t cdc 就是這樣的模式串 在圖4 6中的第一次回溯 當s0 t0 s1 t1 s2 t2時 算法中取i 1 j 0 使主串指針回溯一個位置 比較s1和t0 因t0 t1 所以一定有s1 t0 另外 因有t0 t2 s0 t0 s2 t2 則一定可推出s2 t0 所以也不必取i 2 j 0去比較s2和t0 可直接在第二次比較時取i 3 j 0 比較s3和t0 這樣 模式匹配過程主串指針i就可不必回溯 2 模式串中存在真子串例如t abab 由于 t0t1 t2t3 這里k 1 j 3 則存在真子串 設(shè)s abacabab t abab 第一次匹配過程如下所示 此時不必從i 1 i i j 1 1 j 0重新開始第二次匹配 因t0 t1 s1 t1 必有s1 t0 又因t0 t2 s2 t2 所以必有s2 t0 因此 第二次匹配可直接從i 3 j 1開始 現(xiàn)在我們討論一般情況 設(shè)s s0s1 sn 1 t t0t1 tm 1 當si tj 0 i n m 0 j m 時 存在 t0t1 tj 1 si jsi j 1 si 1 4 1 若模式串中存在的真子串滿足 t0t1 tk tj ktj k 1 tj 0 k j 4 2 由 4 1 式說明模式串中的子串 t0t1 tk 1 已和主串 si ksi k 1 si 1 匹配 下一次可直接比較si和tk 若不存在 4 2 式 則結(jié)合 4 1 式說明在 t0t1 tj 1 中不存在任何以t0為首字符子串與 si j 1si j 2 si 1 中以si 1為末字符的匹配子串 下一次可直接比較si和t0 為此 定義next j 函數(shù)如下 max k 0 k j 且 t0t1 tk 1 tj ktj k 1 tj 1 當此集合非空時 1當j 0時0其他情況 next j t abab 對應(yīng)的next數(shù)組如下 由模式串t求出next值的算法如下 voidGetNext SqStringt intnext intj k j 0 k 1 next 0 1 while j t len 1 if k 1 t ch j t ch k k為 1或比較的字符相等時 j k next j k elsek next k intKMPIndex SqStrings SqStringt KMP算法 intnext MaxSize i 0 j 0 v GetNext t next while i t len v i t len 返回匹配模式串的首字符下標 elsev 1 返回不匹配標志 returnv 設(shè)主串s的長度為n 子串t長度為m 在KMP算法中求next數(shù)組的時間復雜度為O m 在后面的匹配中因主串s的下標不減即不回溯 比較次數(shù)可記為n 所以KMP算法總的時間復雜度為O n m 例如 設(shè)目標串s aaabaaaab 模式串t aaaab s的長度為n n 9 t的長度為m m 5 用指針i指示目標串s的當前比較字符位置 用指針j指示模式串t的當前比較字符位置 KMP模式匹配過程如下所示 上述定義的next 在某些情況下尚有缺陷 例如 模式 aaaab 在和主串 aaabaaaab 匹配時 當i 3 j 3時 s ch 3 t ch 3 由next j 的指示還需進行i 3 j 2 i 3 j 1 i 3 j 0等三次比較 實際上 因為模式中的第1 2 3個字符和第4個字符都相等 因此 不需要再和主串中第4個字符相比較 而可以將模式一次向右滑動4個字符的位置直接進行i 4 j 0時的字符比較 KMP算法的改進 這就是說 若按上述定義得到next j k 而模式中pj pk 則為主串中字符si和pj比較不等時 不需要再和pk進行比較 而直接和pnext k 進行比較 換句話說 此時的next j 應(yīng)和next k 相同 為此將next j 修正為nextval j 由模式串t求出nextval值 voidGetNextval SqStringt intnextval intj 0 k 1 nextval 0 1 while j t len if k 1 t ch j t ch k j k if t ch j t ch k nextval j k elsenextval j nextval k elsek nextval k 本章小結(jié) 在這一章介紹了串類型的定義及其實現(xiàn)方法 并重點討論了串操作中最常用的 串定位操作 又稱模式匹配 的兩個算法 串的兩個顯著特點是 其一 它的數(shù)據(jù)元素都