[計算機軟件及應用]數(shù)據(jù)結構課件吳偉民編著(編輯修改稿)
2025-11-15 04:12 本頁面
【文章內容簡介】 data[j1]=Ldata[j]。 Llength。 } 刪除算法分析： 上述算法 for循環(huán)語句的執(zhí)行次數(shù)為 ni。 若 i=1,最壞： O(n) 若 i=n,無需用移動結點，直接刪除即可。（最好 O(1)） 移動結點的平均次數(shù)： 按等概率考慮： 可能的刪除位置為 i=1,2,……n 共 n個，則 pi=1/n 所以 順序表插入算法平均約需移動一半結點。 小結： 順序表插入、刪除算法平均約需移動一半結點，當 n很大時，算法的效率較低。 順序表存儲空間的動態(tài)分配 若將前面線性表的順序存儲結構類型中的數(shù)組形式改為指針形式 ， 則得到動態(tài)分配形式如下： typedef int ElemType。 typedef struct{ ElemType *elem。 int length。 int listsize。 } Sqlist。 ?順序存儲結構的優(yōu)缺點 ?優(yōu)點 ?邏輯相鄰，物理相鄰 ?可隨機存取任一元素 ?存儲空間使用緊湊 ?缺點 ?插入、刪除操作需要移動大量的元素 ?預先分配空間需按最大空間分配，利用不充分 ?表容量難以擴充 線性表的鏈式存儲結構 存儲方式 ?用一組 任意 的存儲單元存儲線性表的數(shù)據(jù)元素 ?利用 指針 實現(xiàn)用不相鄰的存儲單元存放邏輯上相鄰的元素 ?每個數(shù)據(jù)元素 ai， 除存儲本身信息外，還需存儲其直接后繼的信息 結點 :數(shù)據(jù) ai的鏈式存儲映象 . ?數(shù)據(jù)域：元素本身信息 ?指針域：指示直接后繼的存儲位置 數(shù)據(jù)域 指針域 結點 鏈式存儲結構 :n個結點鏈結成的一個鏈表 單鏈表中每個結點的存儲地址是存放在其前趨結點 next域中，而開始結點無前趨，故設頭指針 head指向開始結點。同時，由于終端結點無后繼，故終端結點的指針域為空，即 null（圖示中也可用 ^表示 )。 一、線性鏈表 結點中只含一個指針域的鏈表叫 ~，也叫單鏈表 例 線性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)的單鏈表示意圖如下 ZHAO QIAN SUN LI ZHOU WU ZHENG WANG ^ H 43 13 1 NULL 37 7 19 25 數(shù)據(jù)域 指針域 LI QIAN SUN WANG WU ZHAO ZHENG ZHOU 存儲地址 1 7 13 19 25 31 37 43 31 H 頭指針 listnode *h,*p。 data next p 結點（ *p） (*p)表示 p所指向的結點 (*p).data?pdata表示 p指向結點的數(shù)據(jù)域 (*p).next?pnext表示 p指向結點的指針域 生成一個 listnode型 新結點： p=(listnode *)malloc(sizeof(listnode))。 系統(tǒng)回收 p結點： free(p) Typedef char Elemtype。 Typedef struct node{ Elemtype data。 struct node *next。 }listnode。 用 C語言描述的單鏈表如下： 頭結點：在單鏈表第一個結點前附設一 個結點叫 ~ 頭結點指針域為空表示線性表為空 h a1 a2 頭結點 an ^ …... h 空表 ^ 不帶頭結點的單鏈表 a 1 h e a d a 2 …… an ^ 單鏈表上的查找運算 (1) 按序號查找 get(L,i) 在單鏈表 L中查找第 i個位置上的元素 ， 若找到 ， 則返回它的地址 ， 否則返回 NULL。 算法思想如下： 從頭結點開始順鏈掃描，用指針 p指向當前掃描到的結點，用 j作統(tǒng)計已掃描結點數(shù)的計數(shù)器，當 p掃描下一個結點時， j自動加 1。 P的 初值指向頭結點， j的初值為 0。 當 j=i時，指針 p所指的結點就是第 i個結點。 listnode *get(listnode *L,int i) { int j。 listnode *p。 j=1。 p=Lnext。 while((ji)amp。amp。(p!=NULL)) { j++。 p=pnext。 } return p。 } 算法的時間復雜度都為Ｏ (n)。 (2) 按值查找 Locate(L,x) 在單鏈表 L中 ， 查找值為 x的結點 ， 若找到 ， 返
教學課件相關推薦
鄂ICP備17016276號-1