当前位置：首页 > news >正文

C++ 数据结构

news 2025/7/14 2:16:38

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;
};