# 数据结构 · 第〇章 引言 > Arietids Learn · 个人课程复习笔记 > 在线阅读：https://learn.arietids.net/courses/data-structures/chapter-00/ ## 0 课程基本信息 - 课程贯穿性公式（多页教师备注反复出现）：**程序 = 数据结构 + 算法**。 ## 2 什么是数据结构 ### 2.1 定义（课件引用的两个 AI 模型定义） - Gemini 3.1 Pro 定义要点：数据结构（Data Structure）是计算机中**存储、组织**和**管理**数据的方式；其核心目的不只是把数据存起来，更是为了能高效地**访问**和**修改**这些数据。 - DeepSeek 3.2 定义要点：数据结构是计算机中存储、组织和管理数据的方式，它定义了数据元素之间的**关系**以及对这些数据可以执行的**操作**；可理解为让计算机高效处理和访问数据的「容器」或「组织形式」。 ### 2.2 引入实例：图书馆 - 问题设定：假设你是图书馆管理员，职责有两件事——操作 1「新的书怎么放到书架上」、操作 2「怎么找到想要的那本书」。 - 优先级提示（教师备注）：图书馆是要服务于读者的，因此「如何找书」的优先级更高。 | 方案 | 操作 1：放书 | 操作 2：找书 | |---|---|---| | ① 随便放 | 从书架第一个位置向后放；不管是什么书，一次操作就能完成 | 从书架第一个位置向最后挨个找；最倒霉的情况要把所有书从前向后全找一遍 | | ② 按类别放（不同类别放不同书架） | 先判断这本书属于什么类别，再放到所属类别的书架上 | 先找到这本书所属的类别，再在该类别书架上从前到后查找 | | ③ 在分类基础上按顺序排列放 | 在分类放的基础上，按书名字典序把书从 A 到 Z 放 | 先找到所属类别，再按字典顺序查找——二分搜索 | ### 2.3 二分搜索演示（方案三找书） - 设定：书架位置编号 0–25，依次放 A–Z 共 26 本书；目标是以「P」开头的那本书。 - 第一步：从中间的字母开始找，(0+25)/2 = 12.5，取整数（向下取整）得 12，对应 M；M 在 P 的前面，所以 P 仅会在 [13, 25] 出现。 - 第二步：(13+25)/2 = 19，对应 T；T 在 P 的后面，所以 P 仅会在 [13, 18] 出现。 - 第三步：(13+18)/2 = 15.5，取整（向下取整）得到 15，对应 P，成功找到。 - 图示信息：每一步箭头指向当前中点字母（M→T→P），已被排除的区间在图中置灰，直观体现候选区间逐步缩小。 - 方法要点：每步取当前候选区间的中点与目标比较，依据先后关系舍弃一半区间，重复直到命中目标。 ### 2.4 实例总结 - 三种存放方式：① 随便放，② 分组放，③ 分组排序放。 - 书的不同存放方式，对应的「放书」和「找书」的复杂度是截然不同的。 - 解决问题（放书–找书）的方法效率，与数据的组织方式（书的存放方式）是紧密相关的。 ### 2.5 类比映射：图书馆 → 数据结构概念 - 书 ≈ 数据元素。 - 放书 ≈ 对于数据的存储操作（算法）。 - 两本书字典序的先后顺序 ≈ 数据与数据之间的关系（数据结构）。 - 取书 ≈ 对于数据的访问操作（算法）。 ### 2.6 延伸：数据结构 vs. 数据库 - 延伸话题：数据结构与数据库（两门课程）的区别，以内嵌视频形式讲解。 - 引导思考（教师备注）：你电脑的文件双击时，计算机内部发生了什么？ ## 3 为什么要学数据结构 ### 3.1 理由一：让你写的代码「快百倍」的秘诀 - 例子：要在 100 万条微博中定位某个人的发言——「青铜写法」用普通数组逐条查找，最坏要查 100 万次（电脑要累死）；「王者写法」用哈希表按用户键定位，通常期望常数次找到入口（若需输出多条结果，输出成本仍与结果数相关）。 - 结论：数据结构选得好，代码效率可显著提升；在本例中，数组逐条查找为 $O(n)$，哈希表按键查找通常为期望 $O(1)$。 ### 3.2 理由二：解决现实问题的「必备工具」 - 用微信时：表情包搜索用**字典树**实现输入联想。 - 刷 B 站时：推荐算法用**图结构**分析你对 UP 主的喜好。 - 打王者时：敌人位置追踪用**四叉树**快速检测碰撞。 - 结论：所有你熟悉的应用，本质都是数据结构的花式组合。 ### 3.3 理由三：计算机学科从小考到大的必修课 - 大一时学、做作业时用、保研时考、找工作时考、做程序员后用、当老师后教——学好数据结构，受益终身。 ## 4 课程目录 - 本课程五大主题：链、树、图、查找、排序。 - 「链」对应线性表（教师备注）。 - 配套平台课程图中的组织方式：数据组织方式——链（Chain）、树（Tree）、图（Graph）；数据处理方式——查找（Search）、排序（Sort）；二者构成了程序设计中最常用的数据组织和处理方式。 ## 5 课程目标 ### 5.1 基础目标 - 了解数据结构基本概念，掌握数据结构的逻辑结构、存储结构、基本操作、基本操作实现、典型应用研究脉络和算法性能的度量、计算方法。 - 掌握每种数据结构的结构特征、存储方式、操作算法设计及各类算法的性能分析和优化、典型应用。 - 熟练应用 C++ 高级语言进行各种结构的存储和基本操作编程实现，通过面向对象中的「类」建造各种数据结构工具；在理解概念、理论基础之上培养和提高实际动手编程能力。 - 能将生活实践中遇到的各类问题，根据数据元素间关系的类别，抽象为某种数据结构，并利用对应的数据结构工具解决实际面对的问题。 ### 5.2 进阶目标 - 具备协同设计、高效实现、创新优化数据存储与处理方案的能力，以应对国家级科技竞赛中的真实难题。 - 配图为 2025 年度中国青年科技创新「揭榜挂帅」擂台赛（人工智能领域）的参赛照片（横幅显示上海交通大学人工智能学院 / School of Artificial Intelligence）；教师备注寄语：希望 2026 年的擂主在我们班。