2019q1 Homework1 (lab0)

contributed by < Laurora >

• C Programming Lab
• F01: lab0

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

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

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

jserv

作業要求

透過 link list 實做 LIFO 與 FIFO queue

• q new: 新增一個空的 queue
• q free: 將 queue 清空
• q insert head: 從 queue 的 head 插入新的元素 ( 實做 LIFO )
• q insert tail: 從 queue 的 tail 插入新的元素 ( 實做 FIFO )
• q remove head: 從 queue 的 head 移除元素
• q size: 紀錄 queue 中有幾個元素
• q reverse: 反轉 queue 中所有元素的順序，不得另外配置元素空間協助反轉，過程必須直接針對原來存在的元素執行。

注意

• q_insert_tail 和 q_size 的時間複雜度須為
  $O(1)$
• 須透過呼叫 malloc() 針對各個 string 的長度分配相應的空間，使用完該空間以後要記得 free()

實作過程

queue.h

typedef struct {
    list_ele_t *head, *tail; 
    size_t qsize;
} queue_t;

• 額外新增 qsize 即時紀錄 queue 空間大小，讓 q_size 可在
  $O(1)$ 時間內完成，不須每次呼叫 q_size 便從 queue 的第一個元素開始數，此時所需時間為
  $O(n)$ 。
• 同理，新增 *tail 紀錄 queue 的 tail element 使 q_insert_tail 可在
  $O(1)$ 時間內完成。

q_new

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

• 配置新增的 queue 空間
• 對新增的 queue 做 initialization

q_free

程式碼縮排和風格已有規範，請確保 HackMD 頁面所有程式碼列表都符合

jserv

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

• 清空整個 queue
• 若 queue = NULL ，則跳出函式，避免 dangling pointers

q_insert_head

bool q_insert_head(queue_t *q, char *s)
{
    if (!q)
        return false;
    
    list_ele_t *newh = NULL;
    newh = malloc(sizeof(list_ele_t));
    
    if (!newh) {
        free(newh);
        return false;
    }

    if (q->qsize == 0) {
        newh->next = NULL;
        q->tail = newh;
    }
    newh->value = malloc(strlen(s) + 1);
    if (!newh->value) {
        free(newh->value);
        newh = NULL;
        return false;
    }
    strcpy(newh->value, s);
    newh->next = q->head;
    q->head = newh;
    q->qsize++;

    free(newh->value);
    newh = NULL;
    return true;
}

• 在 queue 的 head 插入新元素
• 要記得 allocate 新的空間給 newnode （ newh ） 以及新增 queue 的元素空間（ strlen(s)+1 ）
• 新增元素之後要把暫存 newnode 的空間釋出（ free(new->value) ）

q_insert_tail

bool q_insert_tail(queue_t *q, char *s)
{
    
    if (!q)
        return false;

    list_ele_t *newt = NULL;
    newt = malloc(sizeof(list_ele_t));

    if (newt == NULL) {
        free(newt);
        return false;
    } 
    newt->value = malloc(strlen(s) + 1);  // define newt

    if (newt->value)
        strcpy(newt->value, s);

    newt->next = NULL;

    if (q->qsize == 0)
        q->head = newt;  //考慮 queue 原來為空

    q->tail->next = newt;
    q->tail = newt;
    q->qsize++;

    free(newt->value);
    newt = NULL;
    return true;
}

• 在 queue 的 tail 插入新元素

q_remove_head

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
   
    if (!q || q->qsize == 0) {
        return false;
    }

    if (q->qsize == 1) {
        q->qsize--;
        q->head = q->tail = NULL;
        q->head->value = NULL;
        return true;
    }
    list_ele_t *temp = q->head;
    q->head = q->head->next;
    if (sp) {  
        memset(sp, '\0', bufsize);//將 sp 空間初始化
        strncpy(sp, temp->value, bufsize - 1);
    }
    q->qsize--;
    return true;
}

• 須考慮 queue 為空，避免 dangling pointers
• strncpy 可指定 copy 的字串長度，由於 remove 使得需要 copy 的字串少一個，因此在這裡使用 strncpy 而非 strcpy

q_size

int q_size(queue_t *q)
{
    if (!q)
        return 0;
    else
        return q->qsize;
}

• 回傳 queue 空間大小

q_reverse

void q_reverse(queue_t *q)
{
    list_ele_t *next, *prev, *current;
    current = NULL;
    prev = NULL;
    if (q->qsize == 0)  
        return;
    current = q->head;
    q->tail = current;  // tail turns out to be head
    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
        q->head = prev;
    }
}

• 將 queue 中的所有元素反轉

實作過程整理與總結

• 過程中犯了最大的一個錯誤就是未考慮 queue 為空的條件，平常很少接觸指標的寫法，因此在分配指標之前經常忽略這個條件，到 ./qtest 時才發現此盲點。
• strdup() 的轉換
  • strdup() 可將字串複製到指定位址，然而並非標準 C 語言函式，是由 malloc() 和 strcpy() 兩個指令實作而來，最後使用完指定位址的 pointer 空間要記得釋放。常見轉換方式如下：
    ​​​​​char *d = malloc(strlen(s) + 1);
    ​​​​​strcpy(d, s);
    ​​​​​/* some instructions here */
    ​​​​​free(d);
    

解釋自動評分系統運作的原理

待補

qtest 的行為與技巧

待補