2020q3 Week1

課堂問答簡記

ccs100203

Q: 將 add_entry 裡的 new_node 插在 head 的前面要怎麼改?
如果傳進來的是前面 node 的 next 的 reference，那直接 dereference 後接上去就可以了
e.g. add_entry(&(head->next), 109);









void add_entry(node_t **head, int new_value)
{
    node_t *new_node = malloc(sizeof(node_t));
    assert(new_node);
    new_node->value = new_value;
    new_node->next = *head;
    *head = new_node;
}

但如果不是的話，e.g. node_t *head2 = head->next; add_entry(&head2, 109);，就變成用下面的方法，加一個 node 在後面，然後把資料移過去
















void add_entry(node_t **head, int new_value)
{
    node_t *new_node = malloc(sizeof(node_t));
    assert(new_node);
    if(*head){
        new_node->value = (*head)->value;
        new_node->next = (*head)->next;
        (*head)->value = new_value;
        (*head)->next = new_node;
    }else{
        new_node->value = new_value;
        new_node->next = NULL;
        *head = new_node;
    }
}

ZhuMon

Q 如何改 reverse 為 pointer to pointer

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

tigger12613

Q 將 add_entry 裡的 new_node 插在 list 的最前面要怎麼改? (head前面可能還有node，請在確保整體linked list依舊正常的情況下在head前面插入new_node ．另外，不可新增傳入的參數)
我贊同 ccs100203 的方法，以下內容皆參考 ccs100203 的答案
head'是參數的(*head)

digraph structs {
        rankdir=LR;
        node[shape=box];
        struct0 [label= "real head",color=purple];
        struct5 [label= "head'"];
        struct1 [label= "last"];
        struct2 [label= "node1\n value of node1",color=purple];
        struct3 [label= "node2\n value of node2"];   
        struct4 [label= "node3\n value of node3"];
        
        {
            rank="same";
            struct0 -> struct2[color=purple]     
        }
        {
            rank="same";
            struct1 -> struct4        
        }
        {
            rank="same";
            struct5 -> struct3        
        }
        struct2 -> struct3[arrowhead=vee, tailclip=true, arrowsize=1,color=purple];
        struct3 -> struct4[arrowhead=vee, tailclip=true, arrowsize=1];
}

我們並不知道紫色的那些東西存不存在，所以新增一個 node ，把 node2 的 value 丟給 new node

digraph structs {
        rankdir=LR;
        node[shape=box];
        struct0 [label= "real head",color=purple];
        struct5 [label= "head'"];
        struct1 [label= "last"];
        struct2 [label= "node1\n value of node1",color=purple];
        struct3 [label= "node2\n value of node2"];   
        struct4 [label= "node3\n value of node3"];
        struct6 [label= "new node\nno value"];
        {
            rank="same";
            struct0 -> struct2[color=purple]     
        }
        {
            rank="same";
            struct1 -> struct4        
        }
        {
            rank="same";
            struct5 -> struct3        
        }
        struct2 -> struct3[arrowhead=vee, tailclip=true, arrowsize=1,color=purple];
        struct6 -> struct4[arrowhead=vee, tailclip=true, arrowsize=1];
        struct3 -> struct6[arrowhead=vee, tailclip=true, arrowsize=1];
}

copy value of node2 to new node

digraph structs {
        rankdir=LR;
        node[shape=box];
        struct0 [label= "real head",color=purple];
        struct5 [label= "head'"];
        struct1 [label= "last"];
        struct2 [label= "node1\n value of node1",color=purple];
        struct3 [label= "node2\n value of node2"];   
        struct4 [label= "node3\n value of node3"];
        struct6 [label= "new node\nvalue of node2"];
        {
            rank="same";
            struct0 -> struct2[color=purple]     
        }
        {
            rank="same";
            struct1 -> struct4        
        }
        {
            rank="same";
            struct5 -> struct3        
        }
        struct2 -> struct3[arrowhead=vee, tailclip=true, arrowsize=1,color=purple];
        struct6 -> struct4[arrowhead=vee, tailclip=true, arrowsize=1];
        struct3 -> struct6[arrowhead=vee, tailclip=true, arrowsize=1];
}

copy the new value to node2

digraph structs {
        rankdir=LR;
        node[shape=box];
        struct0 [label= "real head",color=purple];
        struct5 [label= "head'"];
        struct1 [label= "last"];
        struct2 [label= "node1",color=purple];
        struct3 [label= "node2\n new value"];   
        struct4 [label= "node3"];
        struct6 [label= "new node\nvalue of node2"];
        {
            rank="same";
            struct0 -> struct2[color=purple]     
        }
        {
            rank="same";
            struct1 -> struct4        
        }
        {
            rank="same";
            struct5 -> struct3        
        }
        struct2 -> struct3[arrowhead=vee, tailclip=true, arrowsize=1,color=purple];
        struct6 -> struct4[arrowhead=vee, tailclip=true, arrowsize=1];
        struct3 -> struct6[arrowhead=vee, tailclip=true, arrowsize=1];
}

這樣就可以在維持 link list 的正確性的情況下，插入一個node

Select a repo