一、什么是数据结构
集合的定义：在计算机中，集合就是一组可变数量的数据项的组合。
数据结构定义：即数据元素相互之前存在一种或多种特定关系的集合。
一般可以从两个维度来理解它：逻辑结构和存储结构。
1、逻辑结构
简单的来说逻辑结构就是数据之间的关系，逻辑结构大概统一的可以分成两种：线性结构、非线性结构。
线性结构：是一个有序数据元素的集合。 其中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。
常用的线性结构有: 栈，队列，链表，线性表。
—非线性结构：各个数据元素不再保持在一个线性序列中，每个数据元素可能与零个或者多个其他数据元素发生联系。
常见的非线性结构有 二维数组，树等；
2、存储结构
逻辑结构指的是数据间的关系，而存储结构是逻辑结构用计算机语言的实现。常见的存储结构有顺序存储、链式存储、索引存储以及散列存储。
1）顺序存储
顺序存储方式就是在一块连续的存储区域一个接一个的存放数据。顺序存储方式把逻辑相邻的节点存储在物理位置相邻的存储单元里，节点间的逻辑关系有存储单元的邻接关系来体现。顺序存储方式也称为顺序存储结构，一般采用数组或结构数组来描述。
2）链式存储
链式存储方式比较灵活，不要求逻辑上相邻的节点在屋里位置上相邻，节点的逻辑关系有附加的引用字段来表示。一个节点的引用字段往往指向下一个节点的存放位置。链式存储方式也称为链式存储结构。
3）索引存储
索引存储方式是采用附加的索引表的方式来存储节点信息的一种存储方式。索引表由若干索引项组成。索引存储方式中索引项的一般形式为（关键字，地址）。其中，关键字是能够唯一表示一个节点的数据项。索引存储方式还可以细分为稠密索引：这种方式中每个节点在索引表中都有一个索引项，其中索引项的地址指示节点所在的存储位置。稀疏索引：这种方式中一组节点在索引表中只对应一个索引项，其中索引项的地址指示一组节点的起始存储位置。
4）散列存储
散列存储方式是根据节点的关键字直接计算出该节点的存储地址的一种存储方式。
在实际应用中，往往需要根据具体的数据结构来决定采用哪种存储方式。同一逻辑结构采用不同的存储方式，可以的得到不同的存储结构。而且这4种存储方法，既可以单独使用，也可以组合起来对数据结构进行存储描述。
例如：数组在内存中的位置是连续的，它就属于顺序存储；链表是主动建立数据间的关联关系的，在内存中却不一定是连续的，它属于链式存储；还有顺序和逻辑上都不存在顺序关系，但是你可以通过一定的方式去访问它的哈希表，数据散列存储。
3、数据结构 ----- 二叉树
树是用来模拟具有树状结构性质的数据集合。根据它的特性可以分为非常多的种类，对于我们来讲，掌握二叉树这种结构就足够了，它也是树最简单、应用最广泛的种类。
二叉树是一种典型的树树状结构。如它名字所描述的那样，二叉树是每个节点最多有两个子树的树结构，通常子树被称作“左子树”和“右子树”。
4、数据结构 ---- 链表
用一组任意存储的单元来存储线性表的数据元素。一个对象存储着本身的值和下一个元素的地址。
- 需要遍历才能查询到元素，查询慢。
- 插入元素只需断开连接重新赋值，插入快。
5、数据结构 ---- 数组
数组是我们在开发中最常见到的数据结构了，用于按顺序存储元素的集合。但是元素可以随机存取，因为数组中的每个元素都可以通过数组索引来识别。插入和删除时要移动后续元素，还要考虑扩容问题，插入慢。
6、数据结构 ---- 栈和队列
在上面的数组中，我们可以通过索引随机访问元素，但是在某些情况下，我们可能要限制数据的访问顺序，于是有了两种限制访问顺序的数据结构：栈（后进先出）、队列（先进先出）
7、数据结构 ---- 哈希表
哈希的基本原理是将给定的键值转换为偏移地址来检索记录。
键转换为地址是通过一种关系（公式）来完成的，这就是哈希（散列）函数。
虽然哈希表是一种有效的搜索技术，但是它还有些缺点。两个不同的关键字，由于哈希函数值相同，因而被映射到同一表位置上。该现象称为冲突。发生冲突的两个关键字称为该哈希函数的同义词。
8、数据结构 ---- 堆
堆的底层实际上是一棵完全二叉树，可以用数组实现
- 每个的节点元素值不小于其子节点 - 最大堆
- 每个的节点元素值不大于其子节点 - 最小堆
|