数据结构基础（基于c++）

前言

参考资料：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+...+nreturn res;
}

常见时间复杂度例子：常见时间复杂度类型

常见空间复杂度例子：常见空间复杂度类型

1、常数阶：常量、变量、对象
2、线性阶：数组、链表、栈、队列
3、平方阶：矩阵、图
4、指数阶：二叉树（满二叉树）
5、对数阶：分治算法

递归函数一分为二时，时间复杂度为O(2ⁿ)， 例子：func(n-1)+func(n-2)

递归函数逐层减半时，时间复杂度为O(log₂n)，例子：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 字节作为最小寻址内存单元。

内存对齐

对齐规则：

1. 第一个成员在与结构体偏移量为0的地址处

2. 其他成员变量要对齐到某个数字（对齐数）的整数倍地址

   对齐数 = 编译器默认的对齐数与该成员大小的较小值

3. 结构体总大小为最大对齐数（每个成员都有一个对齐数）的整数倍

   到底为什么要内存对齐？_哔哩哔哩_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 -> n1ListNode *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. 数组与链表对比