第4章链结串列linkedlists

第4章链结串列linkedlists内容摘要：

點插入串列第 1個節點之前： 只需將新節點newnode的指標指向串列的第 1個節點 first，新節點就成為串列的第 1個節點，如下圖所示：  newnodenext = first。 first = newnode。 433 插入單向鏈結串列的節點 情況 2  將節點插在串列的最後 1個節點之後： 只需將原來串列最後 1個節點的指標指向新節點 newnode，新節點指向 NULL，如下圖所示：  ptrnext = newnode。 newnodenext = NULL。 433 插入單向鏈結串列的節點 情況 3(1)  將節點插在串列的中間位置： 假設節點是插在 p和 q兩個節點之間， p是 q的前一個節點，如下圖所示： 433 插入單向鏈結串列的節點 情況 3(2)  只需將 p指標指向新節點 newnode，然後將新節點指標指向 q，就可以插入新節點，如下圖所示：  newnodenext=ptrnext。 ptrnext = newnode。 44 環狀鏈結串列 說明  如果將最後一個節點的指標改為指向單向鏈結串列開始的第 1個節點，這種串列稱為「環狀鏈結串列」（ Circular Lists）。 44 環狀鏈結串列 建立與走訪  環狀鏈結串列的建立只需將最後 1個節點的 last指標指向第 1個節點，即可完成環狀鏈結串列的建立，如下所示： lastnext = first。  環狀鏈結串列的走訪檢查是否到串列結束的條件是 currentnext == first，如下所示： CList current = first。 do { ……… current = currentnext。 } while ( current != first )。 44 環狀鏈結串列 插入 節 點 (情況 1步驟 )  將節點插入第 1個節點之前成為串列開始，可以分成三個步驟，如下所示： • Step 1： 將新節點 newnode的 next指標指向串列的第 1個節點。 newnodenext = first。 • Step 2： 然後找到最後 1個節點 previous且將其指標指向新節點。 previous = first。 while ( previousnext != first ) previous = previousnext。 previousnext = newnode。 • Step 3： 將串列的開始指向新節點，新節點成為串列的第 1個節點。 first = newnode。 44 環狀鏈結串列 插入 節 點 (情況 1圖例 ) 44 環狀鏈結串列 插入 節 點 (情況 2步驟 )  將節點插在串列中指定節點之後，例如：將節點插在節點 ptr之後，分成二個步驟，如下所示： •Step 1：將新節點 newnode的 next指標指向節點ptr的下一個節點。 newnodenext = ptrnext。 •Step 2：將節點 ptr的指標指向新節點 newnode。 ptrnext = newnode。 44 環狀鏈結串列 插入 節 點 (情況 2圖例 ) 44 環狀鏈結串列 刪 除節點 (情況 1步驟 )  刪除環狀串列的第 1個節點可以分成二個步驟，如下所示： •Step 1： 將串列開始的 first指標移至第 2個節點。 first = firstnext。 •Step 2： 將最後 1個節點的 previous指標指向第 2個節點。 previousnext = ptrnext。 44 環狀鏈結串列 刪 除節點 (情況 1圖例 ) 44 環狀鏈結串列 刪 除節點 (情況 2步驟 )  刪除環狀串列的中間節點，例如：刪除節點 ptr分成二個步驟，如下所示： •Step 1：先找到節點 ptr的前一個節點 previous。 while ( previousnext != ptr ) previous = previousnext。 •Step 2：將前節點的指標指向節點 ptr的下節點。 previousnext = ptrnext。 44 環狀鏈結串列 刪 除節點 (情況 2圖例 ) 45 雙向鏈結。