持续更新…

一、初识数据结构

A、概念

  数据：描述客观事物的符号，是计算机中可以操作的对象，能被计算机识别，并输入给计算机处理的符号集合(整型等数值类型，声音、图像、视频等非数值类型)
数据元素：是组成数据的、有一定意义的基本单位，在计算机通常作为整体处理，也被称为记录（比如人类的数据元素就是人）
数据项：一个数据元素可以由若干个数据项组成，数据项是数据不可分割的最小单位 （比如人的耳、鼻…）

---

B、程序

  程序就是由算法及数据结构构成的

---

C、数据结构

  是相互之间存在一种或多种特定关系的数据元素的集合，可按逻辑结构及物理结构进行分类，逻辑结构是面向问题的，物理结构是面向计算机的，其基本的目标就是将数据及其逻辑关系存储到计算机的内存中

1. 逻辑结构：指数据对象中数据元素之间的相互关系
   集合结构
   数据元素除了同属一个集合外，没有其他任何关系
   线性结构
   数据元素间是一对一的关系
   树形结构
   数据元素间是一对多的层次关系
   图形结构
   数据元素间是多对多的关系
2. 物理结构：数据的存储结构在计算机中的存储形式
   顺序存储结构
   链式存储结构

---

D、算法

  解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作
算法特性：
1. 输入：算法有零个或多个输入
2. 输出：至少有一个或多个输出
3. 有穷性：算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且一个步骤在可接受的时间内完成
4. 确定性：算法的每一个步骤都有确定含义，不会出现二义性
5. 可行性：算法的每一步都必须是可行的，也就是说，每一步都能通过执行有限次数完成

  设计算法要求：
1. 正确性
2. 可读性
3. 健壮性
4. 时间效率高
5. 空间使用率低
6. 简单性

二、算法复杂度

A、时间复杂度

• 常见的复杂度
  O(1)： 　 常数复杂度 　　　Constant Complexity
  O(log n)：对数复杂度 　　　Logarithmic
  O(n)：　　线性时间复杂度　Linear
  O(n^2)：　平方复杂度　　　N square
  O(n^3)：　立方复杂度　　　N square
  O(2^n)：　指数复杂度　　　Exponential
  O(n!)：　　阶乘复杂度　　　Factorial
• 优劣对比
  O(1) > O($log n$) > O($n$) > O($nlog n$) > O($n^2$ ) > O($n^3$) > O($2^n$) > O($n!$)
• O渐进表示法
  几个原则
  1. 如果运行时间是常数量级，则用常数1表示
  2. 只保留时间函数中的最高阶项
  3. 如果最高阶项系数存在且不是1.则去除这个系数
• 读程序直接判断复杂度
  1、无论n是啥，都执行一次，所以为O(1)

int n = 1000;
System.out.println("Hey - your input is: " + n);

  2、无论n是啥，都执行三次，所以为O(1)

int n = 1000;
System.out.println("Hey - your input is: " + n);
System.out.println("Hmm.. I'm doing more stuff with: " + n);
System.out.println("And more: " + n);

  3、for循环会执行n次，所以世为O(n)

for (int i = 1; i <= n; i++) {
System.out.println("Hey - I'm busy looking at: " + i);
}

  4、循环里面套循环，执行n*n次，所以为O(n^2)

for (int i = 1; i <= n; i++) {for (int j = 1; j <=n; j++) {System.out.println("Hey - I'm busy looking at: " + i + " and " + j);
}
}

  5、执行次数为$\log{_{2}}^{n}$，即O($\log{_{2}}^{n}$)，底数为啥无所谓，表示为O(log n)即可

for (int i = 1; i < n; i = i * 2) {
System.out.println("Hey - I'm busy looking at: " + i);
}

  6、为O(2^n)，这里用到了递归
PS：主定理判断递归复杂度

int fib(int n) {
if (n <= 2) return n;
return fib(n - 1) + fib(n - 2);
}

B、空间复杂度

三、物理结构

A、顺序存储结构

数组

• 概念
  数组(array)是有限个相同类型的变量所组成的集合，数组中的每一个变量被称为元素，数组是最简单最为常用的数据结构，在内存中是顺序存储的
• 基本操作
  1、读取元素O(1)
  2、更新元素O(1)
  3、插入元素O(n)
  尾部插入
  中间插入
  超范围插入
  4、删除元素O(n)
• 优缺点
  优点：具有非常高效的随机访问能力，只要给出下标，就可以用常量时间找到对应元素
  缺点：体现在插入和删除元素方面，由于数组元素连续紧密的存储在内存中，插入、删除元素都会导致大量元素被迫移动，影响效率
• Note
  数组适合在读操作多、写操作少的场景

B、链式存储结构

a、链表

• 概念
  链表(linked list)：是一种在物理上非连续、非顺序的数据结构，由若干节点(node)所组成，在内存中是随机存储的
  单项链表：每个节点包含两部分：存放数据的变量data，指向下一个节点的指针next
  双向链表：每个节点包含三部分：指向前置节点的prev指针，存放数据的变量data，指向下一个节点的指针next
  双向链表：尾节点的指针next指向头节点
• 基本操作
  1、查找节点 最坏O(n)
  2、更新节点O(1)
  3、插入节点O(1)：只要内存空间允许，能够插入链表的元素是无穷无尽的，不需要像数组那样考虑扩容的问题
  头部插入
  中间插入
  尾部插入
  4、删除节点O(1)：许多高级语言拥有自动化的垃圾回收机制，所以不用刻意去释放被删除的节点，只要没有外部引用指向它们，被删除的节点会被自动回收
  头部删除
  中间删除
  尾部删除

b、跳表

  跳表(skip list)是针对链表查找时间复杂度大进行改进的数据结构
思想：
1、升维思想
2、空间换时间

时间复杂度：O(log n)
空间复杂度：O(n)   ps:实际上是比链表增加了空间消耗，但量级没变

C、散列存储结构

a、散列表（哈希表）

  提供了键(Key)和值(Value)的映射关系。只要给出一个Key，就可以高效查找到它所匹配Value，时间复杂度接近于O(1)

• 通过哈希函数把Key和数组下标进行转换
  在不同的语言中，哈希函数的实现方式不一样
  在Java及大多数面向对象的语言中，每一个对象都有属于自己的hashcode，这个hashcode是区分不同对象的重要标识。
  转化方式：最简单的按照数组长度进行取模运算index = HashCode (Key) % Array.length
• 写操作(put)
  在散列表中插入新的键值对
  哈希冲突的解决方法
  1、开放寻址法
  当一个Key通过哈希函数获得对应的数组下标已被占用时，我们可以“另谋高就”，寻找下一个空档位置。
  2、链表法
  HashMap数组的每一个元素不仅是一个Entry对象，还是一个链表的头节点。每一个Entry对象通过next指针指向它的下一个Entry节点。当新来的Entry映射到与之冲突的数组位置时，只需要插入到对应的链表中即可
• 读操作
  读操作就是通过给定的Key，在散列表中查找对应的Value
• 扩容(resize)
  扩容，创建一个新的Entry空数组，长度是原数组的2倍，重新Hash，遍历原Entry数组，把所有的Entry重新Hash到新数组中

四、逻辑结构

A、线性结构

数据之间是一对一的关系

a、栈

• 栈(stack)中的元素只能先入后出(First In Last Out，简称FILO)。就像放入乒乓球的圆筒容器，最早进入的元素存放的位置叫作栈底(bottom)，最后进入的元素存放的位置叫作栈顶(top)
• 这种数据结构既可以用数组来实现，也可以用链表来实现
• 基本操作
  1、入栈O(1)
  入栈操作(push)就是把新元素放入栈中，只允许从栈顶一侧放入元素，新元素的位置将会成为新的栈顶
  2、出栈O(1)
  出栈操作(pop)就是把元素从栈中弹出，只有栈顶元素才允许出栈，出栈元素的前一个元素将会成为新的栈顶
• 应用
  1、栈通常用于对“历史”的回溯，也就是逆流而上追溯“历史”
  2、实现递归的逻辑
  3、面包屑导航，使用户在浏览页面时可以轻松地回溯到上一级或更上一级页面

b、队列

• 队列(queue)是一种线性数据结构，它的特征和行驶车辆的单行隧道很相似。不同于栈的先入后出，队列中的元素只能先入先出(First In First Out，简称FIFO)。队列的出口端叫作队头(front)，队列的入口端叫作队尾(rear)
• 这种数据结构既可以用数组来实现，也可以用链表来实现。
• 基本操作
  1、入队O(1)
  入队(enqueue)就是把新元素放入队列中，只允许在队尾的位置放入元素，新元素的下一个位置将会成为新的队尾
  2、出队O(1)
  出队操作(dequeue)就是把元素移出队列，只允许在队头一侧移出元素，出队元素的后一个元素将会成为新的队头
  数组实现的队列可以采用循环队列的方式来维持队列容量的恒定
  需要注意的是，队尾指针指向的位置永远空出1位，所以队列最大容量比数组长度小1
• 应用
  1、通常用于对“历史”的回放，也就是按照“历史”顺序，把“历史”重演一遍
  2、在多线程中，争夺公平锁的等待队列，就是按照访问顺序来决定线程在队列中的次序的
  3、网络爬虫实现网站抓取时，也是把待抓取的网站URL存入队列中，再按照存入队列的顺序来依次抓取和解析的
• 优先队列
  1、最大优先队列，无论入队顺序如何，都是当前最大的元素优先出队，基于最大堆实现
  2、最小优先队列，无论入队顺序如何，都是当前最小的元素优先出队，基于最小堆实现

B、树形结构

数据元素间一对多的关系

• 树的概念
  树(tree)是n(n≥0)个节点的有限集。当n=0时，称为空树。在任意一个非空树中，有如下特点：
  1、有且仅有一个特定的称为根的节点
  2、当n>1时，其余节点可分为m(m>0)个互不相交的有限集，每一个集合本身又是一个树，并称为根的子树
  
• 层级概念
  

a、二叉树

  二叉树(binary tree)是树的一种特殊形式。每个节点最多有2个孩子节点

• 满二叉树
  一个二叉树的所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层级上，那么这个树就是满二叉树
  
• 完全二叉树
  对一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号为从1到n。如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同，则这个二叉树为完全二叉树
  
• 表达方式
  1、链表
  
  2、数组
  对于一个稀疏的二叉树来说，用数组表示法是非常浪费空间的
  假设一个父节点的下标是parent，那么它的左孩子节点下标就是2×parent + 1；右孩子节点下标就是2×parent + 2。反过来，假设一个左孩子节点的下标是leftChild，那么它的父节点下标就是(leftChild-1)/ 2
  
• 应用
  1、查找
  二叉查找树(binary search tree) 时间复杂度：O(logn)
  
  2、维持相对顺序
  二叉排序树和查找树同样
  二叉树的自平衡问题
  红黑树
  AVL树
  树堆
• 遍历
  1、深度优先遍历
  前序遍历
  输出顺序：根节点、左子树、右子树
  
  中序遍历
  输出顺序：左子树、根节点、右子树
  
  后序遍历
  输出顺序：左子树、右子树、根节点
  
  2、广度优先遍历
  层序遍历
  

b、二叉堆

  本质上是一种完全二叉树，其所有节点都存储在数组中，是实现堆排序及优先队列的基础

• 最大堆
  最大堆的任何一个父节点的值，都大于或等于它左、右孩子节点的值
  
• 最小堆
  最小堆的任何一个父节点的值，都小于或等于它左、右孩子节点的值
  
• 二叉堆的自我调整
  1、插入节点O(logn)
  2、删除节点O(logn)
  3、构建二叉堆O(n)

参考资料：

1. 魏梦舒:《漫画算法：小灰的算法之旅》
2. 程杰:《大话数据结构》

→个人网站