单向链结串列.ppt

鏈結串列 (Linked List) 註:要會指標(Pointer) 鍊結串列特性 鏈結串列(linked list)是由許多結點所組成的，在加入和刪除功能上比陣列彈性許多。且加入與刪除的動作，可以針對串列首、串列尾或串列中的某個節點。 鏈結串列視實際需要才配置記憶體空間，可減少浪費。 可以取代陣列儲存方式(堆疊與佇列)，而其所含資料元素的數目可以彈性的增減。 節點（Node） Node的結構與產生 結構宣告： struct node { int number; struct node *llink; } Node 的產生： head = (struct node *) malloc (sizeof(struct node)); Node的結構與產生(續) 結構宣告： struct node { string name; string address; int phone; struct node *llink; } Node 的產生： head = (struct node *) malloc (sizeof(struct node)); Example 假設鏈結串列中每個節點(node)的資料結構有兩欄，分別為資料(data)欄和鏈結(next)欄，結構可需告如下： Struct node { int data; struct node *next; }; 例如：下列串列有a, b, c, d, x等的資料元素。 head：指向串列前端的指標。 tail：指向串列尾端的指標。 鍊結串列概念 鍊結串列 (Linked List) 是一個有序的資料集合，其中每一個元素都包含下一個元素的位址。 也就是說，每一個元素可分為兩部份：資料 (Data) 與鍊結 (Link)。 資料部份儲存資料。 鍊結部份用於將資料鍊結在一起。它包含一個指標，負責辨識串列的下一個元素。 另外，還有一個指標變數，指向串列的第一個元素。 我們討論的鏈結串列－單一鏈結串列，每一個元素只包含一個鍊結，只能指向一個後續元素。 鍊結串列的優點是資料的新增與刪除操作。 當新增與刪除一個元素時，不必因串列中元素邏輯順序的改變，而移動它們的實際儲存位置。 因為串列不要求元素在實際儲存時，要一個接一個地存放。但也無法進行二元搜尋，必須採用循序搜尋。 鍊結串列概念(續) 如圖(a)所示，pHead(指向串列的第一個元素)，包含4個元素。 除了最後一個元素之外，每一個元素中的鍊結都指向它的後續元素。 而最後一個元素的鍊結是一個null指標，表示串列的結束。 若串列的指標變數為null指標，表示它是一個空的鏈結串列，如圖(b) 所示。 鍊結串列的特性就是節點之間沒有實體的 關係，也就是說他們不是連續儲存的。 就鏈結串列而言，在節點之間沒有實體的 關係。 需要指標來辨別串列的第一個節點，還有任何一個節點，其後續節點的位址。 指向串列開始位置的指標稱為表頭指標 (Head Pointer) 。在上圖中，pHead就是 head指標，而link指向節點的後續節點。 鍊結串列種類 可分為： 單向鏈結串列(single linked list) 環狀串列(circular linked list) 雙向鏈結串列(doubly linked list) 單向鏈結串列優點 以陣列方式存放資料時，若要插入（insert）或刪除（delete）某一節點（node）就倍感困難了。 如在陣列中已有a,b,d,e四個元素，現將c加入陣列中，並按字母順序排列。 方法就是d,e往後一格，然後將c插入；而刪除一元素，也必須挪移元素才不會浪費空間，有無方法來改善此一問題呢？ 這就是本章所要探討的鏈結串列（linked list）。 單向鏈結串列(續) 鏈結串列在加入與刪除皆比陣列來得簡單容易，因為只要利用指標（pointer）加以處理就可以了。 假設鏈結串列中每個節點（node）的資料結構有二欄，分別是資料（data）欄和鏈結（next）欄 ，若將節點結構定義為struct node 型態，則宣告如下： 單向鏈結串列(續) 如串列 A={a, b, c, d}，其資料結構如下： head：指向串列前端的指標，通常假設此節點的data欄是空的亦即不放資料，這在一些運作上有其方便之處。 單向鏈結串列(加入於串列的前端) 假設有一串列如下： 有一節點x將加入於串列的前端，其步驟如下： 單向鏈結串列(加入於串列的前端) (3)head-next=x; 單向鏈結串列（加入於