---
# System prepended metadata

title: Quiz2 考試重點
tags: [Data Structure]

---

---
tags: Data Structure
---

<style>
    font {
        color: red;
    }
</style>

# Quiz2 考試重點

# Chap 3

## 1. Add to/delete from a stack, queue or circular queue using array. Data structure, program.

### Stacks
:::success
- A **stack** is an ordered list in which insertions and deleions are made at one end called the **top**.
- A stack is known as <font color=red>**First-In-Last-Out (FILO)**</font> list. 
:::

### Stack implementation (using array)
```c=
#define MAX_STACK_SIZE 100 /*maximum stack size*/
typedef struct {
    int key;
    /*other fields*/
} element;

element stack[MAX_STACK_SIZE];  //堆疊的陣列宣告 
int top = -1;		//堆疊的頂端
```

### Add to a Stack
```c=
void push(int *top, element item) {
// or void add(element stack[], int *top, element item) 
    
    // add an item to the global stack
    if (*top >= MAX_STACK_SIZE - 1) {
        stack_full();
        return ;
    }
    
    stack[++*top] = item;
}
```

### Delete from a Stack
```c=
element pop(int *top) {
// or element delete(element stack[], int *top)
    
    // return the top element from the stack
    if (*top == -1) return stack_empty(); // returns the error key
    return stack[(*top)--];
}
```

### Queues
:::success
- A **queue** is an ordered list in which all insertion take place one end, called **rear**, and all deletions take place at the opposite end called the **front**.
- A queue is known as <font color=red>**First-In-First-Out(FIFO)**</font> list.
:::

### Queue impelemtation 1 (using array)
Using a one dimensional array and two variables, ***front*** and ***rear***.
```c=
#define MAX_QUEUE_SIZE 100 // Maximum queue size
typedef struct {
    int key;
    // other field
} element;

element queue[MAX_QUEUE_SIZE];
int rear = -1;
int front = -1;
```

**Add to a Queue**
```c=
void addq(int *rear, element item) {
// or void addq(element queue[], int *rear, element item)
        
    // add an item to a queue
    if (*rear == MAX_QUEUE_SIZE - 1) queue_full();
    queue[++(*rear)] = item;
}
```

**Delete from a Queue**
```c=
element deleteq(int *front, int rear) {
// or element deleteq(element queue[], int *front, int rear)
    
    // remove element at the front of the queue
    if (*front == rear) return queue_empty();
    return queue[++(*front)];
}
```

### Queue implement 2: regard an array as a circular queue

**Add to a circular queue**
```c=
void addq(int front, int *rear, element item) {
    *rear = (*rear + 1) % MAX_QUEUE_SIZE;
    if (front == *rear) queue_full();
    
    queue[*rear] = item;
}
```
**Delete from a circular queue**
```c=
element deleteq(int *front, int rear) {
    element  item;
    // remove front element from the queue and put it in item
    
    if (*front == rear) return queue_empty();
    
    *front = (*front + 1) % MAX_QUEUE_SIZE;
    return queue[*front];
```





## 2. Convert the expressions between the infix and postfix (prefix) forms.

### Infix &rarr; Postfix
ex.
> $[2 + (3 * 4)]$ &rarr; $2 3 4 * +$

## 3. Algorithm and postfix expression using stack, time complexity.

### Representation
```c=
#define MAX_STACK_SIZE 100
#define MAX_EXPR_SIZE 100 // max size of expression

typedef enum {lparen, rparen, plus, minus, times, divide, mod, eos, operand} precedence;

int stack[MAX_STACK_SIZE];
char expr[MAX_EXPR_SIZE]; // input string 
```

### Get Token
```c=
// get the next token.
// symbol is the character representation, which is returned
// the token is represented by its enumerated value, which is returned in the function name.

precedence get_token(char *symbol, int *n) {
    *symbol = expr[(*n)++];
    switch (*symbol) {
        case '(': return lparen;
        case ')': return rparen;
        case '+': return plus;
        case '-': return minus;
        case '*': return times;
        case '/': return divide;    
        case '%': return mod;
        case ' ': return eos;
        default: return operand; // no error checking, default is operand.
    }
}
```

### Evaluation of Postfix Expression
```c=
// evaluate a postfix expression, expr, maintained as a global variable.
// '\0' is the end of the expression.
// The stack and top of the stack are global variables.
// get_token is used to return the tokentype and the character symbol.
// Operands are assumed to be single character digits.

int eval(void) {
    precedence token;
    char symbol;
    int op1, op2;
    int n = 0;
    int top = -1;
    token = get_token(&symbol, &n);
    
    while (token != eos) {
        if (token == operand) add(&top, symbol-'0'); // stack insert
        else {
            op2 = delete(&top);
            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);
                    break;
            }
        }
        token = get_token(&symbol, &n);
    }
    return delete(&top); 
}
```

### Evaluation of Expressions
![](https://i.imgur.com/71yqC7q.png)


## 4. Algorithm (procedures) to convert an infix expression to a postfix expression, time complexity.

### Algorithm to convert from infix to postfix
:::info
- Assumptions:
    - operators: (, ), +, -, *, /, %
    - operands: single digit integer or variable of one character

1. Scan string from left to right.
2. **Operands** are taken out immediately.
3. **Operators** are taken out of the stack as long as their <font>in-stack precedence (isp)</font> is **higher than or equal to** the <font>incoming precedence (icp)</font> of the new operator.
4. Stack operators till right parenthesis. Then unstack till corresponding left parenthesis.'**(**' has **low isp**, and **high icp**.
:::

```c=
// output the postfix of the expression.
// The expression string, the stack, and the top are global.

void postfix() {
    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);
        else if (token == rparen) {
            // unstack tokens until left parenthesis
            while (stack[top] != lparen) print_token(delete(&top));
            delete(&top); // discard the left parenthesis
        } else {
            // remove and print symbols whose isp is greater than or equal to the current token's icp
            while (isp[stack[top]] >= icp[token]) print_token(delete(&top));
            add(&top, token);
        }
    }
    while ((token = delete(&top)) != eos) print_token(token);
    printf("\n");
}
```

:::info
**Complexity: $\Theta(n)$**
- The total time spent here is $\Theta(n)$ as the number of tokens that get stacked and unstacked is linear in n.
- where n is the number of tokens in the expression.
:::


# Chap 4

## 1. Linked Stacks and Queues. E.g data structure, program.

### Dynamically Linked Stacks and Queues
:::info
- Easily add or delete a node form the top of the stack.
- Easily add a node to the rear of the queue and add or delete a node at the front of a queue.
:::

### Represent n stacks
```c=
#define MAX_STACKS 10
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 in the linked stack
```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 from the linked stack
```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;
}
```


### Represtent n queues
```c=
#define MAX_QUEUES 10
typedef struct queue *queue_pointer;
typedef struct queue {
    element item;
    queue_pointer link;
};

queue_pointer front[MAX_QUEUES], rear[MAX_QUEUES];
```

### Enqueue in the linked queue
```c=
void addq(queeu_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;
    }
    *rear = temp;
}
```

### Dequeue from the linked queue
```c=
element deleteq(queue_pointer *front) {
    // delete an element from 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;
}
```

## 2. Invert 1 chain or concatenate 2 chains. E.g program, time complexity.

### Chain
- A singly linked list in which the last node gaas a NULL link

### Inverting a chain
- For a list of *length* $\ge$ 1 nodes, the **while** loop is executed *length* times and so the computing time is linear or **O(*length*)**.
```c=
list_pointer invert(list_pointer lead) {
    // invert the last pointed to by lead
    
    list_pointer middle, trail;
    middle = NULL;
    while (lead) {
        trail = middle;
        middle = lead;
        lead = lead->link;
        middle->link = trail;
    }
    return middle;
}
```

### Concatenates two chains
```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(pty2)) {
            for (temp = ptr1; temp->link; temp = temp->link);
            temp->link = ptr2;
        }
        return ptr1;
    }
}
```
:::info
**Complexity: O(length of list ptr1)**
:::

## 3. Erase a circular list to an Available List. E.g program, time complexity.

### Erase a circular list in a fixed amount (**constant) of time <font>O(1)</font> independent of the number of nodes** in the list using **cerase**.
```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;
    }
}
```

## 4. Insert or delete node from a doubly linked list. E.g data structure, program.

### Doubly Linked Lists
- Doubly linked list has at least three fields
    - **left field (llink)**, **data field (item)**, **right link (rlink)**.
**The necessary declarations**
```c=
typedef struct node *node_pointer;
typedef struct node {
    node_pointer llink;
    element item;
    node_pointer rlink;
};
```
- Suppose that *ptr* points to any node in a doubly linked list, then:
:::info
- ptr = ptr->llink->rlink = ptr->rlink->llink
:::

### Insert node
```c=
void dinsert (node_pointer node, node_pointer newnode) {
    // insert newnode to the right of node
    
    newnode->llink = node;
    newnode->rlink = node->rlink;
    node->rlink = ->llink = newnode;
    node->rlink = newnode;
}
```

### Delete node
```c=
void ddelte(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;
        deleted->rlink->llink = deleted->llink;
        free(deleted);
    }
}
```


# Chap 5

## 1. Tree definition and basic of Binary tree. ppt. p.3-18.

### Introduction
**Definition** (recursively): A *tree* is a finite set of **one or more** nodes such that
- There is a specially designated node called ***root***
- Every node in the tree is the root of some ***subtree***.

:::success
Some **Terminology:**
- ***node:*** the item of information plus the branches to each node.
- ***degree:*** the number of subtrees of a node.
- ***degree of a tree:*** the maximum of the degree of the nodes in the tree.
- ***termianl nodes (or leaf):*** nodes that have degree **zero**.
- ***nonterminal nodes:*** nodes that don't belong to termianl nodes.
- ***children:*** the roots of the subtrees of a node X are the *children* of X.
- ***parent:*** X is the *parent* of its children.
- ***siblings:*** children of the same parent are said to be siblings.
- ***ancestors of a node:*** all the nodes along the path from the root to that node.
- ***the level of a node:*** defined by letting the root be at level one. If a node is at level *l*, then its children are at level *l+1*.
- ***height (or depth):*** the maximum level of any node in the tree.
:::

### Binary Tree
:::info
**Def:** A *binary tree* is a finite set of nodes that is either empty or consists of a **root** and **two disjoint binary trees** called the **left subtree** and **right subtree**.
:::

**Two special kinds of binary trees:**
(a) *skwed tree* (b) *complete binary tree*
![](https://i.imgur.com/dmCTHKf.png)


### Binary Tree Representation (Using Array)
::: info
**Lemma:** If a complete binary tree with n nodes is represented sequnetially, then for any node with index i, $1 \le i \le n$, we have:

1. **Parent(i)**: 
    - is at $\lfloor \frac{i}{2} \rfloor$ if $i \ne 1$. 
    - If $i = 1$, i is at the root and has no parent.
2. **LeftChild:**
    - is at **2i** if $2i \le n$.
    - If $2i > n$, then i has no left child.
3. **RightChild:**
    - is at **2i+1** if $2i+1 \le n$.
    - If $2i + 1 > n$, then i has no right child.
:::
![](https://i.imgur.com/eGazlCG.png)

![](https://i.imgur.com/hYvn16g.png)


## 2. Binary Tree Traversals (pre-, in-, post-, level-order) + codes. ppt. p.19-27.

### Binary Tree Traversal

![](https://i.imgur.com/bzk133P.png)

### <font color=red>Pre</font>order (<font color=red>V</font>LR)

```c=
void preorder(TreeNode root) {
    if (root) {
        printf("%d", root->val);
        preorder(root->left);
        preorder(root->right);
    }
}
```

### <font color=red>In</font>order (L<font color=red>V</font>R)

```c=
void inorder(TreeNode root) {
   if (root) {
       inorder(root->left);
       printf("%d", root->val);
       inorder(root->right);
   } 
}
```

### <font color=red>Post</font>order (LR<font color=red>V</font>)

```c=
void postorder(TreeNode root) {
    if (root) {
        postorder(root->left);
        postorder(root->right);
        printf("%d", root->val);
    }
}
```

### Iterative inorder traversal
- We use a stack to simulate recursion.
```c=
void iter_inorder (tree_pointer node) {
    int top = -1; // initail stack
    tree_pointer stack[MAX_STACK_SIZE];
    for (;;) {
        for (; node; node = node->left_child) {
            add(&top, node); // add to a stack
        }
        node = delete(&top) // delete from stack
        if (!node) break; // empty stack
        printf("%d", node->data);
        node = node->right_child;
    }
}
```

:::success
Let n be the number of nodes in the tree.
- **Time Complexity: O(n)**
    - Every node of the tree is placed on and removed from the stack exactly once.
- **Space Complexity: O(n)**
    - Equal to the depth of the tree.
    - **Skewed tree** is the worst case.
:::

### Level-order traversal (using 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 queue
    addq(front, &rear, ptr);
    for (;;) {
        ptr = deletq(&front, rear);
        if (rear) {
            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;
    }
}
```

## 3. Heaps (definition + each value being inserted into/delete from the tree) ppt. p.45-50. Textbook: Sect. 5.6(e.g exercise #1, p.229).

### Heaps

:::info
**Def:** A ***max(min) tree*** is a tree in which the key value in each node is **no smaller(larger)** than the key values in its children. A ***max(min) heap*** is a <font color=red>complete binary tree</font> that is also a max(min) tree.
::: 

### Priority Queues
- <font>Heaps is the only way to implement priority queue</font>.
- Heaps are frequently used to implement *priority queues*.
- delete the element with highest (lowest) priority.
- inset the element with arbitrary priority
![](https://i.imgur.com/M1INsoB.png)



### Insert into a Max Heap
```c=
//insert item into a max heap of current size *n
void insert_max_heap(element item, int *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];
        i /= 2;
    }
    heap[i] = item;
}
```
:::info
**Complexity = $O(log_2n)$**
:::


### Deletion from 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 largest 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;
}
```
:::info
**Complexity = $O(log_2n)$**
:::
