删除环状串列的前端.PPT

Chapter 4 鏈結串列 4.1 單項鏈結串列 4.2 環狀串列 4.3 雙向鏈結串列 4.4 鏈結串列之應用 鏈結串列 鏈結串列（linked list）是由許多節點所組成的，在加入和刪除功能上比陣列容易許多。 鏈結串列可分為單向鏈結串列（single linked list）、環狀串列（circular linked list）及雙向鏈結串列（doubly linked list），本章的目標旨在如何學習到每一種鏈結串列的加入與刪除，而這些加入與刪除的動作，又可針對串列首、串列尾或串列的某個特定的節點。 4.1 單向鏈結串列 以陣列方式存放資料時，若要插入（insert）或刪除（delete）某一節點（node）就倍感困難了，如在陣列中已有a,b,d,e四個元素，現將c加入陣列中，並按字母順序排列，方法就是d,e往後一格，然後將c插入；而刪除一元素，也必須挪移元素才不會浪費空間，有無方法來改善此一問題呢？這就是本章所要探討的鏈結串列（linked list）。 4.1 單向鏈結串列 鏈結串列在加入與刪除皆比陣列來得簡單容易，因為只要利用指標（pointer）加以處理即可。 假設鏈結串列中每個節點（node）的資料結構有二欄，分別是資料（data）欄和鏈結（next）欄　　 ，若將節點結構定義為struct node 型態，則表示如下： 4.1 單向鏈結串列 如串列 A={a, b, c, d}，其資料結構如下： head：指向串列前端的指標，通常假設此節點的data欄是空的亦即不放資料，這在一些運作上有其方便之處。 4.1 單向鏈結串列 4.1.1 加入動作 1.加入於串列的前端：假設有一串列如下： 4.1 單向鏈結串列 有一節點x將加入於串列的前端，其步驟如下： x=(struct node*) malloc(sizeof(struct node)); 4.1 單向鏈結串列 (x-next=head-next; /* */ 4.1 單向鏈結串列 head-next=x; /* */ 4.1 單向鏈結串列 2.加入於串列的尾端：假設有一串列如下： 4.1 單向鏈結串列 將一節點x加入於串列的尾端，其步驟如下： x=(struct node *)malloc(sizeof(struct node)); x-next=NULL; 4.1 單向鏈結串列 此時必須追蹤此串列的尾端在那兒，利用下列的片段程式便可找到串列的尾端。 4.1 單向鏈結串列 p-next=x; 4.1 單向鏈結串列 加入在串列某一特定節點的後面假設有一單向鏈結串列，按data欄位由大到小排列之。 4.1 單向鏈結串列 今有一節點ptr之data欄位值為75，欲加入到上述的串列中。首先我們必須找到插入的地方，可想而知75應插入到80和70之間，因此可用下述的片段程式執行之 4.1 單向鏈結串列 利用prev和current二個指標來追蹤，prev會緊跟在current節點之後 4.1 單向鏈結串列 接下來的動作：就是將ptr指向節點插在prev的後面 ptr-next=current; /* ? */ prev-next=ptr; /* ? */ 4.1 單向鏈結串列 4.1.2 刪除動作 刪除串列的前端節點假設有一串列如下： 4.1 單向鏈結串列 只要幾個步驟便可達成目的： p=head-next; head-next=p-next; 4.1 單向鏈結串列 free(p); 經由free(p)便可將p節點回收。 4.1 單向鏈結串列 刪除串列的最後節點：假設有一串列如下： 4.1 單向鏈結串列 此時必須先追蹤尾端及尾端的前一個 節點在那兒，步驟如下： p=head-next; 4.1 單向鏈結串列 prev-next=NULL; free(p); 4.1 單向鏈結串列 刪除某一特定的節點：刪除某一特定的節點也必須利用二個 指標current和prev，分別指到即將被 刪除節點（current）及前一節點 （prev），因此prev永遠跟著current。 假設有一單向鏈結串列如下： 4.1 單向鏈結串列 今欲刪除“Mary”因此將del_data變數指定為“Mary”，接下來利用下列程式片段就可將current指標指向“Mary”的節點，而prev指向“John”節點，並將current指向的節點回收。 4.1 單