基本数据结构

发表于 | 分类于

数组

数组将元素以一种不规则的顺序进行排列，在内存中是连续存放。数据可以通过索引值直接取得。

数组只需记录头部的第一个数据位置，然后累加空间位置即可。

数组的操作

新增

  1. 在 数组最后新增一个元素， 对原数据无影响。 插入时间复杂度 O(1)
  2. 在 数组中间某一个位置新增一个元素，会对插入后面的数据产生影响， 后面的元素位置要依次后挪一个位置 。 插入时间复杂度 O(n)

删除
1 .在 数组最后删除一个元素， 对原数据无影响。 删除时间复杂度 O(1)

  1. 在 数组中间某一个位置删除一个元素，会对删除后面的数据产生影响， 后面的元素位置要依次前挪一个位置 。 删除时间复杂度 O(n)

查找

  1. 基于位置，以索引查找 时间复杂度 O(1)
  2. 查找具体数值，eg： 查找元素为 9 是否出现过。 需要遍历 时间复杂度 O(n)

虽然 很多操作被封装， 但时间复杂度不会改变 （因为python 封装的 函数底层可能是 c，所以一般执行效率会高一点）

数组的长度是固定的，申请时就已在内存空间开辟了若干空间，扩容一般 有一定规则扩容

链表可以 用指针充分利用内存空间。数组想从分利用空间只能选择顺序存储，而且不插入删除数据。

线性表

线性表： n 个数据元素的有序排列，最常用的就是 链式表达

链表：存储的数据元素也叫结点，一个结点存储的就是一条数据记录。一般头指针指向第一个结点，最后一个结点的指针因为没有下一个节点，所以是个空指针

结点的结构包括两个部分:

  1. 具体的数据值
  2. 指向下一个结点的指针

单链表: 只能由上一个结点的 指针 指向下一个结点，反过来不行

循环链表: 将单链表的最后一个元素的指针指向第一个元素

双向链表： 新增一个结点的指针，除了有指向下一个元素的指针，也有指向上一个元素的指针

双向循环链表： 双向链表和循环链表 结合，将双向链表最后一个元素的指针指向第一个元素，第一个指针也指向最后一个元素

链表的增删查, p 为 当前结点，b 为下一个结点

  1. 新增：s 为待插入的结点， 只需要将s 的指针 指向 p的目标b ，p的指针指向s

    1
    2
    s.next = p.next(即指向 b)
    p.next = s （即指向 b）

  2. 删除： 只需要 将 p 的指针指向 下下个结点 （即b 指向的结点）

    1
    p.next = p.next.next

  3. 查找： 1.按位置序号来查找 2.按具体的数值查找

查询第 n 个元素： 从头开始，遍历到第 n 个元素

查询值为 x: 从头开始,判断结点的值是否为 x，直到把所有节点遍历完

链表优缺点：

优点: 新增和删除（但也会伴随着查找）

缺点：查找

链表: 数据元素个数不确定, 需要经常添加删除

数组: 数据元素个数确定，删除插入操作不多。 需要以位置查找

栈

栈是一种特殊的线性表，不同的地方体现在增和删操作。栈的数据结点必须后进先出

后进: 栈的数据新增只能在最后一个结点进行

先出: 栈的数据删除也只能在最后一个节点进行

栈降低了操作的灵活性，但处理一端的新增和删除数据的问题效率更高

表尾用来输入数据，通常叫做栈顶 （top）, 表头就是栈底（bottom）

栈的基本操作

  1. 新增：入栈 push

  2. 删除：出栈 pop

栈分为： 顺序栈，链栈

顺序栈：借助数组实现

链栈： 借助链表实现

顺序栈

一般会把数组的首元素存在栈底，最后一个元素放在栈顶，定义一个 top 指针来指示栈顶元素在 数组中的位置。只有一个元素，top =0。 top =-1 表示空栈。如果定义了最大容量 StackSize，则 top 必须小于 StackSize。

  1. 新增： 将元素放在栈顶，top +1
  2. 删除： 删除元素， top - 1
  3. 查找： 类似于线性表

    链栈

栈顶放在单链表的头部，不需要头部指针。需要增加指向 栈顶的 top 指针。

  1. 新增： 新结点的指针指向 原栈顶，top指向新的结点
  2. 删除： 将 top 指针指向 顶元素的 next 指针
  3. 查找： 类似于线性表

栈： 限制版的线性表，先进后出，新增删除时间复杂度 O(1)，而查找 时间复杂度 O(n)

队列

队列也是一种特殊的线性表，不同的地方体现在增和删操作。队列的数据结点先进先出

先进: 队列的数据新增只能在最后一个结点进行

先出: 队列的数据删除只能在第一个节点进行

队列分为： 顺序队列，链队列

顺序队列：借助数组实现

链队列： 借助链表实现

一个队列 依赖队头（front） 和 队尾 （rear） 两个指针进行唯一确定

顺序队列

实现一个有 k 个元素的顺序队列，需要建立一个长度 比 k 大的数组，以便把所有的队列元素存储在数组中。

  1. 新增： 利用 rear 指针在队尾新增一个元素 O(1)
  2. 删除： 利用 front 指针删除 下标为 0 的元素，然后队列中所有元素都向前移动一个位置。 O(n) 时间复杂度高
  3. 删除： 通过移动指针的方式删除数据，不移动剩余元素。（会产生数组越界，需要开辟足够大的内存空间保证不会越界）

越界：

循环队列

上面的两种删除方法都不太好，可以通过循环队列 解决数据越界问题
待补充

链队列

单链表增加 front 和 rear 指针。 front 指针头结点。头结点不存储数据，只用来标识辅助。

  1. 新增： 将新结点 s 设置为队尾结点，然后 rear 指向 s.

  2. 删除： 找到头结点的后继，删除这个后继结点（头结点不存储数据），删除最后一个有效数据后，让rear 也指向头结点。

头结点存在意义： 防止 最后一个有效数据结点删除后， front 和 rear 指针变成野指针。

总结

  1. 循环队列： 可以确定队列长度的最大值

  2. 链式队列： 无法确定队列长度

队列类似于 排队买票场景，可以使用队列来处理相似问题

哈希

哈希表的设计采用了函数映射的思想，将记录的存储位置与记录的关键字关联起来。这样的设计方式，能够快速定位到想要查找的记录，而且不需要与表中存在的记录的关键字比较后再来进行查找

1
2
3
4
5
6
7
张一：155555555

张二：166666666

张三：177777777

张四：188888888

借助哈希表的思路，构建姓名到地址的映射函数“地址 = f (姓名)”。这样，我们就可以通过这个函数直接计算出”张四“的存储位置，在 O(1) 时间复杂度内就可以完成数据的查找

假如对上面的例子采用的 Hash 函数为，姓名的每个字的拼音开头大写字母的 ASCII 码之和。即：

1
2
3
4
5
6
7
address (张一) = ASCII (Z) + ASCII (Y) = 90 + 89 = 179；

address (张二) = ASCII (Z) + ASCII (E) = 90 + 69 = 159；

address (张三) = ASCII (Z) + ASCII (S) = 90 + 83 = 173；

address (张四) = ASCII (Z) + ASCII (S) = 90 + 83 = 173；

我们发现这个哈希函数存在一个非常致命的问题，那就是 f ( 张三) 和 f (张四) 都是 173。这种现象称作哈希冲突，是需要在设计哈希函数时进行规避的

从本质上来看，哈希冲突只能尽可能减少，不能完全避免。这是因为，输入数据的关键字是个开放集合。只要输入的数据量够多、分布够广，就完全有可能发生冲突的情况。因此，哈希表需要设计合理的哈希函数，并且对冲突有一套处理机制。

哈希表查找的细节过程是：对于给定的 key，通过哈希函数计算哈希地址 H (key)。

如果哈希地址对应的值为空，则查找不成功。

反之，则查找成功。

虽然哈希表查找的细节过程还比较麻烦，但因为一些高级语言的黑盒化处理，开发者并不需要实际去开发底层代码，只要调用相关的函数就可以了。

哈希表在我们平时的数据处理操作中有着很多独特的优点，不论哈希表中有多少数据，查找、插入、删除只需要接近常量的时间，即 O(1）的时间级

哈希表中的数据是没有顺序概念的，所以不能以一种固定的方式（比如从小到大）来遍历其中的元素。在数据处理顺序敏感的问题时，选择哈希表并不是个好的处理方法。同时，哈希表中的 key 是不允许重复的，在重复性非常高的数据中，哈希表也不是个好的选择