最近决定撸一下算法，然后想起来要过一下数据结构基础，接下来就和大家一起复习一下数据结构吧。

下面贴出一张数据结构日常用途。

结尾会给大家一些算法示意图网站，卷起来。

算法在计算机科学中扮演着重要的角色。它是任何正确定义的计算过程，该过程取某个值或值的集合作为输入并产生输出。

良好的算法设计能够提高程序的执行效率、减少程序占用空间、提高程序的可读性和可维护性。同时，解决同一个问题的各种不同算法的效率常常相差非常大，这种效率上的差距影响往往比硬件和软件方面的差距还要大。

算法需要数据结构的支撑，所以学习前我们必须熟练掌握这些基本数据结构！

数组

数组是一种线性数据结构，它用一组连续的内存空间来存储相同类型的数据。在数组中，每个元素都有一个唯一的索引，用于访问和修改它们。数组的优点是易于理解和实现，但缺点是插入和删除操作可能需要移动大量数据，导致效率较低。

链表

链表是一种非线性数据结构，由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。链表的优点是插入和删除操作相对简单，因为它们只需要修改指针。然而，链表的缺点是访问单个元素的速度较慢，因为需要从头节点开始遍历。

链表的特点：

采用动态存储分配，不会造成内存浪费和溢出。链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素。链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多。但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。栈和队列

栈是一种后进先出（LIFO）的数据结构，它只允许在一端（称为栈顶）进行插入和删除操作。栈的常用操作有push（压入元素）、pop（弹出元素）和peek（查看栈顶元素）。栈常用于处理具有特定顺序要求的问题，如函数调用和解谜游戏。

栈分为顺序栈、链式栈、递归栈等

队列是一种线性表，它只允许在表的一端进行插入，在表的另一端进行删除。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列的主要特点就是先进先出（FIFO） 。

队列有：顺序队列、链式队列、循环队列等

哈希表

哈希表提供了快速的插入操作和查找操作，无论哈希表总中有多少条数据，插入和查找的时间复杂度都是为O(1)，因为哈希表的查找速度非常快，所以在很多程序中都有使用哈希表，例如拼音检查器 。

哈希表的基本思想是将任意长度的二进制值通过一个特定的函数，变换成固定长度的字符串，用作数组的下标。比如说我们可以用一个短的字符串表示一个长的字符串，然后用这个短字符串作为数组的下标来存储长字符串。这样就可以通过短字符串来快速地查找到对应的长字符串了。

常见哈希表：

数组哈希表；链式哈希表；开放地址哈希表；二叉哈希表；压缩哈希表；位图哈希表树

树是一种非线性数据结构，由根节点、子节点和叶节点组成。树的一个常见例子是二叉树，其中每个节点最多有两个子节点。树的其他类型包括平衡树（如AVL树和红黑树）和非平衡树（如二叉搜索树）。树结构常用于表示层级关系和组织数据。

常见树的分类有 二叉树、AVL树、红黑树等

排序算法

将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程叫做排序。

分类：

非稳定排序算法：快速排序、希尔排序、堆排序、直接选择排序 稳定的排序算法：基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序

搜索算法

利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况，从而求出问题的解的一种方法。

分类：枚举算法、深度优先搜索、广度优先搜索、A*算法、回溯算法、蒙特卡洛树搜索、散列函数等算法。

贪心算法

在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

典型例子：

0/1背包问题，马踏棋盘，均分纸牌

分治算法

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。

典型例子：

排序中：归并排序、堆排序、快速排序；实例：找伪币、求最值、棋盘覆盖

动态规划

这个感觉比较难，后面也得卷起来！

用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。

动态规划一般可分为线性动规，区域动规，树形动规，背包动规四类。

线性动规：拦截导弹，合唱队形，挖地雷，建学校，剑客决斗等；

区域动规：石子合并， 加分二叉树，统计单词个数，炮兵布阵等；

树形动规：贪吃的九头龙，二分查找树，聚会的欢乐，数字三角形等；

背包问题：01背包问题，完全背包问题，分组背包问题，二维背包，装箱问题，挤牛奶（同济）等

算法相关链接：