單向鏈結串列

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

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

/*head為一個指標，指向鏈結串列之起始節(jié)點*/4基本運作及圖解5單向鏈結串列的釋放當使用malloc配置了記憶體之後，記憶體會一直存在直到程式結束，所以當不使用時必須釋放，釋放的方法為free(變數名稱)；請務必記得釋放記憶體，雖然不會發(fā)生錯誤訊息，可是會一直在記憶體中，導致記憶體的浪費。6單向鏈結串列插入如果打算在鏈結中加入一個新的節(jié)點，可以使用以下的方法，比方說有一個鏈結串列如下：number12345678910namePeter1Peter2Peter3Peter4Peter5Peter6Peter7Peter8Peter9Peter10next(指標)指向2號節(jié)點指向3號節(jié)點指向4號節(jié)點指向6號節(jié)點指向6號節(jié)點指向7號節(jié)點指向8號節(jié)點指向9號節(jié)點指向10號節(jié)點NULL7現在若想要加入一個11號的Mary節(jié)點，加在peter5節(jié)點和peter6節(jié)點之間，則先新增一個11號的Mary節(jié)點：再把串列改成以下這樣就行了：5號Peter5節(jié)點的next指向11號節(jié)點。接著把11號的Mary節(jié)點的next指向6號的peter6節(jié)點就可以了。number1234567891011namePeter1Peter2Peter3Peter4Peter5Peter6Peter7Peter8Peter9Peter10Marynext(指標)指向2號節(jié)點指向3號節(jié)點指向4號節(jié)點指向6號節(jié)點指11號節(jié)點指向7號節(jié)點指向8號節(jié)點指向9號節(jié)點指向10號節(jié)點NULL指向6號節(jié)點為了要完成以上的方法，必須建立一些變數儲存資料，以這一個範例為例需要2個指標：指向Mary節(jié)點的指標New指向Peter5節(jié)點的指標Ptr8單向鏈結串列刪除如果打算在鏈結中刪除節(jié)點，可以使用以下的方法：比方說有一個鏈結串列如下：number12345678910namePeter1Peter2Peter3Peter4Peter5Peter6Peter7Peter8Peter9Peter10next(指標)指向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(指標)指向2號節(jié)點指向3號節(jié)點指向4號節(jié)點指向6號節(jié)點指向6號節(jié)點指向7號節(jié)點指向8號節(jié)點指向9號節(jié)點指向10號節(jié)點NULL接著把5號Peter5節(jié)點釋放掉,使用Free：number1234678910namePeter1Peter2Peter3Peter4Peter6Peter7Peter8Peter9Peter10next(指標)指向2號節(jié)點指向3號節(jié)點指向4號節(jié)點指向6號節(jié)點指向7號節(jié)點指向8號節(jié)點指向9號節(jié)點指向10號節(jié)點NULL10單向鏈結串列的反轉如果鏈結串列如下：number123456789namePeter1Peter2Peter3Peter4Peter5Peter6Peter7Peter8Peter9next(指標)指向2號節(jié)點指向3號節(jié)點指向4號節(jié)點指向5號節(jié)點指向6號節(jié)點指向7號節(jié)點指向8號節(jié)點指向9號節(jié)點NULL改成：number123456789namePeter1Peter2Peter3Peter4Peter5Peter6Peter7Peter8Peter9next(指標)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設為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ā)現9號節(jié)點next是NULL，跳出迴圈把9號節(jié)點的next指向8號把head(頭指標)指向9號節(jié)點即可12每一次迴圈次需要使用3個節(jié)點，把第2個節(jié)點的next指向第1個節(jié)點，下一次的第一個節(jié)點是這一次的第二個節(jié)點下一次的第二個節(jié)點是這一次的第三個節(jié)點下一次的第三個節(jié)點是這一次的第三個節(jié)點的next13基本運算的演算法與程式14產生新節(jié)點C語言程式NODE*getnode(void) /*此函數產生一個新節(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) /*此函數將節(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é)點走訪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計算鏈結串列之長度C語言程式intlength(NODE*p)

/*此函數計算節(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é)點中間任何一個位置圖解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é)點插入*/NODE*insert_node(NODE*head,NODE*ptr,intvalue){NODE*new;

/*新節(jié)點指標變數*/new=getnode();

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

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

/*設定指標初值*/if(ptr==NULL)

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

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

/*是否是串列結束*///第二種情況:插入最後一個節(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é)點中間任何一個位置圖解：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); /*此函數將節(jié)點歸還給記憶體*/return(head);}29C語言程式//鍵結串列的節(jié)點刪除NODE*delete_node(NODE*head,NODE*ptr){NODE*previous; /*指向前一節(jié)點*/if(ptr==head) /*是否是串列開始*/30/*第一種情況:刪除第一個節(jié)點*/{head=head->next;return(head); /*reset起始節(jié)點指標*/}else{previous=head;while(previous->next!=ptr) /*找節(jié)點ptr的前節(jié)點*/previous=previous->next;if(ptr->next==NULL) /*是否是串列結束*/31//第二種情況:刪除最後一個節(jié)點previous->next=NULL;

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

以鏈結串列表示如下：34假設兩個多項式

與 相加若以單向鏈結串列方式呈現

則其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){ /*當兩個多項式皆相加完則結束*/ptr=(structpoly*)malloc(sizeof(structpoly));ptr->next=NULL;//第一個多項式指數大於第二個多項式if(this_n1!=NULL&&(this_n2==NULL||this_n1-