---
tags: linus2021
---

# 2021q1 Homework1 (lab0)
contributed by < `yellow951321` >

## [C Programming Lab](https://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/labs/cprogramminglab.pdf)

### Queue struce

typedef struct {
    list_ele_t *head;
    list_ele_t *tail;
    int size;
}

增加 tail 以及 siz e兩個新的變數，以達成作業要求。將 insert_tail 和 size 兩個函式的時間複雜度控制在$O(1)$內。

### q_new
trace--10 會檢測當動態配置記憶體失敗時的情形。因此要記得處理意外狀況。

if (!q)
    return NULL;

### q_free
需要迭代去釋放佇列的值，測試資料中會測試。假如q為NULL時須特別處理。

if (!q)
    return;
for (node = q->head; node != NULL;) {
    list_ele_t *tmp = node;
    node = node->next;
    free(tmp->value);
    free(tmp);
}

### q_insert_head
假如輸入的佇列為 NULL 時需要特別處理。

if (!q)
    return false;

strcpy 因為沒有指定字串長度會有風險。因此使用 strncpy ，但 strncpy 不會自動補上 `'\0'` 因此需要手動更改。

strncpy(newh->value, s, strlen(s));
newh->value[strlen(s)] = 0;

### q_insert_tail
為了滿足 $O(1)$ 的時間複雜度。利用 queue struct 中的 tail 變數儲存佇列的尾端。實做過程和 insert_head 基本相同。

### q_remove_head
除了需要檢查佇列，還必須檢查 head 是否為NULL。

if (!q || !q->head)
    return false;

然後需要將被移除的 list_element 的記憶體釋放掉以免造成 memory leak

free(tmp->value);
free(tmp);

### q_size
為了達成 $O(1)$ 的時間複雜度，利用變數 size 直接回傳。並且在 insert 和 remove 時維護 size 的正確性。

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    ...
    --(q->size);
    ...
}

bool q_insert_head(queue_t *q, char *s)
{
    ...
    ++(q->size);
    ...
}

除此之外，也要檢查佇列是否存在。

int q_size(queue_t *q)
{
    /* return fasle if q is NULL*/
    if (!q)
        return 0;
    return q->size;
}

### q_reverse

原先長這樣

graph LR
    subgraph linked list
        head==>node1==>node2
    end
    subgraph pointer
        tmp
        prev
    end

從 head 開始，依序將每個 node 的 next 設為前面的 node ，但是 tmp 去紀錄 next 的值以免被覆蓋掉。並且用 prev 去指向上一個 node

graph LR
    subgraph linked list
        node1==>node2
    end
    subgraph linked list2
        head
    end
    subgraph pointer
        tmp==>node1
        prev==>head
    end

接著將 node1 往前指

graph LR
    subgraph linked list
        node2
    end
    subgraph linked list2
        node1==>head
    end
    subgraph pointer
        tmp==>node2
        prev==>node1
    end

依序做到最尾端並且更新 head 和 tail 即可。

### q_sort
參考 [merge sort](https://www.geeksforgeeks.org/merge-sort-for-linked-list/)後改寫成符合作業要求的資料結構。
但是在 trace--15 會因為下列程式碼遞迴的特性，造成 stack overflow。
這個函式是在處理 merge 兩個 sublists

Node* SortedMerge(Node* a, Node* b) 
{
    ...
    if (a->data <= b->data) { 
        result = a; 
        result->next = SortedMerge(a->next, b); 
    } 
    else { 
        result = b; 
        result->next = SortedMerge(a, b->next); 
    } 
    return (result); 
} 

因此改寫成了當前的迭代方式去解決問題。

list_ele_t *merge(list_ele_t *frontRef, list_ele_t *backRef)
{
    list_ele_t *result;
    list_ele_t *tmp;
    /* Base cases */
    if (frontRef == NULL)
        return backRef;
    else if (backRef == NULL)
        return frontRef;

    /* initial result */
    if (strcmp(frontRef->value, backRef->value) < 0) {
        result = frontRef;
        frontRef = frontRef->next;
    } else {
        result = backRef;
        backRef = backRef->next;
    }
    tmp = result;

    /* Pick either frontRef or backRef, and recur */
    while (frontRef || backRef) {
        if (!backRef) {
            tmp->next = frontRef;
            frontRef = frontRef->next;
        } else if (!frontRef) {
            tmp->next = backRef;
            backRef = backRef->next;
        } else if (strcmp(frontRef->value, backRef->value) < 0) {
            tmp->next = frontRef;
            frontRef = frontRef->next;
        } else {
            tmp->next = backRef;
            backRef = backRef->next;
        }
        tmp = tmp->next;
    }

    return result;
}

### 結果