链结串列 （Linked List）注要会指标（Pointer）.ppt

《链结串列 （Linked List）注要会指标（Pointer）.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、鏈結串列(LinkedList)註:要會指標(Pointer)授課老師：蕭志明1鍊結串列特性鏈結串列(linkedlist)是由許多結點所組成的，在加入和刪除功能上比陣列彈性許多。且加入與刪除的動作，可以針對串列首、串列尾或串列中的某個節點。鏈結串列視實際需要才配置記憶體空間，可減少浪費。可以取代陣列儲存方式(堆疊與佇列)，而其所含資料元素的數目可以彈性的增減。陣列儲存方式鏈結串列儲存方式加入與刪除需做大量的資料搬移僅須改變指標即可記憶空間無需額外的空間存放鏈結資料需額外的空間存放鏈結資料資料的存取可對資料做直接的存取適合資料的循序存取資料的合併與分開鏈結

2、串列較優於陣列，因為只需改變一些指標即可2節點（Node）節點(Node)是鏈結串列中的重要元素節點(Node)是一個最少有兩個欄位的結構：一個欄位包含資料。另一個欄位包含串列中下一個節點的位址。3Node的結構與產生結構宣告：structnode{intnumber;structnode*llink;}Node的產生：head=(structnode*)malloc(sizeof(structnode));4Node的結構與產生(續)結構宣告：structnode{stringname;stringaddress;intphone;structnode*

3、llink;}Node的產生：head=(structnode*)malloc(sizeof(structnode));5Example假設鏈結串列中每個節點(node)的資料結構有兩欄，分別為資料(data)欄和鏈結(next)欄，結構可需告如下：Structnode{intdata;structnode*next;};例如：下列串列有a,b,c,d,x等的資料元素。head：指向串列前端的指標。tail：指向串列尾端的指標。abcdxheadtail6鍊結串列概念鍊結串列(LinkedList)是一個有序的資料集合，其中每一個元素都包含下一個元素的位址

4、。也就是說，每一個元素可分為兩部份：資料(Data)與鍊結(Link)。資料部份儲存資料。鍊結部份用於將資料鍊結在一起。它包含一個指標，負責辨識串列的下一個元素。另外，還有一個指標變數，指向串列的第一個元素。我們討論的鏈結串列－單一鏈結串列，每一個元素只包含一個鍊結，只能指向一個後續元素。鍊結串列的優點是資料的新增與刪除操作。當新增與刪除一個元素時，不必因串列中元素邏輯順序的改變，而移動它們的實際儲存位置。因為串列不要求元素在實際儲存時，要一個接一個地存放。但也無法進行二元搜尋，必須採用循序搜尋。7鍊結串列概念(續)如圖(a)所示，pHead(指向串列的第

5、一個元素)，包含4個元素。除了最後一個元素之外，每一個元素中的鍊結都指向它的後續元素。而最後一個元素的鍊結是一個null指標，表示串列的結束。若串列的指標變數為null指標，表示它是一個空的鏈結串列，如圖(b)所示。8鍊結串列的特性就是節點之間沒有實體的關係，也就是說他們不是連續儲存的。就鏈結串列而言，在節點之間沒有實體的關係。需要指標來辨別串列的第一個節點，還有任何一個節點，其後續節點的位址。指向串列開始位置的指標稱為表頭指標(HeadPointer)。在上圖中，pHead就是head指標，而link指向節點的後續節點。鏈結串列資料結構9鍊結串列種類可分

6、為：單向鏈結串列(singlelinkedlist)環狀串列(circularlinkedlist)雙向鏈結串列(doublylinkedlist)10單向鏈結串列優點以陣列方式存放資料時，若要插入（insert）或刪除（delete）某一節點（node）就倍感困難了。如在陣列中已有a,b,d,e四個元素，現將c加入陣列中，並按字母順序排列。方法就是d,e往後一格，然後將c插入；而刪除一元素，也必須挪移元素才不會浪費空間，有無方法來改善此一問題呢？這就是本章所要探討的鏈結串列（linkedlist）。11單向鏈結串列(續)鏈結串列在加入與刪除皆比陣列來得簡

7、單容易，因為只要利用指標（pointer）加以處理就可以了。假設鏈結串列中每個節點（node）的資料結構有二欄，分別是資料（data）欄和鏈結（next）欄，若將節點結構定義為structnode型態，則宣告如下：12單向鏈結串列(續)如串列A={a,b,c,d}，其資料結構如下：head：指向串列前端的指標，通常假設此節點的data欄是空的亦即不放資料，這在一些運作上有其方便之處。13單向鏈結串列(加入於串列的前端)假設有一串列如下：有一節點x將加入於串列的前端，其步驟如下：(1)x=(structnode*)malloc(sizeof(structno

8、de));(2)x->next=head->next;14單向鏈結