CS162 - 9A - Review

TABLE OF CONTENTS

• Sections
  • Pointer
  • Dynamically allocated array
  • Linked List
  • Data abstraction
  • Stack (LIFO)
  • Queue (FIFO)
  • Recursion
  • Binary file
• Revision problems

Sections

Pointer

• CS161 - 1B

Dynamically allocated array

• CS162 - 1B/#array-allocation

Linked List

1. Singly Linked List
   • CS162 - 2B/#build-linked-list
   • CS162 - 3A
   • CS162 - 3B
2. Ordered Linked List
   • CS162 - 4A/#singly-ordered-linked-list
3. Doubly Linked List
   • CS162 - 4A/#double-linked-list
   • CS162 - 4B
4. Circular Linked List
   • CS162 - 5A
   • CS162 - 5B
   • CS162 - 5B (Bonus)

Linked List operations:

• Create the list
• Display the list
• Remove the whole list
• Search an element in the list
• Insert a new item into the list
  • beginning
  • after x
  • before x
  • …
• Remove a node from the list

Data abstraction

• Data members
• Member functions

$\Rightarrow$ Struct

Stack (LIFO)

• CS162 - 6A/#stack

2 operations:

• push
• pop

If implementation based on SLL:

• push at the beginning of SLL.
• pop at the beginning of SLL.

Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

struct MyStack {
    Node* pHead = nullptr;
    
    void push(Node* pNew);
    Node* pop();
};

void MyStack::push(Node* pNew) {
    pNew->pNext = pHead;
    pHead = pNew;
}

Node* MyStack::pop() {
    if(!pHead) return pHead;
    Node* tmp = pHead;
    pHead = pHead->pNext;
    return tmp;
}

Full code (runnable): here

Queue (FIFO)

• CS162 - 6A/#queue

2 operations:

• enqueue
• dequeue

If implementation based on SLL:

• dequeue at the beginning of SLL
• enqueue at the end of SLL.

Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

struct MyQueue {
    Node* pHead = nullptr;
    Node* pTail = nullptr;
    
    void enqueue(Node* pNew);
    Node* dequeue();
};

void MyQueue::enqueue(Node* pNew) {
    if(!pHead) {
        pHead = pNew;
        pTail = pNew;
        pHead->pNext = nullptr;
    } else {
        pTail->pNext = pNew;
        pTail = pTail->pNext;
    }
}

Node* MyQueue::dequeue() {
    if(!pHead) return nullptr;
    Node* tmp = pHead;
    pHead = pHead->pNext;
    if(!pHead) pTail = nullptr;
    return tmp;
}

Full code (runable): here

Recursion

• CS162 - 7B
• CS162 - 8A
• Types of recursion

Binary file

• CS162 - 8B

Revision problems

Given $N$ integer numbers: $x_0, x_1, \dots, x_{N-1}$ and an integer $X$, you are asked to implement a program to place basic arithmetic operators in between the $N$ numbers so that we achieve the following equation:

Hint

Ta có $N-1$ vị trí cần điền $4$ các phép toán cơ bản vào phương trình, vì thế ta có thể sinh tứ phân trong $O(4^N)$.

Vì phép $*$ và phép $/$ có thứ tự ưu tiên cao hơn phép $+$ và phép $-$, khi tính giá trị của vế trái của phương trình đề bài, ta có thể làm như sau:

Xét 2 phép toán đầu tiên trong dãy giá trị, ta sẽ có các trường hợp sau:

• Toán tử đầu tiên là $*$ hoặc $/$ thì ta tính giá trị của toán tử đó và thế vào vị trí tương ứng
• Toán tử đầu tiên là $+$ hoặc $-$ thì ta sẽ xết tới toán tử thứ 2:
  • Nếu toán tử thứ 2 cũng là $+$ hoặc $-$ thì ta sẽ tính giá trị của toán tử đầu tiên rồi thế vào vị trí tương ứng.
  • Nếu toán tử thứ 2 là $*$ hoặc $/$ thì ta sẽ tính giá trị của toán tử thứ 2 và thế vào vị trí tương ứng.

Vì ta phải tính giá trị của 1 toán tử và thay thế 2 tham số của toán tử đó thành 1 tham số duy nhất, ta có thể phải xóa 2 tham số của toán tử và thay bằng kết quả của toán tử. Để xử lý vấn đề này ta có thể đảo thứ tự của toàn bộ các số $x_i$ thành $x_{N-1}, x_{N-2}, \dots, x_0$ thì ta có thể xử lý các phép toán từ trên xuống.