線性表chap(編輯修改稿)
2024-10-22 19:42 本頁面
【文章內(nèi)容簡介】 Create_Link(DataType data[], int num) 存儲結構及基本運算實現(xiàn) a b p 單鏈表 5. 結點 插入 和 刪除 圖示 單鏈表插入結點時的情況 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ù)，過大浪費空間，過小易產(chǎn)生溢出； 鏈表：動態(tài)申請，但存儲密度比順序表低； （ 3） 有利于軟件環(huán)境（程序設計語言） 程序設計語言是否支持動態(tài)分配？ Fortran、 Basic等不支持動態(tài)分配，此時只能選擇順序表。 7. 單鏈表與順序表的選擇 游標 代替鏈表中的指針，插入、刪除時僅需要修改游標項完成。此時的靜態(tài)順序表具有鏈表的優(yōu)點。另外，將整個存儲空間分成兩部分：數(shù)據(jù)元素組成的 工作空間 和備用元素構成的 備用空間 ，這兩部分分別設計一個鏈表（ 靜態(tài)鏈表 ）進行管理。當需要插入一個結點時，從備用鏈中取出第一個結點作為待插入的結點（類似于 Malloc）；當從工作鏈中刪除一個結點時，將被刪除的結點連接到備用鏈上（類似于 Free）。 靜態(tài)鏈表 define MaxSize 1000 /* 供分配空間的大小 */ typedef struct { DataType data。 int cursor。 （ 游標代替鏈表中的指針 ） }Component, SLinkList[MaxSize]。 假定 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 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)鏈表，將所有結點連接成一個備用鏈 */ 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。
黨政相關相關推薦
鄂ICP備17016276號-1