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