单向链结串列的插入节点.ppt

德明科技大學資訊科技系 鏈結串列Link List chapter 6 線性串列(Linear List) 線性串列 又稱有序串列(Ordered List)或循序串列(Sequential List) ，元素與元素之間有線性的相對關係，並且以循序方式儲存 堆疊與佇列都是線性串列 陣列與鏈結串列比較 陣列 固定記憶體大小，設計簡單但沒彈性 鏈結串列 以節點串起整個串列，比較複雜但有彈性 動態記憶體配置 Dynamical Memory Allocation 靜態記憶體配置是在編譯階段時就配置記憶體空間 動態記憶體配置則是等到執行階段，才向作業系統要求配置所需的記憶體空間 動態記憶體配置可以讓程式設計者靈活運用程式所需的記憶體空間 在C++使用動態記憶體配置的函數 malloc() 與 free(): 只針對資料變數 new 與 delete: 針對變數與物件均可 鏈結串列 鏈結串列 依照資料特性，決定使用陣列或鏈結串列 如果需要大量資料讀取，陣列比較合適 如果插入與刪除資料頻繁，鏈結串列比較合適 鏈結串列內，一個節點包含兩部份 資料 data，紀錄資料內容 鏈結 link，紀錄下一個節點的位置 在電腦程式中，實作鏈結串列的方法有二 以陣列完成 以結構與指標搭配完成 以陣列實作鏈結串列 新增節點 刪除節點 指標 Pointer 結構 Structure 動態配置節點實作鏈結串列 鏈結串列所需的節點 資料：以結構的方式呈現多元資料 鏈結：以指標的方式動態配置節點 鏈結串列 鏈結串列 由一個或一個以上動態記憶體分配的節點 (node)所組成 每一個節點至少會有兩個或兩個以上的欄位，分別存放資料及指標，此指標稱為鏈結(link) 若某節點無下一個節點，則此節點的連結為空指標(Null) 鏈結串列特性 各節點不一定要佔用連續的記憶體空間 各節點之資料型態不一定要相同 重點是以指標鏈結串起 插入與刪除節點方便 鏈結串列各元素在記憶體之位置是不連續的 鏈結串列由動態記憶體分配的節點(Node)串接而成 相形之下，陣列為一個循序(Sequential)之記憶體結構 單向鏈結串列與雙向鏈結串列比較 單向鏈結串列 單向鏈結串列的建立 單向鏈結串列的插入節點 有三種不同的情形： 在串列的第一個節點前插入節點 在串列的最後一個節點後面插入節點 在串列的中間位置插入節點 在串列的第一個節點前插入節點 把新節點的指標指向串列首，再把串列首移到新節點上即可 在串列的最後一個節點後面插入節點 把串列的最後一個節點的指標指向新節點，新節點再指向NULL即可 串列的中間位置插入節點 如果插入的節點是在P與Q之間，只要將P節點的指標指向新節點R，新節點的指標指向Q節點即可 單向鍵結串列的刪除節點 有三種不同的情形： 刪除串列的第一個節點 刪除串列內的中間節點 刪除串列後的最後一個節點 刪除串列的第一個節點 把串列首指標指向第二個節點 不要忘記將被刪除的節點釋放記憶體 刪除串列內的中間節點 只要將刪除節點的前一個節點的指標，指向欲刪除節點的下一個節點即可 不要忘記將被刪除的節點釋放記憶體 刪除串列的第一個節點 只要指向最後一個節點的指標，直接指向NULL即可 不要忘記將被刪除的節點釋放記憶體 鏈結串列的反轉 將每個節點的鏈結指標往回指 鏈結串列的連結 兩個鏈結串列首尾相連 鏈結串列的長度 鏈結串列內不含首節點的節點個數 例如下圖長度是4 鏈結串列的長度 步驟三 最後一個反轉後變成第一個節點 * 2. 「鏈結」(link) 就是用來維持這順序的工具，它可以告訴我們「下一個元素放在哪裡」。 「鏈結串列」(linked list) 可以用來解決單純陣列的缺點： 1. 鏈結串列的元素之間不必實體連續（即不必依元素順序佔用記憶體中的連續位址），只要有邏輯上 (logical) 的順序存在即可 首節點 中國 美國 英國 蘇俄 listA 中國 美國 英國 蘇俄 無首節點 有首節點 data next Table[0] [1] [2] [4] [3] [5] [6] [7] [8] 3 6 -1 1 -1 -1 7 0 -1 美 國 中 國 英 國 蘇 俄 #define MAXNODE 9 typedef struct tagListNode { char data[8]; /*資料欄位*/ int next ; /*鏈結欄位*/ } ListNode ; ListNode table[MAXNODE] ; 節點散佈在陣列中，實體位置沒有連續，但根據鏈結可以得到以下次序 3 首節點 1 中國 6 美國 7 英國 0 蘇俄 3 1 0 6 7 目標：要在 ‘英