2019q1 Homework1 (lab0)

contributed by <justin871030>

題目資訊

• F01: lab0
• C Programming Lab: Assessing Your C Programming Skills

作業要求

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

Two of the functions: q_insert_tail and q_size should be operated in time

$O(1)$.

作業實做

queue.h

/* Queue structure */
typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail; 
    size_t size;
} queue_t;

為了使 q_insert_tail and q_size 兩個function可以維持在

$O(1)$ ,宣告 tail , size 兩個變數儲存資訊。

q_new

/*
  Create empty queue.
  Return NULL if could not allocate space.
*/
queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    if(!q)
    {
        return NULL;
    }
    q->head = NULL;
    q->tail = NULL;
    q->size=0;
    return q;
}

q_free

使用指標配合while迴圈逐步釋放每個節點的空間。

/* Free all storage used by queue */
void q_free(queue_t *q)
{
    if(q)
    {
        list_ele_t *next_ptr;
        while(q->head)
        {
            next_ptr=q->head->next;
            free(q->head->value);
            free(q->head);
            q->head=next_ptr;
        }
    }
    else
    {
        return;
    }
    free(q);
}

q_insert_head

在每次要求空間時都要檢查是否為 NULL ,假如為 NULL 要回傳 false ,同時釋放已經索取的空間。

/*
  Attempt to insert element at head of queue.
  Return true if successful.
  Return false if q is NULL or could not allocate space.
  Argument s points to the string to be stored.
  The function must explicitly allocate space and copy the string into it.
 */
bool q_insert_head(queue_t *q, char *s)
{
    if (!q) 
    {
        return false;
    }

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

    newh->value = malloc(strlen(s) + 1);
    if (!newh->value) 
    {
        free(newh);
        return false;
    }
    
    strcpy(newh->value, s);
    
    if (!q->size) 
    {
        q->tail = newh;
    }

    newh->next = q->head;
    q->head = newh;
    q->size++;
    return true;
}

q_insert_tail

使用 q_size 使 q_insert_tail 維持在

$O(1)$ 。

/*
  Attempt to insert element at tail of queue.
  Return true if successful.
  Return false if q is NULL or could not allocate space.
  Argument s points to the string to be stored.
  The function must explicitly allocate space and copy the string into it.
 */
bool q_insert_tail(queue_t *q, char *s)
{
    if (!q) 
    {
        return false;
    }

    list_ele_t *newt;

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

    newt->value = malloc(strlen(s) + 1);
    if (!newt->value) 
    {
        free(newt);
        return false;
    }
    strcpy(newt->value, s);

    if (!q->size) 
    {
        q->head = newt;
    } 
    else {
        q->tail->next = newt;
    }
    newt->next = NULL;
    q->tail = newt;
    q->size++;
    return true;
}

q_remove_head

/*
  Attempt to remove element from head of queue.
  Return true if successful.
  Return false if queue is NULL or empty.
  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.)
  The space used by the list element and the string should be freed.
*/
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if((!q)||(!q->head))
    {
        return false;
    }
    
    if(bufsize && sp)
    {
        if (strlen(q->head->value) > bufsize)                 
        {
            strncpy(sp, q->head->value, bufsize);
            sp[bufsize - 1] = 0;
        }
        else 
        {
            strcpy(sp, q->head->value);
        }
    }
    
    list_ele_t *tmp = q->head;
    q->head = q->head->next;
    free(tmp->value);
    free(tmp);
    q->size--;
    return true;
}

q_size

題目要求在

$O(1)$完成，利用先前宣告的 size 完成這個目標。

/*
  Return number of elements in queue.
  Return 0 if q is NULL or empty
 */
int q_size(queue_t *q)
{
    return (!q)?0:q->size;
}

q_reverse

目標是翻轉整個list，首先先排除不需翻轉的情形，
接下來，把 q->tail 指向 q->head 原先的位置，
用while迴圈逐個反轉節點指針的指向。

/*
  Reverse elements in queue
  No effect if q is NULL or empty
  This function should not allocate or free any list elements
  (e.g., by calling q_insert_head, q_insert_tail, or q_remove_head).
  It should rearrange the existing ones.
 */
void q_reverse(queue_t *q)
{
    if(q && (q->size>1))
    {
        list_ele_t *itr_ptr = q->head->next;
        list_ele_t *tmp = itr_ptr;

        q->tail = q->head;
        while(itr_ptr)
        {
            tmp = itr_ptr->next;
            itr_ptr->next = q->head;
            q->head = itr_ptr;
            itr_ptr = tmp;
        }
        q->tail->next = NULL;
    }
}

測試結果

100/100

尚未熟悉Linux的操作，加上好一陣子未碰C語言，debug比想像中花上更多時間。

認真看作業要求，除了提及如何逐步達到要求，還需要進行:

1. 改善程式效能
2. 解釋自動評分系統運作的原理
3. 提及 qtest 的行為和裡頭的技巧

還未達成符合預期目標，請繼續付出！

jserv