利用链结串列linkedlist课件

DataStructureinC

─鏈結串列0DataStructureinC

大綱單向鏈結串列環狀串列雙向鏈結串列鏈結串列的應用1大綱單向鏈結串列1鏈結串列以陣列方式存放資料，若要插入(insert)或刪除(delete)某一節點(node)就備感困難Ex.陣列中已有a,b,d,e四個元素，若要將c插入d,e需往後一格Ex.陣列中已有a,b,d,e四個元素，若要將d刪除為不浪費空間需挪移元素利用鏈結串列(linkedlist)解決問題2鏈結串列以陣列方式存放資料，若要插入(insert)或刪除(鏈結串列(續)陣列vs.鏈結陣列3鏈結串列(續)陣列vs.鏈結陣列3單向鏈結串列單向鏈結串列(singlelinkedlist)若單向串列中的每個節點(node)的資料結構有兩個欄位，分別為資料欄(data)及鏈結欄(next)，，若將節點定義為struct型態，為

structnode{intdata;structnode*next;};structnode*head=NULL,*tail,*this,*prev,*x,*p,*ptr;4單向鏈結串列單向鏈結串列(singlelinkedli單向鏈結串列(續)Ex.串列A={a,b,c,d,e}，以鏈結串列表示為指向串列前端的指標指向串列尾端的指標5單向鏈結串列(續)Ex.串列A={a,b,c,d,單向鏈結串列(續)單向鏈結串列的加入動作加入於串列的前端加入於串列的尾端加入在串列某一特定節點後面6單向鏈結串列(續)單向鏈結串列的加入動作6Step1:x=(structnode*)malloc(sizeof(structnode));x->next=NULL;加入於串列的前端Step2:x->next=head;7Step1:x=(structnode*)maStep3:head=x;加入於串列的尾端Step1:x=(structnode*)malloc(sizeof(structnode));x->next=NULL;8Step3:head=x;加入於串列的尾端StepStep2:tail->next=x;Step3:tail=x;若未用tail指標，則每次都必須要追蹤串列的尾端9Step2:tail->next=x;Step3:Step1:x=(structnode*)malloc(sizeof(structnode));x->next=NULL;加入在串列某一特定節點後面Assumption:將一個節點x加在ptr所指節點後面Step2:x->next=ptr->next;10Step1:x=(structnode*)maStep3:ptr->next=x;11Step3:ptr->next=x;11voidinsert_node(structnode*ptr,structnode*head,structnode*tail){ structnode*thisif(head==NULL)/*插入資料為第一筆*/ {ptr->next=NULL; head=ptr; tail=ptr;} else { this=head; if(ptr->key>this->key)/*插入位置為前端*/ { ptr->next=this; head=ptr; }

12voidinsert_node(structnode* else {while(this->next!=NULL) { prev=this; this=this->next; if(ptr->key>this->key)/*插入位置於中間*/ { ptr->next=this; prev->next=ptr; break; } } if(ptr->key<=this->score)/*插入資料於尾端*/ { ptr->next=NULL; this->next=ptr; tail=ptr; } } }}13 else13單向鏈結串列(續)單向鏈結串列的刪除動作刪除串列前端的節點刪除串列尾端的節點刪除串列某一特定節點14單向鏈結串列(續)單向鏈結串列的刪除動作14Step1:ptr=head;刪除串列前端的節點Step2:head=ptr->next;Step3:free(ptr);15Step1:ptr=head;刪除串列前端的節點St刪除串列尾端的節點Step1:必須先追蹤tail的前一個節點ptr=head;while(ptr->next!=tail)ptr=ptr->next;Step2:ptr->next=NULL;Step3:free(tail);Step4:tail=ptr;16刪除串列尾端的節點Step1:必須先追蹤tail的前一個節刪除串列某一特定節點Step1:尋找所要刪除的節點，並設定兩指標this及prev即將被刪除節點即將被刪除的前一節點while(this->next!=NULL)prev=this;this=this->next;17刪除串列某一特定節點Step1:尋找所要刪除的節點，並設定Step2:prev->next=this->next;Step3:free(this);18Step2:prev->next=this->nexvoiddelete_f(intdel_key,structnode*head,structnode*tail){ structnode*clear,*this,*prev; this=head; if(del_key==head->key){/*刪除資料於前端*/

clear=this; if(head->next==NULL)/*資料僅存在一筆*/

tail=NULL; head=head->next; free(clear); } while(this->next!=NULL){/*刪除資料於中間*/

prev=this; this=this->next; if(del_key==this->key){ clear=this; prev->next=this->next; free(clear); } } if(del_key==tail->key){/*刪除資料於尾端*/ clear=this; prev->next=NULL; tail=prev; free(clear); }19voiddelete_f(intdel_key,str單向鏈結串列(續)將兩串列相接三種情況x串列為NULL，y串列有資料x串列有資料，y串列為NULLx串列與y串列都有資料20單向鏈結串列(續)將兩串列相接20voidconcatenate(structnode*x,structnode*y,structnode*y){structnode*c;if(x==NULL)z=y;elseif(y==NULL)z=x;else{z=x;c=x;while(c->next!=NULL)c=c->next;c->next=y;}}21voidconcatenate(structnode將一串列反轉串列的反轉是將原先的串列首變成串列尾Ex.若一串列原先以小排到大，此時若想由大到小排列voidinvert(structnode*head){structnode*this,*prev,*next_n;next_n=head;this=NULL;while(next_n!=NULL){prev=this;this=next_n;next_n=next->next;this->next=prev;}tail=head;head=this;}22將一串列反轉22單向鏈結串列(續)計算串列的長度串列長度指的是此串列共有多少個節點，計算上只要指標指到的為NULL，則利用一變數做累加，直到指標指到NULL為止intlength(structnode*head){structnode*this;this=head;intleng=0;while(this!=NULL){leng++’this=this->next;}returnleng;}23單向鏈結串列(續)計算串列的長度23環狀串列假若將鏈結串列最後一個節點的指標指向第一個節點時，此串列稱為環狀串列(circularlist)可以由任一點來追蹤所有節點，而不必區分那一個是第一個節點24環狀串列假若將鏈結串列最後一個節點的指標指向第一個節點時，此環狀串列(續)環狀串列的加入動作加入於串列的前端若串列為空串列(NULL)若串列不為空串列加入於串列的尾端加入在串列某一特定節點後面25環狀串列(續)環狀串列的加入動作25

Step1:head=x;tail=x;加入於串列的前端─串列為空串列Step2:x->next=x;Step1:x->next=head;加入於串列的前端─串列不為空串列26 Step1:head=x;tail=x;加入於串Step2:tail->next=x;Step3:head=x;27Step2:tail->next=x;Step3:加入於串列的尾端Step1:tail->next=x;Step2:x->next=head;Step3:tail=x;28加入於串列的尾端Step1:tail->next=xvoidinsert_node(structnode*ptr,structnode*head,structnode*tail){ structnode*prev,*this; if(head==NULL){/*插入資料為第一筆*/

ptr->next=ptr; head=ptr; tail=ptr; } else { this=head; if(ptr->key<this->key){/*插入位置為前端*/

ptr->next=this; head=ptr; tail->next=head; } else{ while(this->next!=head) { prev=this; this=this->next;

29voidinsert_node(structnode* if(ptr->key<this->key){/*插入位置於中間*/

ptr->next=this; prev->next=ptr; break; } }if(ptr->key>=this->key){/*插入資料於尾端*/

ptr->next=head; this->next=ptr; tail=ptr; } } }}30 if(ptr->key<this->key){環狀串列(續)環狀串列的刪除動作刪除串列前端的節點刪除串列尾端的節點刪除串列某一特定節點31環狀串列(續)環狀串列的刪除動作31Step1:tail->next=head->next;刪除串列前端的節點Step2:ptr=head;head=head->next;Step3:free(ptr);32Step1:tail->next=head->nex刪除串列尾端的節點Step1:必須先追蹤tail的前一個節點Step2:ptr->next=hear;Step3:free(tail);tail=ptr;ptr=head;while(ptr->next!=tail)ptr=ptr->next;33刪除串列尾端的節點Step1:必須先追蹤tail的前一個voiddelete_node(intdel_key,structnode*head,structnode*tail){ structnode*clear,*prev,*this; this=head; if(del_key==head->key){/*刪除資料於前端*/

clear=head; if(head->next==head)/*資料僅存在一筆*/ {head=NULL; tail=NULL;} else { head=head->next; tail->next=head; } }34voiddelete_node(intdel_key, while(this->next!=head&&head!=NULL)/*刪除資料於中間*/ { prev=this; this=this->next; if(del_key==,this->key) { clear=this; prev->next=this->next; tail=prev; } } if(del_key==tail->key){/*刪除資料於尾端*/ clear=tail; prev->next=head; tail=prev; } free(clear);}35 while(this->next!=head&&Step1:Atail->next=Bhead;Step2:Btail->next=Ahead;將兩串列相接36Step1:Atail->next=Bhead;St雙向鏈結串列雙向鏈結串列(doublylinkedlist)每個節點有三個欄位，一為左鏈結(LLink)，二為資料(Data)，三為右鏈結(RLink)特點：假設ptr是任何節點的指標，則

ptr=ptr->llink->rlink=ptr->rlink->llink;若此雙向鏈結串列是空串列，則只有一個串列首37雙向鏈結串列雙向鏈結串列(doublylinkedlis雙向鏈結串列(續)優點：加入或刪除時，無需知道其前一節點的位址可以從任一節點找到其前一節點或後一節點可以將某一節點遺失的左或右指標適時地加以恢復之缺點：增加一個指標空間加入時需改變四個指標(單向只需改變兩個指標)刪除時需改變兩個指標(單向只要改變一個指標)38雙向鏈結串列(續)優點：38雙向鏈結串列(續)雙向鏈結串列的加入動作加入於串列的前端加入於串列的尾端加入在串列某一特定節點後面假設head節點不放任何資料voidinit_head(structnode*ptr,structnode*head,structnode*tail){ ptr=(structnode*)malloc(sizeof(structnode)); ptr->key=NULL; ptr->llink=ptr; ptr->rlink=ptr; head=ptr; tail=ptr;}39雙向鏈結串列(續)雙向鏈結串列的加入動作假設head節點不Step1:x->rlink=head;加入於串列的前端Step2:x->llink=tail;Step3:tail->rlink=x;40Step1:x->rlink=head;加入於串列的Step4:head->rlink=x;Step5:tail=x;41Step4:head->rlink=x;Step5加入於串列的尾端Step1:x->rlink=tail->rlink;Assumption:假設有一串列如下Step2:tail->rlink=x;42加入於串列的尾端Step1:x->rlink=taiStep3:x->llink=tail;Step4:head->llink=x;Step5:tail=x;43Step3:x->llink=tail;Step4雙向鏈結串列(續)加入在串列某一特定節點後面必須先搜尋到某特定的節點，並假設此串列是以key由小而大建立的，而搜尋步驟如下：

prev=head;ptr=head->rlink;while(ptr!=head&&x->key<p->key){ prev=ptr; ptr=ptr->rlink;}44雙向鏈結串列(續)加入在串列某一特定節點後面44voidinsert_node(structnode*ptr,structnode*head,structnode*tail){ structnode*this; this=head->rlink; while(this!=head) { if(ptr->key<this->key){/*插入位置為中間*/

ptr->rlink=this; ptr->llink=this->llink; this->llink->rlink=ptr; this->llink=ptr; break; } this=this->rlink; } /*插入位置為尾端*/

if(head->rlink==head||this==head) { ptr->rlink=head; ptr->llink=head->llink; head->llink->rlink=ptr; head->llink=ptr; tail=ptr;}}45voidinsert_node(structnode*雙向鏈結串列(續)雙向鏈結串列的刪除動作刪除串列前端的節點刪除串列尾端的節點刪除串列某一特定節點46雙向鏈結串列(續)雙向鏈結串列的刪除動作46Step1:ptr=head->rlink;刪除串列前端的節點Step2:head->rlink=ptr->rlink;Step3:p->rlink->llink=p->llink;Step4:free(ptr);47Step1:ptr=head->rlink;刪除串列刪除串列尾端的節點Step1:tail->llink->rlink=head;Step2:head->llink=tail->llink;Step5:free(ptr);Step3:ptr=tail;Step4:tail=tail->llink;48刪除串列尾端的節點Step1:tail->llink->刪除串列某一特定節點Assumption:假設欲刪除this所指的節點Step1:this->llink->rlink=this->rlink;Step2:this->rlink->llink=this->llink;Step3:free(this);49刪除串列某一特定節點Assumption:假設欲刪除thivoiddelete_node(intdel_key,structnode*head,structnode*tail){ structnode*clear,*this; this=head->rlink; while(this!=head){ /*刪除資料於中間*/

if(del_key==this->key) { clear=this; this->llink->rlink=this->rlink; this->rlink->llink=this->llink; if(this==tail) tail=this->llink; break; } this=this->rlink; } free(clear);}50voiddelete_node(intdel_key,鏈結串列的應用以鏈結串列表示堆疊以鏈結串列表示佇列以鏈結串列表示多項式相加51鏈結串列的應用以鏈結串列表示堆疊51鏈結串列的應用(續)以鏈結串列表示堆疊將堆疊內的資料視為單向鏈結串列中的資料項Push:視為將節點加入串列的前端Pop:視為刪除前端的節點52鏈結串列的應用(續)以鏈結串列表示堆疊52鏈結串列的應用(續)以鏈結串列表示堆疊─Pushvoidpush_stack(intdata,structnode*ptr,structnode*top){ptr=(structnode*)malloc(sizeof(structnode));ptr->item=data;ptr->next=top;top=ptr;}53鏈結串列的應用(續)以鏈結串列表示堆疊─Push53鏈結串列的應用(續)以鏈結串列表示堆疊─Popvoidpop_stack(intdata,structnode*top){structnode*clearif(top==NULL) printf(“stack-empty”);clear=top;data=top->item;top=top->next;free(clear);}54鏈結串列的應用(續)以鏈結串列表示堆疊─Pop54鏈結串列的應用(續)以鏈結串列表示佇列將佇列內的資料視為單向鏈結串列中的資料項Enqueue:視為將節點加入串列的尾端Dequeue:視為刪除前端的節點由此處開始刪除由此處開始加入55鏈結串列的應用(續)以鏈結串列表示佇列由此處開始刪除由此處鏈結串列的應用(續)以鏈結串列表示佇列─Enqueuevoidenqueue(intdata,structnode*front,structnode*rear){ptr=(structnode*)malloc(sizeof(structnode));ptr->item=data;ptr->next=NULL;if(rear==NULL) front=rear=ptr;else rear->next=ptr;rear=ptr;}56鏈結串列的應用(續)以鏈結串列表示佇列─Enqueue鏈結串列的應用(續)以鏈結串列表示佇列─Dequeuevoiddequeue(intdata,structnode*front){structnode*clearif(front==NULL) printf(“stack-empty”);data=front->item;clear=front;front=front->next;free(clear);}57鏈結串列的應用(續)以鏈結串列表示佇列─Dequeue鏈結串列的應用(續)以鏈結串列表示多項式相加多項式相加可以用鏈結串列完成，其資料結構為Coef表示變數的係數Exp表示變數的指數Link為指下一節點的指標原理(若有A、B兩多項式)Exp(A)=Exp(B)Exp(A)>Exp(B)Exp(A)<Exp(B)58鏈結串列的應用(續)以鏈結串列表示多項式相加58voidpoly_add(void){ structpoly*this_n1,*this_n2,*prev; this_n1=eq_h1; this_n2=eq_h2; prev=NULL; while(this_n1!=NULL||this_n2!=NULL)/*當兩個多項式皆相加完畢則結束*/ {

ptr=(structpoly*)malloc(sizeof(structpoly)); ptr->next=NULL; /*第一個多項式指數大於第二個多項式*/

if(this_n1!=NULL&&(this_n2==NULL||this_n1->exp>this_n2->exp)) { ptr->coef=this_n1->coef; ptr->exp=this_n1->exp; this_n1=this_n1->next; }

59voidpoly_add(void)59 else /*第一個多項式指數小於第二個多項式*/

if(this_n1==NULL||this_n1->exp<this_n2->exp) { ptr->coef=this_n2->coef; ptr->exp=this_n2->exp; this_n2=this_n2->next; } else/*兩個多項式指數相等，進行相加*/ {

ptr->coef=this_n1->coef+this_n2->coef; ptr->exp=this_n1->exp; if(this_n1!=NULL)this_n1=this_n1->next; if(this_n2!=NULL)this_n2=this_n2->next; }

60 else60 if(ptr->coef!=0)/*當相加結果不等於0，則放入答案多項式中*/ {

if(ans_h==NULL)ans_h=ptr; elseprev->next=ptr; prev=ptr; } elsefree(ptr); }}61 if(ptr->coef!=0)/*當相加結果不DataStructureinC

─鏈結串列62DataStructureinC

大綱單向鏈結串列環狀串列雙向鏈結串列鏈結串列的應用63大綱單向鏈結串列1鏈結串列以陣列方式存放資料，若要插入(insert)或刪除(delete)某一節點(node)就備感困難Ex.陣列中已有a,b,d,e四個元素，若要將c插入d,e需往後一格Ex.陣列中已有a,b,d,e四個元素，若要將d刪除為不浪費空間需挪移元素利用鏈結串列(linkedlist)解決問題64鏈結串列以陣列方式存放資料，若要插入(insert)或刪除(鏈結串列(續)陣列vs.鏈結陣列65鏈結串列(續)陣列vs.鏈結陣列3單向鏈結串列單向鏈結串列(singlelinkedlist)若單向串列中的每個節點(node)的資料結構有兩個欄位，分別為資料欄(data)及鏈結欄(next)，，若將節點定義為struct型態，為

structnode{intdata;structnode*next;};structnode*head=NULL,*tail,*this,*prev,*x,*p,*ptr;66單向鏈結串列單向鏈結串列(singlelinkedli單向鏈結串列(續)Ex.串列A={a,b,c,d,e}，以鏈結串列表示為指向串列前端的指標指向串列尾端的指標67單向鏈結串列(續)Ex.串列A={a,b,c,d,單向鏈結串列(續)單向鏈結串列的加入動作加入於串列的前端加入於串列的尾端加入在串列某一特定節點後面68單向鏈結串列(續)單向鏈結串列的加入動作6Step1:x=(structnode*)malloc(sizeof(structnode));x->next=NULL;加入於串列的前端Step2:x->next=head;69Step1:x=(structnode*)maStep3:head=x;加入於串列的尾端Step1:x=(structnode*)malloc(sizeof(structnode));x->next=NULL;70Step3:head=x;加入於串列的尾端StepStep2:tail->next=x;Step3:tail=x;若未用tail指標，則每次都必須要追蹤串列的尾端71Step2:tail->next=x;Step3:Step1:x=(structnode*)malloc(sizeof(structnode));x->next=NULL;加入在串列某一特定節點後面Assumption:將一個節點x加在ptr所指節點後面Step2:x->next=ptr->next;72Step1:x=(structnode*)maStep3:ptr->next=x;73Step3:ptr->next=x;11voidinsert_node(structnode*ptr,structnode*head,structnode*tail){ structnode*thisif(head==NULL)/*插入資料為第一筆*/ {ptr->next=NULL; head=ptr; tail=ptr;} else { this=head; if(ptr->key>this->key)/*插入位置為前端*/ { ptr->next=this; head=ptr; }

74voidinsert_node(structnode* else {while(this->next!=NULL) { prev=this; this=this->next; if(ptr->key>this->key)/*插入位置於中間*/ { ptr->next=this; prev->next=ptr; break; } } if(ptr->key<=this->score)/*插入資料於尾端*/ { ptr->next=NULL; this->next=ptr; tail=ptr; } } }}75 else13單向鏈結串列(續)單向鏈結串列的刪除動作刪除串列前端的節點刪除串列尾端的節點刪除串列某一特定節點76單向鏈結串列(續)單向鏈結串列的刪除動作14Step1:ptr=head;刪除串列前端的節點Step2:head=ptr->next;Step3:free(ptr);77Step1:ptr=head;刪除串列前端的節點St刪除串列尾端的節點Step1:必須先追蹤tail的前一個節點ptr=head;while(ptr->next!=tail)ptr=ptr->next;Step2:ptr->next=NULL;Step3:free(tail);Step4:tail=ptr;78刪除串列尾端的節點Step1:必須先追蹤tail的前一個節刪除串列某一特定節點Step1:尋找所要刪除的節點，並設定兩指標this及prev即將被刪除節點即將被刪除的前一節點while(this->next!=NULL)prev=this;this=this->next;79刪除串列某一特定節點Step1:尋找所要刪除的節點，並設定Step2:prev->next=this->next;Step3:free(this);80Step2:prev->next=this->nexvoiddelete_f(intdel_key,structnode*head,structnode*tail){ structnode*clear,*this,*prev; this=head; if(del_key==head->key){/*刪除資料於前端*/

clear=this; if(head->next==NULL)/*資料僅存在一筆*/

tail=NULL; head=head->next; free(clear); } while(this->next!=NULL){/*刪除資料於中間*/

prev=this; this=this->next; if(del_key==this->key){ clear=this; prev->next=this->next; free(clear); } } if(del_key==tail->key){/*刪除資料於尾端*/ clear=this; prev->next=NULL; tail=prev; free(clear); }81voiddelete_f(intdel_key,str單向鏈結串列(續)將兩串列相接三種情況x串列為NULL，y串列有資料x串列有資料，y串列為NULLx串列與y串列都有資料82單向鏈結串列(續)將兩串列相接20voidconcatenate(structnode*x,structnode*y,structnode*y){structnode*c;if(x==NULL)z=y;elseif(y==NULL)z=x;else{z=x;c=x;while(c->next!=NULL)c=c->next;c->next=y;}}83voidconcatenate(structnode將一串列反轉串列的反轉是將原先的串列首變成串列尾Ex.若一串列原先以小排到大，此時若想由大到小排列voidinvert(structnode*head){structnode*this,*prev,*next_n;next_n=head;this=NULL;while(next_n!=NULL){prev=this;this=next_n;next_n=next->next;this->next=prev;}tail=head;head=this;}84將一串列反轉22單向鏈結串列(續)計算串列的長度串列長度指的是此串列共有多少個節點，計算上只要指標指到的為NULL，則利用一變數做累加，直到指標指到NULL為止intlength(structnode*head){structnode*this;this=head;intleng=0;while(this!=NULL){leng++’this=this->next;}returnleng;}85單向鏈結串列(續)計算串列的長度23環狀串列假若將鏈結串列最後一個節點的指標指向第一個節點時，此串列稱為環狀串列(circularlist)可以由任一點來追蹤所有節點，而不必區分那一個是第一個節點86環狀串列假若將鏈結串列最後一個節點的指標指向第一個節點時，此環狀串列(續)環狀串列的加入動作加入於串列的前端若串列為空串列(NULL)若串列不為空串列加入於串列的尾端加入在串列某一特定節點後面87環狀串列(續)環狀串列的加入動作25

Step1:head=x;tail=x;加入於串列的前端─串列為空串列Step2:x->next=x;Step1:x->next=head;加入於串列的前端─串列不為空串列88 Step1:head=x;tail=x;加入於串Step2:tail->next=x;Step3:head=x;89Step2:tail->next=x;Step3:加入於串列的尾端Step1:tail->next=x;Step2:x->next=head;Step3:tail=x;90加入於串列的尾端Step1:tail->next=xvoidinsert_node(structnode*ptr,structnode*head,structnode*tail){ structnode*prev,*this; if(head==NULL){/*插入資料為第一筆*/

ptr->next=ptr; head=ptr; tail=ptr; } else { this=head; if(ptr->key<this->key){/*插入位置為前端*/

ptr->next=this; head=ptr; tail->next=head; } else{ while(this->next!=head) { prev=this; this=this->next;

91voidinsert_node(structnode* if(ptr->key<this->key){/*插入位置於中間*/

ptr->next=this; prev->next=ptr; break; } }if(ptr->key>=this->key){/*插入資料於尾端*/

ptr->next=head; this->next=ptr; tail=ptr; } } }}92 if(ptr->key<this->key){環狀串列(續)環狀串列的刪除動作刪除串列前端的節點刪除串列尾端的節點刪除串列某一特定節點93環狀串列(續)環狀串列的刪除動作31Step1:tail->next=head->next;刪除串列前端的節點Step2:ptr=head;head=head->next;Step3:free(ptr);94Step1:tail->next=head->nex刪除串列尾端的節點Step1:必須先追蹤tail的前一個節點Step2:ptr->next=hear;Step3:free(tail);tail=ptr;ptr=head;while(ptr->next!=tail)ptr=ptr->next;95刪除串列尾端的節點Step1:必須先追蹤tail的前一個voiddelete_node(intdel_key,structnode*head,structnode*tail){ structnode*clear,*prev,*this; this=head; if(del_key==head->key){/*刪除資料於前端*/

clear=head; if(head->next==head)/*資料僅存在一筆*/ {head=NULL; tail=NULL;} else { head=head->next; tail->next=head; } }96voiddelete_node(intdel_key, while(this->next!=head&&head!=NULL)/*刪除資料於中間*/ { prev=this; this=this->next; if(del_key==,this->key) { clear=this; prev->next=this->next; tail=prev; } } if(del_key==tail->key){/*刪除資料於尾端*/ clear=tail; prev->next=head; tail=prev; } free(clear);}97 while(this->next!=head&&Step1:Atail->next=Bhead;Step2:Btail->next=Ahead;將兩串列相接98Step1:Atail->next=Bhead;St雙向鏈結串列雙向鏈結串列(doublylinkedlist)每個節點有三個欄位，一為左鏈結(LLink)，二為資料(Data)，三為右鏈結(RLink)特點：假設ptr是任何節點的指標，則

ptr=ptr->llink->rlink=ptr->rlink->llink;若此雙向鏈結串列是空串列，則只有一個串列首99雙向鏈結串列雙向鏈結串列(doublylinkedlis雙向鏈結串列(續)優點：加入或刪除時，無需知道其前一節點的位址可以從任一節點找到其前一節點或後一節點可以將某一節點遺失的左或右指標適時地加以恢復之缺點：增加一個指標空間加入時需改變四個指標(單向只需改變兩個指標)刪除時需改變兩個指標(單向只要改變一個指標)100雙向鏈結串列(續)優點：38雙向鏈結串列(續)雙向鏈結串列的加入動作加入於串列的前端加入於串列的尾端加入在串列某一特定節點後面假設head節點不放任何資料voidinit_head(structnode*ptr,structnode*head,structnode*tail){ ptr=(structnode*)malloc(sizeof(structnode)); ptr->key=NULL; ptr->llink=ptr; ptr->rlink=ptr; head=ptr; tail=ptr;}101雙向鏈結串列(續)雙向鏈結串列的加入動作假設head節點不Step1:x->rlink=head;加入於串列的前端Step2:x->llink=tail;Step3:tail->rlink=x;102Step1:x->rlink=head;加入於串列的Step4:head->rlink=x;Step5:tail=x;103Step4:head->rlink=x;Step5加入於串列的尾端Step1:x->rlink=tail->rlink;Assumption:假設有一串列如下Step2:tail->rlink=x;104加入於串列的尾端Step1:x->rlink=taiStep3:x->llink=tail;Step4:head->llink=x;Step5:tail=x;105Step3:x->llink=tail;Step4雙向鏈結串列(續)加入在串列某一特定節點後面必須先搜尋到某特定的節點，並假設此串列是以key由小而大建立的，而搜尋步驟如下：

prev=head;ptr=head->rlink;while(ptr!=head&&x->key<p->key){ prev=ptr; ptr=ptr->rlink;}106雙向鏈結串列(續)加入在串列某一特定節點後面44voidinsert_node(structnode*ptr,structnode*head,structnode*tail){ structnode*this; this=head->rlink; while(this!=head) { if(ptr->key<this->key){/*插入位置為中間*/

ptr->rlink=this; ptr->llink=this->llink; this->llink->rlink=ptr; this->llink=ptr; break; } this=this->rlink; } /*插入位置為尾端*/

if(head->rlink==head||this==head) { ptr->rlink=head; ptr->llink=head->llink; head->llink->rlink=ptr; head->llink=ptr; tail=ptr;}}107voidinsert_node(structnode*雙向鏈結串列(續)雙向鏈結串列的刪除動作刪除串列前端的節點刪除串列尾端的節點刪除串列某一特定節點108雙向鏈結串列(續)雙向鏈結串列的刪除動作46Step1:ptr=head->rlink;刪除串列前端的節點Step2:head->rlink=ptr->rlink;Step3:p->rlink->llink=p->llink;Step4:free(ptr);109Step1:ptr=head->rlink;刪除串列刪除串列尾端的節點Step1:tail->llink->rlink=head;Step2:head->llink=tail->llink;Step5:free(ptr);Step3:ptr=tail;Step4:tail=tail->llink;110刪除串列尾端的節點Step1:tail->llink->刪除串列某一特定節點Assumption:假設欲刪除this所指的節點Step1:this->llink->rlink=this->rlink;Step2:this->rlink->llink=this->llink;Step3:free(this);111刪除串列某一特定節點Assumption:假設欲刪除thivoiddelete_node(intdel_key,structnode*head,structnode*tail){ structnode*clear,*this; this=head->rlink; while(this!=head){ /*刪除資料於中間*/

if(del_key==this->key) { clear=this; this->llink->rlink=this->rlink; this->rlink->llink=this->llink; if(this==tail) tail=this->llink; break; } this=this->rlink; } free(clear);}112voiddelete_node(intdel_key,鏈結串列的應用以鏈結串列表示堆疊以鏈結串列表示佇列以鏈結串列表示多項式相加113鏈結串列的應用以鏈結串列表示堆疊51鏈結串列的應用(續)以鏈結串列表示堆疊將堆疊內的資料視為單向鏈結串列中的資料項Push:視為將節點加入串列的前端Pop: