《《单向链结串列》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《单向链结串列》PPT课件.ppt（38页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、單向鏈結串列Singly Linked Lists定義及表示法uu節點包含資料（節點包含資料（datadata）及鏈結（）及鏈結（linklink）兩個欄位。）兩個欄位。uu其資料結構表示，如下圖所示其資料結構表示，如下圖所示headhead：指向串列前端之指標：指向串列前端之指標tailtail：指向串列尾端之指標：指向串列尾端之指標uu鏈結串列透過儲存元素在記憶體之位址為指標(Pointer)或鏈結(Link)取得下一個節點。故節點節點=資料資料+指標鏈結指標鏈結uu假設有一節點結構如下圖所示：則其節點結構可定義如下：則其節點結構可定義如下：typedeftypedef structstr
2、uct nodenode /*/*以結構體表示節點以結構體表示節點*/intint data;data;/*data /*data儲存節點資料項目儲存節點資料項目*/structstruct node *next;node *next;NODE;NODE;/*next /*next儲存下一個節點位址儲存下一個節點位址*/*NODE /*NODE表新定義之節點結構資料型態表新定義之節點結構資料型態*/一個指標變數一個指標變數headhead當作鏈結串列之起始指標，其宣當作鏈結串列之起始指標，其宣告如下：告如下：NODE *head;NODE *head;/*head/*head為一個指標，指向鏈
3、結串列之起始節點為一個指標，指向鏈結串列之起始節點*/基本運作及圖解基本運作及圖解單向鏈結串列的釋放單向鏈結串列的釋放uu當使用malloc配置了記憶體之後，記憶體會一直存在直到程式結束，所以當不使用時必須釋放，釋放的方法為free(變數名稱)；請務必記得釋放記憶體，雖然不會發生錯誤訊息，可是會一直在記憶體中，導致記憶體的浪費。單向鏈結串列插入單向鏈結串列插入uu如果打算在鏈結中加入一個新的節點，可以使用以下的方法，比方說有一個鏈結串列如下：number12345678910namePeter1Peter2Peter3Peter4Peter5Peter6Peter7Peter8Peter9Pe
4、ter10next(指標)指向2號節點指向3號節點指向4號節點指向6號節點指向6號節點指向7號節點指向8號節點指向9號節點指向10號節點NULL現在若想要加入一個11號的Mary節點，加在peter5節點和peter6節點之間，則先新增一個11號的Mary節點：number1234567891011namePeter1Peter2Peter3Peter4Peter5Peter6Peter7Peter8Peter9Peter10Marynext(指標)指向2號節點指向3號節點指向4號節點指向6號節點指向6號節點指向7號節點指向8號節點指向9號節點指向10號節點NULL再把串列改成以下這樣就行了：
5、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節點的指標Ptr單向鏈結串列刪除單向鏈
6、結串列刪除uu如果打算在鏈結中刪除節點，可以使用以下的方法：uu比方說有一個鏈結串列如下：number12345678910namePeter1Peter2Peter3Peter4Peter5Peter6Peter7Peter8Peter9Peter10next(指標)指向2號節點指向3號節點指向4號節點指向5號節點指向6號節點指向7號節點指向8號節點指向9號節點指向10號節點NULL若要刪除5號Peter5節點，只需改了2個地方，4號Peter4節點的next指向6號的Peter6：number12345678910namePeter1Peter2Peter3Peter4Peter5Pete
7、r6Peter7Peter8Peter9Peter10next(指標)指向2號節點指向3號節點指向4號節點指向6號節點指向6號節點指向7號節點指向8號節點指向9號節點指向10號節點NULL接著把5號Peter5節點釋放掉,使用Free：number1234678910namePeter1Peter2Peter3Peter4Peter6Peter7Peter8Peter9Peter10next(指標)指向2號節點指向3號節點指向4號節點指向6號節點指向7號節點指向8號節點指向9號節點指向10號節點NULL單向鏈結串列的反轉單向鏈結串列的反轉uu如果鏈結串列如下：number123456789na
8、mePeter1Peter2Peter3Peter4Peter5Peter6Peter7Peter8Peter9next(指標)指向2號節點指向3號節點指向4號節點指向5號節點指向6號節點指向7號節點指向8號節點指向9號節點NULLuu改成：number123456789namePeter1Peter2Peter3Peter4Peter5Peter6Peter7Peter8Peter9next(指標)NULL指向1號節點指向2號節點指向3號節點指向4號節點指向5號節點指向6號節點指向7號節點指向8號節點uu我們先使用我們先使用1,2,31,2,3號節點的位置號節點的位置uu把把1 1號節點的號
9、節點的nextnext設為設為NullNulluu再把再把2 2號的號的nextnext指向指向1 1號節點號節點uu接著使用接著使用2,3,42,3,4號節點號節點uu再把再把3 3號的號的nextnext指向指向2 2號節點號節點uu接著使用接著使用3,4,53,4,5號節點號節點uu再把再把4 4號的號的nextnext指向指向3 3號節點號節點,uu接著使用接著使用4,5,64,5,6號節點，號節點，.uu接著使用接著使用7,8,97,8,9號節點號節點uu將將8 8號節點的號節點的nextnext指向指向7 7號節點號節點uu發現發現9 9號節點號節點nextnext是是NULLNU
10、LL，跳出迴圈，跳出迴圈uu把把9 9號節點的號節點的nextnext指向指向8 8號號uu把把head(head(頭指標頭指標)指向指向9 9號節點即可號節點即可uu每一次迴圈次需要使用3個節點，把第2個節點的next指向第1個節點，下一次下一次的第一個節點是這一次的第二個節點的第一個節點是這一次的第二個節點 下一次的第二個節點是這一次的第三個節點下一次的第二個節點是這一次的第三個節點 下一次的第三個節點是這一次的第三個節點的下一次的第三個節點是這一次的第三個節點的nextnext基本運算的演算法與程式基本運算的演算法與程式產生新節點C C語言程式語言程式NODE *NODE *getnod
11、egetnode(void)(void)/*/*此函數產生一個新節點此函數產生一個新節點*/NODE *p;NODE *p;p p=(NODE*)=(NODE*)malloc(sizeof(NODEmalloc(sizeof(NODE););/*/*mallocmalloc會動態地配置大小為會動態地配置大小為sizeofsizeof 的記憶體的記憶體*/*/*sizeofsizeof會傳回一個型態為會傳回一個型態為NODENODE之值之值*/if(p=NULL)if(p=NULL)printfprintf(“(“記憶體不足記憶體不足”););exit(1);exit(1);return(pre
12、turn(p););歸還一個節點C語言程式void *void *freenode(NODEfreenode(NODE*p)*p)/*/*此函數將節點還給記憶體此函數將節點還給記憶體*/free(pfree(p););尋找一個節點C語言程式NODE search_node(NODE*p,int num)/*自節點p之後尋找一個節點其data項目為 search_data之值*/NODE*q;q=p-next;/*q指向節點p之後第一個節點*/while(q!=NULL&q-data!=num)q=q-next;/*q改指向下一個節點*/return(q);鍵結串列的節點走訪C語言程式NODE
13、NODE find_node(NODEfind_node(NODE*head,*head,intint num)num)NODE*NODE*ptrptr;ptrptr=head;=head;/*/*指向串列起始指向串列起始*/while(while(ptrptr!=NULL)!=NULL)/*/*走訪串列走訪串列*/if(if(ptrptr-num=-num=numnum)/*/*找尋找尋data*/data*/return(return(ptrptr););ptrptr=ptrptr-next;-next;/*/*指向下一節點指向下一節點*/return(return(ptrptr););計
14、算鏈結串列之長度C語言程式intint length(NODE*p)length(NODE*p)/*/*此函數計算節點此函數計算節點p p之後之長度之後之長度*/intint num=0;num=0;NODE*q=p-next;NODE*q=p-next;While(q!=NULL)While(q!=NULL)num+;num+;q=q-next;q=q-next;return(numreturn(num););節點之插入uu由鏈結串列加入一個節點一個節點之插入有三種情況：節點加於第一個節點之前節點加於第一個節點之前節點加於最後一個節點之後節點加於最後一個節點之後加於節點中間任何一個位置加於節
15、點中間任何一個位置uu圖解節點加於第一個節點之前節點加於最後一個節點之後加於節點中間任何一個位置 虛擬碼NODE*NODE*insert_nodeinsert_node(NODE*head,NODE*(NODE*head,NODE*ptrptr,intint value)value)配置記憶體給配置記憶體給new;new;if(if(ptrptr is NULL)is NULL)插入第一個節點；插入第一個節點；elseelse if(if(ptrptr-next=NULL)-next=NULL)插入最後一個節點；插入最後一個節點；elseelse 插入成為中間節點；插入成為中間節點；retur
16、n(head);return(head);C語言程式/*/*鍵結串列的節點插入鍵結串列的節點插入*/NODE*NODE*insert_nodeinsert_node(NODE*head,NODE (NODE*head,NODE*ptrptr,intint value)value)NODE*new;NODE*new;/*/*新節點指標變數新節點指標變數*/new=new=getnodegetnode();();/*(1)/*(1)建立新節點建立新節點,取得一個可用節點取得一個可用節點*/new-num=value;new-num=value;/*(2)/*(2)建立節點內容建立節點內容*/new
17、-next=NULL;new-next=NULL;/*/*設定指標初值設定指標初值*/if(if(ptrptr=NULL)=NULL)/*/*指標指標ptrptr是否是是否是NULL*/NULL*/第一種情況第一種情況:插入第一個節點插入第一個節點 new-next=head;new-next=head;/*/*新節點成為串列開始新節點成為串列開始*/head=new;head=new;else else if(if(ptrptr-next=NULL)-next=NULL)/*/*是否是串列結束是否是串列結束*/第二種情況第二種情況:插入最後一個節點插入最後一個節點 ptrptr-next=n
18、ew;-next=new;/*/*最後指向新節點最後指向新節點*/elseelse /第三種情況第三種情況:插入成為中間節點插入成為中間節點/*(3)/*(3)新節點指向下一節點新節點指向下一節點*/new-next=new-next=ptrptr-next;-next;/*(4)/*(4)節點節點ptrptr指向新節點指向新節點*/ptrptr-next=new;-next=new;return(head);return(head);刪除節點uu由鏈結串列中刪除一個節點：一個節點之刪除有三種情況：刪除第一個節點刪除第一個節點刪除最後一個節點刪除最後一個節點加於節點中間任何一個位置加於節點中間
19、任何一個位置uu圖解：刪除第一個節點刪除最後一個節點加於節點中間任何一個位置虛擬碼NODE*NODE*delete_node(NODEdelete_node(NODE*head,NODE*head,NODE*ptrptr)NODE*previous;NODE*previous;/*/*指向前一節點指向前一節點*/if(if(ptrptr=head)=head)/*/*是否是串列開始是否是串列開始*/刪除第一個節點刪除第一個節點 elseelse if(if(ptrptr-next=NULL)-next=NULL)刪除最後一個節點刪除最後一個節點 elseelse刪除中間節點刪除中間節點free
20、node(ptrfreenode(ptr););/*/*此函數將節點歸還給記憶體此函數將節點歸還給記憶體*/return(headreturn(head););C語言程式/鍵結串列的節點刪除鍵結串列的節點刪除NODE*NODE*delete_node(NODEdelete_node(NODE *head,NODE *head,NODE*ptrptr)NODE*previous;NODE*previous;/*/*指向前一節點指向前一節點*/if(if(ptrptr=head)=head)/*/*是否是串列開始是否是串列開始*/*第一種情況:刪除第一個節點*/head=head-next;ret
21、urn(head);/*reset 起始節點指標*/else previous=head;while(previous-next!=ptr)/*找節點ptr的前節點*/previous=previous-next;if(ptr-next=NULL)/*是否是串列結束*/第二種情況第二種情況:刪除最後一個節點刪除最後一個節點 previous-next=NULL;previous-next=NULL;/*/*最後一個節點最後一個節點*/else else/第三種情況第三種情況:刪除中間節點刪除中間節點 previous-next=previous-next=ptrptr-next;-next;/
22、*/*圖圖(3)(3)之步驟之步驟(1)*/(1)*/freenode(ptrfreenode(ptr););/*/*此函數將節點歸還給記憶體此函數將節點歸還給記憶體*/return(headreturn(head););範例：多項式的相加範例：多項式的相加uu多項式相加可以利用鏈結串列來完成。多項式以鏈結串列來表示的話，其資料結構如下：COEFEXPLINKuu其中COEF表示變數的係數uuEXP表示變數的指數uuLINK為指到下一節點的指標uu假設有一多項式以鏈結串列表示如下：uu假設兩個多項式 與 相加uu若以單向鏈結串列方式呈現則其C語言程式如下：void void poly_add(
23、structpoly_add(struct node*node*eq_hleq_hl,structstruct node*eq_h2,node*eq_h2,structstruct node*node*ans_hans_h,structstruct node*node*ptrptr)structstruct poly*poly*this_nlthis_nl,*this_n2,*,*this_n2,*prevprev;this_n1=eq_h1;this_n1=eq_h1;this_n2=eq_h2;this_n2=eq_h2;prevprev=NULL;=NULL;while(this_n1!
24、=NULL|this_n2!=while(this_n1!=NULL|this_n2!=NULL)NULL)/*/*當兩個多項式皆相加完則結束當兩個多項式皆相加完則結束*/ptrptr=(=(structstruct poly*)poly*)malloc(sizeof(structmalloc(sizeof(struct poly);poly);ptrptr-next=NULL;-next=NULL;/第一個多項式指數大於第二個多項式第一個多項式指數大於第二個多項式if(this_n1!=NULL&(this_n2=NULL if(this_n1!=NULL&(this_n2=NULL|thi
25、s_n1-exp this_n2-exp)|this_n1-exp this_n2-exp)ptrptr-coefcoef=this_n1-=this_n1-coefcoef;ptrptr-exp=this_n1-exp;-exp=this_n1-exp;this_n1=this_n1=this_n1this_n1-next;-next;/第一個多項式指數大於第二個多項式第一個多項式指數大於第二個多項式elseelse if(this_n1!=NULL&(this_n2=NULL if(this_n1!=NULL&(this_n2=NULL|this_n1-exp|this_n1-exp th
26、is_n2-exp)this_n2-exp)ptrptr-coefcoef=this_n2-=this_n2-coefcoef;ptrptr-exp=this_n2-exp;-exp=this_n2-exp;this_n2=this_n2=this_n2this_n2-next;-next;/兩個多項式指數相等，進行相加elseptr-coef=this_n1-coef;ptr-exp=this_n1-exp;this_n1=this_n1-next;ptr-coef=this_n1-coef;+this_n2-coef;ptr-exp=this_n1-exp;if(this_n1!=NULL)this_n1=this_n1-next;if(this_n1!=NULL)this_n2=this_n2-next;if(ptr-coef!=0)if(ans_h=NULL)ans_h=ptr;else prev-next=ptr;prev=ptr;else free(ptr);