2019q1 Homework1 (lab0)

contributed by < joey-ycpeng >

作業要求

• 用 linked-list 實做的 queue：
  

• 藉由 queue.h 裡的兩個 data structure 實做出一個 string 的 queue

  • queue_t:
    • 是一個 linked-list
    • head 指向第一個 element，初始化為 NULL
    • NULL queue: 一個指向 NULL 的 queue_t pointer
    • empty queue: head 為 NULL 的 queue_t instant
  • list_ele_t:
    • value 指向一個 string (array of char)
    • next 指向下一個 list_ele_t
    • 最後一個 element 的 next 指向 NULL

/* Linked list element (You shouldn't need to change this) */
typedef struct ELE {
    /* Pointer to array holding string.
       This array needs to be explicitly allocated and freed */
    char *value;
    struct ELE *next;
} list_ele_t;

/* 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
                      */
} queue_t;

在 queue.h & queue.c 實做出下列 function

• q_new: Create a new, empty queue.
• q_free: Free all storage used by a queue.
• q_insert_head: Attempt to insert a new element at the head of the queue (LIFO discipline).
• q_insert_tail: Attempt to insert a new element at the tail of the queue (FIFO discipline).
• q_remove_head: Attempt to remove the element at the head of the queue.
• q_size: Compute the number of elements in the queue.
• q reverse: Reorder the list so that the queue elements are reversed in order. This function should not allocate or free any list elements (either directly or via calls to other functions that allocate or free list elements.) Instead, it should rearrange the existing elements.

---

實做

• q_size:
  • 記得檢查 NULL queue
  • 因為要求 O(1)，所以在 queue_t 加入 int size
• q_new:
  • 加入 q->size = 0;
• q_free:
  • 記得檢查 NULL queue
  • 每次iterate都先把 next 存起來，接著把 value free 掉，再把 element free 掉
  • queue size - 1
  • 最後把 next assign 給 element，繼續下一次iteration 直到 element 為 NULL

void q_free(queue_t *q)
{
    if (NULL == q)
        return;
    /* How about freeing the list elements and the strings? */
    /* Free queue structure */
    list_ele_t *e = q->head, *e_next;
    while(e) {
        e_next = e->next;
        if (e->value)
            free(e->value);
        free(e);
        e = e_next;
    }
    free(q);
}

• q_insert_head:
  • 注意要 ++q->size，並在 q->size==1 的時候更新 q->tail
• q_insert_tail:
  • 因為要求 O(1) 的執行時間，所以在 queue_t 裡加入 list_ele_t *tail
  • 一樣要 ++q->size，並在 q->size==1 的時候更新 q->head
• q_remove_head:
  • 注意 q->head = q->head->next 之前要先把 q->head 存起來準備之後 free 掉
• q_reverse:
  • 想法：建立一個暫時的 new_head，遍歷整個 queue，每次 iteration 把 head 接在 new_head 的前面直到 tail 。最後再 assign new_head to head 。

void q_reverse(queue_t *q)
{
    list_ele_t *new_head = NULL, *e;
    /* You need to write the code for this function */
    if (NULL == q || NULL == q->head)
        return;

    q->tail = q->head;
    while (q->head) {
        e = q->head;
        q->head = q->head->next;
        e->next = new_head;
        new_head = e;
    }
    q->head = new_head;
}

---

效能改善

---

自動評分系統運作的原理

qtest 的行為與技巧

tags: homework