【文章內(nèi)容簡介】 頭 1火 車 頭 1火車頭2火車頭2 堆棧抽象數(shù)據(jù)類型 １數(shù)據(jù)集合 堆棧的數(shù)據(jù)集合可以表示為 a0,a1,…,an 1，每個數(shù)據(jù)元素的數(shù)據(jù)類型可以是任意的類類型。 ２操作集合 （ 1）入棧 push(obj)：把數(shù)據(jù)元素 obj插入堆棧。 （ 2）出棧 pop()：出棧 , 刪除的數(shù)據(jù)元素由函數(shù)返回。 （ 3）取棧頂數(shù)據(jù)元素 getTop()：取堆棧當前棧頂?shù)臄?shù)據(jù)元素并由函數(shù)返回。 （ 4）非空否 notEmpty()：若堆棧非空則函數(shù)返回 true，否則函數(shù)返回 false。 順序堆棧 1 順序堆棧的存儲結構 順序存儲結構的堆棧稱作 順序堆棧 。 順序堆棧的存儲結構示意圖如圖所示 。 0 1 2 3 4 5m a x S t a c k S i z e 1=棧 頂s t a c kt o p棧 底 0a 1a 2a 4a3a 鏈式堆棧 鏈式存儲結構的堆棧稱作 鏈式堆棧 。 1 鏈式堆棧的存儲結構 和單鏈表相同 ， 鏈式堆棧也是由一個個結點組成的 ， 每個結點由兩個域組成 ， 一個是存放數(shù)據(jù)元素的數(shù)據(jù)元素域 element， 另一個是存放指向下一個結點的對象引用 （ 即指針 ） 域 next。 堆棧有兩端 ， 插入數(shù)據(jù)元素和刪除數(shù)據(jù)元素的一端為棧頂 ， 另一端為棧底 。 鏈式堆棧都設計成把靠近堆棧頭 head的一端定義為棧頂 。 依次向鏈式堆棧入棧數(shù)據(jù)元素 a0, a1, a2, ..., an1后，鏈式堆棧的示意圖如圖所示。 . . .0a2?na1?na ∧ 棧 頂 棧 底h e a d 堆棧是各種軟件系統(tǒng)中應用最廣泛的數(shù)據(jù)結構之一 。括號匹配和表達式計算是編譯軟件中的基本問題 ， 其軟件設計中都需要使用堆棧 。 括號匹配問題 表達式計算問題 堆棧的應用 隊列 隊列的基本概念 隊列 （簡稱作隊）也是一種特殊的線性表，隊列的數(shù)據(jù)元素以及數(shù)據(jù)元素間的邏輯關系和線性表完全相同，其差別是線性表允許在任意位置插入和刪除，而隊列只允許在其一端進行插入操作在其另一端進行刪除操作。 隊列中允許進行插入操作的一端稱為隊尾，允許進行刪除操作的一端稱為隊頭。隊列的插入操作通常稱作入隊列，隊列的刪除操作通常稱作出隊列。 下圖是一個依次向隊列中插入數(shù)據(jù)元素 a0,a1,...,an1后的示意圖，其中， a0是當前隊頭數(shù)據(jù)元素， an1是當前隊尾數(shù)據(jù)元素。 0a 1a 2a...1?na出隊頭入隊尾 隊列的抽象數(shù)據(jù)類型 1 數(shù)據(jù)集合 隊列的數(shù)據(jù)集合可以表示為 a0,a1,…,an 1，每個數(shù)據(jù)元素的數(shù)據(jù)類型可以是任意的類類型。 2 操作集合 （ 1）入隊列 append(obj)：把數(shù)據(jù)元素 obj插入隊尾。 （ 2）出隊列 delete()：把隊頭數(shù)據(jù)元素刪除并由函數(shù)返回。 （ 3）取隊頭數(shù)據(jù)元素 getFront()：取隊頭數(shù)據(jù)元素并由函數(shù)返回。 （ 4）非空否 notEmpty()：非空否。若隊列非空，則函數(shù)返回 true，否則函數(shù)返回 false。 隊列 抽象數(shù)據(jù)類型的 Java接口定義如下： public interface Queue{ public void append(Object obj) throws Exception。 public Object delete() throws Exception。 public Object getFront() throws Exception。 public boolean notEmpty()。 } 順序隊列 1 順序隊列的存儲結構 下圖是一個有 6個存儲空間的順序隊列的動態(tài)示意圖，圖中 front指示隊頭， rear指示隊尾。 43210=5frontrearCBA432105front=rear=C432105front=rear=EDC432105front=rear=(a) (b) (c) (d)2 順序隊列的“假溢出”問題 順序隊列因多次入隊列和出隊列操作后出現(xiàn)的有存儲空間但不能進行入隊列操作的溢出稱作 假溢出 。 EDC43210F5front=6rear=3 順序循環(huán)隊列的基本原理 假溢出是由于隊尾 rear的值和隊頭 front的值不能由所定義數(shù)組下界值自動轉(zhuǎn)為數(shù)組上界值而產(chǎn)生的。因此，解決的方法是把順序隊列所使用的存儲空間構造成一個邏輯上首尾相連的循環(huán)隊列。 當 rear和 front達到 maxSize1后，再加 1就自動到 0。這樣，就不會出現(xiàn)順序隊列數(shù)組的頭部已空出許多存儲空間，但隊尾卻因數(shù)組下標越界而引起溢出的假溢出問題。 4 順序循環(huán)隊列的隊空和隊滿判斷問題 順序循環(huán)隊列的隊列滿和隊列空狀態(tài) （ a）初始化狀態(tài)；（ b）隊列滿狀態(tài)；（ c）隊列空狀態(tài) 154 032EDFABC154 032rear=0front=0rear=0front=0154 032rear=0front=0(a) (b) (c) 解決順序循環(huán)隊列的隊列滿和隊列空狀態(tài)判斷問題通常有三種方法： （ 1） 少用一個存儲空間 當少用一個存儲空間時，以隊尾 rear加 1等于隊頭 front為隊列滿的判斷條件，即隊列滿的判斷條件此時為： (rear + 1) % maxSize == front 隊列空的判斷條件仍然為： rear = = front （ 2） 設置一個標志位 添加一個標志位。設標志位為 tag，初始時置 tag=0；每當入隊列操作成功就置 tag=1；每當出隊列操作成功就置 tag=0。則隊列空的判斷條件為： rear == front amp。amp。 tag==0 隊列滿的判斷條件為： rear = = front amp。amp。 tag= =1 （ 3） 設置一個計數(shù)器 添加一個計數(shù)器。設計數(shù)器為 count，初始時置count=0；每當入隊列操作成功就使 count加 1；每當出隊列操作成功就使 count減 1。這樣，該計數(shù)器不僅具有計數(shù)功能，而且還具有像標志位一樣的標志作用，則此時隊列空的判斷條件為： count == 0 隊列滿的判斷條件為： count 0 amp。amp。 rear == front 順序循環(huán)隊列類 鏈式隊列 鏈式存儲結構的隊列稱作 鏈式隊列 。 1 鏈式隊列的存儲結構 0a. . .1a 1?na∧ 2?na r e a rf r o n t 優(yōu)先級隊列 優(yōu)先級隊列 是帶有優(yōu)先級的隊列。 用順序存儲結構實現(xiàn)的優(yōu)先級隊列稱作 順序優(yōu)先級隊列 。 用鏈式存儲結構存儲的優(yōu)先級隊列稱作 鏈式優(yōu)先級隊列 。 順序優(yōu)先級隊列類 順序優(yōu)先級隊列和順序循環(huán)隊列相比主要有兩點不同： （ 1）對于順序優(yōu)先級隊列來說，出隊列操作不是把隊頭數(shù)據(jù)元素出隊列，而是把隊列中優(yōu)先級最高的數(shù)據(jù)元素出隊列。 （ 2）對于順序優(yōu)先級隊列來說，數(shù)據(jù)元素由兩部分組成，一部分是原先意義上的數(shù)據(jù)元素，另一部分是優(yōu)先級。通常設計優(yōu)先級為 int類型的數(shù)值，并規(guī)定數(shù)值越小優(yōu)先級越高。 優(yōu)先級隊列的應用 操作系統(tǒng)中的進程管理軟件中就使用了優(yōu)先級隊列。操作系統(tǒng)中使用一個優(yōu)先級隊列來管理進程。當優(yōu)先級隊列中有若干個進程排隊等待系統(tǒng)響應，并且 CPU資源空閑時，進程管理系統(tǒng)就可從優(yōu)先級隊列中找出優(yōu)先級最高的進程首先出隊列，從而既達到了當系統(tǒng)繁忙時，所有進程都排隊等待，又達到了實時性要求高的進程先被服務的雙重要求。 第 4章 串 串的基本概念及其抽象數(shù)據(jù) 串的存儲結構 串類 串的模式匹配算法 本章主要知識點： ● 串的基本概念 ● 串的存儲結構 ● 串類的設計方法，主要是拷貝、插入子串和刪除子串的設計方法 ● 串的模式匹配算法，包括 BruteForce算法和 KMP算法 串的基本概念及其抽象數(shù)據(jù)類型 串的基本概念 串 （也稱作字符串）是由 n（ n≥0）個字符組成的有限序列。 一個串中任意個連續(xù)的字符組成的子序列稱為該串的子串 。 包含子串的串稱為該子串的 主串 。 一個字符在一個串中的位置序號（為大于等于 0的正整數(shù)）稱為該字符在串中的 位置 。當且僅當這兩個串的值完全相等時，稱這兩個串 相等 。 串的抽象數(shù)據(jù)類型 數(shù)據(jù)集合： 串的數(shù)據(jù)集合可以表示為字符序列 s0, s1,… , sn 1， 每個數(shù)據(jù)元素的數(shù)據(jù)類型為字符類型。 操作集合： （ 1）取字符 charAt(index) ：取 index下標的字符返回。 （ 2）求長度 length()：返回串的長度。 （ 3）比較 pareTo(anotherString)：比較當前對象串和串 anotherString的 Unicode碼值的大小。 （ 4）取子串 substring(beginIndex, endIndex)：取當前對象串中從 beginIndex下標開始、至 endIndex下標的前一下標止的子串 （ 5）連接 concat(str)：把串 str連接到當前對象串的末尾。 （ 6）插入子串 insert(str, pos)：在當前對象串的第 pos個字符前插入子串 str。 （ 7）刪除子串 delete(beginIndex, endIndex)：刪除當前對象串中從 beginIndex下標開始、至 endIndex下標的前一下標止的子串 。 （ 8）輸出串值 myPrint()：輸出當前對象的串值。 （ 9）查找子串 index(subStr, start)：在當前對象串的start下標開始，查找是否存在子串 subStr。 串的存儲結構 1 串的順序存儲結構 串的順序存儲結構就是用字符類型數(shù)組存放串的所有字符。 表示串的長度通常有兩種方法： （ 1）設置一個串的長度參數(shù)。 （ 2）在串值的末尾添加結束標記 。 串值長度的第一種表示方法下，串的成員變量應包括如下兩項： char[] value。 int count。 其中， value為存儲串值的字符類型數(shù)組名， count表示串值的長度。 2 串的鏈式存儲結構 串的鏈式存儲結構就是把串值分別存放在構成鏈表的若干個結點的數(shù)據(jù)元素域上。 有單字符結點鏈和塊鏈兩種。 單字符結點鏈就是每個結點的數(shù)據(jù)元素域只包括一個字符。 塊鏈就是每個結點的數(shù)據(jù)元素域包括若干個字符。 串類 MyString類 MyString類的測試 MyStringBuffer類 MyStringBuffer類的測試 串的模式匹配算法 BruteForce算法 （ 1）從主串 s的第一個字符開始和模式串 t的第一個字符比較 ,若相等則繼續(xù)比較后續(xù)字符； （ 2）若主串 s的第一個字符和模式串 t的第一個字符比較不相等，則從主串 s的第二個字符開始重新與模式串 t的第一個字符比較，若相等則繼續(xù)比較后續(xù)字符 （ 3）若主串 s的第二個字符與模式串 t的第一個字符比較不相等，則從主串 s的第三個字符開始重新與模式串 t的第一個字符比較； （ 4）如此不斷繼續(xù)。若存在模式串 t中的每個字符依次和主串 s中的一個連續(xù)字符序列相等，則模式匹配成功，函數(shù)返回模式串 t的第一個字符在主串 s中的下標；若比較完主串 s的所有字符序列，不存在一個和模式串 t相等的子串，則模式匹配失敗，函數(shù)返回 1。 設主串 s=“cddcdc”,模式串 t=“cdc”,模式匹配過程如圖： 第一次匹配 s = c d d c d ct = c d ci=2j=2失