c++教程

C++ 数据结构

C++ 数据结构概述与应用

随着计算机科学的发展，数据结构和算法已经成为软件开发的重要组成部分。C++ 作为一种广泛应用于软件开发的编程语言，其对数据结构的支持和操作性能尤为关键。本文将介绍 C++ 中的数据结构，包括常用的线性数据结构和非线性数据结构，以及它们在实际应用中的案例。

一、线性数据结构

线性数据结构是指具有一定线性特征的数据组织形式，其中包括顺序存储和链式存储两种形式。

1. 顺序存储

顺序存储是指用一组连续的存储单元依次存储线性表的数据元素。在 C++ 中，可以使用数组来实现顺序存储。以下是一个简单的示例：

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> arr = {1, 2, 3, 4, 5};

    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }

    return 0;
}

2. 链式存储

链式存储是指用一组存储单元存储线性表的数据元素，并通过指针来实现元素之间的链接。在 C++ 中，可以使用类来实现链式存储。以下是一个简单的链表类：

#include <iostream>

class ListNode {
public:
    int val;
    ListNode* next;

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

void printList(ListNode* head) {
    while (head != nullptr) {
        cout << head->val << " ";
        head = head->next;
    }
}

int main() {
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = nullptr;

    printList(head);

    return 0;
}

二、非线性数据结构

非线性数据结构是指不符合线性特征的数据组织形式。常见的非线性数据结构有树、图等。

1. 树

树（Tree）是一种非常典型的非线性数据结构，它由一个根节点和若干子节点组成。在 C++ 中，可以使用类来实现树的结构。以下是一个简单的二叉树类：

#include <iostream>
#include <queue>

class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void printTree(TreeNode* root) {
    if (root == nullptr) {
        return;
    }

    printTree(root->left);
    cout << root->val << " ";
    printTree(root->right);
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    printTree(root);

    return 0;
}

2. 图

图（Graph）是另一种重要的非线性数据结构，它由顶点和边组成。在 C++ 中，可以使用邻接表或邻接矩阵来实现图的结构。以下是一个简单的邻接表表示的图：

#include <iostream>
#include <vector>
#include <list>

using namespace std;

class Graph {
public:
    int v;
    list<int>* adjList;

    Graph(int vertices) : v(vertices), adjList(new list<int>[vertices]) {}

    void addEdge(int src, int dest) {
        adjList[src].push_back(dest);
        adjList[dest].push_back(src);
    }

    void DFS(int start) {
        vector<bool> visited(v, false);

        dfs(start, visited);
    }

    void d