2019q1 Homework1 (lab0)

contributed by < andy78644 >

實驗環境資訊

$ uname -a
Linux andy78644-GP72VR-7RFX 4.18.0-15-generic #16~18.04.1-Ubuntu SMP Thu Feb 7 14:06:04 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0

實做

queue.h

typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail;
    size_t size;

    /*
           You will need to add more fields to this structure
           to efficiently implement q_size and q_insert_tail
         */
} queue_t;

因為題目要求q_insert_tail和q_size需要達到

$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));

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

q_free

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

        free(q->head->value);
        free(q->head);
        q->head = tmp;
    }
    free(q);
}

free要先free list 的value 再去free list

q_insert_head

/*
  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)
{
    list_ele_t *newh;
    /* What should you do if the q is NULL? */
    if (!q)
        return false;
    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 = malloc(strlen(s) + 1);
    if (!newh->value) {
        free(newh);
        return false;
    }
    // newh->value=strdup(s);
    strcpy(newh->value, s);
    if (q->head == NULL) {
        q->tail = newh;
    }
    newh->next = q->head;
    q->head = newh;
    // free(newh);
    q->size++;
    return true;
}

當malloc產生null,要進行free的時候,不能free value 會產生free null的問題
一開始我使用strdup結果產生錯誤,它會多malloc出一個空間因此須使用strcpy來代替strdup

q_insert_tail

/*
  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)
{
    /* 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 = malloc(strlen(s) + 1);
    if (!newh->value) {
        free(newh);
        return false;
    }
    strcpy(newh->value, s);
    if (q->size == 0) {
        q->head = newh;
    } else {
        q->tail->next = newh;
    }
    newh->next = NULL;
    q->tail = newh;

    q->size++;
    return true;
}

使用q_size讓q_insert_tail達到

$O(1)$

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)
{
    /* You need to fix up this code. */
    if (!q || !q->head)
        return false;
    if (sp) {
        strncpy(sp, q->head->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_ele_t *tmp;
    tmp = q->head;

    q->head = q->head->next;
    free(tmp->value);
    free(tmp);
    q->size--;
    return true;
}

q_size

/*
  Return number of elements in queue.
  Return 0 if q is NULL or empty
 */
int q_size(queue_t *q)
{
    if (q != NULL && (q->head != NULL))
        return q->size;
    /* You need to write the code for this function */
    /* Remember: It should operate in O(1) time */
    return 0;
}

q_reverse

/*
  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)
{
    /* You need to write the code for this function */
    if (q && (q->size > 1)) {
        list_ele_t *now = q->head;
        list_ele_t *tmp = now->next;
        q->tail = q->head;
        while (tmp != NULL) {
            now = tmp;
            tmp = tmp->next;
            now->next = q->head;
            q->head = now;
        }
        q->tail->next = NULL;
    }
}

測試結果

100/100