2022q1 Homework1 (quiz1)

contributed by < BensonYang1999 >

第 1 周測驗題

測驗1

延伸題目

解釋上述程式碼運作原理

資料結構
- map_t 包含 bits 及 ht ，bits儲存hash table的大小( 1<<bits )，ht 為指向 hlist_head 的指標
- hlist_head 中只有一個指標 first ，指向 hlist_node
- hlist_node 包含 pprev 及 next ， pprev 指向前一個node， next 指向後一個node；這裡比較特殊的地方 pprev 是用指標的指標，可以快速修改節點的連結。
- hash_key 包含 key, data, node

第一次使用 graphviz，對 arrow 的調整還不熟悉，會發生edge與node邊框重疊的問題，不確定要怎麼解決。

注意書寫規範：中英文間用一個半形空白字元區隔。
不要急著說「第一次使用」，你很快會接觸一堆工具，理工人說話要精準且資訊量充足。

Image Not Showing Possible Reasons

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 →

jserv

twoSum流程
1. 建立一個map，並設定大小為10<<bits
2. 進入迴圈，走訪陣列中的每個數字
  1. 先將每個數值都透過map_get測試是否有匹配的數值，若匹配成功回傳正確的組合
  2. 若找不當組合，則將此數字加入到hash table
3. 將所有創建的記憶體清除

function說明

map_init
目的：初始化map，建立適當大小的hash table

利用malloc配置空間存放map

map_t *map = malloc(sizeof(map_t));
if (!map)
    return NULL;

配置hash table的記憶體空間，並將所有head的first指標先指向NULL

map->bits = bits;
map->ht = malloc(sizeof(struct hlist_head) * MAP_HASH_SIZE(map->bits));
if (map->ht) {
    for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++)
        (map->ht)[i].first = NULL;
} else {
    free(map);
    map = NULL;
}
return map;

find_key
目的：尋找key是否存在在hash table中
先找到符合的head後，造訪其中的所有node，尋找相同key的node
map_get
目地：利用find_key找到符合的節點後，回傳其原始數值的陣列代碼。

map_add
目地：將原始數值利用hash轉換後，存入hash table，並紀錄陣列代碼。
詳細步驟：

先確保要插入的值不存在在hash table中 (3~5)
配置空間存放hash_key (7, 8)
找到應當插入的hash table欄位 (10)
找到新節點的記憶體位置n及原本存在欄位中的節點first (11)
將新節點的next指向原本存在欄位中的節點first，因此本位置應填入n->next = first; (12)
若原節點存在，須修改該節點的prev (13, 14)
將head接到新節點上 (15)
最後應將新節點的prev連接到head，因此本位置應填入n->pprev = &h->first; (16)

















void map_add(map_t *map, int key, void *data)
{
    struct hash_key *kn = find_key(map, key);
    if (kn)
        return;

    kn = malloc(sizeof(struct hash_key));
    kn->key = key, kn->data = data;

    struct hlist_head *h = &map->ht[hash(key, map->bits)];
    struct hlist_node *n = &kn->node, *first = h->first;
    n->next = first;
    if (first)
        first->pprev = &n->next;
    h->first = n;
    n->pprev = &h->first;
}

map_deinit
目的：把整個map中所有的 map, hash_key, node 清空

研讀 Linux 核心原始程式碼及對應的文件，解釋 hash table 的設計和實作手法，並留意到 `GOLDEN_RATIO_PRIME` ，探討其實作考量

linux 核心利用 Seperate chaining 方式解決衝突
利用 number of bits 定義 hash table 的大小
利用 golden ratio constants 可有效達成高度隨機

測驗2

思路：兩個判斷式都須考慮下一個節點是否存在以及此節點與下一個節點是否擁有相同數值，因此適當的程式碼為head->next && head->val == head->next->val

struct ListNode *deleteDuplicates(struct ListNode *head)
{
    if (!head)
        return NULL;

    if (head->next && head->val == head->next->val) {
        /* Remove all duplicate numbers */
        while (head->next && head->val == head->next->val)
            head = head->next;
        return deleteDuplicates(head->next);
    }

    head->next = deleteDuplicates(head->next);
    return head;
}

延伸問題

嘗試避免遞迴，寫出同樣作用的程式碼

版本一(for leetcode 83)：建立一個新的指標node指向head，利用判斷式確認是否有相同的值，當相同時將當前節的next接到next->next，代表忽略掉下一個節點，當不同時則直接將指標到下一個點
此版本特點在於會保留重複的數字，不會將其全部刪除
















struct ListNode *deleteDuplicates(struct ListNode *head)
{
    if (!head)
        return NULL;
    
    struct ListNode *node = head;
    while (node->next) {
        if (node->val == node->next->val) {
            node->next = node->next->next;
        }
        else {
            node = node->next;
        }
    }
    return head;
}

版本二(for leetcode 82)：利用指標node及指標的指標dnode，透過迴圈將所有重複的數字跳過，並利用dnode把list接到下一個數字
此版本特點在於會將重複的數字全部刪除，不會剩下一個




















struct ListNode *deleteDuplicates(struct ListNode *head)
{
    if (!head)
        return NULL;
    
    struct ListNode *node = head, **dnode = &head;
    while (node) {
        if (node->next && node->val == node->next->val) {
            while (node->next && node->val == node->next->val)
                node = node->next;
            *dnode = node->next; // 將dnode指向的指標（一開始為head)指向的下一個（不重複）的節點
            node = node->next;
        }
        else {
            dnode = &((*dnode)->next); // 將dnode指向下一個節點
            node = node->next;
        }
    }
    return head;
}

以類似 Linux 核心的 circular doubly-linked list 改寫，撰寫遞迴和迭代 (iterative) 的程式碼

測驗3

參考資料

graphviz position