2022q1 Homework1 (lab0)

contributed by < ArielWu0203 >

queue.c 實作

• q_new: 建立新的「空」佇列;
• q_free: 釋放佇列所佔用的記憶體;
• q_insert_head: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則);
• q_insert_tail: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則);
• q_remove_head: 在佇列開頭 (head) 移去 (remove) 給定的節點;
• q_release_element: 釋放特定節點的記憶體空間;
• q_size: 計算目前佇列的節點總量;
• q_delete_mid: 移走佇列中間的節點，詳見 LeetCode 2095. Delete the Middle Node of a Linked List
• q_delete_dup: 在已經排序的狀況，移走佇列中具備重複內容的節點，詳見 LeetCode 82. Remove Duplicates from Sorted List II
• q_swap: 交換佇列中鄰近的節點，詳見 LeetCode 24. Swap Nodes in Pairs
• q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點;
• q_sort: 以遞增順序來排序鏈結串列的節點，可參閱 Linked List Sort 得知實作手法;

q_new

/*
 * Create empty queue.
 * Return NULL if could not allocate space.
 */
struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));
    if(!head)
        return NULL;
    INIT_LIST_HEAD(head);
    return head;
}

使用 INIT_LIST_HEAD 對 head 初始化。

// in <list.h>
static inline void INIT_LIST_HEAD(struct list_head *head)
{
    head->next = head;
    head->prev = head;
}

q_insert_head

/*
 * Attempt to insert element at head of queue.
 * Return true if successful.
 * Return false if q is NULL or could not allocate space.
 * Argument s points to the string to be stored.
 * The function must explicitly allocate space and copy the string into it.
 */
bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *ele = malloc(sizeof(element_t));
    if (!ele)
        return false;
    else {
        // Init ele
        ele->value = strdup(s);
        INIT_LIST_HEAD(&(ele->list));
        // Add a list node to the beginning of the list
        list_add(&(ele->list), head);
    }
    return true;
}

/**
 * list_add() - Add a list node to the beginning of the list
 * @node: pointer to the new node
 * @head: pointer to the head of the list
 */
static inline void list_add(struct list_head *node, struct list_head *head)
{
    struct list_head *next = head->next;

    next->prev = node;
    node->next = next;
    node->prev = head;
    head->next = node;
}

q_insert_tail

/*
 * Attempt to insert element at tail of queue.
 * Return true if successful.
 * Return false if q is NULL or could not allocate space.
 * Argument s points to the string to be stored.
 * The function must explicitly allocate space and copy the string into it.
 */
bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *ele = malloc(sizeof(element_t));
    if (!ele)
        return false;
    else {
        // Init ele
        ele->value = strdup(s);
        INIT_LIST_HEAD(&(ele->list));
        // Add a list node to the beginning of the list
        list_add_tail(&(ele->list), head);
    }
    return true;
}

/**
 * list_add_tail() - Add a list node to the end of the list
 * @node: pointer to the new node
 * @head: pointer to the head of the list
 */
static inline void list_add_tail(struct list_head *node, struct list_head *head)
{
    struct list_head *prev = head->prev;

    prev->next = node;
    node->next = head;
    node->prev = prev;
    head->prev = node;
}

q_free

/* Free all storage used by queue */
void q_free(struct list_head *l)
{
    if(!l)
        return;
    element_t *ele, *ele_safe;
    list_for_each_entry_safe (ele, ele_safe, l, list) {
        q_release_element(ele);
    }
    free(l);
}

list_for_each_entry_safe 會將 entry->next 儲存在 safe ，所以當刪除 entry 時，也不會影響到下一個迴圈的 entry

• list_for_each_entry_safe - iterate over list entries and allow deletes
  @entry: pointer used as iterator
  @safe: @type pointer used to store info for next entry in list
  @head: pointer to the head of the list
  @member: name of the list_head member variable in struct type of @entry

q_size

/*
 * Return number of elements in queue.
 * Return 0 if q is NULL or empty
 */
int q_size(struct list_head *head)
{
    if (!head)
        return 0;

    int len = 0;
    struct list_head *ptr;

    list_for_each (ptr, head)
        len++;
    return len;
}

q_remove_head

/*
 * Attempt to remove element from head of queue.
 * Return target element.
 * Return NULL if queue is NULL or empty.
 * If sp is non-NULL and an element is removed, copy the removed string to *sp
 * (up to a maximum of bufsize-1 characters, plus a null terminator.)
 *
 * NOTE: "remove" is different from "delete"
 * The space used by the list element and the string should not be freed.
 * The only thing "remove" need to do is unlink it.
 *
 * REF:
 * https://english.stackexchange.com/questions/52508/difference-between-delete-and-remove
 */
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *node = list_entry(head->next, element_t, list);
    list_del(head->next);
    if (sp)
        strncpy(sp, node->value, strlen(node->value) + 1);
    return node;
}

list_entry 可以得到 entry 的位址

• list_entry() - Calculate address of entry that contains list node

@node: pointer to list node
@type: type of the entry containing the list node
@member: name of the list_head member variable in struct @type
Return: @type pointer of entry containing node

q_delete_mid

/*
 * Delete the middle node in list.
 * The middle node of a linked list of size n is the
 * ⌊n / 2⌋th node from the start using 0-based indexing.
 * If there're six element, the third member should be return.
 * Return true if successful.
 * Return false if list is NULL or empty.
 */
bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (!head || list_empty(head))
        return false;
    int step = q_size(head) / 2;
    struct list_head *node = head->next;
    while (step--) {
        node = node->next;
    }
    list_del(node);
    q_release_element(list_entry(node, element_t, list));
    return true;
}

q_swap

/*
 * Attempt to swap every two adjacent nodes.
 */
void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head || list_empty(head))
        return;
    struct list_head *first = head->next, *second = head->next->next;
    while (first != head && second != head) {
        first->next = second->next;
        first->next->prev = first;
        second->prev = first->prev;
        second->prev->next = second;
        first->prev = second;
        second->next = first;
        first = first->next;
        second = first->next;
    }
}

尾端的 return 敘述非必要

jserv

q_reverse

/*
 * Reverse elements in queue
 * No effect if q is NULL or empty
 * This function should not allocate or free any list elements
 * (e.g., by calling q_insert_head, q_insert_tail, or q_remove_head).
 * It should rearrange the existing ones.
 */
void q_reverse(struct list_head *head) {
    if(!head || list_empty(head))
        return;
    struct list_head *ptr = head;
    do {
        struct list_head *tmp = ptr->prev;
        ptr->prev = ptr->next;
        ptr->next = tmp;
        ptr = ptr->prev;
    } while (ptr!=head);
    return;
}

q_delete_dup

/*
 * Delete all nodes that have duplicate string,
 * leaving only distinct strings from the original list.
 * Return true if successful.
 * Return false if list is NULL.
 *
 * Note: this function always be called after sorting, in other words,
 * list is guaranteed to be sorted in ascending order.
 */
bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head)
        return false;
    struct list_head *ptr = head->next;
    while (ptr != head && ptr->next != head) {  // ptr is not the tail or head
        element_t *first = list_entry(ptr, element_t, list);
        element_t *second = list_entry(ptr->next, element_t, list);
        if (!strcmp(first->value, second->value)) {
            while (second && !strcmp(first->value, second->value)) {
                list_del(&first->list);
                q_release_element(first);
                first = second;
                if (first->list.next != head) {
                    second = list_entry(first->list.next, element_t, list);
                } else {
                    second = NULL;
                }
            }
            ptr = first->list.next;
            list_del(&first->list);
            q_release_element(first);
        } else {
            ptr = ptr->next;
        }
    }
    return true;
}

q_sort

/*
 * 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.
 */
struct list_head *mergesort_list(struct list_head *head);
struct list_head *merge_two_lists(struct list_head *L1, struct list_head *L2);
void q_sort(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    head->prev->next = NULL;
    head->next = mergesort_list(head->next);
    struct list_head *ptr = head;
    for (; ptr && ptr->next; ptr = ptr->next) {
        ptr->next->prev = ptr;
    }
    ptr->next = head;
    head->prev = ptr;
}

struct list_head *mergesort_list(struct list_head *head)
{
    if (!head || !head->next)
        return head;

    struct list_head *slow = head;
    for (struct list_head *fast = head->next; fast && fast->next;
         fast = fast->next->next)
        slow = slow->next;
    struct list_head *mid = slow->next;
    slow->next = NULL;

    struct list_head *left = mergesort_list(head), *right = mergesort_list(mid);
    return merge_two_lists(left, right);
}

struct list_head *merge_two_lists(struct list_head *L1, struct list_head *L2)
{
    struct list_head *head = NULL, **ptr = &head, **node;
    for (node = NULL; L1 && L2; *node = (*node)->next) {
        node = (strcmp(list_entry(L1, element_t, list)->value,
                       list_entry(L2, element_t, list)->value) <= 0)
                   ? &L1
                   : &L2;
        *ptr = *node;
        ptr = &(*ptr)->next;
    }
    if (L1)
        *ptr = L1;
    else
        *ptr = L2;
    return head;
}