线性结构
# 1. 线性结构
# 数组
数组是列表的实现方式之一,数组中的元素在内存中是连续存储的,且每个元素占用相同大小的内存。
数组的优点:
- 检索效率高
数组的缺点:
- 随机增删元素的效率较低
- 事先必须知道数组的长度
- 空间通常是有限制的
- 需要大块连续的内存块
# 链表
链表中每一个节点都包含此节点的数据和指向下一节点地址的指针。由于是通过指针进行下一个数据元素的查找和访问,使得链表的自由度更高。 这表现在对节点进行增加和删除时,只需要对上一节点的指针地址进行修改,而无需变动其它的节点。不过事物皆有两极,指针带来高自由度的同时,自然会牺牲数据查找的效率和多余空间的使用。
链表的优点:
- 随机增删元素效率较高(因为增删元素不涉及到大量元素的位移)
链表的缺点:
- 查询效率低,每一次查找某个元素的时候都需要从头节点开始往下遍历
# 队列
队列
是一种 FIFO
式的数据结构:第一个元素将被首先处理。有两个重要操作:入队和出队。我们可以使用带有两个指针的动态数组来实现队列。
我们可以使用广度优先搜索
(BFS)。
- 使用数组实现的叫
静态队列
- 使用链表实现的叫
动态队列
# 栈
栈
是一种 LIFO
式的数据结构:最后一个元素将被首先处理。有两个重要操作:push 和 pop。栈的实现非常简单,使用动态数组就足以实现栈。
当满足 LIFO
原则时,我们使用栈。深度优先搜索
(DFS)是栈的一个重要应用。
- 使用数组实现的叫
静态栈
- 使用链表实现的叫
动态栈
# 散列表
散列表(Hash table,也叫哈希表)是一种查找算法,与链表、树等算法不同的是,散列表算法在查找时不需要进行一系列和关键字(关键字是数据元素中某个数据项的值,用以标识一个数据元素)的比较操作。
散列表算法希望能尽量做到不经过任何比较,通过一次存取就能得到所查找的数据元素, 因而必须要在数据元素的存储位置和它的关键字(可用 key 表示)之间建立一个确定的对应关系,使每个关键字和散列表中一个唯一的存储位置相对应。因此在查找时,只要根据这个对应关系找到给定关键字在散列表中的位置即可。这种对应关系被称为散列函数(可用 h(key)表示)。
有两种不同类型的哈希表:哈希集合和哈希映射。
哈希集合
是集合
数据结构的实现之一,用于存储非重复值
。哈希映射
是映射
数据结构的实现之一,用于存储(key, value)
键值对。
用的构造散列函数的方法有:
(1)直接定址法: 取关键字或关键字的某个线性函数值为散列地址。
即:h(key) = key 或 h(key) = a * key + b,其中 a 和 b 为常数。
(2)数字分析法:找出数字的规律,尽可能利用这些数据来构造冲突几率较低的散列地址。
(3)平方取值法: 取关键字平方后的中间几位为散列地址。这是因为:平方后中间几位和关键字中每一位都相关,故不同关键字会以较高的概率产生不同的哈希地址
例:我们把英文字母在字母表中的位置序号作为该英文字母的内部编码。例如K的内部编码为11,E的内部编码为05,Y的内部编码为25,A的内部编码为01, B的内部编码为02。由此组成关键字“KEYA”的内部代码为11052501,同理我们可以得到关键字“KYAB”、“AKEY”、“BKEY”的内部编码。之后对关键字进行平方运算后,取出第7到第9位作为该关键字哈希地址,如下所示
关键字 | 内部编码 | 内部编码的平方值 | H(k)关键字的哈希地址 |
---|---|---|---|
KEYA | 11052501 | 122157778355001 | 778 |
KYAB | 11250102 | 126564795010404 | 795 |
AKEY | 01110525 | 001233265775625 | 265 |
BKEY | 02110525 | 004454315775625 | 315 |
(4)折叠法:将关键字分割成位数相同的几部分,然后取这几部分的叠加和作为散列地址。
例如:每一种西文图书都有一个国际标准图书编号,它是一个10位的十进制数字,若要以它作关键字建立一个哈希表,当馆藏书种类不到10,000时,可采用此法构造一个四位数的哈希函数。
(5)除留余数法:取关键字被某个不大于散列表表长 m 的数 p 除后所得的余数为散列地址,
即:h(key) = key MOD p p ≤ m
(6)随机数法:选择一个随机函数,取关键字的随机函数值为它的散列地址,
即:h(key) = random(key)