数据结构基础（基于c++）
文章目录
- 数据结构基础（基于c++）
- 前言
- 1. 递归、迭代、时间复杂度、空间复杂度
- 2. 数据结构
- 数组与链表
- 1. 数组
- 2. 链表
- 3. 动态数组
- 4. 数组与链表对比
前言
参考资料：Hello 算法 (hello-algo.com)
1. 递归、迭代、时间复杂度、空间复杂度
递归
使用迭代模拟递归：
/* 使用迭代模拟递归 */
int forLoopRecur(int n) {
// 使用一个显式的栈来模拟系统调用栈
stack<int> stack;
int res = 0;
// 递：递归调用
for (int i = n; i > 0; i--) {
// 通过“入栈操作”模拟“递”
stack.push(i);
}
// 归：返回结果
while (!stack.empty()) {
// 通过“出栈操作”模拟“归”
res += stack.top();
stack.pop();
}
// res = 1+2+3+...+n
return res;
}
常见时间复杂度例子：常见时间复杂度类型
常见空间复杂度例子：常见空间复杂度类型
1、常数阶：常量、变量、对象
2、线性阶：数组、链表、栈、队列
3、平方阶：矩阵、图
4、指数阶：二叉树（满二叉树）
5、对数阶：分治算法
递归函数一分为二时，时间复杂度为O(2n)， 例子：func(n-1)+func(n-2)
递归函数逐层减半时，时间复杂度为O(log2n)，例子：func(n/2)
主流排序算法的时间复杂度通常为 𝑂(𝑛log𝑛) ，例如快速排序、归并排序、堆排序等。
笔记：
// 使用系统时间生成随机种子
unsigned seed = chrono::system_clock::now().time_since_epoch().count();
// 随机打乱数组元素
shuffle(nums.begin(), nums.end(), default_random_engine(seed));
//to_string()函数
map[i] = to_string(i);
2. 数据结构
64位计算机数据类型大小（Java）：
- C 和 C++ 未明确规定基本数据类型的大小，而因实现和平台各异。上表遵循 LP64 数据模型，其用于包括 Linux 和 macOS 在内的 Unix 64 位操作系统。
- 字符
char的大小在 C 和 C++ 中为 1 字节，在大多数编程语言中取决于特定的字符编码方法，详见“字符编码”章节。 - 即使表示布尔量仅需 1 位（0 或 1），它在内存中通常也存储为 1 字节。这是因为现代计算机 CPU 通常将 1 字节作为最小寻址内存单元。
内存对齐
对齐规则：
第一个成员在与结构体偏移量为0的地址处
其他成员变量要对齐到某个数字（对齐数）的整数倍地址
对齐数 = 编译器默认的对齐数与该成员大小的较小值
结构体总大小为最大对齐数（每个成员都有一个对齐数）的整数倍
到底为什么要内存对齐？_哔哩哔哩_bilibili
（含字幕）C++ 让你不再害怕内存和指针 其一_哔哩哔哩_bilibili
【C++面试100问】第二十九问：请详细讲讲C和C++中的内存分配方式_哔哩哔哩_bilibili
4.4 内存与缓存 * - Hello 算法 (hello-algo.com)
数字是以“补码”的形式存储在计算机中的。
计算机内部的硬件电路主要是基于加法运算设计的。
问题：哈希冲突、红黑树
数组与链表
1. 数组
索引本质上是内存地址的偏移量。
访问：在数组中访问元素非常高效，我们可以在 𝑂(1) 时间内随机访问数组中的任意一个元素。（随机访问）
插入：如果想在数组中间插入一个元素，则需要将该元素之后的所有元素都向后移动一位，之后再把元素赋值给该索引。
/* 在数组的索引 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;
}
删除：若想删除索引 𝑖 处的元素，则需要把索引 𝑖 之后的元素都向前移动一位。删除元素完成后，原先末尾的元素变得“无意义”了，所以我们无须特意去修改它。
/* 删除索引 index 处的元素 */
void remove(int *nums, int size, int index) {
// 把索引 index 之后的所有元素向前移动一位
for (int i = index; i < size - 1; i++) {
nums[i] = nums[i + 1];
}
}
数组的优缺点
数组存储在连续的内存空间内，且元素类型相同。这种做法包含丰富的先验信息，系统可以利用这些信息来优化数据结构的操作效率。
- 空间效率高：数组为数据分配了连续的内存块，无须额外的结构开销。
- 支持随机访问：数组允许在 𝑂(1) 时间内访问任何元素。
- 缓存局部性：当访问数组元素时，计算机不仅会加载它，还会缓存其周围的其他数据，从而借助高速缓存来提升后续操作的执行速度。
连续空间存储是一把双刃剑，其存在以下局限性。
- 插入与删除效率低：当数组中元素较多时，插入与删除操作需要移动大量的元素。
- 长度不可变：数组在初始化后长度就固定了，扩容数组需要将所有数据复制到新数组，开销很大。
- 空间浪费：如果数组分配的大小超过实际所需，那么多余的空间就被浪费了。
应用：数组典型应用
2. 链表
链表节点 ListNode 除了包含值，还需额外保存一个引用（指针）。因此在相同数据量下，链表比数组占用更多的内存空间。
通常将头节点当作链表的代称
插入：假设我们想在相邻的两个节点 n0 和 n1 之间插入一个新节点 P ，则只需改变两个节点引用（指针）即可，时间复杂度为 𝑂(1) 。
/* 在链表的节点 n0 之后插入节点 P */
void insert(ListNode *n0, ListNode *P) {
ListNode *n1 = n0->next;
P->next = n1;
n0->next = P;
}
删除：在链表中删除节点也非常方便，只需改变一个节点的引用（指针）即可。
/* 删除链表的节点 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;
}
访问：
/* 访问链表中索引为 index 的节点 */
ListNode *access(ListNode *head, int index) {
for (int i = 0; i < index; i++) {
if (head == nullptr)
return nullptr;
head = head->next;
}
return head;
}
查找：
/* 在链表中查找值为 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;
}
应用：链表经典应用
3. 动态数组
vector
访问：用索引进行访问
插入与删除：
/* 清空列表 */
nums.clear();
/* 在尾部添加元素，时间复杂度O(1) */
nums.push_back(1);
nums.push_back(3);
nums.push_back(2);
nums.push_back(5);
nums.push_back(4);
/* 在中间插入元素，时间复杂度O(n) */
nums.insert(nums.begin() + 3, 6); // 在索引 3 处插入数字 6,insert是在前一个位置插入元素
/* 删除元素，时间复杂度O(n) */
nums.erase(nums.begin() + 3); // 删除索引 3 处的元素
拼接：
/* 拼接两个列表 */
vector<int> nums1 = { 6, 8, 7, 10, 9 };
// 将列表 nums1 拼接到 nums 之后
nums.insert(nums.end(), nums1.begin(), nums1.end());
排序：
/* 排序列表 */
sort(nums.begin(), nums.end()); // 排序后，列表元素从小到大排列
用数组实现动态数组：用数组实现动态数组
4. 数组与链表对比
