[0]zero-index clytie0x/zero-index

14.2 แทรก ลบ และกลับลำดับ

หน้าที่แล้วสร้างขบวนรถไฟได้ เพิ่มตู้ได้ทั้งหัวและท้าย หน้านี้ทำงานของลานสับเปลี่ยนตู้ คือพ่วงตู้ใหม่ไว้หลังตู้ที่กำหนด ปลดตู้ออกจากกลางขบวน และกลับหัวขบวน ทั้งสามงานใช้หลักเดียวกัน คือเปลี่ยนแค่ next ไม่กี่ตัว ไม่ย้ายข้อมูล ส่วนที่ยากคือลำดับการเปลี่ยน เปลี่ยนผิดลำดับนิดเดียว ตู้ครึ่งขบวนหายได้

ทุกโปรแกรมในหน้านี้ใช้ฟังก์ชันช่วยสามตัวเหมือนกัน read_list อ่าน N ตัวแล้วสร้างลิสต์ตามลำดับด้วยวิธีเพิ่มท้ายจากหน้า 14.1 print_list พิมพ์ทั้งลิสต์โดยไม่มีช่องว่างเกินท้ายบรรทัด และ free_list ตัวเดิม เวลาอ่านให้ข้ามสามตัวนี้ไปดูฟังก์ชันใหม่ของแต่ละหัวข้อได้เลย

แทรกหลังตู้ที่กำหนด

มีตู้ที่ p ชี้อยู่ จะพ่วงตู้ใหม่ไว้ข้างหลังมัน ต้องเปลี่ยนสองเส้น และลำดับสำคัญ

  1. ให้ตู้ใหม่เกี่ยวตู้ที่อยู่หลัง p ตอนนี้ คือ node->next = p->next;
  2. ให้ p เกี่ยวตู้ใหม่ คือ p->next = node;
p 3 9 2 NULL 5 node 1 2

เส้นประคือเส้นเดิมที่ถูกแทนที่ ถ้าทำเส้นที่ 2 ก่อน p->next จะเป็นตู้ใหม่ไปแล้ว และไม่มีใครจำที่อยู่ของตู้ 2 อีก ดูผลได้ในส่วนลองทำให้พัง

โปรแกรมนี้รับขบวน แล้วรับคู่ x y แปลว่าพ่วงตู้หมายเลข y ไว้หลังตู้หมายเลข x ใช้ find จากหน้า 14.1 หาตู้ x ก่อน

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int value;
    struct Node *next;
} Node;

Node *read_list(int n)
{
    Node *head = NULL;
    Node *tail = NULL;
    for (int i = 0; i < n; i++) {
        Node *node = malloc(sizeof(Node));
        scanf("%d", &node->value);
        node->next = NULL;
        if (head == NULL) {
            head = node;
        } else {
            tail->next = node;
        }
        tail = node;
    }
    return head;
}

void print_list(Node *head)
{
    for (Node *p = head; p != NULL; p = p->next) {
        printf("%d", p->value);
        if (p->next != NULL) { // (1)!
            printf(" ");
        }
    }
    printf("\n");
}

void free_list(Node *head)
{
    while (head != NULL) {
        Node *next = head->next;
        free(head);
        head = next;
    }
}

Node *find(Node *head, int value)
{
    for (Node *p = head; p != NULL; p = p->next) {
        if (p->value == value) {
            return p;
        }
    }
    return NULL;
}

void insert_after(Node *p, int value) // (2)!
{
    Node *node = malloc(sizeof(Node));
    node->value = value;
    node->next = p->next;
    p->next = node;
}

int main()
{
    int n, q;
    scanf("%d %d", &n, &q);
    Node *head = read_list(n);
    for (int i = 0; i < q; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        Node *p = find(head, x);
        if (p != NULL) {
            insert_after(p, y);
        }
        print_list(head);
    }
    free_list(head);
    return 0;
}
  1. เว้นวรรคเฉพาะเมื่อยังมีตู้ต่อ บรรทัดจึงไม่มีช่องว่างเกินท้าย grader บางระบบเทียบทุกตัวอักษร ช่องว่างเกินตัวเดียวก็ผิดได้
  2. ฟังก์ชันนี้ไม่ต้องคืนหัวใหม่ เพราะแทรกหลัง p ไม่มีทางเปลี่ยนตู้หัว ถ้าอยากแทรกเป็นตู้แรกให้ใช้ push_front
4 3
3 9 2 7
9 5
7 8
4 1

3 9 5 2 7
3 9 5 2 7 8
3 9 5 2 7 8

บรรทัดที่สองแทรกหลังตู้สุดท้าย p->next เป็น NULL ตู้ใหม่จึงได้ NULL ไปเป็นตู้สุดท้ายเองโดยไม่ต้องเขียนกรณีพิเศษ บรรทัดที่สามหาตู้ 4 ไม่เจอ จึงไม่ทำอะไร

การแทรกครั้งหนึ่งเปลี่ยนแค่สองเส้น ไม่ว่าขบวนยาวเท่าไร แต่โปรแกรมนี้ยังต้องเดินหาตู้ x ก่อนทุกครั้ง ซึ่งช้าพอๆ กับเลื่อนอาเรย์ linked list จึงเร็วจริงเมื่อเรามี pointer ของตำแหน่งที่จะแทรกอยู่ในมือแล้ว เช่น เคอร์เซอร์ของโปรแกรมพิมพ์ข้อความ หน้า 14.3 มีวิธีหาตู้ x ได้ทันทีโดยไม่ต้องเดิน

ปลดตู้ออก

จะปลดตู้ที่มีหมายเลข x ออก ต้องให้ตู้ก่อนหน้ามันเกี่ยวข้ามไปหาตู้ที่อยู่หลังมันแทน ปัญหาคือ next ชี้ไปข้างหน้าทางเดียว ยืนอยู่ที่ตู้ x แล้วย้อนกลับไปหาตู้ก่อนหน้าไม่ได้ จึงต้องเดินด้วย prev ที่หยุดก่อนถึงตู้ x หนึ่งตู้ แล้วดู prev->next แทน

3 9 2 7 prev target prev->next = target->next

ตู้แรกเป็นกรณีพิเศษ เพราะไม่มีตู้ก่อนหน้า ถ้าตู้ที่จะปลดคือหัว ต้องย้าย head ไปตู้ที่สองแทน ฟังก์ชันจึงต้องคืนหัวใหม่แบบ push_front

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int value;
    struct Node *next;
} Node;

Node *read_list(int n)
{
    Node *head = NULL;
    Node *tail = NULL;
    for (int i = 0; i < n; i++) {
        Node *node = malloc(sizeof(Node));
        scanf("%d", &node->value);
        node->next = NULL;
        if (head == NULL) {
            head = node;
        } else {
            tail->next = node;
        }
        tail = node;
    }
    return head;
}

void print_list(Node *head)
{
    if (head == NULL) {
        printf("empty\n");
        return;
    }
    for (Node *p = head; p != NULL; p = p->next) {
        printf("%d", p->value);
        if (p->next != NULL) {
            printf(" ");
        }
    }
    printf("\n");
}

void free_list(Node *head)
{
    while (head != NULL) {
        Node *next = head->next;
        free(head);
        head = next;
    }
}

Node *delete_value(Node *head, int value)
{
    if (head == NULL) { // (1)!
        return NULL;
    }
    if (head->value == value) { // (2)!
        Node *rest = head->next;
        free(head);
        return rest;
    }
    Node *prev = head;
    while (prev->next != NULL && prev->next->value != value) { // (3)!
        prev = prev->next;
    }
    if (prev->next != NULL) { // (4)!
        Node *target = prev->next;
        prev->next = target->next;
        free(target);
    }
    return head;
}

int main()
{
    int n, q;
    scanf("%d %d", &n, &q);
    Node *head = read_list(n);
    for (int i = 0; i < q; i++) {
        int x;
        scanf("%d", &x);
        head = delete_value(head, x); // (5)!
        print_list(head);
    }
    free_list(head);
    return 0;
}
  1. ลิสต์ว่างไม่มีอะไรให้ลบ และใช้ head->value ไม่ได้
  2. ตู้หัวคือตู้ที่จะลบ จำตู้ที่สองไว้ก่อน free แล้วคืนตู้ที่สองเป็นหัวใหม่
  3. เดินจนกว่าตู้ถัดจาก prev คือตู้ที่ต้องการ หรือหมดขบวน ลำดับของสองเงื่อนไขสำคัญ ถ้า prev->next เป็น NULL เงื่อนไขแรกเป็นเท็จ && จะไม่ประเมินเงื่อนไขที่สองเลยตามหน้า 3.3 จึงไม่ไปแตะ NULL->value
  4. ถ้าออกจากลูปเพราะหมดขบวน แปลว่าไม่มีตู้ x ไม่ต้องทำอะไร
  5. ห้ามลืม head = เพราะการลบตู้หัวทำให้หัวเปลี่ยน
5 6
3 9 2 7 4
2
3
4
8
9
7

3 9 7 4
9 7 4
9 7
9 7
7
empty

ชุดข้อมูลนี้ตั้งใจให้ครบทุกกรณี ลบตู้กลาง ลบตู้หัว ลบตู้ท้าย ลบตู้ที่ไม่มี และลบจนขบวนว่าง เวลาเขียนฟังก์ชันลิสต์ของตัวเอง ให้ทดสอบครบชุดแบบนี้ทุกครั้ง

กลับลำดับ

อยากกลับขบวน 1 2 3 4 เป็น 4 3 2 1 วิธีที่ง่ายที่สุดคือสร้างลิสต์ใหม่ด้วย push_front ทีละตัวตามหน้า 14.1 แต่ต้องขอ node ใหม่ทั้งชุด วิธีที่นิยมกว่าคือกลับทิศลูกศรของลิสต์เดิมทุกเส้น ไม่ต้องสร้าง node ใหม่เลย

เดินจากหัวด้วยสามตัวแปร prev คือตู้ที่กลับทิศแล้ว cur คือตู้ที่กำลังจะกลับ และ next จำตู้ถัดไปไว้ก่อนเส้นจะถูกเปลี่ยน แต่ละรอบทำสี่บรรทัด

Node *next = cur->next; // (1)!
cur->next = prev; // (2)!
prev = cur; // (3)!
cur = next;
  1. จำทางไปตู้ถัดไปไว้ก่อน บรรทัดต่อไปจะเขียนทับ cur->next
  2. กลับทิศ ให้ตู้นี้ชี้ย้อนไปหาตู้ก่อนหน้า
  3. เลื่อนทั้งสองตัวไปข้างหน้าหนึ่งตู้
NULL 1 2 3 4 NULL prev cur reversed

ภาพนี้คือหลังรอบที่สอง ตู้ 1 กับ 2 กลับทิศแล้ว (สีส้ม) prev อยู่ที่ตู้ 2 ซึ่งเป็นหัวของส่วนที่กลับแล้ว cur อยู่ที่ตู้ 3 ซึ่งยังชี้ไปข้างหน้าตามเดิม พอ cur เป็น NULL ทุกตู้กลับครบ และ prev คือหัวใหม่

จบรอบprevcurส่วนที่กลับแล้ว เริ่มจาก prev
ก่อนเริ่มNULL1ไม่มี
1121
2232 1
3343 2 1
44NULL4 3 2 1
 
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int value;
    struct Node *next;
} Node;

Node *read_list(int n)
{
    Node *head = NULL;
    Node *tail = NULL;
    for (int i = 0; i < n; i++) {
        Node *node = malloc(sizeof(Node));
        scanf("%d", &node->value);
        node->next = NULL;
        if (head == NULL) {
            head = node;
        } else {
            tail->next = node;
        }
        tail = node;
    }
    return head;
}

void print_list(Node *head)
{
    for (Node *p = head; p != NULL; p = p->next) {
        printf("%d", p->value);
        if (p->next != NULL) {
            printf(" ");
        }
    }
    printf("\n");
}

void free_list(Node *head)
{
    while (head != NULL) {
        Node *next = head->next;
        free(head);
        head = next;
    }
}

Node *reverse(Node *head)
{
    Node *prev = NULL; // (1)!
    Node *cur = head;
    while (cur != NULL) {
        Node *next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

int main()
{
    int n;
    scanf("%d", &n);
    Node *head = read_list(n);
    head = reverse(head);
    print_list(head);
    head = reverse(head); // (2)!
    print_list(head);
    free_list(head);
    return 0;
}
  1. ตู้หัวเดิมจะกลายเป็นตู้สุดท้าย จึงต้องชี้ NULL การเริ่ม prev ที่ NULL ทำให้รอบแรกได้แบบนั้นพอดี
  2. กลับสองครั้งต้องได้ลำดับเดิม เป็นวิธีทดสอบง่ายๆ ว่าไม่มีตู้หาย
4
1 2 3 4

4 3 2 1
1 2 3 4

ลองป้อน N เป็น 0 และ 1 ด้วย ลูปไม่ทำเลยสักรอบหรือทำรอบเดียว และยังได้คำตอบถูกโดยไม่ต้องเขียนกรณีพิเศษ

ลองทำให้พัง

แบบที่ 1 สลับลำดับตอนแทรก

ในโปรแกรม insert-after สลับสองบรรทัดใน insert_after ให้ p เกี่ยวตู้ใหม่ก่อน

p->next = node;
node->next = p->next;

คอมไพล์ผ่านโดยไม่มีคำเตือน ป้อนข้อมูลชุดเดิม แล้วโปรแกรมพิมพ์ไม่หยุด

3 9 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5

บรรทัดแรกทำให้ p->next เป็นตู้ใหม่ บรรทัดที่สองจึงเท่ากับ node->next = node; ตู้ 5 เกี่ยวตัวเอง ลูปพิมพ์จึงวนอยู่ที่ตู้ 5 ตลอดไป ต้องกด Ctrl+C หรือปิดหน้าต่างเอง ส่วนตู้ 2 กับ 7 ไม่มีใครชี้ถึงอีกแล้ว ถ้าส่ง grader จะได้ผล Time Limit Exceeded เขียนลิสต์ทีไร ให้วาดกล่องกับลูกศรบนกระดาษก่อน แล้วเปลี่ยนลูกศรตามโค้ดทีละบรรทัด

แบบที่ 2 อ่าน next หลัง free

เขียน free_list แบบไม่จำตู้ถัดไปไว้ก่อน

void free_list(Node *head)
{
    while (head != NULL) {
        free(head);
        head = head->next;
    }
}

free_bug.c:13:14: warning: pointer 'head' used after 'free' [-Wuse-after-free]
   13 |         head = head->next;
      |         ~~~~~^~~~~~~~~~~~
free_bug.c:12:9: note: call to 'free' here
   12 |         free(head);
      |         ^~~~~~~~~~

คราวนี้ -Wall จับได้ หลัง free พื้นที่นั้นคืนไปแล้ว อ่าน head->next จากมันอีกคือใช้ของที่ไม่ใช่ของเรา บนเครื่องที่เขียนเอกสารนี้ โปรแกรมยังทำงานจบได้ปกติ เพราะพื้นที่ที่เพิ่งคืนบังเอิญยังมีค่าเดิมอยู่ แต่ไม่มีอะไรรับประกัน ถ้าระหว่างนั้นมีการ malloc พื้นที่นั้นอาจถูกใช้ไปเก็บอย่างอื่นแล้ว วิธีที่ถูกคือจำ next ไว้ในตัวแปรก่อน free แบบในหน้า 14.1

แบบที่ 3 ลืมรับหัวใหม่

ในโปรแกรม delete เขียน delete_value(head, x); เฉยๆ ไม่มี head = ข้างหน้า คอมไพล์ผ่านโดยไม่มีคำเตือน ป้อนข้อมูลชุดเดิม บนเครื่องที่เขียนเอกสารนี้ได้ผลแบบนี้

3 9 7 4
3 9 7 4
3 9 7
3 9 7
3 7
3

Process returned -1073740940 (0xC0000374)

บรรทัดแรกถูกเพราะลบตู้กลาง หัวไม่เปลี่ยน บรรทัดที่สองลบตู้ 3 ซึ่งเป็นหัว ฟังก์ชัน free ตู้ 3 แล้วคืนตู้ 9 มาเป็นหัวใหม่ แต่ไม่มีใครรับ head ของ main ยังชี้ตู้ 3 ที่คืนไปแล้ว พื้นที่นั้นบังเอิญยังมีค่าเดิมค้างอยู่ ตู้ 3 จึงยังโผล่ในทุกบรรทัดที่เหลือ จนบรรทัดสุดท้ายที่ควรขึ้นว่า empty ก็ยังเห็นตู้ 3 พอถึง free_list ตอนจบ ตู้ 3 ถูก free เป็นครั้งที่สอง Windows ตรวจเจอว่าระบบจัดการหน่วยความจำเสียหาย (heap corruption) จึงปิดโปรแกรมด้วยรหัส 0xC0000374 ฟังก์ชันไหนคืนหัวใหม่ ต้องเขียน head = ... ทุกครั้งที่เรียก

สรุป

  • แทรกหลัง p ให้ตู้ใหม่เกี่ยว p->next ก่อน แล้วค่อยให้ p เกี่ยวตู้ใหม่
  • ลบตู้ต้องหยุดที่ตู้ก่อนหน้า แล้วทำ prev->next = target->next ตู้หัวเป็นกรณีพิเศษที่ต้องย้าย head
  • กลับลำดับด้วย prev cur next จำตู้ถัดไปก่อนเปลี่ยนเส้น จบแล้ว prev คือหัวใหม่
  • ทดสอบทุกฟังก์ชันกับลิสต์ว่าง ตัวเดียว ตัวหัว ตัวท้าย และค่าที่ไม่มี
  • ห้ามแตะ node หลัง free และฟังก์ชันที่คืนหัวใหม่ต้องรับค่าด้วย head =