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