C++ 数据结构与算法图解----数据结构_c++ 数据结构 基本算法

数据结构

数据结构简介：
数据结构是计算机科学中用于组织和存储数据的一种方式，它定义了数据元素之间的关系、操作和访问方式。选择适当的数据结构可以提高算法的效率，并使得对数据的处理更加方便和灵活。

常见的数据结构包括以下几种：

数组（Array）：由相同类型的元素按顺序存储而成的数据集合，可以通过索引访问元素。数组在内存中是连续存储的。
初始化数组：int array[] = {1, 4, 5, 8, 2};

链表（Linked List）：由节点组成的数据结构，每个节点包含数据和一个指向下一个节点的指针。链表不需要连续的内存空间，可以实现动态插入和删除。

struct ListNode {
    int val;        // 节点值
    ListNode *next; // 后继节点引用
    ListNode(int x) : val(x), next(NULL) {}
};
 // 实例化节点
ListNode *n1 = new ListNode(4); // 节点 head
ListNode *n2 = new ListNode(5);
ListNode *n3 = new ListNode(1);
// 构建引用指向
n1->next = n2;
n2->next = n3;
1
2
3
4
5
6
7
8
9
10
11
12

栈（Stack）：具有后进先出（LIFO）特性的数据结构，只允许在栈顶进行插入和删除操作。
C++中的示例代码如下

stack<int> stk;
stk.push(1); // 元素 1 入栈
stk.push(2); // 元素 2 入栈
stk.pop();   // 出栈 -> 元素 2
stk.pop();//元素1出栈
1
2
3
4
5

队列（Queue）：具有先进先出（FIFO）特性的数据结构，插入操作在队尾进行，删除操作在队头进行。

queue<int> que;
que.push(2);
que.push(3);
que.pop();
que.pop();
1
2
3
4
5

树（Tree）：由节点和边组成的层次结构，每个节点可以有多个子节点。常见的树结构包括二叉树、红黑树、AVL树等。
以二叉树为例，每个节点包含三个成员变量：「值 val」、「左子节点 left」、「右子节点 right」 。

struct TreeNode {
    int val;         // 节点值
    TreeNode *left;  // 左子节点
    TreeNode *right; // 右子节点
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 初始化节点
TreeNode *n1 = new TreeNode(3); // 根节点 root
TreeNode *n2 = new TreeNode(4);
TreeNode *n3 = new TreeNode(5);
TreeNode *n4 = new TreeNode(1);
TreeNode *n5 = new TreeNode(2);

// 构建引用指向
n1->left = n2;
n1->right = n3;
n2->left = n4;
n2->right = n5;
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

图（Graph）：由节点和边组成的非线性数据结构，节点之间的边可以表示它们之间的关系。
可以分为有向图和无向图：

表示图的方法通常有两种：

邻接矩阵： 使用数组 vertices存储顶点，邻接矩阵edges存储边，edges[i][j]表示节点[i+1]和节点[j+1]之间是否有边.如下图所示

**哈希表（Hash Table）：**根据关键字直接访问数据的数据结构，使用哈希函数将关键字映射到存储位置。通过利用 Hash 函数将指定的「键 key」映射至对应的「值 value」，以实现高效的元素查找。

// 初始化散列表
unordered_map<string, int> dic;

// 添加 key -> value 键值对
dic["小A"] = 10001;
dic["小B"] = 10002;
dic["小C"] = 10003;

// 从姓名查找学号
dic.find("小A")->second; // -> 10001
dic.find("小B")->second; // -> 10002
dic.find("小C")->second; // -> 10003
//dic的first就是对应的string键，second是对应的int值
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14

堆（Heap）：一种特殊的树结构，具有最大堆或最小堆的特性，常用于优先队列等场景。 可使用数组实现。以堆为原理的排序算法称为「堆排序」 。堆分为「大顶堆」和「小顶堆」，大（小）顶堆：任意节点的值不大于（小于）其父节点的值。

小顶堆的特点如下：

对于堆中的任意节点 node，node 的值都小于或等于其子节点的值。
根节点是堆中的最小值。
大顶堆的特点如下：
对于堆中的任意节点 node，node 的值都大于或等于其子节点的值。
根节点是堆中的最大值。
无论是小顶堆还是大顶堆，堆都是一棵完全二叉树。在实现堆的过程中，通常使用数组来存储堆的元素，通过数组的下标关系来表示元素之间的父子关系。

优先队列案例：

// 初始化小顶堆
priority_queue<int, vector<int>, greater<int>> heap;

// 元素入堆
heap.push(1);
heap.push(4);
heap.push(2);
heap.push(6);
heap.push(8);

// 元素出堆（从小到大）
heap.pop(); // -> 1
heap.pop(); // -> 2
heap.pop(); // -> 4
heap.pop(); // -> 6
heap.pop(); // -> 8
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

图表（表格）：以行和列的形式组织的数据结构，常用于存储和处理二维数据。