單向鏈結(jié)串列

單向鏈結(jié)串列SinglyLinkedLists1定義及表示法節(jié)點包含資料（data）及鏈結(jié)（link）兩個欄位。其資料結(jié)構(gòu)表示，如下圖所示head：指向串列前端之指標(biāo)tail：指向串列尾端之指標(biāo)2鏈結(jié)串列透過儲存元素在記憶體之位址為指標(biāo)(Pointer)或鏈結(jié)(Link)取得下一個節(jié)點。故節(jié)點=資料+指標(biāo)鏈結(jié)假設(shè)有一節(jié)點結(jié)構(gòu)如下圖所示：3則其節(jié)點結(jié)構(gòu)可定義如下：typedefstructnode

{ /*以結(jié)構(gòu)體表示節(jié)點*/intdata; /*data儲存節(jié)點資料項目*/structnode*next;}NODE; /*next儲存下一個節(jié)點位址*/ /*NODE表新定義之節(jié)點結(jié)構(gòu)資料型態(tài)*/一個指標(biāo)變數(shù)head當(dāng)作鏈結(jié)串列之起始指標(biāo)，其宣告如下：NODE*head;

/*head為一個指標(biāo)，指向鏈結(jié)串列之起始節(jié)點*/4基本運作及圖解5單向鏈結(jié)串列的釋放當(dāng)使用malloc配置了記憶體之後，記憶體會一直存在直到程式結(jié)束，所以當(dāng)不使用時必須釋放，釋放的方法為free(變數(shù)名稱)；請務(wù)必記得釋放記憶體，雖然不會發(fā)生錯誤訊息，可是會一直在記憶體中，導(dǎo)致記憶體的浪費。6單向鏈結(jié)串列插入如果打算在鏈結(jié)中加入一個新的節(jié)點，可以使用以下的方法，比方說有一個鏈結(jié)串列如下：number12345678910namePeter1Peter2Peter3Peter4Peter5Peter6Peter7Peter8Peter9Peter10next(指標(biāo))指向2號節(jié)點指向3號節(jié)點指向4號節(jié)點指向6號節(jié)點指向6號節(jié)點指向7號節(jié)點指向8號節(jié)點指向9號節(jié)點指向10號節(jié)點NULL7現(xiàn)在若想要加入一個11號的Mary節(jié)點，加在peter5節(jié)點和peter6節(jié)點之間，則先新增一個11號的Mary節(jié)點：再把串列改成以下這樣就行了：5號Peter5節(jié)點的next指向11號節(jié)點。接著把11號的Mary節(jié)點的next指向6號的peter6節(jié)點就可以了。number1234567891011namePeter1Peter2Peter3Peter4Peter5Peter6Peter7Peter8Peter9Peter10Marynext(指標(biāo))指向2號節(jié)點指向3號節(jié)點指向4號節(jié)點指向6號節(jié)點指11號節(jié)點指向7號節(jié)點指向8號節(jié)點指向9號節(jié)點指向10號節(jié)點NULL指向6號節(jié)點為了要完成以上的方法，必須建立一些變數(shù)儲存資料，以這一個範(fàn)例為例需要2個指標(biāo)：指向Mary節(jié)點的指標(biāo)New指向Peter5節(jié)點的指標(biāo)Ptr8單向鏈結(jié)串列刪除如果打算在鏈結(jié)中刪除節(jié)點，可以使用以下的方法：比方說有一個鏈結(jié)串列如下：number12345678910namePeter1Peter2Peter3Peter4Peter5Peter6Peter7Peter8Peter9Peter10next(指標(biāo))指向2號節(jié)點指向3號節(jié)點指向4號節(jié)點指向5號節(jié)點指向6號節(jié)點指向7號節(jié)點指向8號節(jié)點指向9號節(jié)點指向10號節(jié)點NULL9若要刪除5號Peter5節(jié)點，只需改了2個地方，4號Peter4節(jié)點的next指向6號的Peter6：number12345678910namePeter1Peter2Peter3Peter4Peter5Peter6Peter7Peter8Peter9Peter10next(指標(biāo))指向2號節(jié)點指向3號節(jié)點指向4號節(jié)點指向6號節(jié)點指向6號節(jié)點指向7號節(jié)點指向8號節(jié)點指向9號節(jié)點指向10號節(jié)點NULL接著把5號Peter5節(jié)點釋放掉,使用Free：number1234678910namePeter1Peter2Peter3Peter4Peter6Peter7Peter8Peter9Peter10next(指標(biāo))指向2號節(jié)點指向3號節(jié)點指向4號節(jié)點指向6號節(jié)點指向7號節(jié)點指向8號節(jié)點指向9號節(jié)點指向10號節(jié)點NULL10單向鏈結(jié)串列的反轉(zhuǎn)如果鏈結(jié)串列如下：number123456789namePeter1Peter2Peter3Peter4Peter5Peter6Peter7Peter8Peter9next(指標(biāo))指向2號節(jié)點指向3號節(jié)點指向4號節(jié)點指向5號節(jié)點指向6號節(jié)點指向7號節(jié)點指向8號節(jié)點指向9號節(jié)點NULL改成：number123456789namePeter1Peter2Peter3Peter4Peter5Peter6Peter7Peter8Peter9next(指標(biāo))NULL指向1號節(jié)點指向2號節(jié)點指向3號節(jié)點指向4號節(jié)點指向5號節(jié)點指向6號節(jié)點指向7號節(jié)點指向8號節(jié)點11我們先使用1,2,3號節(jié)點的位置把1號節(jié)點的next設(shè)為Null再把2號的next指向1號節(jié)點接著使用2,3,4號節(jié)點再把3號的next指向2號節(jié)點接著使用3,4,5號節(jié)點再把4號的next指向3號節(jié)點,接著使用4,5,6號節(jié)點，...................接著使用7,8,9號節(jié)點將8號節(jié)點的next指向7號節(jié)點發(fā)現(xiàn)9號節(jié)點next是NULL，跳出迴圈把9號節(jié)點的next指向8號把head(頭指標(biāo))指向9號節(jié)點即可12每一次迴圈次需要使用3個節(jié)點，把第2個節(jié)點的next指向第1個節(jié)點，下一次的第一個節(jié)點是這一次的第二個節(jié)點下一次的第二個節(jié)點是這一次的第三個節(jié)點下一次的第三個節(jié)點是這一次的第三個節(jié)點的next13基本運算的演算法與程式14產(chǎn)生新節(jié)點C語言程式NODE*getnode(void) /*此函數(shù)產(chǎn)生一個新節(jié)點*/{NODE*p;p=(NODE*)malloc(sizeof(NODE));/*malloc會動態(tài)地配置大小為sizeof的記憶體*//*sizeof會傳回一個型態(tài)為NODE之值*/if(p==NULL){printf(“記憶體不足”);exit(1);}return(p);}15歸還一個節(jié)點C語言程式void*freenode(NODE*p) /*此函數(shù)將節(jié)點還給記憶體*/{free(p);}16尋找一個節(jié)點C語言程式NODEsearch_node(NODE*p,intnum)/*自節(jié)點p之後尋找一個節(jié)點其data項目為search_data之值*/{ NODE*q;q=p->next; /*q指向節(jié)點p之後第一個節(jié)點*/while(q!=NULL&&q->data!=num)q=q->next; /*q改指向下一個節(jié)點*/return(q);}17鍵結(jié)串列的節(jié)點走訪C語言程式NODEfind_node(NODE*head,intnum){NODE*ptr;ptr=head; /*指向串列起始*/while(ptr!=NULL) /*走訪串列*/{if(ptr->num==num) /*找尋data*/return(ptr);ptr=ptr->next;} /*指向下一節(jié)點*/return(ptr);}18計算鏈結(jié)串列之長度C語言程式intlength(NODE*p)

/*此函數(shù)計算節(jié)點p之後之長度*/{intnum=0;NODE*q=p->next;While(q!=NULL){num++;q=q->next; }return(num);}19節(jié)點之插入由鏈結(jié)串列加入一個節(jié)點

一個節(jié)點之插入有三種情況：節(jié)點加於第一個節(jié)點之前節(jié)點加於最後一個節(jié)點之後加於節(jié)點中間任何一個位置圖解20節(jié)點加於第一個節(jié)點之前節(jié)點加於最後一個節(jié)點之後加於節(jié)點中間任何一個位置21虛擬碼NODE*insert_node(NODE*head,NODE*ptr,intvalue){配置記憶體給new;if(ptrisNULL)插入第一個節(jié)點；elseif(ptr->next==NULL)插入最後一個節(jié)點；else插入成為中間節(jié)點；return(head);}22C語言程式/*鍵結(jié)串列的節(jié)點插入*/NODE*insert_node(NODE*head,NODE*ptr,intvalue){NODE*new;

/*新節(jié)點指標(biāo)變數(shù)*/new=getnode();

/*(1)建立新節(jié)點,取得一個可用節(jié)點*/new->num=value;

/*(2)建立節(jié)點內(nèi)容*/new->next=NULL;

/*設(shè)定指標(biāo)初值*/if(ptr==NULL)

/*指標(biāo)ptr是否是NULL*/23{//第一種情況:插入第一個節(jié)點new->next=head;

/*新節(jié)點成為串列開始*/head=new;}else{if(ptr->next==NULL)

/*是否是串列結(jié)束*///第二種情況:插入最後一個節(jié)點ptr->next=new;

/*最後指向新節(jié)點*/24else{//第三種情況:插入成為中間節(jié)點/*(3)新節(jié)點指向下一節(jié)點*/new->next=ptr->next;/*(4)節(jié)點ptr指向新節(jié)點*/ptr->next=new; }}return(head);}25刪除節(jié)點由鏈結(jié)串列中刪除一個節(jié)點：

一個節(jié)點之刪除有三種情況：刪除第一個節(jié)點刪除最後一個節(jié)點加於節(jié)點中間任何一個位置圖解：26刪除第一個節(jié)點刪除最後一個節(jié)點27加於節(jié)點中間任何一個位置28虛擬碼NODE*delete_node(NODE*head,NODE*ptr){NODE*previous; /*指向前一節(jié)點*/if(ptr==head) /*是否是串列開始*/刪除第一個節(jié)點elseif(ptr->next==NULL)刪除最後一個節(jié)點else刪除中間節(jié)點freenode(ptr); /*此函數(shù)將節(jié)點歸還給記憶體*/return(head);}29C語言程式//鍵結(jié)串列的節(jié)點刪除NODE*delete_node(NODE*head,NODE*ptr){NODE*previous; /*指向前一節(jié)點*/if(ptr==head) /*是否是串列開始*/30/*第一種情況:刪除第一個節(jié)點*/{head=head->next;return(head); /*reset起始節(jié)點指標(biāo)*/}else{previous=head;while(previous->next!=ptr) /*找節(jié)點ptr的前節(jié)點*/previous=previous->next;if(ptr->next==NULL) /*是否是串列結(jié)束*/31//第二種情況:刪除最後一個節(jié)點previous->next=NULL;

/*最後一個節(jié)點*/else//第三種情況:刪除中間節(jié)點previous->next=ptr->next; /*圖(3)之步驟(1)*/}freenode(ptr); /*此函數(shù)將節(jié)點歸還給記憶體*/return(head);}32範(fàn)例：多項式的相加多項式相加可以利用鏈結(jié)串列來完成。多項式以鏈結(jié)串列來表示的話，其資料結(jié)構(gòu)如下：COEFEXPLINK其中COEF表示變數(shù)的係數(shù)EXP表示變數(shù)的指數(shù)LINK為指到下一節(jié)點的指標(biāo)33假設(shè)有一多項式

以鏈結(jié)串列表示如下：34假設(shè)兩個多項式

與 相加若以單向鏈結(jié)串列方式呈現(xiàn)

則其C語言程式如下：voidpoly_add(structnode*eq_hl,structnode*eq_h2,structnode*ans_h,structnode*ptr){structpoly*this_nl,*this_n2,*prev;this_n1=eq_h1;this_n2=eq_h2;prev=NULL;35while(this_n1!=NULL||this_n2!=NULL){ /*當(dāng)兩個多項式皆相加完則結(jié)束*/ptr=(structpoly*)malloc(sizeof(structpoly));ptr->next=NULL;//第一個多項式指數(shù)大於第二個多項式if(this_n1!=NULL&&(this_n2==NULL||this_n1-