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