陣列與鏈結串列 NTU CSIE
Outline 結構陣列鏈結串列 單向鏈結串列之資料型態 單向鏈結串列之基本運算 作業
結構陣列 優點 缺點 使用容易 刪除與插入造成資料移動頻繁浪費不必要之記憶體陣列長度為常數, 可能會不夠用 #include<stdio.h> struct _student int math; int english; int computer; ; typedef struct _student student; int main() student s[5]; return 0; student student student student student math english computer s [0] [1] [2] [3] [4]
Outline 結構陣列 鏈結串列 單向鏈結串列之資料型態 單向鏈結串列之基本運算 作業
靜態與動態結構 struct _node 資料型態變數名稱 ; int data; struct _node *next; ; typedef struct _node node; node c; node *; c.next = NULL; = (node *)malloc(sizeof(node)); ->next = NULL; 資料型態 struct _node * node 資料 int data NULL c 變數名稱 next 資料型態 struct _node * struct _node * node 資料 int data NULL (malloc) 變數名稱 next
鏈結串列節點 節點 : 鏈結串列中最基本的單位 資料 結構指標 節點 下一個節點 節點 = 資料 + 結構指標
定義鏈結串列節點結構 鏈結串列透過儲存元素在記憶體之位址為指標 (Pointer) 或鏈結 (Link) 取得下一個節點 定義節點結構 struct _node 資料型態變數名稱 ; int data; struct _node *next; ; typedef struct _node node; 資料型態 struct _node * node 資料 int data 下一個節點 變數名稱 next
單向鏈結串列 單向鏈結串列之結構如下圖所示 : 指向串列前端之指標 NULL 鏈結起點 鏈結終點
小練習 ( 建立鏈結串列節點 )(ex01 build-1.c) 定義一個鏈結串列節點結構如下圖所示, 並使用 指標指向動態配置之節點 struct _node * node int struct _node * 10 NULL (malloc) data next
連續鏈結串列 node *, *ptr; = (node *)malloc(sizeof(node)); ptr = ; int value; scanf("%d", &value); ptr->data = value; ptr->next = (node *)malloc(sizeof(node)); ptr = ptr->next; 4 5 8 ptr NULL
小練習 ( 建立鏈結串列 ) 定義一個鏈結串列, 將順序輸入的資料存在動態資料結構上 (ex: 輸入 5 筆 ), 然後將此串列資料順序列印出來 (ex04 build-3 add list.c) 4 5 8 ptr NULL 若想要反序列印呢?
小練習 ( 建立鏈結串列 ) 定義一個鏈結串列, 將順序輸入的資料存在動態資料結構上 (ex: 輸入 5 筆 ), 然後將此串列資料反序列印出來 (ex06 build-4 reverse.c) 5 4 2 1 NULL ptr
Outline 結構陣列 鏈結串列 單向鏈結串列之資料型態 單向鏈結串列之基本運算 - 函式整合版 作業
新增節點 動態配置一節點之記憶體 node *getnode () /* 此函數產生一個新節點 */ node *p; p = (node *) malloc(sizeof(node)); /* malloc 會動態地配置大小為 sizeof 的記憶體 */ /* sizeof 會傳回一個型態為 node 之值 */ if ( p == NULL) printf (" 記憶體不足 "); exit(1); return(p); node * p int struct _node * node x x (malloc) data next
釋放節點 歸還一個節點之記憶體 void freenode (node *p) /* 此函數將節點還給記憶體 */ free(p); node * int x data (malloc) p struct _node * x (malloc) next
插入節點 由鏈結串列加入一個節點 一個節點之插入有三種情況 : 節點加於第一個節點之前 new_node ptr=null 節點加於最後一個節點之後 加於節點中間任何一個位置 ptr new_node NULL new_node NULL ptr NULL
插入節點 節點加於最後一個節點之後 NULL (2) ptr (3) new_node NULL (1) Ex1: node *new_node; //(1) new_node = getnode(); ptr->next = new_node//(2) /* 指向新節點 */ new_node -> next = NULL; Ex2: ptr->next = (node *)malloc(sizeof(node)); //(1&2) ptr = ptr->next; //(3) NULL
插入節點 節點加於第一個節點之前 new_node (1) Ex1: node *new_node new_node = getnode(); //(1) new_node->next = ; //(2) = new_node; (2) ptr NULL Ex2: = (node *)malloc(sizeof(node)); //(1) -> next = ptr; //(2) ptr = ; //(3) NULL
插入節點 加於節點中間任何一個位置 new_node(1) (2) (3) node *new_node; //(1) new_node = getnode(); //(2) new_node->next = ptr->next; //(3) /* 新節點指向下一節點 */ ptr->next = new_node; //(4) /* 節點 ptr 指向新節點 */ ptr (4) NULL NULL
插入節點 node *insert_node (node *, node *ptr, node data) node *new_node; /* 新節點指標變數 */ new_node = getnode(); /* 建立新節點, 取得一個可用節點 */ *new_node = data; /* 建立節點內容 */ new_node->next = NULL; /* 設定指標初值 */ if ( ptr == NULL ) /* 指標 ptr 是否是 NULL */ /* 第一種情況 : 插入第一個節點 */ new_node->next = ; /* 新節點成為串列開始 */ = new_node; else if ( ptr->next == NULL ) /* 是否是串列結束 */ /* 第二種情況 : 插入最後一個節點 */ ptr->next = new_node; /* 最後指向新節點 */ else /* 第三種情況 : 插入成為中間節點 */ new_node->next = ptr->next; /* (3) 新節點指向下一節點 (3)*/ ptr->next = new_node; /* 節點 ptr 指向新節點 (4)*/ return ();
小練習 ( 插入鏈結串列節點 ) (ex07 interface i.c) 延續上一小練習 寫一個使用者介面, 輸入 i, 接著輸入一個數字 value, 可插入一筆資料節點中之 data 為 value 於串列最後 建立一個鏈結串列如下圖所示 : 輸入 l, 可將全部內容列印出來 struct _node * int struct _node * node 10 (malloc) node *, *ptr; node n; char key; int value; = NULL; node 20 (malloc) scanf("%d",&value); n.data = value; ptr = ; if(==null) =insert_node(, NULL, n); else while(ptr->next!= NULL) ptr = ptr->next; =insert_node(, ptr, n); printf("insert ok\n"); node 30 NULL (malloc) data next
尋找節點 走訪串列, 將找到之節點位置回傳 node *find_node(node *, int num) node *ptr; ptr = ; /* 指向串列起始 */ while ( ptr!= NULL ) /* 走訪串列 */ return (ptr); if ( ptr->data == num ) /* 找尋 data */ return (ptr); ptr = ptr->next; /* 指向下一節點 */ scanf("%d",&value); ptr = find_node(, value); (ptr!= NULL) ("found: %d\n", ptr->data); else printf("not found\n");
小練習 ( 尋找鏈結串列節點 ) (ex07 interface i.c) 延續上一小練習 寫一個使用者介面, 輸入 f, 接著輸入一個數字 value, 可將一筆資料節點中之 data 與 value 相同者印出資料
刪除節點 由鏈結串列中刪除一個節點一個節點之刪除有三種情況 : 刪除第一個節點 ptr 刪除最後一個節點 刪除中間任何一個節點 previous NULL previous NULL ptr ptr NULL
刪除節點 刪除第一個節點 (1) (2) ptr NULL = ->next; //(1) freenode(ptr); //(2) return(); /* reset 起始節點指標 */ NULL
刪除節點 刪除最後一個節點 previous = ; while ( previous->next!= ptr ) /* 找節點 ptr 的前節點 */ previous = previous->next; previous->next = NULL; //(1) /* 最後一個節點 */ freenode(ptr); //(2) /* 此函數將節點歸還給記憶體 */ previous NULL (1) (2) NULL ptr NULL
刪除節點 刪除中間任何一個節點 previous = ; while ( previous->next!= ptr ) /* 找節點 ptr 的前節點 */ previous = previous->next; /* 第三種情況 : 刪除中間節點 */ previous->next = ptr->next; //(1) freenode(ptr); //(2) /* 此函數將節點歸還給記憶體 */ previous (1) (2) ptr NULL NULL
刪除節點 node *delete_node(node *, node *ptr) node *previous; /* 指向前一節點 */ if ( ptr == ) /* 是否是串列開始 */ /* 第一種情況 : 刪除第一個節點 */ = ->next; else previous = ; while ( previous->next!= ptr ) /* 找節點 ptr 的前節點 */ previous = previous->next; if ( ptr->next == NULL ) /* 是否是串列結束 */ /* 第二種情況 : 刪除最後一個節點 */ previous->next = NULL; /* 最後一個節點 */ else /* 第三種情況 : 刪除中間節點 */ previous->next = ptr->next; /* 圖 (3) 之步驟 (1) */ freenode(ptr); /* 此函數將節點歸還給記憶體 */ return(); scanf("%d",&value); ptr = find_node(, value); if(ptr!= NULL) = delete_node(, ptr); printf("delete ok\n"); else printf("can not delete\n");
小練習 ( 刪除鏈結串列節點 ) (ex07 interface i.c) 延續上一小練習 寫一個使用者介面, 輸入 d, 接著輸入一個數字 value, 可將一筆資料節點中之 data 與 value 相同者刪除 ( 假設輸入之 value 不會重覆 )
鏈結串列長度 計算鏈結串列 之長度 int length (node * ) /* 此函數計算節點之鏈結長度 */ int num=0; node *q = ; while (q!= NULL) num ++; q = q->next; return(num);
Outline 結構陣列 鏈結串列 單向鏈結串列之資料型態 單向鏈結串列之基本運算 作業
小練習 (ex07 interface i.c) 將上述鏈結串列功能整合起來成為同一程式 功能 輸入 i, 接著輸入一個數字, 可插入節點中之 data 為 value 於串列最後 輸入 d, 接著輸入一個數字, 可將節點中之 data 與 value 相同者刪除 ( 假設輸入之 value 不會重覆 ) 輸入 f 接著輸入一個數字, 可將一筆資料節點中之數字相同者印出 輸入 l 印出串列所有節點內容並顯示目前資料筆數 輸入 q 離開程式 bonus: 可設計插入位置於最前 / 中間 / 最後
回家作業 (ex08 member data.c) 使用鏈結串列製作一個會員資料表 功能 輸入 i 新增節點在串列最後, 可輸入姓名, 電話, Email 輸入 d 接著輸入姓名, 可將節點中之姓名相同者刪除 ( 假設輸入之姓名不會重覆 ) 輸入 f 接著輸入一個姓名, 可將節點中之姓名相同者印出資料 輸入 l 印出串列所有節點內容並顯示目前人數 輸入 q 離開程式 提示 : 使用 strcmp 來實作 (string.h ) strcmp(data[0], data[0]) 第一個字串大於第二個字串回傳正值, 反之回傳負值 相等則為 0 bonus: 可設計插入位置於最前 / 中間 / 最後