HackMD
2025q1 Homework2 (quiz1+2)
contributed by < Hande1004 >
第一周測驗 1
在這題當中，主要要達成的是完成 list_insert_before() 這個函式，這是能夠把所要插入的 item 插入佇列當中的函式。
以下圖片為list_insert_before()詳細功能介紹:
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
{
list_item_t **p;
for (p = AAAA; *p != BBBB; p = CCCC)
;
*p = item;
DDDD = before;
}
為了解出這題，必須先了解它程式碼運作的原理，首先要先釐清插入的位置為何，根據題目 before 的敘述，我們要將 new item 插入 before 之前， 因此解題思路就是走訪到插入前的位置，把 new item 插入，即可完成。
在這題當中，使用間接指標 p 來走訪與連接，首先必須先設定 p 的初始值，因為要從頭走訪，因此，要從佇列的 head 開始，接著運用 next 來往後走訪，最後停止在 before 之前，使用*p = item 讓原本指向 before 的指標指向 item 來完成插入，最後再將 item->next 接上 before 就完成了。
{
list_item_t **p;
for (p = &l->head; *p != before; p = &(*p)->next)
;
*p = item;
item = before;
}
在第 2 個延伸問題中，要把現有的程式碼加上合併排序的功能，因此我寫了幾個函式 merge(), merge2(), sort()來執行合併排序，方法是用 sort() 先斷掉此佇列的 dummy head 然後把第一個節點輸入進merge2()執行快慢指標的佇列分割，接著用 merge() 去合併後傳回 sort() 即完成合併排序。
list_item_t *merge(list_item_t *la, list_item_t *lb)
{
list_item_t tail;
tail.next = NULL;
list_item_t *tmp = &tail;
while (la && lb)
{
if (la->value <= lb->value) {
tmp->next = la;
tmp = la;
la = la->next;
} else {
tmp->next = lb;
tmp = lb;
lb = lb ->next;
}
}
if (la) {
tmp->next = la;
}
if (lb) {
tmp->next = lb;
}
return tail.next;
}
list_item_t *merge2(struct list_item *head)
{
if (!head || !head->next)
return head;
list_item_t *fast = head->next;
list_item_t *slow = head;
if (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
fast = slow->next;
slow->next = NULL;
list_item_t *la = merge2(head);
list_item_t *lb = merge2(fast);
return merge(la,lb);
}
void sort(list_item_t *head)
{
list_item_t *head_next = head->next;
head->next = NULL;
head->next = merge2(head_next);
}
我認為可以在現有的程式碼的 static char *test_list(void) 的這個函式中的最後幾行加上
sort(l.head);
這樣就可以在原本的功能，插入 item 到佇列後進行排序了。
第一周測驗 2
void remove_free_tree(block_t **root, block_t *target)
在這個程式碼中，是二元樹搜尋的裡中的刪除節點，視情況而定分為幾種刪除方式。
- 要刪除的節點沒有子節點。
如果要刪除的節點無子節點，那就會直接把此節點的父節點的rorl(端看此節點是其父節點的rorl)指向NULL。 - 此節點只有一個子節點。
會把父節點的rorl(端看此節點是其父節點的rorl)指向子節點。 - 此節點有兩個子節點。
需要去找此節點的左子節點一直往下接到的最大值，來替換此節點。
而此狀況下又分成兩種狀況：
1.左子節點沒有右子節點：直接把左子節點替換成要刪除的節點，並把原本接在刪除節點右子節點接到替換的節點的右子節點。
2.左子節點下還有右子節點：把左子節點往下接到的最大size的節點替換要刪除的節點，要把刪除節點左右兩個子節點都接到替換的節點的左和右子節點上。
在這題當中，要我們去完成的便是有兩種子節點的情況。
if ((*node_ptr)->l && (*node_ptr)->r) {
/* Find the in-order predecessor:
* This is the rightmost node in the left subtree.
*/
block_t **pred_ptr = &(*node_ptr)->l;
while (EEEE)
pred_ptr = FFFF;
/* Verify the found predecessor using a helper function (for debugging).
*/
block_t *expected_pred = find_predecessor_free_tree(root, *node_ptr);
assert(expected_pred == *pred_ptr);
/* If the predecessor is the immediate left child. */
if (*pred_ptr == (*node_ptr)->l) {
block_t *old_right = (*node_ptr)->r;
*node_ptr = *pred_ptr; /* Replace target with its left child. */
(*node_ptr)->r = old_right; /* Attach the original right subtree. */
assert(*node_ptr != (*node_ptr)->l);
assert(*node_ptr != (*node_ptr)->r);
} else {
/* The predecessor is deeper in the left subtree. */
block_t *old_left = (*node_ptr)->l;
block_t *old_right = (*node_ptr)->r;
block_t *pred_node = *pred_ptr;
/* Remove the predecessor from its original location. */
remove_free_tree(&old_left, *pred_ptr);
/* Replace the target node with the predecessor. */
*node_ptr = pred_node;
(*node_ptr)->l = old_left;
(*node_ptr)->r = old_right;
assert(*node_ptr != (*node_ptr)->l);
assert(*node_ptr != (*node_ptr)->r);
}
}
其中因為要去找出左子節點往下接到的最大值，因此要一直往 r 下去找，直到
(*pred_ptr)->r = NULL
所以這題是：
while ((*pred_ptr)->r)
pred_ptr = &(*pred_ptr)->r;
接著根據延伸問題的
嘗試補完程式碼，使其可獨立執行，應提供相關的測試程式碼
我新增了幾個函式以達成測試：
首先是須補完此題中的 find_free_tree()
藉由比對size的大小來決定要往右走訪還是往左訪。
block_t **find_free_tree(block_t **root, block_t *target)
{
while (*root) {
if(*root == target) {
return root;
}
if ((*root)->size <= target->size) {
root = &(*root)->r;
}
if ((*root)->size > target->size) {
root = &(*root)->l;
}
}
return root;
}
為了測試刪除是否能夠運作，必須先建立起二元樹，因此寫了 insert_node()
一樣用 size 去比對要將新節點插在哪裡，如果比當前節點小就往左接，反之就往右接。
bool insert_node(block_t **root, block_t *target)
{
if (target->size == 0 || !target)
return false;
while (*root != NULL)
{
if ((*root)->size <= target->size) {
root = &(*root)->r;
} else {
root = &(*root)->l;
}
}
*root = target;
target->l = NULL;
target->r = NULL;
return true;
}
為了讓我測試後能可視化節點，因此需要把結果展現出來
void print_tree(block_t *root)
{
if(!root)
return;
print_tree(root->l);
printf("%zu ",root->size);
print_tree(root->r);
return;
}
最後是我的測試程式碼，插入10個節點，每個節點的 size 用 rand() 去隨機取 1 到 100 值而定，並插入此二元樹中，接著在隨機刪除 5 個節點，看看是否有刪除成功。
int main()
{
block_t *root = NULL;
block_t *node[N];
printf("insert to the tree:\n");
for (int i = 0; i < N; i++) {
node[i] = malloc(sizeof(block_t));
if (!node[i]) {
fprintf(stderr,"memory allocation failure\n");
exit(1);
}
node[i]->size = rand() % max_size + 1;
root = node[0];
insert_node(&root, node[i]);
}
root = node[0];
print_tree(root);
printf("\n");
int idx;
printf("remove from the tree:\n");
for (int i = 0;i < N >> 1; i++) {
idx = rand() % N;
if (node[idx]) {
printf("%zu ",node[idx]->size);
remove_free_tree(&root, node[idx]);
free(node[idx]);
node[idx] = NULL;
}
}
printf("\n");
printf("final tree:\n");
print_tree(root);
for (int i = 0; i < N; i++) {
if (node[i]) {
free(node[i]);
node[i] = NULL;
}
}
printf("\n");
return 0;
}
接著是我的執行結果：
insert to the tree:
16 22 36 50 78 84 87 87 93 94
remove from the tree:
78 93 84 22 16
final tree:
36 50 87 87 94
依結果來看，有成功執行刪除。
第一周測驗 3
這題主要是在探討如何不用函式遞迴的方式來實做 quick sort 的演算法。
以下是題目中的 quick sort 的主體。
為了達成這個目的，需要有個 begin 的陣列來紀錄節點，才能讓後面執行迴圈的時候能夠查找到對應的節點，因此要先測量所需的陣列的最大值，也就是 quick sort 複雜度最糟的情況 right 和 left 兩個指標，故需要最大陣列為 2 * n
在這題的概念中，是將第一個節點當成 pivot 並將剩下的節點跟它做 value 的大小比較，如果比 pivot 大的就會被接到 R 中，反之，就會被接到 L 中，其中的執行方法是用兩個指標來接起來 left 跟 right 如果當前的值比 pivot 還要來的大，那就會被當前的節點的 next 指向 right ，在讓 right 指向當前的節點，反之，就是指向 left，用此方法來把節點都區分到 L 跟 R 上。
接著會讓 begin 這個陣列去儲存 R 、 L 、 pivot 的起始位置，然後 i += 2 後進入下一次迴圈，目的是要讓下一次迴圈先處理右子串。這個迴圈會一直執行直到被拆分到只剩下一個節點。
當被拆分到剩下一個節點時，就會把此節點就到 result 接著 i-- 讓下一個迴圈能夠處理前面的節點。
節由這種方式就能夠讓最大 value 的節點先被接到 result 中，接下來越來越小的節點不斷的指向更大的節點來完成後進先出的順序排列。
{
int n = list_length(list);
int value;
int i = 0;
int max_level = 2 * n;
struct list_head *begin[max_level];
struct list_head *result = NULL, *left = NULL, *right = NULL;
begin[0] = list->next;
list->prev->next = NULL;
while (i >= 0) {
struct list_head *L = begin[i], *R = list_tail(begin[i]);
if (L != R) {
struct list_head *pivot = L;
value = list_entry(pivot,node_t,list)->value;
struct list_head *p = pivot->next;
pivot->next = NULL; /* break the list */
while (p) {
struct list_head *n = p;
p = p->next;
int n_value = list_entry(n,node_t,list)->value;
if (n_value > value) {
n->next = right;
right = n;
} else {
n->next = left;
left = n;
}
}
begin[i] = left;
begin[i + 1] = pivot;
begin[i + 2] = right;
left = right = NULL;
i += 2;
} else {
if (L) {
L->next = result;
result = L;
}
i--;
}
}
list->next = result;
rebuild_list_link(list);
}
第二周測驗 1
解釋main:
上面的程式碼主要用 getnum() 來產生一個 uint8_t 的隨機數，並分兩次把它填充至 get_unsigned16() 中的前 8 個位元跟後 8 個位元，來產生一個 uint16_t 的隨機數。
接著放進一個陣列裡面洗牌，把洗好的陣列依序從第 0 個元素填入新創好的
list_head testlist 中，並把這個陣列跟被填入的鏈結串列分別做 sort() 及 list_quicksort() 。
接著在對兩個排列好的 陣列及鏈結串列最對應元素的值得比較，如果比較出來，對應的元素的值接相同，就代表有實作出 list_quicksort() 的功能，也就可以把 testlist 指向的鏈結串列依序釋放掉了。
解釋list_quicksort():
用 list_less 來接比 pivot 的值小的節點，用 list_greater 來接大於等於 pivot 的值，接著再把 list_less 和 list_greater 放進函式遞迴中，直到接到的鏈結串列的節點都切到只剩一個或沒有的接，就依小到大的順序排序鏈結串列。
改進 random_shuffle_array
我嘗試用 lab 0 提到的 Fisher–Yates shuffle 的方法來改進。
static inline void random_shuffle_array(uint16_t *operations, uint16_t len)
{
int n = len - 1;
uint16_t tmp;
for (uint16_t i = 0; i < len - 1; i++) {
uint16_t j = get_unsigned16() % n;
tmp = operations[j];
operations[j] = operations[n];
operations[n] = tmp;
n--;
}
}
list_for_each_entry_safe 建構的迴圈中，若將 list_move_tail 換為 list_move，為何會無法滿足 stable sorting
因為這裡的 pivot 是 4 所以 list_less 內會有 3 3* 1等數值，接下來展示用 list_move 和 list_move_tail 兩種的巨集展示 list_less 後的結果。
list_move():
因為 list_move() 會不斷的把新節點插到 head 的 next，所以就會讓原本鏈結串列的順序相反。
list_move_tail():
因為會一直把新節點插在 head 的 prev ，所以就能夠維持順序。
