数据结构 · 第〇章引言

数据结构目录阅读速览下载 Markdown

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 年的擂主在我们班。