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