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)