C Programming Lab: Assessing Your C Programming Skills

Programming Task

Your task is to modify the code in queue.h and queue.c to fully implement the following functions.

queue_new: Create a new, empty queue.
queue_free: Free all storage used by a queue.
queue_insert_head: Attempt to insert a new element at the head of the queue (LIFO discipline).
queue_insert_head: Attempt to insert a new element at the head of the queue (LIFO discipline).
queue_remove_head: Attempt to remove the element at the head of the queue.
queue_size: Compute the number of elements in the queue.
queue_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.

Testing

make

在shell里输入

make

会根据makefile自动编译源文件，特别注意，修改源文件后，别忘了执行make

qtest

./qtest

可进入交互式命令行界面，输入help，可以显示qtest命令的用法

./qtest -f traces/xxx.cmd

可测试某一样例，并显示哪一步有问题

make test

make test

会运行./traces目录下所有的测试样例，最终输出得分

Solution

queue_t

修改queue.h头文件，便于尾插和计算队列长度

typedef struct {
    list_ele_t *head;
    list_ele_t *tail;
    size_t length;
} queue_t;

queue_t *queue_new(void)

/**
 * @brief Allocates a new queue
 * @return The new queue, or NULL if memory allocation failed
 */
queue_t *queue_new(void) {
    queue_t *q = (queue_t *)malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */
    if (q == NULL) return NULL;
    q->head = NULL;
    q->tail = NULL;
    q->length = 0;
    return q;
}

void queue_free(queue_t *q)

/**
 * @brief Frees all memory used by a queue
 * @param[in] q The queue to free
 */
void queue_free(queue_t *q) {
    /* How about freeing the list elements and the strings? */
    /* Free queue structure */
    if(q == NULL) return ;
    if(q->length == 0){
        free(q);
        return ;
    }
    list_ele_t *cur = q->head;
    while (cur) {
        list_ele_t *tmp = cur;
        cur = cur->next;
        free(tmp->value);
        free(tmp); 
    }
    free(q);
}

bool queue_insert_head(queue_t q, const* char *s)

/**
 * @brief Attempts to insert an element at head of a queue
 *
 * This function explicitly allocates space to create a copy of `s`.
 * The inserted element points to a copy of `s`, instead of `s` itself.
 *
 * @param[in] q The queue to insert into
 * @param[in] s String to be copied and inserted into the queue
 *
 * @return true if insertion was successful
 * @return false if q is NULL, or memory allocation failed
 */
bool queue_insert_head(queue_t *q, const char *s) {
    /* What should you do if the q is NULL? */
    if (q == NULL) return false;
        
    /* create new element */
    list_ele_t *newh = (list_ele_t *)malloc(sizeof(list_ele_t));
    if (newh == NULL) return false;

    /* Don't forget to allocate space for the string and copy it */
    newh->value = (char *)malloc(sizeof(char) * (strlen(s) + 1));
    /* if malloc failure then free newh */
    if (newh->value == NULL) {
        free(newh);
        return false;
    }
    strncpy(newh->value, s, strlen(s) + 1);
    newh->next = NULL;
    /* What if either call to malloc returns NULL? */

    /* if q is empty */
    if (q->length == 0) q->head = newh, q->tail = newh;
    else{
        newh->next = q->head;
        q->head = newh;
    }
    q->length++;
    return true;
}

bool queue_insert_tail(queue_t q, const* char *s)

/**
 * @brief Attempts to insert an element at tail of a queue
 *
 * This function explicitly allocates space to create a copy of `s`.
 * The inserted element points to a copy of `s`, instead of `s` itself.
 *
 * @param[in] q The queue to insert into
 * @param[in] s String to be copied and inserted into the queue
 *
 * @return true if insertion was successful
 * @return false if q is NULL, or memory allocation failed
 */
bool queue_insert_tail(queue_t *q, const char *s) {
    /* You need to write the complete code for this function */
    /* Remember: It should operate in O(1) time */
    if (q == NULL) return false;

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

    newh->value = (char *)malloc(sizeof(char) * (strlen(s) + 1));
        // if malloc failure then free newh
    if (newh->value == NULL) {
        free(newh);
        return false;
    }
    strncpy(newh->value, s, strlen(s) + 1);
    newh->next = NULL;

    /* if q is empty */
    if (q->length == 0) q->head = newh, q->tail = newh;
    else{
        q->tail->next = newh;
        q->tail = newh;
    }
    q->length++;
    return true;
}

bool queue_remove_head(queue_t q, char buf, size_t bufsize)

这里重点在于buf == NULL

/**
 * @brief Attempts to remove an element from head of a queue
 *
 * If removal succeeds, this function frees all memory used by the
 * removed list element and its string value before returning.
 *
 * If removal succeeds and `buf` is non-NULL, this function copies up to
 * `bufsize - 1` characters from the removed string into `buf`, and writes
 * a null terminator '\0' after the copied string.
 *
 * @param[in]  q       The queue to remove from
 * @param[out] buf     Output buffer to write a string value into
 * @param[in]  bufsize Size of the buffer `buf` points to
 *
 * @return true if removal succeeded
 * @return false if q is NULL or empty
 */
bool queue_remove_head(queue_t *q, char *buf, size_t bufsize) {
    /* You need to fix up this code. */
    if (q == NULL || q->length == 0 || buf == NULL) return false;

    list_ele_t *cur = q->head;
    q->head = cur->next;
    q->length--;
    /* copy bufsize - 1 char */ 
    strncpy(buf, cur->value, bufsize - 1);
    buf[bufsize - 1] = '\0';
    free(cur->value);
    free(cur);
    if (q->length == 0) q->tail = NULL;
    return true;
}

size_t queue_size(queue_t *q)

/**
 * @brief Returns the number of elements in a queue
 *
 * This function runs in O(1) time.
 *
 * @param[in] q The queue to examine
 *
 * @return the number of elements in the queue, or
 *         0 if q is NULL or empty
 */
size_t queue_size(queue_t *q) {
    /* You need to write the code for this function */
    /* Remember: It should operate in O(1) time */
    return q == NULL ? 0 : q->length;
}

void queue_reverse(queue_t *q)

头插法

/**
 * @brief Reverse the elements in a queue
 *
 * This function does not allocate or free any list elements, i.e. it does
 * not call malloc or free, including inside helper functions. Instead, it
 * rearranges the existing elements of the queue.
 *
 * @param[in] q The queue to reverse
 */
void queue_reverse(queue_t *q) {
    /* You need to write the code for this function */
    if (q == NULL || q->length == 0) return ;

    q->tail = q->head;
    list_ele_t *cur = q->head->next;
    q->head->next = NULL;

    while(cur){
        list_ele_t *tmp = cur->next;
        cur->next = q->head;
        q->head = cur;
        cur = tmp;
    }
}