资料结构与演算法

按一下以編輯母片標題樣式,按一下以編輯母片,第二層,第三層,第四層,第五層,*,資料結構與演算法,課程教學投影片,第九章鏈結串列,本章各段大綱,9-1 鏈結串列概觀,9-2 單一鏈結串列以陣列表示,9-3 雙向鏈結串列以陣列表示,9-4 鏈結串列用指標和結構來表示,9-5 鏈結串列應用在其它結構,9-1 鏈結串列概觀,串列的定義:串列(,list),的抽象觀念是指,一組相同資料型態元素的有序集合,。,例子如下,正奇數串列(1,3,5,7,9,)。,正偶數串列(2,4,6,8,10,)。,費伯那西數串列(1,1,2,3,5,8,)。,正質數串列(2,3,5,7,11,13,)。,大寫英文字母串列(,A,B,C,D,X,Y,Z)。,9-1 鏈結串列概觀,串列的應用,因為串列中的元素是有次序的，一般串列中元素的排列次序是由小而大，例如正整數串列的1234,有序的串列應用到電腦中的情況則有,ASC,碼,如,ABZabz,ex:,(,a)ASC,碼中,A,的下1個,B，,則第10個是什麼？,(,b)ASC,碼中,A,的號碼是65，則,Z,的號碼為多少？,解答：(,a) K (b) 90,9-1 鏈結串列概觀,鏈結串列,在資料處理或資料結構的領域中，對於一些資料(或數字)，可以利用類似箭頭的,鏈結(,link),將資料統合起來,，可以一個連到下一個，而形成有次序的資料(或數字)，則此結構稱為,鏈結串列(,linked list),。,鏈結串列定義:鏈結串列(,link list),是一種有順序的串列，且資料項應包含鏈結(,link)，,可以鏈結到其它資料。此資料項稱為,節點,節點形式,data,link,(1),樂透獎號碼的,開獎,順序,(2),由小到大順著鏈結的順序則為,32,26,24,9,5,11,9,5,11,32,26,24,9-1 鏈結串列概觀,鏈結串列有以下的特性：,鏈結串列一般可以用,陣列結構型式,來表示。,節點順序在記憶體中的實際位址可以不連續,，或者是經由隨機配置，不像陣列的元素在記憶體中的實際位址是連續的。,依鏈結的型式不同，鏈結串列分為下列幾類：,單向鏈結,：節點之間按順序，一個鏈結一個。最後沒有鏈結者，其,link,值為,Null,或特定值。,環狀鏈結,：同單向鏈結的型式，但是最後一個節點指向第1個節點。,雙向鏈結,：節點包含資料和左右兩個鏈結。,樹狀鏈結,：鏈結的型式如樹狀結構。,圖形鏈結,：鏈結的型式如圖形結構。,9-1 鏈結串列概觀,單向鏈結,節點之間按順序，一個鏈結一個。,最後沒有鏈結者，其,link,值為,Null,或特定值,。,9-1 鏈結串列概觀,環狀鏈結,同單向鏈結的型式，但是最後一個節點指向第1個節點。,9-1 鏈結串列概觀,雙向鏈結,節點包含資料和左右兩個鏈結。,9-1 鏈結串列概觀,樹狀鏈結,鏈結的型式如樹狀結構。,9-1 鏈結串列概觀,圖形鏈結,鏈結的型式如圖形結構。,9-1 鏈結串列概觀,鏈結串列的應用:,其特性是因為加入鏈結,(link),使得資料可以串起來，使其有次序性，而形成其他結構的應用，以求得更佳的演算法,加速排序速度,假如用陣列存放數值資料，且依大小排序，刪除、增加、修改資料，且需要重新排序，例如原有資料量,n,個，則由第6章排序方法得知排序演算法的時間是,O(n log n),或是,O(n2)，,而且都是針對固定的資料來排序。,但如果用鏈結串列結構來處理，則資料異動的時間只在有限次數內，時間是,O(1)，,如果加上搜尋到資料再異動時，搜尋的最差時間是,O(n)，,所以總共的異動時間為,O(mn)，,這比,O(mn2),或,O(mn log n),有效率,堆疊、佇列,可以利用鏈結串列來表示其結構。只要資料異動頻繁且要維持其定義的次序性，都適合用鏈結串列。,9-2 單一鏈結串列以,陣列,表示,鏈結陣列的宣告方式如下,#,define maxsize 100；,int A2maxsize；/,第一列存放資料,第二列存放鏈結,int head；,另外需要一個獨立的變數來存放一個陣列的起始點,-,1,代表空鏈結,data,link,A,0,1,2,30,20,50,40,10,30,20,50,40,10,4,3,30,20,50,40,10,30,20,50,40,10,0,1,2,4,1,-,1,3,2,-,1,3,2,4,3,原資料,以鏈結排序,不需調動順序,可以加快速度,鏈結陣列,課本有誤,以鏈結建立排序,9-2 單一鏈結串列以陣列表示,鏈結陣列的主要操作,:,尋找節點,目的,:,找出陣列中比搜尋數值小的最後一個位置,傳回該值所在位置的索引值,演算法說明圖,範例：,Data=35,，要找比,data,小的最後,1,個位置,3,0,1,1,30,5,50,4,20,-,1,3,2,40,60,10,0,1,1,30,5,50,4,20,-,1,3,2,40,60,10,0,1,2,4,5,6,head=0,9-2 單一鏈結串列以陣列表示,鏈結陣列的主要操作,:,尋找節點演算法說明圖,3,0,1,1,30,5,50,4,20,-,1,3,2,40,60,10,0,1,1,30,5,50,4,20,-,1,3,2,40,60,10,0,1,2,4,5,6,範例：,Data=35,，要找比,data,小的最後,1,個位置,A00=10 data,link=A10=2 ,ans,=0,(1)link=head=0,(2)link=2,A02=20 data,(2)link=2,A02=20 data,link=A12=4 ,ans,=2,(3)link=4,A04=30 data,傳回,4,head=0,9-2 單一鏈結串列以陣列表示,節點尋找的演算法如下,01,02,03,04,05,06,07,08,09,10,11,12,13,14,15,16,17,18,19,20,21,22,23,/*,演算法名稱：節點尋找的演算法,僅找尋節點,不更動結構資料,*,/,/*,輸入：要尋找的,data*/,/*,輸出：找到的值或找不到的訊息,*/,int lsearch(int data),/ 1.,假設鏈結陣列由小到大排列,要找尋比,data,小的最後一個位置,link,head;,ans=-1;,for (i,0, i,n,1, i,),/2.,建立搜尋迴圈,0n-1,搜尋順序是由節點,A1link,順序決定,if (A0link,data),/3.,若,A0linkdata,則找到答案,跳出迴圈,傳回,ans,return ans,；,/ ans,為前一筆資料的索引值,else ,anslink;,/4.,否則,代表,data,比,A0link,大或相等,/,則設定,anslink(,為此資料的索引值,), linkA1link,回步驟,2,link,A1link;,return ans;,/ 5.,已經看到最後面,沒有資料了, 沒有比,data,更大的值,/,回傳陣列最大值的索引,3,0,1,1,30,5,50,4,20,-,1,3,2,40,60,10,0,1,1,30,5,50,4,20,-,1,3,2,40,60,10,0,1,2,4,5,6,head=0,9-2 單一鏈結串列以陣列表示,新增節點演算法圖解,1,將,10,加入鏈節串列中,先找到串列中最大值,20,傳回,ans,=-1(,無任何連結節點,),，代表加入的點必須為起始點,設定此加入點的內容,A01=10,及鏈結節點值,A11,為前點,20,的索引值,0,0,0,9-2 單一鏈結串列以陣列表示,新增節點演算法圖解 2,將,40,加入鏈節串列中,40,比所有值都大，先找到串列中最大值,20,傳回前一個值,20,的索引值,0,將,20,的鏈節節點值,A10=-1,複製給將,40,的鏈節節點,A12,將,20,的鏈節節點值,A10,設定為,40,的索引值,2,0,0,0,/ ans=,0,為前一筆資料,(20),的索引值,9-2 單一鏈結串列以陣列表示,新增節點演算法圖解,3,將,30,加入鏈節串列中,30,比,20,大，先找到串列中,20,連結的下一個元素,40,的位置,傳回,20,索引值,0,將,20,的鏈節節點值,A10=2,複製給將,30,的鏈節節點,A13,將,20,的鏈節節點值,A10,設定為,30,的索引值,3,0,置入,30,後需更動的節點,9-2 單一鏈結串列以陣列表示,新增節點演算法圖解,4,將,50,加入鏈節串列中,50,比,40,大，也比所有值都大，先找到串列中,40,連結的位置,傳回,40,索引值,2,將,40,的鏈節節點值,A12=-1,複製給將,50,的鏈節節點,A14,將,40,的鏈節節點值,A12,設定為,50,的索引值,4,0,置入,50,後需更動的節點,9-2 單一鏈結串列以陣列表示,新增節點,linsert,演算法,01,02,03,04,05,06,07,08,09,10,11,12,13,14,15,16,17,18,19,20,21,22,23,/*,演算法名稱：新增節點,linsert,演算法,*/,/*,輸入：節點資料,datai,為一維陣列的資料,需將所有資料加入鏈結串列中*,/,/*,輸出：節點資料,*/,int linsert(int,data,int n),for (i,0,；,i,n,1,；,i+),/,將,datai,的所有資料依序以,lsearch(),法則,/,找到串列中適當的位置,將之插入,ANS,lsearch(datai);,if (ANS,1),/,代表此加入的值為最小值,A0i,datai;,/,將加入的值,datai,設給新加入索引值為,i,的位置,A0i,A1i,head;,/ head,代表原來最小值的索引位置,現在可以成為此加入點的鏈結節點,head,i;,/,將新加入點的索引值設為起始點,else,/,代表在串列中找到此加入值的適當位置,會傳回比此值小的最大值索引值,A1i,A1ANS;,A1ANS,i;,A0i,datai;,return ans;,3,0,1,-1,1,40,10,0,1,40,10,0,1,2,head=0,3,0,1,1,20,-1,2,40,10,0,1,20,40,10,0,1,2,head=0,i,ANS,A1ANS,A1i,A0i,9-2 單一鏈結串列以陣列表示,新增單一節點演算法,圖解 1,9-2 單一鏈結串列以陣列表示,新增單一節點演算法圖解 2,9-2 單一鏈結串列以陣列表示,新增單一節點演算法,其演算法與,linsert(),相似,讀入資料,data,用,lsearch(data,),尋找適合位置,傳回,ANS,i,為目前陣列的可用位置,如果,ANS=-1,代表此節點為新的起始點, a0i=,datai, A1i=head, head=i,如果,ANS-1,調整節點,ANS,下一個節點和新節點的關係,A1i=A1ANS,A1ANS=i,A0i=data,9-2 單一鏈結串列以陣列表示,新增單一節點,ladd( ),的演算法如下,01,02,03,04,05,06,07,08,09,10,11,12,13,14,15,16,17,18,19,20,/*,演算法名稱：新增單一節點,ladd( ),*/,/*,輸入：節點資料,*/,/*,輸出：節點資料,*/,void ladd(data, i),ANS,lsearch(data);,if (ANS,1),A0i,data;,A1i,head;,head,I;,else,A1i,A1ANS;,A1ANS,i;,A0i,data;,9-2 單一鏈結串列以陣列表示,刪除某個節點,在已建立的鏈結陣列刪除某個節點,j,並非真的刪除,而是改變原節點的被鍊結,link1(A1i),和它鏈結到別的節點的值,link2(A1j),9-2 單一鏈結串列以陣列表示,刪除根節點,9-2 單一鏈結串列以陣列表示,刪除節點 演算法圖解1,i,會紀錄欲刪除節點前一個節點的位置,9-2 單一鏈結串列以陣列表示,刪除節點 演算法圖解2,1,9-2 單一鏈結串列以陣列表示,ldelete( ),演算法 如下,01,02,03,04,05,06,07,08,09,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,/*,演算法名稱：刪除節點,ldelete(),*/,/*,輸入：節點資料,*/,/*,輸出：節點資料,*/,ldelete(data),link=head; j=,1;,for(X=0; X,=n,1; X+),if(A0link=data),j,link;,exit for;,else,i=link;,link=A1link;,if (j=-1) notfound();,else,if(j=head),/,代表起始點,head=A1j;,/,把起始點的鏈結節點當為新的起始點,A0j=Null;,else,A1i=A1j ;,A0j=Null;,i,j,範例,:,刪除,30,9-2 單一鏈結串列以陣列表示,反轉鏈結串列,將整個鏈結串列的鏈結次序設定為相反,head,指標指向鏈結串列的最後一個,原來第一個元素變成最後一個,一般節點,起始節點,最後節點,9-2 單一鏈結串列以陣列表示,反轉演算法,1.,一,般節點,的反轉,原先關係,link0,link2,link1,link1=A1link0,link2=A1link1,但其實經由反轉程序後，三個節點的關係為,#1,#1,#2,#2,#3,#3,#4,#4,link0,link2,link1,此時將,link1,連到,link0 A1link1=link0,#1,#1,#2,#2,#3,#3,#4,#4,link0,link2,link1,再把,編號關係遞迴給下三個節點,#1,#1,#2,#2,#3,#3,#4,#4,link1,link0,link2,link0 =link1,link1=link2,link2=A1link3,迴圈處理,#1,#2,#3,3,0,1,1,30,5,50,4,20,-,1,3,2,40,60,10,0,1,1,30,5,50,4,20,-,1,3,2,40,60,10,0,1,2,4,5,6,head=0,link0=0,link1=2,link2=4,link0=2, link1=4, link2=1,link0=4, link1=1, link2=3,.,link0,link1=A1link0,link2=A1link1,9-2 單一鏈結串列以陣列表示,反轉演算法,2.,起始節點,的反轉,head,link0,link2,link1,link0=head,link1=A1link0,link2=A2link1,(1),第,1,個節點指向,Null,A1link0=,-,1,(2),此時已建構出符合圖,9,-,11,的情況,link0,link2,link1,變成最後一個節點,9-2 單一鏈結串列以陣列表示,反轉演算法,3.,最後節點,的反轉,#n,-,2,#n,-,2,#n,-,1,#n,-,1,#n,#n,link0,link2,link1,因,#n,-,1,節點還是在迴圈內的一般節點處理,所以執行完,#n,-,1,節點時，情形如下圖,所以最後節點獨立處理,A1,link1,=link0,he,ad,=link1,#n,-,2,#n,-,2,#n,-,1,#n,-,1,#n,#n,link2,link1,link0,#n,#n,head,link1,link0,9-2 單一鏈結串列以陣列表示,反轉演算法的虛擬碼如下,01,02,03,04,05,06,07,08,09,10,11,12,13,14,15,16,17,18,19,20,21,/*,演算法名稱：,節點反轉,lreverse */,/*,輸入：節點資料,*/,/*,輸出：節點資料,*/,void lreverse( ),int link0, link1, link2, i,；,link0,head;,link1,A1link0;,link2,A1link1;,A1link0,1;,/,將起始點設為最後的節點,for (i,1; i,n,1; i+),/,一般節點反轉,A1link1,link0;,link0,link1;,link1,link2;,link2,A1link1;,A1link1,link0;,/,將原來最後的節點設為起始點,head,link1;,3,0,1,1,30,5,50,4,20,-,1,3,2,40,60,10,0,1,1,30,5,50,4,20,-,1,3,2,40,60,10,0,1,2,4,5,6,head=0,link0,link1=A1link0,link2=A1link1,9-2 單一鏈結串列以陣列表示,鏈結陣列以多個一維陣列處理:本節所介紹的鏈結陣列都是以二維陣列來處理，如果存放的資料是整數時，可用這方式來處理較方便，但如果存放的資料是文字時，我們也提過要分開宣告資料和鏈結,9-3 雙向鏈結串列以陣列表示,單向鏈結串列以單方向找到下一個節點,但要知道前一個節點的資料,需要在搜尋過程中記錄此資料,否則無法知道前一個節點的資料,雙向鏈結串列(,doubly linked list),則是一個節點有二個鏈結，其中一個如單一鏈結串列的指向下一個之鏈結，另一個則指向前一個節點的鏈結，一般以,prev,和,next,分別代表向前鏈結、向後鏈結，其結構以陣列方式宣告如下：,#,define maxsize 100；,int Amaxsize,3,；,/,分別記錄此節點內容,上一個節點,及 下一個節點的位置,9-3 雙向鏈結串列以陣列表示,雙向鏈結串列圖示,一般,row0,放資料, row1,放向後鏈結, row2,放向前鏈結,始端變數,head,及尾端變數,tail,設定從頭或從尾的資料操作,3,0,1,2,4,data,next,prev,圖形表示,data,prev,next,data,prev,next,環狀雙向鍵結,雙向鏈結,Null,Null,9-3 雙向鏈結串列以陣列表示,應用,單向鏈結串列,一般是從頭或某一節點開始,往後尋找,雙向鏈結,則可以,往前和往後,尋找,以鏈結串列應用在排序資料為例，單向鏈結可以找出比某數值大的所有資料(原資料由小到大排序)，但當我們要搜尋某數值附近的資料，例如某數值及比它大的2個數值和比它少的2個數值，則可以應用雙向鏈結串列找到某值時，往前讀取2個數值，往後讀取2個數值。,而且因為有始端,head,和尾端,tail,變數知道資料最小和最大位置，所以可以隨時取出最大值(較大值)或最小值(較小值)等。雙向鏈結串列的操作方式和單向鏈結串列方式類似，也是可分為尋找節點、新增節點、刪除節點來討論。,9-3 雙向鏈結串列以陣列表示,雙向鏈結串列搜尋節點,可分為往前尋找法及往後尋找法（與單向鏈結相同）,現在所在位置的索引值,往前尋找法圖解,9-3 雙向鏈結串列以陣列表示,dlpsearch( ),演算法,01,02,03,04,05,06,07,08,09,10,11,12,13,14,15,16,17,18,/*,演算法名稱：雙向鏈結串列搜尋節點,dlpsearch,*/,/*,輸入：節點資料,*/,/*,輸出：節點資料,*/,int dlpsearch(data),plink,tail;,for (i=0,；,in-1,；,i+),if(A0plink,由,dlpsearch(35),傳回,ANS=3(,假設,next=1,，,prev,=2),，,目前,i=5,30,30,40,40,2,3,x,30,5,30,5,35,3,2,35,3,2,40,40,(4),(3),(2)y,(1)x,2,3,30,2,30,2,40,3,40,3,2,3,x,30,5,30,5,35,3,2,35,3,2,40,5,40,5,(1)x,(2) y,z,z,2,3,y,5,所以錄結陣列為,3,35,50,30,40,10,20,2,-,1,2,4,0,3,1,3,2,0,3,-,1,35,50,30,40,10,20,2,-,1,2,4,0,3,1,3,2,0,3,-,1,0,1,2,4,5,head=1,tail=4,(1)Anexti=AnextANS,A15=A13=2,(2)AprevAi=,Aprev,AnextANS,A2,5,=3,(3)AnextANS=i,A13=5,(4)Aprev,A1ANS,=5,A22=5,(5)A0i=35,雙向鏈結新增節點圖解說明,next=1,prev=2,新加入數值之索引值,比加入數值小的最大值（,30,）索引值,需要修正的鏈結資料,2,3,由,30,的,next,節點找到,40,的索引值,先修正新加入節點的鏈結資料,再修正其前後節點的鏈結資料,9-3 雙向鏈結串列以陣列表示,雙向鏈結新增單一節點的演算式,dlpadd( ),如下,01,02,03,04,05,06,07,08,09,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,/*,演算法名稱：雙向鏈結新增單一節點的演算式,dlpadd( ),*/,/*,輸入：節點資料,*/,/*,輸出：節點資料,*/,void dlpsearch(data, i),int ANS;,int next=1,prev=2;,ANS=dlpsearch(data);,if (ANS=-1),/,最後一個節點,A0i=data,；,Aprevi=tail,；,Anexti=-1,；,A1tail=i,；,tail=i,；,else,Anexti=AnextANS;,Aprevi=Aprev AnextANS ;,AnextANS=i;,Aprev A1ANS =i;,A0i=data;,9-3 雙向鏈結串列以陣列表示,雙向鏈結,刪除一般節點圖解說明,j,i,k,y,x,x,=Anextj,y,=,Aprevj,x,i,y,k,刪除,j,因為是找到,j,，所以,i=,Aprevj,，,k=,Anextj,(1),建立,x,於,i,Anext,Aprevj,=Anextj,(2),建立,y,於,k,Aprev,Anextj,=,Aprevj,(,也就是,Anext,i, ),(,也就是,Apre,k, ),雙向鏈結,刪除前端尾端節點圖解,成為新的,head,成為新的,tail,k,head,j,z,Null,刪除,j,k,head,Null,z,刪除尾端節點,Null,tail,刪除尾端節點,Null,tail,k,z,k,z,j,因為是找到,j,k=Anextj,因為,z,=Anextj,所以,head=Anextj,AprevAnextj,=,-,1,因為是找到,j,，,所以,j,=Anext,k,因為,z,=,Aprevj,所以,tail=,Aprevj,(,也就是,Anextk),AnextAprevj,=,-,1,dldelete( ),演算法的圖解說明,3,2,1,0,50,30,40,10,20,-,1,2,4,0,3,1,2,0,3,-,1,2,1,0,50,30,40,10,20,-,1,2,4,0,3,1,2,0,3,-,1,0,1,2,4,data,next,prev,5,6,10,10,30,30,20,20,0,1,3,head=,1,tail=4,40,40,2,50,50,4,head,tail,第一個節點,最後節點,一般節點,(3),再刪除,30,，因為找到,j,，,所以,i=,Aprevj,=A23=0,k=Anextj=A13=2,建立,x,於,i,AnextAprevj,=Anextj,A10=A13=2,建立,y,於,k,AprevAnextj,=,Aprevj,A22=A23=0,3,2,1,0,50,30,40,10,20,-,1,2,-1,0,3,-1,2,0,3,-,1,2,1,0,30,40,20,2,3,0,3,0,1,2,4,5,6,20,20,0,30,30,3,40,40,2,i,j,k,y,x,(2),刪除,50,，因為找到,j,，,j=4,，,所以,k=,Aprevj,=A24=2,tail=,Aprevj,=A24=2,AnextAprevj,=A12=,-,1,3,2,1,0,50,30,40,10,20,-,1,2,4,0,3,-1,2,0,3,-,1,2,1,0,50,30,40,20,-,1,2,4,3,2,0,3,0,1,2,4,5,6,head=0,tail=2,40,40,2,50,50,tail,k,9-4 鏈結串列用指標和結構來表示,鏈結串列用陣列表示的問題:,用陣列來表示鏈結串列，因為陣列有註標可直接存取陣列中的資料，但是當你宣告的陣列太小時，可能程式運作中會碰到無空間可放資料的已滿情況；或者宣告太大時，當程式並不會用到那麼多空間時，又會浪費空間，你或許會說：現在的記憶體空間，差不多是28,MB，256MB，,浪費一點點空間有何關係。,但是在設計程式時要考慮其移植性，即由個人電腦的作業環境移植到隨身和行動設備等只有少量資源的環境時，記憶體空間的計較就成為很重要的課題了。,要解決固定陣列宣告所造成的不便時，一般有兩種方法可克服：,使用動態陣列：不要宣告陣列大小，只要宣告型態,使用指標和結構：利用結構定義資料和指標，利用類似(,struct node *)malloc(sizeof(node),的函式，當需要存放空間時，再從記憶體取得。,9-4 鏈結串列用指標和結構來表示,結構宣告和使用,9-4 鏈結串列用指標和結構來表示,如果定義了結構，也可以使用陣列變數來使用結構，例如宣告一個有100筆資料的,stu-struct,時，其宣告方式為：,xrecord my_record100；,則將成績,yscore,放入第,i,個結構陣列中時，其陳述句如下：,my_recordistu_scoreyscore；,9-4 鏈結串列用指標和結構來表示,鏈結串列之結構宣告,9-4 鏈結串列用指標和結構來表示,需要置配記憶體空間時，要引入標頭檔等,和,malloc,函式，如下：,include ,.,head(LINKLIST ) malloc(sizeof(LINKLIST)；,if(head=NULL) /*,在這邊要確認是否有要到合法的記憶體 */,Do Error Handling; /*,如果指標指向,NULL,表示現在記憶體不足 */,else,nodehead； /node,和,head,可指向同一位置/,9-4 鏈結串列用指標和結構來表示,當刪除節點時，要將記憶體空間釋放，否則那些空間將會無法使用而浪費，可在程式中使用,free( ),函式，如下：,free(node)；,鏈結串列用指標結構建立3個節點,圖解1,鏈結串列用指標結構建立3個節點,圖解2,鏈結串列用指標結構建立3個節點,圖解3,9-4 鏈結串列用指標和結構來表示,01,02,03,04,05,06,07,08,09,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,/*,演算法名稱,:,建立鏈結演算法,*/,/*,輸,入,:,節點資料,*/,/*,輸,出,:,鏈結串列,*/,include ,typedef struct str_link,int data,；,struct str_link,next,LINKLIST,void main( ),int A A100,；,int i, count,；,LINKLIST,head,node,newnode,；,A0,10,；,A1,20, A3,30,；,count,3 /,假設有,3,個資料要建立鏈,結串列,/,/,建立第,1,個節點,/,node,(LINKLIST,)malloc(sizeof(LINKLIST),；,head,node,；,Node-data,A0,；,Node-next,NULL,；,for(i,1,；,i,count,；,i,),newnode,(LINKLIST,)malloc(sizeof(LINKLIST),；,node,next,newnode,；,newnode,data,Ai,；,newnode,next,NULL,；,node,newnode,；,走訪節點:由範例可以知道要鏈結下一個節點時，只要用,node-next，,要存取節點資料則用,node-data，,要將節點,node,移到它鏈結的節點則用,nodenode-next，,某節點要移到起始節點時，則用,nodehead。,9-5 鏈結串列應用在其它結構,鏈結堆疊,鏈結堆疊和堆疊一樣有一個,top,指標用來指示頂端位置，其節點結構一樣是資料鏈結，而且一樣只能從頂端加入或刪除節點。所以其實鏈結堆疊可以說是鏈結串列的有限功能(鏈結串列可對任意節點進行新增和刪除功能)，其結構定義如下：,typedef struct str_linkstack,int data；,struct str_linkstack next；,LINKSTACK,LINKSTACK top, newnode, node；,鏈結堆疊鏈結堆疊的,push,動作之函式,lspush( ),的圖解說明如下。,鏈結堆疊,push,動作:,lspop( ),在,pop,資料時，需檢查是否,top=NULL，,檢查堆疊是否已經空了，如困未空再將,top,指標指到下一個節點，且釋放掉目前的節點，其圖解說明如下。,9-5 鏈結串列應用在其它結構,01,02,03,04,05,06,07,08,09,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,/*,演算法名稱：,lspush( ),和,lspop( ),演算法,*/,/*,輸入：節點資料,*/,/*,輸出：節點資料,*/,typedef struct str_linkstack,int data,；,struct str_linkstack *next,；,LINKSTACK,LINKSTACK *top, *node, *newnode,；,Void lspush(int xdata),newnode=(LINKSTACK *) malloc(sizeof(LINKSTACK),；,newnode-data=xdata,；,newnode-next=top,；,top=newnode,；,int lspop( ),if (top=NULL),lsempty( ),；,return-1,；,else,node=top,；,xdata=top,data,；,top=top,next,；,free(node),；,return xdata,；,9-5 鏈結串列應用在其它結構,鏈結佇列(,linked queue),同樣是以鏈結串列來表示佇列，在了解上一小節用鏈結指標處理鏈結堆疊後，此部份鏈結佇列的,lqadd( )(,從尾端,rear,加入節點)，,lqdel( )(,從前端,front,刪除節點)的動作和鏈結堆疊的,lspush( ),和,lspop( ),相類似，如下圖。,9-5 鏈結串列應用在其它結構,鏈結佇列可也以看成是鏈結串列的有限功能，它只能在固定的前端(,front),和後端(,rear),加入或刪除節點，但檢查佇列是否已空時，不是先前介紹的檢查,front,和,rear,的關係：,front = rear-1,而是檢查,front,的指標是否指到,NULL。,另外當佇列是空的時候，加入第一個節點時,front,和,rear,設定為相同指標位置，之後,front,和,rear,即可個別動作了。,鏈結佇列的結構定義如下：,typedef struct str_linkgueue,int data；,struct str_linkgueue next；,LINKQUEUE,LINKQUEUE front, rear, newnode, node；,9-5 鏈結串列應用在其它結構,鏈結佇列加入節點之函式,lqadd( ),的圖解1,9-5 鏈結串列應用在其它結構,鏈結佇列加入節點之函式,lqadd( ),的圖解2,9-5 鏈結串列應用在其它結構,鏈結佇列要刪除節點時，要先檢查佇列是否是空了，如困未空，則只要將,front,指標指到下一個節點，且釋放原節點，其圖解說明如下,9-5 鏈結串列應用在其它結構,鏈結佇列要刪除節點圖解2,01,02,03,04,05,06,07,08,09,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,/*,演算法名稱：鏈結佇列刪除節點,*/,/*,輸入：節點資料,*/,/*,輸出：節點資料,*/,typedef struct str_linkqueue,int data,；,struct str_linkqueue *next,；,LINKQUEUE,LINKQUEUE *front, *rear, *node, *newnode,；,void lqadd(int xdata),newnode=(LINKQUEUE *) maloc(sizeof(LINKQUEUE),；,if(rear=NULL),rear=newnode,；,front=rear,；,else,rear-next=newnode,；,rear=newnode,；,rear-next,NULL,；,rear-data,xdata,；,int lqdel( ),if (front=NULL),lqempty(),；,return-1,；,else,node=front,xdata=front-data,front=front-next,free(node),；,9-5 鏈結串列應用在其它結構,鏈結串列可以說是陣列表示法的另一種替代方案，只要你熟練結構和指標的應用，它也是一種簡單的資料表示方法，且可隨機配置記憶體空間，不會受限於陣列大小的宣告,在第11章樹狀結構中，同樣可以用陣列或鏈結串列兩種方式來表示,鏈結樹的表示方式如下,