2018q3 Homework2 (lab0)

contributed by < brad84622 >

實驗目標為實作 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

結構

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

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

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

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

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























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個點的情況
  • 修改成





























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
Select a repo