CSAPP-lab0：C Programming Lab

队列的链表实现

用一个结构体来表示链表，定义如下：

typedef struct {
    /**
     * @brief Pointer to the first element in the queue, or NULL if the
     *        queue is empty.
     */
    list_ele_t *head;
    /*
     * TODO: You will need to add more fields to this structure
     *       to efficiently implement q_size and q_insert_tail
     */
    list_ele_t *tail;
    int size;
} queue_t;

/**
 * @brief Linked list element containing a string.
 *
 * You shouldn't change this struct.
 */
typedef struct list_ele {
    /**
     * @brief Pointer to a char array containing a string value.
     *
     * The memory for this string should be explicitly allocated and freed
     * whenever an element is inserted and removed from the queue.
     */
    char *value;

    /**
     * @brief Pointer to the next element in the linked list.
     */
    struct list_ele *next;
} list_ele_t;

• queue_t结构体中head、tail分别是指向list_ele_t类型的指针
• list_ele结构体中包含两个指针，分别指向char和list_ele类型
• 队列的数据结构如下所示：

实验要求

完成以下函数并通过评测系统：

/* Create empty queue. */
queue_t *queue_new(void);

/* Free ALL storage used by queue. */
void queue_free(queue_t *q);

/* Attempt to insert element at head of queue. */
bool queue_insert_head(queue_t *q, const char *s);

/* Attempt to insert element at tail of queue. */
bool queue_insert_tail(queue_t *q, const char *s);

/* Attempt to remove element from head of queue. */
bool queue_remove_head(queue_t *q, char *sp, size_t bufsize);

/* Return number of elements in queue. */
size_t queue_size(queue_t *q);

/* Reverse elements in queue */
void queue_reverse(queue_t *q);

queue_new

• 使用malloc在堆上给queue_t分配内存
• 将head和tail指针、size初始化

  /**
   * @brief Allocates a new queue
   * @return The new queue, or NULL if memory allocation failed
   */
  queue_t *queue_new(void) {
      // malloc:success return pointer to addr ; error return NULL
      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;
  }

queue_free

• 使用free函数释放内存，注意到q->head->value和q->head都应该被free，如果只free了q->head->value会报内存泄露

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

queue_insert_head

• 在头部插入节点
• 使用malloc为新节点和新节点中的字符串分配空间，注意sizeof(char) * (strlen(s) + 1)语句
• 除了给节点、节点内的字符串分配空间外，不可以分配别的空间

  /**
   * @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;
      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));
      newh->next = NULL;
      /* What if either call to malloc returns NULL? */
      if (newh->value == NULL) {
          free(newh); // this is important
          return false;
      }
  
      strcpy(newh->value, s);
      // insert
      if (q->head == NULL) // what if q->head ==NULL?
      {
          q->head = newh;
          q->tail = newh;
          q->size++;
      } else {
          newh->next = q->head;
          q->head = newh;
          q->size++;
      }
      return true;
  }

queue_remove_head

• 将队列头结点删去，同时要使用strncpy将节点中的字符串复制保存下来
• 注意strncpy的用法，可以参考c++reference，字符串末尾要手动加\0
• 要同时free节点和节点内指向char的指针

  /**
   * @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->size == 0 || buf == NULL)
          return false;
      strncpy(buf, q->head->value, bufsize - 1); // max bufsize-1 bytes copied
      buf[bufsize - 1] = '\0';
      list_ele_t *temp = q->head;
      if (q->size == 1) {
          q->size--;
          q->head = NULL;
          q->tail = NULL;
          if (temp->value != NULL)
              free(temp->value);
          free(temp);
      } else {
          q->size--;
          q->head = q->head->next;
          if (temp->value != NULL)
              free(temp->value);
          free(temp);
      }
      return true;
  }

queue_size

• 要注意到返回值是size_t类型，所以要进行一次强制类型转换

  /**
   * @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 */
      if (q != NULL)
          return (unsigned long)q->size;
      return (unsigned long)0;
  }

  queue_reverse

• 使用三个指针，pre指针和iter指针用来改变节点的指向，next指针一直往后移动且试探是否下一个节点为null
• 绿色为被改变的节点指针的指向
• 红色表示每次循环这三个指针都要往后指
• 最后，队列的首位指针要调换

/**
 * @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) {
    if (q == NULL || q->head == NULL) {
        return;
    }
    list_ele_t *iter = q->head;
    list_ele_t *next = q->head->next;
    list_ele_t *prev = NULL;
    while (next) {
        iter->next = prev;
        prev = iter;
        iter = next;
        next = next->next;
    }
    iter->next = prev;
    q->tail = q->head;
    q->head = iter;
}

测评

make clean

make format

./driver.py

结果

...(略)

+++ TESTING trace trace-15-perf:
./qtest -v 1 -f ./traces/trace-15-perf.cmd
# Test performance of insert_tail, size, and reverse
---     trace-15-perf   7/7
---     TOTAL           100/100