数组（array）是一种线性数据结构，其将相同类型元素存储在连续的内存空间中。将元素在数组中的位置称为该元素的索引（index）
数组优缺点
数组常用操作
/* 1、初始化数组 */
// 存储在栈上
int arr[5];
int nums[5] { 1, 3, 2, 5, 4 };
// 存储在堆上（需要手动释放空间）
int* arr1 = new int[5];
int* nums1 = new int[5] { 1, 3, 2, 5, 4 };
/* 2、在数组的索引 index 处插入元素 num */
void insert(int *nums, int size, int num, int index) {
// 把索引 index 以及之后的所有元素向后移动一位
for (int i = size - 1; i > index; i--) {
nums[i] = nums[i - 1];
}
// 将 num 赋给 index 处元素
nums[index] = num;
}
/* 3、删除索引 index 处元素 */
void remove(int *nums, int size, int index) {
// 把索引 index 之后的所有元素向前移动一位
for (int i = index; i < size - 1; i++) {
nums[i] = nums[i + 1];
}
}
/* 4、在数组中查找指定元素 */
int find(int *nums, int size, int target) {
for (int i = 0; i < size; i++) {
if (nums[i] == target)
return i;
}
return -1;
}
内存空间是所有程序的公共资源，在一个复杂系统运行环境下，空闲的内存空间可能散落在各处。存储数组的内存空间必须是连续的，而当数组非常大时，内存可能无法提供如此大的连续空间，此时链表的灵活性优势就被体现
/* 链表节点结构体 */
struct ListNode {
int val; // 节点值
ListNode *next; // 指向下一节点的指针
ListNode(int x) : val(x), next(nullptr) {} // 构造函数
};
/* 1、初始化链表 1 -> 3 -> 2 -> 5 -> 4 */
// 初始化各个节点（通常将头节点当作链表的代称）
ListNode* n0 = new ListNode(1);
ListNode* n1 = new ListNode(3);
ListNode* n2 = new ListNode(2);
ListNode* n3 = new ListNode(5);
ListNode* n4 = new ListNode(4);
// 构建引用指向
n0->next = n1;
n1->next = n2;
n2->next = n3;
n3->next = n4;
/* 2、在链表的节点 n0 之后插入节点 P */
void insert(ListNode *n0, ListNode *P) {
ListNode *n1 = n0->next;
P->next = n1;
n0->next = P;
}
/* 3、删除链表的节点 n0 之后的首个节点 */
void remove(ListNode *n0) {
if (n0->next == nullptr)
return;
// n0 -> P -> n1
ListNode *P = n0->next;
ListNode *n1 = P->next;
n0->next = n1;
// 释放内存
delete P;
}
/* 4、在链表中查找值为 target 的首个节点 */
int find(ListNode *head, int target) {
int index = 0;
while (head != nullptr) {
if (head->val == target)
return index;
head = head->next;
index++;
}
return -1;
}
数组长度不可变导致实用性降低。在实际中，可能事先无法确定需要存储多少数据，这使数组长度的选择变得困难。若长度过小，需要在持续添加数据时频繁扩容数组；若长度过大，则会造成内存空间的浪费
/* 1、初始化列表 */
// 无初始值
vector<int> list1;
// 有初始值
vector<int> list = { 1, 3, 2, 5, 4 };
/* 2、访问元素 */
// 列表本质上是数组，因此可以在 O(1) 时间内访问和更新元素
int num = list[1]; // 访问索引 1 处的元素
/* 更新元素 */
list[1] = 0; // 将索引 1 处的元素更新为 0
/* 3、插入与删除元素 */
// 在列表尾部添加元素的时间复杂度为 O(1)
// 但插入和删除元素的效率仍与数组相同，时间复杂度为 O(n)
/* 清空列表 */
list.clear();
/* 尾部添加元素 */
list.push_back(1);
list.push_back(3);
list.push_back(2);
list.push_back(5);
list.push_back(4);
/* 中间插入元素 */
list.insert(list.begin() + 3, 6); // 在索引 3 处插入数字 6
/* 删除元素 */
list.erase(list.begin() + 3); // 删除索引 3 处的元素
/* 4、通过索引遍历列表 */
int count = 0;
for (int i = 0; i < list.size(); i++) {
count++;
}
/* 直接遍历列表元素 */
count = 0;
for (int n : list) {
count++;
}
/* 5、拼接两个列表 */
vector<int> list1 = { 6, 8, 7, 10, 9 };
// 将列表 list1 拼接到 list 之后
list.insert(list.end(), list1.begin(), list1.end());
/* 6、排序列表 */
sort(list.begin(), list.end()); // 排序后，列表元素从小到大排列
栈（stack）是一种遵循先入后出的逻辑的线性数据结构
如下图所示，把堆叠元素的顶部称为 “栈顶”，底部称为 “栈底”
/* 初始化栈 */
stack<int> stack;
/* 元素入栈 */
stack.push(1);
stack.push(3);
stack.push(2);
stack.push(5);
stack.push(4);
/* 访问栈顶元素 */
int top = stack.top();
/* 元素出栈 */
stack.pop(); // 无返回值
/* 获取栈的长度 */
int size = stack.size();
/* 判断是否为空 */
bool empty = stack.empty();
队列（queue）是一种遵循先入先出规则的线性数据结构。顾名思义，队列模拟了排队现象，即新来的人不断加入队列的尾部，而位于队列头部的人逐个离开
如下图所示，将队列的头部称为 “队首”，尾部称为 “队尾”，将把元素加入队尾的操作称为 “入队”，删除队首元素的操作称为 “出队”
队列常用操作
/* 初始化队列 */
queue<int> queue;
/* 元素入队 */
queue.push(1);
queue.push(3);
queue.push(2);
queue.push(5);
queue.push(4);
/* 访问队首元素 */
int front = queue.front();
/* 元素出队 */
queue.pop();
/* 获取队列的长度 */
int size = queue.size();
/* 判断队列是否为空 */
bool empty = queue.empty();
队列典型应用
哈希表（hash table），又称散列表，其通过建立键 key 与值 value 之间的映射，实现高效的元素查询
如下图所示，给定 n 个学生，每个学生都有 “姓名” 和 “学号” 两项数据。假如希望实现 “输入一个学号，返回对应的姓名” 的查询功能，则可以采用下图所示的哈希表来实现
除哈希表外，数组和链表也可以实现查询功能，它们的效率对比如下图所示
哈希表常用操作
/* 1、初始化哈希表 */
unordered_map<int, string> map;
/* 2、添加操作 */
// 在哈希表中添加键值对 (key, value)
map[12836] = "小哈";
map[15937] = "小啰";
map[16750] = "小算";
map[13276] = "小法";
map[10583] = "小鸭";
/* 3、查询操作 */
// 向哈希表输入键 key ，得到值 value
string name = map[15937];
/* 4、删除操作 */
// 在哈希表中删除键值对 (key, value)
map.erase(10583);
/* 5、遍历哈希表 */
// 遍历键值对 key->value
for (auto kv: map) {
cout << kv.first << " -> " << kv.second << endl;
}
// 单独遍历键 key
for (auto kv: map) {
cout << kv.first << endl;
}
// 单独遍历值 value
for (auto kv: map) {
cout << kv.second << endl;
}
index = hash(key) % capacity
本质上看，哈希函数的作用是将所有 key 构成的输入空间映射到数组所有索引构成的输出空间，而输入空间往往远大于输出空间。因此，理论上一定存在 “多个输入对应相同输出” 的情况
对于上述示例中的哈希函数，当输入的 key 后两位相同时，哈希函数的输出结果也相同。例如，查询学号为 12836 和 20336 的两个学生时，得到
12836 % 100 = 36
20336 % 100 = 36
如下图所示，两个学号指向了同一个姓名，这显然是不对的。将这种多个输入对应同一输出的情况称为哈希冲突（hash collision）
容易想到，哈希表容量越大，多个 key 被分配到同一个桶中的概率就越低，冲突就越少。因此，可以通过扩容哈希表来减少哈希冲突。如下图所示，扩容前键值对 (136, A) 和 (236, D) 发生冲突，扩容后冲突消失
类似于数组扩容，哈希表扩容需将所有键值对从原哈希表迁移至新哈希表，非常耗时。并且由于哈希表容量 capacity 改变，需要通过哈希函数来重新计算所有键值对的存储位置，这进一步提高了扩容过程的计算开销。为此，通常会预留足够大的哈希表容量，防止频繁扩容
- 在原始哈希表中，每个桶仅能存储一个键值对。链式地址（separate chaining）将单个元素转换为链表，将键值对作为链表节点，将所有发生冲突的键值对都存储在同一链表中
- 开放寻址（open addressing）不引入额外的数据结构，而是通过 “多次探测” 来处理哈希冲突，探测方式主要包括线性探测、平方探测、多次哈希等
index = hash(key) % capacity // 哈希函数
因篇幅问题不能全部显示，请点此查看更多更全内容