第4章鏈結(jié)串列l(wèi)inkedlists(編輯修改稿)
2024-11-16 13:36 本頁面
【文章內(nèi)容簡介】 點(diǎn)插入串列第 1個(gè)節(jié)點(diǎn)之前： 只需將新節(jié)點(diǎn)newnode的指標(biāo)指向串列的第 1個(gè)節(jié)點(diǎn) first，新節(jié)點(diǎn)就成為串列的第 1個(gè)節(jié)點(diǎn)，如下圖所示： ? newnodenext = first。 first = newnode。 433 插入單向鏈結(jié)串列的節(jié)點(diǎn) 情況 2 ? 將節(jié)點(diǎn)插在串列的最後 1個(gè)節(jié)點(diǎn)之後： 只需將原來串列最後 1個(gè)節(jié)點(diǎn)的指標(biāo)指向新節(jié)點(diǎn) newnode，新節(jié)點(diǎn)指向 NULL，如下圖所示： ? ptrnext = newnode。 newnodenext = NULL。 433 插入單向鏈結(jié)串列的節(jié)點(diǎn) 情況 3(1) ? 將節(jié)點(diǎn)插在串列的中間位置： 假設(shè)節(jié)點(diǎn)是插在 p和 q兩個(gè)節(jié)點(diǎn)之間， p是 q的前一個(gè)節(jié)點(diǎn)，如下圖所示： 433 插入單向鏈結(jié)串列的節(jié)點(diǎn) 情況 3(2) ? 只需將 p指標(biāo)指向新節(jié)點(diǎn) newnode，然後將新節(jié)點(diǎn)指標(biāo)指向 q，就可以插入新節(jié)點(diǎn)，如下圖所示： ? newnodenext=ptrnext。 ptrnext = newnode。 44 環(huán)狀鏈結(jié)串列 說明 ? 如果將最後一個(gè)節(jié)點(diǎn)的指標(biāo)改為指向單向鏈結(jié)串列開始的第 1個(gè)節(jié)點(diǎn)，這種串列稱為「環(huán)狀鏈結(jié)串列」（ Circular Lists）。 44 環(huán)狀鏈結(jié)串列 建立與走訪 ? 環(huán)狀鏈結(jié)串列的建立只需將最後 1個(gè)節(jié)點(diǎn)的 last指標(biāo)指向第 1個(gè)節(jié)點(diǎn)，即可完成環(huán)狀鏈結(jié)串列的建立，如下所示： lastnext = first。 ? 環(huán)狀鏈結(jié)串列的走訪檢查是否到串列結(jié)束的條件是 currentnext == first，如下所示： CList current = first。 do { ……… current = currentnext。 } while ( current != first )。 44 環(huán)狀鏈結(jié)串列 插入 節(jié) 點(diǎn) (情況 1步驟 ) ? 將節(jié)點(diǎn)插入第 1個(gè)節(jié)點(diǎn)之前成為串列開始，可以分成三個(gè)步驟，如下所示： ? Step 1： 將新節(jié)點(diǎn) newnode的 next指標(biāo)指向串列的第 1個(gè)節(jié)點(diǎn)。 newnodenext = first。 ? Step 2： 然後找到最後 1個(gè)節(jié)點(diǎn) previous且將其指標(biāo)指向新節(jié)點(diǎn)。 previous = first。 while ( previousnext != first ) previous = previousnext。 previousnext = newnode。 ? Step 3： 將串列的開始指向新節(jié)點(diǎn)，新節(jié)點(diǎn)成為串列的第 1個(gè)節(jié)點(diǎn)。 first = newnode。 44 環(huán)狀鏈結(jié)串列 插入 節(jié) 點(diǎn) (情況 1圖例 ) 44 環(huán)狀鏈結(jié)串列 插入 節(jié) 點(diǎn) (情況 2步驟 ) ? 將節(jié)點(diǎn)插在串列中指定節(jié)點(diǎn)之後，例如：將節(jié)點(diǎn)插在節(jié)點(diǎn) ptr之後，分成二個(gè)步驟，如下所示： ?Step 1：將新節(jié)點(diǎn) newnode的 next指標(biāo)指向節(jié)點(diǎn)ptr的下一個(gè)節(jié)點(diǎn)。 newnodenext = ptrnext。 ?Step 2：將節(jié)點(diǎn) ptr的指標(biāo)指向新節(jié)點(diǎn) newnode。 ptrnext = newnode。 44 環(huán)狀鏈結(jié)串列 插入 節(jié) 點(diǎn) (情況 2圖例 ) 44 環(huán)狀鏈結(jié)串列 刪 除節(jié)點(diǎn) (情況 1步驟 ) ? 刪除環(huán)狀串列的第 1個(gè)節(jié)點(diǎn)可以分成二個(gè)步驟，如下所示： ?Step 1： 將串列開始的 first指標(biāo)移至第 2個(gè)節(jié)點(diǎn)。 first = firstnext。 ?Step 2： 將最後 1個(gè)節(jié)點(diǎn)的 previous指標(biāo)指向第 2個(gè)節(jié)點(diǎn)。 previousnext = ptrnext。 44 環(huán)狀鏈結(jié)串列 刪 除節(jié)點(diǎn) (情況 1圖例 ) 44 環(huán)狀鏈結(jié)串列 刪 除節(jié)點(diǎn) (情況 2步驟 ) ? 刪除環(huán)狀串列的中間節(jié)點(diǎn)，例如：刪除節(jié)點(diǎn) ptr分成二個(gè)步驟，如下所示： ?Step 1：先找到節(jié)點(diǎn) ptr的前一個(gè)節(jié)點(diǎn) previous。 while ( previousnext != ptr ) previous = previousnext。 ?Step 2：將前節(jié)點(diǎn)的指標(biāo)指向節(jié)點(diǎn) ptr的下節(jié)點(diǎn)。 previousnext = ptrnext。 44 環(huán)狀鏈結(jié)串列 刪 除節(jié)點(diǎn) (情況 2圖例 ) 45 雙向鏈結(jié)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1