【正文】 j = 0。 while (p amp。amp。 j i1) { p = pnext。 ++j。 } // 尋找第 i1 個結點 if (!p || j i1) return ERROR。 // i 大于表長或者小于 1 s = (LinkList) malloc ( sizeof (LNode))。 // 生成新結點 sdata = e。 snext = pnext。 pnext = s。 // 插入 return OK。 e ai1 ai s p ?線性表的操作 ListDelete (amp。L, i, amp。e) 在鏈表中的實現 : 有序對 ai1, ai 和 ai, ai+1 改變?yōu)? ai1, ai+1 ai1 ai ai+1 在單鏈表中 刪除第 i 個結點 的 基本操作 為 :找到線性表中第 i1個結點，修改其指向后繼的指針。 ai1 ai ai+1 q = pnext。 pnext = qnext。 e = qdata。 free(q)。 p q Status ListDelete_L(LinkList L, int i, ElemType amp。e) { // 刪除以 L 為頭指針 (帶頭結點 )的單鏈表中第 i 個結點 } // ListDelete_L 算法的 時間復雜度 為 : O(ListLength(L)) p = L。 j = 0。 while (pnext amp。amp。 j i1) { p = pnext。 ++j。 } // 尋找第 i 個結點，并令 p 指向其前趨 if (!(pnext) || j i1) return ERROR。 // 刪除位置不合理 q = pnext。 pnext = qnext。 // 刪除并釋放結點 e = qdata。 free(q)。 return OK。 ?操作 ClearList(amp。L) 在鏈表中的實現 : void ClearList(amp。L) { // 將單鏈表重新置為一個空表 while (Lnext) { p=Lnext。 Lnext=pnext。 } } // ClearList free(p)。 算法 時間復雜度 ： O(ListLength(L)) 如何從線性表得到單鏈表？ 鏈表是一個動態(tài)的結構，它不需要予分配空間，因此 生成鏈表的過程是一個結點“ 逐個插入 ” 的過程。 例如： 逆位序 輸入 n 個數據元素的值， 建立帶頭結點的單鏈表。 操作步驟： 一、建立一個“空表”； 二、輸入數據元素 an， 建立結點并插入； 三、輸入數據元素 an1， 建立結點并插入； an an an1 四、依次類推，直至輸入 a1為止。 void CreateList_L(LinkList amp。L, int n) { // 逆序輸入 n 個數據元素，建立帶頭結點的單鏈表 } // CreateList_L 算法的 時間復雜度 為 : O(Listlength(L)) L = (LinkList) malloc (sizeof (LNode))。 Lnext = NULL。 // 先建立一個帶頭結點的單鏈表 for (i = n。 i 0。 i) { p = (LinkList) malloc (sizeof (LNode))。 scanf(amp。pdata)。 // 輸入元素值 pnext = Lnext。 Lnext = p。 // 插入 } 補充作業(yè)： 寫出按 正位序 建立一個單鏈表的算法。 ?單鏈表的優(yōu)點 ?它是一種 動態(tài)結構 ，整個存儲空間為多個鏈表共用 ?不需預先分配 空間 ?插入、刪除操作方便 ?單鏈表的缺點 ?指針占用 額外 存儲空間 ?不能隨機存取 ，查找速度慢 最后一個結點的指針域的指針又指回第一個結點的鏈表。 a1 a2 … ... a n ?循環(huán)鏈表 和單鏈表的差別僅在于， 判別 鏈表中最后一個結點的 條件 不再是“后繼是否為空”，而是 “后繼是否為頭結點” 。 四、其他形式的鏈表 ?雙向鏈表 typedef struct DuLNode { ElemType data。 // 數據域 struct DuLNode *prior。 // 指向前驅的指針域 struct DuLNode *next。 // 指向后繼的指針域 } DuLNode, *DuLinklist。 prior data next b c a p ppriornext= p= pnextproir。 雙向循環(huán)鏈表 空表 非空表 a1 a2 … ... a n 雙向鏈表的操作特點： “ 查詢” 和單鏈表相同。 “ 插入” 和“刪除”時需要同時修改兩個方向上的指針。 ai1 ai e sprior= pprior。 pprior next=s。 snext = p。 pprior = s 。 p s ?插入 ai1 ?刪除 ai ai+1 ppriornext = pnext。 pnextprior = pprior。 p 第二章作業(yè) 試寫一算法 ,對單鏈表實現就地逆置 ,即利用原表的存儲空間將線性表 （ a1,a2,… ,an）逆置為（ an,an1,… ,a1） 提示： 將原鏈表中的頭結點和第一個元素結點斷開（令其指針域為空），先構成一個空表，然后將原鏈表中各結點從第一個結點起依次插入這個新表的頭部。