數(shù)據(jù)結(jié)構(gòu)之線性表課件(編輯修改稿)
2024-10-06 09:01 本頁面
【文章內(nèi)容簡介】 如下面的圖所示 。 假設(shè)指針 p指向單鏈表中的第 i個結(jié)點，指針 s指向已生成的新結(jié)點，鏈入新結(jié)點的操作如下： 將新結(jié)點 *s的鏈域指向結(jié)點 *p的后繼結(jié)點 (即 snext=pnext)； 將結(jié)點 *p的鏈域指向新結(jié)點 (即 pnext=s)。 head a1 a 2 a i a n ∧ a i +1 S x P insert(head) /*在第 i個結(jié)點 后 插入結(jié)點 S { linklist *p=head。 int k=0。 while ((p!=null) $$ (kI)) { p=pnext。 k=k+1。 } s=(linklist *)malloc(sizeof(linklist)) if (s= =null) { printf (“沒有足夠的空間 ” ) Return(null) } snext=pnext。 pnext=s。 return(head) 插入算法 Linklist *insertllist (head, x, k) / 在頭指針為 linklist *head。 head的單鏈表的第 K個 elementtype x。 結(jié)點之 前 插入 X int k。 {linklist *p,*pre,*s。 int j=1。 p=head； pre=null。 while [(p!=null) $$ (jk)] /*找出第 k個結(jié)點的 {pre=p； /*指針 p和它的前趨 p=pnext。 /*結(jié)點 pre j++ } 插入算法續(xù) if(j!=k) { printf(“k超出鏈表的長度 ” )。 return(null)。 } s=(linklist *)malloc(sizeof(listlist)) if (s= =null) { printf (“沒有足夠的空間 ” ) Return(null) } 插入算法續(xù) sdata=x。 If (pre==null) /*插入的結(jié)點位于鏈 { snext=head。 /*表的頭部 ， 即 k=1 head=s。 } else { snext=p。 prenext=s。 } return(head) } 3. 刪除 ?假設(shè)單鏈表 帶有頭結(jié)點 ，頭指針為 head，刪除單鏈表上一個 其值為 x的結(jié)點 。主要操作 是： 1) 用遍歷的方法在單鏈表上找到該結(jié)點； 2) 從單鏈表上刪除該結(jié)點。 ?欲從單鏈表上刪除一個結(jié)點，需修改該結(jié)點的前一個結(jié)點的指針，如下面的圖所示。 假設(shè)指針 q指向待刪除結(jié)點的前一個結(jié)點，指針 p指向要刪除的結(jié)點，刪除該結(jié)點的操作如下：將該結(jié)點的前一個結(jié)點 *q的鏈域指向 *p的后繼結(jié)點（即 qnext=pnext）。 x head ∧ p q 刪除算法 Linklist * Delete (head, x) linklist *head。 elementtype x。 { linklist *q,*p。 q=head。 p=headnext。 while((p!=null) amp。amp。 (pdata!=x)) { q=p。 p=pnext。 } 刪除算法續(xù) if (p=NULL) { printf (“x不存在 ” ) return(null)。 } else { qnext=pnext。 /*修改指針 free(p)。 } return(head)。 } 返回 靜態(tài)鏈表 ?在某些語言中，沒有指針類型，就不能實現(xiàn)鏈表，可用一數(shù)組來模擬鏈表，這就是靜態(tài)鏈表。 ?靜態(tài)鏈表的定義 define maxsize 元素的最大個數(shù) typedef struct {elementtype data。 int next。 }slinklist。 如： slinklist sl[maxsize]。 定義了一個有 maxsize個元素的數(shù)組，每個元素由信息域和指針域組成。 ?例： L=（ a， b， c， d， e， f）， 0 0 1 1 2 2 3 3 4 4 5 5 6 6 插入 h之后 0 1 a 2 b 3 c 4 d 5 e 6 f 0 0 1 a 2 b 7 c 4 d 5 e 6 f 0 h 3 線性表實現(xiàn)方法比較 ?鏈表：在已知元素個數(shù)的情況下，浪費空間； 在未知元素個數(shù)的情況下，節(jié)約空間； 速度快。 ?順序表：在已知元素個數(shù)的情況下，空間利用率 高；
法律信息相關(guān)推薦
鄂ICP備17016276號-1