數據結構與算法c語言版第2版上ppt(編輯修改稿)

　

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