单向链结串列

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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