《我的第一本算法书》|数据结构

• 数据结构

数据结构：数据存储于内存时，决定了数据的顺序和位置关系的

• 电话号码簿的类比

顺序添加：好添加，不好查找

按照姓名拼音记录：不好添加，好查找

优点结合：使用不同的表记录不同的首字母

• 链表

每个数据都有一指针到下一内存地址

数据分散于内存中，无需连续空间内

需要顺序进行访问

添加数据时改变位置前后的指针即可，删除同理

查找O(n) 添加/删除O(1)时间

循环链表：保存数量固定的最新数据时

双向链表：指针空间增加，添加和删除时改变指针变多

• 数组

呈现线性排列的一种数据结构

存储于连续空间内

可通过下标算出数据的内存地址，称为随机访问

添加数据在末尾增加存储空间，数据一个个后移，再加入目标数据，删除同理

访问数据为随机访问O(1) 添加/删除数据O(n)

链表与数组的对比

• 栈

一种呈现线性排列的数据结构，只能访问最新添加的数据（浏览器的返回上一步等需要访问最新数据）

入栈push

出栈pop

像栈这种最后添加的数据最先被取出，即“后进先出”的结构，我们称为Last In First Out，简称LIFO。

• 队列

队列中的数据呈线性排列，添加和处理数据在两端进行；“先来的数据先处理”是一种很常见的思路，所以队列的应用范围非常广泛

入队

出队：从最下面取出

像队列这种最先进去的数据最先被取来，即“先进先出”的结构，我们称为First In First Out，简称FIFO。

• 哈希表

哈希表存储的是由键（key）和值（value）组成的数据；一般来说，我们可以把键当成数据的标识符，把值当成数据的内容。

查找时候进行线性查找

使用哈希函数计算字符串的键（哈希值），表model取余，插入其中

使用链表在已有数据后继续存储

查找时候先找哪个箱子，再查找链表

在哈希表中，我们可以利用哈希函数快速访问到数组中的目标数据。如果发生哈希冲突，就使用链表进行存储，进行灵活应对

• 堆

堆是一种图的树形结构，被用于实现“优先队列”（priority queues）。需要频繁地从管理的数据中取出最小值使用

优先队列是一种数据结构，可以自由添加数据，但取出数据时要从最小值开始按顺序取出。

在堆的树形结构中，各个顶点被称为“结点”（node），数据就存储在这些结点中

子结点必定大于父结点：最小值被存储在顶端的根结点中

添加新的数字到最下一行靠左位置，再与上面节点置换

取出最上面的数据

将最后的数据提到最前面，然后进行置换

取出最小值的时间复杂度都为O(1)，重构树的时间复杂度便为O（logn）

• 二叉查找树

二叉查找树（又叫作二叉搜索树或二叉排序树）是一种数据结构，采用了图的树形结构

每一个结点的值大于左树上任意一个结点的值，小于右树上任意一个结点的值

最小结点由顶端向左下找，最大结点由顶端向右下找

添加数字，大的左移，小的右移，一路对比到最下面

删除结点时，在左树中寻找最大结点进行替换即可

查找结点时候，小于该结点的值则往左移，大于则往右移进行查找

二叉查找树中一个结点最多有两个子结点，但我们可以把子结点数扩展为m（m为预先设定好的常数）。种子结点数可以自由设定，并且形状均衡的树便是B树