# 2020q3 Homework1 (lab0)
contributed by < `joey3639570` >
###### tags: `進階電腦系統理論與實作`

## 填坑日誌20200909 - 建立隨身Ubuntu系統
由於筆電空間不足，隨時連回桌電也不好切換系統，
決定以**隨身碟**作為 Ubuntu 的系統碟使用。

待辦如下：
- [x] 準備兩支隨身碟
- [x] 建立 ubuntu live usb 20.04
- 格式化隨身碟檔案系統為 **FAT32**
- 使用 Rufus 或 Unetbootin 建立 live usb
- [x] 建立 ubuntu 20.04 隨身系統
- 可以照[ASUS WIN10 筆電進入 BIOS](https://www.asus.com/tw/support/FAQ/1013015/)的方法進入 BIOS
- 調整開機順序為 Live USB 優先
- 安裝方法可參考[ Ubuntu 安裝步驟](https://blog.gtwang.org/linux/install-ubuntu-linux-to-usb-stick/)
- 不割 swap，只使用筆電主記憶體
:::warning
**注意** :zap:
分割磁區時務必設定 **mount point**, <br>不然會有 **root file system not defined** 的問題。
:::

## 填坑日誌20200914

作業目前先以 **WSL Windows Subsystem for Linux** 來寫
:::danger
:boom: WSL 會有一些套件無法安裝, 不是一個好方法！
:::

## 填坑日誌20200922
在不更動 `list_ele_t` 之 Data Structure 的狀況下，目前完成：
- `q_new`: 要記得加入`q->size = 0` 的初始化
- `q_free`: 如同提示，記得連同節點的元素逐一 `free` 掉
- `q_insert_head`: 別忽略增加 `q->size`
:::warning
:zap: 此處參考 `RinHizakura` ，使用更安全的 `strlcpy` ，確保複製後的 String 以 `\0` 為結尾。
在 `queue.c` 的開頭加上以下程式碼：

#ifndef strlcpy
#define strlcpy(dst, src, sz) snprintf((dst), (sz), "%s", (src))
#endif

:::

- `q_insert_tail`: 目前仿照 `quiz1` 之作法以 `pointer to pointer` 走到 queue 之尾巴再加上新節點，但此方法無法達到 **Time Complexity $O(1)$** ，需要額外進行修改
- `q_size`: 這裡也要記得避免 `q` 為 `NULL` 及 `q` 內無元素的狀況，容易忽略!
- `q_reverse`: 整體寫法與 quiz1 相同，使用 `pointer to pointer` ，需要注意資料結構上的不同便可

目前 `make test` 之分數：**66/100**

## 填坑日誌20200923
參考 `RinHizakura` ，更改 `list_ele_t` 之資料結構，新增一元素 `tail`　，詳細 `queue.h` 更改如下:

typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail;
    int size;
} queue_t;

此刻必須注意各函式的修改:
- `q_new`: 記得加上 `q->tail = NULL`
- `q_insert_head` 要特別注意原 queue 是空的狀況下， `tail` 即為剛插入的 node
- `q_insert_tail` 在有了 `tail` 之後，可以透過 `q->tail` 直接找到尾巴，便可以直接插入 node ，同時還是得注意 queue 是空的狀況下要去設定 `head`
- `q_reverse` 必須要思考到 `tail` 於反轉後便是 `head`

目前 `make test` 之分數：**77/100**

---
著手處理 `q_sort` ，嘗試使用 **merge_sort** 的概念撰寫
參考資料: [Comparison Sort: Merge Sort(合併排序法)](https://alrightchiu.github.io/SecondRound/comparison-sort-merge-sorthe-bing-pai-xu-fa.html)
>Merge Sort屬於Divide and Conquer演算法，把問題先拆解(divide)成子問題，並在逐一處理子問題後，將子問題的結果合併(conquer)，如此便解決了原先的問題。

所需之功能如下：
- `move`: Sort 所需之基本功能，移動節點到指定位置
- `split`: Merge Sort 會先需要**將問題拆成子問題**，此步用於將 queue內的內容分成**前後**兩個部份，在此參考 `RinHizakura` 使用以下方法取得 midpoint:

list_ele_t *first = head;
list_ele_t *second = head->next;
// First goes a step, Second goes two steps.
// When second reach the end, first will be the mid point.
while (second != NULL) {
    second = second->next;  // For the case when length is odd number.
    if (second != NULL) {
        first = first->next;
        second = second->next;
    }
}

*front_ref = head;
*back_ref = first->next;
first->next = NULL;

- `merge`: 題目要求以 `ascending order` 排列，在此使用 `strcmp(a,b)` 進行比較，回傳負值則代表a較小，在此參考 `RinHizakura` 使用一個 `dummy` 來保留結果，還要記得若 `a` 或 `b` 其中一者為 `NULL` 的狀況要判斷
- `sort`: 最終整合且包裝遞迴式的函式，先進行 `split` 找到當前的前後半，再分別對這兩半呼叫遞迴進行 `sort`，最終會把結果 `merge` 起來。

`q_sort` 最終會變成一個包裝 `sort` 及以 `q` 為傳入值導向的函式，記得傳進 `sort` 內的值要用 `&q->head`

目前 `make test` 之分數：**100/100**

---

使用 `make valgirnd` 做測試，但卡在`trace trace-17-complexity`
時間上花了將近20分鐘才測試完 `insert_tail` ，暫時先不測，但17以前的測試都正常。