---
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 → Postfix
ex.
> $[2 + (3 * 4)]$ → $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
## 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*
### 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.
:::
## 2. Binary Tree Traversals (pre-, in-, post-, level-order) + codes. ppt. p.19-27.
### Binary Tree Traversal
### <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
### 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)$**
:::
Sign in with Wallet
Connect another wallet