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