常用的数据结构和算法
① 算法的性质是什么常见的数据结构的类型是什么
算法的特点：
1、输入：一个算法必须有零个或以上输入量。
2、输出：一个算法应有一个或以上输出量，输出量是算法计算的结果。
3、明确性：算法的描述必须无歧义，以保证算法的实际执行结果是精确地符合要求或期望，通常要求实际运行结果是确定的。
4、有限性：依据图灵的定义，一个算法是能够被任何图灵完备系统模拟的一串运算，而图灵机只有有限个状态、有限个输入符号和有限个转移函数（指令）。而一些定义更规定算法必须在有限个步骤内完成任务。
5、有效性：又称可行性。能够实现，算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。
常用的数据结构有4种：
1.集合。2.线性结构。3.树形结构。4.图状结构;
② 计算机考研：数据结构常用算法解析(1)
数据结构是计算机考研408计算机学科专业基础综合的重要组成部分，考生需要认真复习，尤其是对于数据结构中一些常用的算法问题，考生一定要弄懂弄会，理解的去掌握。猎考考研就带大家一一梳理这些知识点。
第一章
◆ 数据：指能够被计算机识别、存储和加工处理的信息载体。
◆ 数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。
◆ 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。
在高级语言程序中又分为：非结构的原子类型和结构类型
◆抽象数据类型(ADT)：是指一个数学模型以及定义在该模型上的一组操作。
一个抽象的数据类型的软件模块通常包含定义和表示和实现
用三元组(D，S，P)：数据对象、数据关系、基本操作
◆ 数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:
数据的逻辑结构、存储结构和数据的运算。
◆ 逻辑结构：指各数据元素之间的逻辑关系。
◆ 存储结构：就是数据的逻辑结构用计算机语言的实现。
◆ 线性结构：数据逻辑结构中的一类，它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。
◆ 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。
常用的存储表示方法有四种:
◆ 顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的
逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。
◆ 链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是
由附加的指针字段表示的。由此得到的存储表示称为链式存储结构。
◆ 索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。
◆ 散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。
渐近时间复杂度的表示法T(n)=O(f(n))，这里的"O"是数学符号，它的严格定义是"若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)=O(f(n))表示存在正的常数C和n0 ,使得当n≥n0时都满足0≤T(n)≤C·f(n)。"用容易理解的话说就是这两个函数当整型自变量n趋向于无穷大时，两者的比值是一个不等于0的常数。这么一来，就好计算了吧。
求某一算法的时间复杂度是关于N的统计，下面的例子很有反面意义
x=91; y=100;
while(y>0)
if(x>100)
{x=x-10;y--;}
else x++;
◆ T(n)=O(1)
◇ 这个程序看起来有点吓人，总共循环运行了1000次，但是我们看到n没有? 没。
◇ 这段程序的运行是和n无关的，就算它再循环一万年，我们也不管他，只是一个常数阶的函数。
考研有疑问、不知道如何总结考研考点内容、不清楚考研报名当地政策，点击底部咨询官网，免费领取复习资料：https://www.87dh.com/xl/
③ 一文带你认识30个重要的数据结构和算法
数组是最简单也是最常见的数据结构。它们的特点是可以通过索引（位置）轻松访问元素。
它们是做什么用的？
想象一下有一排剧院椅。每把椅子都分配了一个位置（从左到右），因此每个观众都会从他将要坐的椅子上分配一个号码。这是一个数组。将问题扩展到整个剧院（椅子的行和列），您将拥有一个二维数组（矩阵）。
特性
链表是线性数据结构，就像数组一样。链表和数组的主要区别在于链表的元素不存储在连续的内存位置。它由节点组成——实体存储当前元素的值和下一个元素的地址引用。这样，元素通过指针链接。
它们是做什么用的？
链表的一个相关应用是浏览器的上一页和下一页的实现。双链表是存储用户搜索键哗显示的页面的完美数据结构。
特性
堆栈是一种抽象数据类型，它形式化了受限访问集合的概念。该限制遵循 LIFO（后进先出）规则。因此，添加到堆栈中的最后一个元素是您从中删除的第一个元素。
堆栈可以使用数组或链表来实现。
它们是做什么用的？
现实生活中最常见的例子是在食堂中将盘子叠放在宽枝一起。位于顶部的板首先被移除。放置在最底部的盘子是在堆栈中保留时间最长的盘子。
堆栈最有用的一种情况是您需要获取给定元素的相反顺序。只需将它们全部推入堆栈，然后弹出它们。
另一个有趣的应用是有效括号问题。给定一串括号，您可以使用堆栈检查它们是否匹配。
特性
队列是受限访问集合中的另一种数据类型，就像前面讨论的堆栈一样。主要区别在于队列是按照FIFO（先进先出）模型组织的：队列中第一个插入的元素是第一个被移除的元素。队列可以使用固定长度的数组、循环数组或链表来实现。
它们是做什么用的？
这种抽象数据类型 (ADT) 的最佳用途当然是模拟现实生活中的队列。例如，在呼叫中心应用程序中，队列用于保存等待从顾问那里获得帮助的客户——这些客户应该按照他们呼叫的顺序获得帮助。
一种特殊且非常重要的队列类型是优先级队列。元素根据与它们关联的“优先级”被引入队列：具有最高优先级的元素首先被引入队列。这个 ADT 在许多图算法（Dijkstra 算法、BFS、Prim 算法、霍夫曼编码 ）中是必不可少的。它是使用堆实现的。
另一种特殊类型的队列是deque 队列（双关语它的发音是“deck”）。可以从队列的两端插入/删除元素。
特性
Maps （dictionaries）是包含键集合和值集合的抽象数据类型。每个键都有一个与之关联的值。
哈希表是一种特殊类型的映射。它使用散列函数生成一个散列码，放入一个桶或槽数组：键被散列，结果散列指示值的存储位置。
最常见的散列函数（在众多散列函数中）是模常数函数。例如，如果常量是 6，则键 x 的值是x%6。
理想情况下，散列函数会将每个键分配给一个唯一的桶，但他们的大多数设计都采用了不完善的函数，这可能会导致具有相同生成值的键之间发生冲突。这种碰撞总是以某种方式适应的。
它们是做什么用的？
Maps 最着名的应用是语言词典。语言中的每个词都为其指定了定义。它是使用有序映射实现的（其键按字母顺序排列）。
通讯录也是一张Map。每个名字都有一个分配给它的电话号码。
另一个有用的应用是值的标准化。假设我们要为一天中的每一分钟（24 小时 = 1440 分钟）分配一个从 0 到 1439 的索引。哈希函数将为h(x) = x.小时*60+x.分钟。
特性
术语：
因为maps 是使用自平衡红黑树实现的（文章后面会解释），所以所有操作都在 O(log n) 内完成；所有哈希表操作都是常量。
图是表示一对两个集合的非线性数据结构：G={V, E}，其中 V 是顶点（节点）的集合，而 E 是边（箭头）的集合。节点是由边互连的值 - 描述两个节点之间的依赖关系（有时与成本/距离相关联）的线。
图有两种主要类型：有稿巧行向图和无向图。在无向图中，边(x, y)在两个方向上都可用：(x, y)和(y, x)。在有向图中，边(x, y)称为箭头，方向由其名称中顶点的顺序给出：箭头(x, y)与箭头(y, x) 不同。
它们是做什么用的？
特性
图论是一个广阔的领域，但我们将重点介绍一些最知名的概念：
一棵树是一个无向图，在连通性方面最小（如果我们消除一条边，图将不再连接）和在无环方面最大（如果我们添加一条边，图将不再是无环的）。所以任何无环连通无向图都是一棵树，但为了简单起见，我们将有根树称为树。
根是一个固定节点，它确定树中边的方向，所以这就是一切“开始”的地方。叶子是树的终端节点——这就是一切“结束”的地方。
一个顶点的孩子是它下面的事件顶点。一个顶点可以有多个子节点。一个顶点的父节点是它上面的事件顶点——它是唯一的。
它们是做什么用的？
我们在任何需要描绘层次结构的时候都使用树。我们自己的家谱树就是一个完美的例子。你最古老的祖先是树的根。最年轻的一代代表叶子的集合。
树也可以代表你工作的公司中的上下级关系。这样您就可以找出谁是您的上级以及您应该管理谁。
特性
二叉树是一种特殊类型的树：每个顶点最多可以有两个子节点。在严格二叉树中，除了叶子之外，每个节点都有两个孩子。具有 n 层的完整二叉树具有所有2ⁿ-1 个可能的节点。
二叉搜索树是一棵二叉树，其中节点的值属于一个完全有序的集合——任何任意选择的节点的值都大于左子树中的所有值，而小于右子树中的所有值。
它们是做什么用的？
BT 的一项重要应用是逻辑表达式的表示和评估。每个表达式都可以分解为变量/常量和运算符。这种表达式书写方法称为逆波兰表示法 (RPN)。这样，它们就可以形成一个二叉树，其中内部节点是运算符，叶子是变量/常量——它被称为抽象语法树（AST）。
BST 经常使用，因为它们可以快速搜索键属性。AVL 树、红黑树、有序集和映射是使用 BST 实现的。
特性
BST 有三种类型的 DFS 遍历：
所有这些类型的树都是自平衡二叉搜索树。不同之处在于它们以对数时间平衡高度的方式。
AVL 树在每次插入/删除后都是自平衡的，因为节点的左子树和右子树的高度之间的模块差异最大为 1。 AVL 以其发明者的名字命名：Adelson-Velsky 和 Landis。
在红黑树中，每个节点存储一个额外的代表颜色的位，用于确保每次插入/删除操作后的平衡。
在 Splay 树中，最近访问的节点可以快速再次访问，因此任何操作的摊销时间复杂度仍然是 O(log n)。
它们是做什么用的？
AVL 似乎是数据库理论中最好的数据结构。
RBT（红黑树） 用于组织可比较的数据片段，例如文本片段或数字。在 Java 8 版本中，HashMap 是使用 RBT 实现的。计算几何和函数式编程中的数据结构也是用 RBT 构建的。
在 Windows NT 中（在虚拟内存、网络和文件系统代码中），Splay 树用于缓存、内存分配器、垃圾收集器、数据压缩、绳索（替换用于长文本字符串的字符串）。
特性
最小堆是一棵二叉树，其中每个节点的值都大于或等于其父节点的值：val[par[x]]