《单向链结串列》ppt课件

《《单向链结串列》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、單向鏈結串列SinglyLinkedLists定義及表示法節點包含資料（data）及鏈結（link）兩個欄位。其資料結構表示，如下圖所示head：指向串列前端之指標tail：指向串列尾端之指標鏈結串列透過儲存元素在記憶體之位址為指標(Pointer)或鏈結(Link)取得下一個節點。故節點=資料+指標鏈結假設有一節點結構如下圖所示：則其節點結構可定義如下：typedefstructnode{/*以結構體表示節點*/intdata;/*data儲存節點資料項目*/structnode*next;}NODE;/*next儲存下一個節點位址*//*NODE表新定義之節點結

2、構資料型態*/一個指標變數head當作鏈結串列之起始指標，其宣告如下：NODE*head;/*head為一個指標，指向鏈結串列之起始節點*/基本運作及圖解單向鏈結串列的釋放當使用malloc配置了記憶體之後，記憶體會一直存在直到程式結束，所以當不使用時必須釋放，釋放的方法為free(變數名稱)；請務必記得釋放記憶體，雖然不會發生錯誤訊息，可是會一直在記憶體中，導致記憶體的浪費。單向鏈結串列插入如果打算在鏈結中加入一個新的節點，可以使用以下的方法，比方說有一個鏈結串列如下：number12345678910namePeter1Peter2Peter3Peter4Pete

3、r5Peter6Peter7Peter8Peter9Peter10next(指標)指向2號節點指向3號節點指向4號節點指向6號節點指向6號節點指向7號節點指向8號節點指向9號節點指向10號節點NULL現在若想要加入一個11號的Mary節點，加在peter5節點和peter6節點之間，則先新增一個11號的Mary節點：number1234567891011namePeter1Peter2Peter3Peter4Peter5Peter6Peter7Peter8Peter9Peter10Marynext(指標)指向2號節點指向3號節點指向4號節點指向6號節點指向6號節點指向

4、7號節點指向8號節點指向9號節點指向10號節點NULL再把串列改成以下這樣就行了：5號Peter5節點的next指向11號節點。接著把11號的Mary節點的next指向6號的peter6節點就可以了。number1234567891011namePeter1Peter2Peter3Peter4Peter5Peter6Peter7Peter8Peter9Peter10Marynext(指標)指向2號節點指向3號節點指向4號節點指向6號節點指11號節點指向7號節點指向8號節點指向9號節點指向10號節點NULL指向6號節點為了要完成以上的方法，必須建立一些變數儲存資料，以這

5、一個範例為例需要2個指標：指向Mary節點的指標New指向Peter5節點的指標Ptr單向鏈結串列刪除如果打算在鏈結中刪除節點，可以使用以下的方法：比方說有一個鏈結串列如下：number12345678910namePeter1Peter2Peter3Peter4Peter5Peter6Peter7Peter8Peter9Peter10next(指標)指向2號節點指向3號節點指向4號節點指向5號節點指向6號節點指向7號節點指向8號節點指向9號節點指向10號節點NULL若要刪除5號Peter5節點，只需改了2個地方，4號Peter4節點的next指向6號的Peter6：

6、number12345678910namePeter1Peter2Peter3Peter4Peter5Peter6Peter7Peter8Peter9Peter10next(指標)指向2號節點指向3號節點指向4號節點指向6號節點指向6號節點指向7號節點指向8號節點指向9號節點指向10號節點NULL接著把5號Peter5節點釋放掉,使用Free：number1234678910namePeter1Peter2Peter3Peter4Peter6Peter7Peter8Peter9Peter10next(指標)指向2號節點指向3號節點指向4號節點指向6號節點指向7號節點指

7、向8號節點指向9號節點指向10號節點NULL單向鏈結串列的反轉如果鏈結串列如下：number123456789namePeter1Peter2Peter3Peter4Peter5Peter6Peter7Peter8Peter9next(指標)指向2號節點指向3號節點指向4號節點指向5號節點指向6號節點指向7號節點指向8號節點指向9號節點NULL改成：number123456789namePeter1Peter2Peter3Peter4Peter5Peter6Peter7Peter8Peter9next(指標)NULL指向1號節點指向2號節點指向3號節