2019q1 Homework1 (lab0)

contributed by < stanleyuan >

目標

• 使用 linked list 來實作 queue 的 operation
• F01: lab0
• 2019q1 Homework1 (作業區)

環境

• OS

$ lsb_release -a
LSB Version:    core-9.20170808ubuntu1-noarch:security-9.20170808ubuntu1-noarch
Distributor ID: Ubuntu
Description:    Ubuntu 18.04.2 LTS
Release:        18.04
Codename:       bionic

• Compiler

$ gcc -v
gcc version 8.3.0 (Ubuntu 8.3.0-6ubuntu1~18.04)

coding style

作業說明有特別提到程式碼一致性的重要，要求使用 clang format 來檢查程式法風格，老師有說一句話滿重要的「工程師是會溝通的」。最近也是滿有感的，常常是今天的我看不懂昨天的我的程式碼，明天的我可能也是看不懂今天的我的程式碼。推薦 vim-autoformat 可以一鍵使用系統中的 formatting program。另外還有 syntastic 除了語法檢查之外，也可以使用系統中的 coding style program 來檢查 coding style。

Programming Tasks

完成以下的 oprations:
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_insert_tail and q_size require that implementations operate in time O(1).

queue.h

• list_ele_t 為 linked list 的 node 的 struct

/* Linked list element */
typedef struct ELE {
    /* Pointer to array holding string. */
    char *value;
    struct ELE *next;
} list_ele_t;

• queue_t 為 queue 的 struct，有一個指向 list_ele_t type 的 pointer。

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

queue.c

• queue 所需實作的 operations
  • q new
  • q free
  • q insert head
  • q insert tail
  • q remove head
  • q size

Implementation

queue_t

由於題目要求 q_insert_tail and q_size 的 時間複雜度都是 O(1)，勢必在 queue_t 中要紀錄 tail node 的位置還有 queue 的大小。需要加上一個 tail 的 pointer 還有整數 size。

新 queue_t:

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

q_new()

舊 q_new:

/*
  Create empty queue.
  Return NULL if could not allocate space.
*/
queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */
    q->head = NULL;
    return q;
}

可以看到註解寫到要考慮如果 malloc return NULL，哪些情況下 malloc 會 return NULL呢？

$ man malloc

RETURN VALUE
The malloc() and calloc() functions return a pointer to the allocated memory, which is suitably aligned for any built-in type. On error, these functions return NULL. NULL may also be returned by a successful call to malloc() with a size of zero, or by a successful call to calloc() with nmemb or size equal to zero.

有錯誤或是 size 為零的時候便會回傳NULL，所以將程式修改為：

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */
    if (!q)
        return q;
    q->head = NULL;
    q->tail = NULL;
    q->size = 0;
    return q;
}

因為已經在 queue_t 裡加上 tail 和 size，也要記得初始化。

q_insert_head

舊 q_insert_head:

bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    /* What should you do if the q is NULL? */
    newh = malloc(sizeof(list_ele_t));
    /* Don't forget to allocate space for the string and copy it */
    /* What if either call to malloc returns NULL? */
    newh->next = q->head;
    q->head = newh;
    return true;
}

在這裡有 3 種情況要考慮：

1. 如果 q 為 NULL
2. 如果 list_ele_t 的 malloc 回傳 NULL
3. 在 list_ele_t 中 value 所需的空間 malloc 如果回傳 NULL

會變成：

bool q_insert_head(queue_t *q, char *s)
{
    if (q) {
        list_ele_t *newh;
        char *news;
        int s_len = strlen(s) + 1;
        newh = malloc(sizeof(list_ele_t));
        if (newh) {
            news = malloc(s_len * sizeof(char));
            if (news) {
                // test later
                memset(news, '\0', s_len);
                strcpy(news, s);
                newh->next = q->head;
                newh->value = news;

                if (!q->head)
                    q->tail = newh;
                q->head = newh;
                q->size += 1;
                return true;
            }
            free(newh);
        }
    }
    return false;
}

q->size 要記得加 1

q_remove_head

舊 q_remove_head:

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    q->head = q->head->next;
    return true;
}

要判斷有沒有 q, q->head, sp

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (q && q->head) {
        list_ele_t *tmp = q->head;
        memset(sp, '\0', bufsize);
        if (sp)
            strncpy(sp, tmp->value, bufsize - 1);
        q->head = q->head->next;
        free(tmp->value);
        free(tmp);
        q->size -= 1;
        return true;
    }
    return false;
}

但一直出錯，後來才發現忘記了q->tail，如果是移除掉最後一個 node 的話：

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (q && q->head) {
        list_ele_t *tmp = q->head;
        memset(sp, '\0', bufsize);
        if (sp)
            strncpy(sp, tmp->value, bufsize - 1);
        q->head = q->head->next;
        if (!q->head)  /* new codes */
            q->tail = q->head;  /* new codes */
        free(tmp->value);
        free(tmp);
        q->size -= 1;
        return true;
    }
    return false;
}

要記得 free 該 node 的 value 還有 node，q->size 要減一。

q_size

舊的 q_size

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

因為在初始化、新增、刪除都有對 q-?size 做紀錄，如果 q 存在的話，只需回傳 q->size:

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 q->size;
    return 0;
}

q_insert_tail

舊的 q_insert_tail:

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 */
    return false;
}

這邊要注意的是要求 O(1)，所以要從 q->tail 下手

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) {
        list_ele_t *tmp = malloc(sizeof(list_ele_t));
        char *news;
        int s_len = strlen(s) + 1;

        if (tmp) {
            news = malloc(s_len * sizeof(char));
            if (news) {
                memset(news, '\0', s_len);
                strcpy(news, s);
                tmp->value = news;
                tmp->next = NULL;

                q->size += 1;
                if (!q->tail)
                    q->head = tmp;
                q->tail->next = tmp;
                q->tail = tmp;
                return true;
            }
            free(tmp);
        }
    }

    return false;
}

test 過了，但發現我在處理 q->tail 的時候好像怪怪的，如果一開始沒有 nodes，q->tail 就會等於 NULL，那 q->tail->next = tmp 會指到哪裡？

但 test 過了（？

最後我改成：

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) {
        list_ele_t *tmp = malloc(sizeof(list_ele_t));
        char *news;
        int s_len = strlen(s) + 1;

        if (tmp) {
            news = malloc(s_len * sizeof(char));
            if (news) {
                memset(news, '\0', s_len);
                strcpy(news, s);
                tmp->value = news;
                tmp->next = NULL;

                q->size += 1;
                if (!q->tail) {
                    q->head = tmp;
                    q->tail = tmp;
                } else {
                    q->tail->next = tmp;
                    q->tail = tmp;
                }
                return true;
            }
            free(tmp);
        }
    }

    return false;
}

才有正確的檢查兩種 cases，測試也過了。

q_free

利用 counter 先紀錄 head node，將 head 往前後再把 counter 所指到的 node free 掉。

void q_free(queue_t *q)
{
    /* How about freeing the list elements and the strings? */
    /* Free queue structure */
    if (q) {
        if (q->head) {
            while (q->head) {
                list_ele_t *counter = q->head;
                q->head = q->head->next;
                free(counter->value);
                free(counter);
            }
        }
        free(q);
    }
    return;
}

q_reverse

這個比較複雜，要將所有 node 的 next pointer 轉向，例如：

會變成：

想法是要用兩個 pointer 來紀錄連續兩個 node 並且變更指標所指向的 node:

void q_reverse(queue_t *q)
{
    /* You need to write the code for this function */

    if (q && q->head && q->head->next) {
        list_ele_t *left, *right;

        right = q->head->next;
        left = q->head;
        q->tail = q->head;
        q->tail->next = NULL;
        
        while (right) {
            q->head = right;
            right = q->head->next;
            q->head->next = left;
            left = q->head;
        }
    }
}

tags: knowThyself linux c linkList w1