# Data Structure
**資料結構重點：** 陣列、結構、鏈結串列、堆疊(stack)、佇列、樹狀結構、堆積(heap)、C++ STL 用法
**演算法重點：** 遞迴(費式數列)、排序演算法、搜尋演算法、DP
**物件導向重點：** 多形、多載、封裝、繼承、virtual、friend、父類別、子類別的建構子與解構子呼叫順序
**作業系統重點：** 死結與同步、process 與 thread 差別
**其他：** debug 的方式、程式語言的特性、不用 temp 來 swap 變數
###### tags: `軟韌體知識`
## 陣列 (Array)
使用陣列來儲存資料，並且做**搜尋(Search_data)**、**插入(Insert_data)**、**刪除(Delete_data)** 的動作，預設存的資料為字串 "abcdefg"
```c=
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Complexity: O(N)
int Search_data(char* data, char c){
for(size_t i=0; i<strlen(data); i++){
if(data[i] == c)
return i;
}
exit(-1);
}
// Complexity: O(N)
char* Insert_data(char* data, char c, int index){
char *result = (char*)malloc(strlen(data)+1);
for(size_t i=0; i<index; i++)
result[i] = data[i];
result[index] = c;
for(size_t i=index; i<strlen(data); i++)
result[i+1] = data[i];
return result;
}
// Complexity: O(N)
char* Delete_data(char* data, char c){
char *result = (char*)malloc(strlen(data)-1);
size_t j = 0;
for(size_t i=0; i<strlen(data); i++){
if(data[i] == c)
j--;
else
result[j] = data[i];
j++;
}
return result;
}
int main(void){
char data[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g'};
char buff;
int index;
printf("Data: %s\n\n", data);
printf("Which character you wanna search: ");
scanf("%c", &buff);
printf("The index of '%c' is %d\n\n", buff, Search_data(data, buff));
printf("Input the character you wanna insert: ");
scanf("\n%c", &buff);
printf("Input the index you wanna insert: ");
scanf("\n%d", &index);
printf("Data(new): %s\n\n", Insert_data(data, buff, index));
printf("Input the character you wanna delete: ");
scanf("\n%c", &buff);
printf("Data(new): %s\n\n", Delete_data(data, buff));
return 0;
}
```
由上面程式碼可以發現在陣列中做**搜尋(Search_data)**、**插入(Insert_data)**、**刪除(Delete_data)** 的複雜度都是 **O(N)**
<br/>
### 二維不規則陣列 (2-D Jagged Array)
```c=
/* illustration of dynamically allocated 2D array */
#include <stdio.h>
#include <stdlib.h>
int main()
{
int i; /* general purpose variable used for loop index */
int j; /* general purpose variable used for loop index */
int **a; /* this is the array name */
int size_x; /* this variable will be used for the first dimension */
int size_y; /* this variable will be used for the second dimension */
/* suppose we want an array of int: a[5][3] */
size_x = 5;
size_y = 3;
/* allocate storage for an array of pointers */
a = malloc(size_x * sizeof(int *));
/* for each pointer, allocate storage for an array of ints */
for (i = 0; i < size_x; i++) {
a[i] = malloc(size_y * sizeof(int));
}
/* just for kicks, show the addresses (note: not all sequential) */
/* assign an arbitrary value to each element */
for (i = 0; i < size_x; i++) {
for (j = 0; j < size_y; j++) {
printf("&a[%d][%d] = %p\n", i, j, &a[i][j]); /* show the addresses */
a[i][j] = i * size_y + j; /* just some unique number for each element */
}
printf ("\n");
}
/* now show the contents that were assigned */
for (i = 0; i < size_x; i++) {
for (j = 0; j < size_y; j++) {
printf("a[%d][%d] = %2d\n", i, j, a[i][j]);
}
printf ("\n");
}
/* now for each pointer, free its array of ints */
for (i = 0; i < size_y; i++) {
free(a[i]);
}
/* now free the array of pointers */
free(a);
return 0;
}
```
<br/>
## 動態陣列 (Dynamic array)
設計一個動態陣列，每當陣列裝滿資料，就另外建立兩倍大的新陣列，**將資料搬到新陣列(move)**，捨棄原陣列。
```c=
#include <stdio.h>
#include <stdlib.h>
int* move(int *num, int *size){
int *buffer = (int*)malloc(sizeof(int)**size);
for(size_t i=0; i<*size; i++){
buffer[i] = num[i];
}
num = (int*)malloc(sizeof(int)**size*2);
for(size_t i=0; i<*size; i++){
num[i] = buffer[i];
}
free(buffer);
*size *= 2;
return num;
}
int main(void) {
int size = 1;
int *num = (int*)malloc(sizeof(int)*size);
int i = 0;
while(1){
if(i == size)
num = move(num, &size);
printf("Input digit: ");
scanf("\n%d", &num[i]);
printf("Array: ");
for(int j=0; j<=i; j++){
printf("%d ", num[j]);
}
printf("\n");
i++;
}
free(num);
return 0;
}
```
**將資料搬到新陣列(move)** 的時間複雜度為 **O(N)**
<br/>
## 堆疊 (Stack)
堆疊是一種有序串列 (order list)，其加入或刪除數據的動作都在同一端 (top 端)。加入元素的動作稱為 Push，而刪除元素的動作稱為 Pop。由於堆疊 (Stack) 有著先進去的元素最後才會被搬出來的特性，因此又可稱為 LIFO (Last In First Out) 串列。
### 使用陣列實作堆疊
- **將資料插入堆疊中 (push)**
需要先定義一個 `top=-1` 變數作為此堆疊陣列的 index，也必須先定義好堆疊陣列的大小(MAX)
```c=
void push(char str[20]){
if(top>=MAX-1)
printf(KRED_L"\n[ERROR] Stack is full!\n");
else{
top++;
strcpy(item[top], str);
printf(KGRN_L"\n[SUCCESS] Insert OK!\n");
}
}
```
- **將資料從堆疊中刪除 (pop)**
每次刪除資料都只會刪除堆疊的最上層，也就是最後一個放進的資料，這是 stack 的特性。刪除資料很簡單，只需要把 top 這個 index 往下移一個就行
```c=
void pop(){
if(top<0)
printf(KRED_L"\n[ERROR] No data in stack.\n");
else{
top--;
printf(KGRN_L"\n[SUCCESS] Pop the top item.\n");
}
}
```
- **將堆疊中的全部資料列出 (list)**
將堆疊陣列中的資料列出，越晚放進的要越早輸出
```c=
void list(){
printf(KGRN_L"\nITEM\n");
printf("------------\n");
for(int i=top; i>-1; i--)
printf("%s\n", item[i]);
printf("------------\n");
}
```
- 下方為完整使用堆疊來處理**新增、刪除、輸出資料**的功能
```c=
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#ifndef _DEBUG_COLOR_
#define _DEBUG_COLOR_
#define KDRK "\x1B[0;30m"
#define KGRY "\x1B[1;30m"
#define KRED "\x1B[0;31m"
#define KRED_L "\x1B[1;31m"
#define KGRN "\x1B[0;32m"
#define KGRN_L "\x1B[1;32m"
#define KYEL "\x1B[0;33m"
#define KYEL_L "\x1B[1;33m"
#define KBLU "\x1B[0;34m"
#define KBLU_L "\x1B[1;34m"
#define KMAG "\x1B[0;35m"
#define KMAG_L "\x1B[1;35m"
#define KCYN "\x1B[0;36m"
#define KCYN_L "\x1B[1;36m"
#define WHITE "\x1B[0;37m"
#define WHITE_L "\x1B[1;37m"
#define RESET "\x1B[0m"
#endif
#define MAX 10
int top = -1;
char item[MAX][20];
void push(char str[20]){
if(top>=MAX-1)
printf(KRED_L"\n[ERROR] Stack is full!\n");
else{
top++;
strcpy(item[top], str);
printf(KGRN_L"\n[SUCCESS] Insert OK!\n");
}
}
void pop(){
if(top<0)
printf(KRED_L"\n[ERROR] No data in stack.\n");
else{
top--;
printf(KGRN_L"\n[SUCCESS] Pop the top item.\n");
}
}
void list(){
printf(KGRN_L"\nITEM\n");
printf("------------\n");
for(int i=top; i>-1; i--)
printf("%s\n", item[i]);
printf("------------\n");
}
int main(void){
int option;
char str[20];
while(1){
puts(KBLU_L"");
puts("|----------------------------------------|");
puts("|We provide the following functionality. |");
puts("|----------------------------------------|");
puts("|[1] Insert (Push) |");
puts("|[2] Delete (Pop) |");
puts("|[3] List all data |");
puts("|[4] Quit |");
puts("|----------------------------------------|");
printf(KYEL"\nEnter your choice: ");
option = getchar();
getchar();
switch((char)option){
case '1':
printf(KCYN"\nEnter the item(string) you want to add: ");
fgets(str, sizeof str, stdin);
strtok(str, "\n");
push(str);
break;
case '2':
pop();
break;
case '3':
list();
break;
case '4':
printf(KGRN_L"\n[SUCCESS] Quit.\n\n");
exit(0);
default:
printf(KRED_L"\n[ERROR] You enter the wrong command. Please try again.\n");
}
}
return 0;
}
```
<br/>
## 佇列 (Queue)
Queue 的操作模式是先進先出，類似於排隊的概念，排在前面的會先被輸出。
### 使用陣列實作佇列 (Queue)
- **將資料放入佇列中 (enqueue)**
需要預先定義兩個變數 `front=-1` 以及 `rear=-1`，`front` 代表最前的資料的 index，`rear` 代表最後面資料的 index。此外，也需要先定義好陣列的大小
```c=
void enqueue(char num[10]){
if(rear>=MAX-1)
printf(KRED_L"\n[ERROR] The Queue is full!\n");
else{
rear++;
strcpy(queue[rear], num);
printf(KGRN_L"\n[SUCCESS] Insert OK!\n");
}
}
```
- **將資料從佇列中刪除 (dequeue)**
原則就是越早放入的資料越先刪除，作法也很簡單，只需要將 `front++` 即可
```c=
void dequeue(){
if(front==rear)
printf(KRED_L"\n[ERROR] The Queue is empty.\n");
else{
front++;
printf(KGRN_L"\n[SUCCESS] Delete ok!\n");
}
}
```
- **列出佇列中所有資料 (list)**
```c=
void list(){
if(front==rear)
printf(KRED_L"\n[ERROR] The Queue is empty.\n");
else{
printf(KGRN_L"\nContent\n");
printf("-------------\n");
for(int i=front+1; i<=rear; i++)
printf("%s\n", queue[i]);
printf("-------------\n");
}
}
```
### 環狀佇列 (Circle queue)
實作前面一般的佇列會發現，每次 Dequeue 只是將 `front++`，這將會導致前面的位置被空出來 (如下圖)，而這是一件不合理且浪費空間的事
因為上面不合理的原因，佇列經常使用環狀佇列 (circle queue) 來表示
- **在環狀佇列中加入資料 (enqueue)**
```c=
void enqueue(char num[10]){
if((rear==MAX-1 && front==-1) || (rear+1)%MAX==front)
printf(KRED_L"\n[ERROR] Circle Queue is full!\n");
else{
rear = (rear+1) % MAX;
strcpy(queue[rear], num);
printf(KGRN_L"\n[SUCCESS] Insert ok!\n");
}
}
```
- **從環狀佇列中拿出資料 (dequeue)**
同樣秉持著先進先出的原則
```c=
void dequeue(){
if(front==rear)
printf(KRED_L"\n[ERROR] Circle Queue is empty.\n");
else{
front = (front+1) % MAX;
printf(KGRN_L"\n[SUCCESS] Delete ok!\n");
}
}
```
- **列出環狀佇列中的所有資料 (list)**
越早存進來的資料要越早輸出
```c=
void list(){
if(front==rear)
printf(KRED_L"\n[ERROR] Circle Qeueue is empty.\n");
else{
printf(KGRN_L"\nITEM\n");
printf("------------\n");
for(int i=(front+1)%MAX; ; i=(i+1)%MAX){
printf("%s\n", queue[i]);
if(i==rear)
break;
}
printf("------------\n");
}
}
```
- 以下用環狀佇列實作新增、刪除數據等功能
```c=
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#ifndef _DEBUG_COLOR_
#define _DEBUG_COLOR_
#define KDRK "\x1B[0;30m"
#define KGRY "\x1B[1;30m"
#define KRED "\x1B[0;31m"
#define KRED_L "\x1B[1;31m"
#define KGRN "\x1B[0;32m"
#define KGRN_L "\x1B[1;32m"
#define KYEL "\x1B[0;33m"
#define KYEL_L "\x1B[1;33m"
#define KBLU "\x1B[0;34m"
#define KBLU_L "\x1B[1;34m"
#define KMAG "\x1B[0;35m"
#define KMAG_L "\x1B[1;35m"
#define KCYN "\x1B[0;36m"
#define KCYN_L "\x1B[1;36m"
#define WHITE "\x1B[0;37m"
#define WHITE_L "\x1B[1;37m"
#define RESET "\x1B[0m"
#endif
#define MAX 3
int front = -1;
int rear = -1;
char queue[MAX][10];
void enqueue(char num[10]){
if((rear==MAX-1 && front==-1) || (rear+1)%MAX==front)
printf(KRED_L"\n[ERROR] Circle Queue is full!\n");
else{
rear = (rear+1) % MAX;
strcpy(queue[rear], num);
printf(KGRN_L"\n[SUCCESS] Insert ok!\n");
}
}
void dequeue(){
if(front==rear)
printf(KRED_L"\n[ERROR] Circle Queue is empty.\n");
else{
front = (front+1) % MAX;
printf(KGRN_L"\n[SUCCESS] Delete ok!\n");
}
}
void list(){
if(front==rear)
printf(KRED_L"\n[ERROR] Circle Qeueue is empty.\n");
else{
printf(KGRN_L"\nITEM\n");
printf("------------\n");
for(int i=(front+1)%MAX; ; i=(i+1)%MAX){
printf("%s\n", queue[i]);
if(i==rear)
break;
}
printf("------------\n");
}
}
int main(void){
int option;
char num[10];
while(1){
puts(KBLU_L"");
puts("|----------------------------------------|");
puts("|We provide the following functionality. |");
puts("|----------------------------------------|");
puts("|[1] Insert (Enqueue) |");
puts("|[2] Delete (Dequeue) |");
puts("|[3] List all data |");
puts("|[4] Quit |");
puts("|----------------------------------------|");
printf(KYEL"\nEnter your choice: ");
option = getchar();
getchar();
switch(option){
case '1':
printf(KCYN"\nEnter the item(int) you want to add: ");
fgets(num, sizeof num, stdin);
strtok(num, "\n");
enqueue(num);
break;
case '2':
dequeue();
break;
case '3':
list();
break;
case '4':
printf(KGRN_L"\n[SUCCESS] Quit.\n\n");
exit(0);
default:
printf(KRED_L"\n[ERROR] You enter the wrong command. Please try again.\n");
}
}
return 0;
}
```
<br/>
## 結構 (Struct)
結構的好處在於可以將多個相關的變數**包成自己需要的型態**，在此結合指標使用以順便複習
```c=
#include <stdio.h>
#include <stdlib.h>
typedef struct notebook{
char model[10];
char cpu[10];
char ram[5];
int price;
}notebook;
void Discount(notebook *n){
for(size_t i=0; i<3; i++)
n[i].price *= 0.8;
}
int main(void){
notebook n[3] = {
{"acer", "i5", "8G", 24000},
{"asus", "i3", "8G", 19500},
{"hp", "i7", "8G", 30500},
};
int length = (sizeof(n) / sizeof(n[0]));
for(size_t i=0; i<length; i++){
printf("Product %ld\n", i+1);
printf("MODEL: %s\n", n[i].model);
printf("CPU: %s\n", n[i].cpu);
printf("RAM: %s\n", n[i].ram);
printf("Price: NT.%d\n\n", n[i].price);
}
printf("=================\n\n");
printf("After discounting...\n");
Discount(n);
for(size_t i=0; i<length; i++){
printf("Product %ld\n", i+1);
printf("MODEL: %s\n", n[i].model);
printf("CPU: %s\n", n[i].cpu);
printf("RAM: %s\n", n[i].ram);
printf("Price: NT.%d\n\n", n[i].price);
}
printf("=================\n\n");
return 0;
}
```
<br/>
## 鏈結串列 (Linked list)
鏈結串列的好處為，當中間需要插入或刪除資料時，不需要動到其他資料，只需要將前後兩者的 Address 接上即可。
從鏈結串列中搜尋資料時(Search_data)，可以宣告一個 current 指標來尋找節點，並且同時定義一個 previous 指標來跟在 current 後面，當找到資料並且要將其刪除時，只需要 `previous->next = current->next`，接著再清除 current 即可，其複雜度為 O(N)。
需要從鏈結串列中插入資料時(Insert_data)，仍須先搜尋位址，故複雜度也是 O(N)。
```c=
#include <stdio.h>
#include <stdlib.h>
typedef struct Number{
int num;
struct Number *next;
}Number;
void Show_linked_list(Number *head){
Number *current = (Number*)malloc(sizeof(Number));
current = head;
printf("Data in linked list = ");
while(1){
printf("%d ", current->num);
current = current->next;
if(current->next == NULL){
printf("%d\n\n", current->num);
break;
}
}
}
Number* Delete_data(Number *head, int num){
Number *current, *previous;
current = head;
if(head->num == num){
head = head->next;
free(current);
} else {
while((current->next!=NULL)&&(current->num!=num)){
previous = current;
current = current->next;
}
if(current == NULL){
printf("Not found.\n");
} else{
previous->next = current->next;
free(current);
}
}
return head;
}
void Insert_data(Number *head, int num){
Number *current;
Number *new = (Number*)malloc(sizeof(Number));
current = head;
while(current->next!=NULL){
if(current->num==num){
new->next = current->next;
current->next = new;
new->num = 999;
break;
}
current = current->next;
}
if(current->next==NULL){
current->next = new;
new->num = 999;
new->next = NULL;
}
}
int main(void){
Number *head = (Number*)malloc(sizeof(Number));
Number *current;
int num;
printf("Type in 5 numbers\n");
printf("Number 1 = ");
scanf("\n%d", &num);
head->num = num;
head->next = NULL;
current = head;
for(int i=1; i<5; i++){
current->next = (Number*)malloc(sizeof(Number));
printf("Number %d = ", i+1);
scanf("\n%d", &num);
current = current->next;
current->num = num;
}
Show_linked_list(head);
printf("Which data you wanna delete = ");
scanf("\n%d", &num);
head = Delete_data(head, num);
Show_linked_list(head);
printf("Insert 999 after number ? = ");
scanf("\n%d", &num);
Insert_data(head, num);
Show_linked_list(head);
return 0;
}
```
<br/>
## 樹結構 (Tree)
- Tree 的相關術語
| Term | Remark |
| --------------------- | --------------------------------------------------------------- |
| **N 元樹** | 樹的一個 Node 最多擁有 N 個 Sub-Node |
| **二元樹 (Binary Tree)** | 樹的一個 Node 最多擁有 2 個 Sub-Node |
| **根節點 (Root)** | 沒有父節點的 Node 就是 Root |
| **葉節點 (Leaf)** | 沒有子節點的 Node 就是 Leaf |
| **祖先節點 (Ancenstors)** | 指從某節點到 Root 之間所經過的所有節點，都是此節點的 Ancenstors |
| **非終端節點 (Non-terminal Nodes)** | 除了 Leaf 之外的所有節點都是 Non-terminal Nodes |
| **分支度 (Degree)** | 指某個節點所擁有的子節點數量，例如下圖 B 節點的 Degree 為 2 |
| **階層 (Level)** | 一般將 Root 的 Level 視為 1，以下圖為例，A 節點的 Level=1，B~H 節點的 Level=2，I~M節點的 Level=3 |
| **深度 (Depth)、高度 (Height)** | 一顆 Tree 的總階層樹，以下圖為例，其 Depth=3 |
上圖的 Node A 為 Root，Node I、J、K、L、M 為 Leaf
### 二元樹 (Binary Tree)
陣列和單向鏈結串列都只能從頭至尾或從尾至頭執行單向「走訪」（Traverse），不過二元樹的每一個節點都擁有指向左和右 2 個子節點的指標，所以走訪可以有兩條路徑。
Binary Tree 的節點可以分成兩個沒有交集的子樹，左子樹 (Left Sub-tree) 和右子樹 (Right Sub-tree)
- 一棵深度為 h 的樹，最多擁有 $2^h-1$ 個節點
- 從上圖你可以發現規則性，左子樹節點的 Index 剛好是其父節點 Index 的 2 倍 ; 而右子樹節點的 Index 剛好是其父節點 Index 的 2 倍加 1
- 練習使用 Linked list 寫一個下圖的樹結構
> **注意：** 若使用 Linked list 來實作，則不存在 Index，Index 僅在 array 存在
```c=
#include <stdio.h>
#include <stdlib.h>
typedef struct binary_tree_node{
int data;
struct binary_tree_node *left_next;
struct binary_tree_node *right_next;
}Node;
int main(void){
Node *root = (Node*)malloc(sizeof(Node));
Node *current;
root->data = 5;
root->left_next = (Node*)malloc(sizeof(Node));
root->right_next = (Node*)malloc(sizeof(Node));
current = root;
current = current->left_next;
current->data = 4;
current->left_next = NULL;
current->right_next = NULL;
current = root;
current = current->right_next;
current->data = 6;
current->left_next = NULL;
current->right_next = NULL;
return 0;
}
```
- Binary Tree 的走訪過程是持續決定向左或向右走，直到沒有路可走。 Binary Tree 的走訪是一種**遞迴走訪**，根據遞迴函數中的呼叫排列順序不同，可以分成三種走訪方式
- 中序走訪 (Inorder Traversal)
- 前序走訪 (Preorder Traversal)
- 後序走訪 (Postorder Traversal)
- **中序走訪 (Inorder Traversal)**
```c=
void print_inorder(Node *ptr){
if(ptr != NULL){
print_inorder(ptr->left_next);
printf("[%d] ", ptr->data);
print_inorder(ptr->right_next);
}
}
```
> 上圖經 Inorder Traversal 後的結果為: [1] [2] [3] [4] [5] [6] [7] [8] [9]
- **前序走訪 (Preorder Traversal)**
```c=
void print_preorder(Node *ptr){
if(ptr != NULL){
printf("[%d] ", ptr->data);
print_preorder(ptr->left_next);
print_preorder(ptr->right_next);
}
}
```
> 上圖經 Preorder Traversal 後的結果為: [5] [4] [2] [1] [3] [6] [8] [7] [9]
- **後序走訪 (Postorder Traversal)**
```c=
void print_postorder(Node *ptr){
if(ptr != NULL){
print_postorder(ptr->left_next);
print_postorder(ptr->right_next);
printf("[%d] ", ptr->data);
}
}
```
> 上圖經 Postorder Traversal 後的結果為: [1] [3] [2] [4] [7] [9] [8] [6] [5]
- 學會二元樹的 Traversal 之後，就可以用來從樹中搜尋你要的資料
```c=
Node* Search_node(Node* ptr, int value){
Node *temp;
if(ptr!=NULL){
printf("data is %d\n", ptr->data);
if(ptr->data==value)
return ptr;
else{
temp = Search_node(ptr->left_next, value);
if(temp!=NULL)
return temp;
temp = Search_node(ptr->right_next, value);
if(temp!=NULL)
return temp;
}
}
return NULL;
}
```
- 求二元樹的最大深度 (Maximum Depth of BT)
```c=
int maxDepth(Node *root){
if(!root)
return 0;
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth);
}
```
<br/>
### 二元搜尋樹 (Binary Search Tree, BST)
- 也是一種二元樹，但是資料的排序擁有以下特性
- 每個節點所帶的值都不一樣
- 每個節點的值都大於左子節點的值且小於右子節點的值
- 節點的左子樹和右子樹也是一顆 Binary Search Tree
- 『**插入 (Insert_node)**』新節點到二元搜尋樹中
插入的方法非常簡單，只需要遵照二元搜尋樹的規則做插入就行。由於二元搜尋樹的特性，每一次比大小都可以踢除一半可能性，因此其最好的時間複雜度為樹的高度，也就是 O(logN)，最差即為樹的節點數量，也就是 O(N)。
```c=
Node *Insert_node(Node *root, int value){
Node *new = (Node*)malloc(sizeof(Node));
Node *parent;
Node *current;
new->data = value;
new->left_next = NULL;
new->right_next = NULL;
if(root==NULL)
return new;
current = root;
while(current!=NULL){
parent = current;
if(current->data>value)
current = current->left_next;
else
current = current->right_next;
}
if(parent->data>value)
parent->left_next = new;
else
parent->right_next = new;
return root;
}
```
- 從 BST 中『**搜尋 (Search_node)**』節點
搜尋也一樣，由於每次都可以剔除一半的條件，因此時間複雜度為樹的高度，也就是 O(logN)。我們可以跟前面一般二元樹的搜尋來做比較，由於一般二元樹只能透過遞迴法將所有節點 RUN 過一次來做搜尋，因此其運行速度慢，複雜度為 O(N)。
```c=
Node *Search_node(Node *ptr, int value){
while(ptr!=NULL){
if(ptr->data==value)
return ptr;
else if(ptr->data>value)
ptr = ptr->left_next;
else
ptr = ptr->right_next;
}
return NULL;
}
```
- **從 BST 中『刪除 (Delete_node)』節點**
要從 BST 刪除某節點的步驟會較為複雜，因為你必須保證在刪除某節點後，樹仍然能保有 BST 的特性，因此在刪除節點時，會有三種可能發生的 case 需要去考慮。
**1. 要刪除的節點剛好是葉子 (Leaf, 沒任何子節點)**
這是最簡單的狀況，因為刪除葉子 (Leaf) 並不會影響 BST 的特性，因此可以直接刪除即可。
> 這裡指的刪除都是讓其父節點指到 NULL 的意思
**2. 要刪除的節點擁有【一個】子節點**
若你要刪除的節點底下還有一個子節點 (左子或右子都沒差)，這也是簡單的狀況，只要讓自己的子節點接上自己的父節點即可。
**3. 要刪除的節點擁有【兩個】子節點**
這是最複雜的狀況，因為如果直接讓父子節點接在一起，可能會破壞 BST 特性。這裡提出了兩種做法，第一種是找自己左子樹中最大的值來替代掉自己，第二種是找右子樹中最小的值來替代掉自己。
<br/>
## C++ STL
STL (Standard Template Library) 中文叫標準模板庫，他是 C++ 的一個軟體庫，也是 C++ 標準程式庫的一部份。其中包含 4 個元件，分別是演算法、容器、疊代器。
### 【Container】 Vector
可以看成一個動態陣列，他會自動變動陣列大小
- 基本功能
- **push_back(value) :** 把一個值加到陣列最後面
- **pop_back( ) :** 把陣列最後面的值移除掉
- **size( ) :** 獲取陣列大小
- **vec[index] :** 獲取某一個 index 位置的值
- **back( ) :** 獲取尾巴的值
- **front( ) :** 獲取頭的值
- **簡單的 vector 容器操作**
```c=
#include <iostream>
#include <vector>
using namespace std;
int main(void){
vector<int> vec;
vec.push_back(10);
vec.push_back(20);
vec.push_back(30);
cout << "The length of this vector is " << vec.size() << endl;
for(int i=0; i<vec.size(); i++)
cout << vec[i] << " " ;
cout << endl << endl;
vec.pop_back();
cout << "After poping one time." << endl;
cout << "The length of this vector is " << vec.size() << endl;
for(int i=0; i<vec.size(); i++)
cout << vec[i] << " ";
cout << endl;
return 0;
}
```
<br/>
### 【Container】Queue
跟前面提到的佇列概念一模一樣，就像是排隊買東西，只能往尾巴排，然後從頭出來
- 基本功能
- **push(value) :** 把一個值加到尾巴
- **pop( ) :** 把一個值從頭移除掉
- **back( ) :** 獲取尾巴的值
- **front( ) :** 獲取頭的值
- **size( ) :** 獲取陣列大小
- **簡單的 Queue 容器操作**
```c=
#include <queue>
#include <iostream>
using namespace std;
int main(void){
queue<int> q;
q.push(10);
q.push(20);
q.push(30);
q.push(40);
while(q.size()!=0){
cout << q.front() << " ";
q.pop();
}
cout << endl;
return 0;
}
```
<br/>
### 【Container】Stack
跟前面提到的堆疊概念一模一樣，越晚放進去的會越早被拿出來
- 基本功能
- **push(value) :** 放一個值進去最上層
- **pop( ) :** 從最上層移除一個值
- **top( ) :** 獲取最上層的值
- **size( ) :** 獲取陣列大小
- **簡單的 Stack 容器操作**
```c=
#include <stack>
#include <iostream>
using namespace std;
int main(){
stack<int> s;
s.push(10);
s.push(20);
s.push(30);
while(s.size()!=0){
cout << s.top() << " ";
s.pop();
}
cout << endl;
return 0;
}
```
<br/>
### 【Container】Set
set 就是集合
- 基本功能
- **insert(value) :** 把一個值放進集合中
- **erase(value) :** 把某個值從集合中刪除
- **count(value) :** 檢查某個值是否存在集合中，存在則回傳 1，不存在回傳 0
- **簡單的 Set 容器操作**
```c=
#include <set>
#include <iostream>
using namespace std;
int main(void){
set<int> myset;
myset.insert(10);
myset.insert(20);
myset.insert(30);
myset.insert(40);
cout << myset.count(20) << endl;
cout << myset.count(100) << endl;
myset.erase(20);
cout << myset.count(20) << endl;
return 0;
}
```
<br/>
### 【Container】Map
Map 就像是一個對應表，用起來很類似 python 的 dictionary
- 基本功能
- **m[index] :** 獲取 index 對應的值
- **count(value) :** 檢查某個值是否存在對應值
- **簡單的 Map 容器操作**
```c=
#include <map>
#include <iostream>
using namespace std;
int main(void){
map<string, int> m;
m["one"] = 1;
m["two"] = 2;
m["three"] = 3;
m["four"] = 4;
cout << m.count("one") << endl;
cout << m.count("ten") << endl;
cout << m["one"] << endl;
cout << m["two"] << endl;
cout << m["three"] << endl;
cout << m["four"] << endl;
return 0;
}
```
<br/>
### 【Iterator】
Iterator 像是一個比較聰明的 pointer，它可以指到容器內的任何一個位置，然後操作那個位置的資料
```c=
#include <vector>
#include <iostream>
using namespace std;
int main(void){
int arr[] = {1, 2, 3, 4, 5};
vector<int> vec(arr, arr+5);
int len = vec.size();
/* 用 index 把 vec 印出來 */
for(int i=0; i<len; i++)
cout << vec[i] << endl;
/* -------------------- */
/* 用 iterator 把 vec 印出來 */
vector<int>::iterator begin = vec.begin();
vector<int>::iterator end = vec.end();
vector<int>::iterator it;
for(it=begin; it!=end; it++)
cout << *it << endl;
/* */
return 0;
}
```
Sign in with Wallet
Connect another wallet