@TOC
前言
数据结构是计算机科学中的一个重要主题，它涉及到如何组织和存储数据，以便于在计算机程序中进行访问和操作。以下是一些常见的数据结构及其用途：
数组：数组是一种简单的数据结构，它可以存储一系列相同类型的数据。数组的主要优点是可以快速访问任何一个元素。数组的缺点是大小固定，一旦分配了内存空间，就无法改变。
链表：链表是一种动态数据结构，可以在运行时添加或删除元素。链表的主要优点是可以动态地分配内存空间，但是访问链表中的任何一个元素需要遍历整个链表，所以访问速度较慢。
栈：栈是一种后进先出（LIFO）的数据结构。它通常用于存储临时数据，例如函数调用时的局部变量。栈的主要优点是可以快速访问最后一个元素，但是不能随机访问栈中的其他元素。
队列：队列是一种先进先出（FIFO）的数据结构。它通常用于实现缓冲区或消息队列。队列的主要优点是可以快速访问最后一个元素和第一个元素，但是不能随机访问队列中的其他元素。
树：树是一种层次结构，它可以用于表示有父子关系的数据。树的主要优点是可以快速查找和插入元素，但是删除元素比较麻烦。
图：图是一种非常灵活的数据结构，可以用于表示复杂的关系。图的主要优点是可以表示各种类型的关系，但是访问和操作图比较复杂。
一、数组
数组是数据结构中最基本的一种数据类型，它可以存储一组相同类型的数据，并通过下标来访问其中的元素。以下是一些关于数组的知识点总结：
（一）知识点
| 概念 | 说明 |
|---|---|
| 数组的定义 | 数组是一种由相同类型的元素组成的集合，这些元素在内存中是连续存储的。数组的大小在创建时就确定了，无法在运行时改变。 |
| 数组的下标 | 数组的下标从零开始，最大值为数组长度减一。可以使用下标来访问数组中的元素，例如arr[0]表示数组中的第一个元素。 |
| 多维数组 | 数组也可以是多维的，例如二维数组就是由多个一维数组组成的。访问多维数组中的元素需要使用多个下标，例如arr[0][0]表示二维数组中的第一个元素。 |
| 数组的初始化 | 数组可以在创建时进行初始化，也可以在之后的代码中进行初始化。如果没有初始化，数组中的元素将会是随机值。 |
| 数组的遍历 | 可以使用for循环来遍历数组中的所有元素。 |
| 数组的排序 | 可以使用Arrays类提供的sort方法对数组中的元素进行排序。Arrays.sort(arr); |
| 数组的复制 | 可以使用Arrays类提供的copyOf方法复制数组，int[] arr2 = Arrays.copyOf(arr, arr.length); |
（二）常用操作代码示例
以下是C++中数组的基本操作示例：
1. 声明数组
int arr[5]; //声明一个长度为5的整型数组
2. 初始化数组
int arr[5] = {
1, 2, 3, 4, 5}; //声明一个长度为5的整型数组，并初始化为1,2,3,4,5
3. 访问数组元素
int arr[5] = {
1, 2, 3, 4, 5};
cout << arr[0] << endl; //输出数组第一个元素，即1
4. 修改数组元素
int arr[5] = {
1, 2, 3, 4, 5};
arr[0] = 0; //将数组第一个元素修改为0
5. 遍历数组
int arr[5] = {
1, 2, 3, 4, 5};
for (int i = 0; i < 5; i++) {
cout << arr[i] << " "; //输出数组所有元素
}
6. 数组作为函数参数
void printArray(int arr[], int len) {
for (int i = 0; i < len; i++) {
cout << arr[i] << " "; //输出数组所有元素
}
}
int main() {
int arr[5] = {
1, 2, 3, 4, 5};
printArray(arr, 5); //将数组作为函数参数传递
return 0;
}
二、链表
链表是数据结构中一种常用的线性结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。以下是一些关于链表的知识点总结：
（一）知识点
| 概念 | 说明 |
|---|---|
| 链表的定义 | 链表是一种线性结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表中的节点不一定是连续存储的，每个节点可以单独分配内存空间。 |
| 链表的分类 | 链表可以分为单向链表、双向链表和循环链表三种。单向链表每个节点只有一个指针指向下一个节点，双向链表每个节点有两个指针分别指向前一个节点和下一个节点，循环链表的尾节点指向头节点。 |
| 链表的操作 | 链表的基本操作包括插入、删除和查找。插入和删除操作需要修改节点的指针，查找操作需要遍历链表。 |
| 链表的优缺点 | 链表的优点是可以动态地分配内存空间，插入和删除操作效率高，缺点是访问链表中的任意节点需要遍历整个链表，效率较低。 |
| 链表的应用 | 链表在计算机科学中有广泛的应用，例如实现栈、队列、哈希表等数据结构，还可以用于表示多项式、图等抽象数据类型。 |
（二）常用操作代码示例
以下是C++中链表的基本操作示例：
1. 定义链表节点结构体
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {
}
};
2. 创建链表
ListNode* head = new ListNode(1); //创建头节点
ListNode* node1 = new ListNode(2); //创建第一个节点
ListNode* node2 = new ListNode(3); //创建第二个节点
head->next = node1; //头节点指向第一个节点
node1->next = node2; //第一个节点指向第二个节点
3. 遍历链表
ListNode* p = head; //从头节点开始遍历
while (p != NULL) {
cout << p->val << " "; //输出节点值
p = p->next; //指向下一个节点
}
4. 插入节点
ListNode* newNode = new ListNode(4); //创建新节点
ListNode* p = head; //从头节点开始遍历
while (p->next != NULL) {
p = p->next; //指向下一个节点
}
p->next = newNode; //将新节点插入到链表末尾
5. 删除节点
ListNode* p = head; //从头节点开始遍历
while (p->next != NULL && p->next->val != 3) {
p = p->next; //指向下一个节点
}
if (p->next != NULL) {
ListNode* temp = p->next; //保存要删除的节点
p->next = temp->next; //删除节点
delete temp; //释放内存
}
三、栈
栈是数据结构中一种常用的线性结构，它遵循先进后出的原则，即最后进入的元素最先弹出。以下是一些关于栈的知识点总结：
（一）知识点
| 概念 | 说明 |
|---|---|
| 栈的定义 | 栈是一种线性结构，它只允许在一端进行插入和删除操作。栈遵循先进后出的原则，即最后进入的元素最先弹出。 |
| 栈的基本操作 | 栈的基本操作包括入栈（push）、出栈（pop）、查看栈顶元素（peek）和判断栈是否为空（isEmpty）。 |
| 栈的实现 | 栈可以使用数组或链表来实现。使用数组实现的栈称为顺序栈，使用链表实现的栈称为链式栈。 |
| 栈的应用 | 栈在计算机科学中有广泛的应用，例如实现函数调用、表达式求值、括号匹配、迷宫路径搜索等。 |
| 栈的复杂度 | 入栈、出栈、查看栈顶元素和判断栈是否为空的时间复杂度均为O(1)。 |
（二）常用操作代码示例
以下是C++中栈的基本操作示例：
1. 头文件引用
#include <stack>
2. 声明栈
stack<int> s; //声明一个整型栈
3. 入栈
s.push(1); //将1入栈
s.push(2); //将2入栈
4. 出栈
s.pop(); //将栈顶元素2出栈
5. 访问栈顶元素
cout << s.top() << endl; //输出栈顶元素1
6. 判断栈是否为空
if (s.empty()) {
cout << "栈为空" << endl;
} else {
cout << "栈不为空" << endl;
}
四、队列
队列是数据结构中一种常用的线性结构，它遵循先进先出的原则，即最先进入的元素最先弹出。以下是一些关于队列的知识点总结：
（一）知识点
| 概念 | 说明 |
|---|---|
| 队列的定义 | 队列是一种线性结构，它只允许在一端进行插入操作，在另一端进行删除操作。队列遵循先进先出的原则，即最先进入的元素最先弹出。 |
| 队列的基本操作 | 队列的基本操作包括入队（enqueue）、出队（dequeue）、查看队头元素（peek）和判断队列是否为空（isEmpty）。 |
| 队列的实现 | 队列可以使用数组或链表来实现。使用数组实现的队列称为顺序队列，使用链表实现的队列称为链式队列。 |
| 队列的应用 | 队列在计算机科学中有广泛的应用，例如实现广度优先搜索、任务调度、消息传递等。 |
| 队列的复杂度 | 入队、出队、查看队头元素和判断队列是否为空的时间复杂度均为O(1)。 |
（二）常用操作代码示例
以下是C++中队列的基本操作示例：
1. 头文件引用
#include <queue>
2. 声明队列
queue<int> q; //声明一个整型队列
3. 入队
q.push(1); //将1入队
q.push(2); //将2入队
4. 出队
q.pop(); //将队首元素1出队
5. 访问队首元素
cout << q.front() << endl; //输出队首元素2
6. 访问队尾元素
cout << q.back() << endl; //输出队尾元素2
7. 判断队列是否为空
if (q.empty()) {
cout << "队列为空" << endl;
} else {
cout << "队列不为空" << endl;
}
五、树
树是数据结构中一种非线性结构，它由多个节点和边组成，节点之间有父子关系。以下是一些关于树的知识点总结：
（一）知识点
| 概念 | 说明 |
|---|---|
| 树的定义 | 树是一种非线性结构，它由多个节点和边组成，节点之间有父子关系。树的根节点是没有父节点的节点，树的叶子节点是没有子节点的节点。 |
| 树的基本概念 | 树的基本概念包括节点、边、根节点、叶子节点、父节点、子节点、深度、高度等。 |
| 树的遍历 | 树的遍历分为深度优先遍历和广度优先遍历。深度优先遍历包括前序遍历、中序遍历和后序遍历，广度优先遍历又称为层次遍历。 |
| 树的实现 | 树可以使用数组或链表来实现。使用数组实现的树称为顺序存储树，使用链表实现的树称为链式存储树。 |
| 树的应用 | 树在计算机科学中有广泛的应用，例如实现文件系统、数据库索引、哈夫曼编码等。 |
| 树的复杂度 | 树的遍历时间复杂度为O(n)，其中n为树中节点的个数。 |
（二）常用操作代码示例
以下是C++中二叉树的基本操作示例：
1. 定义二叉树节点结构体
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {
}
};
2. 创建二叉树
TreeNode* root = new TreeNode(1); //创建根节点
TreeNode* node1 = new TreeNode(2); //创建左子节点
TreeNode* node2 = new TreeNode(3); //创建右子节点
root->left = node1; //根节点的左子节点为node1
root->right = node2; //根节点的右子节点为node2
3. 遍历二叉树
- 前序遍历
void preorderTraversal(TreeNode* root) {
if (root != NULL) {
cout << root->val << " "; //输出节点值
preorderTraversal(root->left); //遍历左子树
preorderTraversal(root->right); //遍历右子树
}
}
preorderTraversal(root); //从根节点开始前序遍历
- 中序遍历
void inorderTraversal(TreeNode* root) {
if (root != NULL) {
inorderTraversal(root->left); //遍历左子树
cout << root->val << " "; //输出节点值
inorderTraversal(root->right); //遍历右子树
}
}
inorderTraversal(root); //从根节点开始中序遍历
- 后序遍历
void postorderTraversal(TreeNode* root) {
if (root != NULL) {
postorderTraversal(root->left); //遍历左子树
postorderTraversal(root->right); //遍历右子树
cout << root->val << " "; //输出节点值
}
}
postorderTraversal(root); //从根节点开始后序遍历
4. 插入节点
TreeNode* newNode = new TreeNode(4); //创建新节点
TreeNode* p = root; //从根节点开始遍历
while (p->left != NULL) {
p = p->left; //指向左子节点
}
p->left = newNode; //将新节点插入到最左侧
5. 删除节点
TreeNode* p = root; //从根节点开始遍历
while (p->left != NULL && p->left->val != 2) {
p = p->left; //指向左子节点
}
if (p->left != NULL) {
TreeNode* temp = p->left; //保存要删除的节点
p->left = temp->left; //删除节点
delete temp; //释放内存
}
六、图
图是数据结构中一种非线性结构，它由多个节点和边组成，节点之间可以有多条边连接。以下是一些关于图的知识点总结：
（一）知识点
| 概念 | 说明 |
|---|---|
| 图的定义 | 图是一种非线性结构，它由多个节点和边组成，节点之间可以有多条边连接。图分为有向图和无向图，有向图中每条边都有一个方向，无向图中每条边没有方向。 |
| 图的基本概念 | 图的基本概念包括节点、边、度、路径、连通性、权重等。 |
| 图的遍历 | 图的遍历分为深度优先遍历和广度优先遍历。深度优先遍历和树的深度优先遍历类似，广度优先遍历和树的层次遍历类似。 |
| 图的实现 | 图可以使用邻接矩阵或邻接表来实现。邻接矩阵使用二维数组表示图中节点之间的连接关系，邻接表使用链表表示图中节点之间的连接关系。 |
| 图的应用 | 图在计算机科学中有广泛的应用，例如实现路由算法、社交网络分析、图像处理等。 |
| 图的复杂度 | 图的遍历时间复杂度为O(n+m)，其中n为图中节点的个数，m为图中边的个数。 |
（二）常用操作代码示例
以下是C++中图的基本操作示例：
1. 头文件引用
#include <vector>
#include <queue>
2. 定义图节点结构体
struct GraphNode {
int val;
vector<GraphNode*> neighbors;
GraphNode(int x) : val(x) {
}
};
3. 创建图
GraphNode* node1 = new GraphNode(1);
GraphNode* node2 = new GraphNode(2);
GraphNode* node3 = new GraphNode(3);
node1->neighbors.push_back(node2);
node1->neighbors.push_back(node3);
node2->neighbors.push_back(node1);
node2->neighbors.push_back(node3);
node3->neighbors.push_back(node1);
node3->neighbors.push_back(node2);
4. 遍历图
- 广度优先遍历
void bfs(GraphNode* node) {
queue<GraphNode*> q;
q.push(node); //将起始节点加入队列
unordered_set<GraphNode*> visited; //记录已经访问过的节点
visited.insert(node); //将起始节点标记为已访问
while (!q.empty()) {
GraphNode* curr = q.front(); //取出队首节点
q.pop(); //将队首节点出队
cout << curr->val << " "; //输出节点值
for (auto neighbor : curr->neighbors) {
if (visited.find(neighbor) == visited.end()) {
//如果邻居节点未被访问过
visited.insert(neighbor); //将邻居节点标记为已访问
q.push(neighbor); //将邻居节点加入队列
}
}
}
}
bfs(node1); //从节点1开始广度优先遍历
- 深度优先遍历
void dfs(GraphNode* node, unordered_set<GraphNode*>& visited) {
visited.insert(node); //将节点标记为已访问
cout << node->val << " "; //输出节点值
for (auto neighbor : node->neighbors) {
if (visited.find(neighbor) == visited.end()) {
//如果邻居节点未被访问过
dfs(neighbor, visited); //递归遍历邻居节点
}
}
}
unordered_set<GraphNode*> visited; //记录已经访问过的节点
dfs(node1, visited); //从节点1开始深度优先遍历
总结
数据结构(data structure)是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。简而言之，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合。“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结构。
