2021q1 Homework1 (lab0)

contributed by < roger90810 >

進度

• new
• free
• insert_head
• insert_tail
• remove_head
• size
• reverse
• sort

開發紀錄

new

按照題目要求，在 malloc 失敗時回傳 NULL

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    if (q == NULL)
        return NULL;
    q->head = NULL;
    q->size = 0;
    return q;
}

free

從 queue 的 head 開始，依序 free

void q_free(queue_t *q)
{
    if (q == NULL)
        return;
    list_ele_t *p = q->head;
    while (p) {
        list_ele_t *n = p;
        p = p->next;
        free(n->value);
        free(n);
    }
    free(q);
}

insert_head

• 按照題目要求，malloc 皆需要檢查是否失敗
• malloc 時需注意，配置的空間大小需要為 strlen(s) + 1，要包含字串結尾的 '\0'
• 避免使用 strcpy()，這裡我使用的是 strncpy()
• 使用 strncpy() 要注意，並不會幫你在結尾補上 '\0'，有兩種方法解決
  1. 複製長度為 n = strlen(s) + 1，因為 strncpy() 中，若要複製的長度大於 src 的長度，多出來的部分就會以 '\0' 代替
  2. 複製長度為 n = strlen(s)，並手動在結尾補上 '\0'，即 newh->value[n] = '\0'
  • 見補充 : strcpy 和 strncpy
• 加入 q->tail 後，需檢查若 list 為空時，插入要將 q->tail 設成新插入的點

bool q_insert_head(queue_t *q, char *s)
{
    if (q == NULL)
        return false;
    list_ele_t *newh = malloc(sizeof(list_ele_t));
    if (newh == NULL)
        return false;
    int n = strlen(s);
    newh->value = malloc((n + 1) * sizeof(char));
    if (newh->value == NULL) {
        free(newh);
        return false;
    }
    strncpy(newh->value, s, n);
    newh->value[n] = '\0';
    newh->next = q->head;
    if (q->size == 0)
        q->tail = newh;
    q->head = newh;
    q->size++;
    return true;
}

insert_tail

• 根據題目要求，需要達到
  $O(1)$ 時間時間複雜度，因此在 queue 資料結構中中加入 list_ele_t *tail
• malloc 配置大小和字串的複製皆和 insert_head 相同
• 記得檢查當 list 為空的時候，需要將 head 設成新插入的點
• list 不為空的時候，queue 的 tail 才存在，才能將 q->tail->next 設成新插入的點

bool q_insert_tail(queue_t *q, char *s)
{
    if (q == NULL)
        return false;
    list_ele_t *newt = malloc(sizeof(list_ele_t));
    if (newt == NULL)
        return false;
    int n = strlen(s);
    newt->value = malloc((n + 1) * sizeof(char));
    if (newt->value == NULL) {
        free(newt);
        return false;
    }
    strncpy(newt->value, s, n);
    newt->value[n] = '\0';
    newt->next = NULL;
    if (q->size == 0)
        q->head = newt;
    else
        q->tail->next = newt;
    q->tail = newt;
    q->size++;
    return true;
}

remove_head

• 根據題目要求，需要將原本 head 的值複製到 sp
• head 及 head->value 需要確實 free

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (q == NULL || q->head == NULL)
        return false;
        
    if (sp != NULL) {
        strncpy(sp, q->head->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    free(q->head->value);
    list_ele_t *t = q->head;
    q->head = q->head->next;
    free(t);
    t = NULL;
    q->size--;
    return true;
}

size

根據題目要求，需要達到

$O(1)$ 時間時間複雜度
因此先在 list.h 中加入 int size

/* Queue structure */
typedef struct {
    list_ele_t *head; /* Linked list of elements */
    int size;
} queue_t;

• 在 insert 和 remove 時，對 size 做增加和減少
• 呼叫 q_size() 時，即可直接回傳 size 的值

int q_size(queue_t *q)
{
    if (q == NULL || q->head == NULL)
        return 0;
    return q->size;
}

reverse

• 採用三個指標的方式，將 list 做 reverse
• 在一開始就將 list 的 tail 設成原本的 head，可以避免做完 reverse 還要在走訪一遍 list

void q_reverse(queue_t *q)
{
    if (q == NULL)
        return;
    list_ele_t *n = NULL;
    list_ele_t *t = NULL;
    list_ele_t *p = q->head;
    q->tail = q->head;
    while (p) {
        t = p;
        p = p->next;
        t->next = n;
        n = t;
    }
    q->head = t;
}

sort

• 根據題目要求，需要達到
  $O(nlogn)$ 時間時間複雜度，因此我選擇使用 merge sort 來實作
• 參考 Linked List Sort 實作手法，採用遞迴的方式實作
• 加入兩個函式

1. list_split

• 首先將 list 拆成數量相等的兩半
• fast 一次會往後兩個節點，而 slow 只會往後一個節點，因此當 fast 到 list 的結尾時，slow 會在 list 一半的位置
• 利用 fast = slow->next 和 slow->next = NULL，即可使 list 拆成兩半

list_ele_t *list_split(list_ele_t *head)
{
    if (head == NULL || head->next == NULL)
        return head;
    
    list_ele_t *fast = head->next;
    list_ele_t *slow = head;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    fast = slow->next;
    slow->next = NULL;

    list_ele_t *l1 = list_split(head);
    list_ele_t *l2 = list_split(fast);

    return list_merge(l1, l2);
}

• 由拆出來的兩半再繼續遞迴，拆至 list 只有一個或沒有元素時就開始合併
• 因為題目規定 sort 過程不能有 malloc，因此採用參考資料中的遞迴方式合併

list_ele_t *list_merge(list_ele_t *l1, list_ele_t *l2)
{
    if (l1 == NULL)
        return l2;
    if (l2 == NULL)
        return l1;

    if (strcmp(l1->value, l2->value) < 0) {
        l1->next = list_merge(l1->next, l2);
        return l1;
    }
    else {
        l2->next = list_merge(l1, l2->next);
        return l2;
    }
}

• q_sort 只需要將 head 傳入 list_split，即可完成排序
• 需要注意的是 list_split 只會回傳排序後新的 head，而 tail 則需要重新指定

void q_sort(queue_t *q)
{
    if (q == NULL || q->size <= 1)
        return;
    q->head = list_split(q->head);
    list_ele_t *t = q->head;
    while (t->next)
        t = t->next;
    q->tail = t;
}

TODO : trace-15-perf 會失敗，但沒有錯誤訊息，正在找出原因

+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
---     trace-15-perf   0/6

目前進度 : –- TOTAL 94/100

補充

strcpy 和 strncpy

輸入 man strcpy 可看到

DESCRIPTION
The strcpy() function copies the string pointed to by src, including the terminating null byte ('\0'), to the buffer pointed to by dest. The strings may not overlap, and the destination string dest must be large enough to receive the copy. Beware of buffer overruns! (See BUGS.)

The strncpy() function is similar, except that at most n bytes of src are copied. Warning: If there is no null byte among the first n bytes of src, the string placed in dest will not be null-terminated.

If the length of src is less than n, strncpy() writes additional null bytes to dest to ensure that a total of n bytes are written.

…

BUGS
If the destination string of a strcpy() is not large enough, then anything might happen. Overflowing fixed-length string buffers is a favorite cracker technique for taking complete control of the machine. Any time a program reads or copies data into a buffer, the program first needs to check that there's enough space. This may be unnecessary if you can show that overflow is impossible, but be careful: programs can get changed over time, in ways that may make the impossible possible.

strncpy

• 若 src 的長度較小，則會在 dest 補上 '\0'
• 但若是長度剛好相等，則 dest 的結尾就不會有 '\0'，也就是不為 null-terminated.
• 若想要有 '\0' 在結尾，只須加上 dest[n - 1] = '\0' 即可

strcpy

• 當 dest 的長度小於 src，也就是 dest 所配置的記憶體空間不夠容納要複製的字串時，這時就會產生 Buffer Overflow 問題
• 這也是為什麼 strcpy() 不安全的原因
• 雖然如此，strcpy() 也是有它的好處和可以使用的時機

根據 man strcpy 中的 NOTE:

NOTES
Some programmers consider strncpy() to be inefficient and error prone. If the programmer knows (i.e., includes code to test!) that the size of dest is greater than the length of src, then strcpy() can be used.

只要能事先確保 dest 的長度大於 src，即可使用 strcpy()