Linked Data Structures Cheng-Chin Chiang
Introduction 鏈式資料結構 : 一種容器資料型態, 元素以節點 (Node) 形式儲存, 前後元素之間藉由單向或雙向指標互相連結 範例 串列 (Linked List) 樹 (Tree)
Nodes 每個節點可以宣告為一個 structure 或 class 記憶體靠動態配置產生 須包含指到其他節點的 pointers (links) struct ListNode { string item; int count; ListNode *link; }; typedef ListNode* ListNodePtr; ListNodePtr head; // 宣告一個串列的起點 ListNode
Accessing a Node 透過指標則使用 ->, 透過 dereference (*) 則用. (*head).count = 12; // 把 head 所指 node 中的 count 欄位設為 12 head->count = 12; // 同上 cin >> head->item; // 鍵盤輸入 head 所指 node 中的 item 欄位值
End Markers 一個鏈式資料結構必須有終點 將最後一個節點的指標欄位設為 NULL
Linked List 串列包含二個重要元素 第一個節點 ( 頭,head) 我們一定會在程式中儲存一個指標指向它 最後一個節點 ( 尾, tail 或 end) 此節點的指標欄位必為 NULL
Linked List Class Definition class IntNode { public: IntNode() { } IntNode(int thedata, IntNOde* thelink) : data(thedata), link(thelink) { } IntNode* getlink() const {return link;} int getdata() const {return data;} void setdata(int thedata) {data = thedata;} void setlink(intnode* pointer) private: int data; IntNode *link; }; typedef IntNode* IntNodePtr; {link=pointer;}
Create 1 st Node IntNodePtr head; 宣告一個節點指標, 預備使其指到串列頭 head = new IntNode; 動態配置第一個節點記憶體, 將 head 指到此節點 head->setdata(3); 設定節點資料值為 3 head->setlink(null); 此時因此節點為串列頭, 亦為串列尾, 所以將其指標欄位設為 NULL!
Adding a Node at the Head
Lost Nodes Pitfall
Inserting in the Middle of a Linked List (1 of 2)
Inserting in the Middle of a Linked List (2 of 2)
Removing a Node
Searching a Linked List Function with two arguments: IntNodePtr search(intnodeptr head, int target); //Precondition: pointer head points to head of //linked list. Pointer in last node is NULL. //If list is empty, head is NULL //Returns pointer to 1 st node containing target //If not found, returns NULL
Pseudocode for search Function while (here doesn t point to target node or last node) { Make here point to next node in list } if (here node points to target) return here; else return NULL; while (here->getdata()!= target && here->getlink()!= NULL) here = here->getlink(); if (here->getdata() == target) return here; else return NULL;
Doubly Linked Lists Doubly Linked List 每個節點有二個指標, 一個指向前元素, 另一個指向後繼元素 可以雙向跟尋 利用 NULL 標示二頭端點
Doubly Linked Lists class DoublyLinkedIntNode { public: DoublyLinkedIntNode ( ){} DoublyLinkedIntNode (int thedata, DoublyLinkedIntNode* previous, DoublyLinkedIntNode* next) : data(thedata), nextlink(next), previouslink(previous) {} DoublyLinkedIntNode* getnextlink( ) const { return nextlink; } DoublyLinkedIntNode* getpreviouslink( ) const { return previouslink; } int getdata( ) const { return data; } void setdata(int thedata) { data = thedata; } void setnextlink(doublylinkedintnode* pointer) { nextlink = pointer; } void setpreviouslink(doublylinkedintnode* pointer) { previouslink = pointer; } private: int data; DoublyLinkedIntNode *nextlink; DoublyLinkedIntNode *previouslink; }; typedef DoublyLinkedIntNode* DoublyLinkedIntNodePtr;
Adding a Node to the Front of a Doubly Linked List (1 of 2)
Adding a Node to the Front of a Doubly Linked List (2 of 2)
Deleting a Node from a Doubly Linked List (1 of 2)
Deleting a Node from a Doubly Linked List (2 of 2)
Stacks 堆疊 先進後出 (FILO) 或是 後進先出 (LIFO) 應用 追蹤 C++/C 中的函數呼叫 區域變數記憶體管理 模擬 可以利用串列來模擬堆疊
A Stack Graphic
Interface File for a Stack Template Class (1 of 2)
Interface File for a Stack Template Class (2 of 2)
Program Using the Stack Template Class (1 of 2)
Program Using the Stack Template Class (2 of 2)
Stack Push and Pop 新增資料到堆疊 push Recall: goes to "top" of stack 自堆疊移除資料 pop Recall: removed from "top" of stack Exercise by yourselves!
Queues 佇列 資料先進先出 (FIFO) 應用 尾進頭出 排隊買票 模擬 可以利用串列來模擬佇列
Interface File for a Queue Template Class (1 of 3)
Interface File for a Queue Template Class (2 of 3)
Interface File for a Queue Template Class (3 of 3)
Program Using the Queue Template Class
Hash Tables 雜湊 ( 赫序 ) 表 可以快速儲存與取出資料的對應表 ( 或映射 ) 我們將以單向串列來模擬 使用雜湊函數 將資料對應到索引 (Key) 在此以 string integer 為例
Simple Hash Function for Strings 函數輸出定義 : 將字串內所有字元的 ASCII 碼總和除以一數的餘數 此函數可以自行依照需要設計與定義 int computehash(string s) { int hash = 0; for (int i = 0; i < s.length( ); i++) { hash = hash + s[i]; } return hash % SIZE; // SIZE = 10 in example } Example: dog = ASCII 100, 111, 103 Hash = (100 + 111 + 103) % 10 = 4
Hash Table Operations 存入 (Store) 準備十個串列 加入一字串資料時, 先算出此字串之雜湊函數輸出值, 假設為 N 將新資料節點加入第 N 個串列中 取出 (Retrieve) 以輸入字串為索引, 計算雜湊函數輸出值, 假設為 N 從第 N 個串列中搜尋出此字串所在之節點
Constructing a Hash Table
Interface File for a HashTable Class (1 of 2) 1 // This is the header file hashtable.h. This is the interface 2 // for the class HashTable, which is a class for a hash table 3 // of strings. 4 #ifndef HASHTABLE_H 5 #define HASHTABLE_H 6 #include <string> 7 #include "listtools.h" The library "listtools.h" is the linked list library interface from Display 17.14. 8 using LinkedListSavitch::Node; 9 using std::string; 10 namespace HashTableSavitch 11 { 12 const int SIZE = 10; // Maximum size of the hash table array
Interface File for a HashTable Class (2 of 2) 13 class HashTable 14 { 15 public: 16 HashTable(); // Initialize empty hash table 17 // Normally a copy constructor and overloaded assignment 18 // operator would be included. They have been omitted 19 // to save space. 20 virtual ~HashTable(); // Destructor destroys hash table 21 bool containsstring(string target) const; 22 // Returns true if target is in the hash table, 23 // false otherwise 24 void put(string s); 25 // Adds a new string to the hash table 26 private: 27 Node<string> *hasharray[size]; // The actual hash table 28 static int computehash(string s); // Compute a hash value 29 }; // HashTable 30 } // HashTableSavitch 31 #endif // HASHTABLE_H
Implementation File for Hash Table Class (1 of 3) 1 // This is the implementation file hashtable.cpp. 2 // This is the implementation of the class HashTable. 3 #include <string> 4 #include "listtools.h" 5 #include "hashtable.h" 6 using LinkedListSavitch::Node; 7 using LinkedListSavitch::search; 8 using LinkedListSavitch::headInsert; 9 using std::string; 10 namespace HashTableSavitch 11 { 12 HashTable::HashTable() 13 { 14 for (int i = 0; i < SIZE; i++) 15 { 16 hasharray[i] = NULL; 17 } 18}
Implementation File for Hash Table Class (2 of 3) 19 HashTable::~HashTable() 20 { 21 for (int i=0; i<size; i++) 22 { 23 Node<string> *next = hasharray[i]; 24 while (next!= NULL) 25 { 26 Node<string> *discard = next; 27 next = next->getlink( ); 28 delete discard; 29 } 30 } 31 } 32 int HashTable::computeHash(string s) 33 { 34 int hash = 0; 35 for (int i = 0; i < s.length( ); i++) 36 { 37 hash = hash + s[i]; 38 } 39 return hash % SIZE; 40 }
Implementation File for Hash Table Class (3 of 3) 41 void HashTable::put(string s) 42 { 43 int hash = computehash(s); 44 if (search(hasharray[hash], s)==null) 45 { 46 // Only add the target if it's not in the list 47 headinsert(hasharray[hash], s); 48 } 49 } 50 } // HashTableSavitch
Hash Table Demonstration 1 // Program to demonstrate use of the HashTable class 2 #include <string> 3 #include <iostream> 4 #include "hashtable.h" 5 #include "listtools.cpp" 6 #include "hashtable.cpp" 7 using std::string; 8 using std::cout; 9 using std::endl; 10 using HashTableSavitch::HashTable; SAMPLE DIALOGUE Adding dog, cat, turtle, bird Contains dog? 1 Contains cat? 1 Contains turtle? 1 Contains bird? 1 Contains fish? 0 Contains cow? 0 11 int main() 12 { 13 HashTable h; 14 cout << "Adding dog, cat, turtle, bird" << endl; 15 h.put("dog"); 16 h.put("cat"); 17 h.put("turtle"); 18 h.put("bird"); 19 cout << "Contains dog? " << h.containsstring("dog") << endl; 20 cout << "Contains cat? " << h.containsstring("cat") << endl; 21 cout << "Contains turtle? " << h.containsstring("turtle") << endl; 22 cout << "Contains bird? " << h.containsstring("bird") << endl; 23 cout << "Contains fish? " << h.containsstring("fish") << endl; 24 cout << "Contains cow? " << h.containsstring("cow") << endl; 25 return 0; 26 17-43} Copyright 2008 Pearson Addison-Wesley. All rights reserved.
Hash Table Efficiency 最差狀況 (Worst Case) 全部資料都有相同的雜湊輸出值, 導致搜尋時要搜尋全部的節點才能找到資料 ( 或確定不存在 ) 最佳狀況 (Best Case) 每個料都有不同的雜湊輸出值, 如此只要搜尋僅包含一個節點即可找到資料 ( 或確定不存在 ) 好的雜湊表必須有好的雜湊函數 抉擇取捨 : 須靠大空間來換取低的雜湊碰撞 (Collision) 率
Set Template Class 集合包含多個不重複的元素 集合基本運算 Add Contains Union Intersection
Interface File for a Set Template Class (1 of 2) 1 // This is the header file set.h. This is the interface 2 // for the class Set, which is a class for a generic set. 3 #ifndef SET_H 4 #define SET_H 5 #include "listtools.h" "listtools.h" is the linked list library interface from Display 17.14. 6 using LinkedListSavitch::Node; 7 namespace SetSavitch 8 { 9 template<class T> 10 class Set 11 { 12 public: 13 Set() { head = NULL; } // Initialize empty set 14 // Normally a copy constructor and overloaded assignment 15 // operator would be included. They have been omitted 16 // to save space. 17 virtual ~Set(); // Destructor destroys set
Interface File for a Set Template Class (2 of 2) 18 bool contains(t target) const; 19 // Returns true if target is in the set, false otherwise 20 void add(t item); 21 // Adds a new element to the set 22 void output(); 23 // Outputs the set to the console 24 Set<T>* setunion(const Set<T>& otherset); 25 // Union calling object's set with otherset 26 // and return a pointer to the new set 27 Set<T>* setintersection(const Set<T>& otherset); 28 // Intersect calling object's set with otherset 29 // and return a pointer to the new set 30 private: 31 Node<T> *head; 32 }; // Set 33 } // SetSavitch 34 #endif // SET_H
Implementation File for a Set Template Class (1 of 4) 1 // This is the implementation file set.cpp. 2 // This is the implementation of the class Set. 3 #include <iostream> 4 #include "listtools.h" 5 #include "set.h" 6 using std::cout; 7 using std::endl; 8 using LinkedListSavitch::Node; 9 using LinkedListSavitch::search; 10 using LinkedListSavitch::headInsert; 11 namespace SetSavitch 12 { 13 template<class T> 14 Set<T>::~Set() 15 { 16 Node<T> *todelete = head; 17 while (head!= NULL) 18 { 19 head = head->getlink( ); 20 delete todelete; 21 todelete = head; 22 } 23 }
Implementation File for a Set Template Class (2 of 4) 24 template<class T> 25 bool Set<T>::contains(T target) const 26 { 27 Node<T>* result = search(head, target); 28 if (result == NULL) 29 return false; 30 else 31 return true; 32 } 33 void Set<T>::output() 34 { 35 Node<T> *iterator = head; 36 while (iterator!= NULL) 37 { 38 cout << iterator->getdata( ) << " "; 39 iterator = iterator->getlink( ); 40 } 41 cout << endl; 42 }
Implementation File for a Set Template Class (3 of 4) 43 template<class T> 44 void Set<T>::add(T item) 45 { 46 if (search(head, item) ==NULL) 47 { 48 // Only add the target if it's not in the list 49 headinsert(head, item); 50 } 51 } 52 template<class T> 53 Set<T>* Set<T>::setUnion(const Set<T>& otherset) 54 { 55 Set<T> *unionset = new Set<T>(); 56 Node<T>* iterator = head; 57 while (iterator!= NULL) 58 { 59 unionset->add(iterator- >getdata( )); 60 iterator = iterator->getlink( ); 61 } 62 iterator = otherset.head; 63 while (iterator!= NULL) 64 { 65 unionset->add(iterator- >getdata( )); 66 iterator = iterator->getlink( ); 67 } 68 return unionset; 69 }
Implementation File for a Set Template Class (4 of 4) 70 template<class T> 71 Set<T>* Set<T>::setIntersection(const Set<T>& otherset) 72 { 73 Set<T> *interset = new Set<T>(); 74 Node<T>* iterator = head; 75 while (iterator!= NULL) 76 { 77 if (otherset.contains(iterator->getdata( ))) 78 { 79 interset->add(iterator->getdata( )); 80 } 81 iterator = iterator->getlink( ); 82 } 83 return interset; 84 } 85 } // SetSavitch
Set Demonstration (1 of 3) 1 // Program to demonstrate use of the Set class 2 #include <iostream> 3 #include <string> 4 #include "set.h" 5 #include "listtools.cpp" 6 #include "set.cpp" 7 using std::cout; 8 using std::endl; 9 using std::string; 10 using namespace SetSavitch; 11 int main() 12 { 13 Set<string> round; // Round things 14 Set<string> green; // Green things 15 round.add("peas"); // Sample data for both sets 16 round.add("ball"); 17 round.add("pie"); 18 round.add("grapes"); 19 green.add("peas"); 20 green.add("grapes"); 21 green.add("garden hose"); 22 green.add("grass");
Set Demonstration (2 of 3) 23 cout << "Contents of set round: "; 24 round.output(); 25 cout << "Contents of set green: "; 26 green.output(); 27 cout << "ball in set round? " << 28 round.contains("ball") << endl; 29 cout << "ball in set green? " << 30 green.contains("ball") << endl; 31 cout << "ball and peas in same set? "; 32 if ((round.contains("ball") && round.contains("peas")) 33 (green.contains("ball") && green.contains("peas"))) 34 cout << " true" << endl; 35 else 36 cout << " false" << endl; 37 cout << "pie and grass in same set? "; 38 if ((round.contains("pie") && round.contains("grass")) 39 (green.contains("pie") && green.contains("grass"))) 40 cout << " true" << endl; 41 else 42 cout << " false" << endl;
Set Demonstration (3 of 3) 43 cout << "Union of green and round: " << endl; 44 Set<string> *unionset = round.setunion(green); 45 unionset->output(); 46 delete unionset; 47 cout << "Intersection of green and round: " << endl; 48 Set<string> *interset = round.setintersection(green); 49 interset->output(); 50 delete interset; 51 return 0; 52 } SAMPLE DIALOGUE Contents of set round: grapes pie ball peas Contents of set green: grass garden hose grapes peas ball in set round? 1 ball in set green? 0 ball and peas in same set? true pie and grass in same set? false Union of green and round: garden hose grass peas ball pie grapes Intersection of green and round: peas grapes
Iterators 迭代器 用來在鏈式結構中依序逐一拜訪節點元素的機制
Pointers as Iterators 我們可以利用指標來模擬迭代器 指標迭代器 : 範例 : Node_Type *iterator; for (iterator = Head; iterator!= NULL; iterator=iterator->link) Do_Action
Iterator Classes 我們也可自定一個比指標迭代器更多功能的迭代器類別 此迭代器類別可有下列運算子 : ++ 迭代器移到下一個節點 -- 迭代器移到上一個節點 == 比較迭代器是否相等!= 比較迭代器是否不相等 * 取得迭代器所指的節點 也可有下列成員函數 : begin(): 傳回第一個節點 end(): 傳回最後一個節點
Iterator Class Example 逐一拜訪並處理每個節點 : for (i=ds.begin();i!=ds.end();i++) process *i //*i is current data item i: variable name of iterator class
Trees 樹的資料結構較複雜 樹的每個資料節點可有多個指標指到其他節點 二元樹範例
Tree Structure: A Binary Tree (2 of 2)
Tree Properties 根節點 樹的頭 路徑 (Paths) 從根節點到其他任一節點的串列不能出現循環 二元樹 (Binary Trees) 除了葉結點外, 每個節點都有二個連結指到其他二個節點最常用到的樹 葉節點 二個連結指標都是 NULL( 不指到其他節點 )
Trees and Recursion 樹是一種遞迴結構 每棵二元樹都有二棵 子樹, 每個子樹又有二棵子樹, 依此類推 用在樹上的許多演算法都可用遞迴方式來設計 例如 : 樹中的資料搜尋
Binary Tree Processing Orders Preorder Processing: 1. 處理根節點資料 2. 處理左子樹 3. 處理右子樹 In-order Processing: 1. 處理左子樹 2. 處理根節點資料 3. 處理右子樹 Postorder Processing: 1. 處理左子樹 2. 處理右子樹 3. 處理根節點資料
Binary Search Tree (BST) Storage 通常依照特定順序儲存 1. 左子樹所有節點值小於根節點值 2. 右子樹所有節點值大於根節點值 3. 此規則適用於左子樹和又子樹中的節點和子樹 節點拜訪順序 Inorder values "in order Preorder "prefix" notation Postorder "postfix" notation