# 2025q1 Homework2 (quiz1+2)
contributed by <`WenHsuanYu`>
## quiz 1
### 測驗 1
首先看到題目給定的 `list_t` 與節點 `list_item_t` 結構，便可得知是單向鏈結串列。
```c
#include <stddef.h>
typedef struct list_item {
int value;
struct list_item *next;
} list_item_t;
typedef struct {
struct list_item *head;
} list_t;
```
```graphviz
digraph structs {
node[shape=record];
rankdir=LR;
list_item_t [label="<value> value|<list_item_ptr>next"]
}
```
```graphviz
digraph structs {
node[shape=record];
rankdir=LR;
list_t[label="<list_item_ptr>head"]
}
```
其中 head 會指向頭節點 （如果頭節點存在的話）。
題目指出其關鍵操作 `list_insert_before` 函式的語意如下：
由此可得知，傳入參數 `l` 為指向串列的指標，而函式會走訪串列以定位插入位置傳入參數 `before` 會指向插入節點 `item` 的下一個位置。
當 `before` 指向頭節點，`item` 會插入到最前面；`before` 指向 `NULL`，`item` 會插入到最尾端。當 `before` 不屬於 `l` 所指向的串列的節點時，會導致未定義的行為。
此 `list_insert_before` 函式定義如下：
```c
list_item_t **p;
for (p = AAAA; *p != BBBB; p = CCCC)
;
*p = item;
DDDD = before;
```
依照該函式功能的註解，可推論一開始間接指標 p 指向偽節點位置(結構成員只有指標，而不具有值)，故 `AAAA` 為 `&l->head`，而迴圈會走訪每個節點(實際上 p 指向各個節點的 next 指標位置）直到註解所說定位到 `before` 之間的位置，由此可知 `BBBB` 為 `before`，而 `CCCC` 為 `&(*p)->next`，離開迴圈後，此時，間接指標 `p` 會指向 `before` 前節點的 `next` 指標，因此解參考（即 `*p`）很容易得到下一個節點，所以我們可以透過解參考的方式將該節點 next 指標指向插入節點 `item`，之後插入節點再跟原先的 before 連接起來，故 `DDDD` 為 `item->next`。
解釋 list_insert_before 函式，假設 ‵p‵ 已經走訪到 ‵before‵ 之前的節點，如下圖所示：
```graphviz
digraph list {
node[shape=record];
rankdir=LR
head [label="<head>head|<ref> "]
node1 [label="<name>node1| {<value>999|<next>next}"];
node2 [label="<name>node2| {<value>998|<next>next}"];
node3 [label="<name>node3| {<value>997|<next>next}"];
node4 [label="<name>node4| {<value>996|<next>next}"];
node5 [label="<name>node5| {<value>995|<next>next}"];
node6 [label="<name>node6| {<value> 994 |<next>next}"];
head:ref -> node1;
node1:next->node2;
node2:next->node3;
node3:next->node4;
node4:next->node5;
node5:next->node6;
before->node4
p->node3:next [label="next 指標的位置"]
}
```
接著，我們想要插入 `item` 節點，其值為 2， 其。
```graphviz
digraph list {
node[shape=record];
rankdir=LR
head [label="<head>head|<ref> "]
node1 [label="<name>node1| {<value>999|<next>next}"];
node2 [label="<name>node2| {<value>998|<next>next}"];
node3 [label="<name>node3| {<value>997|<next>next}"];
node4 [label="<name>node4| {<value>996|<next>next}"];
node5 [label="<name>node5| {<value>995|<next>next}"];
node6 [label="<name>node6| {<value> 994 |<next>next}"];
item [label="<name>item| {<value> 2|<next>next}"];
head:ref->node1;
node1:next->node2;
node2:next->node3;
node3:next->item [color=red];
item:next->node4 [color=blue];
node4:next->node5;
node5:next->node6;
before->node4:node4
p->node3:next
}
```
紅線表示插入 `item` 節點，與其相對應的程式碼如下：
```c
*p = item;
```
藍線表示插入節點指向 `before` 所指向的節點位置，與其相對應的程式碼如下:
```c
item->next = before;
```
**延伸問題**:
1. 解釋運作原理
程式流程如下：
- `main` 函數會呼叫 `test_suite` 函式，該函式會進行鏈結串列的插入測試，並針對函式回傳結果進行處理，印出相關測試資訊，最後將函式回傳結果進行兩次 `not` 運算，反映出測試正常（以 `0` 結束)或者測試異常（以 `1` 不正常結束）。
```c
int main(void)
{
printf("---=[ List tests\n");
char *result = test_suite();
if (result)
printf("ERROR: %s\n", result);
else
printf("ALL TESTS PASSED\n");
printf("Tests run: %d\n", tests_run);
return !!result;
}
```
- test_suite 函式透過巨集 `my_run_test` 來呼叫 `test_list` 測試函式，此巨集會接收傳入測試函式，並執行測試函式，檢查測試結果，若有錯誤訊息則將其回傳，否則在 `test_suite` 函式那一層會回傳 NULL，表示測試正常。
```c
#define my_run_test(test) \
do { \
char *message = test(); \
tests_run++; \
if (message) \
return message; \
} while (0)
int tests_run = 0;
static char *test_suite(void)
{
my_run_test(test_list);
return NULL;
}
```
- `test_list` 測試函式主要用於驗證鏈結串列操作的正確性，其測試流程如下：
- 初始化設定：
首先，透過呼叫 `list_reset` 函式來初始化全域節點陣列和鏈結串列。這會將每個節點的值設定為其對應的索引值，並清除所有現有的鏈結關係，確保測試環境的乾淨。
- 測試情境一：節點前端插入：
在這個測試中，我們模擬將所有節點（目前設定為 1000 個）依序從鏈結串列的最前端插入。插入完成後，我們會利用 `my_assert` 巨集檢查鏈結串列的總長度是否正確，並確認節點數值是否呈現反向排列，以驗證前端插入的邏輯無誤。
- 測試情境二：節點尾端插入：
接著，我們將所有節點（同樣是 1000 個）依序從鏈結串列的尾端插入。插入完成後，一樣會透過 `my_assert` 巨集來檢查鏈結串列的長度，並驗證節點數值是否呈現順向排列，以確保尾端插入的功能正常。
- 測試情境三：節點尾端插入
這個情境是任意順序方式插入，當前同測試情境二。
```c
#define my_assert(test, message) \
do { \
if (!(test)) \
return message; \
} while (0)
static list_item_t items[N];
static list_t l;
```
```c
static list_t *list_reset(void)
{
for (size_t i = 0; i < N; i++) {
items[i].value = i;
items[i].next = NULL;
}
l.head = NULL;
return &l;
}
```
```c
static char *test_list(void)
{
/* Test inserting at the beginning */
list_reset();
my_assert(list_size(&l) == 0, "Initial list size is expected to be zero.");
for (size_t i = 0; i < N; i++)
list_insert_before(&l, l.head, &items[i]);
my_assert(list_size(&l) == N, "Final list size should be N");
size_t k = N - 1;
list_item_t *cur = l.head;
while (cur) {
my_assert(cur->value == k, "Unexpected list item value");
k--;
cur = cur->next;
}
/* Test inserting at the end */
list_reset();
my_assert(list_size(&l) == 0, "Initial list size is expected to be zero.");
for (size_t i = 0; i < N; i++)
list_insert_before(&l, NULL, &items[i]);
my_assert(list_size(&l) == N, "Final list size should be N");
k = 0;
cur = l.head;
while (cur) {
my_assert(cur->value == k, "Unexpected list item value");
k++;
cur = cur->next;
}
/* Reset the list and insert elements in order (i.e. at the end) */
list_reset();
my_assert(list_size(&l) == 0, "Initial list size is expected to be zero.");
for (size_t i = 0; i < N; i++)
list_insert_before(&l, NULL, &items[i]);
my_assert(list_size(&l) == N, "list size should be N");
return NULL;
}
```
2. 撰寫合併排序操作
```c
/**
* Merges two singly-linked lists into a single sorted list.
*
* @param l Pointer to the head of the first sorted list.
* @param r Pointer to the head of the second sorted list.
* @return Pointer to the head of the merged sorted list.
*
* The function assumes that both input lists are sorted in ascending order.
* It iteratively selects the smaller head node from the two lists and appends it to the result list.
* The merged list reuses the nodes from the input lists; no new nodes are allocated.
*/
static list_item_t *merge_twolists(list_item_t *l, list_item_t *r)
{
list_item_t dummy;
list_item_t **indirect = &dummy->next;
dummy.next = NULL;
while(l && r) {
list_item_t **item = (l->value <= r->value) ? &l : &r;
*indirect = *item;
indirect = &(*indirect)->next;
*item = (*item)->next;
}
*item = a ? a : b;
return dummy.next;
}
/**
* @brief Sorts a singly linked list using the merge sort algorithm.
*
* This function implements the merge sort algorithm for singly linked lists.
* It recursively splits the list into two halves, sorts each half, and then
* merges the sorted halves back together.
*
* @param head Pointer to the head of the singly linked list to be sorted.
* @return Pointer to the head of the sorted linked list.
*/
static list_item_t *list_merge_sort(list_item_t *head)
{
if (!head || !head->next)
return head;
list_item_t *slow = head;
list_item_t *fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
list_item_t *mid = slow->next;
slow->next = NULL;
list_item_t *left = merge_sort_list(head);
list_item_t *right = merge_sort_list(mid);
return merge_twolists(left, right);
}
```
### 測驗 2
### 測驗 3
## quiz 2
### 測驗 1
### 測驗 2
### 測驗 3
Sign in with Wallet
Connect another wallet