2019q1 Homework1 (lab0)

contributted by < billqwer1687 >

認真看作業要求，除了提及如何逐步達到要求，還需要進行:

1. 改善程式效能
2. 解釋自動評分系統運作的原理
3. 提及 qtest 的行為和裡頭的技巧

還未達成符合預期目標，請繼續付出！
jserv

開發環境

$ uname -a
Linux bill-X550JX 4.18.0-15-generic #16~18.04.1-Ubuntu SMP Thu Feb 7 14:06:04 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux


$ gcc --version
gcc (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0

作業要求

實作以下 LIFO FIFO Queue 之功能

• qnew: Create a new, empty queue.

• qfree: Free all storage used by a queue.

• qinserthead: Attempt to insert a new element at the head of the queue (LIFO discipline).

• qinserttail: Attempt to insert a new element at the tail of the queue (FIFO discipline).

• qremovehead: Attempt to remove the element at the head of the queue.

• qsize: Compute the number of elements in the queue.

• 詳細說明 :

  • 作業說明
  • C Programming Lab

實作

queue structure

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

新增了指標tail與變數size,目的是為了讓insert from tail與計算size的時間複雜度為

$O(1)$

q_new

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

將queue初始化,且要記得malloc為NULL的狀況

q_free

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

    /* Free queue structure */
    free(q);
}

這邊要先free value才能free temp等到queue為空時再將queue給清空

q_insert_head

bool q_insert_head(queue_t *q, char *s)
{
    if (!q) {
        return false;
    }
    list_ele_t *newh;
    /* What should you do if the q is NULL? */
    newh = malloc(sizeof(list_ele_t));
    if (!newh) {
        return false;
    }
    newh->value = malloc(strlen(s) + 1);
    if (newh->value == NULL) {
        free(newh);
        return false;
    }
    strcpy(newh->value, s);
    if (q->head == NULL) {
        q->head = newh;
        q->tail = newh;
        q->tail->next = NULL;
        q->size++;
        return true;
    }
    /* 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;
    q->size++;
    return true;
}

在寫作業的時候忘記將tail指向NULL所以出現了Bug

q_insert_tail

bool q_insert_tail(queue_t *q, char *s)
{
    /* You need to write the complete code for this function */
    if (!q) {
        return false;
    }
    list_ele_t *newh;
    /* What should you do if the q is NULL? */
    newh = malloc(sizeof(list_ele_t));
    if (!newh) {
        return false;
    }
    newh->value = malloc(strlen(s) + 1);
    if (newh->value == NULL) {
        free(newh);
        return false;
    }
    strcpy(newh->value, s);
    if (q->tail == NULL) {
        q->head = newh;
        q->tail = newh;
        q->tail->next = NULL;
        q->size++;
        return true;
    } else {
        q->tail->next = newh;
        q->tail = q->tail->next;
        q->tail->next = NULL;
        q->size++;
        /* Remember: It should operate in O(1) time */
        return true;
    }
}

這邊也是忘記將tail指向NULL

q_remove_head

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    if (!q || q->head == NULL) {
        return false;
    }
    if (sp) {
        strncpy(sp, q->head->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_ele_t *temp;
    temp = q->head;
    q->head = q->head->next;
    free(temp->value);
    free(temp);
    q->size--;
    return true;
}

sp[bufsize-1]是為了將'\0'放入字串的尾端,因為strncpy不會在尾端留'\0'

q_size

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

因為有使用變數size儲存queue的大小所以在這裡可以以

$O(1)$的時間複雜度求得queue的size

q_reverse

void q_reverse(queue_t *q)
{
    /* You need to write the code for this function */
    if (!q || q->size < 2) {
        return;
    }
    list_ele_t *current = q->head;
    list_ele_t *prev = NULL;
    list_ele_t *rear;
    while (current != NULL) {
        rear = current->next;
        current->next = prev;
        prev = current;
        current = rear;
    }
    q->tail = q->head;
    q->head = prev;
}

此處queue的反轉參考了以下的資料資料參考,然後在q->tail = q->head的地方打反了,找了一下子

TOTAL 100/100

自動評分系統運作的原理

在trace資料夾中有cmd命令檔案,test會依據這些cmd的命令所回傳的結果去判定程式執行是否正確
待補完

qtest 的行為和裡頭的技巧

待補