第二章線(xiàn)性表-文庫(kù)吧
2025-07-17 13:03 本頁(yè)面
【正文】 int i,elementtype x) { int j。 if (i0||i=listn){ /*位置不合理 */ printf(“not exit!\n”)。 return(0)。 } if (listn==Maxnum) { /*空間已滿(mǎn) */ printf(“out of space!\n”)。return (0)。 } for (j=listn1。j=i。j) /*向后移動(dòng)元素 */ listelement[j+1]= listelement[j]。 listelement[i]=x。 /*插入元素 */ listn++。 /*長(zhǎng)度加 1*/ return(1)。 } 演示 5. 刪除 delete(L, i) 功能： 刪除順序表 L中下標(biāo)為 i（ 0≤in 1）的數(shù)據(jù)元 素 ,刪除前線(xiàn)性表為 ( a0， a1， … ， an1 ) 刪除后 ,線(xiàn)性表長(zhǎng)度為 n1, 線(xiàn)性表為 ( a0， a1， … ， ai1， ai+1， … ， an1 ) 刪除前 n=8 刪除后 n=7 刪除操作示意圖： Delete(p,3) 11 12 34 3 27 16 147 44 12 34 3 11 27 16 147 44 a0 a1 a2 a3 a4 a5 a6 a7 a0 a1 a2 a3 a4 a5 a6 a7 刪除操作算法 int Delete(ptsqlist list,int i) { int j。 if (i0||i=listn){ /*位置不合理 */ printf(“not exist!\n”)。 return (0)。 } for (j=i。j=listn1。j++) /*向前移動(dòng)元素 */ listelement[j]= listelement[j+1]。 listn。 /*長(zhǎng)度減 1 */ return(1)。 } 演示 viod fanzhuanlist(ptsqlist list) { elementtype mid。 int a,z。 a=0。z=listn1。 for (。az。a++,z) /*逆轉(zhuǎn)順序表 */ { mid=listelement[a]。 listelement[a]=listelement[z]。 listelement[z]=mid。 } } a0 a1 … ai1 ai ai+1 … an1 mid 怎樣分析插入和刪除算法 的 T（ n）呢？ 在下標(biāo)為 i的位置 (第 i+1個(gè)位置 )前插入 元素下標(biāo) 移動(dòng)元素個(gè)數(shù) 0 n 1 n1 i ni n1 1 n 0 三、算法時(shí)間復(fù)雜度分析 在順序表中插入元素，時(shí)間主要耗費(fèi)在移動(dòng)元素上，而移動(dòng)的個(gè)數(shù)取決于插入的位置以及表的長(zhǎng)度。 1 2 i1 i i+1 n a0 a1 … ai1 ai ai+1 … an1 假設(shè)在線(xiàn)性表的任何位置插入元素的概率相同，即 pi= 1/(n+1) 則有： 假設(shè) pi是在第 i個(gè)元素之前插入元素的概率，在長(zhǎng)度為 n的順序表中插入一個(gè)元素，所需移動(dòng)元素個(gè)數(shù)數(shù)學(xué)期望值為： ninnEnii 21)(110???? ??????niii pinE0*)(假設(shè)在線(xiàn)性表的任何位置刪除元素的概率相同，即 pd= 1/n 則有： 刪除下標(biāo)為 i的元素（第 i+1個(gè)）需移動(dòng) ni1個(gè)元素，設(shè)在相應(yīng)位置刪除元素的概率是 pd，則刪除的平均移動(dòng)次數(shù)是： 21)1(1 10????? ???ninnEnid??????10*)1(nidd pinE在順序表中插入或刪除元素的 時(shí)間時(shí)間復(fù)雜度 為 O(n) 相關(guān)例題 例 1 利用順序表設(shè)計(jì)一算法，用以清除表 L中的多余的重復(fù)結(jié)點(diǎn)。如表 L（ 21， 3， 5， 3， 21， 3， 90， 5）運(yùn)算后變?yōu)?L（ 21， 3， 5， 90） 算法思想應(yīng)該是怎樣的呢？ 相關(guān)代碼： void Purge(ptsqlist list) { int i,j,k。 i=0。 while (ilistn) { j=i+1。 while (jlistn) { if (listelement[i]==listelement[j]) { for (k=j+1。klistn 。k++ ) listelement[k1]=listelement[k]。 listn=listn1。 }else j=j+1。 } i=i+1。 } } 作業(yè)：設(shè)計(jì)相關(guān)算法，完成線(xiàn)性表的其它操作：Locate(p,x)。 Union(p,q). 小結(jié) 順序表的特點(diǎn)： 1 通過(guò)元素的存儲(chǔ)順序反映線(xiàn)性表中 數(shù)據(jù)元素之間的邏輯關(guān)系； 2 可隨機(jī)存取順序表的元素； 3 順序表的插入、刪除操作要通過(guò)移動(dòng) 元素實(shí)現(xiàn)； 線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用一組 任意 的存儲(chǔ)單元存儲(chǔ)線(xiàn)性表的數(shù)據(jù)元素。為了表示線(xiàn)性表中元素的先后關(guān)系，每個(gè)結(jié)點(diǎn)除了需要存儲(chǔ)自身的信息外，還需存儲(chǔ)一個(gè)指示其直接后繼的信息（直接后繼的存儲(chǔ)位置）。 ai+1 a1 ai1 a2 ai an 線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 1010 1012 1014 1016 1018 1020 1022 1024 1026 用線(xiàn)性鏈表存儲(chǔ)線(xiàn)性表時(shí)，數(shù)據(jù)元素之間的關(guān)系是通過(guò)保存直接后繼元素的存儲(chǔ)位置來(lái)實(shí)現(xiàn)的 線(xiàn)性鏈表 一，線(xiàn)性鏈表的概念 a4 a3 a1 a2 NULL 1010 1024 1014 a1 a4 a2 結(jié)點(diǎn) 數(shù)據(jù)域 指針域 ? 線(xiàn)性鏈表有關(guān)術(shù)語(yǔ) ? 結(jié)點(diǎn)： 數(shù)據(jù)元素及直接后繼的存儲(chǔ)位置（地址）組成一個(gè)數(shù)據(jù)元素的存儲(chǔ)結(jié)構(gòu)，稱(chēng)為一個(gè)結(jié)點(diǎn)； ? 結(jié)點(diǎn)的數(shù)據(jù)域 ： 結(jié)點(diǎn)中用于保存數(shù)據(jù)元素的部分 。 ? 結(jié)點(diǎn)的指針域 ： 結(jié)點(diǎn)中用于保存數(shù)據(jù)元素直接后繼存儲(chǔ)地址的部分 。 存儲(chǔ)數(shù)據(jù)元素 存儲(chǔ)直接后繼 結(jié)點(diǎn)的地址 怎樣在計(jì)算機(jī)上 實(shí)現(xiàn)線(xiàn)性鏈表？ 結(jié)點(diǎn)變量圖示 LNode ：結(jié)構(gòu)類(lèi)型名； LNode類(lèi)型結(jié)構(gòu)變量有兩個(gè)域： data： 用于存放線(xiàn)性表的數(shù)據(jù)元素， next： 用于存放元素直接后繼結(jié)點(diǎn)的地址； 該類(lèi)型結(jié)構(gòu)變量用于表示線(xiàn)性鏈表中的一個(gè)結(jié)點(diǎn)； data next LNode類(lèi)型 結(jié)構(gòu)變量 p p是 LNode類(lèi)型的指針變量 線(xiàn)性鏈表的結(jié)點(diǎn)類(lèi)型定義及指向結(jié)點(diǎn)的指針類(lèi)型定義 typedef struct Node { Etype data。 struct Node *next。 }LNode, *LinkList。 數(shù)據(jù)域 指針域 順序 建立單鏈表 （尾插法） H p a q H p a q H p a q b q H b c p q q a ① ① ② ② Lnode* Screat_List (void)
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1