---
# System prepended metadata

title: 資料結構第二次期中考前
tags: [學業共筆]

---

# Ch3

## compiler進行數學運算

為了讓compiler處理運算式(Expression)，我們需要
1. 把我們使用的infix(中置)表達式轉化成postfix(後置)表達式
2. 計算postfix(後置)表達式的結果

**1. infix轉postfix**

![image](https://hackmd.io/_uploads/r1m_zsbSa.png)

**2. postfix計算**

![image](https://hackmd.io/_uploads/SkTx9WGS6.png)


## infix轉postfix 

### 流程

1. 決定運算式的先後順序
2. 取代常數後的右括號，並刪除括號

![image](https://hackmd.io/_uploads/S14TP2WrT.png)

### 演算法

**時間複雜度**
* θ(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的值**

![image](https://hackmd.io/_uploads/r11ucWMrT.png)

**各運算元的英文表示**
![image](https://hackmd.io/_uploads/SJhWEzMrp.png)




### 詳細運作過程

![image](https://hackmd.io/_uploads/H1vSo-MS6.png)


### 程式碼

```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儲存

![image](https://hackmd.io/_uploads/ByZ8EibSp.png)

### 資料結構

![image](https://hackmd.io/_uploads/H1vXBsbrT.png)

### 程式碼
```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

![image.png](https://hackmd.io/_uploads/r1KuBnFXa.png)

### 資料結構

```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()

![image](https://hackmd.io/_uploads/HyZ7n17B6.png)



**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
![image.png](https://hackmd.io/_uploads/B1cFHhYXp.png)

### 資料結構

```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

![image](https://hackmd.io/_uploads/BkfR8lmS6.png)


**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

![image.png](https://hackmd.io/_uploads/HJ9HchYQT.png)


**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

![image.png](https://hackmd.io/_uploads/rkaunnFQp.png)

### Available List
把不會用到的memory先進行保留，之後要使用時就不用再malloc和free了，可以加快程式效率

![image](https://hackmd.io/_uploads/ByT1zW7Ha.png)


### Cerase
將一個list接在avail後面，當作刪除一個list

![image.png](https://hackmd.io/_uploads/HkIbSTFm6.png)


**程式碼**

```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)

![image.png](https://hackmd.io/_uploads/ryaucpF7a.png)

### 資料結構

```c=
typedef struct node *node_pointer;
typedef struct node{
    node_pointer llink; //上一個節點(左邊)
    element item;
    node_pointer rlink; //下一個節點(右邊)
};
```

### Insert node
![image](https://hackmd.io/_uploads/Hy9NAZ7ra.png)


**程式碼**
```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

![image.png](https://hackmd.io/_uploads/Skn8haF76.png)

**程式碼**
```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


![image.png](https://hackmd.io/_uploads/SJUy80KXa.png)

## Binary tree representations (using link)

![image](https://hackmd.io/_uploads/B1k2ggmEp.png)

### 資料結構

```C=
typedef struct node *tree-pointer;
typedef struct node{
int data;
tree-pointer left-child, right-child;
};
```

### 索引順序種類

* LVR: 先讀左邊，資料中置
* LRV: 先讀左邊，資料後置
* VLR: 先讀左邊，資料前置

![image](https://hackmd.io/_uploads/Hk6mzg7Ep.png)

### Arithmetic Expression using binary tree

![image](https://hackmd.io/_uploads/BymUmeQNT.png)

### 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
    }
}
```

![image](https://hackmd.io/_uploads/r1syFUQra.png)

### 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;
    }
}
```
![image](https://hackmd.io/_uploads/HJWtgwQrT.png)

## Heaps

### 定義
* Max heap()任何的父節點都會**大於等於**其子節點
* Min heap()任何的父節點都會**小於等於**其子節點

### Max Heap
![image](https://hackmd.io/_uploads/r1PgswmrT.jpg)


### Min Heap

![image](https://hackmd.io/_uploads/HJZMovXB6.png)

### 課本例題

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

![image](https://cdn.discordapp.com/attachments/1172456732698619904/1179454280651001906/2023-11-29_19.48_3.jpg?ex=6579d765&is=65676265&hm=da91e62069fcb2e7bd60324bb2d11b041f83728fe1fe315ce51ff14eb76ba6b8&)
> 來源: 學習家
* Min heap

![掃描全能王 2023-11-29 19.48_5](https://hackmd.io/_uploads/B1TaTBHrT.jpg)
> 來源: 學習家(剛才誤刪，原本的答案就是對的)

:::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
* 左節點會小於父節點
* 右節點會大於父節點

![image](https://hackmd.io/_uploads/SkWWgG7Vp.png)
:::info
老師說要畫出tree的insertion和delection的結果
:::
### Inserting into a binary search tree
**時間複雜度:**
* O(logN) or O(h) h:樹的高度

![image](https://cdn.discordapp.com/attachments/850204675232104478/1179066795420827678/IMG_2925.jpg?ex=65786e86&is=6565f986&hm=7e187e11769b2687cb8e9de1cba500ad4487dad21558100e118b434496e65c9f&)

### Deletion from a binary search tree
有可能發生三種情況:
1. 如果為leaf節點則直接刪除
2. 如果只有一個子節點，直接替換其父節點
3. 如果有兩個子節點
    1. 從**左子樹尋找最大**節點並替換其父節點
    2. 從**右子樹尋找最小**節點並替換其父節點

**時間複雜度:**
* O(logN) or O(h) h:樹的高度


![image](https://hackmd.io/_uploads/SyrvEGXNa.png)