一、数据结构概述

数据结构是计算机科学的基本概念之一，是指数据的组织、管理和存储方式。在计算机科学中，数据结构是一种特殊的格式，用于组织和存储数据。数据结构可分为线性结构、树结构、图结构等不同类型。在 C++ 语言中，可以通过类和模板来实现各种不同类型的数据结构。

二、链表实现

链表是一种常见的数据结构，可以在任意节点处插入或删除数据，而无需移动其他数据。在 C++ 中，可以使用类实现链表。下面是一个简单的链表实现，包括节点和链表类：

// 链表节点类
class ListNode {
public:
    int val;
    ListNode *next;

    ListNode(int x) : val(x), next(NULL) {}
};

// 链表类
class LinkedList {
public:
    ListNode *head;

    LinkedList() {
        head = NULL;
    }

    // 在头部插入一个节点
    void insert(int x) {
        ListNode *node = new ListNode(x);
        node->next = head;
        head = node;
    }

    // 删除第一个节点
    void remove() {
        if (head == NULL) return;
        ListNode *node = head;
        head = head->next;
        delete node;
    }

    // 打印链表
    void print() {
        ListNode *node = head;
        while (node != NULL) {
            cout << node->val << " -> ";
            node = node->next;
        }
        cout << "NULL" << endl;
    }
};

使用该链表类可以很方便地进行链表操作：

LinkedList list;
list.insert(1);    // 插入 1
list.insert(2);    // 插入 2
list.insert(3);    // 插入 3
list.print();      // 输出 3 -> 2 -> 1 -> NULL
list.remove();     // 删除 3
list.print();      // 输出 2 -> 1 -> NULL

三、栈实现

栈是一种后进先出（LIFO）的数据结构，可以在栈顶插入和删除数据，非栈顶数据不能访问。在 C++ 中，可以使用类和模板实现栈。下面是一个简单的栈实现：

template
class Stack {
private:
    vector data;
public:
    // 入栈
    void push(T x) {
        data.push_back(x);
    }
    
    // 取栈顶元素
    T top() {
        if (data.empty()) return -1;  // 栈为空
        return data.back();
    }
    
    // 出栈
    void pop() {
        if (data.empty()) return;     // 栈为空
        data.pop_back();
    }
    
    // 判断栈是否为空
    bool empty() {
        return data.empty();
    }
    
    // 返回栈中元素个数
    int size() {
        return data.size();
    }
};

使用该栈类可以很方便地进行栈操作：

Stack<int> s;
s.push(1);    // 入栈 1
s.push(2);    // 入栈 2
s.push(3);    // 入栈 3
cout << s.top() << endl;    // 输出 3
s.pop();      // 出栈 3
cout << s.top() << endl;    // 输出 2
cout << s.size() << endl;   // 输出 2
cout << s.empty() << endl;  // 输出 0

四、队列实现

队列是一种先进先出（FIFO）的数据结构，可以在队尾插入和队头删除数据。在 C++ 中，可以使用类和模板实现队列。下面是一个简单的队列实现：

template
class Queue {
private:
    vector data;
public:
    // 入队
    void push(T x) {
        data.push_back(x);
    }
    
    // 取队头元素
    T front() {
        if (data.empty()) return -1;  // 队列为空
        return data.front();
    }
    
    // 出队
    void pop() {
        if (data.empty()) return;     // 队列为空
        data.erase(data.begin());
    }
    
    // 判断队列是否为空
    bool empty() {
        return data.empty();
    }
    
    // 返回队列中元素个数
    int size() {
        return data.size();
    }
};

使用该队列类可以很方便地进行队列操作：

Queue<int> q;
q.push(1);    // 入队 1
q.push(2);    // 入队 2
q.push(3);    // 入队 3
cout << q.front() << endl;  // 输出 1
q.pop();      // 出队 1
cout << q.front() << endl;  // 输出 2
cout << q.size() << endl;   // 输出 2
cout << q.empty() << endl;  // 输出 0

五、堆实现

堆是一种特殊的树型数据结构，满足堆属性（heap property）：对于每个节点 X，其父节点的键值小于或等于 X 的键值，子节点的键值大于或等于 X 的键值。在 C++ 中，可以使用类和模板实现堆。下面是一个简单的最小堆实现：

template
class MinHeap {
private:
    vector data;
public:
    // 向堆中插入一个元素
    void push(T x) {
        data.push_back(x);
        int cur = data.size() - 1;
        int parent = (cur - 1) / 2;
        while (cur > 0 && data[parent] > data[cur]) {
            swap(data[cur], data[parent]);
            cur = parent;
            parent = (cur - 1) / 2;
        }
    }
    
    // 取堆顶元素
    T top() {
        if (data.empty()) return -1;   // 堆为空
        return data[0];
    }
    
    // 删除堆顶元素
    void pop() {
        if (data.empty()) return;      // 堆为空
        swap(data[0], data.back());
        data.pop_back();
        int cur = 0;
        int left_child = cur * 2 + 1;
        while (left_child < data.size()) {
            int right_child = (cur + 1) * 2;
            int min_child = left_child;
            if (right_child < data.size() && data[right_child] < data[left_child]) {
                min_child = right_child;
            }
            if (data[cur] <= data[min_child]) break;
            swap(data[cur], data[min_child]);
            cur = min_child;
            left_child = cur * 2 + 1;
        }
    }
    
    // 判断堆是否为空
    bool empty() {
        return data.empty();
    }
    
    // 返回堆中元素个数
    int size() {
        return data.size();
    }
};

使用该堆类可以很方便地进行堆操作：

MinHeap<int> h;
h.push(3);    // 插入元素 3
h.push(1);    // 插入元素 1
h.push(2);    // 插入元素 2
cout << h.top() << endl;   // 输出 1
h.pop();      // 删除堆顶元素
cout << h.top() << endl;   // 输出 2
cout << h.size() << endl;  // 输出 2
cout << h.empty() << endl; // 输出 0

六、总结

C++ 可以通过类和模板来实现各种不同类型的数据结构，例如链表、栈、队列和堆。这些数据结构在算法和数据处理中都有广泛应用。

本文链接：https://my.lmcjl.com/post/15725.html