2019q1 Homework1 (lab0)

contributed by < warrenanson >

開發環境（已更改）

雙系統linux

$ uname -a
Linux warrenanson 4.18.0-16-generic #17~18.04.1-Ubuntu SMP Tue Feb 12 13:35:51 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0

bash on window 虛擬器（舊版）

$ uname -a
Linux DESKTOP-6FQUATJ 4.4.0-17134-Microsoft #523-Microsoft Mon Dec 31 17:49:00 PST 2018 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 5.4.0-6ubuntu1~16.04.10) 5.4.0 20160609

不要將 Linux 安裝在虛擬機器上，也不要用雲端主機，否則之後用 perf 一類的工具將無法測量出實際程式效能
:notes: jserv

作業目標

Your task is to modify the code in queue.h and queue.c to fully implement the following functions.

• q_new:
  • Create a new, empty queue.
    
    
• q_free:
  • Free all storage used by a queue.
    
    
• q_insert_head:
  • Attempt to insert a new element at the head of the queue (LIFO discipline).
    
    
• q_insert_tail:
  • Attempt to insert a new element at the tail of the queue (FIFO discipline).
    
    
• q_remove_head:
  • Attempt to remove the element at the head of the queue.
    
    
• q_size:
  • Compute the number of elements in the queue.
    
    
• q_reverse:
  • Reorder the list so that the queue elements are reversed in order. This function should not allocate or free any list elements (either directly or via calls to other functions that allocate or free list elements.)
  • Instead, it should rearrange the existing elements

實作

Queue structure

新增 size 以及 tail
則 q_size 和 q_insert_tail 可以在

$O(1)$ 內完成

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

q_new

初始化Queue之設定，若malloc失敗則回傳NULL

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));

    if (!q) /* What if malloc returned NULL? */
        return NULL;

    q->head = NULL;
    q->tail = NULL;
    q->size = 0;
    return q;
}

q_free

無法一次釋放掉整個Queue，必須從head到tail一個個釋放
將q->head移動到next，再將prev本身和其value釋放

void q_free(queue_t *q)
{
    /* How about freeing the list elements and the strings? */
    /* Free queue structure */

    list_ele_t *prev;

    if (!q)
        return;

    while (q->head) {
        prev = q->head;
        q->head = q->head->next;

        if (prev->value)
            free(prev->value);
        free(prev);
    }

    free(q);
}

q_insert_head

由於strcpy回傳的長度不含\0，所以 newh->value所需空間大小要多一

bool q_insert_head(queue_t *q, char *s)
{
    /* What should you do if the q is NULL? */
    if (!q)
        return false;

    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;

    newh->value = malloc(strlen(s) + 1);
    if (!newh->value) {
        free(newh);
        return false;
    }

    strcpy(newh->value, s);

    if (!q->head)
        q->tail = newh;

    q->size++;
    newh->next = q->head;
    q->head = newh;

    return true;
}

q_insert_tail

和q_insert_head差不多
差別在於當q->head為空時，q->tail = newh
當ㄉq->head不為空時， q->tail->next = newh;

bool q_insert_tail(queue_t *q, char *s)
{
    /* You need to write the complete code for this function */
    /* Remember: It should operate in O(1) time */
    if (!q)
        return false;

    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;

    newh->value = malloc(strlen(s) + 1);
    if (!newh->value) {
        free(newh);
        return false;
    }

    strcpy(newh->value, s);

    if (!q->head)
        q->tail = newh;
    else {
        q->tail->next = newh;
    }

    q->size++;
    newh->next = NULL;
    q->tail = newh;

    return true;
}

q_remove_head

依照題目要求當Queue為NULL或空時回傳false
以及copy the removed string to *sp
(up to a maximum of bufsize-1 characters, plus a null terminator.)
所以 sp[bufsize - 1] = '\0'此處要加上\0

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    if (!q || !q->head)
        return false;

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

    list_ele_t *remove_ele;
    remove_ele = q->head;

    q->size--;
    if (q->size == 0)
        q->head = q->tail = NULL;
    else
        q->head = q->head->next;

    free(remove_ele->value);
    free(remove_ele);

    return true;
}

q_size

若Queue不回空就直接回傳size，可在

$O(1)$ 內完成

int q_size(queue_t *q)
{
    /* You need to write the code for this function */
    /* Remember: It should operate in O(1) time */

    if (!q)
        return 0;

    return q->size;
}

q_reverse

這部分本來的寫法是將value從tail開始依序丟到另一個Queue當中
後來改寫成目前這樣，將指標反轉即可達到效果，不需要額外的空間

void q_reverse(queue_t *q)
{
    /* You need to write the code for this function */
    if (!q || q_size(q) == 0 || q_size(q) == 1)
        return;

    q->tail = q->head;
    list_ele_t *rev = q->tail->next;

    while (rev) {
        q->tail->next = rev->next;
        rev->next = q->head;
        q->head = rev;
        rev = q->tail->next;
    }
}