owned this note
owned this note
Published
Linked with GitHub
# 2018q3 Homework2 (lab0)
contributed by < [brad84622](https://github.com/brad84622/lab0-c) >
## 實驗目標為實作 queue
- first in, first out (FIFO)
- last in, first out (LIFO)
## 開發環境設定
- 設定好 GitHub 帳號同步, vim
- 安裝以下開發工具
``` $ sudo apt install build-essential git-core cppcheck clang-format ```
## 目標
- new
- insert head
- insert tail
- remove head
- reverse
- free
- size
## 結構
```graphviz
digraph {
node[shape=box]
tail [shape=plaintext,label=tail]
head [shape=plaintext,label=head]
{rank=same;a,b,c,NULL}
a->b
b->c
NULL[shape=plaintext]
c->NULL
head->a
tail->c
}
```
### insert head
```graphviz
digraph {
node[shape=box]
tail [shape=plaintext,label=tail]
head [shape=plaintext,label=head]
{rank=same;a,b,c,NULL,newh}
newh->a
a->b
b->c
NULL[shape=plaintext]
c->NULL
head->newh
tail->c
}
```
### insert tail
```graphviz
digraph {
node[shape=box]
tail [shape=plaintext,label=tail]
head [shape=plaintext,label=head]
{rank=same;a,b,c,NULL,newt}
a->b
b->c
c->newt
NULL[shape=plaintext]
newt->NULL
head->a
tail->newt
}
```
### remove head
```graphviz
digraph {
node[shape=box]
tail [shape=plaintext,label=tail]
head [shape=plaintext,label=head]
{rank=same;b,c,NULL}
b->c
NULL[shape=plaintext]
c->NULL
head->b
tail->c
}
```
### reverse
```graphviz
digraph {
node[shape=box]
tail [shape=plaintext,label=tail]
head [shape=plaintext,label=head]
{rank=same;a,b,c,NULL}
b->a
c->b
NULL[shape=plaintext]
a->NULL
head->c
tail->a
}
```
### 遭遇的錯誤
```
$ make test
scripts/driver.py
...
# Test of truncated strings
ERROR: Segmentation fault occurred. You dereferenced a NULL or invalid pointer
--- trace-06-string 0/7
...
--- TOTAL 93/100
```
- 觀察trace-06-string做了什麼?
```=
# Test of truncated strings
option fail 0
option malloc 0
new
ih aardvark_bear_dolphin_gerbil_jaguar 5
it meerkat_panda_squirrel_vulture_wolf 5
rh aardvark_bear_dolphin_gerbil_jaguar
reverse
rh meerkat_panda_squirrel_vulture_wolf
option length 30
rh meerkat_panda_squirrel_vulture
reverse
option length 28
rh aardvark_bear_dolphin_gerbil
option length 21
rh aardvark_bear_dolphin
reverse
option length 22
rh meerkat_panda_squirrel
option length 7
rh meerkat
reverse
option length 8
rh aardvark
option length 100
rh aardvark_bear_dolphin_gerbil_jaguar
reverse
rh meerkat_panda_squirrel_vulture_wolf
free
quit
```
- 照著執行發現最後一個reverse(27行)發生錯誤
回頭檢查reverse
```clike=
void q_reverse(queue_t *q) {
/* You need to write the code for this function */
if (q == NULL || q->size == 0) {
} else {
list_ele_t *prev, *cur, *nt;
prev = q->head;
cur = prev->next;
nt = cur->next;
prev->next = NULL;
cur->next = prev;
prev = cur;
cur = nt;
int i;
for (i = 0; i < (q->size) - 2; i++) {
nt = nt->next;
cur->next = prev;
prev = cur;
cur = nt;
}
q->tail = q->head;
q->head = prev;
}
}
```
- 發現自己預設考慮3個以上及q=NULL還有size=0的情況
忽略掉1&2個點的情況
- 修改成
```clike=
void q_reverse(queue_t *q) {
/* You need to write the code for this function */
if (q == NULL || q->size == 0||q->size==1) {
} else if(q->size==2) {
q->tail->next=q->head;
q->head->next=NULL;
q->head=q->tail;
q->tail=q->tail->next;
} else {
list_ele_t *prev, *cur, *nt;
prev = q->head;
cur = prev->next;
nt = cur->next;
prev->next = NULL;
cur->next = prev;
prev = cur;
cur = nt;
int i;
for (i = 0; i < (q->size) - 2; i++) {
nt = nt->next;
cur->next = prev;
prev = cur;
cur = nt;
}
q->tail = q->head;
q->head = prev;
}
}
```
## 結果
```
$ make test
gcc -O0 -g -Wall -Werror -c queue.c
gcc -O0 -g -Wall -Werror -o qtest qtest.c report.c console.c harness.c queue.o
scripts/driver.py
--- Trace Points
...
--- TOTAL 100/100
```