数据结构与算法

数据结构和算法

一、数据结构的三个方面

1. 数据的逻辑结构

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

2.数据的存储结构

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

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

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

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

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

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

二、线性表

• 线性表逻辑结构

• 线性表的存储结构

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

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

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

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

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

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

     • 优点：

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

     • 缺点：

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

• java中的线性表

三、栈

• 栈的逻辑结构

• 栈的存储结构

  1. 顺序栈

  2. 链栈

四、队列

• 队列的逻辑结构

• 队列的存储结构

  1. 顺序队列

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

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

  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