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

1、下一頁上一頁停止放映西安交通大學(xué)計(jì)教中心西安交通大學(xué)計(jì)教中心下一頁上一頁停止放映 第第2 2/42/42頁頁 思考問題數(shù)據(jù)結(jié)構(gòu)要研究什么問題？什么是線性數(shù)據(jù)結(jié)構(gòu)和線性表？如何描述線性表？線性表在計(jì)算機(jī)中如何存放？有幾種存儲形式？它們的特點(diǎn)是什么？如何處理線性數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)？下一頁上一頁停止放映 第第3 3/42/42頁頁 數(shù)據(jù)結(jié)構(gòu)問題的由來計(jì)算機(jī)求解問題的過程步驟： 調(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í)際問題問題

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

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

4、述：放。一般用下列二元組來描述： 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ī)中的存放的物理位置無關(guān)下一頁上一頁停止放映 第第8 8/42/42頁頁 舉例 課題組由課題組由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 下一頁上一頁停止放映 第第9 9/42/42頁頁 數(shù)據(jù)的存儲結(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ù)庫中的數(shù)據(jù)存放在計(jì)算機(jī)中的物理位置下一頁上一頁停止放映 第第1010/42/42頁頁 邏輯結(jié)構(gòu)和存儲結(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ù)的存儲結(jié)構(gòu)存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)，是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)，是依賴于計(jì)算機(jī)的；離開了機(jī)器，則無法進(jìn)行任是依賴于計(jì)算機(jī)的；離開了機(jī)器，則無法進(jìn)行任何操作。何操作。v任何一個(gè)任何一個(gè)算法的設(shè)計(jì)算法的設(shè)計(jì)取決于選定的邏輯結(jié)構(gòu)；而取決于選定的邏輯結(jié)構(gòu)；而算法的最終實(shí)現(xiàn)算法的最終實(shí)現(xiàn)依賴于采用的存儲結(jié)構(gòu)。依賴于采用的存儲結(jié)構(gòu)。下一頁上一頁停止放映 第第1111/42/42頁頁 數(shù)據(jù)存儲結(jié)構(gòu)分類v順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)v鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈

7、式存儲結(jié)構(gòu)v索引存儲結(jié)構(gòu)索引存儲結(jié)構(gòu)v散列存儲結(jié)構(gòu)散列存儲結(jié)構(gòu) 下一頁上一頁停止放映 第第1212/42/42頁頁 順序存儲結(jié)構(gòu) 把數(shù)據(jù)元素按某種順序存放在一塊連續(xù)的存儲單元中的存儲形式。數(shù)據(jù)結(jié)點(diǎn)結(jié)構(gòu): d1 d2 dn數(shù)據(jù)域數(shù)據(jù)域特點(diǎn)特點(diǎn): 連續(xù)存放連續(xù)存放;邏輯上相鄰邏輯上相鄰,物理上也相鄰。物理上也相鄰。 結(jié)構(gòu)簡單，易實(shí)現(xiàn)。結(jié)構(gòu)簡單，易實(shí)現(xiàn)。 插入、刪除操作不便（需大量移動(dòng)元素）。插入、刪除操作不便（需大量移動(dòng)元素）。下一頁上一頁停止放映 第第1313/42/42頁頁 鏈?zhǔn)酱鎯Y(jié)構(gòu) 以鏈表形式將數(shù)據(jù)元素存放于任意存儲單元中，可連續(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ù)存放,借助指針來表示元素間的關(guān)系借助指針來表示元素間的關(guān)系;插入、刪除操作簡單，只要修改指針即可；插入、刪除操作簡單，只要修改指針即可；結(jié)構(gòu)較復(fù)雜，需要額外存儲空間。結(jié)構(gòu)較復(fù)雜，需要額外存儲空間。下一頁上一頁停止放映 第第1414/42/42頁頁 索引存儲結(jié)構(gòu) 數(shù)據(jù)按索引形式存放。存儲時(shí)分為：數(shù)據(jù)項(xiàng)和索數(shù)據(jù)按索引形式存放。存儲時(shí)分為：數(shù)據(jù)項(xiàng)和索引號；通過索引表記錄邏輯號（記錄號）和物理引號；通過索引表記錄邏輯號（記錄號）和物理號（存儲序號）之間的對應(yīng)關(guān)系。號（存儲序號）之間的對應(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ù)域 索引順序號索引順序號特點(diǎn)：特點(diǎn)：非連續(xù)存放；非連續(xù)存放；檢索速度快；檢索速度快；增、刪操作簡單。增、刪操作簡單。 序 號： 1 2 3 4 5 6 7 數(shù)據(jù)項(xiàng)：索引號：下一頁上一頁停止放映 第第1515/42/42頁頁 散列存儲結(jié)構(gòu) 在數(shù)據(jù)元素與存儲位置之間建立一種在數(shù)據(jù)元素與存儲位置之間建立一種存儲關(guān)系存儲關(guān)系f f，根據(jù)這種關(guān)系，根據(jù)這種關(guān)系f f，已知元，已知元素素e e，就可以得到它的存儲地址，即，就可以得到它的存儲地址，即d=fd=f（e e）。）。 哈希查找中的哈希表就是這樣一種存哈希查找中的哈希表就是這

10、樣一種存儲結(jié)構(gòu)。儲結(jié)構(gòu)。 特點(diǎn)：特點(diǎn)：數(shù)據(jù)元素間無內(nèi)在聯(lián)系；數(shù)據(jù)元素間無內(nèi)在聯(lián)系；存儲形式不定。存儲形式不定。下一頁上一頁停止放映 第第1616/42/42頁頁 數(shù)據(jù)運(yùn)算 數(shù)據(jù)運(yùn)算是指對存放在物理結(jié)構(gòu)上的數(shù)據(jù)數(shù)據(jù)運(yùn)算是指對存放在物理結(jié)構(gòu)上的數(shù)據(jù), ,按定義的邏輯結(jié)構(gòu)進(jìn)行的各種操作。按定義的邏輯結(jié)構(gòu)進(jìn)行的各種操作。 常見操作有：常見操作有：輸入、檢索、插入、刪除、修改、排序輸入、檢索、插入、刪除、修改、排序等。等。下一頁上一頁停止放映 第第1717/42/42頁頁 數(shù)據(jù)結(jié)構(gòu)分類 線性表線性表堆棧堆棧隊(duì)列隊(duì)列串串?dāng)?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下一頁上一頁停止放映 第第1818/42/42頁頁 數(shù)據(jù)結(jié)構(gòu)基本類型 線性結(jié)構(gòu)線性結(jié)構(gòu) 通迅錄、成績單、花名冊通迅錄、成績單、花名冊 樹形結(jié)構(gòu)樹形結(jié)構(gòu) 電子字典、家譜、目錄電子字典、家譜、目錄 圖狀結(jié)構(gòu)圖狀結(jié)構(gòu) 交通線路、通信網(wǎng)絡(luò)交通線路、通信網(wǎng)絡(luò)下一頁上一頁停止放映 第第1919/42/42頁頁 算法（algorithm） 輸入輸入：具有具有0 0個(gè)或多個(gè)輸入的外界量（算法開始前的個(gè)或多個(gè)輸入的外界量（算法開始前的初始量）初始量）輸出輸出：至少有一個(gè)輸出，是算法執(zhí)行完后的結(jié)果。至少有一個(gè)輸出，是算法執(zhí)行完后的結(jié)果。有窮性有窮性：每條指令的執(zhí)行次數(shù)必須是有限的。每條指令的執(zhí)行次數(shù)必須是有限的

12、。確定性確定性：每條指令的含義都必須明確，無二義性。每條指令的含義都必須明確，無二義性?？尚行钥尚行裕好織l指令的執(zhí)行時(shí)間都是有限的。每條指令的執(zhí)行時(shí)間都是有限的。下一頁上一頁停止放映 第第2020/42/42頁頁 1 1時(shí)間復(fù)雜度時(shí)間復(fù)雜度 一個(gè)算法花費(fèi)的時(shí)間與算法中語句的執(zhí)行次一個(gè)算法花費(fèi)的時(shí)間與算法中語句的執(zhí)行次數(shù)成正比，哪個(gè)算法中語句執(zhí)行次數(shù)多，它花費(fèi)數(shù)成正比，哪個(gè)算法中語句執(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稱為問題的規(guī)模，稱為問題的規(guī)模，當(dāng)當(dāng)n n不斷變化時(shí)，語句的執(zhí)行次數(shù)也會變化。一不斷變化時(shí)，語句的執(zhí)行次數(shù)也會變化。一個(gè)算法中

13、的時(shí)間復(fù)雜度一般用語句執(zhí)行次數(shù)的數(shù)個(gè)算法中的時(shí)間復(fù)雜度一般用語句執(zhí)行次數(shù)的數(shù)量級來衡量。量級來衡量。例如：例如： for(i=1; i=n; i+) for(j =1; j=i; j+) dij=dataij+1;算法分析o(n2)下一頁上一頁停止放映 第第2121/42/42頁頁 算法的評價(jià)算法評價(jià)的標(biāo)準(zhǔn)：算法評價(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ù)量級）（數(shù)量級）”來表示，稱為來表示，稱為“階階”。常見。常見的時(shí)間復(fù)雜度有：的時(shí)間復(fù)雜度有： o o（1 1） o o（lognlogn） o o（ n n ）

14、o o（ n n2 2 ） 常數(shù)階常數(shù)階 對數(shù)階對數(shù)階 線性階線性階 平方階平方階空間復(fù)雜度空間復(fù)雜度 指算法在計(jì)算機(jī)上運(yùn)行所占用的存儲空間。指算法在計(jì)算機(jī)上運(yùn)行所占用的存儲空間。度量同時(shí)間復(fù)雜度。度量同時(shí)間復(fù)雜度。 下一頁上一頁停止放映 第第2222/42/42頁頁 時(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 ）下一頁上一頁停止放映 第第2323/42/42頁頁 2 2、空間復(fù)雜度、空間復(fù)雜度與時(shí)間復(fù)雜度類似，空間復(fù)雜度是指算法與時(shí)間復(fù)雜度類似，空間復(fù)雜度是指算法在計(jì)算機(jī)內(nèi)執(zhí)行時(shí)所占用的內(nèi)存開銷規(guī)模。但在計(jì)算機(jī)內(nèi)執(zhí)行時(shí)所占用的內(nèi)存開銷規(guī)模。但我們一般所討論的是除正常占用內(nèi)存開銷外的我們一般所討論的是除正常占用內(nèi)存開銷外的輔助存儲單元規(guī)模。討論方法與時(shí)間復(fù)雜度類輔助存儲單元規(guī)模。討論方法與時(shí)間復(fù)雜度類似，不再贅述。似，不再贅述。下一頁上一頁停止放映 第第2424/42/42頁頁 2.2 線性數(shù)據(jù)結(jié)構(gòu)下一頁上一頁停止放映 第第

16、2525/42/42頁頁 線性表的邏輯結(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è)有序偶對的集合。是一個(gè)有序偶對的集合。下一頁上一頁停止放映 第第2626/42/42頁頁 順序表 采用順序存儲結(jié)構(gòu)的線性表稱為順序表，它的數(shù)采用順序存儲結(jié)構(gòu)的線性表稱為順序表，它的數(shù)據(jù)元素按照邏輯順序依次存放在一組連續(xù)的存儲單據(jù)元素按照邏輯順序依次存放在一組連續(xù)的存儲單元中。邏輯上相鄰的

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

19、+1.loc(a1)+(i-1).下一頁上一頁停止放映 第第2828/42/42頁頁 順序表類型描述 struct seqlist elemtype *data; / 順序表存儲數(shù)組的地址順序表存儲數(shù)組的地址 int maxsize; / 順序表最大允許長度順序表最大允許長度 int length; / 順序表當(dāng)前長度順序表當(dā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)申請，申請，maxsize為其長度。數(shù)組的下標(biāo)從

20、為其長度。數(shù)組的下標(biāo)從0開始。開始。（3）length表示線性表當(dāng)前長度，初始長度為表示線性表當(dāng)前長度，初始長度為0（空（空表），最大不超過表），最大不超過maxsize。下一頁上一頁停止放映 第第2929/42/42頁頁 線性表的基本操作setnullsetnull（l l） 置空表置空表lengthlength（l l） 求表長度；求表中元素個(gè)數(shù)求表長度；求表中元素個(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） 判別表是否為空判別表是否為空下一頁上一頁停止放映 第第3030/42/42頁頁 順序表的主要算法 （1 1）順序表的初始化）順序表的初始化 順序表的初始化主要是為順序表的初始化主要是為elemtype類型的數(shù)組申類型的數(shù)組申請空間，下面的初始化函數(shù)為順序表申請了長度請空間，下面的初始化函數(shù)為順序表申請了長度為為size的空間。的空間。voi

22、d init( seqlist *l, int size ) if( size 0 ) l-maxsize = size; l-length = 0; l-data = new elemtypesize; /申請空間申請空間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 位置表長度加“1” l-length+; / 加“1”后，結(jié)果為“9”最后，得到的結(jié)果數(shù)列

23、是4,5,8,10,21,25,30,43,59 下一頁上一頁停止放映 第第3434/42/42頁頁 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+; / 表長度加一表長度加一 順序表插入算法順序表插入算法下一頁上一頁停止放映 第第3535/42/42頁

24、頁 （3）在表中刪除第i個(gè)元素 算法實(shí)現(xiàn)的主要步驟是：算法實(shí)現(xiàn)的主要步驟是： 判斷刪除位置的合理性。判斷刪除位置的合理性。 從第從第i+1i+1個(gè)元素開始，依次向后直到個(gè)元素開始，依次向后直到最后一個(gè)元素為止，將每個(gè)元素向前移最后一個(gè)元素為止，將每個(gè)元素向前移動(dòng)一個(gè)位置。這時(shí)第動(dòng)一個(gè)位置。這時(shí)第i i個(gè)元素已經(jīng)被覆蓋個(gè)元素已經(jīng)被覆蓋刪除。刪除。 最后還要將線性表長度減一。最后還要將線性表長度減一。下一頁上一頁停止放映 第第3636/42/42頁頁 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 序號序號 內(nèi)容內(nèi)容 序號序號 內(nèi)容內(nèi)容 刪除前刪除前 刪除后刪除后 順序表中刪除元素前后狀態(tài)順序表中刪除元素前后狀態(tài) 下一頁上一頁停止放映 第第3737/42/42頁頁 刪除算法示意舉例刪除算法示意舉例設(shè)有數(shù)列4,5,8,10,21,25,30,43,59，長度為9，將第6位的元素“25”刪除。算法描述：從第7個(gè)元素開始(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)長度減“1” l-length-； / 操作后，length 等于8最后，得到的結(jié)果數(shù)列是4,5,8,10,21,30,43,59 下一頁上一頁停止放映 第第3838/42/42頁頁 void delete( seqlist *l, int i ) if(il-length ) cout表中沒有第表中沒有第i個(gè)元素個(gè)元素; else for ( int j=i; jlength-1; j+ ) l-dataj-1 = l-dataj; /數(shù)據(jù)元素左移數(shù)據(jù)元素左移 l-length-; 順序表刪除算法順序表刪除算法下一頁上一頁停止放映 第第3939/42

27、/42頁頁 （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 下一頁上一頁停止放映 第第4040/42/42頁頁 順序表應(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 +