# Ch3
## compiler進行數學運算
為了讓compiler處理運算式(Expression)，我們需要
1. 把我們使用的infix(中置)表達式轉化成postfix(後置)表達式
2. 計算postfix(後置)表達式的結果
**1. infix轉postfix**
**2. postfix計算**
## infix轉postfix
### 流程
1. 決定運算式的先後順序
2. 取代常數後的右括號，並刪除括號
### 演算法
**時間複雜度**
* θ(n)
**資料結構**
利用一個Stack來儲存operators，並決定先後順序
* 輸入類別:
* operators: 運算元 (, ), +, -, *, /, %
* operands: 運算子(A, B, X...)
**isp & icp**
* in stack precedence (isp)是當前Stack最高元素的的operators(運算元)
* incoming precedence (icp)是指當前讀取到Expression的operators(運算元)
1. 如果遇到右括號，則會對Stack進行`pop()`並輸出運算元，直到在Stack中遇到左括號為止
2. 如果**isp高於等於當前的icp**，則會對Stack進行`pop()`並輸出運算元，直到滿足**isp低於當前的icp**
3. Operands會被直接輸出(Output)
**各運算元isp和icp的值**
**各運算元的英文表示**
### 詳細運作過程
### 程式碼
```c=
void postfix (void){
//output the postfix of the expression.
//The expression string, the stack, and top are global
char symbol;
precedence token;
int n = 0;
int top = 0;/* place eos on stack */
stack [0] = eos;
for (token = get_token(&symbol, &n);token != eos;token = get_token(&symbol, &n)){
if (token == operand)
printf ("%c", symbol);
//如果遇到右括號，則會對Stack進行pop()並輸出運算元，直到在Stack中遇到左括號為止
else if (token == rparen){ //rparen(右括號)
/* 對Stack進行`pop()`並輸出運算元，直到在Stack中遇到左括號為止 */
while (stack[top] != lparen) //lparen(左括號)
print_token(delete(&top));
delete(&top); //discard the left parenthesis
}else{
//如果isp高於當前的icp，則會對Stack進行pop()並輸出運算元，
//直到滿足isp高於當前的icp的情況
while (isp[stack[top]] >= icp[token])
print_token(delete(&top));
add(&top, token);
}
}
while ((token = delete(&top)) != eos)
print_token(token) ;
printf("\n");
}
```
## postfix計算
### postfix的compile過程
* 從表示式左邊到右邊
* 使用STACK儲存
### 資料結構
### 程式碼
```c=
int eval (void){
precedence token;
char symbol;
int op1, op2;
int n = 0;.//counter for the expression string
int top = -1;
token = get_token(&symbol, &n) ;
while (token != eos){
if (token == operand)
add (&top, symbol-'0'); /* stack insert */
else{
/* remove two operands, perform operation,
* and return result to the stack */
op2 = delete(&top) ://stack delete
op1 = delete(&top) ;
switch (token){
case plus: add(&top, op1+op2);break;
case minus: add(&top, op1-op2);break;
case times: add(&top, op1*op2);break;
case divide: add(&top, op1/op2);break;
case mod: add(&top, op1%op2);
}
}
token = get token (&symbol, &n) ;
}
return delete (&top); /* return result*/
}
```
# Ch4
## Linked Stack
### 資料結構
```c=
#define MAX_STACKS 10 /*maximum number ofstacks*/
typedef struct {
int key;
//other fields
}element;
typedef struct stack *stack_pointer;
typedef struct stack{
element item;
stack_pointer link;
};
stack_pointer top[MAX_STACKS];
```
### push() & pop()
**Push 程式碼**
```c=
void add(stack_pointer *top, element item){
/* add an element to the top of the stack */ Push
stack_pointer temp = (stack_pointer) malloc (sizeof (stack));
if (IS_FULL(temp)) {
fprintf(stderr, “ The memory is full\n”);
exit(1);
}
temp->item = item;
temp->link = *top;
*top= temp;
}
```
**pop 程式碼**
```c=
element delete(stack_pointer *top) {
/* delete an element from the stack */ Pop
stack_pointer temp = *top;
element item;
if (IS_EMPTY(temp)) {
fprintf(stderr, “The stack is empty\n”);
exit(1);
}
item = temp->item;
*top = temp->link;
free(temp);
return item;
}
```
## Linked queue
### 資料結構
```c=
#define MAX_QUEUES 10 /* maximum number of queues*/
typedef struct queue *queue_pointer;
typedef struct queue{
element item;
queue_pointer link
}
queue_pointer front[MAX_QUEUES], rear[MAX_QUEUES];
```
### addq & deleteq
**Addq 程式碼**
```c=
void addq(queue_pointer *front, queue_pointer *rear, element item){
/* add an element to the rear of the queue */
queue_pointer temp = (queue_pointer) malloc (sizeof (queue));
if (IS_FULL(temp)) {
fprintf(stderr, “ The memory is full\n”);
exit(1);
}
temp->item = item;
temp->link = NULL;
if(*front) (*rear)->link = temp;
else *front = temp; //如果queue為空
*rear = temp;
}
```
**deleteq 程式碼**
```c=
void deleteq(queue_pointer *front){
/* add an element to the rear of the queue */
queue_pointer temp = *front;
element item;
if (IS_EMPTY(*front)) {
fprintf(stderr, “ The queue is empty\n”);
exit(1);
}
item = temp->item;
*front = temp->link;
free(temp);
return item;
}
```
## Chain
**定義:**
* A singly linked list in which the last node has a null link
**Inverting chain(倒置):**
```c=
list_pointer invert(list_pointer lead){
/*invert the list pointed to by lead */
list_pointer middle,trail;
middle = NULL;
while (lead) {
trail = middle;
middle = lead,
lead = lead->link;
middle->link = trail;
}
return middle;
}
```
> 時間複雜度: O(n)
**Chain Concatenates(串接):**
```c=
list_pointer concatenate (list_pointer ptr1,list_pointer ptr2){
/*produce a new list that contains the list ptr1 followed by the list ptr2.
The list pointed to by ptr1 is changed permanently*/
list_pointer temp;
if(IS_EMPTY(ptr1)) return ptr2;
else{
if (!IS_EMPTY(ptr2)){
//從chain的lead找到最後一個元素
for(temp = ptr1; temp->link; temp = temp->link)
;
temp->link = ptr2;
}
}
return ptr1;
}
```
> 時間複雜度: O(n)
## Circular Linked list & Available List
### Circular Linked list
The link field of the last node points to the first node in the
list
### Available List
把不會用到的memory先進行保留，之後要使用時就不用再malloc和free了，可以加快程式效率
### Cerase
將一個list接在avail後面，當作刪除一個list
**程式碼**
```c=
void cerase (poly_pointer *ptr){
//erase the circular list ptr
poly_pointer temp;
if (*ptr){
temp = (*ptr)->link;
(*ptr)->link = avail;
avail = temp;
*ptr = NULL;
}
}
```
> 時間複雜度: O(1)
## Doubly Linked Lists
跟自己上一個和下一個節點各有連結(pointer)
### 資料結構
```c=
typedef struct node *node_pointer;
typedef struct node{
node_pointer llink; //上一個節點(左邊)
element item;
node_pointer rlink; //下一個節點(右邊)
};
```
### Insert node
**程式碼**
```c=
void dinsert(node_pointer node, node_pointer newnode){
// insert newnode to the right of node
newnode->llink = node; //步驟(1)
newnode->rlink = node->rlink; //步驟(2)
node->rlink->llink = newnode; //步驟(3)
node->rlink = newnode; //步驟(4)
}
```
### Delete node
**程式碼**
```c=
void delete (node_pointer node, node_pointer deleted){
/* delete from the doubly linked list*/
if (node == deleted)
printf ("Deletion of head node not permitted. \n");
else {
deleted->llink->rlink = deleted->rlink; //步驟(1)
deleted->rlink->llink = deleted->llink; //步驟(2)
free(deleted);
}
}
```
# Ch5
## Tree
Tree(樹)是由一個或多個節點所組成的有限集合，並且滿足：
* 存在且只有一個稱為root(樹根)的節點；
* 其餘的節點可以分割成任意正整數個(包含零個)互斥(disjoint)的集合：T1、...、Tn，其中每一個集合也都滿足樹的定義，這些集合又稱為這棵樹的subtree(子樹)。
**名詞定義**
* root(樹根)：樹中最上層的node
* siblings：擁有相同parent的node們
* external node：沒有child的node
* internal node：至少有一個child的node，稱為internal node
* level：定義root的level為1，其餘node的level為其parent的level加一
* height of tree：樹的height即為root的height
* degree(分歧度)：一個node擁有的subtree(子樹)的個數
* descendant(子嗣)：節點的子結點以及其子節點
* ancestor(祖先)：其父節點以及其父節點
> 來源:https://alrightchiu.github.io/SecondRound/treeshu-introjian-jie.html
## Binary tree representations (using link)
### 資料結構
```C=
typedef struct node *tree-pointer;
typedef struct node{
int data;
tree-pointer left-child, right-child;
};
```
### 索引順序種類
* LVR: 先讀左邊，資料中置
* LRV: 先讀左邊，資料後置
* VLR: 先讀左邊，資料前置
### Arithmetic Expression using binary tree
### Binary Tree Traversals
以上三種的程式碼結構和邏輯都差不多，只差在順序而已
### Inorder traversal (LVR) (recursive version)
```c=
void inorder(tree_pointer ptr){
/*inorder tree traversal */
if (ptr){
inorder(ptr->left_child); //L
printf("%d",ptr->data); //V
inorder (ptr->right_child); //R
}
}
```
### Inorder traversal (LVR) (Iterative version)
```c=
void iter_inorder (tree_pointer node){
int top = -1; /*initialize stack*/
tree_pointer stack[MAX_STACK_SIZE];
for (;;) {
for (; node; node = node->left_child)
add (&top, node) ; /* add to stack*/
node = delete(&top); //delete from stack
if(!node) break; /*empty stack*/
printf ("%d", node->data);
node = node->right_child;
}
}
```
> 時間複雜度: O(n) (n = node的數量)
### Level-order traversal (queue)
```c=
void level_order(tree_pointer ptr)
/* level order tree traversal */
{
int front = rear = 0;
tree_pointer queue[MAX_QUEUE_SIZE];
if(!ptr) return;/* empty tree */
addq (front, &rear, ptr);
for (;;) {
ptr = deleteq(&front, rear);
if(ptr){
printf("%d",ptr->data);
if(ptr->left_child)
addq(front,&rear,ptr->left_child);
if (ptr->right_child)
addq(front, &rear ,ptr->right_child);
}
else break;
}
}
```
## Heaps
### 定義
* Max heap()任何的父節點都會**大於等於**其子節點
* Min heap()任何的父節點都會**小於等於**其子節點
### Max Heap
### Min Heap
### 課本例題
Suppose that we have the following key values: 7,16,49,82,5,31,6,2,44
* Write out the max heap after each value is inserted into the heap.
* Write out the min heap after each value is inserted into the heap.
**參考解答:**
* Max heap
> 來源: 學習家
* Min heap
> 來源: 學習家(剛才誤刪，原本的答案就是對的)
:::warning
答案是我自己寫的，有錯在幫我糾正感謝
:::
### 演算法程式碼(不會考)
**Insertion Into A Max Heap(不會考)**
```c=
void insert_max_heap(element item, int n){
//insert item into a max heap of current size *n
int i;
if(HEAP_FULL(n)){
fprintf(stderr,"The heap is full.\n");
exit (1);
}
i = ++(*n);
while ((i != 1) && (item.key > heap[i/2].key)){
heap [i] = heap [i/2]; //parent sink
i /= 2: //item upheap
}
heap [i] = item;
}
```
> 時間複雜度: O(log2 n)
**Delection Into A Max Heap(不會考)**
```c=
element delete_max_heap (int *n){
//delete element with the highest key from the heap */
int parent, child;
element item, temp;
if(HEAP_EMPTY(*n)){
fprintf (stderr,"The heap is empty\n");
exit (1);
}
/* save value of the element with the highest key*/
item = heap (1);
/* use last element in heap to adjust heap*/
temp = heap [(*n)--];
parent = 1;
child = 2;
while (child <= *n){
//find the larger child of the current parent
if((child<*n)&&(heap[child].key<heap[child+1].key))
child++;
if (temp.key >= heap [child].key)
break;
//move to the next lower level
heap[parent] = heap[child];
parent = child;
child *= 2;
}
heap[parent] = temp;
return item;
}
```
> 時間複雜度: O(log2 n)
## Binary search tree
### 定義
* 每個節點都是不一樣的key
* 左節點會小於父節點
* 右節點會大於父節點
:::info
老師說要畫出tree的insertion和delection的結果
:::
### Inserting into a binary search tree
**時間複雜度:**
* O(logN) or O(h) h:樹的高度
### Deletion from a binary search tree
有可能發生三種情況:
1. 如果為leaf節點則直接刪除
2. 如果只有一個子節點，直接替換其父節點
3. 如果有兩個子節點
1. 從**左子樹尋找最大**節點並替換其父節點
2. 從**右子樹尋找最小**節點並替換其父節點
**時間複雜度:**
* O(logN) or O(h) h:樹的高度
Sign in with Wallet
Connect another wallet