數據結構之線性表課件(編輯修改稿)

　

【文章內容簡介】 如下面的圖所示 。 假設指針 p指向單鏈表中的第 i個結點，指針 s指向已生成的新結點，鏈入新結點的操作如下： 將新結點 *s的鏈域指向結點 *p的后繼結點 (即 snext=pnext)； 將結點 *p的鏈域指向新結點 (即 pnext=s)。 head a1 a 2 a i a n ∧ a i +1 S x P insert(head) /*在第 i個結點 后 插入結點 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。 結點之 前 插入 X int k。 {linklist *p,*pre,*s。 int j=1。 p=head； pre=null。 while [(p!=null) $$ (jk)] /*找出第 k個結點的 {pre=p； /*指針 p和它的前趨 p=pnext。 /*結點 pre j++ } 插入算法續 if(j!=k) { printf(“k超出鏈表的長度 ” )。 return(null)。 } s=(linklist *)malloc(sizeof(listlist)) if (s= =null) { printf (“沒有足夠的空間 ” ) Return(null) } 插入算法續 sdata=x。 If (pre==null) /*插入的結點位于鏈 { snext=head。 /*表的頭部 ， 即 k=1 head=s。 } else { snext=p。 prenext=s。 } return(head) } 3. 刪除 ?假設單鏈表 帶有頭結點 ，頭指針為 head，刪除單鏈表上一個 其值為 x的結點 。主要操作 是： 1) 用遍歷的方法在單鏈表上找到該結點； 2) 從單鏈表上刪除該結點。 ?欲從單鏈表上刪除一個結點，需修改該結點的前一個結點的指針，如下面的圖所示。 假設指針 q指向待刪除結點的前一個結點，指針 p指向要刪除的結點，刪除該結點的操作如下：將該結點的前一個結點 *q的鏈域指向 *p的后繼結點（即 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。 } 刪除算法續 if (p=NULL) { printf (“x不存在 ” ) return(null)。 } else { qnext=pnext。 /*修改指針 free(p)。 } return(head)。 } 返回 靜態鏈表 ?在某些語言中，沒有指針類型，就不能實現鏈表，可用一數組來模擬鏈表，這就是靜態鏈表。 ?靜態鏈表的定義 define maxsize 元素的最大個數 typedef struct {elementtype data。 int next。 }slinklist。 如： slinklist sl[maxsize]。 定義了一個有 maxsize個元素的數組，每個元素由信息域和指針域組成。 ?例： 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 線性表實現方法比較 ?鏈表：在已知元素個數的情況下，浪費空間； 在未知元素個數的情況下，節約空間； 速度快。 ?順序表：在已知元素個數的情況下，空間利用率 高；