数据结构笔记
数据结构笔记
本文档是对2026年3月2日及之后数据结构课程相关的总结，仅供参考。
部分内容借助大语言模型丰富和完善。
绪论
**我们为什么要学习数据结构呢？**为了提高程序运行的速度。
1. 程序提速的核心方向 (Speedup)
程序性能的提升主要依赖于“硬件”和“软件”两个维度的优化：
1.1 硬件层面 (Hardware)
硬件升级是提升速度的物理基础：
CPU：主要关注核心数 (Cores) 和运行频率 (Freq.)，这里说的是主频。 内存：RAM 的大小和速度直接影响程序运行。 存储设备 (Storage)：HDD -> SSD（将机械硬盘替换为固态硬盘，可以大幅提高硬盘的读写和运行速度）。
1.2 软件层面 (Software) 与加速方法 (How to accelerate)
在硬件既定的情况下，软件层面的加速是核心，即在有一个良好的操作系统的管理下，合理运用数据结构 (Data Structure)。
搜索与查找优化：
地址查找 (Address find)：优化数据寻址效率。 空间与容量：权衡硬件能力 (Hardware capacity) 与软件能力 (Software capacity)。 搜索策略：通过缩小搜索空间 (Search space)、建立内容列表 (Content list) 或目录 (TOC) 来大幅提高检索效率。
2. 数据结构的基础与分类
数据结构主要研究数据的组织方式以及相应的操作逻辑：
2.1 结构类型分析
逻辑结构 (Logical Structure) vs. 物理结构 (Physical Structure)：区分数据在人脑逻辑中的形态与在计算机内部实际存储的形态。
存储介质差异：数据在**内存 (RAM)与磁盘 (Disk)**中的读写机制存在本质区别。
排列决定搜索：数据的排列方式 (Arranged) 直接决定了后续的搜索方式 (way of search)。
2.2 线性结构 (Linear)
数据元素之间存在一对一的线性关系：
基础线性表：数组 与 链表。
核心在于理解它们不同的存取规则（例如数组支持随机存取，而链表适合顺序存取）。
受限线性表 (Rules)：基于基础线性表，加上特定的操作规则限制，衍生出了：
栈 (Stack)：后进先出 (LIFO)。
队列 (Queue)：先进先出 (FIFO)。
3. 开发环境与工具配置 (Environment & Tools)
为后续的 C++ 编程实践做准备，了解底层的工具链机制：
3.1 编辑器与编译器的关系
机制：日常使用的集成开发环境 (IDE) 本质上是调用底层的编译器 (IDE employ a compiler) 来将代码转化为可执行程序的。 代码编写：代码的编写可以在 VS Code、其他 IDE 甚至是纯文本编辑器 (Text Editor) 中完成。
3.2 编译器工具链 (Compiler tools)
不同平台有不同的 C++ 开发工具：
Linux 平台：常用 MinGW 等工具链（虽然 MinGW 常用于 Windows 上模拟 Linux 编译环境，但笔记中将其与 Linux 关联，代表 GCC/G++ 工具系）。 Windows 平台：通常使用微软的 Visual Studio (VS)。
系统架构：开发时需明确目标环境是 x86 架构下的 32 位 (32 bit) 还是 64 位 (64 bit) 系统。
3.3 后续作业与提交要求 (Homework & Submission)
统一环境：后续的数据结构实践要求统一在 VS Code 集成开发环境 (IDE) 中配置 MinGW 编译器进行开发。 提交格式：最终提交作业时，需将包含代码声明的头文件 (.h) 和包含具体实现的源文件 (.cpp) 一同打包成压缩包上交。
备注：关于作业的具体细节和详细要求，将在后续课程中另行提出。