โครงสร้างข้อมูลใน C/C++

Singly Linked List

แต่ละ node เก็บ value และ link ไป node ถัดไป

Singly Linked List คืออะไร?

แต่ละ node เก็บ value และ link ไป node ถัดไป

สร้าง วน และทำลาย linked list

ประเด็นสำคัญ

  • กำหนด invariant ก่อนเขียน operation
  • จัดการกรณีว่าง เต็ม และ allocation ล้มเหลว
  • ประเมิน complexity และ ownership พร้อมกัน

ตัวอย่างโค้ด C และ C++

C
รันโค้ด →
main.c
#include <stdio.h>
#include <stdlib.h>

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

int main(void) {
    Node *head = NULL;
    for (int value = 3; value >= 1; --value) {
        Node *node = malloc(sizeof *node);
        if (!node) return 1;
        *node = (Node){value, head};
        head = node;
    }
    while (head) {
        Node *next = head->next;
        printf("%d ", head->value);
        free(head);
        head = next;
    }
    puts("");
    return 0;
}
ผลลัพธ์ที่คาดหวัง
1 2 3
C++
รันโค้ด →
main.cpp
#include <iostream>
#include <memory>

struct Node {
    int value;
    std::unique_ptr<Node> next;
};

int main() {
    std::unique_ptr<Node> head;
    for (int value = 3; value >= 1; --value) {
        head = std::make_unique<Node>(Node{value, std::move(head)});
    }
    for (Node *node = head.get(); node; node = node->next.get()) {
        std::cout << node->value << ' ';
    }
    std::cout << '\n';
}
ผลลัพธ์ที่คาดหวัง
1 2 3

เปรียบเทียบ C และ C++

C malloc และ free ทุก node ส่วน C++ unique_ptr ปล่อยทั้ง chain เมื่อ head ถูกทำลาย

C

Struct และ operation แยกกัน การจัดสรรชัดเจน

C++

Class และ container รักษา invariant และ resource

แบบฝึกหัด

รันทั้งสองเวอร์ชันแล้วแก้ไขเพื่อสังเกตความแตกต่างของภาษา

  • ทดสอบสถานะว่างและเต็ม
  • เขียน cleanup และตรวจ memory leak
  • เปรียบเทียบกับ standard container