第2數(shù)據(jù)結(jié)構(gòu)及應(yīng)用概念及順序表

1、下一頁(yè)上一頁(yè)停止放映西安交通大學(xué)計(jì)教中心西安交通大學(xué)計(jì)教中心下一頁(yè)上一頁(yè)停止放映 第第2 2/42/42頁(yè)頁(yè) 思考問(wèn)題數(shù)據(jù)結(jié)構(gòu)要研究什么問(wèn)題？什么是線性數(shù)據(jù)結(jié)構(gòu)和線性表？如何描述線性表？線性表在計(jì)算機(jī)中如何存放？有幾種存儲(chǔ)形式？它們的特點(diǎn)是什么？如何處理線性數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)？下一頁(yè)上一頁(yè)停止放映 第第3 3/42/42頁(yè)頁(yè) 數(shù)據(jù)結(jié)構(gòu)問(wèn)題的由來(lái)計(jì)算機(jī)求解問(wèn)題的過(guò)程步驟： 調(diào)試程序調(diào)試程序編制編制程序程序求解求解結(jié)果結(jié)果運(yùn)行運(yùn)行程序程序結(jié)果輸出結(jié)果輸出用戶用戶需求需求數(shù)據(jù)類型、格式、數(shù)據(jù)類型、格式、邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)數(shù)據(jù)數(shù)據(jù)邏輯邏輯運(yùn)算運(yùn)算數(shù)據(jù)的物理數(shù)據(jù)的物理操作操作分析抽象分析抽象實(shí)際實(shí)際問(wèn)題問(wèn)題

2、模型求解模型求解問(wèn)題問(wèn)題模型模型命令命令編程編程求解求解算法算法下一頁(yè)上一頁(yè)停止放映 第第4 4/42/42頁(yè)頁(yè) 數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)的專業(yè)技術(shù)基礎(chǔ)課。它研究的主要問(wèn)題有： 分析數(shù)據(jù)（計(jì)算機(jī)加工的對(duì)象）的特征 選擇適當(dāng)邏輯存儲(chǔ)結(jié)構(gòu)和物理存儲(chǔ)結(jié)構(gòu) 在存儲(chǔ)結(jié)構(gòu)的基礎(chǔ)上實(shí)現(xiàn)對(duì)數(shù)據(jù)的操作下一頁(yè)上一頁(yè)停止放映 第第5 5/42/42頁(yè)頁(yè) 2.1 數(shù)據(jù)結(jié)構(gòu)基本概念1數(shù)據(jù)（數(shù)據(jù)（data）數(shù)據(jù)是指能夠輸入到計(jì)算機(jī)中，并被計(jì)算機(jī)識(shí)數(shù)據(jù)是指能夠輸入到計(jì)算機(jī)中，并被計(jì)算機(jī)識(shí)別和處理的符號(hào)的集合別和處理的符號(hào)的集合。 2數(shù)據(jù)元素（數(shù)據(jù)元素（data element）數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位。數(shù)據(jù)元素是數(shù)據(jù)

3、元素是組成數(shù)據(jù)的基本單位。數(shù)據(jù)元素是一個(gè)數(shù)據(jù)整體中相對(duì)獨(dú)立的單位。但它還可以分一個(gè)數(shù)據(jù)整體中相對(duì)獨(dú)立的單位。但它還可以分割成若干個(gè)具有不同屬性的項(xiàng)（字段），故不是割成若干個(gè)具有不同屬性的項(xiàng)（字段），故不是組成數(shù)據(jù)的最小單位組成數(shù)據(jù)的最小單位下一頁(yè)上一頁(yè)停止放映 第第6 6/42/42頁(yè)頁(yè) 數(shù)據(jù)結(jié)構(gòu)（data structure）下一頁(yè)上一頁(yè)停止放映 第第7 7/42/42頁(yè)頁(yè) 數(shù)據(jù)的邏輯結(jié)構(gòu) 它是描述數(shù)據(jù)間的順序（邏輯）關(guān)它是描述數(shù)據(jù)間的順序（邏輯）關(guān)系，只是抽象地反映數(shù)據(jù)元素的結(jié)系，只是抽象地反映數(shù)據(jù)元素的結(jié)構(gòu)，而不管它們?cè)谟?jì)算機(jī)中如何存構(gòu)，而不管它們?cè)谟?jì)算機(jī)中如何存放。一般用下列二元組來(lái)描

4、述：放。一般用下列二元組來(lái)描述： ds=ds=（d d，r r） 其中：其中： d d：是數(shù)據(jù)元素的有限集合；：是數(shù)據(jù)元素的有限集合； r r：是數(shù)據(jù)元素之間關(guān)系的集合。：是數(shù)據(jù)元素之間關(guān)系的集合。與數(shù)據(jù)在計(jì)算機(jī)中的存放的物理位置無(wú)關(guān)下一頁(yè)上一頁(yè)停止放映 第第8 8/42/42頁(yè)頁(yè) 舉例 課題組由課題組由1 1名教師、名教師、1313名研究生、名研究生、1616名本名本科生組成；成員關(guān)系是：教師指導(dǎo)研究生、科生組成；成員關(guān)系是：教師指導(dǎo)研究生、研究生指導(dǎo)研究生指導(dǎo)1212名本科生。名本科生。 定義定義dsds如下：如下： group=group=（d d，r r） 其中：其中： d=t，g1，

5、,gn,s11,snm 1 n 3 , 1 m 2r=r1,r2r1=|1 i n , 1 n 3r2=|1in ,1 j m , 1 n 3 , 1 m 2 下一頁(yè)上一頁(yè)停止放映 第第9 9/42/42頁(yè)頁(yè) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 又稱物理結(jié)構(gòu)又稱物理結(jié)構(gòu) 是指數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示是指數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示( (又稱映象又稱映象),),即數(shù)據(jù)在計(jì)算機(jī)中即數(shù)據(jù)在計(jì)算機(jī)中的存放。的存放。數(shù)據(jù)庫(kù)中的數(shù)據(jù)存放在計(jì)算機(jī)中的物理位置下一頁(yè)上一頁(yè)停止放映 第第1010/42/42頁(yè)頁(yè) 邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)的關(guān)系v數(shù)據(jù)的數(shù)據(jù)的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)是從邏輯關(guān)系（某種順序）上觀是從邏輯關(guān)系（某種順序）上觀察數(shù)據(jù)，它是獨(dú)

6、立于計(jì)算機(jī)的；可以在理論上、察數(shù)據(jù)，它是獨(dú)立于計(jì)算機(jī)的；可以在理論上、形式上進(jìn)行研究、推理、運(yùn)算等各種操作。形式上進(jìn)行研究、推理、運(yùn)算等各種操作。v數(shù)據(jù)的數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)，是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)，是依賴于計(jì)算機(jī)的；離開(kāi)了機(jī)器，則無(wú)法進(jìn)行任是依賴于計(jì)算機(jī)的；離開(kāi)了機(jī)器，則無(wú)法進(jìn)行任何操作。何操作。v任何一個(gè)任何一個(gè)算法的設(shè)計(jì)算法的設(shè)計(jì)取決于選定的邏輯結(jié)構(gòu)；而取決于選定的邏輯結(jié)構(gòu)；而算法的最終實(shí)現(xiàn)算法的最終實(shí)現(xiàn)依賴于采用的存儲(chǔ)結(jié)構(gòu)。依賴于采用的存儲(chǔ)結(jié)構(gòu)。下一頁(yè)上一頁(yè)停止放映 第第1111/42/42頁(yè)頁(yè) 數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)分類v順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)v鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈

7、式存儲(chǔ)結(jié)構(gòu)v索引存儲(chǔ)結(jié)構(gòu)索引存儲(chǔ)結(jié)構(gòu)v散列存儲(chǔ)結(jié)構(gòu)散列存儲(chǔ)結(jié)構(gòu) 下一頁(yè)上一頁(yè)停止放映 第第1212/42/42頁(yè)頁(yè) 順序存儲(chǔ)結(jié)構(gòu) 把數(shù)據(jù)元素按某種順序存放在一塊連續(xù)的存儲(chǔ)單元中的存儲(chǔ)形式。數(shù)據(jù)結(jié)點(diǎn)結(jié)構(gòu): d1 d2 dn數(shù)據(jù)域數(shù)據(jù)域特點(diǎn)特點(diǎn): 連續(xù)存放連續(xù)存放;邏輯上相鄰邏輯上相鄰,物理上也相鄰。物理上也相鄰。 結(jié)構(gòu)簡(jiǎn)單，易實(shí)現(xiàn)。結(jié)構(gòu)簡(jiǎn)單，易實(shí)現(xiàn)。 插入、刪除操作不便（需大量移動(dòng)元素）。插入、刪除操作不便（需大量移動(dòng)元素）。下一頁(yè)上一頁(yè)停止放映 第第1313/42/42頁(yè)頁(yè) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 以鏈表形式將數(shù)據(jù)元素存放于任意存儲(chǔ)單元中，可連續(xù)存放，也可以不連續(xù)存放，以指針實(shí)現(xiàn)鏈表間的聯(lián)系。數(shù)據(jù)結(jié)點(diǎn)結(jié)

8、構(gòu): d1. d2dn 數(shù)據(jù)域數(shù)據(jù)域 指針域指針域特點(diǎn)特點(diǎn):非連續(xù)存放非連續(xù)存放,借助指針來(lái)表示元素間的關(guān)系借助指針來(lái)表示元素間的關(guān)系;插入、刪除操作簡(jiǎn)單，只要修改指針即可；插入、刪除操作簡(jiǎn)單，只要修改指針即可；結(jié)構(gòu)較復(fù)雜，需要額外存儲(chǔ)空間。結(jié)構(gòu)較復(fù)雜，需要額外存儲(chǔ)空間。下一頁(yè)上一頁(yè)停止放映 第第1414/42/42頁(yè)頁(yè) 索引存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)按索引形式存放。存儲(chǔ)時(shí)分為：數(shù)據(jù)項(xiàng)和索數(shù)據(jù)按索引形式存放。存儲(chǔ)時(shí)分為：數(shù)據(jù)項(xiàng)和索引號(hào)；通過(guò)索引表記錄邏輯號(hào)（記錄號(hào)）和物理引號(hào)；通過(guò)索引表記錄邏輯號(hào)（記錄號(hào)）和物理號(hào)（存儲(chǔ)序號(hào)）之間的對(duì)應(yīng)關(guān)系。號(hào)（存儲(chǔ)序號(hào)）之間的對(duì)應(yīng)關(guān)系。 數(shù)據(jù)結(jié)點(diǎn)結(jié)構(gòu)數(shù)據(jù)結(jié)點(diǎn)結(jié)構(gòu): :1

9、2 21 35 2 45 5 10 4 3 2 7 1 6 5 數(shù)據(jù)域數(shù)據(jù)域 索引順序號(hào)索引順序號(hào)特點(diǎn)：特點(diǎn)：非連續(xù)存放；非連續(xù)存放；檢索速度快；檢索速度快；增、刪操作簡(jiǎn)單。增、刪操作簡(jiǎn)單。 序 號(hào)： 1 2 3 4 5 6 7 數(shù)據(jù)項(xiàng)：索引號(hào)：下一頁(yè)上一頁(yè)停止放映 第第1515/42/42頁(yè)頁(yè) 散列存儲(chǔ)結(jié)構(gòu) 在數(shù)據(jù)元素與存儲(chǔ)位置之間建立一種在數(shù)據(jù)元素與存儲(chǔ)位置之間建立一種存儲(chǔ)關(guān)系存儲(chǔ)關(guān)系f f，根據(jù)這種關(guān)系，根據(jù)這種關(guān)系f f，已知元，已知元素素e e，就可以得到它的存儲(chǔ)地址，即，就可以得到它的存儲(chǔ)地址，即d=fd=f（e e）。）。 哈希查找中的哈希表就是這樣一種存哈希查找中的哈希表就是這

10、樣一種存儲(chǔ)結(jié)構(gòu)。儲(chǔ)結(jié)構(gòu)。 特點(diǎn)：特點(diǎn)：數(shù)據(jù)元素間無(wú)內(nèi)在聯(lián)系；數(shù)據(jù)元素間無(wú)內(nèi)在聯(lián)系；存儲(chǔ)形式不定。存儲(chǔ)形式不定。下一頁(yè)上一頁(yè)停止放映 第第1616/42/42頁(yè)頁(yè) 數(shù)據(jù)運(yùn)算 數(shù)據(jù)運(yùn)算是指對(duì)存放在物理結(jié)構(gòu)上的數(shù)據(jù)數(shù)據(jù)運(yùn)算是指對(duì)存放在物理結(jié)構(gòu)上的數(shù)據(jù), ,按定義的邏輯結(jié)構(gòu)進(jìn)行的各種操作。按定義的邏輯結(jié)構(gòu)進(jìn)行的各種操作。 常見(jiàn)操作有：常見(jiàn)操作有：輸入、檢索、插入、刪除、修改、排序輸入、檢索、插入、刪除、修改、排序等。等。下一頁(yè)上一頁(yè)停止放映 第第1717/42/42頁(yè)頁(yè) 數(shù)據(jù)結(jié)構(gòu)分類 線性表線性表堆棧堆棧隊(duì)列隊(duì)列串串?dāng)?shù)組數(shù)組樹(shù)樹(shù)二叉樹(shù)二叉樹(shù)圖圖線性結(jié)構(gòu)線性結(jié)構(gòu)非線性結(jié)構(gòu)非線性結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)dsd

11、s下一頁(yè)上一頁(yè)停止放映 第第1818/42/42頁(yè)頁(yè) 數(shù)據(jù)結(jié)構(gòu)基本類型 線性結(jié)構(gòu)線性結(jié)構(gòu) 通迅錄、成績(jī)單、花名冊(cè)通迅錄、成績(jī)單、花名冊(cè) 樹(shù)形結(jié)構(gòu)樹(shù)形結(jié)構(gòu) 電子字典、家譜、目錄電子字典、家譜、目錄 圖狀結(jié)構(gòu)圖狀結(jié)構(gòu) 交通線路、通信網(wǎng)絡(luò)交通線路、通信網(wǎng)絡(luò)下一頁(yè)上一頁(yè)停止放映 第第1919/42/42頁(yè)頁(yè) 算法（algorithm） 輸入輸入：具有具有0 0個(gè)或多個(gè)輸入的外界量（算法開(kāi)始前的個(gè)或多個(gè)輸入的外界量（算法開(kāi)始前的初始量）初始量）輸出輸出：至少有一個(gè)輸出，是算法執(zhí)行完后的結(jié)果。至少有一個(gè)輸出，是算法執(zhí)行完后的結(jié)果。有窮性有窮性：每條指令的執(zhí)行次數(shù)必須是有限的。每條指令的執(zhí)行次數(shù)必須是有限的

12、。確定性確定性：每條指令的含義都必須明確，無(wú)二義性。每條指令的含義都必須明確，無(wú)二義性。可行性可行性：每條指令的執(zhí)行時(shí)間都是有限的。每條指令的執(zhí)行時(shí)間都是有限的。下一頁(yè)上一頁(yè)停止放映 第第2020/42/42頁(yè)頁(yè) 1 1時(shí)間復(fù)雜度時(shí)間復(fù)雜度 一個(gè)算法花費(fèi)的時(shí)間與算法中語(yǔ)句的執(zhí)行次一個(gè)算法花費(fèi)的時(shí)間與算法中語(yǔ)句的執(zhí)行次數(shù)成正比，哪個(gè)算法中語(yǔ)句執(zhí)行次數(shù)多，它花費(fèi)數(shù)成正比，哪個(gè)算法中語(yǔ)句執(zhí)行次數(shù)多，它花費(fèi)時(shí)間就多。時(shí)間就多。 數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素個(gè)數(shù)數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素個(gè)數(shù)n n稱為問(wèn)題的規(guī)模，稱為問(wèn)題的規(guī)模，當(dāng)當(dāng)n n不斷變化時(shí)，語(yǔ)句的執(zhí)行次數(shù)也會(huì)變化。一不斷變化時(shí)，語(yǔ)句的執(zhí)行次數(shù)也會(huì)變化。一個(gè)算法中

13、的時(shí)間復(fù)雜度一般用語(yǔ)句執(zhí)行次數(shù)的數(shù)個(gè)算法中的時(shí)間復(fù)雜度一般用語(yǔ)句執(zhí)行次數(shù)的數(shù)量級(jí)來(lái)衡量。量級(jí)來(lái)衡量。例如：例如： for(i=1; i=n; i+) for(j =1; j=i; j+) dij=dataij+1;算法分析o(n2)下一頁(yè)上一頁(yè)停止放映 第第2121/42/42頁(yè)頁(yè) 算法的評(píng)價(jià)算法評(píng)價(jià)的標(biāo)準(zhǔn)：算法評(píng)價(jià)的標(biāo)準(zhǔn)：時(shí)間復(fù)雜度時(shí)間復(fù)雜度 指在計(jì)算機(jī)上運(yùn)行該算法所花費(fèi)的時(shí)間。用指在計(jì)算機(jī)上運(yùn)行該算法所花費(fèi)的時(shí)間。用“o o（數(shù)量級(jí)）（數(shù)量級(jí)）”來(lái)表示，稱為來(lái)表示，稱為“階階”。常見(jiàn)。常見(jiàn)的時(shí)間復(fù)雜度有：的時(shí)間復(fù)雜度有： o o（1 1） o o（lognlogn） o o（ n n ）

14、o o（ n n2 2 ） 常數(shù)階常數(shù)階 對(duì)數(shù)階對(duì)數(shù)階 線性階線性階 平方階平方階空間復(fù)雜度空間復(fù)雜度 指算法在計(jì)算機(jī)上運(yùn)行所占用的存儲(chǔ)空間。指算法在計(jì)算機(jī)上運(yùn)行所占用的存儲(chǔ)空間。度量同時(shí)間復(fù)雜度。度量同時(shí)間復(fù)雜度。 下一頁(yè)上一頁(yè)停止放映 第第2222/42/42頁(yè)頁(yè) 時(shí)間復(fù)雜度舉例（a a） x x：=x+1 =x+1 ；（b b） for ifor i：=1 to n do =1 to n do x x：= x+1= x+1；（c c） for ifor i：= 1 to n do= 1 to n do for j for j：= 1 to n do= 1 to n do x x：= x+

15、1= x+1；o o（ 1 1 ）o o（ n n ）o o（ n n2 2 ）下一頁(yè)上一頁(yè)停止放映 第第2323/42/42頁(yè)頁(yè) 2 2、空間復(fù)雜度、空間復(fù)雜度與時(shí)間復(fù)雜度類似，空間復(fù)雜度是指算法與時(shí)間復(fù)雜度類似，空間復(fù)雜度是指算法在計(jì)算機(jī)內(nèi)執(zhí)行時(shí)所占用的內(nèi)存開(kāi)銷規(guī)模。但在計(jì)算機(jī)內(nèi)執(zhí)行時(shí)所占用的內(nèi)存開(kāi)銷規(guī)模。但我們一般所討論的是除正常占用內(nèi)存開(kāi)銷外的我們一般所討論的是除正常占用內(nèi)存開(kāi)銷外的輔助存儲(chǔ)單元規(guī)模。討論方法與時(shí)間復(fù)雜度類輔助存儲(chǔ)單元規(guī)模。討論方法與時(shí)間復(fù)雜度類似，不再贅述。似，不再贅述。下一頁(yè)上一頁(yè)停止放映 第第2424/42/42頁(yè)頁(yè) 2.2 線性數(shù)據(jù)結(jié)構(gòu)下一頁(yè)上一頁(yè)停止放映 第第

16、2525/42/42頁(yè)頁(yè) 線性表的邏輯結(jié)構(gòu)定義：定義： 線性表是線性表是n n（n n 0 0）個(gè)元素）個(gè)元素a a1 1,a,a2 2, ,a,an n 的的有限序列；表中每個(gè)數(shù)據(jù)元素，除了第有限序列；表中每個(gè)數(shù)據(jù)元素，除了第1 1個(gè)和最個(gè)和最后后1 1個(gè)外，有且僅有一個(gè)前趨元素和后繼元素。個(gè)外，有且僅有一個(gè)前趨元素和后繼元素。形式定義：形式定義： 含有含有n n個(gè)數(shù)據(jù)元素的線性表是一種數(shù)據(jù)結(jié)構(gòu)，表個(gè)數(shù)據(jù)元素的線性表是一種數(shù)據(jù)結(jié)構(gòu)，表示為：示為： linear_list=( d , r )linear_list=( d , r ) 其中其中: : d=a d=ai i | a | ai i

17、d d0 0,i=1,2,3,i=1,2,3,n,n ,n,n 00 r=n, n=a r=n, n=|a|ai-1i-1,a,ai i d d0 0 ,i=1, ,i=1,n,n d d是數(shù)據(jù)元素的有限集合，是數(shù)據(jù)元素的有限集合，r r是是d d上邏輯關(guān)系的有上邏輯關(guān)系的有限集合。關(guān)系限集合。關(guān)系n n是一個(gè)有序偶對(duì)的集合。是一個(gè)有序偶對(duì)的集合。下一頁(yè)上一頁(yè)停止放映 第第2626/42/42頁(yè)頁(yè) 順序表 采用順序存儲(chǔ)結(jié)構(gòu)的線性表稱為順序表，它的數(shù)采用順序存儲(chǔ)結(jié)構(gòu)的線性表稱為順序表，它的數(shù)據(jù)元素按照邏輯順序依次存放在一組連續(xù)的存儲(chǔ)單據(jù)元素按照邏輯順序依次存放在一組連續(xù)的存儲(chǔ)單元中。邏輯上相鄰的

18、數(shù)據(jù)元素，其存儲(chǔ)位置也彼此元中。邏輯上相鄰的數(shù)據(jù)元素，其存儲(chǔ)位置也彼此相鄰。相鄰。假定元素假定元素a1的物理地址是的物理地址是loc(aloc(a1 1) )，每個(gè)元素占，每個(gè)元素占d個(gè)存儲(chǔ)單元，則第個(gè)存儲(chǔ)單元，則第i個(gè)元素的存儲(chǔ)位置為個(gè)元素的存儲(chǔ)位置為：loc(ai) = loc(a1) + (i-1) * d length=n maxsize 0 1 i-2 i-1 i n-1 a2ai-1aiai+1a1an下一頁(yè)上一頁(yè)停止放映 第第2727/42/42頁(yè)頁(yè) 線性表元素存儲(chǔ)示意圖 a1a2.ai.元素序號(hào)元素序號(hào) 內(nèi)存狀態(tài)內(nèi)存狀態(tài) 存儲(chǔ)地址存儲(chǔ)地址12. i.loc(a1)loc(a1)

19、+1.loc(a1)+(i-1).下一頁(yè)上一頁(yè)停止放映 第第2828/42/42頁(yè)頁(yè) 順序表類型描述 struct seqlist elemtype *data; / 順序表存儲(chǔ)數(shù)組的地址順序表存儲(chǔ)數(shù)組的地址 int maxsize; / 順序表最大允許長(zhǎng)度順序表最大允許長(zhǎng)度 int length; / 順序表當(dāng)前長(zhǎng)度順序表當(dāng)前長(zhǎng)度 ； seqlist list;/ 定義一個(gè)線性表定義一個(gè)線性表list （1）elemtype代表數(shù)組的類型。代表數(shù)組的類型。（2）數(shù)組）數(shù)組data需要在初始化函數(shù)中利用需要在初始化函數(shù)中利用new操作動(dòng)態(tài)操作動(dòng)態(tài)申請(qǐng)，申請(qǐng)，maxsize為其長(zhǎng)度。數(shù)組的下標(biāo)從

20、為其長(zhǎng)度。數(shù)組的下標(biāo)從0開(kāi)始。開(kāi)始。（3）length表示線性表當(dāng)前長(zhǎng)度，初始長(zhǎng)度為表示線性表當(dāng)前長(zhǎng)度，初始長(zhǎng)度為0（空（空表），最大不超過(guò)表），最大不超過(guò)maxsize。下一頁(yè)上一頁(yè)停止放映 第第2929/42/42頁(yè)頁(yè) 線性表的基本操作setnullsetnull（l l） 置空表置空表lengthlength（l l） 求表長(zhǎng)度；求表中元素個(gè)數(shù)求表長(zhǎng)度；求表中元素個(gè)數(shù)getget（l l，i i） 取表中第取表中第i i個(gè)元素（個(gè)元素（1 1 i i n n）priorprior（l l，i i） 取取i i的前趨元素的前趨元素nextnext（l l，i i） 取取i i的后繼元素的后

21、繼元素locatelocate（l l，x x） 返回指定元素在表中的位置返回指定元素在表中的位置insertinsert（l l，i i，x x） 插入元素插入元素deletedelete（l l，x x） 刪除元素刪除元素emptyempty（l l） 判別表是否為空判別表是否為空下一頁(yè)上一頁(yè)停止放映 第第3030/42/42頁(yè)頁(yè) 順序表的主要算法 （1 1）順序表的初始化）順序表的初始化 順序表的初始化主要是為順序表的初始化主要是為elemtype類型的數(shù)組申類型的數(shù)組申請(qǐng)空間，下面的初始化函數(shù)為順序表申請(qǐng)了長(zhǎng)度請(qǐng)空間，下面的初始化函數(shù)為順序表申請(qǐng)了長(zhǎng)度為為size的空間。的空間。voi

22、d init( seqlist *l, int size ) if( size 0 ) l-maxsize = size; l-length = 0; l-data = new elemtypesize; /申請(qǐng)空間申請(qǐng)空間else coutlength-1; j=i-1; j- ) / length 是元素個(gè)數(shù)(8) l-dataj+1=l-dataj;l-dataj+1=l-dataj; / j是插入位置(5) 將空出的第6個(gè)位置，存放“25”。 l-datai-1 = x; / 將x存放在第i-1 位置表長(zhǎng)度加“1” l-length+; / 加“1”后，結(jié)果為“9”最后，得到的結(jié)果數(shù)列

23、是4,5,8,10,21,25,30,43,59 下一頁(yè)上一頁(yè)停止放映 第第3434/42/42頁(yè)頁(yè) void insert( seqlist *l, int i, elemtype x ) if( il-length+1 | l-length=l-maxsize ) coutlength-1; j=i-1; j- ) l-dataj+1 = l-dataj; /元素依次右移元素依次右移 l-datai-1 = x; / 向第向第 i 個(gè)位置存入新元素個(gè)位置存入新元素 xl-length+; / 表長(zhǎng)度加一表長(zhǎng)度加一 順序表插入算法順序表插入算法下一頁(yè)上一頁(yè)停止放映 第第3535/42/42頁(yè)

24、頁(yè) （3）在表中刪除第i個(gè)元素 算法實(shí)現(xiàn)的主要步驟是：算法實(shí)現(xiàn)的主要步驟是： 判斷刪除位置的合理性。判斷刪除位置的合理性。 從第從第i+1i+1個(gè)元素開(kāi)始，依次向后直到個(gè)元素開(kāi)始，依次向后直到最后一個(gè)元素為止，將每個(gè)元素向前移最后一個(gè)元素為止，將每個(gè)元素向前移動(dòng)一個(gè)位置。這時(shí)第動(dòng)一個(gè)位置。這時(shí)第i i個(gè)元素已經(jīng)被覆蓋個(gè)元素已經(jīng)被覆蓋刪除。刪除。 最后還要將線性表長(zhǎng)度減一。最后還要將線性表長(zhǎng)度減一。下一頁(yè)上一頁(yè)停止放映 第第3636/42/42頁(yè)頁(yè) 0 1 2 i-2 i-1 i n-1 maxsize a1 a2 a3 ai-1 ai+1 an 0 1 2 i-2 i-1 i n-1 maxs

25、ize a1 a2 a3 ai-1 ai ai+1 an 序號(hào)序號(hào) 內(nèi)容內(nèi)容 序號(hào)序號(hào) 內(nèi)容內(nèi)容 刪除前刪除前 刪除后刪除后 順序表中刪除元素前后狀態(tài)順序表中刪除元素前后狀態(tài) 下一頁(yè)上一頁(yè)停止放映 第第3737/42/42頁(yè)頁(yè) 刪除算法示意舉例刪除算法示意舉例設(shè)有數(shù)列4,5,8,10,21,25,30,43,59，長(zhǎng)度為9，將第6位的元素“25”刪除。算法描述：從第7個(gè)元素開(kāi)始(i+1)；將第7個(gè)元素“30”存入第6位，將“25”覆蓋，即元素左移，移動(dòng)元素個(gè)數(shù)是3（9-6）； for ( int j=i; jlength-1; j+ ) / length是元素個(gè)數(shù)(9) l-dataj-1 =

26、 l-dataj; / i是刪除位置(6)長(zhǎng)度減“1” l-length-； / 操作后，length 等于8最后，得到的結(jié)果數(shù)列是4,5,8,10,21,30,43,59 下一頁(yè)上一頁(yè)停止放映 第第3838/42/42頁(yè)頁(yè) void delete( seqlist *l, int i ) if(il-length ) cout表中沒(méi)有第表中沒(méi)有第i個(gè)元素個(gè)元素; else for ( int j=i; jlength-1; j+ ) l-dataj-1 = l-dataj; /數(shù)據(jù)元素左移數(shù)據(jù)元素左移 l-length-; 順序表刪除算法順序表刪除算法下一頁(yè)上一頁(yè)停止放映 第第3939/42

27、/42頁(yè)頁(yè) （4）在表中查找某個(gè)元素 下面是根據(jù)數(shù)據(jù)元素本身的值進(jìn)行查詢的算下面是根據(jù)數(shù)據(jù)元素本身的值進(jìn)行查詢的算法，法，x為需要查找的元素，算法返回元素的實(shí)為需要查找的元素，算法返回元素的實(shí)際位置。查找算法際位置。查找算法: :int find( seqlist *l, elemtype x ) for( int i = 0; ilength; i+ ) /查找成功查找成功, 返回元素位置返回元素位置 if( l-datai=x ) return i+1; return 0; /查找失敗查找失敗, 返回返回 0 下一頁(yè)上一頁(yè)停止放映 第第4040/42/42頁(yè)頁(yè) 順序表應(yīng)用舉例順序表應(yīng)用舉例

28、 【例【例2-1】利用順序表表示多項(xiàng)式，實(shí)現(xiàn)兩個(gè)】利用順序表表示多項(xiàng)式，實(shí)現(xiàn)兩個(gè)一元多項(xiàng)式一元多項(xiàng)式l1(x)和和l2(x)相加，將結(jié)果存于相加，將結(jié)果存于多項(xiàng)式多項(xiàng)式l3(x)中。若中。若: l1(x) = 3.5 + 4x2 + 2.5x4 l2(x) = 1.5x + 2.6x2 + 1.6x3 則，則，l3(x)的結(jié)果是的結(jié)果是: l3(x)= 3.5 + 1.5x + 6.6x2 + 1.6x3 + 2.5x4 一元多項(xiàng)式一元多項(xiàng)式p(x)可表示為可表示為(a0, 0), (a1, 1), , (an, n)。 例如線性表例如線性表(6, 1), (-5, 4), (8, 10)表示多項(xiàng)式表示多項(xiàng)式: p(x) = 6x - 5x4 +