# 資料結構 (Data Structure) > 2018.1.11 AndyLee <style> .align-right { text-align: right; } .align-center { text-align: center; color: blue; } </style> ## Array ### 優點: * random access:只要利用index即可在O(1)時間對Array的資料做存取。 * 較Linked list為節省記憶體空間:因為Linked list需要多一個pointer來記錄下一個node的記憶體位置。 ### 缺點: * 新增/刪除資料很麻煩:若要在第一個位置新增資料,就需要O(N)時間把矩陣中所有元素往後移動。同理,若要刪除第一個位置的資料,也需要O(N)時間把矩陣中剩餘的元素往前移動。 * 若資料數量時常在改變,要時常調整矩陣的大小,會花費O(N)的時間在搬動資料(把資料從舊的矩陣移動到新的矩陣)。 ### 適用時機: * 希望能夠快速存取資料。 * **已知欲處理的資料數量**,便能確認矩陣的大小。 * 要求記憶體空間的使用越少越好。 ## Linked list ### 優點: * 新增/刪除資料較Array簡單,只要對O(1)個node(所有與欲新增/刪除的node有pointer相連的node)調整pointer即可,不需要如同Array般搬動其餘元素。 * 若是在Linked list的「開頭」新增node,只要O(1)。 * 若要刪除特定node,或者在特定位置新增node,有可能需要先執行O(N)的「搜尋」。 * Linked list的資料數量可以是動態的,不像Array會有resize的問題。 ### 缺點: * 因為Linked list沒有index,若要找到特定node,需要從頭(ListNode *first)開始找起,搜尋的時間複雜度為O(N)。 * 需要額外的記憶體空間來儲存pointer。 ### 適用時機: * 無法預期資料數量時,使用Linked list就沒有resize的問題。 * 需要頻繁地新增/刪除資料時。 * 不需要快速查詢資料。 --- ## Linked Node 與 Linked List定義 ```clike= // C++ code #include <iostream> using std::cout; using std::endl; class LinkedList; // 為了將class LinkedList設成class ListNode的friend, // 需要先宣告 class ListNode{ private: int data; ListNode *next; public: ListNode():data(0),next(0){}; ListNode(int a):data(a),next(0){}; friend class LinkedList; }; class LinkedList{ private: // int size; // size是用來記錄Linked list的長度, 非必要 ListNode *first; // list的第一個node public: LinkedList():first(0){}; void PrintList(); // 印出list的所有資料 void Push_front(int x); // 在list的開頭新增node void Push_back(int x); // 在list的尾巴新增node void Delete(int x); // 刪除list中的 int x void Clear(); // 把整串list刪除 void Reverse(); // 將list反轉: 7->3->14 => 14->3->7 }; ``` ## PrintList()列舉所有ListNode的value ![](https://github.com/alrightchiu/SecondRound/blob/master/content/Algorithms%20and%20Data%20Structures/BasicDataStructures/LinkedList/Insert_Delete_Reverse/f1.png?raw=true) ```clike= // C++ code void LinkedList::PrintList(){ if (first == 0) { // 如果first node指向NULL, 表示list沒有資料 cout << "List is empty.\n"; return; } ListNode *current = first; // 用pointer *current在list中移動 while (current != 0) { // Traversal cout << current->data << " "; current = current->next; } cout << endl; } ``` ## Push_front()開頭新增newNode資料 ![](https://github.com/alrightchiu/SecondRound/blob/master/content/Algorithms%20and%20Data%20Structures/BasicDataStructures/LinkedList/Insert_Delete_Reverse/f2.png?raw=true) ```clike= void LinkedList::Push_front(int x){ ListNode *newNode = new ListNode(x); // 配置新的記憶體 newNode->next = first; // 先把first接在newNode後面 first = newNode; // 再把first指向newNode所指向的記憶體位置 } ``` ## Push_back()尾巴新增newNode資料 ![](https://github.com/alrightchiu/SecondRound/blob/master/content/Algorithms%20and%20Data%20Structures/BasicDataStructures/LinkedList/Insert_Delete_Reverse/f4.png?raw=true) ![](https://github.com/alrightchiu/SecondRound/blob/master/content/Algorithms%20and%20Data%20Structures/BasicDataStructures/LinkedList/Insert_Delete_Reverse/f5.png?raw=true) ```clike= // C++ code void LinkedList::Push_back(int x){ ListNode *newNode = new ListNode(x); // 配置新的記憶體 if (first == 0) { // 若list沒有node, 令newNode為first first = newNode; return; } ListNode *current = first; while (current->next != 0) { // Traversal到最後一個node current = current->next; } current->next = newNode; // 將newNode接在list的尾巴 } ``` ## Delete 刪除資料為int x的node ![](https://github.com/alrightchiu/SecondRound/blob/master/content/Algorithms%20and%20Data%20Structures/BasicDataStructures/LinkedList/Insert_Delete_Reverse/f6.png?raw=true) ![](https://github.com/alrightchiu/SecondRound/blob/master/content/Algorithms%20and%20Data%20Structures/BasicDataStructures/LinkedList/Insert_Delete_Reverse/f7.png?raw=true) ![](https://github.com/alrightchiu/SecondRound/blob/master/content/Algorithms%20and%20Data%20Structures/BasicDataStructures/LinkedList/Insert_Delete_Reverse/f8.png?raw=true) ```clike= // C++ code void LinkedList::Delete(int x){ ListNode *current = first; ListNode *previous = 0; while (current != 0 && current->data != x) { // Traversal linked list previous = current; // 如果current指向NULL current = current->next; // 或是current->data == x } // 即結束while loop if (current == 0) { // list沒有要刪的node, 或是list為empty std::cout << "There is no " << x << " in list.\n"; return; }else if (current == first) { // 要刪除的node剛好在list的開頭 first = current->next; // 把first移到下一個node delete current; // 如果list只有一個node, 那麼first就會指向NULL current = 0; // 當指標被delete後, 將其指向NULL, 可以避免不必要bug return; }else { // 其餘情況, list中有欲刪除的node, previous->next = current->next; // 而且node不為first, 此時previous不為NULL delete current; current = 0; return; } } ``` ## Clear()清除整個Linked list ```clike= // C++ code void LinkedList::Clear(){ while (first != 0) { // Traversal ListNode *current = first; first = first->next; delete current; current = 0; } } ``` ## Reverse()反轉Linked list ![](https://github.com/alrightchiu/SecondRound/blob/master/content/Algorithms%20and%20Data%20Structures/BasicDataStructures/LinkedList/Insert_Delete_Reverse/f24.png?raw=true) 有了這三個指標後,要執行的步驟只有兩個: * 將current->next從原本指向preceding更新成指向previous,如圖。執行current->next=previous,就把node(3)的指向node(7)。 * 把三個指標「按照順序」往前移動,然後進行下一個node之pointer調整,如圖。 * previous=current,將previous移動到node(3)。 * current=preceding,將current移動到node(14)。 * preceding=preceding->next,將preceding移動到node(8)。 重複上述步驟,直到preceding更新成NULL,調整Linked list的first所指向的記憶體位置,即完成Linked list之反轉。 ![](https://github.com/alrightchiu/SecondRound/blob/master/content/Algorithms%20and%20Data%20Structures/BasicDataStructures/LinkedList/Insert_Delete_Reverse/f25.png?raw=true) ```clike= // C++ code void LinkedList::Reverse(){ if (first == 0 || first->next == 0) { // list is empty or list has only one node return; } ListNode *previous = 0; ListNode *current = first; ListNode *preceding = first->next; while (preceding != 0) { current->next = previous; // 把current->next轉向 previous = current; // previous往後挪 current = preceding; // current往後挪 preceding = preceding->next; // preceding往後挪 } // preceding更新成NULL即跳出while loop current->next = previous; // 此時current位於最後一個node, 將current->next轉向 first = current; // 更新first為current } ``` Reference: http://alrightchiu.github.io/SecondRound/linked-list-xin-zeng-zi-liao-shan-chu-zi-liao-fan-zhuan.html --- ## Stack 在以下Array實作Stack程式範例中,StackArray的private data有三項: * int top:記錄於stack中,最上面資料的index。 * int capacity:即為Array的size,也就是實際配置的記憶體大小。 * int *stack:這裡以int的Array來表示Stack。 ```clike= // C++ code #include <iostream> class StackArray{ private: int top; // index of top element int capacity; // allocated memory space of array int *stack; // array representing stack void DoubleCapacity(); // double the capacity of stack public: StackArray():top(-1),capacity(1){ // constructor stack = new int[capacity]; // initial state: top=-1, capacity=1 } void Push(int x); void Pop(); bool IsEmpty(); int Top(); int getSize(); }; ``` DoubleCapacity():因為利用Array來存放資料,所以有可能在不斷新增資料時,碰上一開始分配給Array的記憶體空間(capacity)不夠的情況,可以透過重新配置一個capacity為==兩倍大的Array來解決==。 更理想的做法是,能夠先對欲放進Stack處理的資料數量有個底,在初始化時,就把capacity設定在差不多的範圍,如此一來,不需要重複多次DoubleCapacity(),也不會過分浪費記憶體空間。 本篇文章提供的範例程式碼將capacity初始為11,主要是為了方便測試DoubleCapacity()。 ```clike= void StackArray::DoubleCapacity(){ capacity *= 2; // double capacity int *newStack = new int[capacity]; // create newStack for (int i = 0 ; i < capacity/2; i++) { // copy element to newStack newStack[i] = stack[i]; } delete [] stack; // release the memory of stack stack = newStack; // redirect stack to newStack } ``` Stack的基本處理資料的函式: **Push()** ```clike= void StackArray::Push(int x){ if (top == capacity - 1) { // if stack is full, double the capacity DoubleCapacity(); } stack[++top] = x; // update top and put x into stack } ``` **Pop()** ```clike= void StackArray::Pop(){ if (IsEmpty()) { // if stack is empty, there is nothing to pop std::cout << "Stack is empty.\n"; return; } top--; // update top // stack[top] = 0; // (*1) // stack[top].~T(); // (*2) } ``` **IsEmpty()** ```clike= bool StackArray::IsEmpty(){ // if (top == -1) { // return true; // } // else { // return false; // } return (top == -1); } ``` **Top()** ```clike= int StackArray::Top(){ if (IsEmpty()) { // check if stack is empty std::cout << "Stack is empty.\n"; return -1; } return stack[top]; // return the top element } ``` **getSize()** ```clike= int StackArray::getSize(){ return top+1; // return the number of elements in stack } ``` --- ## Queue Queue是具有**First-In-First-Out**的資料結構,Queue也具有以下特徵: 隊伍有前方(front)以及後方(rear)之分。 * 若要進入隊伍(Push),一定是從rear進入。 * 若要離開隊伍(Pop),一定是從front離開。 使用陣列來實作佇列,我們必須保留兩個旗標,假設front指向佇列的前端,rear向佇列的後端,我們每次從佇列後端加入一個資料,rear就加1指向最後一個資料,每次從佇列前端取出一個資料,front就加1指向佇列的最前端,如下圖所示: <div class="align-center"> ![](http://www.bcwhy.com/jdsf/AlgorithmGossip/images/queneByArray-1.jpg) </div> 這是最簡單的佇列實作,但是由於陣列的大小必須先決定,所以這種線性的結構有個問題,front與rear會到達陣列的後端,而這個陣列就不能再使用了,為了解決這個問題,將陣列當作**環狀**來使用,當front或rear到達陣列後端時,就重新從陣列前端再循環,也就是形成**環狀佇列**,如下圖所示: <div class="align-center"> ![](http://www.bcwhy.com/jdsf/AlgorithmGossip/images/queneByArray-2.jpg) </div> 不過陣列的容量還是受限制,所以這個陣列還是會滿的,當front = rear時,佇列就滿了; Queue的基本操作有五項:**新增佇列、加入資料、顯示前端資料、取出前端資料、顯示所有的佇列元素**。 ```clike= #include <stdio.h> #include <stdlib.h> #define N 10 void createq(int[], int*, int*); void showfront(int[], int, int); void add(int[], int*, int*, int); void del(int[], int*, int*); void showqueue(int[], int, int); int main(void) { int queue[N]; int front, rear; int input, select; createq(queue, &front, &rear); while(1) { printf("\n\n請輸入選項(-1結束):"); printf("\n(1)插入值至佇列"); printf("\n(2)顯示佇列前端"); printf("\n(3)刪除前端值"); printf("\n(4)顯示所有內容"); printf("\n$c>"); scanf("%d", &select); if(select == -1) break; switch(select) { case 1: printf("\n輸入值:"); scanf("%d", &input); add(queue, &front, &rear, input); break; case 2: showfront(queue, front, rear); break; case 3: del(queue, &front, &rear); break; case 4: showqueue(queue, front, rear); break; default: printf("\n選項錯誤!"); } } printf("\n"); return 0; } void createq(int queue[], int* front, int* rear) { int i; for(i = 0; i < N; i++) queue[i] = 0; *front = *rear = 0; } void showfront(int queue[], int front, int rear) { if(front == rear) printf("\n佇列為空!"); else printf("%d", queue[(front+1) % N]); } void add(int queue[], int* front, int* rear, int data) { int f, r; f = *front; r = *rear; r = (r+1) % N; if(f == r) { printf("\n佇列已滿!"); return; } queue[r] = data; *rear = r; } void del(int queue[], int* front, int* rear) { int f, r; f = *front; r = *rear; if(f == r) { printf("\n佇列為空!"); return; } f = (f+1) % N; *front = f; } void showqueue(int queue[], int front, int rear) { int i; printf("\n佇列內容:"); for(i = (front+1) % N; i <= rear; i++) printf("%d ", queue[i]); } ``` ## Traversal in Binary Tree ![](https://github.com/alrightchiu/SecondRound/blob/master/content/Algorithms%20and%20Data%20Structures/Tree%20series/BinaryTree_fig/Traversal/f2.png?raw=true) * **pre-order(VLR)**:當CurrentNode移動到A時,會先對A進行Visiting,接著前往left child進行Visiting,再前往right child進行Visiting。(若child指向NULL則忽略。) * **in-order(LVR)**:當CurrentNode移動到A時,會先對A的left child(B)進行Visiting,接著回到A進行Visiting,再前往right child(C)進行Visiting。(若child指向NULL則忽略。) * **post-order(LRV)**:當CurrentNode移動到A時,會先對A的left child(B)進行Visiting,再前往right child(C)進行Visiting,接著回到A進行Visiting。(若child指向NULL則忽略。)