【文章內(nèi)容簡介】 1) 找到 p的前驅(qū)結(jié)點 pre。 (2) 將 prenext指向 pnext。 (3) 釋放 p。 單鏈表的創(chuàng)建方法有兩種，一種是頭插法，另一種是尾插法。頭插法是將新增結(jié)點插入第一個結(jié)點之前。尾插法就是將新增的結(jié)點插入最后一個結(jié)點之后。 按照保序合并的思想，首先，需要設(shè)置 3個指針 pa、 pb、 pc， pa和 pb分別指向鏈表 La與 Lb的當前待比較插入結(jié)點， pc指向鏈表 Lc的最后一個結(jié)點。當 padata≤pb data時，將 pa所指的結(jié)點插入到 pc后面，否則就將pb所指的結(jié)點插入到 pc后面。最后，當有一個表合并完以后，只需要將另一個表剩余的結(jié)點全插入到 pc即可。 雙向鏈表與相關(guān)操作實現(xiàn) 1．雙向鏈表的插入操作 因為雙向鏈表本身就帶有一個指向前驅(qū)結(jié)點的指針，因此在 p結(jié)點前插入元素 e的操作可以通過下面幾個步驟來完成。 (1) 創(chuàng)建一個新的結(jié)點 q，讓 qdata等于需要插入的元素 e。 (2) 將 qprior指向 pprior。 (3) 將 ppriornext指向 q。 (4) 將 qnext指向 p。 (5) 將 pprior指向 q。 2．雙向鏈表的刪除操作 雙向鏈表的刪除結(jié)點 p操作要修改兩個指針，需要執(zhí)行下面 3個步驟。 (1) 將 ppriornext指向 pnext。 (2) 將 pnextprior指向 pprior。 (3) 釋放 p。 循環(huán)鏈表與其相關(guān)操作實現(xiàn) ? 循環(huán)鏈表是一種特殊的線性表，它的第一個結(jié)點之前就是最后一個結(jié)點；反之亦然。 ? 單向循環(huán)鏈表的操作與非循環(huán)鏈表的操作相同，只是將原來控制條件由判斷指針是否為 NULL變?yōu)槭欠袷穷^指針而已。 ? 根據(jù)不同的需求，循環(huán)鏈表還可以和雙向鏈表組合形成雙向循環(huán)鏈表，它的操作和雙向鏈表的操作類似，只需要將原來控制條件由判斷指針是否為 NULL變?yōu)槭欠袷穷^指針而已。 鏈式存儲結(jié)構(gòu)分析 1. 鏈式存儲結(jié)構(gòu)優(yōu)、缺點 鏈表是線性表的另一種存儲方式，與線性表相比，鏈表具有以下的優(yōu)、缺點。 (1)鏈表的存儲空間是動態(tài)分配的，只要內(nèi)存尚有空間，就不會產(chǎn) 生溢出。 (2)便于實現(xiàn)插入和刪除操作。 (3)由于鏈表的不連續(xù)存儲，因此它的內(nèi)容分散，有時會導(dǎo)致調(diào)試的不方便。 (4)鏈表中的每個結(jié)點既有數(shù)據(jù)域又有指針域，增加了線性表的存儲開銷。 (5)在鏈表中查找結(jié)點時，需要從頭指針開始遍歷，增加了時間。 ? 在線性表的鏈式存儲結(jié)構(gòu)中，主要有單鏈表、雙向鏈表、循環(huán)鏈表 3種，下面就對這 3種結(jié)構(gòu)鏈表的優(yōu)、缺點進行分析。 (1)雙向鏈表解決了單鏈表的單向性問題，使得鏈表查找前驅(qū)結(jié)點變得簡單，但是它增加了結(jié)點的存儲空間，使維護操作變得困難。 (2)循環(huán)鏈表解決了單鏈表必須從頭指針進行遍歷的限制。 2. 選擇存儲結(jié)構(gòu)遵循的原則 (1)當線性表的長度變化較大，難以估計其存儲的規(guī)模時，一般采用鏈表作為存儲結(jié)構(gòu)。 (2)當線性表的長度變化不大，易于事先確定其大小時，宜采用順序表作為存儲結(jié)構(gòu)，這樣可以節(jié)省存儲空間。 (3)當線性表的主要操作是查找，并且很少進行插入和刪除操作時，宜采用順序表作為存儲結(jié)構(gòu)。 (4)若線性表需要頻繁地進行插入和刪除操作時，為了提高性能，宜采用鏈表作為存儲結(jié)構(gòu)。 線性表的應(yīng)用 一元多項式的抽象數(shù)據(jù)類型 多項式的順序表實現(xiàn) 一元多項式的抽象數(shù)據(jù)類型 在數(shù)學(xué)中，一個一元多項式可以按升冪寫成以下形式： 這個多項式由 n+1個系數(shù)唯一確定。那么，就可以用一個線性表 P來存儲這些系數(shù)，即 那么，通過這個線性表，就可以編寫一些多項式的加、減、乘、微分等操作的算法。 20 1 2() nnnP x p p x p x p x? ? ? ? ?0 1 2( , , , , )nP p p p p? 多項式的順序表實現(xiàn) 很顯然，可以采用順序表實現(xiàn)這個多項式。 下面給出了多項式的順序表實現(xiàn)的類型聲明。 typedef struct Node { int CoefArray[MaxDegree+1]。 int HighPower。 }*SeqPolynomial。 第 3章 棧 和 隊 列 本章主要內(nèi)容 棧 棧的應(yīng)用 隊列 隊列的應(yīng)用 棧 棧概述 棧的實現(xiàn) 棧的實現(xiàn)方式的比較 棧概述 棧 (stack)是限定僅在表尾進行插入和刪除操作的線性表。表尾又稱為棧頂 (top)，表頭稱為棧底 (bottom)。棧又稱為后進先出 (Last In First Out， LIFO)的線性表。 棧的抽象數(shù)據(jù)類型定義為： ADT Stack{ 數(shù)據(jù)對象：任意數(shù)據(jù)元素的集合 D={ ai| ai ∈elementset ， i=1,2,?,n,n≥0} 數(shù)據(jù)關(guān)系：數(shù)據(jù)之間呈線性關(guān)系，除第一個和最后一個外，每個元素有唯一的直接前驅(qū)和唯一的直接后繼。 R={ai1， ai| ai1， ai∈D,i=1,2,?,n,n≥0} 棧的實現(xiàn) 1．順序棧 利用順序表實現(xiàn)的棧稱為順序棧。 1) 順序棧的初始化 順序棧的初始化就是將棧初始化為一個空棧。 2) 棧判空操作 順序棧的棧判空操作就是查看 top是否為 1，如果 top=1則說明這是一個空棧，返回 true，否則返回 false。 3) 入棧操作 因為順序棧用數(shù)組實現(xiàn)，因此在實現(xiàn)順序棧的入棧操作時，需要對 S進行是否棧滿判斷。只有在棧不滿的情況下才能進行入棧操作。棧滿的條件為 top=MAXSIZE1。 4) 出棧操作 順序棧的出棧操作，只需要將 top。 5) 取棧頂元素 2．鏈棧 下面將給出鏈棧的基本操作的算法。 1) 鏈棧的初始化 鏈棧初始化的算法如下所示。 void LinkedStackInit(LinkedStack S) { Stop=NULL。 } 2) 判棧空操作 下面給出了鏈棧判?？詹僮鞯乃惴ā? BOOL LinkedStackEmpty(LinkedStack S) { if(Stop==NULL) return TRUE。 else return FALSE。 } 3) 入棧操作 由于鏈棧采用動態(tài)的存儲方式，不存在棧滿的情況，因此，在進行入棧操作時，只需要將創(chuàng)建的新結(jié)點插入到棧中即可。 4) 出棧操作 雖然鏈棧的入棧操作不需要判定棧是否已滿，但是鏈棧的出棧操作仍需要判斷棧是否為空。 棧的實現(xiàn)方式的比較 ? 順序棧與鏈棧操作的時間復(fù)雜度均為 O(1)。 ? 順序棧主要的缺點是，需要預(yù)先定義?？臻g的大小，當棧中的元素不多時容易造成空間的浪費，當棧的入棧操作過多時，又可能出現(xiàn)?？臻g的不足。 ? 鏈棧的主要缺點是鏈棧需要增加每個結(jié)點的存儲開銷。 棧 的 應(yīng) 用 平衡符號 表達式求值 函數(shù)調(diào)用 遞歸與棧 平衡符號 人們稱符號“ (” 、“ [” 、“ {” 為開分隔符 (opening delimiter)，稱“ )” 、“ ]” 、“ }” 為閉分隔符 (closing delimiter)。平衡符號的算法主要分為以下 3步。 (1) 設(shè)置空棧 S。 (2) 依次讀入文件中的字符，如果讀到的字符屬于開分隔符，則將其壓入到棧 S中，如果讀到的字符屬于閉分隔符，則將棧 S中的棧頂元素彈出，并與此閉分隔符比較，如果二者不匹配，則報錯，否則繼續(xù)讀入下一個字符，直到文件結(jié)尾。 (3) 最后如果棧 S為空棧，則說明符號匹配成功，否則匹配不成功，報錯。 表達式求值 對于表達式 3*4+5+6*7 可以將上述的計算順序書寫為 34*5+67*+ 以上的記法稱為后綴 (posfix)或逆波蘭 (reverse Polish)記法。并且用后綴記法描述的表達式稱為后綴式。后綴式的計算方法是上面所描述的過程，采用?？梢院苋菀椎貙崿F(xiàn)上面的過程。算法的主要思想分為以下 3步。 (1)設(shè)置一個空棧 S。 (2)依次讀取表達式中的元素，如果元素是一個數(shù)，則將其壓入棧 S中；否則，元素為一個計算符，這時將棧 S的兩個棧頂元素彈出，并采用此運算符做相應(yīng)的操作。直到整個表達式計算完畢。 (3)最后棧 S中唯一的元素即為表達式的求值結(jié)果。 棧不僅可以用來計算一個后綴式的值，而且還可以用棧將一個標準形式的表達式 (又稱為中綴式 (infix))轉(zhuǎn)換為后綴式。 (1) 設(shè)置空棧 S(用來存放操作符 )。 (2) 依次讀入中綴表達式中的元素。 (3) 最后，直至讀到輸入的表達式的末尾。 函數(shù)調(diào)用 在進行函數(shù)調(diào)用時，系統(tǒng)將所需要的信息存放在棧中。在系統(tǒng)中，每個函數(shù) (包括 main函數(shù) )的狀態(tài)是由函數(shù)中的局部變量、函數(shù)參數(shù)值、函數(shù)的返回地址決定的。存儲這些信息的數(shù)據(jù)區(qū)域稱為活動記錄 (activation record)，或叫做棧幀 (stack frame)，它是運行時系統(tǒng)棧上分配的空間，只要函數(shù)是正在執(zhí)行的，它的活動記錄就一直存在，只有當函數(shù)退出時才釋放其空間。 遞歸與棧 1．遞歸的定義 遞歸是指一個直接調(diào)用自己或者通過一系列的過程調(diào)用語句間接地調(diào)用自己的過程。 ? 根據(jù)調(diào)用的方式不同，遞歸還可以分為直接遞歸和間接遞歸。若一個過程在執(zhí)行前直接調(diào)用其本身就稱其為直接遞歸。 ? 若一個過程 A調(diào)用了過程 B，而過程 B又調(diào)用了過程 A，則過程A通過過程 B來調(diào)用自身的方式稱為間接遞歸。 ? 遞歸定義必須同時滿足以下兩個條件。 (1)被定義項在定義中應(yīng)具有更小的“尺度”。 (2)被定義項在最小“尺度”上的定義不是遞歸的。 2．遞歸調(diào)用的剖析 在執(zhí)行函數(shù)時，系統(tǒng)跟蹤運行時棧上的所有調(diào)用，并且通過返回地址來記錄調(diào)用完畢后從哪一個位置繼續(xù)程序的運行。在系統(tǒng)中為每一行代碼指定一個數(shù)，如果這一行是一個函數(shù)調(diào)用，該數(shù)就為該函數(shù)的返回值。 3．遞歸的消除 最一般的消除遞歸的方法是將原由系統(tǒng)管理的棧改為由程序員管理。 采用棧來模擬遞歸時，采用了以下步驟。 (1)構(gòu)造一個棧。 (2)為了能夠一次將參數(shù)、返回地址和函數(shù)的返回值壓入棧中，設(shè)置了一個結(jié) 構(gòu) ELEM，它含有 3個變量 rd、 pn和 pf，對于 rd并不是函數(shù)的真實的返回地址，只是為了模擬時設(shè)置標號的值。 (3)將標號 L0賦值給算法的第一條可執(zhí)行語句。 (4)接下來通過標號語句與 goto語句的使用，完成了將不同狀態(tài)的參數(shù)、返回地址、返回值壓入棧中。 (5)最后利用標號 L1與 goto語句，完成了出棧操作。 隊 列 隊列概述 隊列的實現(xiàn)