第3章 數(shù)據(jù)描述

1、計(jì)算機(jī)與控制工程學(xué)院第第3 3章章 數(shù)據(jù)描述數(shù)據(jù)描述-初窺門徑：由第一種數(shù)據(jù)結(jié)構(gòu)線性表談起初窺門徑：由第一種數(shù)據(jù)結(jié)構(gòu)線性表談起計(jì)算機(jī)與控制工程學(xué)院主要內(nèi)容主要內(nèi)容 基本概念基本概念 線性表的描述與分析線性表的描述與分析 公式化描述（順序表示）公式化描述（順序表示） 鏈表描述（鏈?zhǔn)奖硎荆╂湵砻枋觯ㄦ準(zhǔn)奖硎荆?間接尋址間接尋址 線性表的應(yīng)用線性表的應(yīng)用2計(jì)算機(jī)與控制工程學(xué)院數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 概念概念 包括數(shù)據(jù)對(duì)象和實(shí)例以及構(gòu)成實(shí)例的每個(gè)元素之包括數(shù)據(jù)對(duì)象和實(shí)例以及構(gòu)成實(shí)例的每個(gè)元素之間所存在的各種關(guān)系。間所存在的各種關(guān)系。 學(xué)習(xí)順序?qū)W習(xí)順序3ADT該數(shù)據(jù)結(jié)構(gòu)有什么特點(diǎn)？有哪些操作？C+實(shí)現(xiàn)實(shí)現(xiàn)可執(zhí)

2、行的C+代碼是怎樣的？性能分析性能分析空間消耗如何？關(guān)鍵操作的時(shí)間性能如何？應(yīng)用應(yīng)用用在什么地方？怎么用？計(jì)算機(jī)與控制工程學(xué)院線性表線性表 特征特征 linear-listlinear-list 是最常用且最簡(jiǎn)單的一種數(shù)據(jù)結(jié)構(gòu)是最常用且最簡(jiǎn)單的一種數(shù)據(jù)結(jié)構(gòu) 是是n n個(gè)數(shù)據(jù)元素的有限序列個(gè)數(shù)據(jù)元素的有限序列 其中數(shù)據(jù)元素可以是各種各樣的，包括一個(gè)數(shù)、其中數(shù)據(jù)元素可以是各種各樣的，包括一個(gè)數(shù)、一個(gè)符號(hào)、一條記錄等一個(gè)符號(hào)、一條記錄等 同一線性表中的元素必定同一線性表中的元素必定具有相同特性具有相同特性，即屬同，即屬同一數(shù)據(jù)對(duì)象一數(shù)據(jù)對(duì)象 相鄰數(shù)據(jù)元素之間存在序偶關(guān)系相鄰數(shù)據(jù)元素之間存在序偶關(guān)系4

3、計(jì)算機(jī)與控制工程學(xué)院線性表線性表 實(shí)例形式：實(shí)例形式： ( (e e1 1, , e e2 2, , e en n) )nn有窮自然數(shù)，表的長(zhǎng)度有窮自然數(shù)，表的長(zhǎng)度e ei i表中元素，視為表中元素，視為原子原子n n = 0= 0，空表，空表 n 0n 0，e e1 1第一個(gè)元素，第一個(gè)元素，e en n最后一個(gè)元素最后一個(gè)元素e el l優(yōu)先于優(yōu)先于e e2 2，e e2 2優(yōu)先于優(yōu)先于e e3 3，僅有的元素間僅有的元素間關(guān)系關(guān)系5計(jì)算機(jī)與控制工程學(xué)院線性表舉例線性表舉例 字母表字母表 (A,B,C,Z)(A,B,C,Z) 奧斯卡近奧斯卡近1010年年 最佳影片最佳影片6年份年份片名片名

4、2006Crash2007The Departed2008No Country for Old Men2009Slumdog Millionaire2010The Hurt Locker2011The Kings Speech 2012The Artist 2013Argo 201412 years a slave2015Birdman計(jì)算機(jī)與控制工程學(xué)院線性表操作線性表操作 創(chuàng)建一個(gè)線性表創(chuàng)建一個(gè)線性表 確定線性表是否為空確定線性表是否為空 確定線性表的長(zhǎng)度確定線性表的長(zhǎng)度 查找第查找第k k個(gè)元素個(gè)元素 查找指定的元素查找指定的元素 刪除第刪除第k k個(gè)元素個(gè)元素 在第在第k k個(gè)元素之后

5、插入一個(gè)新元素個(gè)元素之后插入一個(gè)新元素7數(shù)據(jù)數(shù)據(jù)是計(jì)算機(jī)的處理對(duì)象，也是計(jì)算機(jī)的關(guān)鍵所在。數(shù)據(jù)操作包括增、刪、增、刪、改、查改、查四種計(jì)算機(jī)與控制工程學(xué)院線性表之線性表之ADTADT8抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型LinearList LinearList 實(shí)例實(shí)例0 0或多個(gè)元素的有序集合或多個(gè)元素的有序集合操作操作CreateCreate()()： 創(chuàng)建一個(gè)空線性表創(chuàng)建一個(gè)空線性表DestroyDestroy()()： 刪除表刪除表IsEmptyIsEmpty()()： 如果表為空則返回如果表為空則返回truetrue，否則返回，否則返回falsefalseLengthLength()()： 返

6、回表的大小返回表的大小( (即表中元素個(gè)數(shù)即表中元素個(gè)數(shù)) ) FindFind( (k k, ,x x) )： 尋找表中第尋找表中第k k個(gè)元素，并把它保存到個(gè)元素，并把它保存到x x中；如果不存中；如果不存 在，則返回在，則返回falsefalseSearchSearch( (x x) )： 返回元素返回元素x x在表中的位置；如果在表中的位置；如果x x不在表中，返回不在表中，返回0 0DeleteDelete( (k k, ,x x) )：刪除表中第：刪除表中第k k個(gè)元素，并把它保存到個(gè)元素，并把它保存到x x中；函數(shù)返回中；函數(shù)返回 修改后的線性表修改后的線性表InsertInse

7、rt( (k k, ,x x) )：在第：在第k k個(gè)元素之后插入個(gè)元素之后插入x x；函數(shù)返回修改后的線性表；函數(shù)返回修改后的線性表OutputOutput( (outout) )：把線性表放入輸出流：把線性表放入輸出流outout之中之中 計(jì)算機(jī)與控制工程學(xué)院提出問(wèn)題提出問(wèn)題 我們已經(jīng)知道了我們已經(jīng)知道了 線性表應(yīng)該是什么樣子的線性表應(yīng)該是什么樣子的 線性表應(yīng)該具備哪些功能線性表應(yīng)該具備哪些功能 這些構(gòu)成了線性表的這些構(gòu)成了線性表的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu) 接下來(lái)，一個(gè)自然而然的問(wèn)題是接下來(lái)，一個(gè)自然而然的問(wèn)題是 線性表的線性表的物理結(jié)構(gòu)物理結(jié)構(gòu)應(yīng)該是怎樣的？應(yīng)該是怎樣的？9e1e2en計(jì)算機(jī)與控

8、制工程學(xué)院主要內(nèi)容主要內(nèi)容 基本概念基本概念 線性表的描述與分析線性表的描述與分析 公式化描述（順序表示）公式化描述（順序表示） 鏈表描述鏈表描述 間接尋址間接尋址 線性表的應(yīng)用線性表的應(yīng)用10計(jì)算機(jī)與控制工程學(xué)院H1.H1.線性表的公式化描述線性表的公式化描述 公式化描述（順序存儲(chǔ)）公式化描述（順序存儲(chǔ)） 用數(shù)組來(lái)描述線性表實(shí)例用數(shù)組來(lái)描述線性表實(shí)例 數(shù)組位置數(shù)組位置單元（單元（cellcell）、節(jié)點(diǎn)（）、節(jié)點(diǎn)（nodenode） 每個(gè)數(shù)組單元保存線性表的一個(gè)元素每個(gè)數(shù)組單元保存線性表的一個(gè)元素11e1e2en計(jì)算機(jī)與控制工程學(xué)院C+C+類定義類定義12templateclass Line

9、arList public: LinearList(int MaxListSize = 10); / 構(gòu)造函數(shù)構(gòu)造函數(shù) LinearList() delete element; / 析構(gòu)函數(shù)析構(gòu)函數(shù) bool IsEmpty() const return length = 0; int Length() const return length; bool Find(int k, T& x) const; / 返回列表的第返回列表的第k個(gè)元素個(gè)元素 int Search(const T& x) const; / 返回返回x的位置的位置 LinearList& Delete

10、(int k, T& x); / 刪除第刪除第k個(gè)元素，將其保存在個(gè)元素，將其保存在x中中 LinearList& Insert(int k, const T& x); / 在第在第k個(gè)元素后插入個(gè)元素后插入x void Output(ostream& out) const; private: int length; int MaxSize; T *element; / 一維動(dòng)態(tài)數(shù)組一維動(dòng)態(tài)數(shù)組;計(jì)算機(jī)與控制工程學(xué)院C+C+實(shí)現(xiàn)：創(chuàng)建和釋放實(shí)現(xiàn)：創(chuàng)建和釋放templateLinearList:LinearList(int MaxListSize)/ Constr

11、uctor for formula-based linear list. MaxSize = MaxListSize; element = new TMaxSize; length = 0;LinearList() delete element;13計(jì)算機(jī)與控制工程學(xué)院C+C+實(shí)現(xiàn)：實(shí)現(xiàn)：Find(1n)Find(1n)templatebool LinearList:Find(int k, T& x) const/ Set x to the kth element of the list. / Return false if no kth; true otherwise. if (k

12、length) return false; / no kth x = elementk - 1; return true; 時(shí)間復(fù)雜性：時(shí)間復(fù)雜性：(1)(1) 因其關(guān)鍵操作只有一條賦值語(yǔ)句因其關(guān)鍵操作只有一條賦值語(yǔ)句14計(jì)算機(jī)與控制工程學(xué)院C+C+實(shí)現(xiàn)：實(shí)現(xiàn)：SearchSearchtemplateint LinearList:Search(const T& x) const/ Locate x. Return position of x if found. / Return 0 if x not in list. for (int i = 0; i length; i+) if (

13、elementi = x) return +i; return 0; 時(shí)間復(fù)雜性：時(shí)間復(fù)雜性：(length)(length)15計(jì)算機(jī)與控制工程學(xué)院刪除元素刪除元素DeleteDelete 刪除第刪除第k k個(gè)元素個(gè)元素 k k是否合法是否合法OutOfBoundsOutOfBounds異常，異常， (1)(1) 元素元素k+1, k+2, , lengthk+1, k+2, , length向前移動(dòng)一個(gè)位置向前移動(dòng)一個(gè)位置消除空位，消除空位，(length - k)s)(length - k)s)Delete(2, x)16計(jì)算機(jī)與控制工程學(xué)院C+C+實(shí)現(xiàn)：實(shí)現(xiàn)：DeleteDeletet

14、emplateLinearList& LinearList:Delete(int k, T& x) if (Find(k, x) / 當(dāng)當(dāng)k是個(gè)合理的值時(shí)是個(gè)合理的值時(shí) for (int i = k; i length; i+) elementi-1 = elementi; length-; return *this; else throw OutOfBounds(); / 當(dāng)當(dāng)k不是個(gè)合理的值時(shí)不是個(gè)合理的值時(shí) return *this; / visual needs this17(length - k)s)計(jì)算機(jī)與控制工程學(xué)院插入元素插入元素InsertInsert 插入到

15、第插入到第k k個(gè)元素之后個(gè)元素之后 k k是否合法是否合法OutOfBoundsOutOfBounds異常，異常， (1)(1) 另一種錯(cuò)誤：表滿另一種錯(cuò)誤：表滿數(shù)組無(wú)空間容納新元素，數(shù)組無(wú)空間容納新元素，拋出拋出NoMemNoMem異常，異常，(1)(1) 常規(guī)情況下，元素常規(guī)情況下，元素k+1, k+2, , lengthk+1, k+2, , length向后移向后移動(dòng)一個(gè)位置動(dòng)一個(gè)位置 (length - k)s)(length - k)s)18計(jì)算機(jī)與控制工程學(xué)院插入操作示意插入操作示意Insert(3, 7)19計(jì)算機(jī)與控制工程學(xué)院C+C+實(shí)現(xiàn)：實(shí)現(xiàn)：InsertInsertte

16、mplateLinearList& LinearList:Insert(int k, const T& x) if (k length) throw OutOfBounds();/k非法非法 if (length = MaxSize) throw NoMem(); /表空間滿表空間滿 for (int i = length-1; i = k; i-) /常規(guī)情況常規(guī)情況 elementi+1 = elementi; elementk = x; length+; return *this;20計(jì)算機(jī)與控制工程學(xué)院C+C+實(shí)現(xiàn)：實(shí)現(xiàn)：OutputOutputtemplatevoid

17、 LinearList:Output(ostream& out) const/ Put the list into the stream out. for (int i = 0; i length; i+) out elementi ;/ overload template ostream& operator(ostream& out, const LinearList& x) x.Output(out); return out; (length)(length)21計(jì)算機(jī)與控制工程學(xué)院使用示例使用示例 創(chuàng)建一個(gè)大小為創(chuàng)建一個(gè)大小為5 5的整數(shù)線性表的整數(shù)線性表

18、L L 輸出該表的長(zhǎng)度（輸出該表的長(zhǎng)度（0 0） 在第在第0 0個(gè)元素之后插入個(gè)元素之后插入2 2（表為（表為2 2） 在第一個(gè)元素之后插入在第一個(gè)元素之后插入6 6（表為（表為2 2，6 6） 尋找并輸出第一個(gè)元素（尋找并輸出第一個(gè)元素（2 2） 輸出表的長(zhǎng)度（輸出表的長(zhǎng)度（2 2） 刪除并輸出第一個(gè)元素（刪除并輸出第一個(gè)元素（6 6）22計(jì)算機(jī)與控制工程學(xué)院程序程序#include #include llist.h#include xcept.h“void main(void) try LinearList L(5); cout Length = L.Length() endl; cout

19、 IsEmpty = L.IsEmpty() endl; L.Insert(0,2).Insert(1,6); cout List is L endl; cout IsEmpty = L.IsEmpty() endl;23計(jì)算機(jī)與控制工程學(xué)院程序（續(xù)）程序（續(xù)） int z; L.Find(1,z); cout First element is z endl; cout Length = L.Length() endl; L.Delete(1,z); cout Deleted element is z endl; cout List is L endl; catch (.) cerr An e

20、xception has occurred endl; 24計(jì)算機(jī)與控制工程學(xué)院評(píng)價(jià)評(píng)價(jià) 空間效率低空間效率低 三個(gè)表，元素總數(shù)不超過(guò)三個(gè)表，元素總數(shù)不超過(guò)50005000個(gè)，但任何一個(gè)表的個(gè)，但任何一個(gè)表的元素都可能達(dá)到元素都可能達(dá)到50005000個(gè)個(gè) 必須為每個(gè)表分配必須為每個(gè)表分配50005000個(gè)元素的空間，共需個(gè)元素的空間，共需1500015000個(gè)個(gè)元素的空間元素的空間 提高空間效率思路：三個(gè)表共用一個(gè)數(shù)組提高空間效率思路：三個(gè)表共用一個(gè)數(shù)組 兩個(gè)額外數(shù)組兩個(gè)額外數(shù)組 firstifirsti第第i i個(gè)表的第一個(gè)元素在數(shù)組中的位置個(gè)表的第一個(gè)元素在數(shù)組中的位置 lastilas

21、ti第第i i個(gè)表最后一個(gè)元素在數(shù)組中的位置個(gè)表最后一個(gè)元素在數(shù)組中的位置25計(jì)算機(jī)與控制工程學(xué)院多個(gè)表共享空間多個(gè)表共享空間 設(shè)置兩個(gè)虛擬邊界表設(shè)置兩個(gè)虛擬邊界表 first0=last0=-1first0=last0=-1 firstm+1=lastm+1=MaxSize-1firstm+1=lastm+1=MaxSize-1 可使所有表的處理均相同，無(wú)需特別處理表可使所有表的處理均相同，無(wú)需特別處理表1 1和表和表m m26計(jì)算機(jī)與控制工程學(xué)院新元素插入表新元素插入表i i的位置的位置k k之后之后 不僅要考慮表內(nèi)元素的移動(dòng)，由于共享一個(gè)數(shù)不僅要考慮表內(nèi)元素的移動(dòng)，由于共享一個(gè)數(shù)組，還要

22、考慮相鄰表的銜接組，還要考慮相鄰表的銜接 最好情況：僅需表最好情況：僅需表i i內(nèi)部元素移動(dòng)內(nèi)部元素移動(dòng) 表表i i和和i+1i+1之間有空位：之間有空位：lasti firsti+1lasti firsti+1，k+1lengthk+1length后移后移一個(gè)位置一個(gè)位置 表表i-1i-1和表和表i i之間有空位：之間有空位：lasti-1 firstilasti-1 firsti，元素元素1k-11k-1前移前移一個(gè)位置一個(gè)位置27計(jì)算機(jī)與控制工程學(xué)院插入操作（續(xù)）插入操作（續(xù)） 需相鄰表移動(dòng)的情況需相鄰表移動(dòng)的情況 表表j-1j-1表表j j（jijiki）之間有空位，表）之間有空位，表

23、i+1ki+1k后移后移 效率差！效率差！ 為了改善空間復(fù)雜性，搞壞了時(shí)間復(fù)雜性為了改善空間復(fù)雜性，搞壞了時(shí)間復(fù)雜性28計(jì)算機(jī)與控制工程學(xué)院H1.H1.線性表順序存儲(chǔ)小結(jié)線性表順序存儲(chǔ)小結(jié) 常數(shù)級(jí)操作常數(shù)級(jí)操作( (1) ) IsEmptyIsEmpty LengthLength FindFind 線性操作線性操作( (n)-)-近似近似 SearchSearch DeleteDelete InsertInsert OutputOutput29計(jì)算機(jī)與控制工程學(xué)院主要內(nèi)容主要內(nèi)容 基本概念基本概念 線性表的描述與分析線性表的描述與分析 公式化描述公式化描述 鏈表描述鏈表描述 間接尋址間接尋址

24、線性表的應(yīng)用線性表的應(yīng)用30計(jì)算機(jī)與控制工程學(xué)院H2.H2.線性表的鏈表描述線性表的鏈表描述 與公式化描述的本質(zhì)區(qū)別：與公式化描述的本質(zhì)區(qū)別：數(shù)據(jù)結(jié)構(gòu)中的關(guān)聯(lián)元素不保證存儲(chǔ)空間上的數(shù)據(jù)結(jié)構(gòu)中的關(guān)聯(lián)元素不保證存儲(chǔ)空間上的關(guān)聯(lián)關(guān)聯(lián)定位定位O(1)O(1)O(n)O(n) 節(jié)點(diǎn)內(nèi)容節(jié)點(diǎn)內(nèi)容 數(shù)據(jù)對(duì)象實(shí)例的元素?cái)?shù)據(jù)對(duì)象實(shí)例的元素 為了正確定位，必須保留關(guān)聯(lián)節(jié)點(diǎn)的位置為了正確定位，必須保留關(guān)聯(lián)節(jié)點(diǎn)的位置31計(jì)算機(jī)與控制工程學(xué)院線性表的鏈表描述線性表的鏈表描述 線性表線性表L=(L=(e e1 1, , e e2 2, , e en n) ) 每個(gè)元素每個(gè)元素e ei i放在不同節(jié)點(diǎn)的放在不同節(jié)點(diǎn)的數(shù)據(jù)域

25、數(shù)據(jù)域內(nèi)內(nèi) 僅有的結(jié)構(gòu)就是元素次序，僅有的結(jié)構(gòu)就是元素次序，“e el l優(yōu)先于優(yōu)先于e e2 2，e e2 2優(yōu)優(yōu)先于先于e e3 3，”所謂所謂“關(guān)聯(lián)關(guān)聯(lián)”，就是下一個(gè)，就是下一個(gè)節(jié)點(diǎn)節(jié)點(diǎn) 節(jié)點(diǎn)節(jié)點(diǎn)e ei i的的鏈接域鏈接域（指針域）保存指向節(jié)點(diǎn)（指針域）保存指向節(jié)點(diǎn)e ei+1i+1的的指針指針32計(jì)算機(jī)與控制工程學(xué)院線性表的鏈表描述（續(xù)）線性表的鏈表描述（續(xù)） e en n的鏈接域設(shè)置為的鏈接域設(shè)置為NULLNULL（0 0）無(wú)后繼節(jié)點(diǎn)無(wú)后繼節(jié)點(diǎn)尾節(jié)點(diǎn)尾節(jié)點(diǎn) e e1 1首節(jié)點(diǎn)，沒(méi)有其他節(jié)點(diǎn)的鏈接域指向它，首節(jié)點(diǎn)，沒(méi)有其他節(jié)點(diǎn)的鏈接域指向它，首指針首指針正確定位數(shù)據(jù)的關(guān)鍵！正確定位數(shù)

26、據(jù)的關(guān)鍵！ 單向鏈表單向鏈表鏈（鏈（chainchain）33計(jì)算機(jī)與控制工程學(xué)院鏈表節(jié)點(diǎn)：鏈表節(jié)點(diǎn)：ChainNodeChainNodetemplate class ChainNode friend Chain; friend ChainIterator;private: T data; /數(shù)據(jù)域 ChainNode *link; /鏈接域34計(jì)算機(jī)與控制工程學(xué)院?jiǎn)蜗蜴湵恚簡(jiǎn)蜗蜴湵恚篊hainChaintemplateclass Chain friend ChainIterator; public: Chain() first = 0; Chain(); bool IsEmpty() con

27、st return first = 0; int Length() const; bool Find(int k, T& x) const; int Search(const T& x) const; Chain& Delete(int k, T& x); Chain& Insert(int k, const T& x); void Output(ostream& out) const; private: ChainNode *first; / 首指針：特別重要！首指針：特別重要！;使用鏈Chain L;35計(jì)算機(jī)與控制工程學(xué)院析構(gòu)函數(shù)：

28、刪除鏈表中所有析構(gòu)函數(shù)：刪除鏈表中所有節(jié)點(diǎn)節(jié)點(diǎn)templateChain:Chain() ChainNode *next; / 臨時(shí)變量，用于控制指針臨時(shí)變量，用于控制指針 while (first) /當(dāng)下一個(gè)節(jié)點(diǎn)存在當(dāng)下一個(gè)節(jié)點(diǎn)存在 next = first-link; delete first; first = next; 【繪圖演示繪圖演示】時(shí)間復(fù)雜性時(shí)間復(fù)雜性(n)(n)資源，而非內(nèi)容36計(jì)算機(jī)與控制工程學(xué)院lengthlength操作操作確定鏈表長(zhǎng)度確定鏈表長(zhǎng)度templateint Chain:Length() const ChainNode *current = first;

29、/ 臨時(shí)變量，用于控制指針臨時(shí)變量，用于控制指針 int len = 0; while (current) len+; current = current-link; return len; 時(shí)間復(fù)雜性時(shí)間復(fù)雜性(n)(n)37計(jì)算機(jī)與控制工程學(xué)院查找操作查找操作templatebool Chain:Find(int k, T& x) const if (k 1) return false; ChainNode *current = first; int index = 1; / 用于與用于與k比對(duì)比對(duì) while (index link; index+; if (current) x

30、 = current-data; return true; return false; 尋找第k個(gè)元素復(fù)雜性為(k)公式描述為(1)情況1：目標(biāo)非法，k過(guò)小情況2：目標(biāo)合法，且存在情況3：目標(biāo)非法，k過(guò)大38計(jì)算機(jī)與控制工程學(xué)院搜索操作搜索操作templateint Chain:Search(const T& x) const ChainNode *current = first; int index = 1; / 用于記錄用于記錄x所在位置所在位置k while (current & current-data != x) current = current-link; ind

31、ex+; if (current) return index; return 0;復(fù)雜性為復(fù)雜性為(n)(n) 公式描述也為公式描述也為(n)(n)39計(jì)算機(jī)與控制工程學(xué)院輸出函數(shù)輸出函數(shù)templatevoid Chain:Output(ostream& out) const ChainNode *current; for (current = first; current; current = current-link) out data ;template ostream& operator(ostream& out, const Chain& x) x.

32、Output(out); return out;復(fù)雜性為復(fù)雜性為(n)(n)40計(jì)算機(jī)與控制工程學(xué)院刪除元素的方法刪除元素的方法找到前驅(qū)和后繼找到前驅(qū)和后繼令前驅(qū)的鏈接域指向后繼令前驅(qū)的鏈接域指向后繼釋放釋放被刪除節(jié)點(diǎn)所占用的內(nèi)存空間被刪除節(jié)點(diǎn)所占用的內(nèi)存空間41計(jì)算機(jī)與控制工程學(xué)院刪除操作的實(shí)現(xiàn)刪除操作的實(shí)現(xiàn)templateChain& Chain:Delete(int k, T& x) if (k 1 | !first) throw OutOfBounds(); / k不合法或列表空不合法或列表空 ChainNode *p = first; / 臨時(shí)變量，最終指向第臨時(shí)變量

33、，最終指向第k個(gè)元素個(gè)元素 if (k = 1) / 刪除第一個(gè)元素刪除第一個(gè)元素 first = first-link; / 令列表頭指向下一節(jié)點(diǎn)令列表頭指向下一節(jié)點(diǎn)刪除表頭刪除表頭情況1：目標(biāo)非法，因其過(guò)小或表為空情況2：目標(biāo)合法，刪第一個(gè)元素情況3：目標(biāo)合法，刪其他元素情況4：目標(biāo)非法，因其過(guò)大42計(jì)算機(jī)與控制工程學(xué)院刪除操作的實(shí)現(xiàn)刪除操作的實(shí)現(xiàn) else / p獲取獲取k-1個(gè)元素個(gè)元素 ChainNode *q = first; for (int index = 1; index link; /這句話是關(guān)鍵：指針右移！這句話是關(guān)鍵：指針右移！ if (!q | !q-link) th

34、row OutOfBounds(); / k列表長(zhǎng)度列表長(zhǎng)度 p = q-link; / kth q-link = p-link; / k-1項(xiàng)指向項(xiàng)指向k+1項(xiàng)項(xiàng) / 釋放第釋放第k項(xiàng)占用的內(nèi)存空間項(xiàng)占用的內(nèi)存空間 x = p-data; delete p; return *this;【繪圖演示】43計(jì)算機(jī)與控制工程學(xué)院插入元素的方法插入元素的方法 新節(jié)點(diǎn)插入在第新節(jié)點(diǎn)插入在第k k個(gè)元素的后面，個(gè)元素的后面，O(k)O(k) k=0k=0：新節(jié)點(diǎn)成為新的首節(jié)點(diǎn)，將它的：新節(jié)點(diǎn)成為新的首節(jié)點(diǎn)，將它的linklink指向原首指向原首節(jié)點(diǎn)，而線性表的節(jié)點(diǎn)，而線性表的firstfirst指針指向新

35、節(jié)點(diǎn)指針指向新節(jié)點(diǎn) k k0 0：令節(jié)點(diǎn)：令節(jié)點(diǎn)k k的的linklink域指向新節(jié)點(diǎn)，新節(jié)點(diǎn)的域指向新節(jié)點(diǎn)，新節(jié)點(diǎn)的linklink指向原來(lái)的節(jié)點(diǎn)指向原來(lái)的節(jié)點(diǎn)k+1k+144計(jì)算機(jī)與控制工程學(xué)院插入操作的實(shí)現(xiàn)插入操作的實(shí)現(xiàn)templateChain& Chain:Insert(int k, const T& x) if (k 0) throw OutOfBounds(); ChainNode *p = first; / 臨時(shí)變量，最終指向第臨時(shí)變量，最終指向第k個(gè)個(gè)元素元素 for (int index = 1; index link; if (k 0 & !p)

36、throw OutOfBounds(); / k列表長(zhǎng)度列表長(zhǎng)度情況1：目標(biāo)非法，因其過(guò)小情況2：目標(biāo)非法，因其過(guò)大情況3：目標(biāo)合法，插入到表中或表后情況4：目標(biāo)合法，插入到表頭【繪圖演示】45計(jì)算機(jī)與控制工程學(xué)院插入操作的實(shí)現(xiàn)（續(xù)）插入操作的實(shí)現(xiàn)（續(xù)） / insert ChainNode *y = new ChainNode; y-data = x; if (k) / 插入插入p后面后面 y-link = p-link; / 新元素指向原新元素指向原k+1項(xiàng)項(xiàng) p-link = y; / 第第k項(xiàng)指向新元素項(xiàng)指向新元素 else / 插入第一個(gè)位置插入第一個(gè)位置 y-link = firs

37、t; / 新元素指向原表頭新元素指向原表頭 first = y; / 新元素作為新表頭新元素作為新表頭 return *this;這兩句話能互換順序嗎？這兩句話能互換順序嗎？46計(jì)算機(jī)與控制工程學(xué)院鏈表描述引出的新操作鏈表描述引出的新操作 EraseErase：刪除鏈表所有節(jié)點(diǎn)，釋放內(nèi)存空間：刪除鏈表所有節(jié)點(diǎn)，釋放內(nèi)存空間templatevoid Chain:Erase() ChainNode *next; while (first) next = first-link; delete first; first = next; 47計(jì)算機(jī)與控制工程學(xué)院ZeroZero操作操作 清空列表，但不刪

38、除任何節(jié)點(diǎn)，不釋放內(nèi)存清空列表，但不刪除任何節(jié)點(diǎn)，不釋放內(nèi)存空間，僅斷開空間，僅斷開firstfirst指針與鏈表節(jié)點(diǎn)的連接指針與鏈表節(jié)點(diǎn)的連接 void Zero() first = 0;48計(jì)算機(jī)與控制工程學(xué)院AppendAppend操作操作 在鏈表末端添加一個(gè)元素在鏈表末端添加一個(gè)元素 新增一個(gè)數(shù)據(jù)成員新增一個(gè)數(shù)據(jù)成員lastlast來(lái)跟蹤尾節(jié)點(diǎn)來(lái)跟蹤尾節(jié)點(diǎn)templateChain& Chain:Append(const T& x) ChainNode *y; y = new ChainNode; y-data = x; y-link = 0; if (first) /

39、 chain is not empty last-link = y; last = y; else / chain is empty first = last = y; return *this;49計(jì)算機(jī)與控制工程學(xué)院循環(huán)鏈表循環(huán)鏈表 優(yōu)化操作實(shí)現(xiàn)的兩種鏈表形式優(yōu)化操作實(shí)現(xiàn)的兩種鏈表形式 單向循環(huán)鏈表（單向循環(huán)鏈表（singly linked circular listsingly linked circular list），），簡(jiǎn)稱循環(huán)鏈表（簡(jiǎn)稱循環(huán)鏈表（circular listcircular list）鏈表最后一個(gè)節(jié)點(diǎn)指向第一個(gè)節(jié)點(diǎn)鏈表最后一個(gè)節(jié)點(diǎn)指向第一個(gè)節(jié)點(diǎn) 鏈表前部附加一個(gè)頭節(jié)

40、點(diǎn)（鏈表前部附加一個(gè)頭節(jié)點(diǎn)（head nodehead node）50計(jì)算機(jī)與控制工程學(xué)院兩種改進(jìn)形式的結(jié)構(gòu)兩種改進(jìn)形式的結(jié)構(gòu)51計(jì)算機(jī)與控制工程學(xué)院優(yōu)化的優(yōu)化的SearchSearch函數(shù)函數(shù)【帶頭節(jié)點(diǎn)帶頭節(jié)點(diǎn)】templateint CircularList:Search(const T& x) const ChainNode *current = first-link; int index = 1; first-data = x; /關(guān)鍵：設(shè)置一個(gè)終止條件關(guān)鍵：設(shè)置一個(gè)終止條件 while (current-data != x) current = current-link; i

41、ndex+; / are we at head? return (current = first) ? 0 : index);52計(jì)算機(jī)與控制工程學(xué)院雙向鏈表雙向鏈表 每個(gè)節(jié)點(diǎn)兩個(gè)指針每個(gè)節(jié)點(diǎn)兩個(gè)指針 LeftLeft指向前一節(jié)點(diǎn)指向前一節(jié)點(diǎn) RightRight指向后一節(jié)點(diǎn)指向后一節(jié)點(diǎn) 進(jìn)一步簡(jiǎn)化代碼設(shè)計(jì)進(jìn)一步簡(jiǎn)化代碼設(shè)計(jì)53計(jì)算機(jī)與控制工程學(xué)院雙向鏈表節(jié)點(diǎn)雙向鏈表節(jié)點(diǎn)template class DoubleNode friend Double; private: T data; DoubleNode *left, *right;54計(jì)算機(jī)與控制工程學(xué)院雙向鏈表類實(shí)現(xiàn)（續(xù)）雙向鏈表類實(shí)現(xiàn)（

42、續(xù)）templateclass Double public: Double() LeftEnd = RightEnd = 0; Double(); int Length() const; bool Find(int k, T& x) const; int Search(const T& x) const; Double& Delete(int k, T& x); Double& Insert(int k, const T& x); void Output(ostream& out) const; private: DoubleNode *

43、LeftEnd, *RightEnd;雙向循環(huán)鏈表可省掉RightEnd55計(jì)算機(jī)與控制工程學(xué)院H2H2小結(jié)小結(jié) 單向鏈表單向鏈表 單向循環(huán)鏈表單向循環(huán)鏈表 帶頭節(jié)點(diǎn)的單向循環(huán)鏈表帶頭節(jié)點(diǎn)的單向循環(huán)鏈表 雙向鏈表雙向鏈表 雙向循環(huán)鏈表雙向循環(huán)鏈表56計(jì)算機(jī)與控制工程學(xué)院H2H2小結(jié)（續(xù)）小結(jié)（續(xù)） 空間復(fù)雜性空間復(fù)雜性 公式化公式化空間全部用來(lái)保存列表元素空間全部用來(lái)保存列表元素鏈表鏈表額外空間保存鏈接指針額外空間保存鏈接指針 鏈表鏈表動(dòng)態(tài)分配，占用空間與當(dāng)前列表大小成比動(dòng)態(tài)分配，占用空間與當(dāng)前列表大小成比例，利用率高例，利用率高公式化公式化靜態(tài)分配，無(wú)法預(yù)測(cè)實(shí)際需求，浪費(fèi)或靜態(tài)分配，無(wú)法預(yù)測(cè)

44、實(shí)際需求，浪費(fèi)或不足不足 時(shí)間復(fù)雜性時(shí)間復(fù)雜性 插入、刪除操作，鏈表描述性能更好插入、刪除操作，鏈表描述性能更好 隨機(jī)訪問(wèn)，公式化描述性能更優(yōu)隨機(jī)訪問(wèn)，公式化描述性能更優(yōu)57計(jì)算機(jī)與控制工程學(xué)院快速練習(xí)快速練習(xí) 已知單向鏈表節(jié)點(diǎn)的定義，請(qǐng)寫出以下函數(shù)已知單向鏈表節(jié)點(diǎn)的定義，請(qǐng)寫出以下函數(shù)的的C+C+實(shí)現(xiàn)實(shí)現(xiàn) Chain(); int Length() const; bool Find(int k, T& x) const; int Search(const T& x) const; Chain& Delete(int k, T& x); Chain& I

45、nsert(int k, const T& x);58template class ChainNode friend Chain;private: T data; ChainNode *link;計(jì)算機(jī)與控制工程學(xué)院順序表順序表 VSVS 單向鏈表單向鏈表59操作操作(ADT)順序表順序表單向鏈表單向鏈表Destroy(1)(1)(n)(n)IsEmpty(1)(1)(1)(1)Length(1)(1)(n)(n)Find(1)(1)(k)(k)Search(n)(n)(n)(n)Delete(n-k)s)(n-k)s)(k)(k)Insert(n-k)s)(n-k)s)(k)(k)O

46、utput(n)(n)(n)(n)計(jì)算機(jī)與控制工程學(xué)院主要內(nèi)容主要內(nèi)容 基本概念基本概念 線性表的描述與分析線性表的描述與分析 公式化描述公式化描述 鏈表描述鏈表描述 間接尋址間接尋址 線性表的應(yīng)用線性表的應(yīng)用60計(jì)算機(jī)與控制工程學(xué)院間接尋址間接尋址 元素的存儲(chǔ)元素的存儲(chǔ)鏈接方式，動(dòng)態(tài)存儲(chǔ)，通過(guò)指鏈接方式，動(dòng)態(tài)存儲(chǔ)，通過(guò)指針訪問(wèn)，連續(xù)元素存儲(chǔ)不連續(xù)針訪問(wèn)，連續(xù)元素存儲(chǔ)不連續(xù) 指針的組織指針的組織公式化方式，連續(xù)元素的指針公式化方式，連續(xù)元素的指針在存儲(chǔ)上是連續(xù)的在存儲(chǔ)上是連續(xù)的61計(jì)算機(jī)與控制工程學(xué)院元素元素i i的定位方式的定位方式 首先找到元素指針首先找到元素指針tablei-1table

47、i-1公式化公式化 再由指針找到元素再由指針找到元素多一次多一次間接尋址間接尋址 鏈表描述：指針?lè)稚⒃诠?jié)點(diǎn)中鏈表描述：指針?lè)稚⒃诠?jié)點(diǎn)中類似超鏈接類似超鏈接方式方式 間接尋址：指針集中在數(shù)組中間接尋址：指針集中在數(shù)組中類似目錄索類似目錄索引方式引方式62計(jì)算機(jī)與控制工程學(xué)院間接尋址列表類定義間接尋址列表類定義templateclass IndirectList public: IndirectList(int MaxListSize = 10); / constructor IndirectList(); / destructor bool IsEmpty() const return leng

48、th = 0; int Length() const return length; bool Find(int k, T& x) const; int Search(const T& x) const;(1)，與公式化描述的實(shí)現(xiàn)非常相似63計(jì)算機(jī)與控制工程學(xué)院間接尋址列表類定義（續(xù)）間接尋址列表類定義（續(xù)） IndirectList& Delete(int k, T& x); IndirectList& Insert(int k, const T& x); void Output(ostream& out) const; private:

49、 T *table; / 1D array of T pointers int length, MaxSize;64計(jì)算機(jī)與控制工程學(xué)院構(gòu)造函數(shù)和析構(gòu)函數(shù)構(gòu)造函數(shù)和析構(gòu)函數(shù)templateIndirectList:IndirectList(int MaxListSize)/ Constructor. MaxSize = MaxListSize; table = new T *MaxSize; length = 0;templateIndirectList:IndirectList()/ Delete the list. for (int i = 0; i length; i+) delete

50、tablei; delete table;數(shù)組保存元素指針，比元素所需空間少很多，可一定程度解決公式化描述的缺點(diǎn)65計(jì)算機(jī)與控制工程學(xué)院FindFind函數(shù)的實(shí)現(xiàn)函數(shù)的實(shí)現(xiàn)templatebool IndirectList:Find(int k, T& x) const/ Set x to the kth element in the chain. / Return false if no kth; return true otherwise. if (k length) return false; / no kth x = *tablek - 1; return true; (1)(

51、1)，與公式化描述實(shí)現(xiàn)相似，與公式化描述實(shí)現(xiàn)相似 FindFind、LengthLength、IsEmptyIsEmpty隨機(jī)訪問(wèn)（根隨機(jī)訪問(wèn)（根據(jù)元素索引編號(hào)訪問(wèn)）據(jù)元素索引編號(hào)訪問(wèn)）66計(jì)算機(jī)與控制工程學(xué)院刪除操作刪除操作templateIndirectList& IndirectList:Delete(int k, T& x)/ Set x to the kth element and delete it. / Throw OutOfBounds exception if no kth element. if (Find(k, x) / move pointers k+1

52、, ., down for (int i = k; i length; i+) tablei-1 = tablei; length-; return *this; else throw OutOfBounds(); return *this; / Visual needs this line公式化：定位(1)，刪除元素移動(dòng)(length - k)s)鏈表：定位(k)，刪除(1) 間接：定位(1)，刪除指針移動(dòng)(length k)67計(jì)算機(jī)與控制工程學(xué)院插入操作插入操作templateIndirectList& IndirectList:Insert(int k, const T&

53、; x)/ Insert x after the kth element. if (k length) throw OutOfBounds(); if (length = MaxSize) throw NoMem(); / move one up for (int i = length-1; i = k; i-) tablei+1 = tablei; tablek = new T; *tablek = x; length+; return *this;時(shí)間復(fù)雜性類似刪除操作68計(jì)算機(jī)與控制工程學(xué)院間接尋址小結(jié)間接尋址小結(jié) 結(jié)合公式化描述和鏈表描述的優(yōu)點(diǎn)結(jié)合公式化描述和鏈表描述的優(yōu)點(diǎn) 定位元素是

54、定位元素是(1)(1) 其他多數(shù)操作也是其他多數(shù)操作也是(1)(1)，而不是，而不是(n)(n)！ 插入、刪除無(wú)需移動(dòng)數(shù)據(jù)插入、刪除無(wú)需移動(dòng)數(shù)據(jù) 空間上接近鏈表，優(yōu)于公式化空間上接近鏈表，優(yōu)于公式化69計(jì)算機(jī)與控制工程學(xué)院幾種描述方法的比較幾種描述方法的比較 間接尋址結(jié)合了公式化和鏈表的優(yōu)點(diǎn)，適用于間接尋址結(jié)合了公式化和鏈表的優(yōu)點(diǎn)，適用于 表元素本身很大表元素本身很大 插入、刪除操作頻繁插入、刪除操作頻繁 確定表長(zhǎng)度、按編號(hào)訪問(wèn)元素操作頻繁確定表長(zhǎng)度、按編號(hào)訪問(wèn)元素操作頻繁描述方法描述方法操作操作查找第查找第k個(gè)元素個(gè)元素刪除第刪除第k個(gè)元素個(gè)元素插入第插入第k元素后元素后公式化公式化(1)O

55、(n-k)s)O(n-k)s)鏈表鏈表O(k)O(k)O(k+s)間接尋址間接尋址(1)O(n-k)O(n-k)70計(jì)算機(jī)與控制工程學(xué)院主要內(nèi)容主要內(nèi)容 基本概念基本概念 線性表的描述與分析線性表的描述與分析 公式化描述公式化描述 鏈表描述鏈表描述 間接尋址間接尋址 線性表的應(yīng)用線性表的應(yīng)用71計(jì)算機(jī)與控制工程學(xué)院箱子排序（箱子排序（bin sortbin sort） 班級(jí)學(xué)生信息班級(jí)學(xué)生信息鏈表存儲(chǔ)鏈表存儲(chǔ) 按成績(jī)排序：按成績(jī)排序：O(nO(n2 2) ) 成績(jī)特點(diǎn)：成績(jī)特點(diǎn)：0 05 5分，有限個(gè)分，有限個(gè) 箱子箱子分?jǐn)?shù)，相同成績(jī)分?jǐn)?shù)，相同成績(jī)同一箱子同一箱子 箱子按順序連接箱子按順序連接

56、按分?jǐn)?shù)排序按分?jǐn)?shù)排序72計(jì)算機(jī)與控制工程學(xué)院箱子排序例箱子排序例73計(jì)算機(jī)與控制工程學(xué)院箱子排序?qū)崿F(xiàn)方法箱子排序?qū)崿F(xiàn)方法 箱子箱子鏈表鏈表 排序方法排序方法 逐個(gè)刪除鏈表每個(gè)節(jié)點(diǎn)，所刪除節(jié)點(diǎn)放入適當(dāng)?shù)南渲饌€(gè)刪除鏈表每個(gè)節(jié)點(diǎn)，所刪除節(jié)點(diǎn)放入適當(dāng)?shù)南渥又校矗翰迦胂鄳?yīng)鏈表）子中（即：插入相應(yīng)鏈表） 收集并鏈接所有箱子，產(chǎn)生排序鏈表收集并鏈接所有箱子，產(chǎn)生排序鏈表74計(jì)算機(jī)與控制工程學(xué)院箱子排序?qū)崿F(xiàn)方法箱子排序?qū)崿F(xiàn)方法 輸入鏈表為輸入鏈表為ChainChain類型：類型： 連續(xù)地刪除鏈表首元素并將其插入到相應(yīng)箱子鏈表連續(xù)地刪除鏈表首元素并將其插入到相應(yīng)箱子鏈表的首部的首部 逐個(gè)刪除每個(gè)箱子中的元素（

57、從最后一個(gè)箱子開始）逐個(gè)刪除每個(gè)箱子中的元素（從最后一個(gè)箱子開始）并將其插入到一個(gè)初始為空的鏈表的首部并將其插入到一個(gè)初始為空的鏈表的首部75計(jì)算機(jī)與控制工程學(xué)院鏈表數(shù)據(jù)域鏈表數(shù)據(jù)域NodeNode類類class Node friend ostream& operator(ostream&, const Node &); friend void BinSort(Chain&, int);public: int operator !=(Node x) const return (score != x.score); private: int score; char

58、 *name;ostream& operator(ostream& out, const Node& x) out x.score ; return out;Chain類需要Node類支持這兩個(gè)操作76計(jì)算機(jī)與控制工程學(xué)院箱子排序?qū)崿F(xiàn)箱子排序?qū)崿F(xiàn)void BinSort(Chain& X, int range)/ Sort by score. int len = X.Length(); Node x; Chain *bin; bin = new Chain range + 1; / 以下部分為關(guān)鍵：將元素放入箱子以下部分為關(guān)鍵：將元素放入箱子 for (int

59、i = 1; i = 0; j-) while (!binj.IsEmpty() binj.Delete(1,x); X.Insert(0,x); delete bin; DeleteDelete操作操作(1)(1) 第一個(gè)循環(huán)第一個(gè)循環(huán)(n)(n)，第二個(gè)循環(huán)，第二個(gè)循環(huán)(n+range)(n+range) 總復(fù)雜性總復(fù)雜性(n+range)(n+range)78計(jì)算機(jī)與控制工程學(xué)院優(yōu)化：作為優(yōu)化：作為ChainChain類的成員函數(shù)類的成員函數(shù) 直接操縱直接操縱ChainChain的數(shù)據(jù)成員的數(shù)據(jù)成員【程序程序3-443-44】 節(jié)點(diǎn)重復(fù)被多個(gè)鏈表使用，避免對(duì)節(jié)點(diǎn)重復(fù)被多個(gè)鏈表使用，避免對(duì)newnew和和deletedelete的頻繁調(diào)用的頻繁調(diào)用templatevoid Chain:BinSort(int