简介
数据结构是计算机科学中的一个基本概念，用于存储和组织数据，以便能够高效地访问和修改。合理选择和使用数据结构可以显著提高程序的性能。
在本章中，我们将介绍一些常用的 C++ 数据结构，包括数组、链表、栈、队列和树等，并探讨它们的特点、优势以及适用场景。
数组
定义与特性
数组是一种线性数据结构，它将一系列元素按顺序存储在连续的内存空间中。每个元素通过索引（通常是整数）进行访问，索引从0开始。数组具有以下特点：
- 固定大小：创建数组时需要指定其大小，且大小不能改变。
- 随机访问：可以通过索引快速访问或修改数组中的任意元素。
- 内存连续：数组元素在内存中是连续存储的，因此访问速度快。
示例代码
-- -------------------- ---- -------
-------- ----------
--- ------ -
--- ------- -- -------------
--- ---- - - -- - - -- ---- -
------ - - - -- -- ------------
-
--------- -- ------- -- ----------
--- ---- - - -- - - -- ---- -
--------- -- ------ -- - --
-
------ --
-链表
定义与特性
链表也是一种线性数据结构，但它通过指针链接节点而非连续存储。链表的特点如下：
- 动态大小：可以根据需要添加或删除节点，从而改变链表的大小。
- 顺序访问：只能按照顺序依次访问链表中的元素，无法像数组那样通过索引随机访问。
- 内存不连续：链表的各个节点可以分散存储在内存的不同位置。
单向链表
单向链表的每个节点包含数据部分和指向下一个节点的指针。
节点定义
struct Node {
int data;
Node* next;
};插入节点
-- -------------------- ---- -------
---- ----------------- ----- --- ------ -
----- ------- - --- -------
------------- - ------
------------- - --------
-- ----- -- -------- -
---- - --------
- ---- -
----- ---- - -----
----- ----------- -- -------- -
---- - -----------
-
---------- - --------
-
-删除节点
-- -------------------- ---- -------
---- ----------------- ----- --- ---- -
----- ---- - -----
----- ---- - --------
-- ----- -- ------- -- ---------- -- ---- -
---- - -----------
------ -----
-------
-
----- ----- -- ------- -- ---------- -- ---- -
---- - -----
---- - -----------
-
-- ----- -- -------- -------
---------- - -----------
------ -----
-栈
定义与特性
栈是一种特殊的线性数据结构，遵循后进先出（LIFO）的原则。栈的操作主要有两种：压栈（push）和弹栈（pop）。栈通常用于实现递归算法、表达式求值和函数调用管理等。
示例代码
-- -------------------- ---- -------
-------- ----------
-------- -------
--- ------ -
--------------- --
---------- -- -------
----------
----------
--------- -- ------- -- ------- -- ---------- -- ------
-------- -- ------
--------- -- --------- -- ------- -- ----------
--------- -- -------- -- --------- -- ---------- -- -------
------ --
-队列
定义与特性
队列也是一种线性数据结构，遵循先进先出（FIFO）的原则。队列的主要操作包括入队（enqueue）和出队（dequeue），常用于任务调度、缓冲机制等场景。
循环队列
循环队列是一种特殊的队列形式，当队列达到最大容量时，新元素会被插入到队列的起始位置，形成“循环”。
定义队列
-- -------------------- ---- -------
------- -------- ---
----- ----- -
-------
------- - ----- - ---- - --- -
---- -------- ----- - ------ ------- -- - -- ---- -- -------- - -- -- ----- -- ---- - --- -
---- --------- ----- - ------ ------ -- ---- -
---- ----------- -------
--- ----------
--------
--- ------ -----
--- --------------
--
---- ------------------ ------ -
-- ---------- -
--------- -- ------ -- ----------
-------
-
-- ------ -- --- ----- - --
---- - ----- - -- - ---------
--------- - ------
-
--- ---------------- -
-- ----------- -
--------- -- ------ -- ----------
------ ---
-
--- ---- - -----------
-- ------ -- ----- -
----- - ---- - ---
- ---- -
----- - ------ - -- - ---------
-
------ -----
-树
定义与特性
树是一种非线性的数据结构，由有限个结点组成，其中有一个称为根的特殊结点，其余结点分为若干互不相交的子集，每个子集本身也是一棵树。树具有以下特点：
- 层次关系：树的结构使得它可以表示层次关系。
- 分支结构：树的每个节点可以有多个子节点。
- 无环：树中没有环路。
二叉树
二叉树是最常见的树形结构之一，每个节点最多有两个子节点。
二叉树节点定义
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};前序遍历
void preorderTraversal(TreeNode* root) {
if (root == nullptr) return;
std::cout << root->val << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}中序遍历
void inorderTraversal(TreeNode* root) {
if (root == nullptr) return;
inorderTraversal(root->left);
std::cout << root->val << " ";
inorderTraversal(root->right);
}后序遍历
void postorderTraversal(TreeNode* root) {
if (root == nullptr) return;
postorderTraversal(root->left);
postorderTraversal(root->right);
std::cout << root->val << " ";
}以上便是对几种常用数据结构的简要介绍和示例代码。这些数据结构在实际编程中应用广泛，理解它们的工作原理对于提升编程技能非常重要。