Hello Lang

外观

C 与 C++ 数据结构深度解析 ​

C 与 C++ 都能精确控制内存布局与生命周期，但二者的抽象哲学截然不同：

  • C 语言：采用命令式内存管理，通过 malloc/free、指针算术与显式结构体布局构建数据结构，由开发者全权负责资源销毁与所有权。
  • C++ (C++20)：采用 RAII（资源获取即初始化）、泛型模板与现代智能指针（std::unique_ptr/std::shared_ptr），标准库（STL）提供了兼具零成本抽象与工业级强度的容器体系。

📊 核心结构对照矩阵 ​

数据结构分类C 语言底层模式C++20 现代实现核心时间复杂度内存特征
动态数组struct + malloc/reallocstd::vector<T> / 自定义模板 Vector随机访问 $O(1)$，尾部均摊 $O(1)$连续内存，自动倍增扩容
单/双向链表裸指针节点 + 手动遍历释放std::forward_list / std::list / 智能指针链表头部/已知节点插删 $O(1)$，随机访问 $O(n)$非连续节点分散存储
栈 (LIFO)固定数组或链表栈std::stack<T> (底层默认 std::deque)Push / Pop $O(1)$适配器模式，保护栈语义
双端队列循环数组模运算std::deque<T> / std::queue<T>首尾插删 $O(1)$分段连续中控缓冲区
二叉搜索树递归指针节点std::set<T> / std::map<T> (红黑树底座)增删查 $O(\log n)$严格自平衡，节点开销
二叉堆 / 优先队列数组扁平化上浮下沉std::priority_queue<T> (std::make_heap)堆顶 $O(1)$，入堆出堆 $O(\log n)$隐式完全二叉树，无指针开销

1. 线性结构：动态数组 (Vector) ​

C 语言实现：手动 realloc 扩容与显式内存管理 ​

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

typedef struct {
    int *data;
    size_t size;
    size_t capacity;
} DynamicArray;

DynamicArray* da_create(size_t initial_cap) {
    DynamicArray *arr = (DynamicArray*)malloc(sizeof(DynamicArray));
    arr->capacity = initial_cap > 0 ? initial_cap : 4;
    arr->size = 0;
    arr->data = (int*)malloc(arr->capacity * sizeof(int));
    return arr;
}

void da_push(DynamicArray *arr, int val) {
    if (arr->size >= arr->capacity) {
        arr->capacity *= 2;
        arr->data = (int*)realloc(arr->data, arr->capacity * sizeof(int));
    }
    arr->data[arr->size++] = val;
}

int da_get(const DynamicArray *arr, size_t idx) {
    assert(idx < arr->size);
    return arr->data[idx];
}

void da_free(DynamicArray *arr) {
    if (arr) {
        free(arr->data);
        free(arr);
    }
}

int main(void) {
    printf("=== C Dynamic Array ===\n");
    DynamicArray *arr = da_create(2);
    da_push(arr, 10);
    da_push(arr, 20);
    da_push(arr, 30);
    assert(arr->size == 3);
    assert(arr->capacity == 4);
    assert(da_get(arr, 0) == 10);
    assert(da_get(arr, 1) == 20);
    assert(da_get(arr, 2) == 30);
    printf("DynamicArray size=%zu, cap=%zu, elements=[%d, %d, %d]\n", 
           arr->size, arr->capacity, da_get(arr, 0), da_get(arr, 1), da_get(arr, 2));
    printf("C Dynamic Array tests passed successfully.\n");
    da_free(arr);
    return 0;
}
🐳 Docker Verified📋gcc:13
Exit Code: 0
=== C Dynamic Array ===
DynamicArray size=3, cap=4, elements=[10, 20, 30]
C Dynamic Array tests passed successfully.

C++ 实现：RAII 泛型动态数组与 std::vector 对照 ​

cpp
#include <iostream>
#include <vector>
#include <cassert>

template <typename T>
class CustomVector {
private:
    T* data_;
    size_t size_;
    size_t capacity_;

    void reallocate(size_t new_cap) {
        T* new_data = new T[new_cap];
        for (size_t i = 0; i < size_; ++i) {
            new_data[i] = std::move(data_[i]);
        }
        delete[] data_;
        data_ = new_data;
        capacity_ = new_cap;
    }

public:
    CustomVector(size_t init_cap = 4) : size_(0), capacity_(init_cap) {
        data_ = new T[capacity_];
    }
    ~CustomVector() { delete[] data_; }

    void push_back(const T& value) {
        if (size_ >= capacity_) reallocate(capacity_ * 2);
        data_[size_++] = value;
    }
    const T& operator[](size_t index) const { return data_[index]; }
    size_t size() const { return size_; }
    size_t capacity() const { return capacity_; }
};

int main() {
    std::cout << "=== C++ std::vector & Custom Vector ===" << std::endl;
    std::vector<int> std_vec = {10, 20, 30};
    std_vec.push_back(40);
    assert(std_vec.size() == 4);

    CustomVector<std::string> str_vec(2);
    str_vec.push_back("Hello");
    str_vec.push_back("DataStructures");
    str_vec.push_back("C++20");
    assert(str_vec.size() == 3);
    assert(str_vec.capacity() == 4);
    assert(str_vec[0] == "Hello");

    std::cout << "CustomVector elements: " << str_vec[0] << ", " << str_vec[1] << ", " << str_vec[2] << std::endl;
    std::cout << "C++ Dynamic Array tests passed successfully." << std::endl;
    return 0;
}
🐳 Docker Verified📋gcc:13
Exit Code: 0
=== C++ std::vector & Custom Vector ===
CustomVector elements: Hello, DataStructures, C++20
C++ Dynamic Array tests passed successfully.

2. 链式结构：单向链表 (Linked List) ​

C 语言实现：显式所有权与递归/迭代析构 ​

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

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

Node* list_prepend(Node *head, int val) {
    Node *node = (Node*)malloc(sizeof(Node));
    node->value = val;
    node->next = head;
    return node;
}

void list_free(Node *head) {
    while (head) {
        Node *temp = head;
        head = head->next;
        free(temp);
    }
}

int main(void) {
    printf("=== C Singly Linked List ===\n");
    Node *head = NULL;
    head = list_prepend(head, 30);
    head = list_prepend(head, 20);
    head = list_prepend(head, 10);

    assert(head->value == 10);
    assert(head->next->value == 20);
    assert(head->next->next->value == 30);

    printf("List traversal: %d -> %d -> %d -> NULL\n", head->value, head->next->value, head->next->next->value);
    printf("C Linked List tests passed successfully.\n");
    list_free(head);
    return 0;
}
🐳 Docker Verified📋gcc:13
Exit Code: 0
=== C Singly Linked List ===
List traversal: 10 -> 20 -> 30 -> NULL
C Linked List tests passed successfully.

C++ 实现：std::forward_list 与 std::unique_ptr 现代节点 ​

cpp
#include <iostream>
#include <memory>
#include <forward_list>
#include <cassert>

template <typename T>
class LinkedList {
    struct Node {
        T data;
        std::unique_ptr<Node> next;
        Node(T val) : data(std::move(val)), next(nullptr) {}
    };
    std::unique_ptr<Node> head_;

public:
    void push_front(T val) {
        auto node = std::make_unique<Node>(std::move(val));
        node->next = std::move(head_);
        head_ = std::move(node);
    }
    const T& front() const { return head_->data; }
    bool empty() const { return head_ == nullptr; }
};

int main() {
    std::cout << "=== C++ std::forward_list & RAII UniquePtr List ===" << std::endl;
    std::forward_list<int> flist = {10, 20, 30};
    flist.push_front(5);
    assert(flist.front() == 5);

    LinkedList<std::string> custom_list;
    custom_list.push_front("World");
    custom_list.push_front("Hello");
    assert(custom_list.front() == "Hello");

    std::cout << "C++ Linked List tests passed successfully." << std::endl;
    return 0;
}
🐳 Docker Verified📋gcc:13
Exit Code: 0
=== C++ std::forward_list & RAII UniquePtr List ===
C++ Linked List tests passed successfully.

3. 受限线性结构：栈与队列 (Stack & Queue) ​

C 语言顺序栈实现 (Stack) ​

c
#include <stdio.h>
#include <stdbool.h>
#include <assert.h>

#define STACK_CAP 100

typedef struct {
    int data[STACK_CAP];
    int top;
} Stack;

void stack_init(Stack *s) { s->top = -1; }
bool stack_is_empty(const Stack *s) { return s->top == -1; }
void stack_push(Stack *s, int val) {
    assert(s->top < STACK_CAP - 1);
    s->data[++s->top] = val;
}
int stack_pop(Stack *s) {
    assert(!stack_is_empty(s));
    return s->data[s->top--];
}
int stack_peek(const Stack *s) {
    assert(!stack_is_empty(s));
    return s->data[s->top];
}

int main(void) {
    printf("=== C LIFO Stack ===\n");
    Stack s;
    stack_init(&s);
    stack_push(&s, 100);
    stack_push(&s, 200);
    assert(stack_peek(&s) == 200);
    assert(stack_pop(&s) == 200);
    assert(stack_pop(&s) == 100);
    assert(stack_is_empty(&s));
    printf("C Stack tests passed successfully.\n");
    return 0;
}
🐳 Docker Verified📋gcc:13
Exit Code: 0
=== C LIFO Stack ===
C Stack tests passed successfully.

C++ std::queue 与 std::deque 容器适配器 ​

cpp
#include <iostream>
#include <queue>
#include <deque>
#include <cassert>

int main() {
    std::cout << "=== C++ std::queue & std::deque ===" << std::endl;
    std::queue<std::string> q;
    q.push("first");
    q.push("second");
    q.push("third");

    assert(q.front() == "first");
    q.pop();
    assert(q.front() == "second");
    assert(q.size() == 2);

    std::deque<int> dq = {1, 2, 3};
    dq.push_front(0);
    dq.push_back(4);
    assert(dq.front() == 0 && dq.back() == 4);

    std::cout << "C++ Queue tests passed successfully." << std::endl;
    return 0;
}
🐳 Docker Verified📋gcc:13
Exit Code: 0
=== C++ std::queue & std::deque ===
C++ Queue tests passed successfully.

4. 树与堆：BST、智能指针树与优先队列 ​

C 语言二叉搜索树 (BST) ​

c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

typedef struct BSTNode {
    int key;
    struct BSTNode *left, *right;
} BSTNode;

BSTNode* bst_insert(BSTNode *root, int key) {
    if (!root) {
        BSTNode *n = (BSTNode*)malloc(sizeof(BSTNode));
        n->key = key;
        n->left = n->right = NULL;
        return n;
    }
    if (key < root->key) root->left = bst_insert(root->left, key);
    else if (key > root->key) root->right = bst_insert(root->right, key);
    return root;
}

bool bst_search(const BSTNode *root, int key) {
    if (!root) return false;
    if (root->key == key) return true;
    return key < root->key ? bst_search(root->left, key) : bst_search(root->right, key);
}

void bst_free(BSTNode *root) {
    if (!root) return;
    bst_free(root->left);
    bst_free(root->right);
    free(root);
}

int main(void) {
    printf("=== C Binary Search Tree (BST) ===\n");
    BSTNode *root = NULL;
    root = bst_insert(root, 50);
    root = bst_insert(root, 30);
    root = bst_insert(root, 70);
    root = bst_insert(root, 20);

    assert(bst_search(root, 30) == true);
    assert(bst_search(root, 99) == false);
    printf("C BST search verified successfully.\n");
    bst_free(root);
    return 0;
}
🐳 Docker Verified📋gcc:13
Exit Code: 0
=== C Binary Search Tree (BST) ===
C BST search verified successfully.

C++ 现代智能指针二叉树遍历 ​

cpp
#include <iostream>
#include <memory>
#include <vector>
#include <cassert>

struct TreeNode {
    int val;
    std::unique_ptr<TreeNode> left;
    std::unique_ptr<TreeNode> right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

void inorder(const TreeNode* node, std::vector<int>& out) {
    if (!node) return;
    inorder(node->left.get(), out);
    out.push_back(node->val);
    inorder(node->right.get(), out);
}

int main() {
    std::cout << "=== C++ Binary Tree with Smart Pointers ===" << std::endl;
    auto root = std::make_unique<TreeNode>(2);
    root->left = std::make_unique<TreeNode>(1);
    root->right = std::make_unique<TreeNode>(3);

    std::vector<int> traversed;
    inorder(root.get(), traversed);

    assert((traversed == std::vector<int>{1, 2, 3}));
    std::cout << "Inorder traversal: " << traversed[0] << ", " << traversed[1] << ", " << traversed[2] << std::endl;
    std::cout << "C++ Binary Tree tests passed successfully." << std::endl;
    return 0;
}
🐳 Docker Verified📋gcc:13
Exit Code: 0
=== C++ Binary Tree with Smart Pointers ===
Inorder traversal: 1, 2, 3
C++ Binary Tree tests passed successfully.

C++ 优先队列 (Priority Queue / Heap) ​

cpp
#include <iostream>
#include <queue>
#include <vector>
#include <cassert>

int main() {
    std::cout << "=== C++ std::priority_queue (Binary Heap) ===" << std::endl;
    std::priority_queue<int> max_heap;
    max_heap.push(15);
    max_heap.push(50);
    max_heap.push(30);

    assert(max_heap.top() == 50);
    max_heap.pop();
    assert(max_heap.top() == 30);

    std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
    min_heap.push(15);
    min_heap.push(50);
    min_heap.push(10);
    assert(min_heap.top() == 10);

    std::cout << "C++ Priority Queue tests passed successfully." << std::endl;
    return 0;
}
🐳 Docker Verified📋gcc:13
Exit Code: 0
=== C++ std::priority_queue (Binary Heap) ===
C++ Priority Queue tests passed successfully.

Released under the MIT License.

Copyright © 2026 Hello-Lang Platform