【正文】 p 第二章作業(yè) 試寫一算法 ,對單鏈表實現就地逆置 ,即利用原表的存儲空間將線性表 （ a1,a2,… ,an）逆置為（ an,an1,… ,a1） 提示： 將原鏈表中的頭結點和第一個元素結點斷開（令其指針域為空），先構成一個空表，然后將原鏈表中各結點從第一個結點起依次插入這個新表的頭部。 p s ?插入 ai1 ?刪除 ai ai+1 ppriornext = pnext。 snext = p。 ai1 ai e sprior= pprior。 雙向循環(huán)鏈表 空表 非空表 a1 a2 … ... a n 雙向鏈表的操作特點： “ 查詢” 和單鏈表相同。 // 指向后繼的指針域 } DuLNode, *DuLinklist。 // 數據域 struct DuLNode *prior。 a1 a2 … ... a n ?循環(huán)鏈表 和單鏈表的差別僅在于， 判別 鏈表中最后一個結點的 條件 不再是“后繼是否為空”，而是 “后繼是否為頭結點” 。 // 插入 } 補充作業(yè)： 寫出按 正位序 建立一個單鏈表的算法。 // 輸入元素值 pnext = Lnext。 scanf(amp。 i 0。 Lnext = NULL。 void CreateList_L(LinkList amp。 例如： 逆位序 輸入 n 個數據元素的值， 建立帶頭結點的單鏈表。 } } // ClearList free(p)。L) { // 將單鏈表重新置為一個空表 while (Lnext) { p=Lnext。 ?操作 ClearList(amp。 free(q)。 pnext = qnext。 } // 尋找第 i 個結點，并令 p 指向其前趨 if (!(pnext) || j i1) return ERROR。 j i1) { p = pnext。 while (pnext amp。e) { // 刪除以 L 為頭指針 (帶頭結點 )的單鏈表中第 i 個結點 } // ListDelete_L 算法的 時間復雜度 為 : O(ListLength(L)) p = L。 free(q)。 pnext = qnext。e) 在鏈表中的實現 : 有序對 ai1, ai 和 ai, ai+1 改變?yōu)? ai1, ai+1 ai1 ai ai+1 在單鏈表中 刪除第 i 個結點 的 基本操作 為 :找到線性表中第 i1個結點，修改其指向后繼的指針。 e ai1 ai s p ?線性表的操作 ListDelete (amp。 pnext = s。 // 生成新結點 sdata = e。 } // 尋找第 i1 個結點 if (!p || j i1) return ERROR。 j i1) { p = pnext。 while (p amp。 Status ListInsert_L(LinkList L, int i, ElemType e) { // L 為帶頭結點的單鏈表的頭指針，本算法 // 在鏈表中第 i 個結點之前插入新的元素 e } // LinstInsert_L 算法的 時間復雜度 為 : O(ListLength(L)) …… p = L。 可見，在鏈表中插入結點只需要修改指針。 ai1 ?線性表的操作 ListInsert(amp。 // 第 i 個元素不存在 e = pdata。 ++j。amp。 j = 1。 Status GetElem_L(LinkList L, int i, ElemType amp。 單鏈表是一種順序存取的結構，為找第 i 個數據元素，必須先找到第 i1 個數據元素。 ++j。amp。L, n) // 生成含 n 個數據元素的鏈表 ?線性表的操作 GetElem(L, i, amp。L, i, e) // 刪除 數據元素 ClearList(amp。 data next p 結點（ *p） (*p)表示 p所指向的結點 (*p).data?pdata表示 p指向結點的數據域 (*p).next?pnext表示 p指向結點的指針域 二、結點和單鏈表的 C 語言描述 ai ai+1 p … … pnext 三、單鏈表操作的實現 GetElem(L, i, e) // 取第 i個數據元素 ListInsert(amp。 空指針 線性表為空表時， 頭結點的指針域為空 ? typedef struc LNode{ // 定義單鏈表結點 ElemType data。 數據域 指針域 結點 以 元素 (數據元素的映象 ) + 指針 (指示后繼元素存儲位置 ) = 結點 (表示數據元素 或 數據元素的映象 ) ZHAO QIAN SUN LI ZHOU WU ZHENG WANG ^ H 例 線性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG) 43 13 1 NULL 37 7 19 25 數據域 指針域 LI QIAN SUN WANG WU ZHAO ZHENG ZHOU 存儲地址 1 7 13 19 25 31 37 43 31 H 頭指針 以線性表中第一個數據元素 的存儲地址 作為線性表的地址，稱作線性表的頭指針 。 ?順序存儲結構的優(yōu)缺點 ?優(yōu)點