[計算機軟件及應用]數(shù)據(jù)結構課件吳偉民編著-文庫吧資料
2024-10-25 04:12本頁面
【正文】 ad中數(shù)據(jù)域為 a的結點。pnext=qnext。++j。amp。j=0。 int j。 p q ? a 1 x a 2 圖 刪除結點的指針修改 思想 ：先找到被刪結點（第 i個）的前趨結點，即第 i1個結點 *p,然后刪除 *p的后繼。 pnext=s。 sdata=x。++j。amp。j=0。 int j。 pnext=s。 算法思想： (1)先求出第 i1個結點 (2)然后在第 i1個結點之后插入結點 x。 } 算法的時間復雜度都為Ｏ (n)。(pdata!=x)) p=pnext。 while((p!=NULL)amp。 listnode *Locate(listnode *head,elemtype x) { listnode *p。 (2) 按值查找 Locate(L,x) 在單鏈表 L中 ， 查找值為 x的結點 ， 若找到 ， 返回它的地址 ， 否則返回 NULL。 } return p。(p!=NULL)) { j++。 while((ji)amp。 j=1。 listnode *get(listnode *L,int i) { int j。 P的 初值指向頭結點， j的初值為 0。 用 C語言描述的單鏈表如下： 頭結點：在單鏈表第一個結點前附設一 個結點叫 ~ 頭結點指針域為空表示線性表為空 h a1 a2 頭結點 an ^ …... h 空表 ^ 不帶頭結點的單鏈表 a 1 h e a d a 2 …… an ^ 單鏈表上的查找運算 (1) 按序號查找 get(L,i) 在單鏈表 L中查找第 i個位置上的元素 ， 若找到 ， 則返回它的地址 ， 否則返回 NULL。 struct node *next。 系統(tǒng)回收 p結點： free(p) Typedef char Elemtype。 一、線性鏈表 結點中只含一個指針域的鏈表叫 ~，也叫單鏈表 例 線性表 (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。 ?順序存儲結構的優(yōu)缺點 ?優(yōu)點 ?邏輯相鄰，物理相鄰 ?可隨機存取任一元素 ?存儲空間使用緊湊 ?缺點 ?插入、刪除操作需要移動大量的元素 ?預先分配空間需按最大空間分配，利用不充分 ?表容量難以擴充 線性表的鏈式存儲結構 存儲方式 ?用一組 任意 的存儲單元存儲線性表的數(shù)據(jù)元素 ?利用 指針 實現(xiàn)用不相鄰的存儲單元存放邏輯上相鄰的元素 ?每個數(shù)據(jù)元素 ai， 除存儲本身信息外，還需存儲其直接后繼的信息 結點 :數(shù)據(jù) ai的鏈式存儲映象 . ?數(shù)據(jù)域：元素本身信息 ?指針域：指示直接后繼的存儲位置 數(shù)據(jù)域 指針域 結點 鏈式存儲結構 :n個結點鏈結成的一個鏈表 單鏈表中每個結點的存儲地址是存放在其前趨結點 next域中，而開始結點無前趨，故設頭指針 head指向開始結點。 int listsize。 typedef struct{ ElemType *elem。 小結： 順序表插入、刪除算法平均約需移動一半結點，當 n很大時，算法的效率較低。 若 i=1,最壞： O(n) 若 i=n,無需用移動結點，直接刪除即可。 Llength。j=Llength1。 return ERROR。 演示 內存 a1 a2 ai ai+1 an 0 1 i1 V數(shù)組下標 n1 i n 1 2 i 元素序號 i+1 n n+1 內存 a1 a2 ai+1 V數(shù)組下標 0 1 i1 n2 i n1 1 2
教學課件相關推薦
鄂ICP備17016276號-1