【正文】 .ia 1?na∧ so b j. . .1?iapn e x td a t a在單鏈表非第一個(gè)結(jié)點(diǎn)前插入結(jié)點(diǎn)過程 要在第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)前插入一個(gè)新結(jié)點(diǎn)，若采用不帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)，則結(jié)點(diǎn)插入后，頭指針 head就要等于新插入結(jié)點(diǎn) s，這和在非第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)前插入結(jié)點(diǎn)時(shí)的情況不同。因此，算法對(duì)這兩種情況就要分別設(shè)計(jì)實(shí)現(xiàn)方法。 因此 ， 算法實(shí)現(xiàn)方法比較簡單 。 h e a d( b ). . .0a 1a 1?na∧ so b j∧ h e a d. . .0a 1a 1?na∧ o b j( a )sn e x td a t app圖在帶頭結(jié)點(diǎn)單鏈表第一個(gè)結(jié)點(diǎn)前插入結(jié)點(diǎn)過程 結(jié)點(diǎn)類 單鏈表是由一個(gè)一個(gè)結(jié)點(diǎn)組成的 ， 因此 ， 要設(shè)計(jì)單鏈表類 ， 必須先設(shè)計(jì)結(jié)點(diǎn)類 。 單鏈表類 單鏈表類的成員變量至少要有兩個(gè)：一個(gè)是頭指針 ， 另一個(gè)是單鏈表中的數(shù)據(jù)元素個(gè)數(shù) 。 單鏈表的效率分析 在單鏈表的任何位置上插入數(shù)據(jù)元素的概率相等時(shí) ，在單鏈表中插入一個(gè)數(shù)據(jù)元素時(shí)比較數(shù)據(jù)元素的平均次數(shù)為： 2)(11)(00ninninpEniniiis ?????? ???? 刪除單鏈表的一個(gè)數(shù)據(jù)元素時(shí)比較數(shù)據(jù)元素的平均次數(shù)為： 21)(1)( 1010?????? ?? ????ninninqEniniidl 因此，單鏈表插入和刪除操作的時(shí)間復(fù)雜度均為 O（ n）。 順序表和單鏈表的比較 順序表的主要優(yōu)點(diǎn)是支持隨機(jī)讀取，以及內(nèi)存空間利用效率高；順序表的主要缺點(diǎn)是需要預(yù)先給出數(shù)組的最大數(shù)據(jù)元素個(gè)數(shù)，而這通常很難準(zhǔn)確作到。另外，順序表插入和刪除操作時(shí)需要移動(dòng)較多的數(shù)據(jù)元素。另外，單鏈表插入和刪除操作時(shí)不需要移動(dòng)數(shù)據(jù)元素。另外，單鏈表不支持隨機(jī)讀取，單鏈表取數(shù)據(jù)元素操作的時(shí)間復(fù)雜度為 O（ n）；而順序表支持隨機(jī)讀取，順序表取數(shù)據(jù)元素操作的時(shí)間復(fù)雜度為 O（ 1）。 和單鏈表相比 ， 循環(huán)單鏈表的長處是從鏈尾到鏈頭比較方便 。 循環(huán)單鏈表 和單鏈表相同 ， 循環(huán)單鏈表也有帶頭結(jié)點(diǎn)結(jié)構(gòu)和不帶頭結(jié)點(diǎn)結(jié)構(gòu)兩種 ， 帶頭結(jié)點(diǎn)的循環(huán)單鏈表實(shí)現(xiàn)插入和刪除操作時(shí) ， 算法實(shí)現(xiàn)較為方便 。 （ 2） 在 index(i)成員函數(shù)中 ， 把循環(huán)結(jié)束判斷條件current != null改為 current != head。 和單鏈表類同 ， 雙向鏈表也有帶頭結(jié)點(diǎn)結(jié)構(gòu)和不帶頭結(jié)點(diǎn)結(jié)構(gòu)兩種 ， 帶頭結(jié)點(diǎn)的雙向鏈表更為常用；另外 ， 雙向鏈表也可以有循環(huán)和非循環(huán)兩種結(jié)構(gòu) ， 循環(huán)結(jié)構(gòu)的雙向鏈表更為常用 。圖 212為雙向鏈表結(jié)點(diǎn)的圖示結(jié)構(gòu)。從圖 213可見，循環(huán)雙向鏈表的 next和 prior各自構(gòu)成自己的循環(huán)單鏈表。 圖 214是雙向鏈表上述關(guān)系的圖示 。 圖中的指針 p表示要插入結(jié)點(diǎn)的位置 ， s表示要插入的結(jié)點(diǎn) ， ① 、② 、 ③ 、 ④ 表示實(shí)現(xiàn)插入過程的步驟 。 圖中的指針 p表示要插入結(jié)點(diǎn)的位置 ， ① 、 ② 表示實(shí)現(xiàn)刪除過程的步驟 。我們也可以用數(shù)組來構(gòu)造仿真鏈表。我們把這些 int類型變量構(gòu)造的指針稱為 仿真指針 。 AB12C 3D 4E 101234m a x S i z e 1...e l e m e n t n e x tAE2 1B 4D 1C 301234m a x S i z e 1...n e x t......( a )( b )( c )A B C D E∧ h e a de l e m e n te l e m e n t n e x t（ a）常規(guī)單鏈表；（ b）仿真單鏈表一；（ c）仿真單鏈表二 面向?qū)ο蟮能浖O(shè)計(jì)方法 面向?qū)ο筌浖O(shè)計(jì)方法是一種和人類認(rèn)識(shí)事物、分析事物方法一致的軟件設(shè)計(jì)方法。 模塊化軟件設(shè)計(jì)的基本思想是：把基礎(chǔ)軟件設(shè)計(jì)成可重復(fù)使用的模塊，這些模塊提供外部調(diào)用的接口，其他程序通過接口使用這些基礎(chǔ)軟件模塊。 第 3章 堆棧和隊(duì)列 堆棧 堆棧的應(yīng)用 隊(duì)列 優(yōu)先級(jí)隊(duì)列 本章主要知識(shí)點(diǎn)： ● 堆棧的基本概念，堆棧的用途 ● 順序堆棧類的設(shè)計(jì)方法，鏈?zhǔn)蕉褩ｎ惖脑O(shè)計(jì)方法 ● 隊(duì)列的基本概念，隊(duì)列的用途 ● 順序循環(huán)隊(duì)列的基本實(shí)現(xiàn)原理，順序循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿判斷方法，順序循環(huán)隊(duì)列類的設(shè)計(jì)方法 ● 鏈?zhǔn)蕉褩ｎ惖脑O(shè)計(jì)方法 ● 優(yōu)先級(jí)隊(duì)列的概念，優(yōu)先級(jí)隊(duì)列的用途，順序優(yōu)先級(jí) 隊(duì)列的入隊(duì)列和出隊(duì)列操作設(shè)計(jì)方法 堆棧 堆棧的基本概念 堆棧 （也簡稱作棧）是一種特殊的線性表，堆棧的數(shù)據(jù)元素以及數(shù)據(jù)元素間的邏輯關(guān)系和線性表完全相同，其差別是線性表允許在任意位置進(jìn)行插入和刪除操作，而堆棧只允許在固定一端進(jìn)行插入和刪除操作。堆棧的插入和刪除操作通常稱為進(jìn)?；蛉霔?，堆棧的刪除操作通常稱為出?；蛲藯?。 ( a )( c )( b )火 車 頭 1火 車 頭 1火車頭2火車頭2 堆棧抽象數(shù)據(jù)類型 １數(shù)據(jù)集合 堆棧的數(shù)據(jù)集合可以表示為 a0,a1,…,an 1，每個(gè)數(shù)據(jù)元素的數(shù)據(jù)類型可以是任意的類類型。 （ 2）出棧 pop()：出棧 , 刪除的數(shù)據(jù)元素由函數(shù)返回。 （ 4）非空否 notEmpty()：若堆棧非空則函數(shù)返回 true，否則函數(shù)返回 false。 順序堆棧的存儲(chǔ)結(jié)構(gòu)示意圖如圖所示 。 1 鏈?zhǔn)蕉褩５拇鎯?chǔ)結(jié)構(gòu) 和單鏈表相同 ， 鏈?zhǔn)蕉褩Ｒ彩怯梢粋€(gè)個(gè)結(jié)點(diǎn)組成的 ， 每個(gè)結(jié)點(diǎn)由兩個(gè)域組成 ， 一個(gè)是存放數(shù)據(jù)元素的數(shù)據(jù)元素域 element， 另一個(gè)是存放指向下一個(gè)結(jié)點(diǎn)的對(duì)象引用 （ 即指針 ） 域 next。 鏈?zhǔn)蕉褩６荚O(shè)計(jì)成把靠近堆棧頭 head的一端定義為棧頂 。 . . .0a2?na1?na ∧ 棧 頂 棧 底h e a d 堆棧是各種軟件系統(tǒng)中應(yīng)用最廣泛的數(shù)據(jù)結(jié)構(gòu)之一 。 括號(hào)匹配問題 表達(dá)式計(jì)算問題 堆棧的應(yīng)用 隊(duì)列 隊(duì)列的基本概念 隊(duì)列 （簡稱作隊(duì)）也是一種特殊的線性表，隊(duì)列的數(shù)據(jù)元素以及數(shù)據(jù)元素間的邏輯關(guān)系和線性表完全相同，其差別是線性表允許在任意位置插入和刪除，而隊(duì)列只允許在其一端進(jìn)行插入操作在其另一端進(jìn)行刪除操作。隊(duì)列的插入操作通常稱作入隊(duì)列，隊(duì)列的刪除操作通常稱作出隊(duì)列。 0a 1a 2a...1?na出隊(duì)頭入隊(duì)尾 隊(duì)列的抽象數(shù)據(jù)類型 1 數(shù)據(jù)集合 隊(duì)列的數(shù)據(jù)集合可以表示為 a0,a1,…,an 1，每個(gè)數(shù)據(jù)元素的數(shù)據(jù)類型可以是任意的類類型。 （ 2）出隊(duì)列 delete()：把隊(duì)頭數(shù)據(jù)元素刪除并由函數(shù)返回。 （ 4）非空否 notEmpty()：非空否。 隊(duì)列 抽象數(shù)據(jù)類型的 Java接口定義如下： public interface Queue{ public void append(Object obj) throws Exception。 public Object getFront() throws Exception。 } 順序隊(duì)列 1 順序隊(duì)列的存儲(chǔ)結(jié)構(gòu) 下圖是一個(gè)有 6個(gè)存儲(chǔ)空間的順序隊(duì)列的動(dòng)態(tài)示意圖，圖中 front指示隊(duì)頭， rear指示隊(duì)尾。 EDC43210F5front=6rear=3 順序循環(huán)隊(duì)列的基本原理 假溢出是由于隊(duì)尾 rear的值和隊(duì)頭 front的值不能由所定義數(shù)組下界值自動(dòng)轉(zhuǎn)為數(shù)組上界值而產(chǎn)生的。 當(dāng) rear和 front達(dá)到 maxSize1后，再加 1就自動(dòng)到 0。 4 順序循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿判斷問題 順序循環(huán)隊(duì)列的隊(duì)列滿和隊(duì)列空狀態(tài) （ a）初始化狀態(tài)；（ b）隊(duì)列滿狀態(tài)；（ c）隊(duì)列空狀態(tài) 154 032EDFABC154 032rear=0front=0rear=0front=0154 032rear=0front=0(a) (b) (c) 解決順序循環(huán)隊(duì)列的隊(duì)列滿和隊(duì)列空狀態(tài)判斷問題通常有三種方法： （ 1） 少用一個(gè)存儲(chǔ)空間 當(dāng)少用一個(gè)存儲(chǔ)空間時(shí)，以隊(duì)尾 rear加 1等于隊(duì)頭 front為隊(duì)列滿的判斷條件，即隊(duì)列滿的判斷條件此時(shí)為： (rear + 1) % maxSize == front 隊(duì)列空的判斷條件仍然為： rear = = front （ 2） 設(shè)置一個(gè)標(biāo)志位 添加一個(gè)標(biāo)志位。則隊(duì)列空的判斷條件為： rear == front amp。 tag==0 隊(duì)列滿的判斷條件為： rear = = front amp。 tag= =1 （ 3） 設(shè)置一個(gè)計(jì)數(shù)器 添加一個(gè)計(jì)數(shù)器。這樣，該計(jì)數(shù)器不僅具有計(jì)數(shù)功能，而且還具有像標(biāo)志位一樣的標(biāo)志作用，則此時(shí)隊(duì)列空的判斷條件為： count == 0 隊(duì)列滿的判斷條件為： count 0 amp。 rear == front 順序循環(huán)隊(duì)列類 鏈?zhǔn)疥?duì)列 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的隊(duì)列稱作 鏈?zhǔn)疥?duì)列 。 用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的優(yōu)先級(jí)隊(duì)列稱作 順序優(yōu)先級(jí)隊(duì)列 。 順序優(yōu)先級(jí)隊(duì)列類 順序優(yōu)先級(jí)隊(duì)列和順序循環(huán)隊(duì)列相比主要有兩點(diǎn)不同： （ 1）對(duì)于順序優(yōu)先級(jí)隊(duì)列來說，出隊(duì)列操作不是把隊(duì)頭數(shù)據(jù)元素出隊(duì)列，而是把隊(duì)列中優(yōu)先級(jí)最高的數(shù)據(jù)元素出隊(duì)列。通常設(shè)計(jì)優(yōu)先級(jí)為 int類型的數(shù)值，并規(guī)定數(shù)值越小優(yōu)先級(jí)越高。操作系統(tǒng)中使用一個(gè)優(yōu)先級(jí)隊(duì)列來管理進(jìn)程。 第 4章 串 串的基本概念及其抽象數(shù)據(jù) 串的存儲(chǔ)結(jié)構(gòu) 串類 串的模式匹配算法 本章主要知識(shí)點(diǎn)： ● 串的基本概念 ● 串的存儲(chǔ)結(jié)構(gòu) ● 串類的設(shè)計(jì)方法，主要是拷貝、插入子串和刪除子串的設(shè)計(jì)方法 ● 串的模式匹配算法，包括 BruteForce算法和 KMP算法 串的基本概念及其抽象數(shù)據(jù)類型 串的基本概念 串 （也稱作字符串）是由 n（ n≥0）個(gè)字符組成的有限序列。 包含子串的串稱為該子串的 主串 。當(dāng)且僅當(dāng)這兩個(gè)串的值完全相等時(shí)，稱這兩個(gè)串 相等 。 操作集合： （ 1）取字符 charAt(index) ：取 index下標(biāo)的字符返回。 （ 3）比較 pareTo(anotherString)：比較當(dāng)前對(duì)象串和串 anotherString的 Unicode碼值的大小。 （ 6）插入子串 insert(str, pos)：在當(dāng)前對(duì)象串的第 pos個(gè)字符前插入子串 str。 （ 8）輸出串值 myPrint()：輸出當(dāng)前對(duì)象的串值。 串的存儲(chǔ)結(jié)構(gòu) 1 串的順序存儲(chǔ)結(jié)構(gòu) 串的順序存儲(chǔ)結(jié)構(gòu)就是用字符類型數(shù)組存放串的所有字符。 （ 2）在串值的末尾添加結(jié)束標(biāo)記 。 int count。 2 串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)就是把串值分別存放在構(gòu)成鏈表的若干個(gè)結(jié)點(diǎn)的數(shù)據(jù)元素域上。 單字符結(jié)點(diǎn)鏈就是每個(gè)結(jié)點(diǎn)的數(shù)據(jù)元素域只包括一個(gè)字符。 串類 MyString類 MyString類的測(cè)試 MyStringBuffer類 MyStringBuffer類的測(cè)試 串的模式匹配算法 BruteForce算法 （ 1）從主串 s的第一個(gè)字符開始和模式串 t的第一個(gè)字符比較 ,若相等則繼續(xù)比較后續(xù)字符； （ 2）若主串 s的第一個(gè)字符和模式串 t的第一個(gè)字符比較不相等，則從主串 s的第二個(gè)字符開始重新與模式串 t的第一個(gè)字符比較，若相等則繼續(xù)比較后續(xù)字符 （ 3）若主串 s的第二個(gè)字符與模式串 t的第一個(gè)字符比較不相等，則從主串 s的第三個(gè)字符開始重新與模式串 t的第一個(gè)字符比較； （ 4）如此不斷繼續(xù)。 設(shè)主串 s=“cddcdc”,模式串 t=“cdc”,模式匹配過程如圖： 第一次匹配 s = c d d c d ct = c d ci=2j=2失敗第二次匹配 i=1j=0失敗第三次匹配 i=2j=0失敗第四次匹配 i=5