数据结构与算法

数据结构和算法

数据结构（data structure ）是指相互之间存在一种或多种特定关系的数据元素的集合

数据结构=逻辑结构+存储结构

数据结构=逻辑结构+存储结构+（存储结构上的）运算和操作

一、数据结构的三个方面

1. 数据的逻辑结构

• 线性结构：数据元素之间存在着"一对一"的线性关系
  • 线性表
  • 栈
  • 队列
  • 串及数组
• 非线性结构
  • 树形结构
  • 图形结构

2.数据的存储结构

• 顺序存储：把逻辑上相邻的节点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现

• 链式存储：数据元素的存储对应的是不连续的存储空间，每个存储节点对应一个需要存储的数据元素。

  ​ 每个结点是由数据域和指针域组成。 元素之间的逻辑关系通过存储节点之间的链接关系反映出来。

• 索引存储：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。

• 散列存储：根据结点的关键字直接计算出该结点的存储地址

3.数据的运算：检索、排序、插入、删除、修改等

同一逻辑结构可以对应多种存储结构

同样的运算，在不同的存储结构中，其实现过程是不同个的

二、线性表

• 线性表逻辑结构

  定义:线性表是n个类型相同数据元素的有限序列，通常记作（a 0 , a 1 , …a i-1 , a i , a i+1 …,a n-1 ）。

  特点：相同数据类型、序列（顺序性）、有限

• 线性表的存储结构

  1. 顺序表--顺序存储结构（ArrayList)

     • 特点：在内存中分配连续的空间，只存储数据，不需要存储地址信息。位置就隐含着地址
     • 优点：
       1. 节省存储空间，因为分配给数据的存储单元全用存放结点的数据（不考虑c/c++语言中数组需指定大小的情况），结点之间的逻辑关系没有占用额外的存储空间。
       2. 索引查找效率高，即每一个结点对应一个序号，由该序号可以直接计算出来结点的存储地址。
     • 缺点：
       1. 插入和删除操作需要移动元素，效率较低。
       2. 必须提前分配固定数量的空间，如果存储元素少，可能导致空闲浪费。
       3. 按照内容查询效率低，因为需要逐个比较判断

  2. 链表--链式存储结构(LinkedList--双向链表)

     • 特点：数据元素的存储对应的是不连续的存储空间，每个存储结点对应一个需要存储的数据元素。

       每个结点是由数据域和指针域组成。 元素之间的逻辑关系通过存储节点之间的链接关系反映出来。

       逻辑上相邻的节点物理上不必相邻。

     • 优点：

       1. 插入、删除灵活 (不必移动节点，只要改变节点中的指针，但是需要先定位到元素上)。
       2. 有元素才会分配结点空间，不会有闲置的结点。

     • 缺点：

       1. 比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成，所以相同空间内假设全存满的话顺序比链式存储更多)。
       2. 查找结点时链式存储要比顺序存储慢（每个节点地址不连续、无规律，导致按照索引查询效率低下）。

• java中的线性表

  深入理解java中的ArrayList和LinkedList

  https://www.cnblogs.com/fingerboy/p/5478073.html

三、栈

• 栈的逻辑结构

  栈（stack ）又称堆栈，它是运算受限的线性表。
  其限制是仅允许在表的一端进行插入和删除操作，不允许在其他任何位置进行插入、查找、删除等操作。
  表中进行插入、删除操作的一端称为 栈顶（top） ，栈顶保存的元素称为 栈顶元素。
  相对的，表的另一端称为栈底（bottom）

  当栈中没有数据元素时称为空栈；
  向一个栈插入元素又称为 进栈或 入栈；
  从一个栈中删除元素又称为 出栈或 退栈。
  由于栈的插入和删除操作仅在栈顶进行，后进栈的元素必定先出栈，
  所以又把堆栈称为 后进先出表（Last In First Out，简称 LIFO）

    栈接口，定义了栈的主要操作
     记住针对栈的专业词汇：push、pop、peek
  

• 栈的存储结构

  1. 顺序栈

     顺序栈是使用顺序存储结构实现的堆栈，即利用一组地址连续的存储单元依次存放堆栈中的数据元素。
     由于堆栈是一种特殊的线性表，因此在线性表的顺序存储结构的基础上，选择线性表的一端作为栈顶即可。
     根据数组操作的特性，选择数组下标大的一端，即线性表顺序存储的表尾来作为栈顶，此时入栈、出栈等操作可以在Ο(1)时间完成。
     由于堆栈的操作都在栈顶完成，因此在顺序栈的实现中需要附设一个指针 top 来动态的指示栈顶元素在数组中的位置。
     通常 top 可以用栈顶元素所在数组下标来表示，top= -1 时表示空栈。

  2. 链栈

     当采用单链表存储线性表后，根据单链表的操作特性选择单链表的头部作为栈顶，此时，入栈、出栈等操作可以在Ο(1)内完成。
     由于堆栈的操作只在线性表的一端进行，在这里使用带头结点的单链表或不带头结点的单链表都可以。
     使用带头结点的单链表时，结点的插入和删除都在头结点之后进行；
     使用不带头结点的单链表时，结点的插入和删除都在链表的首结点上进行。

四、队列

• 队列的逻辑结构

  队列（queue ）简称队，它同堆栈一样，也是一种运算受限的线性表，
  其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。
  在队列中把插入数据元素的一端称为 队尾（rear） ），删除数据元素的一端称为 队首（front） ）。
  向队尾插入元素称为 进队或入队，新元素入队后成为新的队尾元素；
  从队列中删除元素称为 离队或出队，元素出队后，其后续元素成为新的队首元素。
  由于队列的插入和删除操作分别在队尾和队首进行，每个元素必然按照进入的次序离队，
  也就是说先进队的元素必然先离队，所以称队列为 先进先出表（First In First Out,简称FIFO）。

• 队列的存储结构

  1. 顺序队列

     • 方法1：使用数组作为存储结构：

       缺点：通过出队操作将数据弹出队列后，front之前的空间还能够再次得到吗？

       不能。所以使用普通数组实现队列，就再也不能使用front之前的空间了，这会导致大量空间丢失

     • 方法2：使用循环数组作为存储结构：

       为了解决这个问题，将普通数组换成循环数组。在循环数组中，末尾元素的下一个元素不是数组外，而是数组的头元素。

       这样就能够再次使用front之前的存储空间了

  2. 链式队列

     • 单链队列

       根据单链表的特点，选择链表的头部作为队首，链表的尾部作为队尾。

       除了链表头结点需要通过一个引用来指向之外，还需要一个对链表尾结点的引用，以方便队列的入队操作的实现。
       为此一共设置两个指针，一个队首指针和一个队尾指针，如图 所示。
       队首指针指向队首元素的前一个结点，即始终指向链表空的头结点，队尾指针指向队列当前队尾元素所在的结点。
       当队列为空时，队首指针与队尾指针均指向空的头结点
       

     • 双端队列deque double ended queue 通常读为"deck"

       所谓双端队列是指两端都可以进行进队和出队操作的队列，如下图所示，将队列的两端分别称为前端和后端，两端都可以入队和出队。其元素的逻辑结构仍是线性结构

       在双端队列进队时：前端进的元素排列在队列中后端进的元素的前面，后端进的元素排列在队列中前端进的元素的后面。在双端队列出队时，无论前端出还是后端出，先出的元素排列在后出的元素的前面。

       输出受限的双端队列，即一个端点允许插入和删除，另一个端点只允许插入的双端队列。

       输入受限的双端队列，即一个端点允许插入和删除，另一个端点只允许删除的双端队列。

五、树

1. 二叉树

   • 二叉树的定义：二叉树的每个结点至多只有二棵子树 (不存在度大于 2 的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第 i 层至多有 2i-1 个结点；深度为 k 的二叉树至多有 2k-1 个结点；对任何一棵二叉树 T，如果其终端结点数为 n0，度为 2 的结点数为 n2，则 n0=n2+1。
   • 满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点。也可以这样理解，除叶子结点外的所有结点均有两个子结点。节点数达到最大值，所有叶子结点必须在同一层上。
   • 完全二叉树：若设二叉树的深度为 h，除第 h 层外，其它各层 (1～(h-1) 层) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

2. 二叉查找树

   • 二叉查找树定义：又称为是二叉排序树（Binary Sort Tree）或二叉搜索树。二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
     • 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
     • 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
     • 左、右子树也分别为二叉排序树；
     • 没有键值相等的节点。
   • 二叉查找树的性质：对二叉查找树进行中序遍历，即可得到有序的数列。
   • 二叉查找树的时间复杂度：它和二分查找一样，插入和查找的时间复杂度均为 O(logn)，但是在最坏的情况下仍然会有 O(n) 的时间复杂度。

3. 平衡二叉树

   • 平衡二叉树定义：平衡二叉树（Balanced Binary Tree）又被称为 AVL 树（有别于 AVL 算法）

     • 具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用算法有红黑树、AVL 树等。在平衡二叉搜索树中，我们可以看到，其高度一般都良好地维持在 O(log2n)，大大降低了操作

   • 最小二叉平衡树的节点的公式如下：

     　　F(n)=F(n-1)+F(n-2)+1

     　　这个类似于一个递归的数列，可以参考 Fibonacci 数列，1 是根节点，F(n-1) 是左子树的节点数量，F(n-2) 是右子树的节点数量。

   • 自平衡二叉查找树：在 AVL 中任何节点的两个儿子子树的高度最大差别为 1，所以它也被称为高度平衡树，n 个结点的 AVL 树最大深度约 1.44log2n。查找、插入和删除在平均和最坏情况下都是 O(logn)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在 O(logN)。但是频繁旋转会使插入和删除牺牲掉 O(logN) 左右的时间，不过相对二叉查找树来说，时间上稳定了很多。

   • 红黑树的定义：红黑树是一种自平衡二叉查找树

   • 红黑树的性质：

     　　红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制的一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:

     　　性质 1. 节点是红色或黑色。

     　　性质 2. 根是黑色。

     　　性质 3. 所有叶子都是黑色（叶子是 NIL 节点）。

     　　性质 4. 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)

     　　性质 5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

4. B树

   • 　B 树也是一种用于查找的平衡树，但是它不是二叉树。

   • 　B 树的定义：B 树（B-tree）是一种树状数据结构，能够用来存储排序后的数据。这种数据结构能够让查找数据、循序存取、插入数据及删除的动作，都在对数时间内完成。B
     树，概括来说是一个一般化的二叉查找树，可以拥有多于 2 个子节点。与自平衡二叉查找树不同，B -
     树为系统最优化大块数据的读和写操作。B-tree
     算法减少定位记录时所经历的中间过程，从而加快存取速度。这种数据结构常被应用在数据库和文件系统的实作上。

     ​

参考资料：https://www.cnblogs.com/duye/p/9521102.html