Try   HackMD

2020q3 Homework1 (quiz1)

contributed by <hsiehong>

tags: 進階電腦系統理論與實作

作業說明


add_entry

AA1 : assert(new_node);

AA2 : *indirect = new_node;

void add_entry(node_t **head, int new_value) { node_t **indirect = head; node_t *new_node = malloc(sizeof(node_t)); new_node->value = new_value; new_node->next = NULL; assert(new_node);//AA1 while (*indirect) indirect = &(*indirect)->next; *indirect = new_node;//AA2 }
  • line 5-7 : 新增一 node






newNode



newNode

new_node



NULL
NULL



newNode->NULL





  • line 9 : assert(new_node)C Library中,此 macro 會比較參數與0。相同的話錯誤訊息會被寫入 standard error device 且會呼叫abort
    目的是確保 new_node 能分配到空間
  • line 12 : line 10 和 line 11,*indirect 會從 head 走訪 linked list 的所有節點,在迴圈結束時會停在最後一個節點,此時會將新的節點 new_node assign 給*indirect,即插入串列尾。






link



it
indirect



N
null



it->N





A

A



B

B



A->B





C

C



B->C





C->N





nn

new_node









link2



it2
indirect



NN

new_node



it2->NN





A

A



B

B



A->B





C

C



B->C





C->NN





Null
NULL



NN->Null






swap_pair

BB1 : node = &(*node)->next->next

BB2 : *node = (*node)->next

node_t *swap_pair(node_t *head) { for (node_t **node = &head; *node && (*node)->next; node = &(*node)->next->next/*BB1*/) { node_t *tmp = *node; *node = (*node)->next;//BB2; tmp->next = (*node)->next; (*node)->next = tmp; } return head; }
  • 將 linked list 中的node兩兩一組,並做交換
  • line 3 : 走訪 linked list,且一次走訪兩個 node,此處是使用pointer to pointer,所以每次要跳兩個 node。
  • 一開始沒注意到 -> 優先權大於 &,參考運算子優先順序
  • line 4-7 : 交換兩個 node 的指向

dereference 與 reference 概念不清楚, pointer to pointer 概念混亂, 還需要去多找一些資料閱讀







swapGraph



head
head



A

A



head->A





B

B



A->B





C

C



B->C





D

D



C->D





E

E



D->E





Null
NULL



E->Null





N
N



N->A





N->B











struct



head
head



B2

B



head->B2





A2

A



C2

C



A2->C2





B2->A2





D2

D



C2->D2





E2

E



D2->E2





Null2
NULL



E2->Null2





N2
node



N2->C2











swapGraph



head
head



B

B



head->B





A

A



C

C



A->C





B->A





D

D



C->D





E

E



D->E





Null
NULL



E->Null





N
node



N->E






reverse

CCC : head->next = cursor; cursor = head

node_t *reverse(node_t *head) { node_t *cursor = NULL; while (head) { node_t *next = head->next; head->next = cursor; //CCC cursor = head; //CCC head = next; } return cursor; }
  • 將整個 linked list 反轉,並回傳反轉後的 head
  • cursor 在每一個 iteration 中,初始都會在原 linked list 中 head 的前一個 node ,next 則永遠是 head 的下一項,並且將 head->next 指向 cursor (反轉的動作),再將 cursor 指向 head

待補

  • Graphviz 圖表優化,表達的不夠好,也畫的好醜
  • pointer to pointer 的相關應用