HackMD
2025q1 Homework1 (lab0)
contributed by < reberu6 >
開發環境
$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 12
On-line CPU(s) list: 0-11
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i7-8700 CPU @ 3.20GHz
CPU family: 6
Model: 158
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 10
CPU(s) scaling MHz: 64%
CPU max MHz: 4600.0000
CPU min MHz: 800.0000
BogoMIPS: 6399.96
Virtualisation: VT-x
L1d: 192 KiB (6 instances)
L1i: 192 KiB (6 instances)
L2: 1.5 MiB (6 instances)
L3: 12 MiB (1 instance)
NUMA node0 CPU(s): 0-11
開發過程
目前透過自動評分系統得到的分數是 77/100。
q_new
此函式會創建一個空的佇列並初始化成next和prev指標都指向自己。在queue.h給定的函式定義中，將struct list_head的指標作為回傳值，可得知此處需要透過malloc來分配struct list_head這個結構所需之記憶體空間（此結構大小則透過sizeof()取得），才得以在函式結束時仍保留記憶體資訊。分配記憶體也有可能出現失敗的情況，所以在分配完畢時就判斷如果新建的new_list為空則代表分配失敗則函式回傳NULL。
q_free
此函式傳入佇列的位址後就會把整個佇列從記憶體中釋放。
處理head為NULL:
如果傳入的佇列的head是NULL的話就代表佇列本身就不存在而就不需要額外去釋放記憶體，所以就在程式的一開始就判斷。
透過走訪每個節點來進行記憶體的釋放：
原本想說只要使用list_head類型的指標從頭到尾走訪每個節點並使用free來釋放記憶就可以了，但是佇列有兩種類型的節點一種是list_head另一種則是element_t，所以無法直接操作element_t類型的節點。後來我想說head->next會指向element_t類型的節點，那直接把head->next指向的位置直接給element_t *類型的current就可以直接操作，而後面的操作就是分成兩種狀況 :
- 如果
head下一個節點是自己的話代表沒有element_t，所以就直接把head給釋放。 - 若有
element_t類型的節點，先暫存current下一個節點next等我們釋放完element_t再把current移過去，所以一開始就先釋放節點的value接著釋放節點本身就可以了，最後往下個節點移動。 - 重複2以上直到
current是head節點，也就是把element_t類型的節點都已是放完畢。
19 void q_free(struct list_head *head)
20 {
21 if (!head)
22 return;
23 element_t *current = head->next;
24 while (current != head) {
25 element_t *next = current->list.next;
26 free(current->value);
27 free(current);
28 current = next;
29 }
30 free(head);
31 }
進行編譯卻出現
queue.c: In function ‘q_free’:
queue.c:23:26: error: initialization of ‘element_t *’ from incompatible pointer type ‘struct list_head *’ [-Werror=incompatible-pointer-types]
23 | element_t *current = head->next;
| ^~~~
queue.c:25:27: error: initialization of ‘element_t *’ from incompatible pointer type ‘struct list_head *’ [-Werror=incompatible-pointer-types]
25 | element_t *next = current->list.next;
| ^~~~~~~
cc1: all warnings being treated as errors
make: *** [Makefile:54: queue.o] Error 1
程式中第23和25都出現了指標類型不相容的錯誤，後來我看了指標的介紹發現我之前想的不對，不能直接把
element_t *current = head->next;
這是因為head->next的類型是list_head，而current所需element_t的類型，這會導致編譯失敗。雖然head下個節點的確是element_t的類型，但是事實上head->next是連結到element_t裡面的list_head結構的list，程式中的第25行也是同樣的錯誤，所以應該做的修正就是把current跟next的類型改成list_head來走訪每個節點。
那現在的問題就是由於current跟next類型是list_head的話要如何操控element_t類型的記憶體去釋放element_t中的value，所以只好創一個新的element_t類型的指標去接管這個記憶體，但之前說過head->next所連結的位置是element_t中的list，所以沒辦法取得下個節點的起始位置，這時要透過結構的記憶體排列來回推element_t的位置，例如 :
element_t tmp;
Address of tmp: 0x1000
Address of tmp.char: 0x1000
Address of tmp.list: 0x1000+sizeof(char *)
我們會知道tmp.list的位置，所以回推到tmp的位置就會是：
假設tmp.list的位置是0x1008的話，那麼0x1008 - sizeof(char *)則可得到tmp的位置。具體的計算如下:
element_t *real_pos = (element_t *)((char *)current - offsetof(element_t, list));
原本current是list_head類型的指標，但需要先把它轉成char類型的指標，這是因為在計算位址的時候，若是current - 1的話會依照list_head的單位計算，那麼假設current = 0x1008的話，減一之後也不會是0x1007而是current減去一個list_head的單位，所以若我們先把current轉成char類型的指標的話就能正確的計算，這是因為char的單位是 1 byte。
至於為何是用offsetof而不是sizeof去計算偏移量的原因是不同環境和編譯器的原因需要處理對齊的問題所以有些會有 padding，比如說 32 位元的電腦在存取資料時一次都是 4 bytes (32 bits)，而使用sizeof的話就會忽略那個可能性而導致出錯，offset本身就是用來計算結構體成員的偏移量（bytes），而sizeof則是計算一個類型的總大小。
q_insert_head
此函式會在佇列的最前面插入一個元素 (element)。
佇列不存在 :
一開始就先判斷佇列是否存在比較好，避免後面的操作。
分配失敗 :
這跟q_new的檢查一樣，記憶體不一定分配就會成功。這裡要注意的是如果分配失敗的話，記得檢查前面有沒有分配的操作，有的話在這裡分配失敗需要釋放掉它。
插入最前面 :
插入最前面只需修改4個指標，比如說一開始是 :
-> -> ->
head a ... head
<- <- <-
然後插入一元素b
- 在修改
head->next之前，先把新增的元素b指向原本head->next所指的地方，比如說a，避免遺失a的位置。 - 接著把
head->next指向新元素b。
完成後 :
head -> b -> a -> ... -> head
但向左的連結還是 :
head <- a <- ... <- head
所以需要以下操作 :
- 在修改
a指向b，之前先把b指向a所指的地方，避免遺失head位置。 - 接著把
a指向b
完成後 :
head <- b <- a <- head
字串處理 :
基於要求，需要把字串存入一塊新的記憶體空間。
- 所以我們得知道字串的長度來分配記憶體。可以靠字串最後一個字元是
\0的特性來計算，只需透過while迴圈來進行迭代計算長度。 - 接著就可分配空間。
- 透過指標操作一個個的把字元複製到新的記憶體中，我們可以透過剛才計算出的長度來決定
for迴圈要迭代幾次。
當元素的value超過 4個字元的時候出現重複釋放的問題 :
我在想為何是4這個數字，因為程式中根本沒有直接使用到接近4的常數，後來才發現應該要直接分配字串長度加上\0的長度len，而不需要sizeof去計算，因為這樣反而是計算len這個變數型別的大小，len是int型別，所以之前每次分配記憶時都只有分配4 bytes，這就導致了只要插入4個字元或以上時就會出現記憶體錯誤的問題。
--- a/queue.c
+++ b/queue.c
@@ -42,7 +42,7 @@ bool q_insert_head(struct list_head *head, char *s)
len++;
}
len++;
- char *value = malloc(sizeof(len));
+ char *value = malloc(len);
if (!value)
return false;
修正指標更新的順序確保連結正確
這個錯誤是在實做q_insert_tail時才發現的，我發現順序不對的話是沒法把元素插到尾端的，
這時我想起在做q_insert_head好像沒特別意識到這件事，於是回去檢查後發現了錯誤。在實做完q_insert_head時也有測試，但功能都正常，我想這是因為把head->next指向b的話是沒問題的，但被影響的是head->next-prev，也就是a的prev沒指向b，而是讓b指向了自己，所以這沒影響到後續要在最前面插入新的元素。在釋放測試時也正常是因為q_free是透過next來向右移動，而向右的連結都沒錯的話當然也可以正常釋放了。
- head->next = &new->list;
head->next->prev = &new->list;
+ head->next = &new->list;
return true;
}
q_insert_tail
程式基本上跟q_insert_head一樣，所以只須想出如何插入在最後面。
插入最後面 :
同樣只需修改4個指標，比如說一開始是 :
-> -> ->
head ... a head
<- <- <-
然後插入一元素b在尾端，由於需要透過head->prev存取a，所以這個指標最後改 :
- 把
b直接指向head。 - 透過修改
head->prev->next讓a指向b。
完成後 :
head -> ... -> a -> b -> head
但向左的連結還是 :
head <- ... <- a <- head
所以需要以下操作 :
- 把
b指向a（也就是head->prev所指的位置）。 - 修改
head->prev所指的位置為b。
完成後 :
head <- ... <- a <- b <- head
q_remove_head
此函式會移除最前面的元素。
移除最前面的元素 :
比如說一開始是 :
-> -> -> ->
head b a ... head
<- <- <- <-
要將b移除的話，要注意head->next和head->next->next的變更順序是較低的，因為分別透過它們存取b和a。操作順序如以下 :
- 將
a指向head。 - 因為要修改
head->next，所以透過tmp將b的位置暫存。 - 將
head指向a。 - 將
b的next和prev指向NULL。
若傳入的sp非空且成功移除b :
由於bufsize的大小限制且最後得放\0，最多只能複製bufsize - 1個字元，所以透過for迴圈複製前bufsize - 1個字元到sp。
q_remove_tail
移除最後面的元素 :
比如說一開始是 :
-> -> -> ->
head ... a b head
<- <- <- <-
要移除b同樣也得注意操作順序 :
- 將
a指向head。 - 透過
tmp暫存b的位置。 - 將
head指向a。 - 將
b的next和prev指向NULL。
q_size
此函式回傳佇列所包含的節點數量。實作上使用了 list_for_each() 巨集，這本質上是一個走訪每一個節點的 for 迴圈，然後每走訪一個節點就對計數器加 1 即可計算節點的數量。若給定的佇列開頭指標不合法或是給定一空佇列，直接回傳 0 即可。
q_delete_mid
一開始想到的方法是先計算出總共有幾個節點n，接著計算出中間節點的位置為第 for迴圈迭代變更指標current的位置到中間節點的前一個 (後來在使用快慢指標時發現其實直接移到中間節點也可以，因為雙向鏈結所以進行指標更新時b不會遺失a和c的位置)，進行釋放和指標更新。
假如一開始只看向右的連結的話如下：
head -> a -> b -> c -> head
那透過走訪每個節點可以算出佇列的長度為 3 ，接著要走到a然後釋放b，但如果就這樣釋放b的話會導致遺失c的位置，所以順序如下：
b。- 走到
b的前一節點a。 - 把
b的下一個節點c暫存。 - 釋放
b並把a指向c。
接下來看向左的連結：
head <- a b <- c <- head;
b已經被釋放了所以沒法從b到a，而c仍指向b原本的記憶體位置，但如果存取c->prev會導致未定義的行為。
最後只須透過剛才暫存的指標讓c指向當前位置a，這樣一來就完成了刪除和正確連結。
完成後沒法通過提交檢查出現了NO dictionary found，由於它是fmtscan的執行結果，所以看了lab0-c/tools/fmtscan.c的內容後發現會用到/usr/share/dict/american-english和lab0-c/scripts/aspell-pws，因為aspell-pws存在所以去看american-english有沒有存在，發現沒有，後來執行sudo apt install wamerican安裝完後，有了american-english就可以了。
快慢指標
參考分析「快慢指標」實現找到中間的點，也了解雖然在演算法上的複雜度都是一樣的，但是根據操作的方式不同讓時間局部性產生差異，這需要了解硬體架構才有可能意識到這點。
q_delete_dup
刪除具有重複的字串的節點，就需要比對的動作，目前是想到用兩個指標來完成 :
- 先用一指標
a指向要被比較的對象，另一指標b則指向比較的對象，如以下示意 :
[a]=>=>=>
head <-> cat <-> dog <-> cat <-> pig <-> head
[b]=>=>=>
- 接著就是固定
a，然後b不斷向右並與a的字串進行比較，有相同就是刪除元素並更新指標。 - 等
b到達尾端後，a就往下個元素移動。 - 重複2和3直到
a到達最後一個元素就完成了所有的比對。
完成後才發現做錯了，比如輸入[a, a, a]，結果出現ERROR: Queue has more than 0 elements，我一開始以為是要實現跟 LeetCode 相同的功能，後來回去看才發現是刪除所有有重複字串的元素，只保留原始佇列中不重複的字串。
input: [a, a, a]
output: [a]
expected: []
在修改的過程中程式的運作一直不如預期，所以使用 gdb 來看過程，結果發現:
雖然ae->value和be->value都是"a"，但是程式碼中ae->value == be->value的結果卻是false，這才發現因為ae->value是char的指標，所以比較的是指標的地址，所以不管怎麼比都是false，所以改用string.h中的strcmp比較字串是否相等。
完成q_delete_dup後發現，只要有相同的字串中間有別的字串的話就會出現錯誤，如以下示意:
intput: [a b a]
output: [b]
出現ERROR: Duplicate strings are in queue or distinct strings are not in queue雖然功能正確但還是出現了錯誤，這裡不確定是queue.h中的描述錯誤還是檢查程式的錯誤，待查證。
q_swap
q_swap在實作上是比較容易的，因為只需要修改6個指標就能完成兩個點的位置交換。以下為示意:
[c]
head <-> a <-> b <-> head
需要清楚的知道更改指標的順序，這樣一來就可以只透過一個指標修改。 先把c指向佇列中的第一個元素a，接下來c->prev跟c->next會比較晚更改，這是分別為了操作head和b:
- 透過
c->prev把head->next指向b。 - 透過
c->next把b->prev指向head。
接下來就可修改c->prev跟c->next:
- 把
c->prev指向b，也就是b在a前。 - 把
c->next指向b->next，也就是head前。
既然知道c-prev是b和c->next是head最後再更新一些指標就完成了:
- 把
b->next指向a。 - 把
head->prev指向a。
最後如以下:
[c]
head <-> b <-> a <-> head
接著就是想元素有兩個以上的時候要怎麼處裡可以重複以上的動作，那麼經過以上的操作，可以知道c只要指向要交換的a與b相對位置中的a就能夠進行操作的話，接著只需要檢查有沒有元素可操作並把c移到適當的位置即可。
假如新增兩元素x和y:
[c]
head <-> b <-> a <-> x <-> y <-> head
- 如果
a的下個元素如果是head代表沒其他元素則結束函式，否則c往下個元素移動。 - 因為至少要有兩個元素才能交換，所以需再檢查一次
c的下個元素是不是head，但這次是當作while的判斷條件，while會把上面a和b交換的動作和剛才的檢查全都包起來，這樣一來可以檢查出只有奇數個節點的情況，這是因為c已經到了跟一開始一樣的相對位置，所以這樣做。
所以如果最後有成功移動的話則如以下:
[c]
head <-> b <-> a <-> x <-> y <-> head
q_reverse
目前是採用兩個指標達成q_reverse:
- 先用一指標
a指向要被修改的對象，另一指標b則指向暫存位置的對象，如以下示意 :
[a] [b]
head <-> x <-> y <-> head
- 因為是反轉所以
a的下一個會是現在a的前一個，修改a->next為a->prev。 - 接著
a的前一個會是b，所以修改a->prev為b(剛才暫存b所以不怕2修改了a->next)。 - 判斷
b是否在head的位置，如果不是a和b往下移動。 - 重複2~4直到
b在head的位置則結束。
[a] [b]
head <-> x <-> y <-> head
q_reverseK
q_sort
q_ascend & q_descend
q_merge()
