# 【資料結構與演算法】00 淺談DSA

[TOC]

<br>

---

## Part 1. 資料結構
程序 = 資料結構 + 演算法。

資料結構主要可分為 「線性結構」以及「非線性結構」。

### 線性結構
線性結構有兩種不同的儲存方式，分別為「順序儲存結構」和「鏈式儲存結構」 :

- 順序儲存結構
例如 : Stack (堆疊)、Queue (佇列)、Array (陣列)
- 鏈式儲存結構
例如 : Linked List (連結串列)

### 非線性結構
例如 : Tree、Graph

<img src='https://cdn.discuss.boardinfinity.com/original/2X/d/debab6838897d45c790fbb5da719c895483e5049.png'>

<br>

---
## Part 2. 如何撰寫 Pseudo Code (虛擬碼)

Good Pseudo Code 應該要符合以下條件 :
- **模組化 (modularize)**
- 他人可以讀懂
- 可以與一般的 definition 共用

Here is an example :

// SELECTION-SORT(A)
for i=1 to A.length
    m = GET-MIN-INDEX(A, i, A.length)
    SWAP(A[i], A[m])
return A    // which has been sorted in place

// GET-MIN-INDEX(A,i,r)
m = i    // store current min.index
for i=i+1 to r
    // update if i-th element smaller
    if A[m] > A[i] 
        m = i
return m

在以上的例子中，就不需要將 SWAP 的細節一一寫出來。

<br>

---

## Part 3. 演算法原則

- **input**
- **definiteness** : clear instructions (人要能看懂)
- **effectiveness** : feasible instructions (電腦要能做到)
- **finiteness** : completable instructions (跑得完)
- **output**

output (**correctness**) : needs proving with respect to requirements

<br>

---

## Part 4. 如何寫證明 ?

### Claim
- **Correctness** of GET-MIN-INDEX

Upon exiting GET-MIN-INDEX(A),

$$A[m] = \underset{1 \leq j \leq n}{\min} A[j] \text{ with n = A.length }$$

### Proof
Proof of Loop Invariant => correctness claim of algorithm

- **Invariant** within GET-MIN-INDEX

Upon finishing the loop with i = k,
donate m by $m_k$

$$A[m_k] \le A[j] \quad for \quad j = 1,2,...,k$$

**(loop) invariant: property that algorithm maintains**

- **Mathematical Induction**
- Base
when i = 2, invariant true because...
- Assume
assume invariant true for i = t-1;
when i = t, ...
- Proof