線性表chap(編輯修改稿)
2024-10-22 19:42 本頁面
【文章內(nèi)容簡介】 Create_Link(DataType data[], int num) 存儲結(jié)構(gòu)及基本運(yùn)算實(shí)現(xiàn) a b p 單鏈表 5. 結(jié)點(diǎn) 插入 和 刪除 圖示 單鏈表插入結(jié)點(diǎn)時(shí)的情況 slink = plink。 (1) plink = s。 (2) 注 : (1),(2)順序不能反 a b x s p (1) (2) a b p c 單鏈表刪除結(jié)點(diǎn)時(shí)的情況 plink = plinklink。 結(jié)點(diǎn) 插入 和 刪除運(yùn)算中的幾個(gè)問題 ： 1） 帶頭結(jié)點(diǎn)與不帶頭結(jié)點(diǎn)問題 2） 結(jié)點(diǎn)的生成與刪除 （ 動態(tài)生成 malloc，刪除 free） 3） 時(shí)間復(fù)雜度問題 由于 “ 條件插入、刪除運(yùn)算 ” 首先需要定位，而定位必須從頭結(jié)點(diǎn)開始順鏈一個(gè)一個(gè)結(jié)點(diǎn)進(jìn)行比較，因此其 “ 基本的操作 ” 為比較運(yùn)算。比較運(yùn)算的執(zhí)行次數(shù)與結(jié)點(diǎn)的位置有關(guān)，最好情況時(shí)為 1次（第一個(gè)結(jié)點(diǎn)），最壞為 n次（所有結(jié)點(diǎn)皆比較一次），因此條件插入、刪除運(yùn)算的 時(shí)間復(fù)雜度仍然為O(n). 對于在 p所指結(jié)點(diǎn)后插入新的結(jié)點(diǎn)，無定位問題，因此其時(shí)間復(fù)雜度為 O(1)。 (1) 單鏈表的存儲密度比順序表低；但在許多情況下鏈?zhǔn)降姆峙浔软樞蚍峙溆行? ；順序表為靜態(tài)結(jié)構(gòu)，而鏈表為動態(tài)結(jié)構(gòu)。 (2) 在單鏈表里進(jìn)行插入、刪除運(yùn)算比在順序表里容易得多；順序表通過數(shù)據(jù)元素移動完成，而鏈表通過修改指針完成。 (3) 對于順序表，可通過簡單的定位公式隨機(jī)訪問任一個(gè)元素，而在單鏈表中，需要順著鏈逐個(gè)進(jìn)行查找。因此，順序表為隨機(jī)存取結(jié)構(gòu)，而鏈表不是。 6. 單鏈表與順序表的比較 （ 1） 有利于基本運(yùn)算的實(shí)現(xiàn) 頻繁訪問：順序表（隨機(jī)存?。? 頻繁插入、刪除：鏈表 （ 2） 有利于數(shù)據(jù)的特性 順序表：難于事先估計(jì)數(shù)據(jù)元素個(gè)數(shù)，過大浪費(fèi)空間，過小易產(chǎn)生溢出； 鏈表：動態(tài)申請，但存儲密度比順序表低； （ 3） 有利于軟件環(huán)境（程序設(shè)計(jì)語言） 程序設(shè)計(jì)語言是否支持動態(tài)分配？ Fortran、 Basic等不支持動態(tài)分配，此時(shí)只能選擇順序表。 7. 單鏈表與順序表的選擇 游標(biāo) 代替鏈表中的指針，插入、刪除時(shí)僅需要修改游標(biāo)項(xiàng)完成。此時(shí)的靜態(tài)順序表具有鏈表的優(yōu)點(diǎn)。另外，將整個(gè)存儲空間分成兩部分：數(shù)據(jù)元素組成的 工作空間 和備用元素構(gòu)成的 備用空間 ，這兩部分分別設(shè)計(jì)一個(gè)鏈表（ 靜態(tài)鏈表 ）進(jìn)行管理。當(dāng)需要插入一個(gè)結(jié)點(diǎn)時(shí)，從備用鏈中取出第一個(gè)結(jié)點(diǎn)作為待插入的結(jié)點(diǎn)（類似于 Malloc）；當(dāng)從工作鏈中刪除一個(gè)結(jié)點(diǎn)時(shí)，將被刪除的結(jié)點(diǎn)連接到備用鏈上（類似于 Free）。 靜態(tài)鏈表 define MaxSize 1000 /* 供分配空間的大小 */ typedef struct { DataType data。 int cursor。 （ 游標(biāo)代替鏈表中的指針 ） }Component, SLinkList[MaxSize]。 假定 S為 SlinkList型變量， s[0].cursor指示第一個(gè)結(jié)點(diǎn)在數(shù)組中的位置，若設(shè) i= s[0].cursor, 則 s[i].data保存第一個(gè)數(shù)據(jù)元素， s[i].cursor指示第二個(gè)結(jié)點(diǎn)在數(shù)組中的位置。如第 i個(gè)分量表示鏈表的第 k個(gè)結(jié)點(diǎn)，則 s[i].cursor指示第 k+1個(gè)結(jié)點(diǎn)在數(shù)組中的位置。 i = s[i].cursor類似鏈表中的 p=plink 最后結(jié)點(diǎn)的 cursor=0(類似鏈表中的 NULL)。 3 C 5 A 6 E 7 D 4 B 1 F 0 S[0] S[1] S[2] S[3] S[4] S[5] S[6] S[7] 線性表： (A, B, C, D, E, F) 0 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 0 Zhao Qian Sun Li Zhou Wu Zheng Wang 0 1 2 3 4 5 6 7 8 9 10 1 2 3 4 9 6 8 8 0 5 Zhao Qian Sun Li Zhou Wu Zheng Wang Shi 靜態(tài)鏈表示例 (插入 li，刪除 zheng） 修改前 修改后 /* 初始化靜態(tài)鏈表，將所有結(jié)點(diǎn)連接成一個(gè)備用鏈 */ void InitList(SLinkList list)。 /* 用‘ 0’表示空 */ /* 從備用鏈中申請空間，返回申請到的空間的下標(biāo) */ int Malloc(SLinkList list)。 /* 釋放 ‘ k’指向的空間，將其連接到備用鏈中 */ void Free(SLinkList list, int k)。 void InitList(SLinkList list) { int i。 for(i = 0。 i MaxSize 1。 i++) list[i].cursor = i + 1。 list[MaxSize1].cursor = 0。
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1