2020q3 Homework1 (quiz1)

contributed by < Rsysz >

tags: sysprog

Outline

• 2020q3 Homework1 (quiz1)
  • Outline
  • 1. 解釋程式運作原理
  • 2. 修改函式 swap_pair 和 reverse，以pointer to pointer避免回傳
  • 3. 改寫 reverse，新增rev_recursive遞迴反轉Link list
  • 4. 實作 Fisher–Yates shuffle，使用swap減少記憶體使用量

1. 解釋程式運作原理

由add_entry, find_entry, remove_entry, swap_pair, reverse, print_list構成

• add_entry

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);
    while (*indirect)
        indirect = &(*indirect)->next;

    *indirect = new_node;
}

透過node_t **indirect存取head內保存的記憶體位址，接著建立新節點new_node分配記憶體空間與賦值，另外由此可知node_t **head是多餘的，程式碼可修改為void add_entry(node_t **indirect, int new_value)

利用assert(new_node)確保正確分配記憶體，透過*indirect遍歷Link list找到末端節點
並接上新節點

• find_entry

node_t *find_entry(node_t *head, int value)
{
    node_t *current = head;
    for (; current && current->value != value; current = current->next);
        /* interate */
    return current;
}

透過head遍歷Link list尋找value對應的節點

• remove_entry

void remove_entry(node_t **head, node_t *entry)
{
    node_t **indirect = head;

    while ((*indirect) != entry)
        indirect = &(*indirect)->next;

    *indirect = entry->next;
    free(entry);
}

透過find_entry找到對應的節點後將其放入entry，再使用remove_entry刪除指定的節點

而remove_entry使用*indrect遍歷Link list找尋指定的節點並予以刪除

• swap_pair

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;
}

透過*node遍歷Link list 每兩個節點交換一次

• reverse

node_t *reverse(node_t *head)
{
    node_t *cursor = NULL;
    while (head) {
        node_t *next = head->next;
        head->next = cursor; //CCC
        cursor = head;
        head = next;
    }
    return cursor;
}

透過next保留後續Link list

透過cursor反轉Link list

• print_list

void print_list(node_t *head)
{
    for (node_t *current = head; current; current = current->next)
        printf("%d ", current->value);
    printf("\n");
}

透過head遍歷Link list印出所有value

2. 修改函式 swap_pair 和 reverse，以pointer to pointer避免回傳

 void swap_pair(node_t **head)
 {
     for (node_t **node = head; *node && (*node)->next; node = &(*node)->next->next) {
         node_t *tmp = *node;
         *node = (*node)->next;
         tmp->next = (*node)->next;
         (*node)->next = tmp;
     }
 }
 void reverse(node_t **head)
 {
     node_t *cursor = NULL;
     while (*head) {
         node_t *next = (*head)->next;
         (*head)->next = cursor;
         cursor = *head;
         *head = next;
     }
     *head = cursor;
 }

3. 改寫 reverse，新增rev_recursive遞迴反轉Link list

 node_t *rev_recursive(node_t *cursor, node_t *head)
 {
     if(!head)
         return cursor;
     node_t *next = head->next;
     head->next = cursor;
     return rev_recursive(head, next);
 }
 void reverse(node_t **head)
 {
     if(!(*head))
         return;
     *head = rev_recursive(NULL, *head);
 }

4. 實作 Fisher–Yates shuffle，使用swap減少記憶體使用量

 void shuffle(node_t **head)
 {
     srand(time(NULL));
     int size = 0;
     node_t *tmp = *head;
     while(tmp){
         size++;
         tmp = tmp->next;
     }
     while(size != 0)
     {
         node_t *tail, *prev_tmp = NULL, *prev_tail = NULL;
         int rad = rand() % size;
         tmp = tail = *head;
         for(int i = 0; i < rad; i++){
             prev_tmp = tmp;
             tmp = tmp->next;
         }
         for(int j = 0; j < size - 1; j++){
             prev_tail = tail;
             tail = tail->next;
         }
         /*prev_swap & head*/
         if(prev_tmp != NULL)
             prev_tmp->next = tail;
         else
             *head = tail;
         if(prev_tail != NULL)
             prev_tail->next = tmp;
         else
             *head = tmp;
         /*swap*/
         node_t *next = tmp->next;
         tmp->next = tail->next;
         tail->next = next;
         size--;
     }
 }