该文章是我在别处写的小随笔，现在转过来
实验下载地址
15-213/14-513/15-513: Intro to Computer Systems, Spring 2022
大致要求
1.Linux命令行基础
2.C语言基础
3.数据结构基础（链表基本操作）
4.基本英语阅读能力
大致操作
下载.tar 文件，解压后对着README操作即可；
简单来说，允许直接修改的文件只有 queue.h和queue.c，打代码的时候打开这两个就够了，其他的鼓励查看学习；
按照要求修改后，保存；
在linux终端输入命令进行测试打分。
自动打分具体操作
（在所在路径下操作）
（1）make format：直接make可能会返回一个跟clang-format有关的报错
（2）make：编译文件并产生自动测试文件
（3）make test：测试正确性
这里的报错方式是valgrind，可以连带着大致学习一下
代码和大致思路
用中文写注释会报错（QAQ）
1.queue.h中两个结构体
/************** Data structure declarations ****************/
/**
* @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;
/**
* @brief Queue structure representing a list of elements
*/
typedef struct {
/**
* @brief Pointer to the first element in the queue, or NULL if the
* queue is empty.
*/
size_t size;
list_ele_t *tail;
list_ele_t *head;
/*
* TODO: You will need to add more fields to this structure
* to efficiently implement q_size and q_insert_tail
*/
} queue_t;
这里可以看到cmu给的注释还是比较详细的
2.queue.c中的几个函数
创建新queue：
/**
* @brief Allocates a new queue
* @return The new queue, or NULL if memory allocation failed
*/
queue_t *queue_new(void) {
queue_t *q = malloc(sizeof(queue_t));
if (q != NULL)
/* What if malloc returned NULL? */
{
q->head = NULL;
q->tail = NULL;
q->size = 0;
}
return q;
}
3.Free queue的函数
/**
* @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? */
if (q != NULL) {
while (q->head != NULL) {
/*Free all the space*/
// for (size_t i = 0; i < q->size; i++) {
/*I think they're the same.*/
list_ele_t *temp;
temp = q->head;
q->head = temp->next;
free(temp->value);
/*Array in structs are not freed with structs being freed.*/
free(temp);
}
/* Free queue structure */
free(q);
}
}
4.两个insert函数：
拿到文件时已有的代码后面有注释：already there
/**
* @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) {
list_ele_t *newh; // already there.
if (!q)
return false;
/* What should you do if the q is NULL? */
newh = (list_ele_t *)malloc(sizeof(list_ele_t)); // alreadythere
if (!newh)
return false;
char *stemp;
/* Don't forget to allocate space for the string and copy it */
if (s) {
stemp = (char *)malloc((strlen(s) + 1) * sizeof(char));
if (!stemp) {
free(newh);
return false;
}
strcpy(stemp, s);
} else
stemp = NULL;
/* What if either call to malloc returns NULL? */
newh->value = stemp;
newh->next = q->head; // already there.
q->head = newh; // already there.
if (q->tail == NULL) //(q->size == 0) // means q->size==0
q->tail = q->head;
q->size++;
return true; // already there.
}
/**
* @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) {
if (!q)
return false;
list_ele_t *newh;
newh = (list_ele_t *)malloc(sizeof(list_ele_t));
if (!newh) {
return false;
}
char *newc;
if (s) {
newc = (char *)malloc(sizeof(char) * (strlen(s) + 1));
if (!newc) {
free(newh);
return false;
}
strcpy(newc, s);
} else
newc = NULL;
newh->value = newc;
newh->next = NULL;
q->tail->next = newh;
q->tail = newh;
if (q->size == 0) {
q->head = q->tail;
}
q->size++;
return true;
/* You need to write the complete code for this function */
/* Remember: It should operate in O(1) time */
// return false;//already there.
}
5.Remove函数
/**
* @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)
return false;
if (q->size == 0) // which means q->size==0
return false;
list_ele_t *newqt;
newqt = q->head;
q->head = newqt->next;
q->size--;
if (q->size == 0) {
q->tail = NULL;
// q->head = NULL;
}
if (buf) {
// buf = newqt->value;
// if (strlen(newqt->value) > bufsize - 1) {
// buf[bufsize - 1] = '\0';
// newqt->value = &buf[bufsize];
// // free(newqt->value);
// }
/*ERROR: AddressSanitizer: attempting free on
address which was not malloc()-ed*/
strncpy(buf, newqt->value, bufsize - 1);
buf[bufsize - 1] = '\0'; ///
}
//if (newqt->value)
free(newqt->value);
free(newqt);
return true;
}
6.Return Size函数
/**
* @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)
return 0;
return q->size;
}
7.Reverse函数
（不让用allocate和free）
/**
* @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) {
list_ele_t *s;
list_ele_t *temp;
if (!q || q->size == 0 || q->size == 1)
return;
s = q->head;
temp = s->next;
while (temp) {
s->next = temp->next;
temp->next = q->head;
q->head = temp;
temp = s->next;
}
q->tail = s;
/* You need to write the code for this function */
}
Auto Grade分数
user@user-virtual-machine:~/桌面/CSAPP/Lab/Lab0 CProgramming Lab/cprogramminglab-handout$ make test
chmod +x driver.py
./driver.py
--- Trace Points
+++ TESTING trace trace-01-ops:
./qtest -v 1 -f ./traces/trace-01-ops.cmd
# Test of insert_head and remove_head
--- trace-01-ops 6/6
+++ TESTING trace trace-02-ops:
./qtest -v 1 -f ./traces/trace-02-ops.cmd
# Test of insert_head, insert_tail, and remove_head
--- trace-02-ops 6/6
+++ TESTING trace trace-03-ops:
./qtest -v 1 -f ./traces/trace-03-ops.cmd
# Test of insert_head, insert_tail, reverse, and remove_head
--- trace-03-ops 6/6
+++ TESTING trace trace-04-ops:
./qtest -v 1 -f ./traces/trace-04-ops.cmd
# Test of insert_head, insert_tail, and size
--- trace-04-ops 6/6
+++ TESTING trace trace-05-ops:
./qtest -v 1 -f ./traces/trace-05-ops.cmd
# Test of insert_head, insert_tail, remove_head reverse, and size
--- trace-05-ops 6/6
+++ TESTING trace trace-06-string:
./qtest -v 1 -f ./traces/trace-06-string.cmd
# Test of truncated strings
--- trace-06-string 7/7
+++ TESTING trace trace-07-robust:
./qtest -v 1 -f ./traces/trace-07-robust.cmd
# Test operations on NULL queue
--- trace-07-robust 7/7
+++ TESTING trace trace-08-robust:
./qtest -v 1 -f ./traces/trace-08-robust.cmd
# Test operations on empty queue
--- trace-08-robust 7/7
+++ TESTING trace trace-09-robust:
./qtest -v 1 -f ./traces/trace-09-robust.cmd
# Test remove_head with NULL argument
--- trace-09-robust 7/7
+++ TESTING trace trace-10-malloc:
./qtest -v 1 -f ./traces/trace-10-malloc.cmd
# Test of malloc failure on new
--- trace-10-malloc 7/7
+++ TESTING trace trace-11-malloc:
./qtest -v 1 -f ./traces/trace-11-malloc.cmd
# Test of malloc failure on insert_head
--- trace-11-malloc 7/7
+++ TESTING trace trace-12-malloc:
./qtest -v 1 -f ./traces/trace-12-malloc.cmd
# Test of malloc failure on insert_tail
--- trace-12-malloc 7/7
+++ TESTING trace trace-13-perf:
./qtest -v 1 -f ./traces/trace-13-perf.cmd
# Test performance of insert_tail
--- trace-13-perf 7/7
+++ TESTING trace trace-14-perf:
./qtest -v 1 -f ./traces/trace-14-perf.cmd
# Test performance of size
--- trace-14-perf 7/7
+++ 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
满分
标签：head,return,trace,Programming,CSAPP,Lab,queue,NULL,size From： https://www.cnblogs.com/isayiaaa/p/18337668