Try   HackMD

2018q3 Homework2 lab(0) Queue

tags: C語言

contributed by < asd757817 >

實驗環境c
作業系統： Ubuntu 16.04 x64
kernel： 4.15.0-34-generic
gcc 版本： gcc version 5.4.0 20160609 (Ubuntu 5.4.0-6ubuntu1~16.04.10)
gcc version 5.4.0 20160609 (Ubuntu 5.4.0-6ubuntu1~16.04.10)

github 使用 develop 分支

請補上實驗環境
課程助教

int q_size

  • 規定時間複雜度為 O(1)
  • 可以推測出這個函式是直接回傳長度，所以必須在 queue list 的結構中加入儲存長度的變數。每次呼叫 insert 長度增一、呼叫 remove 時長度減一。

queue_t 中加入 size 儲存 queue 長度










/\* Queue structure */
typedef struct {
    list_ele_t *head; /* Linked list of elements */
                      /*
                        You will need to add more fields to this structure
                        to efficiently implement q_size and q_insert_tail
                      */
    int size;
} queue_t;

考慮 NULL queue 的情況，在 NULL queue 時直接回傳 0

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

當創建一個 queue 時把長度設為0









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

q_insert_head

  • 規定執行成功回傳 true
  • q 是 null 或不能配置記憶體則失敗回傳 faulse
  • 配置空間儲存傳入的文字內容
bool q_insert_head(queue_t *q, char *s)
{
    /* 判斷 q 跟 s 是否為 NULL */
    if (q == NULL || s == NULL) {
        return false;
    } 
    /* 為新加入的節點配置空間、配置空間儲存 s 的內容 */
    else {
        list_ele_t *newh;
        newh = malloc(sizeof(list_ele_t));
        /* What should you do if the q is NULL? */
        int s_len = sizeof(s);
        char *s_cpy = malloc(s_len);
        /* Don't forget to allocate space for the string and copy it */
        /* What if either call to malloc returns NULL? */
        /* 判斷是否為 NULL ，並把配置的空間釋放 */
        if (newh == NULL || s_cpy == NULL) {
            free(newh);
            free(s_cpy)
            return false;
        } else {
            strncpy(s_cpy, s, s_len);
            newh->next = q->head;
            newh->value = s_cpy;
            q->head = newh;
            q->size += 1;
            return true;
        }
    }
### 
}

在測試時出現 ERROR: Segmentation fault occurred. You dereferenced a NULL or invalid pointer 的錯誤警告，檢查後發現程式在 malloc failure 時會對 newh、s_cpy 都釋放記憶體，但兩者至少有一個是 NULL 就造成了這個錯誤。
把程式修正成：

  • 兩者都不為 NULL 才進行 insertion
  • 檢查 newh、s_cpy 不為 NULL 就釋放記憶體
bool q_insert_head(queue_t *q, char *s)
{
    if ( !q || !s ) {
        printf("false");
        return false;
    } else {
        list_ele_t *newh;
        newh = malloc(sizeof(list_ele_t));
        char *s_cpy = malloc(sizeof(s));
        /* What should you do if the q is NULL? */
        /* Don't forget to allocate space for the string and copy it */
        /* What if either call to malloc returns NULL? */
        if (newh && s_cpy) {
            strcpy(s_cpy, s);
            newh->next = q->head;
            newh->value = s_cpy;
            q->head = newh;
            if ( !q->tail )
                q->tail = newh;
            q->size += 1;
            return true;
        } else {
            if (newh)
                free(newh);
            if (s_cpy)
                free(s_cpy);
            return false;
        }
    }
}

bool q_insert_tail

  • 在 queue 的結尾加入新的物件
  • 時間複雜度要求 O(1)
    一般在結尾加入新的物件必須走訪至物件的 next 為 NULL 時，把 next 從 NULL 指向新的物件，但因為需要走訪整個 queue 所以時間複雜度為 O(n)，為了在 O(1)找到 queue 結尾，因此需要新增一個指在 queue 結尾的指標。

修正 queue_t

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

bool q_insert_tail 大致上內容與 insert_head 相似，只有部份地方需要修改

  • 新加入的物件由 tail 的 next 指向
  • 若 queue 的 head 還是 NULL 時需把 head 設定成新加入的物件
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 */
    /* 判斷傳入的兩個指標是否為 NULL */
    if (q == NULL || s == NULL) {
        return false;
    } else {
    /* 為新加入 queue 的物件配置空間、為新物件的 value 配置空間 */
        list_ele_t *newh;
        newh = malloc(sizeof(list_ele_t));
        int s_len = sizeof(s);
        char *s_cpy = malloc(s_len);
    /* 檢查配置空間是否成功 */
        if (newh == NULL || s_cpy == NULL) {
            free(newh);
            free(s_cpy);
            return false;
        } else {
            strncpy(s_cpy, s, s_len);
            newh->next = NULL;
            newh->value = s_cpy;
        /* 若 head 為 NULL 表示目前 queue_size 為 0，此時加入的物件同時也是 head */
            if (q->head == NULL)
                q->head = newh;
        /* 若 tail 不是 NULL 則把 tail->next 指向新加入的物件 */
            if (q->tail != NULL)
                q->tail->next = newh;
        /*  把 tail 設成新加入的物件 */
            q->tail = newh;
            q->size += 1;
            return true;
        }
    }
}

在 test 時會出現 ERROR: Segmentation fault occurred. You dereferenced a NULL or invalid pointer
檢查後發現是判斷 newh、s_cpy 在釋放記憶體時出錯，原本是只要其中一個為 NULL 就釋放記憶體並回傳 false，但這樣當會對 NULL 的部份也進行一次 free ，應該改為其中一個為 NULL而另一個不為 NULL 的情況釋出不為 NULL 的記憶體才對

修改後的為

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 || !s) {
        return false;
    } else {
        list_ele_t *newh;
        newh = malloc(sizeof(list_ele_t));
        char *s_cpy = malloc(sizeof(s));
        if( newh && s_cpy) {
            //strncpy(s_cpy, s, s_len);
            s_cpy = strcpy(s_cpy,s);
            newh->next = NULL;
            newh->value = s_cpy;
            if (q->head == NULL) {
                q->head = newh;
            }
            if (q->tail != NULL)
                q->tail->next = newh;
            q->tail = newh;
            q->size += 1;
            return true;
        }
        else{
            if(s_cpy)
                free(s_cpy);
            if(newh)
                free(newh);
            return false;
        }

    }
}

void q_free 將所有配置過的空間釋放

所有配置過的空間有：

  • queue_t
  • list_ele_t
  • space for list_ele_t->value
void q_free(queue_t *q)
{
    /* How about freeing the list elements and the strings? */
    /* Free queue structure */
    list_ele_t *to_be_free = q->head; //把要 free 的對象指定成當前的 head
    while(to_be_free){
        q->head = q->head->next; // 走訪 queue 中的所有物件
        free(to_be_free->value); // free value 
        free(to_be_free);        // free list_ele_t
        to_be_free = q->head;    // 更新要 free 的目標
    }
    free(q);                     // free queue_t    
}

bool q_remove_head

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    /* 當 queue 是 NULL 時回傳 false */
    if (q == NULL) {
        return false;
    }
    /* 當 queue head 為 NULL 時回傳 NULL */
    else if(q->head == NULL){
        return false;
    }else {
        /* You need to fix up this code. */
        /* 把原本 value 的內容複製到 sp */
        list_ele_t *old_head = q->head;
        int str_len = sizeof(old_head->value);
        strncpy(sp, old_head->value, str_len);
        /* 更新 queue head */
        q->head = q->head->next;
        /* 釋放原本 queue head 的空間 */
        free(old_head->value);
        old_head->value = NULL;
        free(old_head);
        old_head = NULL;
        q->size -= 1;
        return true;
    }
}

在 make test 時一直出現錯誤訊息，目前已知是strncpu出現問題，但仍在處理中。

ERROR:  Removed value meerkat_XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX != expected value meerkat
Error limit exceeded.  Stopping command execution

仔細重新閱讀了題目

If sp is non-NULL and an element is removed, copy the removed string to *sp
(up to a maximum of bufsize-1 characters, plus a null terminator.)

真正要取的字串長度是bufsize-1，最後一位要補成結尾符號('\0')，而 strncpy 只是將長度 n 的字串複製到目標中，並沒有加入結尾符號，因此我的作法：

  • 把目標內 bufsize 長度都設成結尾符號再使用 strncpy 複製字串

修改後的 q_remove_head 如下：

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    if (!q) {
        return false;
    } else if (!q->head) {
        return false;
    } else {
        /* You need to fix up this code. */
        /* How about freeing the list elements and the strings? */
        /* Free queue structure */
        if (sp) {
            memset(sp,'\0',bufsize);
            strncpy(sp, q->head->value + '\0', bufsize-1);
            printf("%s\n",sp);
        }
        list_ele_t *to_be_free = q->head;
        q->head = q->head->next;
        if (q->size == 1 && !q->head) {
            q->tail = NULL;
        }
        free(to_be_free->value);
        free(to_be_free);
        q->size -= 1;
        return true;
    }
}

void q_reverse

題目要求：

  • 不能配置額外的記憶體空間
  • 對於 NULL queue or empty queue 沒有影響
  • 作法：
    • 對 NULL queue 和 empty queue 不做任何事情
void q_reverse(queue_t *q)
{
    /* You need to write the code for this function */
    if( q && q->head){
        q->tail = q->head;
        list_ele_t *pre_node = NULL;
        list_ele_t *next_node = q->head->next;

        while(next_node){
            q->head->next = pre_node;
            pre_node = q->head;
            q->head = next_node;
            next_node = q->head->next;
        }
        q->head->next = pre_node;
    }
}

評分機制相關

Makefile 撰寫

  • 以 "=" 或是 ":=" 賦予數值
  • target: dependencies
    • target 是要產生的目標物件，dependencies 是產生目標需要引入的物件，若找不到物件會在 makefile 中尋找是否有產生該物件的規則
    • : 後以 tab 隔開，不是空格(空白鍵)
    • all 是一個最終的目標，只有輸入 make 時，就是以產生 all 為目標進行動作

以這次作業的 makefile 為例子：

  • 只輸入 make 指令是，程式的目標是產生 all 這個檔案，而產生這個檔案需要 $(GIT_HOOKS)、qtest，所以程式接著尋找產生這兩個檔案所需要的動作。
  • 測試分數時會使用指令 make test，指定產生的目標檔案為 test，因此會執行
test: qtest scripts/driver.py
    scripts/driver.py

Git hook

是一個在執行 commit 或是 merge 指令時會觸發的一個腳本，又可以分成 pre-hook 或是 post-hook，一個是在指令輸入後執行前觸發；一個是在指令執行完畢後觸發。

這一次作業使用的是 pre-hook，當我們要進行提交的時候會觸發腳本，檢查這次提交之前是不是有執行過 clang-format 的排版檢查，而這次作業會使用的 clang-format、cppcheck 在腳本內也會檢查是否安裝，若是未安裝會以文字警告尚未安裝。

Clang-format

調整 C 語言的原始碼的格式，以方便開發人員閱讀，由於不同的開發人員有不同的習慣，在團隊開發時為了使團隊間的溝通順利，可以利用 clang-format 調整程式碼的格式，原本套件就有預設Google、Chromium、Mozilla 等程式，開發人員也可以自行定義團隊的開發格式。

實際操作：
clang-format -i target.c -i 參數會抓當前目錄底下的格式檔進行調整。

cppcheck

一個靜態分析的工具，不用實際運行程式只透過原始碼分析找出程式的問題，所找的問題類型是編譯器難以察覺的。

檢查項目包括：

  • double free
  • 自動變量生存週期檢查
  • 空指針引用
  • sizeof內的計算
  • 檢查動態配置是否被釋放
  • …等功能

在這次的作業中使用 cppcheck 檢查動態配置的記憶體是否有正確釋放、程式是否操作 null pointer 等，檢查可以編譯執行但卻有疑慮的問題。

評分機制

  • qtest.c 是用來對 queue 進行操作的介面
  • report.c 定義了對 queue 進行操作後預期得到的結果，若是結果和預期不符會輸出錯誤訊息
  • harness.c 裡面定義了 malloc、free 記憶體的行為，用來測我們所做的是否有在正確的時間點進行 malloc、free
  • 輸入指令 make test 可以測試程式並計算分數。在 Makefile 中得知這行指令會運行 driver.py 檔案。
  • driver 檔案內引入了許多測試用的腳本(trace-01 ~ trace-01)，在 trace 資料夾中可以看見每個腳本內對 queue 進行的操作，測試程式開啟 qtest並依據腳本內的指令進行操作，根據 report、harness 回傳的訊息給分。

效能改善

  • 反轉陣列
    • 由於原本是 queue 的結構是 singly linked list ，在做反向運算時需要額外紀錄當前節點、當前節點的前一個節點跟當前節點的下一個節點，才能完成反轉，但是若把結果修改成 doubly linked list 直接由節點本身就可以取得前一個節點與下一個節點，如此一來可以節省做反向運算的時間。
Last changed by 
 
yenpo_c
0
429
Published on HackMD