Try   HackMD

2021q1 Homework1 (lab0-c)

contributed by < JimmyZhan070100 >

tags: linux2021

Queue 實做

github

Queue structure

題目要求必須在

O(1) 的時間內得到 qeue 的尾端和大小,所以在結構裡增加 tailsize

typedef struct { list_ele_t *head; /* Linked list of elements */ list_ele_t *tail; /* Insert tail in O(1) time */ int size; /* Get count of elements in O(1) time */ } queue_t;

New

產生一個新的 queue,同時初始化相關的資料結構

Free

釋放 queue 前需要檢查是否 queue 為 NULL。
再來釋放 queue 上的每個 node 使用空間,此外必須先將字串的空間先釋放後,再來釋放 node

Insert head/tail

新增一個 node 並且將字串放入 value,然後將 node 放入頭/尾

  • 注意
    • 如果 queue 是空的,則必須改動 head/tail
    • 不論是新增一個 node 或為 value 要一塊空間都必須確認是否 malloc 有成功,若沒有成功則必須 return false
    • 為字串新增一塊空間時必須 +1 負責存放 \0
      malloc(sizeof(char) * (strlen(s) + 1))

Remove head

移除之前必須檢查是否 queue 為空的,以及 sp 是否有指向一塊記憶體位置。
依據題目要求,必須先將 value 指向的字串複製到 sp。接著改變 q->head 方向後,再釋放原本 q->head 的空間

題目說 up to a maximum of bufsize-1 characters, plus a null terminator,要注意字串的正確長度

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

Size

因為在結構上有紀錄節點的長度,所以只需要回傳 q->size 即可,不過要注意若 q 是空的,則要回傳 0

Reverse

宣告三個指標 curr, next, tmp。利用 curr 紀錄當下的節點,next紀錄下一個節點,tmp負責當作中介

list_ele_t *curr = q->head, *next = q->head->next, *tmp;






struct



curr
curr



n2

1-value

next



curr->n2:f0





next
next



n3

2-value

next



next->n3





n1

head

size

tail



n1:f0->n2





nn

...

next



n1:f2->nn





n2:f1->n3





n3:f1->nn





接著將 tail 改為 head 的位置,並進入迴圈改變節點的順序

while (next) { tmp = next->next; next->next = curr; curr = next; next = tmp; }

最後將 tail->next 改為 NULL,以及 head 指向 curr 所在的節點。

q->tail->next = NULL; q->head = curr;

Sort

如何測試

測試所有測資
$ make test
針對單一個測資可以用:
$ ./qtest -f <command file>
以得到更詳細的程式運行狀況,方便檢查程式的錯誤