Download presentation
Presentation is loading. Please wait.
1
單向鏈結串列 Singly Linked Lists
2
定義及表示法 節點包含資料（data）及鏈結（link）兩個欄位。 其資料結構表示，如下圖所示 head：指向串列前端之指標
tail：指向串列尾端之指標
3
鏈結串列透過儲存元素在記憶體之位址為指標(Pointer)或鏈結(Link)取得下一個節點。故
節點=資料+指標鏈結 假設有一節點結構如下圖所示：
4
一個指標變數head當作鏈結串列之起始指標，其宣告如下：
則其節點結構可定義如下： typedef struct node { /*以結構體表示節點*/ int data; /*data儲存節點資料項目*/ struct node *next; } NODE; /*next儲存下一個節點位址*/ /*NODE表新定義之節點結構資料型態*/ 一個指標變數head當作鏈結串列之起始指標，其宣告如下： NODE *head; /*head為一個指標，指向鏈結串列之起始節點*/
5
基本運作及圖解
6
單向鏈結串列的釋放 當使用malloc配置了記憶體之後，記憶體會一直存在直到程式結束，所以當不使用時必須釋放，釋放的方法為free(變數名稱)；請務必記得釋放記憶體，雖然不會發生錯誤訊息，可是會一直在記憶體中，導致記憶體的浪費。
7
單向鏈結串列插入 如果打算在鏈結中加入一個新的節點，可以使用以下的方法，比方說有一個鏈結串列如下： number 1 2 3 4 5 6 7
8 9 10 name Peter1 Peter2 Peter3 Peter4 Peter5 Peter6 Peter7 Peter8 Peter9 Peter10 next (指標) 指向2號節點 指向3號節點 指向4號節點 指向6號節點 指向7號節點 指向8號節點 指向9號節點 指向10號節點 NULL
8
現在若想要加入一個11號的Mary節點，加在peter5節點和peter6節點之間，則先新增一個11號的Mary節點：
number 1 2 3 4 5 6 7 8 9 10 11 name Peter1 Peter2 Peter3 Peter4 Peter5 Peter6 Peter7 Peter8 Peter9 Peter10 Mary next (指標) 指向2號節點 指向3號節點 指向4號節點 指向6號節點 指向7號節點 指向8號節點 指向9號節點 指向10號節點 NULL 再把串列改成以下這樣就行了： 5號Peter5節點的next指向11號節點。 接著把11號的Mary節點的next指向6號的peter6節點就可以了。 number 1 2 3 4 5 6 7 8 9 10 11 name Peter1 Peter2 Peter3 Peter4 Peter5 Peter6 Peter7 Peter8 Peter9 Peter10 Mary next (指標) 指向2號節點 指向3號節點 指向4號節點 指向6號節點 指11號節點 指向7號節點 指向8號節點 指向9號節點 指向10號節點 NULL 為了要完成以上的方法，必須建立一些變數儲存資料，以這一個範例為例需要2個指標： 指向Mary節點的指標New 指向Peter5節點的指標Ptr
9
單向鏈結串列刪除 如果打算在鏈結中刪除節點，可以使用以下的方法： 比方說有一個鏈結串列如下： number 1 2 3 4 5 6 7 8
9 10 name Peter1 Peter2 Peter3 Peter4 Peter5 Peter6 Peter7 Peter8 Peter9 Peter10 next (指標) 指向2號節點 指向3號節點 指向4號節點 指向5號節點 指向6號節點 指向7號節點 指向8號節點 指向9號節點 指向10號節點 NULL
10
若要刪除5號Peter5節點，只需改了2個地方，4號Peter4節點的next指向6號的Peter6：
number 1 2 3 4 5 6 7 8 9 10 name Peter1 Peter2 Peter3 Peter4 Peter5 Peter6 Peter7 Peter8 Peter9 Peter10 next (指標) 指向2號節點 指向3號節點 指向4號節點 指向6號節點 指向7號節點 指向8號節點 指向9號節點 指向10號節點 NULL 接著把5號Peter5節點釋放掉,使用Free： number 1 2 3 4 6 7 8 9 10 name Peter1 Peter2 Peter3 Peter4 Peter6 Peter7 Peter8 Peter9 Peter10 next (指標) 指向2號節點 指向3號節點 指向4號節點 指向6號節點 指向7號節點 指向8號節點 指向9號節點 指向10號節點 NULL
11
單向鏈結串列的反轉 如果鏈結串列如下： 改成： number 1 2 3 4 5 6 7 8 9 name Peter1 Peter2
next (指標) 指向2號節點 指向3號節點 指向4號節點 指向5號節點 指向6號節點 指向7號節點 指向8號節點 指向9號節點 NULL 改成： number 1 2 3 4 5 6 7 8 9 name Peter1 Peter2 Peter3 Peter4 Peter5 Peter6 Peter7 Peter8 Peter9 next (指標) NULL 指向1號節點 指向2號節點 指向3號節點 指向4號節點 指向5號節點 指向6號節點 指向7號節點 指向8號節點
12
我們先使用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號節點即可
13
每一次迴圈次需要使用3個節點，把第2個節點的next指向第1個節點，
下一次的第一個節點是這一次的第二個節點 下一次的第二個節點是這一次的第三個節點 下一次的第三個節點是這一次的第三個節點的next
14
基本運算的演算法與程式
15
產生新節點 C語言程式 NODE *getnode (void) /* 此函數產生一個新節點*/ { NODE *p;
p = (NODE *) malloc(sizeof(NODE)); /* malloc會動態地配置大小為sizeof 的記憶體*/ /* sizeof會傳回一個型態為NODE之值*/ if ( p == NULL) printf (“記憶體不足”); exit(1); } return(p);
16
歸還一個節點 C語言程式 void *freenode(NODE*p) /*此函數將節點還給記憶體*/ { free(p); }
17
尋找一個節點 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); }
18
鍵結串列的節點走訪 C語言程式 NODE find_node(NODE *head, int num) { NODE *ptr;
ptr = head; /*指向串列起始*/ while ( ptr != NULL ) /*走訪串列*/ { if ( ptr->num == num ) /*找尋data*/ return (ptr); ptr = ptr->next; } /*指向下一節點*/ }
19
計算鏈結串列之長度 C語言程式 int length (NODE *p ) /*此函數計算節點p之後之長度*/ { int num=0;
NODE *q = p->next; While (q != NULL) { num ++; q = q->next; } return(num); }
20
節點之插入 由鏈結串列加入一個節點 一個節點之插入有三種情況： 圖解 節點加於第一個節點之前 節點加於最後一個節點之後
加於節點中間任何一個位置 圖解
21
節點加於第一個節點之前 節點加於最後一個節點之後 加於節點中間任何一個位置
22
虛擬碼 NODE *insert_node ( NODE *head, NODE *ptr, int value) { 配置記憶體給new;
if (ptr is NULL) 插入第一個節點； else if ( ptr->next = = NULL ) 插入最後一個節點； 插入成為中間節點； return (head); }
23
C語言程式 /*鍵結串列的節點插入*/ NODE *insert_node ( NODE *head, NODE *ptr, int value) { NODE *new; /*新節點指標變數*/ new = getnode(); /*(1)建立新節點,取得一個可用節點*/ new->num = value; /* (2) 建立節點內容*/ new->next = NULL; /* 設定指標初值*/ if ( ptr = = NULL ) /*指標ptr是否是NULL */
24
{ //第一種情況: 插入第一個節點 new->next = head; /*新節點成為串列開始*/ head = new; } else if ( ptr->next = = NULL ) /*是否是串列結束*/ //第二種情況: 插入最後一個節點 ptr->next = new; /*最後指向新節點*/
25
else { //第三種情況: 插入成為中間節點 /* (3)新節點指向下一節點*/ new->next = ptr->next; /* (4)節點ptr指向新節點*/ ptr->next = new; } return (head);
26
刪除節點 由鏈結串列中刪除一個節點： 一個節點之刪除有三種情況： 刪除第一個節點 刪除最後一個節點 加於節點中間任何一個位置 圖解：
27
刪除第一個節點 刪除最後一個節點
28
加於節點中間任何一個位置
29
虛擬碼 NODE *delete_node(NODE *head, NODE *ptr) {
NODE *previous; /*指向前一節點*/ if ( ptr = = head ) /*是否是串列開始*/ 刪除第一個節點 else if ( ptr->next = = NULL ) 刪除最後一個節點 刪除中間節點 freenode(ptr); /*此函數將節點歸還給記憶體*/ return(head); }
30
C語言程式 //鍵結串列的節點刪除 NODE *delete_node(NODE *head, NODE *ptr) {
NODE *previous; /*指向前一節點*/ if ( ptr == head ) /*是否是串列開始*/
31
/* 第一種情況: 刪除第一個節點 */ { head = head->next; return(head); /*reset 起始節點指標*/ } else previous = head; while ( previous->next != ptr ) /*找節點ptr的前節點*/ previous = previous->next; if ( ptr->next == NULL ) /*是否是串列結束*/
32
//第二種情況: 刪除最後一個節點 previous->next = NULL; /*最後一個節點*/ else //第三種情況: 刪除中間節點 previous->next = ptr->next; /*圖(3)之步驟(1)*/ } freenode(ptr); /*此函數將節點歸還給記憶體*/ return(head);
33
範例：多項式的相加 多項式相加可以利用鏈結串列來完成。多項式以鏈結串列來表示的話，其資料結構如下： 其中COEF表示變數的係數
EXP LINK 其中COEF表示變數的係數 EXP表示變數的指數 LINK為指到下一節點的指標
34
假設有一多項式 以鏈結串列表示如下：
35
若以單向鏈結串列方式呈現 則其C語言程式如下：
假設兩個多項式 與 相加 若以單向鏈結串列方式呈現 則其C語言程式如下： void poly_add(struct node *eq_hl, struct node *eq_h2, struct node *ans_h, struct node *ptr) { struct poly *this_nl, *this_n2, *prev; this_n1 = eq_h1; this_n2 = eq_h2; prev = NULL;
36
while(this_n1 != NULL || this_n2 != NULL)
{ /*當兩個多項式皆相加完則結束*/ ptr = (struct poly*) malloc(sizeof(struct poly)); ptr ->next = NULL; //第一個多項式指數大於第二個多項式 if (this_n1 != NULL&& (this_n2 == NULL | | this_n1->exp > this_n2 ->exp)) { ptr->coef = this_n1->coef; ptr->exp = this_n1->exp; this_n1 = this_n1->next; }
37
//第一個多項式指數大於第二個多項式 else { if (this_n1 != NULL&& (this_n2 == NULL | | this_n1->exp ＜ this_n2 ->exp)) ptr->coef = this_n2->coef; ptr->exp = this_n2->exp; this_n2 = this_n2->next; }
38
//兩個多項式指數相等，進行相加 else { ptr->coef = this_n1->coef; ptr->exp = this_n1->exp; this_n1 = this_n1->next; ptr->coef = this_n1->coef; + this_n2->coef; 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);
Similar presentations
