or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Do you want to remove this version name and description?
Syncing
xxxxxxxxxx
2024q1 Homework1 (lab0)
contributed by <
LULser0204
>Reviewed by
mervin0102
關於 ascend 與 descend ,如果佇列的走訪方向從節點
node
走訪至node->next
稱為正向走訪,可以將迴圈的移動從safe = current->next;
改為safe = current->prev;
,讓迴圈反向走訪佇列,也就是走訪方向從節點node
走訪至node->prev
,可以省略開頭與結尾的q_reverse
, 增進函式效能。在
list.h
中,函式list_move
就包含list_del
與list_add
,q_swap
的實作可以考使用list_move
使函式更為精簡。開發環境
佇列實作
無論標題和內文中,中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
在開始之前,我先觀察
list.h
檔裡面所定義的結構雙向鏈結串列
以及在
queue.h
檔案第 23~26 行裡面所定義的鏈結串列元素q_new
避免非必要的項目縮排 (即
*
和-
),以清晰、明確,且流暢的漢語書寫。建立新的「空」佇列
根據老師
lab0
的教材可以得知「空」佇列的定義我使用
malloc
配置記憶體空間,若成功配置足夠空間,則讓new
的 prev 和next 指向自身,否則返回NULL
後來實作
q_free
時,研究在 Linux 核心中 queue 的結構,點進去 The Linux Kernel API - List Management Functions ,第一個就是void INIT_LIST_HEAD(struct list_head *list)
,在list.h
找到其定義後,回到q_new
在程式碼中使用 API 實作詳閱作業說明,自 sysprog21/lab0-c fork 再提交對應的 commits
q_free
使用你 fork 後得到的 GitHub repository 對應的超連結,也就是以 https://github.com/LULser0204/lab0-c 開頭
釋放佇列所佔用的記憶體
文字訊息不要用圖片展現,而且上傳圖片要留意權限。
實作:
在 你所不知道的 C 語言: linked list 和非連續記憶體 觀察佇列在 Linux 核心中的結構,先用
list_for_each_safe
走訪所有成員,而node
紀錄該成員的位址,釋放該節點所指向的value
,接著使用 list_del函式 移去 該節點,再釋放element_t
。最後也需要將
head
的list_head
記憶體也釋放。避免非必要的項目縮排 (即
*
和-
),以清晰、明確,且流暢的漢語書寫。insert_head
在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)
先檢查佇列是否為空,為空則
return false
接著先配置記憶體給新節點
new_head
,接著再配字記憶體給字串,如果配置成功,則用 strcpy 將內容複製到new_head
。最後在使用 list_add 將指定的節點插入佇列
head
的開頭但我在 git 上去的時候,跳出這訊息
Common vulnerabilities guide for C programmers 提到:
所以我做了以下變更,使用了
strncpy
來避免buffer overflow
,並手動增加'\0'
字元以符合佇列的規範詳閱作業說明,自 sysprog21/lab0-c fork 再提交對應的 commits
insert_tail
避免非必要的項目縮排 (即
*
和-
),以清晰、明確,且流暢的漢語書寫。在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則)
概念上和
insert_head
相同,唯一不同的地方在於使用list_add_tail
來將指定的節點插入head
的尾端。remove_head
避免非必要的項目縮排 (即
*
和-
),以清晰、明確,且流暢的漢語書寫。在佇列開頭 (head) 移去 (remove) 給定的節點
由於是雙向鏈結串列,所以
head->next
為佇列的第一個元素,只需要使用list_del
移除第一個元素,之後透過list_entry
將list_head
的entry
回傳即可。但再我測試 trace-08-robust 顯示以下內容:
但當我執行
remove_tail
時,卻沒這問題,所以我更改了判斷邏輯讓函式更明確的檢查鏈節列表是否為空。remove_tail
避免非必要的項目縮排 (即
*
和-
),以清晰、明確,且流暢的漢語書寫。在佇列尾端 (tail) 移去 (remove) 給定的節點,概念上和
remove_head
相似。由於是雙向鏈結串列,所以
head->prev
為佇列的最後一個元素。只需要使用list_del
移除第一個元素,之後透過list_entry
將list_head
的entry
回傳即可。詳細實作: commit ee38aaa
delete_mid
修正上方超連結,對應到實際修改的 commit,而非 patch!
避免非必要的項目縮排 (即
*
和-
),以清晰、明確,且流暢的漢語書寫。移走佇列中間的節點。
參考你所不知道的 C 語言: linked list 和非連續記憶體使用快慢指標來找出佇列的中點,迴圈結束後
slow
指向的正是中間節點,接著使用list_del
刪除並釋放記憶點空間注意用語
原理:
fast
指標每次移動兩個,而slow
指標只移動一格,故結束後慢指標位置就會在中點考慮到環狀且雙向鏈結串列,你能否撰寫更快更精簡的程式碼?
delete_dup
在佇列已經排序的狀況下,移走佇列中具備重複內容的節點。
使用
list_for_each_entry_safe
走訪每個節點,並且分別用before
和tmp
紀錄當前節點和下個節點是否相同flag
來記錄當前節點是不是重複用
tmp
來承擔被刪除與釋放空間的任務。我當時想說刪除before
(畢竟tmp
記錄下一個節點的位置了)不會怎樣,結果一直觸發 "Segmentation fault" 問chatgpt
才知道是什麼問題但當我覺得這麼改會沒問題的時候, "Segmentation fault" 還是一直發生,
chatgpt
告訴我釋放tmp
後,嘗試存取它,可能會導致未定義行為,後來改用q_release_elememt
來釋放節點。access 的翻譯是「存取」,而非「訪問」(visit)
詳細實作:commit 536d842
修改好的實作:commit 95c742b
q_swap
交換佇列中鄰近的節點
交換兩個相鄰節點的位置
(in pairs)
。直覺上想到的方法是先用nextnext
紀錄下一輪的位置,再用cur
和tmp
分別記錄該輪數組 (兩兩一組)第一個元素及第二個元素,使用list_add
和list_del
完成交換位置q_reverse
以反向順序重新排列鏈結串列,該函式不該配置或釋放任何鏈結串列節點,換言之,它只能重排已經存在的節點
經過
q_swap
的實作經驗後,反轉鏈結串列只需要用list_for_each_safe
走訪每個結點,並將每個節點用list_del
和list_add
讓各個節點從頭加入佇列,就能達到反轉的效果q_reverseK
類似 q_reverse,但指定每 k 個節點為一組,進行反向順序排列
我直覺上的想法是用兩層迴圈,第一次跑的次數是有「幾組」節點用
q_size(head)/k
,第二層則跑 k 次。在最裡面那層迴圈的作法和將整個
q_reverse
相似,將這輪翻轉的子佇列先接在另一條佇列上,最後再將其用list_splice
接回 headq_sort
以遞增順序來排序鏈結串列的節點,可參閱 Linked List Sort 得知實作手法
參考你所不知道的 C 語言: linked list 和非連續記憶體提到的方法
將整個數列不停地拆成兩推,直到每堆只剩下一個元素,再兩兩合併直到合併成一個數列為止。我一開始想法是用前面使用前面的
delete_mid
,來將佇列分成兩段閉循環的佇列,但會一直觸發Segmentation fault occurred
後來,參考 wanghanchi 學長採取將環狀鏈結串列斷開,子串列的結尾設為 NULL ,當成單向鏈結串列處理,如此一來也能在迭代的時候方便判斷是否抵達尾端。
split
函式:使用前面提到的快慢指針找到中點,再將其拆成兩半;mergeSort
函式:left
和right
逐一比較,但我那時候沒有考慮到一種情形:如果left
都用完,right
還有兩個以上的情形,所以我測試的時候總是會有幾個元素消失你如何確保目前的測試已涵蓋排序演算法的最差狀況?
我跑去看了 qtest 的隨機資料輸入,使用這一段生成
參考 stackoverflow 這篇文章,合併排序演算法會遇到的最差狀況是 "需要進行最多比較的時候" ,也就是每對集合中都參與比較。
所以如果要產生最差狀況的測試資料,可以使用 q_sort 生成降序的字串。
q_sort
:把環狀結構斷開,以及最後將整個串列的環狀結構接回來函式
q_sort
不完整,請整合q_sort
與mergesort
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →q_ascend
參閱 LeetCode 2487. Remove Nodes From Linked List,在佇列中該「位置」的右邊不能有大於他的數字存在
正確使用標點符號。
我的想法是先用
q_reverse
翻轉整個佇列,接著從左往右走訪每個節點。假設一個變數max
初始值為該佇列的第一個值,往右走訪的路上會有兩個情形:1.如果碰到該節點的值比
max
還要小,則移去掉它2.如果碰到該節點的值比
max
還要大,則更新max
的值為該節點的值繼續走訪直到最後一個節點最後,再將整個佇列翻轉回來並用
q_size
傳回佇列的長度如果調整刪去的條件,是否可以省略
q_reverse
的呼叫?- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →q_descend
參閱 LeetCode 2487. Remove Nodes From Linked List,在佇列中該 "位置" 的右邊不能有小於他的數字存在
其作法和
ascend
概念相同,只是從找是否有"更大"的值變成找"更小"的值。既然
q_decend
、q_ascend
概念相同,能否將兩函式整合,使程式更簡潔?- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →q_merge
合併所有已排序的佇列,並合而為一個新的已排序佇列,詳見 LeetCode 23. Merge k Sorted Lists
我一開始認為傳進來的會是多條佇列,所以我嘗試使用
q_sort
所使用到的mergesort
函式,將其兩兩合併成一條,但失敗了。後來,參考 ItisCaleb 的作法,發現有queue_contex_t
的存在,直接將queue_contex_t
google 搜尋會跳出 SPFishcool 所整理的架構圖!無效的超連結,檢查權限設定
引用 SPFishcool 的內文。
queue_contex_t
在紀錄每一條佇列的資訊,*q
為pointer of queue head
,size
是佇列裡面element_t
的數量,chain
為與其他queue_contex_t
串連的list_head
,下面是其內容為甚麼不直接將
queue_contex_t
中的陣列直接做 merge?先將陣列連接起來再呼叫
q_sort
,在排序時又會經過拆分與合併,顯然有點多此一舉。- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →實測結果:
測試結果不穩定。原因是 ascend 和 descend 有時候會誤刪節點,有時候則正常運作。查閱辭典,理解「穩定」的寓意,用字該精準
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →很奇怪,我的 ascend 只有呼叫 descend 而已,結果功能是正常的???我嘗試了很久,還是不知道為什麼這樣結果是對的。原本的想法是先把串列最後一個節點暫時移除,翻轉第 1~n-1 再接上移除的節點,之後呼叫 descend ,處理後的串列在重複前面的操作。
我搞錯了 ascend 的定義…以及輸入 [5,2,13,3,8] 之所以只輸出 [8]
是因為我前面都用 char ,所以 '13' 他比較的對象是字元 '1' 而不是數字 13
linked list 為「鏈結串列」,可簡稱為 list (串列),但不可稱「链表」,該資料結構不具備任何「表」的寓意,參見中華民國教育部重編國語辭典「表」,指「分格或分項以列記事物的文件」,而 linked list 作為資料結構,全然沒有「分格」和「分項」的意涵。
\(\to\) 資訊科技詞彙翻譯
從我的實作可以看到我的作法屬於是
bad taste
那種只考慮能不能動…,還需要磨練能力把學到的東西拿出來使用。太過於依賴 Chatgpt 或是網路論壇上的解答
你現在的問題不僅是 bad taste,亦有對細節的掌握不足。
以 Valgrind 分析記憶體問題
整合 tiny-web-server
在 qtest 提供新的命令 shuffle
研讀 Linux 核心原始程式碼的 lib/list_sort.c
改進 dudect 實作