《最新单向链结串列ppt课件》由会员分享，可在线阅读，更多相关《最新单向链结串列ppt课件（39页珍藏版）》请在金锄头文库上搜索。
1、单向链结串列单向链结串列定義及表示法uu節點包含資料（節點包含資料（datadata）及鏈結（）及鏈結（linklink）兩個欄位。）兩個欄位。uu其資料結構表示，如下圖所示其資料結構表示，如下圖所示headhead：指向串列前端之指標：指向串列前端之指標tailtail：指向串列尾端之指標：指向串列尾端之指標單向鏈結串列刪除單向鏈結串列刪除uu如果打算在鏈結中刪除節點，可以使用以下的方法：uu比方說有一個鏈結串列如下：numbernumber1 12 23 34 45 56 67 78 89 91010namenamePeter1Peter1Peter2Peter2Peter3Peter3P
2、eter4Peter4Peter5Peter5Peter6Peter6Peter7Peter7Peter8Peter8Peter9Peter9Peter10Peter10nextnext( (指標指標) )指向指向2 2號節點號節點指向指向3 3號節點號節點指向指向4 4號節點號節點指向指向5 5號節點號節點指向指向6 6號節點號節點指向指向7 7號節點號節點指向指向8 8號節點號節點指向指向9 9號節點號節點指向指向1010號節點號節點NULLNULL若要刪除5號Peter5節點，只需改了2個地方，4號Peter4節點的next指向6號的Peter6：numbernumber1 12 23
3、34 45 56 67 78 89 91010namenamePeter1Peter1Peter2Peter2Peter3Peter3Peter4Peter4Peter5Peter5Peter6Peter6Peter7Peter7Peter8Peter8Peter9Peter9Peter10Peter10nextnext( (指標指標) )指向指向2 2號節點號節點指向指向3 3號節點號節點指向指向4 4號節點號節點指向指向6 6號節點號節點指向指向6 6號節點號節點指向指向7 7號節點號節點指向指向8 8號節點號節點指向指向9 9號節點號節點指向指向1010號節點號節點NULLNULL接著把
4、5號Peter5節點釋放掉,使用Free：numbernumber1 12 23 34 46 67 78 89 91010namenamePeter1Peter1Peter2Peter2Peter3Peter3Peter4Peter4Peter6Peter6Peter7Peter7Peter8Peter8Peter9Peter9Peter10Peter10nextnext( (指標指標) )指向指向2 2號號節點節點指向指向3 3號號節點節點指向指向4 4號號節點節點指向指向6 6號號節點節點指向指向7 7號號節點節點指向指向8 8號號節點節點指向指向9 9號號節點節點指向指向1010號節點號
5、節點NULLNULL單向鏈結串列的反轉單向鏈結串列的反轉uu如果鏈結串列如下：numbernumber1 12 23 34 45 56 67 78 89 9namenamePeter1Peter1Peter2Peter2Peter3Peter3Peter4Peter4Peter5Peter5Peter6Peter6Peter7Peter7Peter8Peter8Peter9Peter9nextnext( (指標指標) )指向指向2 2號節點號節點指向指向3 3號節點號節點指向指向4 4號節點號節點指向指向5 5號節點號節點指向指向6 6號節點號節點指向指向7 7號節點號節點指向指向8 8號節點
6、號節點指向指向9 9號節點號節點NULLNULLuu改成：numbernumber1 12 23 34 45 56 67 78 89 9namenamePeter1Peter1Peter2Peter2Peter3Peter3Peter4Peter4Peter5Peter5Peter6Peter6Peter7Peter7Peter8Peter8Peter9Peter9nextnext( (指標指標) )NULLNULL指向指向1 1號節點號節點指向指向2 2號節點號節點指向指向3 3號節點號節點指向指向4 4號節點號節點指向指向5 5號節點號節點指向指向6 6號節點號節點指向指向7 7號節點號節
7、點指向指向8 8號節點號節點uu我們先使用我們先使用1,2,31,2,3號節點的位置號節點的位置uu把把1 1號節點的號節點的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、 8號節點的號節點的nextnext指向指向7 7號節點號節點uu發現發現9 9號節點號節點nextnext是是NULLNULL，跳出迴圈，跳出迴圈uu把把9 9號節點的號節點的nextnext指向指向8 8號號uu把把head(head(頭指標頭指標) )指向指向9 9號節點即可號節點即可uu每一次迴圈次需要使用3個節點，把第2個節點的next指向第1個節點，下一次下一次的第一個節點是這一次的第二個節點的第一個節點是這一次的第二個節點 下一次的第二個節點是這一次的第三個節點下一次的第二個節點是這一次的第三個節點 下一次的第三個節點是這一次的第三個節點的下一次的第三個節點是這一次的第三個節點的
9、nextnext基本運算的演算法與程式基本運算的演算法與程式產生新節點C C語言程式語言程式NODE *getnode (void)NODE *getnode (void)/* /* 此函數產生一個新節點此函數產生一個新節點*/*/ NODE *p; NODE *p;p p= (NODE *) malloc(sizeof(NODE); = (NODE *) malloc(sizeof(NODE); /* malloc/* malloc會動態地配置大小為會動態地配置大小為sizeof sizeof 的記憶體的記憶體*/*/* sizeof/* sizeof會傳回一個型態為會傳回一個型態為NODE
10、NODE之值之值*/*/ if ( p = NULL) if ( p = NULL) printf (“printf (“記憶體不足記憶體不足”);”);exit(1);exit(1); return(p); return(p); 歸還一個節點C語言程式void *freenode(NODE*p)void *freenode(NODE*p)/*/*此函數將節點還給記憶體此函數將節點還給記憶體*/*/ free(p);free(p); 尋找一個節點C語言程式NODE search_node (NODE *p, int num )NODE search_node (NODE *p, int num
11、 )/*/*自節點自節點p p之後尋找一個節點其之後尋找一個節點其datadata項目為項目為 search_data search_data之值之值*/*/ NODE *q;NODE *q;q = p-next; q = p-next; /*q/*q指向節點指向節點p p之後第一個節點之後第一個節點*/*/ while( q!= NULL & q-data != num) while( q!= NULL & q-data != num) q = q-next; q = q-next;/*q/*q改指向下一個節點改指向下一個節點*/*/return(q);return(q); 鍵結串列的節點走
12、訪C語言程式NODE find_node(NODE *head, int num)NODE find_node(NODE *head, int num) NODE *ptr; NODE *ptr; ptr = head; ptr = head; /*/*指向串列起始指向串列起始*/*/ while ( ptr != NULL ) while ( ptr != NULL ) /*/*走訪串列走訪串列*/*/ if ( ptr-num = num ) if ( ptr-num = num ) /*/*找尋找尋data*/data*/ return (ptr); return (ptr); ptr
13、= ptr-next; ptr = ptr-next; /*/*指向下一節點指向下一節點*/*/ return (ptr); return (ptr); 計算鏈結串列之長度C語言程式int length (NODE *p ) int length (NODE *p ) /*/*此函數計算節點此函數計算節點p p之後之長度之後之長度*/*/ int num=0; int num=0; NODE *q = p-next; NODE *q = p-next; While (q != NULL) While (q != NULL) num +; num +; q = q-next; q = q-nex
14、t; return(num); return(num); 節點之插入uu由鏈結串列加入一個節點一個節點之插入有三種情況：節點加於第一個節點之前節點加於第一個節點之前節點加於最後一個節點之後節點加於最後一個節點之後加於節點中間任何一個位置加於節點中間任何一個位置uu圖解節點加於第一個節點之前節點加於最後一個節點之後加於節點中間任何一個位置 虛擬碼NODE *insert_node ( NODE *head, NODE *ptr, NODE *insert_node ( NODE *head, NODE *ptr, int value)int value) 配置記憶體給配置記憶體給new;new;
15、if (ptr is NULL)if (ptr is NULL)插入第一個節點；插入第一個節點；elseelse if ( ptr-next = = NULL ) if ( ptr-next = = NULL )插入最後一個節點；插入最後一個節點；elseelse 插入成為中間節點；插入成為中間節點；return (head);return (head); C語言程式/*/*鍵結串列的節點插入鍵結串列的節點插入*/*/NODE *insert_node ( NODE *head, NODE NODE *insert_node ( NODE *head, NODE *ptr, int value
16、)*ptr, int value) NODE *new; NODE *new;/*/*新節點指標變數新節點指標變數*/*/new = getnode();new = getnode();/*(1)/*(1)建立新節點建立新節點, ,取得一個可用節點取得一個可用節點*/*/ new-num = value; new-num = value;/* (2) /* (2) 建立節點內容建立節點內容*/*/ new-next = NULL; new-next = NULL;/* /* 設定指標初值設定指標初值*/*/ if ( ptr = = NULL ) if ( ptr = = NULL ) /*/
17、*指標指標ptrptr是否是是否是NULL */ NULL */ /第一種情況第一種情況: : 插入第一個節點插入第一個節點 new-next = head; new-next = head; /*/*新節點成為串列開始新節點成為串列開始*/*/ head = new; head = new; else else if ( ptr-next = = NULL ) if ( ptr-next = = NULL ) /*/*是否是串列結束是否是串列結束*/*/第二種情況第二種情況: : 插入最後一個節點插入最後一個節點 ptr-next = new; ptr-next = new;/*/*最後指向
18、新節點最後指向新節點*/*/elseelse /第三種情況第三種情況: : 插入成為中間節點插入成為中間節點/* (3)/* (3)新節點指向下一節點新節點指向下一節點*/*/ new-next = ptr-next; new-next = ptr-next; /* (4)/* (4)節點節點ptrptr指向新節點指向新節點*/ */ ptr-next = new; ptr-next = new; return (head); return (head); 刪除節點uu由鏈結串列中刪除一個節點：一個節點之刪除有三種情況：刪除第一個節點刪除第一個節點刪除最後一個節點刪除最後一個節點加於節點中間任
19、何一個位置加於節點中間任何一個位置uu圖解：刪除第一個節點刪除最後一個節點加於節點中間任何一個位置虛擬碼NODE *delete_node(NODE *head, NODE *ptr)NODE *delete_node(NODE *head, NODE *ptr) NODE *previous; NODE *previous;/*/*指向前一節點指向前一節點*/*/ if ( ptr = = head ) if ( ptr = = head ) /*/*是否是串列開始是否是串列開始*/*/刪除第一個節點刪除第一個節點 else else if ( ptr-next = = NULL ) if
20、( ptr-next = = NULL )刪除最後一個節點刪除最後一個節點 else else刪除中間節點刪除中間節點freenode(ptr);freenode(ptr); /*/*此函數將節點歸還給記憶體此函數將節點歸還給記憶體*/*/return(head);return(head); C語言程式/鍵結串列的節點刪除鍵結串列的節點刪除NODE *delete_node(NODE *head, NODE NODE *delete_node(NODE *head, NODE *ptr)*ptr) NODE *previous; NODE *previous;/*/*指向前一節點指向前一節點*
21、/*/ if ( ptr = head ) if ( ptr = head )/*/*是否是串列開始是否是串列開始*/*/* /* 第一種情況第一種情況: : 刪除第一個節點刪除第一個節點 */ */ head = head-next; head = head-next; return(head); return(head); /*reset /*reset 起始節點指標起始節點指標*/*/ else else previous = head; previous = head; while ( previous-next != ptr ) while ( previous-next != pt
22、r ) /* /*找節點找節點ptrptr的前節點的前節點*/*/ previous = previous-next; previous = previous-next; if ( ptr-next = NULL ) if ( ptr-next = NULL ) /* /*是否是串列結束是否是串列結束*/*/第二種情況第二種情況: : 刪除最後一個節點刪除最後一個節點 previous-next = NULL; previous-next = NULL;/*/*最後一個節點最後一個節點*/*/ else else/第三種情況第三種情況: : 刪除中間節點刪除中間節點 previous-next
23、 = ptr-next; previous-next = ptr-next;/*/*圖圖(3)(3)之步驟之步驟(1)*/(1)*/ freenode(ptr);freenode(ptr);/*/*此函數將節點歸還給記憶體此函數將節點歸還給記憶體*/*/return(head);return(head); 範例：多項式的相加範例：多項式的相加uu多項式相加可以利用鏈結串列來完成。多項式以鏈結串列來表示的話，其資料結構如下：COEFCOEFEXPEXPLINKLINKuu其中COEF表示變數的係數uuEXP表示變數的指數uuLINK為指到下一節點的指標uu假設有一多項式以鏈結串列表示如下：uu假
24、設兩個多項式 與 相加uu若以單向鏈結串列方式呈現則其C語言程式如下：void poly_add(struct node *eq_hl, struct void poly_add(struct node *eq_hl, struct node *eq_h2, struct node *ans_h, struct node *eq_h2, struct node *ans_h, struct node *ptr)node *ptr) struct poly *this_nl, *this_n2, *prev;struct poly *this_nl, *this_n2, *prev;this_n
25、1 = eq_h1;this_n1 = eq_h1;this_n2 = eq_h2;this_n2 = eq_h2;prev = NULL;prev = NULL;while(this_n1 != NULL | this_n2 != while(this_n1 != NULL | this_n2 != NULL)NULL) /*/*當兩個多項式皆相加完則結束當兩個多項式皆相加完則結束*/*/ptr = (struct poly*) malloc(sizeof(struct ptr = (struct poly*) malloc(sizeof(struct poly);poly);ptr -ne
26、xt = NULL;ptr -next = NULL;/第一個多項式指數大於第二個多項式第一個多項式指數大於第二個多項式if (this_n1 != NULL& (this_n2 = NULL if (this_n1 != NULL& (this_n2 = NULL | | this_n1-exp this_n2 -exp)| | this_n1-exp this_n2 -exp) ptr-coef = this_n1-coef;ptr-coef = this_n1-coef;ptr-exp = this_n1-exp;ptr-exp = this_n1-exp;this_n1 = this_
27、n1-next;this_n1 = this_n1-next; /第一個多項式指數大於第二個多項式第一個多項式指數大於第二個多項式elseelse if (this_n1 != NULL& (this_n2 = NULL if (this_n1 != NULL& (this_n2 = NULL | | this_n1-exp | | this_n1-exp this_n2 -exp) this_n2 -exp) ptr-coef = this_n2-coef;ptr-coef = this_n2-coef;ptr-exp = this_n2-exp;ptr-exp = this_n2-exp;
28、this_n2 = this_n2-next;this_n2 = this_n2-next; /兩個多項式指數相等，進行相加兩個多項式指數相等，進行相加elseelse ptr-coef = this_n1-coef;ptr-coef = this_n1-coef;ptr-exp = this_n1-exp;ptr-exp = this_n1-exp;this_n1 = this_n1-next;this_n1 = this_n1-next;ptr-coef = this_n1-coef; + this_n2-coef;ptr-coef = this_n1-coef; + this_n2-co
29、ef;ptr-exp = this_n1-exp;ptr-exp = this_n1-exp;if (this_n1 != NULL) this_n1 = this_n1-next;if (this_n1 != NULL) this_n1 = this_n1-next;if (this_n1 != NULL) this_n2 = this_n2-next;if (this_n1 != NULL) this_n2 = this_n2-next; if (ptr-coef != 0)if (ptr-coef != 0) if (ans_h = = NULL) ans_h = ptr;if (ans_h = = NULL) ans_h = ptr;else prev - next = ptr;else prev - next = ptr;prev = ptr;prev = ptr; else free (ptr);else free (ptr);
