2019q1 Homework1 (lab0)

contributed by < dianarolien >

開發環境

Linux dianarolien-Aspire-E5-575G 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

作業要求

作業要求寫得很多，不是只有下方這件事，請重新閱讀指定材料並摘要

jserv

作業說明 / cprogramminglab

• 實驗目標為實作 queue

  • first in, first out (FIFO)
  • last in, first out (LIFO)

• 實作以下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.
  • q_insert_tail : Attempt to insert a new element at the tail of the queue.
  • 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.

• 解釋自動評分系統運作的原理
• 提及 qtest 的行為和裡頭的技巧

實作

Queue structure

typedef struct ELE {
    char *value;
    struct ELE *next;
} list_ele_t;

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

q_new

Create a new, empty queue.

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

q_free

Free all storage used by a queue.

void q_free(queue_t *q)
{
    if (q == NULL)
        return;

    /* How about freeing the list elements and the strings? */
    if (q->head != NULL) {
        list_ele_t *p = q->head;
        list_ele_t *n = q->head->next;
        while (p != NULL) {
            free(p->value);
            free(p);
            p = n;
            if (n != NULL)
                n = n->next;
        }
    }
    /* Free queue structure */
    free(q);
}

q_insert head

Attempt to insert a new element at the head of the queue (LIFO discipline).

bool q_insert_head(queue_t *q, char *s)
{
    /* What should you do if the q is NULL? */
    if (q == NULL)
        return false;
   
   /* What if either call to malloc returns NULL? */
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL)
        return false;

    newh->value = (char *) malloc((strlen(s) + 1) * sizeof(char));
    if (newh->value == NULL) {
        free(newh);
        return false;
    }
    strncpy(newh->value, s, strlen(s) + 1);
    newh->next = q->head;
    q->head = newh;
    q->size += 1;
    if (q->tail == NULL)
        q->tail = newh;
    return true;
}

q_insert_tail

Attempt to insert a new element at the tail of the queue (FIFO discipline).

bool q_insert_tail(queue_t *q, char *s)
{
    /* Remember: It should operate in O(1) time */
    if (q == NULL)
        return false;

    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL)
        return false;

    newh->value = (char *) malloc((strlen(s) + 1) * sizeof(char));
    if (newh->value == NULL) {
        free(newh);
        return false;
    }
    strncpy(newh->value, s, strlen(s) + 1);
    newh->next = NULL;
    if (q->tail != NULL)
        q->tail->next = newh;
    q->tail = newh;
    if (q->head == NULL)
        q->head = newh;
    q->size += 1;
    return true;
}

q_remove_head

Attempt to remove the element at the head of the queue.

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (q == NULL)
        return false;
    if (q->head == NULL)
        return false;

    list_ele_t *tmp = q->head;
    q->head = q->head->next;
    if (sp != NULL) {
        strncpy(sp, tmp->value, bufsize - 1);
        sp[bufsize - 1] = 0;
    }
    free(tmp->value);
    free(tmp);
    q->size -= 1;
    if (q->size == 0)
        q->tail = NULL;
    return true;
}

q_size

Compute the number of elements in the queue.

int q_size(queue_t *q)
{
    if (q != NULL)
        return q->size;
    return 0;
}

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.

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

    list_ele_t *p = NULL;
    list_ele_t *t = q->head;
    list_ele_t *r = q->head->next;
    while (t != NULL) {
        t->next = p;
        p = t;
        t = r;
        if (r != NULL)
            r = r->next;
    }
    q->tail = q->head;
    q->head = p;
}

自動評分系統運作的原理

qtest 的行為和裡頭的技巧