# 2025q1 Homework2 (quiz1+2) contributed by < [Hlunlun](https://github.com/Hlunlun) > ## 第一周 ### [測驗 1](https://hackmd.io/@sysprog/linux2025-quiz1#%E6%B8%AC%E9%A9%97-1) 實做 `list_insert_before()` 這個函數，並使用到 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list) 中指標指標的技巧 函數定義的參數有三個指標變數，`l` 指向 `list` ，`before` 指向預添加節點後所連接的節點，`item` 指向預添加節點，三個節點可能會呈現以下 ```graphviz digraph list_type{ rankdir=LR; node [shape=record]; // Improve edge routing splines=true; overlap=false; l[label="l", shape=none]; l_[label="<ref>list|<head>head"]; n0[label="<ref>n0|{0|<next>next}"] n1[label="<ref>n1|{1|<next>next}"] n2[label="<ref>n2|{8|<next>next}"] item[label="item", shape=none]; item_[label="<ref> n3|{5|<next>next}"]; before[label="before", shape=none]; l->l_:ref; item -> item_:ref; before -> n2:ref; l_:head->n0:ref; n0:next->n1:ref; n1:next->n2:ref; l-> l_ -> n0 -> n1 -> n2 [style=invis]; } ``` `list_insert_before()` 主要功能就是將 `n3` 接在 `n2` 之前 ```graphviz digraph list_type{ rankdir=LR; node [shape=record]; // Improve edge routing splines=true; overlap=false; l[label="l", shape=none]; l_[label="<ref>list|<head>head"]; n0[label="<ref>n0|{0|<next>next}"] n1[label="<ref>n1|{1|<next>next}"] n2[label="<ref>n2|{8|<next>next}"] item[label="item", shape=none]; n3[label="<ref> n3|{5|<next>next}"]; before[label="before", shape=none]; l->l_:ref; item -> n3:ref; before -> n2:ref; l_:head->n0:ref; n0:next->n1:ref; n1:next->n3:ref; n3:next->n2:ref; l-> l_ -> n0 -> n1 -> n3 -> n2 [style=invis]; } ``` 運用 指標的指標 技巧，首先將指標 `p` 指向指標 `l->head`，指標變數 `p` 中存放的是 指標 `l->head` 的記憶體位置，藉由檢查 `*p` 來避免直接使用空的 `l->head` 進行迭代 ```graphviz digraph list_type{ rankdir=LR; node [shape=record]; // Improve edge routing splines=true; overlap=false; l[label="l", shape=none]; l_[label="<ref>list|<head>head"]; n0[label="<ref>n0|{0|<next>next}"] n1[label="<ref>n1|{1|<next>next}"] n2[label="<ref>n2|{8|<next>next}"] item[label="item"]; item_[label="<ref> n3|{5|<next>next}"]; before[label="before", shape=none]; p[label="p" fontcolor="red", shape=none]; p->l_:head; l->l_:ref; item -> item_:ref; before -> n2:ref; l_:head->n0:ref; n0:next->n1:ref; n1:next->n2:ref; l-> l_ -> n0 -> n1 -> n2 [style=invis]; } ``` 接下來找到指向 `*before` 的指標，也就是在鍊結串列中進行迭代找到 `n1->next`，而指標的指標可以透過 `&(*p)->next` 取得 `*p` 指向的節點的 `next` 的記憶體位置，直到 `*p` 指向 `*before` 及停止如下圖 ```graphviz digraph list_type{ rankdir=LR; node [shape=record]; // Improve edge routing splines=true; overlap=false; l[label="l", shape=none]; l_[label="<ref>list|<head>head"]; n0[label="<ref>n0|{0|<next>next}"] n1[label="<ref>n1|{1|<next>next}"] n2[label="<ref>n2|{8|<next>next}"] item[label="item"]; item_[label="<ref> n3|{5|<next>next}"]; before[label="before", shape=none]; p0[label="p", fontcolor="red", shape=none]; p1[label="p", fontcolor="red", shape=none]; p[label="p", fontcolor="red", shape=none]; p0->l_:head[style="dashed"]; p1->n0:next[style="dashed"]; p->n1:next[color="red"]; l->l_:ref; item -> item_:ref; before -> n2:ref[color="green"]; l_:head->n0:ref; n0:next->n1:ref; n1:next->n2:ref[color="green" label="*p" fontcolor="green"]; l-> l_ -> n0 -> n1 -> n2 [style=invis]; } ``` 最後將目前 `p` 指向的指標 `n1->next` 指向 `*item` (也就是 `n3` )，最後用 `n3->next` 將 `*before` (也就是 `n2` ) 接在 `n3` 後面，至此即完成實做 `list_insert_before()` ```graphviz digraph list_type{ rankdir=LR; node [shape=record]; // Improve edge routing splines=true; overlap=false; l[label="l", shape=none]; l_[label="<ref>list|<head>head"]; n0[label="<ref>n0|{0|<next>next}"] n1[label="<ref>n1|{1|<next>next}"] n2[label="<ref>n2|{8|<next>next}"] item[label="item"]; n3[label="<ref> n3|{5|<next>next}"]; before[label="before", shape=none]; p[label="p" fontcolor="red", shape=none]; l->l_:ref; item -> n3:ref; before -> n2:ref; l_:head->n0:ref; n0:next->n1:ref; n1:next->n3:ref[color="red"]; p->n1:next n3:next->n2:ref[color="red"]; l-> l_ -> n0 -> n1 -> n2 [style=invis]; } ``` ## [測驗2](https://hackmd.io/@sysprog/linux2025-quiz1#%E6%B8%AC%E9%A9%97-2) ## [測驗3](https://hackmd.io/@sysprog/linux2025-quiz1#%E6%B8%AC%E9%A9%97-3)