[理學(xué)]第二章線性表(編輯修改稿)
2024-11-15 01:00 本頁面
【文章內(nèi)容簡介】 示 單鏈表插入結(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)的前驅(qū) 結(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. 單鏈表與順序表的選擇 整個(gè)結(jié)構(gòu)采用順序表。 順序表中，每個(gè)元素包含兩項(xiàng)：數(shù)據(jù)項(xiàng)和存儲后繼位置的游標(biāo)項(xiàng)。 通過游標(biāo)表達(dá)數(shù)據(jù)元素之間的邏輯關(guān)系。邏輯上相鄰元素，存儲位置不一定相鄰。 靜態(tài)鏈表 define MaxSize 1000 /* 供分配空間的大小 */ typedef struct { DataType data。 int cursor。 （ 游標(biāo)代替鏈表中的指針 ） }Component, SLinkList[MaxSize]。 D1 C1 D3 C3 D4 C4 D2 C2 數(shù)據(jù) 后繼在數(shù)組中的位置（游標(biāo)） 游標(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）。 D1 A2 E3 E4 D3 A4 E2 E6 D4 A5 E5 D6 1 D5 A6 E7 E9 D2 A3 E8 1 PD PA 假定 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 A B C D E F G H 0 1 2 3 4 5 6 7 8 9 10 1 2 3 4 9 6 7 8 0 5 A B C D E F G H D’ 靜態(tài)鏈表示例 (插入 D’，刪除 zheng） 修改前 插入 D’ 0 1 2 3 4 5 6 7 8 9 10 1 2 3 4 9 7 7 8 0 5 A B C D E F G H D’ 刪除 F // 初始化靜態(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。 } d 6 3 c 0 5 a 7 0 e 0 b 2 9 1 0
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1