2020q1 Homework (lab0)

contributed by <love1357983>

tags: `linux2020`

Image Not Showing Possible Reasons
The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported
Learn More →

作業描述

開發紀錄

queue_t

說明：

為了讓 q_insert_tail 和 q_size 在

O (1)

的時間複雜度，在 queue_t 結構中增加以下欄位。

tail 變數名稱 - list_ele_t 型態
size 變數名稱 - int 型態

`queue.h` 實作:

typedef struct {
    list_ele_t *head; 
    list_ele_t *tail;
    int size;
} queue_t;

建立

說明：

在執行 qtest 程式一開始，會先呼叫 queue.h 中 q_new 函式，將欄位進行初始化。其中使用 malloc 函式，配置一個 queue_t 需要的空間，如果成功的話會回傳 void* 的記憶體位址；若失敗則回傳 NULL ，所以需要檢查 malloc 是否成功。

q_new

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

釋放

說明：

將所建立 queue_t 型態的 q 記憶體空間釋放，包含每個節點上的動態配置的資料 value 欄位。在運行前一樣會先檢查 queue_t 是否存在，如果不存在直接返回。在這裡使用 while 迴圈走訪鏈結串列中各個節點。在 while 迴圈中，使用 prev 記錄目前 tmp 的記憶體位置，在 tmp 移動到下一個節點後，再將該節點中的 next 欄位作釋放動作，完成該節點在記憶裡空間完全釋放完畢。

q_free

void q_free(queue_t *q) 
{
    if (!q)
        return;
    list_ele_t *tmp = q->head;
    while (tmp) {
        list_ele_t *ptr = tmp;
        free((tmp->value));
        tmp = tmp->next;
        free(ptr);
    }
    free(q);
}

`LIFO`插入

說明：

使用 LIFO 方法進行排序，先建立 newh 的 list_ele_t 節點，將接收到的 s ，使用 strdup 複製字串加入 newh 的 value 中。把 q->head 接續在 newh 的 next 中，修改 q->head 為 newh ，判斷 q_size 是否為 0 ，如果為 0 時，再把 q->tail 設定為 newh ，最後再將 q_size 增加 1。

q_insert_head

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

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

    newh->value = strdup(s);
    if (!newh->value) {
        free(newh);
        return false;
    }   
    newh->next = q->head;

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

`FIFO`插入

說明：

同理，使用 FIFO 方法進行排序，先建立 newt 的 list_ele_t 節點，同樣將接收到的 s ，使用 strdup 複製字串加入 newt 的 value 中，把 newt 的 next 設定為 NULL ，把原 q->tail->next 為 NULL 設定為先前建立出的 newt ，再把原先的 q->tail 設定為 newt 進行取代，最後將 q_size 增加 1 。另外，在呼叫此函式開始時，會先取得 q_size 進行判斷，如果為 0 時，會呼叫與 q_insert_head 相同的程式碼，進行新增節點動作。

q_insert_tail





























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

    if (!q_size(q)) {
        q_insert_head(q, s);
        return true;
    }

    list_ele_t *newt = malloc(sizeof(list_ele_t));
    if (!newt) {
        free(newt);
        return false;
    }

    newt->value = strdup(s);
    if (!newt->value) {
        free(newt);
        return false;
    }
    newt->next = NULL;

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

    ++q->size;
    return true;
}

刪除

說明：

將取得 q->head->value 節點內容複製到 sp 中，然後釋放該節點及資料所佔用的記憶體空間。先建立 tmp 的 list_ele_t 節點，記錄 q->head 該節點記憶體位置，再將 q->head 指向 tmp->next 記憶體位置，再把 tmp 記憶體位置進行釋放，將 q_size 減 1 。若 q_size 等於 0 時，須將 q->tail 記憶體空間進行清空動作。

q_remove_head



















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

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

    list_ele_t *tmp = q->head;
    q->head = tmp->next;
    --q->size;
    if (!q_size(q))
        q->tail = NULL;
    free(tmp->value);
    free(tmp);
    return true;
}

個數

說明：

如 queue_t 加入記錄佇列的 size 個數，可將計算 linked list 減少所需時間，將時間複雜度從

O (n)

縮短到

O (1)

。

q_size




int q_size(queue_t *q)
{
    return (q == NULL) ? 0 : q->size;
}

反轉

說明：

此函式限制在不建立額外配置空間下，先建立 prev 初始狀態為 NULL, curr 初始狀態為 q->head, prec 初始狀態為 q->head->next ，共三個 list_ele_t 節點。將當前的 curr 佇列位置從新指向 next 的 prev 記憶體位置，因為 curr 的 next 已經從新指向了，所以 prec 節點是為了讀取原有 q->next 佇列中的記憶體位置，使用 while 迴圈進行 queue_t 輪詢至 prec 為 NULL 為止，最後在將 queue_t 中 head, tail 進行對調動作。

q_reverse

void q_reverse(queue_t *q)
{
    if (!q || !q->head)
        return;

    list_ele_t *prev = NULL, *curr = q->head, *prec = q->head->next;

    while (prec) {
        curr->next = prev;
        prev = curr;
        curr = prec;
        prec = prec->next;
    }
    curr->next = prev;

    q->tail = q->head;
    q->head = curr;
    return;
}

排序

說明：

以下程式碼使用 Bubble Sort 法，以遞增順序來排序鏈結串列的元素，其執行的時間複雜度為

O (n^{2})

。透過 strcasecmp 將 first->value 和 curr->value 比較，當strcasecmp 回傳數值小於 0 時，把兩個節點的 value 交換動作。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

這邊程式碼可能比較偷懶，只對 list_ele_t 中的 value 內容進行交換的動作，這邊有可能在兩者被分配的記憶體空間大小不同，而造成記憶體洩露 (memory leak)，後續會針對樣的問題進行實驗與研究。

q_sort

void q_sort(queue_t *q)
{
    if (!q || !q->head)
        return;

    list_ele_t *first = q->head;
    while (first) {
        list_ele_t *curr = q->head;
        while (curr) {
            if (strcasecmp(first->value, curr->value) < 0) {
                char *tmp = curr->value;
                curr->value = first->value;
                first->value = tmp;
            }
            curr = curr->next;
        }
        first = first->next;
    }
    return;
}

make test評分

// Mar 3 -> make test

---	Trace		Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
---	trace-01-ops	6/6
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, and remove_head
---	trace-02-ops	6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
---	trace-03-ops	6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, and sort
---	trace-04-ops	6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, and sort
# bear gerbil jiu kuo sheng
---	trace-05-ops	5/5
+++ TESTING trace trace-06-string:
# Test of truncated strings
---	trace-06-string	6/6
+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
---	trace-07-robust	6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
---	trace-08-robust	6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
---	trace-09-robust	6/6
+++ TESTING trace trace-10-malloc:
# Test of malloc failure on new
---	trace-10-malloc	6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
---	trace-11-malloc	6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
---	trace-12-malloc	6/6
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
---	trace-13-perf	6/6
+++ TESTING trace trace-14-perf:
# Test performance of size
---	trace-14-perf	6/6
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Not sorted in ascending order
---	trace-15-perf	0/6
+++ TESTING trace trace-16-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Not sorted in ascending order
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Not sorted in ascending order
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Not sorted in ascending order
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Not sorted in ascending order
---	trace-16-perf	0/6
+++ TESTING trace trace-17-complexity:
# Test if q_insert_tail and q_size is constant time complexity
Probably constant time
Probably constant time
---	trace-17-complexity	5/5
---	TOTAL		88/100