欢迎来到天天文库
浏览记录
ID:27118254
大小:259.51 KB
页数:38页
时间:2018-12-01
《《单向链结串列》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號節
此文档下载收益归作者所有