资料结构课程.PPT

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 一、刪除環狀串列的第一個節點 步驟 1：將環狀串列首指標指向第二個節點。 head = head-next; (1)原始環狀串列： (2)首指標指向第二個節點： 步驟 2：將最後1個節點的next指標指向第2個節點。 tail-next = head-next; 步驟3：將第1個節點釋放出記憶體空間。 free(p); 二、刪除環狀串列內的中間節點 只要將欲刪除節點的前一個節點的指標，指向欲刪除節點的下一個節點即可 原始環狀串列： 步驟1：找出欲刪除節點的前一個節點的指標(pt)： 欲刪除的節點 步驟2：將前一個節點(pt)的指標指向節點mid的下一個節點。 pt-next = mid-next; 步驟3：將mid節點釋放出記憶體空間。 free(mid); 5-8 雙向鏈結串列 由於單向鏈結串列只能一個方向來進行，而無法往回走。因此，本單元 中將介紹雙向鏈結串列來解決此一問題，其定義如下： 【定義】 每一個節點具有三個欄位，中間為資料欄位。左右各有一個指標欄位， 分別為Llink及Rlink。其中Llink指向上一個節點，而Rlink指向下一個 節點。節點結構，如下圖所示： 5-8 雙向鏈結串列(續) 雙向鏈結串列的優缺點如下說明： 【優點】 1. 雙向鏈結串列有兩個指標節點，在處理加入或刪除節點動作時， 速度比較快。 2.若雙向鏈結串列有任一端的指標連結脫落時，則可以快速 進行修補脫落的節點。 【缺點】 1.由於雙向鏈結串列有兩個指標節點，所以比較浪費記憶體空間。 2.雙向鏈結串列的加入或刪除時，必須要有較多的連結節點。 5-8 雙向鏈結串列(續) 建立雙向鏈結串列的方法，首先就是宣告每個節點有三個欄位。 由於雙向鏈結串列的加入與刪除動作與單向鏈結串列相同，因此， 筆者就不在此多加介紹。但雙向鏈結串列也有許多優缺點，請讀者 在實務的應用上，可依照情況來選擇。 5-9 多項式串列表示法 多項式的鏈結串列表示法主要是儲存非零項目，並且每一項的資料結構如下所示： 其中：COEF：多項式係數。 EXP：多項式指數。 LINK：指標，指向下一個節點。 【串列節點宣告】 typedef struct poly_node { int coef; //宣告多項式係數 int exp; //宣告多項式指數 struct poly_node *link; //宣告指向下一個節點的指標 } POLY_NODE; 5-9.1 多項式串列的資料結構 假設有n個非零項，則可以表示如下圖所示： 【例如】 A(X)=3X2+2X+1= 3X2+2X1+1X0 雖然在第三章已經介紹利用陣列來處理多項式，但是，鏈結串列在處理多項式具有以下兩項優點： 1.當多項式的內容變動(加入或刪除)時，則比較容易處理。 2.鏈結串列可以動態的配置記憶體，因此，比較有彈性。 5-9.2 多項式的相加 了解多項式串列的資料結構之後，接下來，我們來實際完成多項式的相加。 【作法】 逐一比較兩個多項式的項次，當指數相同時，則可以直接相加，而當指數較大者，則可以直接照抄下來，直到兩個多項式比較完畢為止。 【實例】 假設有兩個多項式A與B，其表示如下所示： A(X)=3X2+2X+1 B(X)=10X2+5 請利用鏈結串列來進行兩個多項式的相加。 【解答】前置工作 A(X)=3X2+2X+1 = 3X2+2X1+1X0 B(X)=10X2 +5 = 10X2+0X1+5X0 步驟一：將兩個多項式，分別以鏈結串列表示，並且p1與p2分別 指向二串列的首節點。 步驟二：因為上個步驟之(Exp(p1)=Exp(p2))，因為指數相同，因此， 係數可以相加，並且將相加後的結果，放到C串列中， 並且p1與p2繼續往下一個指數比較。 步驟三：因為上個步驟之Exp(p1)Exp(p2))，因此複製p