資料結構與C++程式設計進階 鏈結串列 講師：林業峻 CSIE, NTU 6/ 10, 2010

大綱 鏈結串列 鏈結串列之資料型態 鏈結串列之基本運算 作業

鏈結串列 … 將資料以結構方式儲存, 並利用結構指標串連 用途： 鏈結串列之結構如下圖所示 head 鏈結起點 鏈結終點 (1) 不知道資料個數時 (2) 資料常需要隨時插入或刪除, 為了效率考量時 鏈結串列之結構如下圖所示 head：指向串列前端之指標 head Andy 0919.. Andy@... Joe 0958.. Joe@... Mary 0937.. Mary@... … NULL 鏈結起點 鏈結終點

靜態與動態結構 struct _node * head node node 資料 資料 n (malloc) struct _node *next; };  typedef struct _node node; struct _node * head node node 資料 資料 資料型態 變數名稱 資料型態 變數名稱 struct _node * NULL next struct _node * NULL next n (malloc) node n; n.next = NULL; node *head; head = (node *)malloc(sizeof(node)); head->next = NULL;

鏈結串列節點 節點：鏈結串列中最基本的單位 節點 資料 結構指標 下一個節點 節點 = 資料+ 結構指標

新增節點 動態配置一節點之記憶體 node x node * p (malloc) p = (node *) malloc(sizeof(node)); data next (malloc) node x struct _node * int node * p

釋放節點 歸還一個節點之記憶體 x node * p (malloc) free(p); data next int (malloc) struct _node * int node * (malloc) p

練習 (建立鏈結串列節點) 建立一個鏈結串列節點結構如下圖所示： struct _node * head node node node 10 20 30 int data struct _node * NULL next (malloc) (malloc) (malloc)

大綱 鏈結串列 鏈結串列之資料型態 鏈結串列之基本運算 作業

插入節點 … … … 功能：將一新節點插到鏈結串列中某個位置 一個節點之插入有三種情況： 節點加於第一個節點之前 節點加於最後一個節點之後 加於節點中間任何一個位置 new_node head … NULL ptr=NULL head new_node … NULL ptr head new_node … NULL ptr

插入節點 … … 狀況一：節點加於第一個節點之前 new_node (1) (4) head (2) NULL (3) ptr=NULL

插入節點 … … 狀況二：節點加於最後一個節點之後 head new_node (1) NULL NULL (2) ptr head

插入節點 … … 狀況三：加於節點中間任何一個位置 (1) (2) (3) (4) new_node head NULL ptr head

插入節點 將功能寫成程式之結果： node *insertNode(node *head, node *ptr, node data) { node *new_node; //新節點指標變數 new_node = (node *)malloc(sizeof(node)); //建立新節點,取得一個可用節點 *new_node = data; //建立節點內容 new_node->next = NULL; //設定指標初值 if(ptr == NULL) //第一種情況: 插入第一個節點 new_node->next = head; //新節點成為串列開始 head = new_node; } else if(ptr->next == NULL) //第二種情況: 插入最後一個節點 ptr->next = new_node; //最後指向新節點 else //第三種情況: 插入成為中間節點 new_node->next = ptr->next; //新節點指向下一節點 ptr->next = new_node; //節點ptr指向新節點 return head; //回傳串列起始位置

應用範例 (插入資料於串列最後) 寫一個使用者介面，功能如下(chap02_ex.c)： 輸入i，接著輸入一個整數放在一個節點並插入於鏈結串列最 後。 輸入q後程式結束。 (可利用下面找出最後節點之函式) //尋找最後一個節點 node *findFinalNode(node *head) { node *ptr; //新節點指標變數 ptr = head; //指向串列起始 while(ptr->next != NULL) //如果ptr->next為NULL代表ptr為最後節點 ptr = ptr->next; } return ptr; //回傳最後節點位置 head 插入資料 30 10 50 30 NULL

練習 (插入資料於串列某位置) 寫一個使用者介面，功能如下： 輸入i，接著輸入一個整數放在一個節點並輸入插入鏈結串列 第幾個位置 (輸入位置範圍: 1～個數+1)。 輸入q後程式結束。 head 插入位置: 3 10 50 1 30 NULL head 10 50 30 1 NULL

搜尋節點 功能：走訪串列，找出目標節點位置 head 搜尋目標 30 10 50 30 5 … 1 d NULL ptr ptr ptr

搜尋節點 將功能寫成程式之結果： node *searchNode(node *head, int d) { node *ptr; ptr = head; //指向串列起始 while(ptr != NULL) //走訪串列 if (ptr->data == d) //判斷是否找到 return ptr; //回傳找到節點位置 } ptr = ptr->next; //指向下一節點 return NULL; //找不到, 回傳NULL

應用範例 (搜尋鏈結串列節點) 寫一個使用者介面，功能如下： 輸入i，接著輸入一個整數放在一個節點中，再將此節點插入 於鏈結串列最後。 輸入f，接著輸入一個整數，印出該整數是否存在鏈結串列中 輸入q後程式結束。

練習 寫一個使用者介面，功能如下： 輸入i，接著輸入一個整數放在一個節點中，再將此節點插入 於鏈結串列最後。 輸入f，接著輸入串列資料編號 (輸入編號範圍: 1～個數)， 印出該節點資料 輸入q後程式結束。 輸入編號: 3 10 50 30 1 共4個資料 NULL No.1 No.2 No.3 No.4

刪除節點 … … … 功能：刪除鏈結串列中一個節點 一個節點之刪除有三種情況： 刪除第一個節點 刪除最後一個節點 刪除中間任何一個節點 head … NULL ptr head … NULL ptr head … NULL ptr

刪除節點 狀況一：刪除第一個節點 (1) head (2) … NULL ptr head … NULL

刪除節點 狀況二：刪除最後一個節點 head previous NULL (1) … NULL (2) ptr head … NULL

刪除節點 狀況三：刪除中間任何一個節點 (1) head previous (2) … NULL ptr … NULL head

刪除節點 將功能寫成程式之結果： node *deleteNode(node *head, node *ptr) { node *previous; //用來指向要刪除目標之上一個節點 if (ptr == head) //第一種情況: 刪除第一個節點 head = head->next; } else previous = head; while(previous->next != ptr) //找要刪除目標之上一個節點 previous = previous->next; if(ptr->next == NULL) //第二種情況: 刪除最後一個節點 previous->next = NULL; //最後一個節點 else //第三種情況: 刪除中間節點 previous->next = ptr->next; //繞過刪除目標 free(ptr); //此函數將節點歸還給記憶體 return head; //回傳串列起始位置

應用範例 (刪除鏈結串列節點) 寫一個使用者介面，功能如下： 輸入i，接著輸入一個整數放在一個節點中，再將此節點插入 於鏈結串列最後。 輸入f，接著輸入一個整數，印出該整數是否存在鏈結串列中 輸入d，接著輸入一個整數，將鏈結串列中刪除一筆該整數資 料。 輸入q後程式結束。

練習 寫一個使用者介面，功能如下： 輸入i，接著輸入一個整數放在一個節點中，再將此節點插入 於鏈結串列最後。 輸入f，接著輸入一個整數，印出該整數是否存在鏈結串列中 輸入d，接著輸入串列編號(輸入編號範圍: 1～個數)，將鏈 結串列中資料刪除。 輸入q後程式結束。 輸入編號: 3 10 50 30 1 共4個資料 NULL No.1 No.2 No.3 No.4 10 50 1 剩3個資料 NULL No.1 No.2 No.3

印出鏈結串列內容 … 功能：印出鏈結串列所有節點內容 10 50 30 5 1 void listNode(node *head) { NULL ptr ptr void listNode(node *head) { node *ptr; ptr = head; //指向串列起始 while(ptr != NULL) //走訪串列 printf("%d\n", ptr->data); //印出目前節點內容 ptr = ptr->next; //指向下一節點 }

應用練習 (印出鏈結串列所有節點) 寫一個使用者介面，功能如下： 輸入i，接著輸入一個整數放在一個節點中，再將此節點插入 於鏈結串列最後。 輸入f，接著輸入一個整數，印出該整數是否存在鏈結串列中 輸入d，接著輸入一個整數，將鏈結串列中刪除一筆該整數資 料。 輸入l，印出鏈結串列中所有內容。 輸入q後程式結束。

大綱 鏈結串列 鏈結串列之資料型態 鏈結串列之基本運算 作業

作業一 使用鏈結串列製作一個通訊錄程式 功能 參考範例 輸入’i’ 新增節點在串列最後,可輸入姓名, 電話, Email 輸入’d’接著輸入姓名，可將一筆資料節點中之姓名相同者 刪除 輸入’f’接著輸入一個姓名，可將一筆資料節點中之姓名相 同者印出資料 輸入’l’ 印出串列所有節點內容並顯示目前人數 輸入’q’ 讀取離開程式 參考範例 http://www.csie.ntu.edu.tw/~d95027/train/download/DS_Addressbook.exe

繳交 使用FTP上傳 請使用FileZilla上傳作業至指定FTP主機 繳交期限：2010. 6/17(四) 主機： 使用者名稱： 密碼： 連接埠： 將程式存到自己學號之資料夾 (請自行新增) 檔名: ca1871XX_hw1_##.c XX為學號, ##為版本編號 Ex: ca187100_hw1_01.c (ca187100號同學 作業1 第1版) 請使用FileZilla上傳作業至指定FTP主機 繳交期限：2010. 6/17(四) 6/17 (四)上課公佈解答後,不再收作業