2019q1 Homework1 (lab0)

contributed by < LiunuXXX >

作業解說
C Programming Lab

tags: DesignOfLinuxkernel-HW

題目要求

• By modifying the code in queue.h and queue.c to fully implement the following fuctions.

  • q_new : Create a new, empty queue

  (Notice that An empty queue is one pointing to a valid structure, but the head field has value NULL.)

  • 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.

  (Noitce that this function should not allocate or free any list elements.)

---

實作

Queue Structure :

為了使 q_size 和 q_insert_tail 在

$O(1)$ 時間內完成，在 Queue Structure 內加入 tail 和 size 分別記錄尾端指標和大小。

/* Queue structure */
typedef struct {
    int size;
    list_ele_t *tail;
    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;

q_new :

初始化queue

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

q_free :

釋放 queue 所佔用的空間，若 queue 為空則 return，
否則利用 this 記錄 head，並逐步釋放每一個 node 的 value 及其空間。

/* Free all storage used by queue */
void q_free(queue_t *q)
{
    /* How about freeing the list elements and the strings? */
    if (!q)
        return;
    list_ele_t *this = q->head;
    while (this) {
        list_ele_t *temp;
        temp = this;
        this = this->next;
        free(temp->value);
        free(temp);
    }
    /* Free queue structure */
    free(q);
}

q_insert_head :

• 插入 node 於 queue_head

• 以下三種情況回傳false :

  1. queue is NULL
  2. malloc 失敗
  3. input string 為 NULL

• 此外，若 queue 為 empty queue，則 head 和 tail 均指向 inserted node (newh)

bool q_insert_head(queue_t *q, char *s)
{
    if (!q)
        return false;
    list_ele_t *newh;
    /* What should you do if the q is NULL? */
    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    /* Don't forget to allocate space for the string and copy it */
    /* What if either call to malloc returns NULL? */
    newh->value = strdup(s);
    if (!newh->value) {
        free(newh);
        return false;
    }
    if (!q->head) {
        q->tail = newh;
    }
    newh->next = q->head;
    q->head = newh;
    q->size++;
    return true;
}

q_insert_tail

• 插入 node 於 queue_tail，

• 同 q_insert_head，以下三種情況回傳 false :

  1. queue is NULL
  2. malloc 失敗
  3. input string 為 NULL

• 若 queue 為 empty queue，則 head 和 tail 均指向 inserted node (newh)

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)
        return false;
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    newh->value = strdup(s);
    if (!newh->value) {
        free(newh);
        return false;
    }
    newh->next = NULL;
    if (!q->head) {
        q->tail = newh;
        q->head = newh; /* if queue is empty */
    }
    q->tail->next = newh;
    q->tail = newh;
    q->size++;
    return true;
}

q_remove_head

• 若 queue is NULL 或 queue is empty 則 return false
• 將 removed node 中的字串複製到 sp
• 若 q_size >= 2，將 head 指向 head 指的下一個 node，並釋放 removed node

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    if (!q || !q->head)
        return false;
    list_ele_t *temp;
    temp = q->head;
    /* Copy removed value to sp */
    if (sp) {
        strncpy(sp, temp->value, bufsize);
        sp[bufsize - 1] = '\0';
    }
    /* If queue has only one node */
    if (q->size == 1) {
        q->head = NULL;
        q->tail = NULL;
    } else {
        q->head = q->head->next;
    }
    q->size--;
    /* Free temp */
    free(temp->value);
    free(temp);
    return true;
}

q_size

若 queue is NULL 則 return 0，否則 return q->size 即可

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

q_reverse

將queue反轉，策略是利用 r 指標緊跟著 p 後面，並從 q_head 開始，循序將各個 node(即 p) 的 next 指向 r，最後再將 head 和 tail 互換即可

void q_reverse(queue_t *q)
{
    if (!q || q->size <= 1)
        return;
    list_ele_t *p, *r, *s, *temp; /* r follows p */
    p = NULL;
    s = q->head;
    while (s) {
        r = p;
        p = s;
        s = s->next;
        p->next = r;
    }
    /* Swap head and tail */
    temp = q->tail;
    q->tail = q->head;
    q->head = temp;
}

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

未完成待補

提及 qtest 的行為和裡頭的技巧

未完成待補