2020q3 Homework1 (lab0)

contributed by < mingjer >

Outline

環境

$ uname -a
Linux kdd179 5.4.0-47-generic #51-Ubuntu SMP Fri Sep 4 19:50:52 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version
gcc (Ubuntu 9.3.0-10ubuntu2) 9.3.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

作業要求

在 queue.[c/h] 中完成以下實作

• q_new: 建立新的「空」佇列;
• q_free: 釋放佇列所佔用的記憶體;
• q_insert_head: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則);
• q_insert_tail: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則);
• q_remove_head: 在佇列開頭 (head) 移除 (remove) 給定的元素。
• q_size: 計算佇列中的元素數量。
• q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列元素，換言之，它只能重排已經存在的元素;
• q_sort: 以遞增順序來排序鏈結串列的元素

實作流程

queue.h

• 為了讓 q_size 和 q_insert_tail 兩個funtion能在
  $O(1)$ 時間內完成
• 在 queue_t 中新增兩個參數 ( tail, size )

/* Queue structure */
typedef struct 
{
    /* Linked list of elements */
    /* TODO: You will need to add more fields to this structure
     *        to efficiently implement q_size and q_insert_tail.
     */
    /* TODO: Remove the above comment when you are about to implement. */
    list_ele_t *head;
    list_ele_t *tail;
    int size;
} queue_t;

queue.c

• q_new

  • 先確認malloc有分配給記憶體
  • 有分配 : 初始所有參數
  • 沒分配 : 回傳 NULL

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

• q_free

• q_insert_head

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

• q_insert_tail

• q_remove_head

• q_size

  • 因為要在
    $O(1)$時間內完成，所以不能走訪每個節點來計算
  • 直接從 q->size 中取值，就可以在
    $O(1)$ 內完成

int q_size(queue_t *q)
{
    /* TODO: You need to write the code for this function */
    /* Remember: It should operate in O(1) time */
    /* TODO: Remove the above comment when you are about to implement. */
    if(q != NULL)
    {
        return q->size;
    }
    else
    {
        return 0;
    }
}

• q_reverse

• q_sort