# 2019q1 Homework1 (lab0)
contributed by < `stanleyuan` >
## 目標
- 使用 linked list 來實作 queue 的 operation
- [F01: lab0](https://hackmd.io/s/BJA8EgFB4)
- [2019q1 Homework1 (作業區)](https://hackmd.io/s/SJ4kPZYS4)
## 環境
- OS
```shell
$ lsb_release -a
LSB Version: core-9.20170808ubuntu1-noarch:security-9.20170808ubuntu1-noarch
Distributor ID: Ubuntu
Description: Ubuntu 18.04.2 LTS
Release: 18.04
Codename: bionic
```
- Compiler
```shell
$ gcc -v
gcc version 8.3.0 (Ubuntu 8.3.0-6ubuntu1~18.04)
```
## coding style
作業說明有特別提到程式碼一致性的重要，要求使用 [clang format](https://clang.llvm.org/docs/ClangFormat.html) 來檢查程式法風格，老師有說一句話滿重要的「工程師是會溝通的」。最近也是滿有感的，常常是今天的我看不懂昨天的我的程式碼，明天的我可能也是看不懂今天的我的程式碼。推薦 [vim-autoformat](https://github.com/Chiel92/vim-autoformat) 可以一鍵使用系統中的 formatting program。另外還有 [syntastic](https://github.com/vim-syntastic/syntastic) 除了語法檢查之外，也可以使用系統中的 coding style program 來檢查 coding style。
## Programming Tasks
完成以下的 oprations:
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 (LIFO discipline).
q insert tail: Attempt to insert a new element at the tail of the queue (FIFO discipline).
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_insert_tail and q_size require that implementations operate in **time O(1)**.
## queue.h
- list_ele_t 為 linked list 的 node 的 struct
```cpp
/* Linked list element */
typedef struct ELE {
/* Pointer to array holding string. */
char *value;
struct ELE *next;
} list_ele_t;
```
- queue_t 為 queue 的 struct，有一個指向 list_ele_t type 的 pointer。
```cpp
/* Queue structure */
typedef struct {
/* Linked list of elements */
list_ele_t *head;
} queue_t;
```
## queue.c
- queue 所需實作的 operations
* q new
* q free
* q insert head
* q insert tail
* q remove head
* q size
# Implementation
## queue_t
由於題目要求 q_insert_tail and q_size 的 時間複雜度都是 O(1)，勢必在 queue_t 中要紀錄 tail node 的位置還有 queue 的大小。需要加上一個 tail 的 pointer 還有整數 size。
新 queue_t:
```cpp
/* Queue structure */
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
int size;
} queue_t;
```
## q_new()
舊 q_new:
```cpp
/*
Create empty queue.
Return NULL if could not allocate space.
*/
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
/* What if malloc returned NULL? */
q->head = NULL;
return q;
}
```
可以看到註解寫到要考慮如果 malloc return NULL，哪些情況下 malloc 會 return NULL呢？
```shell
$ man malloc
```
>RETURN VALUE
>The malloc() and calloc() functions return a pointer to the allocated memory, which is suitably aligned for any built-in type. **On error, these functions return NULL**. NULL may also be returned by a successful call to malloc() **with a size of zero**, or by a successful call to calloc() with nmemb or size equal to zero.
有錯誤或是 size 為零的時候便會回傳NULL，所以將程式修改為：
```cpp
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
/* What if malloc returned NULL? */
if (!q)
return q;
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
```
因為已經在 queue_t 裡加上 tail 和 size，也要記得初始化。
## q_insert_head
舊 q_insert_head:
```cpp
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
/* What should you do if the q is NULL? */
newh = malloc(sizeof(list_ele_t));
/* Don't forget to allocate space for the string and copy it */
/* What if either call to malloc returns NULL? */
newh->next = q->head;
q->head = newh;
return true;
}
```
在這裡有 3 種情況要考慮：
1. 如果 q 為 NULL
2. 如果 list_ele_t 的 malloc 回傳 NULL
3. 在 list_ele_t 中 value 所需的空間 malloc 如果回傳 NULL
會變成：
```cpp
bool q_insert_head(queue_t *q, char *s)
{
if (q) {
list_ele_t *newh;
char *news;
int s_len = strlen(s) + 1;
newh = malloc(sizeof(list_ele_t));
if (newh) {
news = malloc(s_len * sizeof(char));
if (news) {
// test later
memset(news, '\0', s_len);
strcpy(news, s);
newh->next = q->head;
newh->value = news;
if (!q->head)
q->tail = newh;
q->head = newh;
q->size += 1;
return true;
}
free(newh);
}
}
return false;
}
```
q->size 要記得加 1
## q_remove_head
舊 q_remove_head:
```cpp
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
/* You need to fix up this code. */
q->head = q->head->next;
return true;
}
```
要判斷有沒有 q, q->head, sp
```cpp
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (q && q->head) {
list_ele_t *tmp = q->head;
memset(sp, '\0', bufsize);
if (sp)
strncpy(sp, tmp->value, bufsize - 1);
q->head = q->head->next;
free(tmp->value);
free(tmp);
q->size -= 1;
return true;
}
return false;
}
```
但一直出錯，後來才發現忘記了q->tail，如果是移除掉最後一個 node 的話：
```cpp
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (q && q->head) {
list_ele_t *tmp = q->head;
memset(sp, '\0', bufsize);
if (sp)
strncpy(sp, tmp->value, bufsize - 1);
q->head = q->head->next;
if (!q->head) /* new codes */
q->tail = q->head; /* new codes */
free(tmp->value);
free(tmp);
q->size -= 1;
return true;
}
return false;
}
```
要記得 free 該 node 的 value 還有 node，q->size 要減一。
## q_size
舊的 q_size
```cpp
int q_size(queue_t *q)
{
/* You need to write the code for this function */
/* Remember: It should operate in O(1) time */
return 0;
}
```
因為在初始化、新增、刪除都有對 q-?size 做紀錄，如果 q 存在的話，只需回傳 q->size:
```cpp
int q_size(queue_t *q)
{
/* You need to write the code for this function */
/* Remember: It should operate in O(1) time */
if (q)
return q->size;
return 0;
}
```
## q_insert_tail
舊的 q_insert_tail:
```cpp
bool q_insert_tail(queue_t *q, char *s)
{
/* You need to write the complete code for this function */
/* Remember: It should operate in O(1) time */
return false;
}
```
這邊要注意的是要求 O(1)，所以要從 q->tail 下手
```cpp
bool q_insert_tail(queue_t *q, char *s)
{
/* You need to write the complete code for this function */
/* Remember: It should operate in O(1) time */
if (q) {
list_ele_t *tmp = malloc(sizeof(list_ele_t));
char *news;
int s_len = strlen(s) + 1;
if (tmp) {
news = malloc(s_len * sizeof(char));
if (news) {
memset(news, '\0', s_len);
strcpy(news, s);
tmp->value = news;
tmp->next = NULL;
q->size += 1;
if (!q->tail)
q->head = tmp;
q->tail->next = tmp;
q->tail = tmp;
return true;
}
free(tmp);
}
}
return false;
}
```
test 過了，但發現我在處理 q->tail 的時候好像怪怪的，如果一開始沒有 nodes，q->tail 就會等於 NULL，那 ```q->tail->next = tmp``` 會指到哪裡？
但 test 過了（？
最後我改成：
```cpp
bool q_insert_tail(queue_t *q, char *s)
{
/* You need to write the complete code for this function */
/* Remember: It should operate in O(1) time */
if (q) {
list_ele_t *tmp = malloc(sizeof(list_ele_t));
char *news;
int s_len = strlen(s) + 1;
if (tmp) {
news = malloc(s_len * sizeof(char));
if (news) {
memset(news, '\0', s_len);
strcpy(news, s);
tmp->value = news;
tmp->next = NULL;
q->size += 1;
if (!q->tail) {
q->head = tmp;
q->tail = tmp;
} else {
q->tail->next = tmp;
q->tail = tmp;
}
return true;
}
free(tmp);
}
}
return false;
}
```
才有正確的檢查兩種 cases，測試也過了。
## q_free
利用 counter 先紀錄 head node，將 head 往前後再把 counter 所指到的 node free 掉。
```cpp
void q_free(queue_t *q)
{
/* How about freeing the list elements and the strings? */
/* Free queue structure */
if (q) {
if (q->head) {
while (q->head) {
list_ele_t *counter = q->head;
q->head = q->head->next;
free(counter->value);
free(counter);
}
}
free(q);
}
return;
}
```
## q_reverse
這個比較複雜，要將所有 node 的 next pointer 轉向，例如：
```graphviz
digraph revert {
//graph [ranksep=4];
labelloc = "b";
graph [splines=ortho];
/* nodes */
node [shape=record, label=""];
q [label="<f0> head | <f1> size | <f2> tail" xlabel="q"]
node [shape=plaintext]
node1 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> <TR>
<TD PORT="f1">value</TD>
<TD PORT="f2">next</TD>
</TR> </TABLE>>
xlabel="node1"];
node2 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> <TR>
<TD PORT="f1">value</TD>
<TD PORT="f2">next</TD>
</TR> </TABLE>>
xlabel="node2"];
node3 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> <TR>
<TD PORT="f1">value</TD>
<TD PORT="f2">next</TD>
</TR> </TABLE>>
xlabel="node3"];
node4 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> <TR>
<TD PORT="f1">value</TD>
<TD PORT="f2">next</TD>
</TR> </TABLE>>
xlabel="node4"];
node [shape=plaintext, label=""]
NULL [label="NULL"]
subgraph cluster_node {
style=invis;
{rank=same node1 node2 node3 node4};
q:f0 -> node1;
q:f2 -> node4;
edge [headport=w]
node1:f2 -> node2;
node2:f2 -> node3;
node3:f2 -> node4;
edge [headport=n]
node4:f2 -> NULL;
}
}
```
會變成：
```graphviz
digraph revert {
//graph [ranksep=4];
labelloc = "b";
graph [splines=ortho];
/* nodes */
node [shape=record, label=""];
q [label="<f0> head | <f1> size | <f2> tail" xlabel="q"]
node [shape=plaintext]
node1 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> <TR>
<TD PORT="f1">value</TD>
<TD PORT="f2">next</TD>
</TR> </TABLE>>
xlabel="node1"];
node2 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> <TR>
<TD PORT="f1">value</TD>
<TD PORT="f2">next</TD>
</TR> </TABLE>>
xlabel="node2"];
node3 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> <TR>
<TD PORT="f1">value</TD>
<TD PORT="f2">next</TD>
</TR> </TABLE>>
xlabel="node3"];
node4 [label=<
<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> <TR>
<TD PORT="f1">value</TD>
<TD PORT="f2">next</TD>
</TR> </TABLE>>
xlabel="node4"];
node [shape=plaintext, label=""]
NULL [label="NULL"]
subgraph cluster_node1 {
style=invis;
{rank=same node1 node2 node3 node4};
q:f0 -> node4;
q:f2 -> node1;
edge [headport=w]
node4:f2 -> node3;
node3:f2 -> node2;
node2:f2 -> node1;
edge [headport=n]
node1:f2 -> NULL;
}
}
```
想法是要用兩個 pointer 來紀錄連續兩個 node 並且變更指標所指向的 node:
```cpp
void q_reverse(queue_t *q)
{
/* You need to write the code for this function */
if (q && q->head && q->head->next) {
list_ele_t *left, *right;
right = q->head->next;
left = q->head;
q->tail = q->head;
q->tail->next = NULL;
while (right) {
q->head = right;
right = q->head->next;
q->head->next = left;
left = q->head;
}
}
}
```
###### tags: `knowThyself` `linux` `c` `linkList` `w1`
Sign in with Wallet
Connect another wallet