2022q1 Homework1 (lab0)

contributed by < Julian-Chu >
GitHub

Data type

主要使用的 struct, 與去年不同改以 Linux Doubly Linked Lists 實作 lab0

typedef struct {
    char *value;
    struct list_head list;
} element_t;

struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

API

操作 doubly linked list 的 API 已經包含在 lab0-c/list.h 裡面

實作

q_new

struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));
    if (head)
        INIT_LIST_HEAD(head);
    return head;
}

創建一個 list_head 當作操作的基準節點, 此節點不嵌入在 element_t

q_free

void q_free(struct list_head *l)
{
    if (!l || list_empty(l)) {
        free(l);
        return;
    }

    element_t *entry, *n;
    list_for_each_entry_safe (entry, n, l, list) {
        list_del(&entry->list);
        free(entry->value);
        free(entry);
    }

    free(l);
}

使用 list API 走訪個節點釋放記憶體，需要注意釋放的記憶體有

• element_t
• element_t->list
• head 本身

q_insert_head

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *e = malloc(sizeof(element_t));
    if (!e)
        return false;

    e->value = strdup(s);
    if (!e->value) {
        free(e);
        return false;
    }
    list_add(&e->list, head);
    return true;
}

利用 list_add 插入節點, 注意賦值給 e->value 失敗的情況也需要釋放 element_t 的記憶體空間

q_insert_tail

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *e = malloc(sizeof(element_t));
    if (!e)
        return false;

    e->value = strdup(s);
    if (!e->value) {
        free(e);
        return false;
    }
    list_add_tail(&e->list, head);
    return true;
}

與 q_insert_tail 類似，改用 list_add_tail API

q_remove_head

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *e = list_first_entry(head, element_t, list);
    if (!e)
        return NULL;
    list_del(&e->list);

    if (sp) {
        strncpy(sp, e->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return e;
}

使用 list_first_entry 取得節點， list_del 移除節點，另外還需要把節點的值輸出到 sp, 由於此處是字串，需要注意 \0 結尾，使用 strlcpy 會更好

q_remove_tail

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *e = list_last_entry(head, element_t, list);
    if (!e)
        return NULL;
    list_del(&e->list);

    if (sp) {
        strncpy(sp, e->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return e;
}

同上，改用 list_last_entry

q_size

int q_size(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;

    int size = 0;
    struct list_head *node;
    list_for_each (node, head) {
        size++;
    }
    return size;
}

沒有

$O(1)$ 的需求可以直接迴圈計算，如有

$O(1)$ 需求可以在把 head 嵌入一個 struct 利用該 struct 紀錄個數

q_delete_mid

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    struct list_head *slow = head->next, *fast = head->next;
    while (fast != head->prev && fast != head) {
        slow = slow->next;
        fast = fast->next->next;
    }

    element_t *e = list_entry(slow, element_t, list);
    if (!e)
        return false;
    list_del(slow);
    free(e->value);
    free(e);

    return true;
}

這邊採用單向快慢指針， 由於是 doubly linked list 也可以兩個指針分別往 prev 和 next 走，相遇點爲中點

q_delete_dup

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head)
        return false;
    if (list_empty(head))
        return true;

    struct list_head **indirect = &head->next;
    while (*indirect != head && (*indirect)->next != head) {
        element_t *a = list_entry(*indirect, element_t, list);
        element_t *b = list_entry((*indirect)->next, element_t, list);
        if (strcmp(a->value, b->value) == 0) {
            // 需要特別檢查 b 移動到 head 的情況
            while (&b->list != head && strcmp(a->value, b->value) == 0) {
                list_del((*indirect)->next);
                q_release_element(b);
                b = list_entry((*indirect)->next, element_t, list);
            }

            list_del(*indirect);
            q_release_element(a);
        } else {
            indirect = &(*indirect)->next;
        }
    }

    return true;
}

利用 pointer to pointer 實作，需要注意當 list_entry 接收到 head 情況， 會回傳 non-null 的 entry, 但 list_entry 不會檢查型別, 所以該 entry 是非法的

q_swap

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head || list_empty(head))
        return;
    struct list_head *cur, *tmp;
    cur = head->next;
    while (cur != head && cur->next != head) {
        tmp = cur->next;
        cur->prev->next = tmp;
        tmp->prev = cur->prev;
        cur->next = tmp->next;
        cur->next->prev = cur;
        cur->prev = tmp;
        tmp->next = cur;
        cur = cur->next;
    }
}

q_reverse

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    struct list_head *cur = head, *next = head->next;
    do {
        cur->next = cur->prev;
        cur->prev = next;
        cur = next;
        next = cur->next;

    } while (cur != head);
}

doubly linked list 實作 reverse 意外的簡單，prev 與 next 互換即可

q_sort

struct list_head *merge_sort_two_nodes(struct list_head *a, struct list_head *b)
{
    if (!b)
        return a;
    if (!a)
        return b;

    struct list_head *head = NULL;
    struct list_head **indirect = &head;

    while (a && b) {
        element_t *entry_a = list_entry(a, element_t, list);
        element_t *entry_b = list_entry(b, element_t, list);
        if (strcmp(entry_a->value, entry_b->value) < 0) {
            *indirect = a;
            a = a->next;
        } else {
            *indirect = b;
            b = b->next;
        }
        indirect = &(*indirect)->next;
    }

    if (a)
        *indirect = a;
    if (b)
        *indirect = b;

    return head;
}

struct list_head *merge_sort(struct list_head *node)
{
    if (!node)
        return NULL;
    if (!node->next)
        return node;

    struct list_head *slow = node, *fast = node->next;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    struct list_head *mid = slow->next;
    slow->next = NULL;

    struct list_head *left, *right;
    left = merge_sort(node);
    right = merge_sort(mid);

    return merge_sort_two_nodes(left, right);
}

/* Sort elements of queue in ascending order
 * No effect if q is NULL or empty. In addition, if q has only one
 * element, do nothing.
 */
void q_sort(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    head->prev->next = NULL;
    head->next = merge_sort(head->next);
    struct list_head *cur = head;
    while (cur->next) {
        cur->next->prev = cur;
        cur = cur->next;
    }
    cur->next = head;
    head->prev = cur;
}

切斷 doubly linked list 當成 singly linked list 就可以使用 merge sort 了， 最後重建 link 即可

Todo