# 2025q1 Homework2 (quiz1+2)
contributed by < PigeonSir >
## w1 測驗 1
運用 "a pointer to a pointer" 技巧操作單向的鏈結串列，其中基本的結構體如下
```graphviz
digraph queue_context {
rankdir=TB;
node [shape=plaintext];
queue1 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR><TD COLSPAN="1" BGCOLOR="lightgray"><B> list_t </B></TD></TR>
<TR><TD PORT="n">next</TD></TR>
</TABLE>
>];
queue2 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR><TD PORT="p" COLSPAN="2" BGCOLOR="lightgray"><B> list_item_t </B></TD></TR>
<TR><TD>value</TD><TD PORT="n">next</TD></TR>
</TABLE>
>];
nullNode [label="NULL", shape=none];
queue1:n -> queue2:p [constraint=false];
queue2:n -> nullNode [weight=0, minlen=2, constraint=false];
}
```
### insert before
```c
static inline void list_insert_before(list_t *h, list_item_t *before, list_item_t *item)
{
list_item_t **p;
for (p = &h->head; *p != before; p = &(*p)->next)
;
*p = item;
item->next = before;
}
```
利用 p 做為指標的指標，指向當前節點的 next 的地址，對 p 執行 deference 可得到下一個節點的地址
與沒有使用指標的指標技巧的作法比較 :
```c
static inline void list_insert_before(list_t *h, list_item_t *before, list_item_t *item)
{
lsit_item_t *cur, *prev;
for (cur = h->head; cur != before; prev = cur, cur = cur->next)
;
prev->next = item;
item->next = cur;
}
```
使用 "a pointer to a pointer" 技巧後就不需要使用額外的指標紀錄拜訪過的節點 (prev)
### 測試程式
#### my_assert
```c
#define my_assert(test, message) \
do { \
if (!(test)) \
return message; \
} while (0)
```
定義 my_assert 宏用於觀察執行時遭遇的錯誤，這裡有一個疑問是為何要使用到 do while ，
### 圖例
要插入 node2 於 node3 以前
```graphviz
digraph g{
rankdir=LR;
node [shape=record];
l [label = "{<data>h |<ref>}"];
1 [label = "{<head>node 1} | {<data>1 |<ref>}"];
2 [label = "{<head>node 3} |{<data>3 |<ref>}"];
3 [label = "{<head>node 2} | {<data>2 |<ref>}"];
node [shape=none]
p;
before;
edge[weight=2];
l:ref:c -> 1:head [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
1:ref:c -> 2:head [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
2:ref:c -> NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
edge[weight=1];
p -> l:ref:s;
edge[weight=1]
before -> 2:head:n;
{ rank=max; 3;}
}
```
走訪鏈結串列直到 `*p == before` 時跳出迴圈，此時 p 紀錄的為 node1 中 next 的地址
```graphviz
digraph g{
rankdir=LR;
node [shape=record];
l [label = "{<data>h |<ref>}"];
1 [label = "{<head>node 1} | {<data>1 |<ref>}"];
2 [label = "{<head>node 3} |{<data>3 |<ref>}"];
3 [label = "{<head>node 2} | {<data>2 |<ref>}"];
node [shape=none]
p;
before;
edge[weight=2];
l:ref:c -> 1:head [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
1:ref:c -> 2:head [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
2:ref:c -> NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
edge[weight=1];
p -> 1:ref:s;
edge[weight=1]
before -> 2:head:n;
{ rank=max; 3;}
}
```
更新 *p (即 node1 的 next) 為 node2 ，最後再將 node3 接上於 node2 後便完成
```graphviz
digraph g{
rankdir=LR;
node [shape=record];
l [label = "{<data>h |<ref>}"];
1 [label = "{<head>node 1} | {<data>1 |<ref>}"];
3 [label = "{<head>node 3} |{<data>3 |<ref>}"];
2 [label = "{<head>node 2} | {<data>2 |<ref>}"];
node [shape=none]
p;
before;
null; // NULL 仍然保留作為節點名稱
edge[weight=2];
l:ref:c -> 1:head [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
1:ref:c -> 2:head [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
2:ref:c -> 3:head [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
3:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
edge[weight=1];
p -> 1:ref:s;
edge[weight=1]
before -> 3:head:n;
{ rank=max; null; } // 這行將 null 設為最右側
}
```
## W1 測驗 2
Sign in with Wallet
Connect another wallet