【正文】 的最大允許數(shù)據(jù)元素個數(shù) ， size表示數(shù)組的當(dāng)前數(shù)據(jù)元素個數(shù) 。 . . .1a 2a 3a 4a 5am a x S i z e 1l i s t A r r a y0 1 2 3 4 5 6s i z e = 60a 順序表類 類包含成員變量和成員函數(shù)。成員變量用來表示抽象數(shù)據(jù)類型中定義的數(shù)據(jù)集合，成員函數(shù)用來表示抽象數(shù)據(jù)類型中定義的操作集合。順序表類實現(xiàn)接口 List。順序表類的 public成員函數(shù)主要是接口List中定義的成員函數(shù)。 順序表的效率分析 插入和刪除是順序表中時間復(fù)雜度最高的成員函數(shù) 。 插入時 ， 主要的耗時部分是循環(huán)移動數(shù)據(jù)元素部分 。 循環(huán)移動數(shù)據(jù)元素的效率和插入的位置 i有關(guān) ， 最壞情況是 i = 0， 需移動 size個數(shù)據(jù)元素；最好情況是 i = size， 需移動 0個數(shù)據(jù)元素 。 平均次數(shù)為： 類似地，刪除時，平均次數(shù)為： 2)(11)(00ninninpEniniiis ?????? ????21)(1)( 1010?????? ?? ????ninninqEniniidl 順序表中的其余操作都和數(shù)據(jù)元素個數(shù) n無關(guān)，因此在順序表中插入和刪除一個數(shù)據(jù)元素成員函數(shù)的時間復(fù)雜度為 O（ n）。 順序表支持隨機讀取，因此，順序表取數(shù)據(jù)元素的時間復(fù)雜度為 O（ 1）。 順序表的主要優(yōu)點是：支持隨機讀取，以及內(nèi)存空間利用效率高。 順序表的主要缺點是：需要預(yù)先給出（很難準(zhǔn)確）數(shù)組的最大數(shù)據(jù)元素個數(shù)，另外，插入和刪除操作時需要移動較多的數(shù)據(jù)元素。 單鏈表 指針 表示一個數(shù)據(jù)元素邏輯意義上的存儲位置。 鏈?zhǔn)酱鎯Y(jié)構(gòu)是基于指針實現(xiàn)的。我們把一個數(shù)據(jù)元素和一個指針稱為一個 結(jié)點 。 鏈?zhǔn)酱鎯Y(jié)構(gòu) 是用指針把相互直接關(guān)聯(lián)的結(jié)點（即直接前驅(qū)結(jié)點或直接后繼結(jié)點）鏈接起來。 鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表稱為 鏈表 。 根據(jù)結(jié)點構(gòu)造鏈的方法不同，鏈表主要有單鏈表、單循環(huán)鏈表和循環(huán)雙向鏈表三種。這樣，一個數(shù)據(jù)元素集就可以用鏈?zhǔn)酱鎯Y(jié)構(gòu)來存儲。 單鏈表的結(jié)構(gòu) 單鏈表 是構(gòu)成鏈表的每個結(jié)點只有一個指向直接后繼結(jié)點的指針 。 1 單鏈表的表示方法 單鏈表中每個結(jié)點的結(jié)構(gòu)： 數(shù) 據(jù) 元 素 域 指 針 域或e l e m e n t n e x t 單鏈表有帶頭結(jié)點結(jié)構(gòu)和不帶頭結(jié)點結(jié)構(gòu)兩種 。 我們把指向單鏈表的指針稱為單鏈表的 頭指針 。 頭指針?biāo)傅牟淮娣艛?shù)據(jù)元素的第一個結(jié)點稱作 頭結(jié)點 。 存放第一個數(shù)據(jù)元素的結(jié)點稱作第一個數(shù)據(jù)元素結(jié)點 ， 或稱首元結(jié)點 。 頭 指 針∧ 頭 指 針. . .( a )( b )0a 1a 1?na∧ ∧ 頭 結(jié) 點 頭 結(jié) 點（ a）空鏈； （ b）非空鏈 2 帶頭結(jié)點單鏈表和不帶頭結(jié)點單鏈表的比較 從線性表的定義可知，線性表要求允許在任意位置進行插入和刪除。當(dāng)選用帶頭結(jié)點的單鏈表時，插入和刪除操作的實現(xiàn)方法比不用帶頭結(jié)點單鏈表的實現(xiàn)方法簡單。 設(shè)頭指針用 head表示，在單鏈表中任意結(jié)點（但不是第一個數(shù)據(jù)元素結(jié)點）前插入一個新結(jié)點的方法如圖 26所示。算法實現(xiàn)時，首先把插入位置定位在要插入結(jié)點的前一個結(jié)點位置，然后把 s表示的新結(jié)點插入單鏈表中。 0ah e a d . . .ia 1?na∧ so b j. . .1?iapn e x td a t a在單鏈表非第一個結(jié)點前插入結(jié)點過程 要在第一個數(shù)據(jù)元素結(jié)點前插入一個新結(jié)點，若采用不帶頭結(jié)點的單鏈表結(jié)構(gòu)，則結(jié)點插入后，頭指針 head就要等于新插入結(jié)點 s，這和在非第一個數(shù)據(jù)元素結(jié)點前插入結(jié)點時的情況不同。另外，還有一些不同情況需要考慮。因此，算法對這兩種情況就要分別設(shè)計實現(xiàn)方法。 而如果采用帶頭結(jié)點的單鏈表結(jié)構(gòu) ， 算法實現(xiàn)時 ， p指向頭結(jié)點 ， 改變的是 p指針的 next指針的值 ， 而頭指針 head的值不變 。 因此 ， 算法實現(xiàn)方法比較簡單 。 在帶頭結(jié)點單鏈表中第一個數(shù)據(jù)元素結(jié)點前插入一個新結(jié)點的過程如圖所示 。 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é)點單鏈表第一個結(jié)點前插入結(jié)點過程 結(jié)點類 單鏈表是由一個一個結(jié)點組成的 ， 因此 ， 要設(shè)計單鏈表類 ， 必須先設(shè)計結(jié)點類 。 結(jié)點類的成員變量有兩個：一個是數(shù)據(jù)元素 ， 另一個是表示下一個結(jié)點的對象引用 （ 即指針 ） 。 單鏈表類 單鏈表類的成員變量至少要有兩個：一個是頭指針 ， 另一個是單鏈表中的數(shù)據(jù)元素個數(shù) 。 但是 ， 如果再增加一個表示單鏈表當(dāng)前結(jié)點位置的成員變量 ， 則有些成員函數(shù)的設(shè)計將更加方便 。 單鏈表的效率分析 在單鏈表的任何位置上插入數(shù)據(jù)元素的概率相等時 ，在單鏈表中插入一個數(shù)據(jù)元素時比較數(shù)據(jù)元素的平均次數(shù)為： 2)(11)(00ninninpEniniiis ?????? ???? 刪除單鏈表的一個數(shù)據(jù)元素時比較數(shù)據(jù)元素的平均次數(shù)為： 21)(1)( 1010?????? ?? ????ninninqEniniidl 因此，單鏈表插入和刪除操作的時間復(fù)雜度均為 O（ n）。另外，單鏈表取數(shù)據(jù)元素操作的時間復(fù)雜度也為 O（ n）。 順序表和單鏈表的比較 順序表的主要優(yōu)點是支持隨機讀取，以及內(nèi)存空間利用效率高；順序表的主要缺點是需要預(yù)先給出數(shù)組的最大數(shù)據(jù)元素個數(shù)，而這通常很難準(zhǔn)確作到。當(dāng)實際的數(shù)據(jù)元素個數(shù)超過了預(yù)先給出的個數(shù)，會發(fā)生異常。另外，順序表插入和刪除操作時需要移動較多的數(shù)據(jù)元素。 和順序表相比，單鏈表的主要優(yōu)點是不需要預(yù)先給出數(shù)據(jù)元素的最大個數(shù)。另外，單鏈表插入和刪除操作時不需要移動數(shù)據(jù)元素。 單鏈表的主要缺點是每個結(jié)點中要有一個指針，因此單鏈表的空間利用率略低于順序表的。另外，單鏈表不支持隨機讀取，單鏈表取數(shù)據(jù)元素操作的時間復(fù)雜度為 O（ n）；而順序表支持隨機讀取，順序表取數(shù)據(jù)元素操作的時間復(fù)雜度為 O（ 1）。 循環(huán)單鏈表是單鏈表的另一種形式 ， 其結(jié)構(gòu)特點是鏈表中最后一個結(jié)點的指針不再是結(jié)束標(biāo)記 ， 而是指向整個鏈表的第一個結(jié)點 ， 從而使單鏈表形成一個環(huán) 。 和單鏈表相比 ， 循環(huán)單鏈表的長處是從鏈尾到鏈頭比較方便 。 當(dāng)要處理的數(shù)據(jù)元素序列具有環(huán)型結(jié)構(gòu)特點時 ， 適合于采用循環(huán)單鏈表 。 循環(huán)單鏈表 和單鏈表相同 ， 循環(huán)單鏈表也有帶頭結(jié)點結(jié)構(gòu)和不帶頭結(jié)點結(jié)構(gòu)兩種 ， 帶頭結(jié)點的循環(huán)單鏈表實現(xiàn)插入和刪除操作時 ， 算法實現(xiàn)較為方便 。 帶頭結(jié)點的循環(huán)單鏈表結(jié)構(gòu)如下： ...0a 1a 1?na(a) (b)head head（ a）空鏈表；（ b）非空鏈表 帶頭結(jié)點的循環(huán)單鏈表的操作實現(xiàn)方法和帶頭結(jié)點的單鏈表的操作實現(xiàn)方法類同 ， 差別僅在于： （ 1） 在構(gòu)造函數(shù)中 ， 要加一條 = head 語句 ， 把初始時的帶頭結(jié)點的循環(huán)單鏈表設(shè)計成圖 211 （ a） 所示的狀態(tài) 。 （ 2） 在 index(i)成員函數(shù)中 ， 把循環(huán)結(jié)束判斷條件current != null改為 current != head。 雙向鏈表 是每個結(jié)點除后繼指針外還有一個前驅(qū)指針 。 和單鏈表類同 ， 雙向鏈表也有帶頭結(jié)點結(jié)構(gòu)和不帶頭結(jié)點結(jié)構(gòu)兩種 ， 帶頭結(jié)點的雙向鏈表更為常用；另外 ， 雙向鏈表也可以有循環(huán)和非循環(huán)兩種結(jié)構(gòu) ， 循環(huán)結(jié)構(gòu)的雙向鏈表更為常用 。 雙向鏈表 在雙向鏈表中，每個結(jié)點包括三個域，分別是 element域、 next域和 prior域，其中 element域為數(shù)據(jù)元素域， next域為指向后繼結(jié)點的對象引用， prior域為指向前驅(qū)結(jié)點的對象引用。圖 212為雙向鏈表結(jié)點的圖示結(jié)構(gòu)。 p r i o r n e x td a t a 雙向鏈表結(jié)點的圖示結(jié)構(gòu) 圖 213是帶頭結(jié)點的循環(huán)雙向鏈表的圖示結(jié)構(gòu)。從圖 213可見，循環(huán)雙向鏈表的 next和 prior各自構(gòu)成自己的循環(huán)單鏈表。 帶頭結(jié)點的循環(huán)雙向鏈表 （ a）空鏈表；（ b）非空鏈表 0a 1a ...(a)(b)1?naheadhead 在雙向鏈表中 ， 有如下關(guān)系：設(shè)對象引用 p表示雙向鏈表中的第 i個結(jié)點 ， 則 i+1個結(jié)點 ， i個結(jié)點 ， 即 == p；同樣地 ， i1個結(jié)點 ， i個結(jié)點 ， 即 == p。 圖 214是雙向鏈表上述關(guān)系的圖示 。 ia1?ia 1?iap圖 214 雙向鏈表的關(guān)系 循環(huán)雙向鏈表的插入過程如圖 215所示 。 圖中的指針 p表示要插入結(jié)點的位置 ， s表示要插入的結(jié)點 ， ① 、② 、 ③ 、 ④ 表示實現(xiàn)插入過程的步驟 。 0a ia . . . 1?na. . .x1?ia. . .① ② ③ ④ ph e a ds圖 215 循環(huán)雙向鏈表的插入過程 循環(huán)雙向鏈表的刪除過程如圖 216所示 。 圖中的指針 p表示要插入結(jié)點的位置 ， ① 、 ② 表示實現(xiàn)刪除過程的步驟 。 ... 1?ia ...1?na① ② 1?naheadp1?iaia 循環(huán)雙向鏈表的刪除過程 仿真鏈表 在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，我們實現(xiàn)數(shù)據(jù)元素之間的次序關(guān)系依靠指針。我們也可以用數(shù)組來構(gòu)造仿真鏈表。方法是在數(shù)組中增加一個（或兩個） int類型的變量域，這些變量用來表示后一個（或前一個）數(shù)據(jù)元素在數(shù)組中的下標(biāo)。我們把這些 int類型變量構(gòu)造的指針稱為 仿真指針 。這樣，就可以用仿真指針構(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è)計方法 面向?qū)ο筌浖O(shè)計方法是一種和人類認(rèn)識事物、分析事物方法一致的軟件設(shè)計方法。不僅如此，面向?qū)ο笤O(shè)計方法的模塊化軟件、數(shù)據(jù)封裝、信息隱藏等特點，還可以使軟件設(shè)計可以像其他工業(yè)產(chǎn)品一樣，可以大規(guī)模協(xié)作開發(fā)。 模塊化軟件設(shè)計的基本思想是：把基礎(chǔ)軟件設(shè)計成可重復(fù)使用的模塊，這些模塊提供外部調(diào)用的接口，其他程序通過接口使用這些基礎(chǔ)軟件模塊。這樣，軟件工業(yè)將擺脫了小作坊工作方式，像現(xiàn)代的其他工業(yè)一樣，可以進行大規(guī)模的協(xié)作生產(chǎn)或開發(fā)。 第 3章 堆棧和隊列 堆棧 堆棧的應(yīng)用 隊列 優(yōu)先級隊列 本章主要知識點： ● 堆棧的基本概念，堆棧的用途 ● 順序堆棧類的設(shè)計方法，鏈?zhǔn)蕉褩ｎ惖脑O(shè)計方法 ● 隊列的基本概念，隊列的用途 ● 順序循環(huán)隊列的基本實現(xiàn)原理，順序循環(huán)隊列的隊空和隊滿判斷方法，順序循環(huán)隊列類的設(shè)計方法 ● 鏈?zhǔn)蕉褩ｎ惖脑O(shè)計方法 ● 優(yōu)先級隊列的概念，優(yōu)先級隊列的用途，順序優(yōu)先級 隊列的入隊列和出隊列操作設(shè)計方法 堆棧 堆棧的基本概念 堆棧 （也簡稱作棧）是一種特殊的線性表，堆棧的數(shù)據(jù)元素以及數(shù)據(jù)元素間的邏輯關(guān)系和線性表完全相同，其差別是線性表允許在任意位置進行插入和刪除操作，而堆棧只允許在固定一端進行插入和刪除操作。 堆棧中允許進行插入和刪除操作的一端稱為棧頂，另一端稱為棧底。堆棧的插入和刪除操作通常稱為進棧或入棧，堆棧的刪除操作通常稱為出?；蛲藯?。 從輸入和輸出數(shù)據(jù)元素的位置關(guān)系看 ， 堆棧的功能和一種火車調(diào)度裝置的功能類同 。 ( a )( c )( b )火 車