【正文】 釋放被刪結點； 返回被刪元素值； 線性表的鏈接存儲結構及實現 單鏈表的實現 ——— 刪除 數據結構（ C＋＋版） 清華大學出版社 template class T T LinkList::Delete(int i) { p=first 。 j=0。 while (p amp。amp。 ji1) { p=pnext。 j++。 } 線性表的鏈接存儲結構及實現 算法描述 —— C++描述 單鏈表的實現 ——— 刪除 if (!p | | !pnext) throw “位置” 。 else { q=pnext。 x=qdata。 pnext=qnext。 delete q。 return x。 } } 數據結構（ C＋＋版） 清華大學出版社 單鏈表的實現 ——— 構造函數 操作接口： LinkList(T a[ ], int n) 頭插法： 將待插入結點插在頭結點的后面 。 算法描述： first=new NodeT。 firstnext=NULL。 線性表的鏈接存儲結構及實現 數組 a 35 12 24 33 42 初始化 first ∧ 數據結構（ C＋＋版） 清華大學出版社 單鏈表的實現 ——— 構造函數 操作接口： LinkList(T a[ ], int n) 頭插法： 將待插入結點插在頭結點的后面 。 線性表的鏈接存儲結構及實現 數組 a 35 12 24 33 42 算法描述： s=new NodeT。 sdata=a[0]。 snext=firstnext。 firstnext=s。 插入第一個元素結點 first ∧ 35 s ∧ 數據結構（ C＋＋版） 清華大學出版社 單鏈表的實現 ——— 構造函數 操作接口： LinkList(T a[ ], int n) 頭插法： 將待插入結點插在頭結點的后面 。 線性表的鏈接存儲結構及實現 數組 a 35 12 24 33 42 算法描述： s=new NodeT。 sdata=a[1]。 snext=firstnext。 firstnext=s。 依次插入每一個結點 12 s first 35 ∧ 數據結構（ C＋＋版） 清華大學出版社 template class T LinkList:: LinkList(T a[ ], int n) { first=new NodeT。 firstnext=NULL。 for (i=0。 in。 i++) { s=new NodeT。 sdata=a[i]。 snext=firstnext。 firstnext=s。 } } 線性表的鏈接存儲結構及實現 單鏈表的實現 ——— 構造函數 算法描述： 數據結構（ C＋＋版） 清華大學出版社 尾插法： 將待插入結點插在終端結點的后面。 線性表的鏈接存儲結構及實現 單鏈表的實現 ——— 構造函數 操作接口： LinkList(T a[ ], int n) 算法描述： first=new NodeT。 rear=first。 數組 a 35 12 24 33 42 初始化 first rear 數據結構（ C＋＋版） 清華大學出版社 尾插法： 將待插入結點插在終端結點的后面。 線性表的鏈接存儲結構及實現 單鏈表的實現 ——— 構造函數 操作接口： LinkList(T a[ ], int n) 算法描述： s=new NodeT。 sdata=a[0]。 firstnext=s。 rear=first。 數組 a 35 12 24 33 42 插入第一個元素結點 first rear 35 s rear 數據結構（ C＋＋版） 清華大學出版社 尾插法： 將待插入結點插在終端結點的后面。 線性表的鏈接存儲結構及實現 單鏈表的實現 ——— 構造函數 操作接口： LinkList(T a[ ], int n) 算法描述： s=new NodeT。 sdata=a[1]。 firstnext=s。 rear=first。 數組 a 35 12 24 33 42 依次插入每一個結點 first rear 35 rear 12 s rear 數據結構（ C＋＋版） 清華大學出版社 尾插法： 將待插入結點插在終端結點的后面。 線性表的鏈接存儲結構及實現 單鏈表的實現 ——— 構造函數 操作接口： LinkList(T a[ ], int n) 算法描述： rearnext=NULL。 數組 a 35 12 24 33 42 最后一個結點插入后 first rear 35 rear 42 s rear ∧ 數據結構（ C＋＋版） 清華大學出版社 template class T LinkList:: LinkList(T a[ ], int n) { first=new NodeT 。 rear=first。 for (i=0。 in。 i++) { s=new NodeT 。 sdata=a[i]。 rearnext=s。 rear=s。 } rearnext=NULL。 } 線性表的鏈接存儲結構及實現 單鏈表的實現 ——— 構造函數 算法描述： 數據結構（ C＋＋版） 清華大學出版社 啟示：算法設計的一般過程 算法設計的一般步驟： 第一步：確定 入口 （ 已知條件 ） 、 出口 （ 結果 ） ； 第二步：根據一個小實例畫出 示意圖 ； 第三步： ① 正向思維 ：選定一個思考問題的起點 ， 逐步提出問題 、 解決問題； ② 逆向思維 ：從結論出發(fā)分析為達到這個結論應該先有什么； ③ 正逆結合 ； 第四步：寫出 頂層 較抽象算法 ， 分析 邊界 情況； 第五步： 驗證 第四步的算法； 第六步：寫出 具體 算法； 第七步： 進一步 驗證 ， 手工運行 。 數據結構（ C＋＋版） 清華大學出版社 單鏈表的實現 —— 析構函數 析構函數將單鏈表中所有結點的存儲空間釋放。 線性表的鏈接存儲結構及實現 操作接口： ~LinkList( )。 first a1 a2 an ∧ ai p q 算法描述： q=p。 p=pnext。 Delete q。 p 注意：保證鏈表未處理的部分不斷開 數據結構（ C＋＋版） 清華大學出版社 單鏈表的實現 —— 析構函數 template class T LinkList:: ~LinkList( ) { p=first。 while (p) { q=p。 p=pnext。 delete q。 } } 線性表的鏈接存儲結構及實現 算法描述： 數據結構（ C＋＋版） 清華大學出版社 存儲分配方式比較 ?順序表采用順序存儲結構，即用一段地址 連續(xù) 的存儲單元 依次 存儲線性表的數據元素，數據元素之間的邏輯關系通過 存儲位置 來實現。 ?單鏈表采用鏈接存儲結構，即用一組 任意 的存儲單元存放線性表的元素。用 指針 來反映數據元素之間的邏輯關系。 順序表和單鏈表的比較 數據結構（ C＋＋版） 清華大學出版社 順序表和單鏈表的比較 時間性能比較 時間性能 是指實現基于某種存儲結構的基本操作（即算法）的時間復雜度。 按位查找： ?順序表的時間為 Ｏ (1)，是隨機存取； ?單鏈表的時間為 Ｏ (n)，是順序存取。 插入和刪除： ?順序表需移動表長一半的元素，時間為 Ｏ (n)； ?單鏈表不需要移動元素，在給出某個合適位置的指針后，插入和刪除操作所需的時間僅為 Ｏ (1)。 數據結構（ C＋＋版） 清華大學出版社 順序表和單鏈表的比較 空間性能比較 空間性能 是指某種存儲結構所占用的存儲空間的大小。 定義結點的存儲密度： 數據域占用的存儲量 整個結點占用的存儲量 存儲密度＝ 數據結構（ C＋＋版） 清華大學出版社 順序表和單鏈表的比較 空間性能比較 結點的存儲密度： ?順序表中每個結點的存儲密度為 1（只存儲數據元素），沒有浪費空間； ?單鏈表的每個結點的存儲密度 1（包括數據域和指針域），有指針的結構性開銷。 整體結構： ?順序表需要預分配存儲空間，如果預分配得過大，造成浪費，若估計得過小，又將發(fā)生上溢； ?單鏈表不需要預分配空間，只要有內存空間可以分配，單鏈表中的元素個數就沒有限制。 數據結構（ C＋＋版） 清華大學出版社 結論 ⑴若線性表需 頻繁查找 卻很少進行插入和刪除操作，或其操作和元素在表中的位置密切相關時，宜采用順序表作為存儲結構；若線性表需 頻繁插入和刪除 時，則宜采用單鏈表做存儲結構。 ⑵當線性表中元素 個數變化 較大或者未知時，最好使用單鏈表實現；而如果用戶事先知道線性表的大致長度，使用順序表的空間效率會更高。 順序表和單鏈表的比較 總之 ，線性表的順序實現和鏈表實現各有其優(yōu)缺點，不能籠統(tǒng)地說哪種實現更好，只能根據實際問題的具體需要，并對各方面的優(yōu)缺點加以綜合平衡，才能最終選定比較適宜的實現方法。 數據結構（ C＋＋版） 清華大學出版社 線性表的其它存儲方法 循環(huán)鏈表 first a1 ai1 an ∧ ai p 從單鏈表中某結點 p出發(fā)如何找到其前驅？ 將單鏈表的首尾相接，將終端結點的指針域由空指針改為指向頭結點，構成 單循環(huán)鏈表 ，簡稱 循環(huán)鏈表 。 數據結構（ C＋＋版） 清華大學出版社 線性表的其它存儲方法 循環(huán)鏈表 空表和非空表的處理一致 附設頭結點 first 空循環(huán)鏈表 first a1 ai1 an ai 非空循環(huán)鏈表 數據結構（ C＋＋版） 清華大學出版社 first a1 ai1 an ai 線性表的其它存儲方法 循環(huán)鏈表 —— 插入 x s p x s p x s p 算法描述： s=new NodeT。 sdata=x。 snext=pnext。 pnext=s。 數據結構（ C＋＋版） 清華大學出版社 template class T void LinkList::Insert(int i, T x) { p=first 。 j=0。 while (p!=first amp。amp。 ji1) { p=pnext。 j++。 } if (!p) throw 位置 。 else { s=new NodeT。 sdata=x。 snext=pnext。 pnext=s。 } } 線性表的其它存儲方法 循環(huán)鏈表 —— 插入 與單鏈表的插入操作相比，差別是什么？ 數據結構（ C＋＋版） 清華大學出版社 循環(huán)條件： p!=NULL?p!=first pnext!=NULL?pnext!=first 線性表的其它存儲方法 循環(huán)鏈表 循環(huán)鏈表中沒有明顯的尾端 如何避免死循環(huán) 數據結構（ C＋＋版） 清華大學出版社 如何查找開始結點和終端結點？ 線性表的其它存儲方法 循環(huán)鏈表 first a1 ai1 an ai 開始結點： firstnext 終端結點：將單鏈表掃描一遍，時間為 O(n)