《漫画算法》—— 数据结构基础

2 数据结构基础

2.1 什么是数组

2.1.1 初识数组？

数组是由有限个相同类型的变量所组成的有序集合，数组中的每一个变量称为元素。

数组的特点：有限个，在内存中顺序存储。

内存是由一个个连续的内存单元组成的，每一个内存单元都有自己的地址。

数组中的每一个元素，都存储在小小的内存单元中，并且元素直接紧密排列，既不能打乱元素的存储顺序，也不能跳过某个存储单元进行存储。

2.1.2 数组的基本操作：

1、读取元素：读取元素只需要给出一个数组的下标，就可以读取对应的数组元素，如array[3],读取下标为3的元素。

2、更新元素：利用索引，比较容易，直接操作，array[3]=10。

数组读取元素、更新元素的时间复杂度都是O(1)

3、插入元素：

• 尾部插入：末尾插入最简单，直接在最后插入即可。等同于更新元素。
• 中间插入：非末尾插入，由于数组的每一个元素都有其固定下标，所以需要先把插入位置及后面的元素向后移动，挪出地方，再把要插入的元素放到对应的数组位置上。
• 超范围插入：如果传入的下标参数index大于size或小于0，会直接抛出异常，需要先扩容。

4、删除元素：和插入过程相反，若删除的元素不是位于末尾，其后的元素都要向前移动。

插入元素、删除元素的时间复杂度都是O(n)

2.1.3 数组的优势：

非常高效的访问能力，只要给出下标，就能找到对应元素。如二分查找就是利用这个优势。

2.1.4 数组的劣势：

插入、删除效率低下。数组元素连续紧密地存储在内存中，插入、删除元素都会导致大量元素被迫移动，影响效率。

数组适合读操作多、写操作少的场景。链表和数组的适用情形正好相反。

2.2 链表

2.2.1 什么是链表：

链表（linked list）一种在物理上非连续、非顺序的数据结构，由若干节点(node)所组成。

单向链表的每一个节点包含两部分，存放数据的变量data，指向下一个节点的指针next。

private static class Node{
    int data ;
    Node next;
}

链表的第一个节点被称为头结点，最后一个节点被称为尾节点。尾节点的next指针指向空。
与数组不同，对于链表中的节点A，我们只能根据next的指针来找该节点的下一个节点B。

如果想要每个节点回溯到它的前置节点，我们可以用双向链表。

双向链表，每一个节点除了拥有 data 和 next，还拥有指向前置节点的 prev 指针。

存储方式：数组在内存中的存储方式是顺序存储，链表 在内存中的存储顺序是随机存储。
数组在内存中占用了连续完整的存储空间，而链表采用了见缝插针的方式，链表的没一个节点分布在内存的不同位置，依靠next指针关联起来。这样可以灵活有效地利用零散的碎片空间。

2.2.2 链表的基本操作：

1、查找节点：只能从头节点开始向后一个一个节点逐一查找。
链表中的数据只能按顺序进行访问，最坏的时间复杂度是O(n)。
2、更新节点：如果不考虑查找节点的过程，链表的更新过程和数组一样简单，直接把旧数据替换成新数据即可。
3、插入节点：

• 尾部插入：最简单，把最后一个节点的next指向新插入的节点。
• 头部插入：
  分两个步骤：
  1.把新节点的next指针指向原先的头节点。
  2.把新节点变为链表的头节点。
• 中间插入：
  分两个步骤：
  1.把插入位置的前置节点的next指针指向插入的新节点。
  2.把插入的新节点的next指针指向前置节点的next指针指向的原先所指的节点。
  只要内存空间允许，能够插入的链表元素是无穷的，不用考虑扩容。

4、删除节点：
分三种情况：

• 尾部删除：最简单，把倒数第二个节点的next指针指向NULL。
• 头部删除：也很简单，把链表头节点设为原先头节点的next指针。
• 中间删除：把删除节点的前置节点的next指针，指向要删除元素的下一个节点即可。

链表的插入和删除的时间复杂度：如果不考虑插入、删除操作之前查找元素的过程，只考虑纯粹的插入、删除操作，时间复杂度为O(1)

2.2.3 数组 vs 链表

	查找	更新	插入	删除
数组	O(1)	O(1)	O(n)	O(n)
链表	O(n)	O(1)	O(1)	O(1)

数组能够利用下标快速定位元素，对于读操作多、写操作少的场景非常使用。而链表的有事在于能灵活的进行插入和删除操作，适用于读操作少、写操作多的场景。

2.3 栈和队列

2.3.1 物理结构和逻辑结构

数据存储的物理结构和逻辑结构：
物理结构：物质层面，实实在在的，看得见，摸得着。
顺序存储结构：数组
链式存储结构：链表
逻辑结构：精神层面，抽象的概念，依赖于物理结构而存在。
线性结构：顺序表、栈、队列
非线性结构：树、图

线性结构	非线性结构
顺序表、栈、队列	树、图

2.3.2 什么是栈

栈（stack）是一种线性数据结构，栈中的元素只能先进后出(FILO，First In Last Out)。最早进入的元素存放的位置叫作栈底（bottom），最后进入的元素存放的位置叫作栈顶（top）。用数组、链表均可以实现。例子：往圆筒放乒乓球。

2.3.3 栈的基本操作

入栈（push）：只能从栈顶放入元素，新元素成为新栈顶。
出栈（pop）：就是把元素从栈中弹出，只有栈顶元素才允许出栈，出栈元素的前一个元素成为新栈顶。
入栈、出栈的时间复杂度：O(1)，因为只会影响到最后一个元素。

2.3.4 什么是队列

队列：queue。一种线性数据结构，队列中的元素只能先进先出(FIFO，First In First Out)。队列的出口端叫作队头(front)，队列的入口端叫作队尾(rear)。用数组、链表均可以实现。例子：单行隧道。

2.3.5 队列的基本操作

入队（enqueue），只能在队尾的位置放入元素，新元素成为新队尾。
出队（dequeue），只能在队头的位置移出元素，出队元素的后一个元素成为新队头。
需要注意是是，队尾指针指向的位置永远空出一位，所以队列最大容量比数组长度小1。
额外：循环队列、双端队列、优先队列。
循环队列：
当队列为空时，front=rear
队列满时：（rear+1）% maxsiz=front，（队尾下标+1）% 数组长度=队头下标，少用一个存储空间，也就是数组的最后一个存数空间不用
入队、出队的时间复杂度：O(1)。

循环队列的相关条件和公式：
1.队空条件：rear==front
2.队满条件：(rear+1) %QueueSIze==front，其中QueueSize为循环队列的最大长度
3.计算队列长度：（rear-front+QueueSize）%QueueSize
4.入队：（rear+1）%QueueSize
5.出队：（front+1）%QueueSize

2.3.6 栈和队列的应用

1.栈的应用：面包屑导航，使用户在浏览页面时可以轻松的回溯到上一级或更上一级。因为栈的输入顺序和输出顺序相反。
2.队列的应用：队列的输出顺序和输入顺序相同，通常用于历史的“回放”，按照历史顺序，把历史重演一遍。例如：多线程中，争夺公平锁的等待队列，也就是按照访问顺序来决定线程在队列中的次序。还有爬虫实现网站抓取时，把待抓取的网站URL存入队列中，再按照队列的存入顺序依次抓取和解析。
3.双端队列（deque）：结合栈和队列的优点，既可以先进先出，也可以先进后出。对双端队列来说，从队头一端可以入队或出队，从队尾一端也可以入队或出队。
4.优先队列：遵循谁的优先级最高，谁先出队。不属于线性结构数据的范围，它是基于二叉堆来实现。

2.4 散列表

2.4.1 为什么需要散列表

散列表：也称哈希表（hash table）。是存储 key-value 映射的集合，时间复杂度接近于O(1)。本质上也是一个数组。例如：英语词典。

2.4.2 哈希函数

通过某种方式，把 key 和数组下标进行转换，这个中转站就叫哈希函数。

2.4.3 散列表的读写操作

1.写操作(put)：在散列表中插入新的键值对。
通过哈希函数，把 key 转换成数组下标。如果数组下标的位置没有元素，就放到该位置，如果该位置有值，这种情况为哈希冲突。
解决哈希冲突：开放寻址法和链表法。
开放寻址法：它的实现是在插入一个元素的时候，先通过哈希函数进行判断，若是发生哈希冲突，就以当前地址为基准，根据再寻址的方法（探查序列），去寻找下一个地址，若发生冲突再去寻找，直至找到一个为空的地址为止。所以这种方法又称为再散列法。
链表法：基本思路为：将所有具有相同哈希地址的而不同关键字的元素连接到同一个单链表中。对于冲突的哈希值，将其链入到该地址所对应的链表头中。

与开放定址法相比，拉链法有如下几个优点：
①拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
②由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
③开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
④在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。

2.读操作(get)：通过给定的key，在散列表中查找对应的value。
通过哈希函数，把 key 转换成数组下标，然后根据下标找value。

3.扩容（resize）
影响扩容的因素有两个：
- Capacity，hashmap的当前长度。
- LoadFactor，hashmap的负载因子，默认值为0.75f。
衡量hashmap需要进行扩容的条件：HashMap.Size >= Capacity * LoadFactor

- 散列表可以说是数组和链表的结合。

2.5 小结

• 什么是数组
  数组是由有限个相同类型的变量所组成的有序集合，它的物理存储方式是顺序存储，访问方式是随机访问。利用下标查找数组元素的时间复杂度是0(1)，中间插入、删除数组元素的时间复杂度是0(n)。
• 什么是链表
  链表是一种链式数据结构，由若干节点组成，每个节点包含指向下一节点的指针。链表的物理存储方式是随机存储，访问方式是顺序访问。查找链表节点的时间复杂度是O(n)，中间插入、删除节点的时间复杂度是0(1)。
• 什么是栈
  栈是一种线性逻辑结构，可以用数组实现，也可以用链表实现。栈包含入栈和出栈操作，遵循先入后出的原则(FILO)。
• 什么是队列
  队列也是一种线性逻辑结构，可以用数组实现，也可以用链表实现。队列包含人队和出队操作，遵循先入先出的原则(FIFO)。
• 什么是散列表
  散列表也叫哈希表，是存储KeyValue映射的集合。 对于某一个Key, 散列表可以在接近0(1)的时间内进行读写操作。散列表通过哈希函数实现Key和数组下标的转换，通过开放寻址法和链表法来解决哈希冲突。

参考：

1、https://blog.csdn.net/qq_34115899/article/details/87718847
2、https://www.cnblogs.com/EnSnail/p/11037209.html