[理學]第二章線性表(編輯修改稿)
2024-11-15 01:00 本頁面
【文章內容簡介】 示 單鏈表插入結點時的情況 slink = plink。 (1) plink = s。 (2) 注 : (1),(2)順序不能反 a b x s p (1) (2) a b p c 單鏈表刪除結點時的情況 plink = plinklink。 對于單鏈表，必須找到插入或刪除結點的前驅 結點 插入 和 刪除運算中的幾個問題 ： 1） 帶頭結點與不帶頭結點問題 2） 結點的生成與刪除 （ 動態(tài)生成 malloc，刪除 free） 3） 時間復雜度問題 由于 “ 條件插入、刪除運算 ” 首先需要定位，而定位必須從頭結點開始順鏈一個一個結點進行比較，因此其 “ 基本的操作 ” 為比較運算。比較運算的執(zhí)行次數(shù)與結點的位置有關，最好情況時為 1次（第一個結點），最壞為 n次（所有結點皆比較一次），因此條件插入、刪除運算的 時間復雜度仍然為O(n). 對于在 p所指結點后插入新的結點，無定位問題，因此其時間復雜度為 O(1)。 (1) 單鏈表的存儲密度比順序表低；但在許多情況下鏈式的分配比順序分配有效 ；順序表為靜態(tài)結構，而鏈表為動態(tài)結構。 (2) 在單鏈表里進行插入、刪除運算比在順序表里容易得多；順序表通過數(shù)據(jù)元素移動完成，而鏈表通過修改指針完成。 (3) 對于順序表，可通過簡單的定位公式隨機訪問任一個元素，而在單鏈表中，需要順著鏈逐個進行查找。因此，順序表為隨機存取結構，而鏈表不是。 6. 單鏈表與順序表的比較 （ 1） 有利于基本運算的實現(xiàn) 頻繁訪問：順序表（隨機存?。? 頻繁插入、刪除：鏈表 （ 2） 有利于數(shù)據(jù)的特性 順序表：難于事先估計數(shù)據(jù)元素個數(shù)，過大浪費空間，過小易產生溢出； 鏈表：動態(tài)申請，但存儲密度比順序表低； （ 3） 有利于軟件環(huán)境（程序設計語言） 程序設計語言是否支持動態(tài)分配？ Fortran、 Basic等不支持動態(tài)分配，此時只能選擇順序表。 7. 單鏈表與順序表的選擇 整個結構采用順序表。 順序表中，每個元素包含兩項：數(shù)據(jù)項和存儲后繼位置的游標項。 通過游標表達數(shù)據(jù)元素之間的邏輯關系。邏輯上相鄰元素，存儲位置不一定相鄰。 靜態(tài)鏈表 define MaxSize 1000 /* 供分配空間的大小 */ typedef struct { DataType data。 int cursor。 （ 游標代替鏈表中的指針 ） }Component, SLinkList[MaxSize]。 D1 C1 D3 C3 D4 C4 D2 C2 數(shù)據(jù) 后繼在數(shù)組中的位置（游標） 游標 代替鏈表中的指針，插入、刪除時僅需要修改游標項完成。 此時的靜態(tài)順序表具有鏈表的優(yōu)點。 另外，將整個存儲空間分成兩部分：數(shù)據(jù)元素組成的 工作空間 和備用元素構成的 備用空間 ，這兩部分分別設計一個鏈表（ 靜態(tài)鏈表 ）進行管理。 當需要插入一個結點時，從備用鏈中取出第一個結點作為待插入的結點（類似于 Malloc）；當從工作鏈中刪除一個結點時，將被刪除的結點連接到備用鏈上（類似于 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指示第一個結點在數(shù)組中的位置，若設 i= s[0].cursor, 則 s[i].data保存第一個數(shù)據(jù)元素， s[i].cursor指示第二個結點在數(shù)組中的位置。如第 i個分量表示鏈表的第 k個結點，則 s[i].cursor指示第 k+1個結點在數(shù)組中的位置。 i = s[i].cursor類似鏈表中的 p=plink 最后結點的 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)鏈表，將所有結點連接成一個備用鏈 void InitList(SLinkList list)。 /* 用‘ 0’表示空 */ //從備用鏈中申請空間，返回申請到的空間的下標 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
教學課件相關推薦
鄂ICP備17016276號-1