EX11. 鏈結串列DELETENODE

修改程式範例: Ch4-3-2.c 為 Ch4-3-2e.c
1.修改 Ch4-3-2.c 中include的 “deleteNode.c”程式
2.將”情況2: 刪除最後一個節點”及”情況3: 刪除中間節點 “的程式碼判
斷改為同時指向 ptr->next.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

/* Ch4-3.h */ struct Node /* Node節點結構 */ { int data; /* 結構變數宣告 */ struct Node *next; /* 指向下一個節點 */ }; typedef struct Node LNode; /* 串列節點的新型態 */ typedef LNode *List; /* 串列的新型態 */ List first = NULL; /* 串列的開頭指標 */ /* 抽象資料型態的操作函數宣告 */ extern void creatList(int len, int *array); extern int isListEmpty(); extern void printList(); extern List searchNode(int d); extern int deleteNode(List ptr); extern void insertNode(List ptr, int d);

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

/* createList.c */ /* 函數: 建立串列 */ void createList(int len, int *array) { int i; List newnode; for ( i = 0; i < len; i++ ) { /* 配置節點記憶體 */ newnode = (List) malloc(sizeof(LNode)); newnode->data = array[i]; /* 建立節點內容 */ newnode->next = first; first = newnode; } } /* 函數: 檢查串列是否是空的 */ int isListEmpty() { if ( first == NULL ) return 1; else return 0; } /* 函數: 顯示串列資料 */ void printList() { List current = first; /* 目前的串列指標 */ while ( current != NULL ) /* 顯示主迴圈 */ { printf("[%d]", current->data); current = current->next; /* 下一個節點 */ } printf("\n"); } /* 函數: 搜尋節點資料 */ List searchNode(int d) { List current = first; /* 目前的串列指標 */ while ( current != NULL ) /* 搜尋主迴圈 */ { if ( current->data == d ) /* 是否找到資料 */ return current; /* 找到 */ current = current->next; /* 下一個節點 */ } return NULL; /* 沒有找到 */ }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

/* deleteNode.c */ /* 函數: 刪除節點 */ int deleteNode(List ptr) { List current = first; /* 指向前一節點 */ int value = ptr->data; /* 取得刪除的節點值 */ if ( isListEmpty() ) /* 檢查串列是否是空的 */ return -1; if (ptr==first || ptr==NULL) {/* 串列開始或NULL */ /* 情況1: 刪除第一個節點 */ first = first->next; /* 刪除第1個節點 */ } else { while (current->next!=ptr) /* 找節點ptr的前節點 */ current = current->next; current->next = ptr->next; /* 刪除中間或最後一個節點 */ } free(ptr); /* 釋放節點記憶體 */ return value; /* 傳回刪除的節點值 */ }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

/* Ch4-3-2e.c */ #include <stdio.h> #include <stdlib.h> #include "Ch4-3.h" #include "createList.c" #include "deleteNode.c" /* 主程式 */ int main() { int temp; /* 宣告變數 */ int data[6]={ 1, 2, 3, 4, 5, 6 };/* 建立串列的陣列 */ List ptr; createList(6, data); /* 建立串列 */ printf("原來的串列: "); printList(); /* 顯示串列 */ /* 4-3-2: 節點刪除 */ temp = 0; while ( temp != -1 ) { printf("請輸入刪除的郵寄編號(-1結束) ==> "); scanf("%d", &temp); /* 讀取郵寄編號 */ if ( temp != -1 ) /* 搜尋節點資料 */ { ptr = searchNode(temp); /* 找尋節點 */ if ( ptr != NULL ) { temp = deleteNode(ptr); /* 刪除節點 */ printf("刪除節點: %d\n", temp); printf("刪除後串列: "); printList(); /* 顯示刪除後串列 */ } } } system("PAUSE"); return 0; }