C++ 数据结构

引言

数据结构是计算机科学中的一个核心概念，它涉及到如何在计算机中组织和存储数据，以便高效地进行数据访问和修改。C++作为一种高效的编程语言，提供了丰富的内置数据类型和库，支持各种复杂的数据结构实现。本文将探讨C++中常用的数据结构，包括数组、链表、栈、队列、树和图等，并分析它们的特点、应用场景以及如何在C++中实现这些数据结构。

数组

数组是C++中最基本的数据结构，它允许存储相同类型的数据元素集合。数组的特点是元素在内存中连续存储，可以通过索引快速访问。然而，数组的长度在定义时固定，不易动态扩展。

数组的声明和初始化

int arr[10]; // 声明一个包含10个整数的数组
int arr[5] = {1, 2, 3, 4, 5}; // 声明并初始化数组

数组的访问和修改

int firstElement = arr[0]; // 访问第一个元素
arr[2] = 10; // 修改第三个元素

链表

链表是一种动态数据结构，由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。链表的特点是元素不连续存储，通过指针连接，便于插入和删除操作。

单链表的实现

struct Node {
    int data;
    Node* next;
};

class LinkedList {
public:
    LinkedList() : head(nullptr) {}
    void insert(int value);
    void deleteValue(int value);
    void display();
private:
    Node* head;
};

链表的插入和删除操作

void LinkedList::insert(int value) {
    Node* newNode = new Node{value, nullptr};
    if (head == nullptr) {
        head = newNode;
    } else {
        Node* current = head;
        while (current->next != nullptr) {
            current = current->next;
        }
        current->next = newNode;
    }
}

void LinkedList::deleteValue(int value) {
    if (head == nullptr) return;

    if (head->data == value) {
        Node* temp = head;
        head = head->next;
        delete temp;
        return;
    }

    Node* current = head;
    while (current->next != nullptr && current->next->data != value) {
        current = current->next;
    }

    if (current->next != nullptr) {
        Node* temp = current->next;
        current->next = current->next->next;
        delete temp;
    }
}

栈和队列

栈和队列是两种特殊的线性数据结构，它们对元素的插入和删除操作有特定的限制。

栈

栈是一种后进先出（LIFO）的数据结构。在C++中，可以使用标准模板库（STL）中的stack容器来实现栈。

#include <stack>

std::stack<int> s;
s.push(1); // 入栈
s.pop(); // 出栈
int top = s.top(); // 获取栈顶元素

队列

队列是一种先进先出（FIFO）的数据结构。在C++中，可以使用STL中的queue容器来实现队列。

#include <queue>

std::queue<int> q;
q.push(1); // 入队
q.pop(); // 出队
int front = q.front(); // 获取队首元素

树和图

树和图是两种非线性数据结构，用于表示元素之间的复杂关系。

树

树是一种层次化的数据结构，由节点组成，每个节点有零个或多个子节点。常见的树结构包括二叉树、二叉搜索树（BST）、平衡树（如AVL树）等。

struct TreeNode {
    int value;
    TreeNode* left;
    TreeNode* right;
};

图

图是由节点（或顶点）和边组成的数据结构，用于表示对象之间的多对多关系。图的表示方法有邻接矩阵和邻接表等。

#include <vector>

class Graph {
public:
    Graph(int vertices) : adjacencyList(vertices) {}
    void addEdge(int src, int dest);
    void display();
private:
    std::vector<std::vector<int>> adjacencyList;
};

结论

C++提供了丰富的数据结构选择，每种数据结构都有其独特的特性和应用场景。了解和掌握这些数据结构对于提高程序性能和解决复杂问题至关重要。在实际编程中，应根据具体需求选择合适的数据结构，并灵活运用C++的内置类型和库来实现它们。