陣列與鏈結串列 Array and Linked List

陣列與鏈結串列 Array and Linked List 講師 : 洪安 1

大綱 結構陣列 鏈結串列 單向鏈結串列之資料型態 單向鏈結串列之基本運算 課堂練習 2

結構陣列 優點 缺點 使用容易 class student int math; int english; int computer; ; 刪除與插入造成資料移動頻繁 浪費不必要之記憶體 int main() student s[5]; return 0; student student student student student math english computer 3 s [0] [1] [2] [3] [4]

動態記憶體配置 (1/2) new 運算子會配置一個 int 所需要的空間, 並傳回該空間的位址, 所以您使用指標 ptr 來儲存這個位址 int *ptr = new int; 如果要在配置完成後指定儲存值, 則可以如此宣告 int *ptr = new int(100); #include <iostream> using namespace std; int main() int *ptr = new int(100); cout << " 空間位置 :" << ptr << endl; cout << " 空間儲存值 :" << *ptr << endl; *ptr = 200; cout << " 空間位置 :" << ptr << endl; cout << " 空間儲存值 :" << *ptr << endl; delete ptr; 4 4 return 0;

動態記憶體配置 (2/2) 動態配置陣列空間 int *arr = new int[1000]; 歸還配置陣列空間給記憶體 delete [] arr; #include <iostream> using namespace std; int main() int size = 0; cout << " 請輸入陣列長度 :"; cin >> size; int *arr = new int[size]; cout << " 指定元素值 :" << endl; for(int i = 0; i < size; i++) cout << "arr[" << i << "] = "; cin >> *(arr+i); 5 5 cout << " 顯示元素值 :" << endl; for(i = 0; i < size; i++) cout << "arr[" << i << "] = " << *(arr+i) << endl; delete [] arr; return 0;

複習 : 動態記憶體配置 動態記憶體配置則是 : 當程式執行到一半, 發現它需要一塊記憶體空間來存放資料, 才向系統索取一塊記憶體空間 當此記憶體空間用不到時, 也可隨時將之釋放供其它程式使用 動態記憶體配置的特色 : 有需要, 才配置! 6

大綱 結構陣列 鏈結串列 單向鏈結串列之資料型態 單向鏈結串列之基本運算 課堂練習 7

鏈結串列 Linked List 定義 由一組節點 (node) 所構成 各節點之間並不一定占用連續的 Memory 空間 各節點的型態不一定相同 插入節點 刪除節點方便 因為只改變指標 僅支援循序存取, 不支援隨機存取 可任意 ( 動態 ) 增加 刪除空間 8

陣列與鏈結串列比較 9 陣列 占用連續的記憶體空間 各元素型態皆相同 不支援串列之共享 插入 刪除元素麻煩 ( 因為需挪移元素 ) 無法動態增加 刪除空間 可支援循序及隨機存取 可靠度高 循序存取速度快 可以非連續 鏈結串列 各節點型態不必一定相同 支援 方便 可以 僅支援循序存取 低, 因為指標斷裂, 資料就遺失 慢, 因為必須先讀取指標

靜態與動態結構 class node 資料型態變數名稱 ; // 如 : int data; node *next; ; node c; node *head; c.next = NULL; head = NULL; head = new node; head->next = NULL; node node * head node 資料型態 資料 變數名稱 資料型態 資料 變數名稱 node * NULL next node * NULL next 10 c (new)

鏈結串列節點 節點 : 鏈結串列中最基本的單位 資料 物件指標 節點 下一個節點 節點 = 資料 + 物件指標 11

定義鏈結串列節點結構 鏈結串列透過儲存元素在記憶體之位址為指標 (Pointer) 或鏈結 (Link) 取得下一個節點 定義節點結構 class node 資料型態變數名稱 ; // 如 : int data; node *next; ; 資料型態 node * node 資料 下一個節點 變數名稱 next 12

單向鏈結串列 單向鏈結串列之類別如下圖所示 head: 指向串列前端之指標 tail: 指向串列尾端之指標 head tail 鏈結起點 NULL 鏈結終點 13

走訪鏈結串列 從 head 開始 依序存取節點中的 next 指標 直到存取到 NULL 為止 範例 :print() 走訪鏈結串列並輸出每個節點之 data 值 14

小練習 ( 建立鏈結串列節點 ) 定義一個鏈結串列節點類別如下圖所示, 並使用 head 與 tail 指標指向動態配置之節點 node * head int node * node 10 NULL (new) node * tail data next 1. 請定義 Node 類別, 並設定 LinkedList 類別為其夥伴 (friend class LinkedList;) 2. 請定義 LinkedList 類別, 類別資料成員包含 head 與 tail 3. 請實作建構函數, 內容包含新增一個節點, 設定 data 為 10, 設定 next 為 NULL, 並讓 head 和 tail 指到此新增節點 4. 請實作 print() 函數 15 答案在 7-15.cpp, 請先自己試試看唷

大綱 結構陣列 鏈結串列 單向鏈結串列之資料型態 單向鏈結串列之基本運算 課堂練習 16

新增節點 動態配置一節點之記憶體 node *LinkedList::getnode () /* 此函數產生一個新節點 */ node *p; p = new node; if ( p == NULL) cout << " 記憶體不足 " << endl; exit(1); return(p); 17

釋放節點 歸還一個節點之記憶體 void LinkedList::freenode (node *p) /* 此函數將節點還給記憶體 */ delete p; 18

插入節點 由鏈結串列加入一個節點 一個節點之插入有三種情況 : 節點加於第一個節點之前 new head tail ptr 節點加於最後一個節點之後 head NULL tail new 加於節點中間任何一個位置 head new ptr NULL tail 19 ptr NULL

插入節點 加於節點中間任何一個位置 new (2) (1) head (3) tail ptr (4) NULL head new tail ptr NULL 20

插入節點 void LinkedList::insert_node(Node *ptr, int value) Node *new_node = getnode(); new_node -> data = value; new_node -> next = NULL; if (ptr == NULL) // 加在串列首 new_node -> next = head; head = new_node; else if (ptr == tail) ptr -> next = new_node; tail = tail -> next; // 等同於 tail = new_node; else // 加在串列中間 new_node -> next = ptr -> next; ptr -> next = new_node; // 加在串列尾等同於 ptr->next == NULL; 21

插入節點前的動作 找到插入的位置指標, 傳給 insert_node(node *ptr, int value) void LinkedList::insert(int value) if(head==null) else // 串列為空 head = getnode(); head->data=value; head->next=null; tail = head; // 串列不為空 insert_node(tail, value); cout << "Insert Successful!" << endl; 22

小練習 ( 插入鏈結串列節點 ) 延續上一個練習 修改建構函數為設定 head, tail 為 NULL 寫一個使用者介面, 輸入 i, 接著輸入一個數字 value, 可插入一筆資料節點中之 data 為 value 於串列最後 (insert, insert_node functions) 輸入其他則印出串列內容並結束 建立一個鏈結串列如下圖所示 : 答案在 7-23.cpp, 請先自己試試看唷 node * head node * tail node node node int 10 20 30 data 23 node * (new) (new) NULL (new) next

刪除節點 由鏈結串列中刪除一個節點 一個節點之刪除有三種情況 : 刪除第一個節點 head tail ptr 刪除最後一個節點 head tail NULL NULL NULL 刪除中間任何一個節點 head previous tail 24 ptr NULL

刪除節點 刪除中間任何一個節點 head previous tail NULL ptr head previous (1) tail 25 ptr (2) NULL

26 刪除節點 void LinkedList::remove_node(Node *ptr) if (ptr == head) /* 第一種情況 : 刪除第一個節點 */ head = head -> next; else // 尋找 ptr 的前一個節點 Node *prev = head; /* 指向前一節點 */ while (prev -> next!= ptr) prev = prev -> next; /* 第二種情況 : 刪除最後一個節點 */ if (ptr == tail) /* 最後一個節點 */ prev -> next = NULL; tail = prev; /* 第三種情況 : 刪除中間節點 */ else prev -> next = ptr ->next; /* 圖 (3) 之步驟 (1) */ freenode(ptr); /* 此函數將節點歸還給記憶體 */

27 找到刪除節點的位置

小練習 ( 刪除鏈結串列節點 ) 延續上一個練習 寫一個使用者介面, 輸入 d, 接著輸入一個數字 value, 可將一筆資料節點中之 data 與 value 相同者刪除 ( 假設輸入之 value 不會重覆 ) 28 答案在 7-28.cpp, 請先自己試試看唷

尋找節點 走訪串列, 尋找輸入和資料相同的節點 29

小練習 ( 尋找鏈結串列節點 ) 延續上一個練習 寫一個使用者介面, 輸入 f, 接著輸入一個數字 value, 可將一筆資料節點中之 data 與 value 相同者印出資料 30 答案在 7_LinkedList.cpp, 請先自己試試看唷

鏈結串列長度 計算鏈結串列之長度 31 int LinkedList::length () /* 此函數計算節點之鏈結長度 */ int num=0; node *q = head; while (q!= NULL) num ++; q = q->next; return(num);