第06章 数据的组织结构与算法 - 信息技术导论
课程：北京大学 0A006 信息技术导论（苏清元） 章节：第6章 数据的组织结构与算法 格式：PowerPoint 97-2003 二进制 PPT，LibreOffice 转 PDF 后 pdftotext 全文提取 页数：约 46 页，339 行文本
本章结构
- 6.1 数据结构的基本概念 — 起源、定义、操作
- 6.2 常用的几种数据结构 — 线性/树/图/集合四大类
- 6.3 算法 — 特性、评价标准、复杂度、表示方法
- 6.4 程序设计方法 — 程序性质、结构化设计、设计步骤
6.1 数据结构的基本概念
6.1.1 数值计算与非数值计算
数据的定义：描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。简言之，数据就是计算机化的信息。
数学模型两类：
- 定量模型：可用数值方程表示的计算模型
- 定性模型：非数值性的数据结构（表、树、图等）及其运算
| 类型 | 数据量 | 结构 | 运算 | 典型问题 |
|---|---|---|---|---|
| 数值计算 | 小 | 简单 | 算术/逻辑运算（整型、实型、布尔型） | 求解数学方程/方程组 |
| 非数值计算 | 大 | 复杂 | 表/树/图等结构操作 | 信息检索、关系分析、路径规划 |
核心洞见：非数值计算问题的关键不再是分析数学和计算方法，而是设计出合适的数据结构。
6.1.2 数据结构的起源
- 起源于程序设计的发展
- 早期计算机内存极小（8008 芯片仅 4K 内存），优化至关重要
- 逐渐将有效解决问题的数据表示和操作总结为独立学问：表、栈、队、树、图等
6.1.3 对数据结构的理解
两大维度：
- 逻辑数据结构：反映数据元素之间的逻辑关系
- 物理数据结构：反映数据在计算机内部的存储安排
两大核心问题：
- 表示：对象/实体及其关系在计算机中的表示（存储）
- 操作：对对象/实体进行处理、访问
一般定义：相互之间存在着一定关系的数据元素的集合，及定义在其上的操作（运算），称为数据结构。
6.1.4 数据元素的五种基本操作
- 插入：在指定位置增添新的数据元素
- 删除：删去指定的数据元素
- 查找：寻找某个特定要求的数据元素
- 排序：（线性结构中）按关键字值重新排列逻辑顺序
- 遍历：按某一次序访问每一个数据元素
6.1.5 数据结构能解决什么问题
三个经典示例：
- 例1：一元二次方程 → 线性表（a, b, c），方程系数的线性排列
- 例2：电话号码查询系统 → N元向量（名字, 号码），查找算法
- 例3：家族族谱 → 树形结构，层次关系表示
6.1.6 数据结构的图示
- 小圆圈 = 数据元素
- 连线 = 元素间关系
- 带箭头线段 = 方向性关系（如父子关系）
6.2 常用的几种数据结构
四大逻辑结构（按元素间关系分类）：
- 集合结构（元素间无特定关系）
- 线性结构（一对一）
- 树状结构（一对多）
- 图结构（多对多）
6.2.1 线性结构
1. 栈（Stack）
- 只能在某一端插入和删除的特殊线性表
- 栈顶（Top）：进行插入和删除的一端
- 栈底（Bottom）：另一端
- 进栈 Push：插入操作
- 退栈 Pop：删除操作
- 后进先出（LIFO: Last In, First Out）
2. 队列（Queue）
- 限定一端插入、另一端删除的特殊线性表
- 队尾：入队端（Rear）
- 队头：出队端（Front）
- 先进先出（FIFO: First In, First Out）
3. 链表（Linked List）
- 用任意存储单元依次存放线性表的数据元素
- 每个结点包含：数据域 + 指针域（指示后继/前驱结点地址）
- 单链表：每个结点一个指针域（指向后继）
- 双链表：每个结点两个指针域（一个前驱，一个后继）
约瑟夫环（Josephus Ring） — 单循环链表经典应用：
- n个人围成一圈，从第1人开始报数，数到第m人出列
- 用单循环链表：每个结点一个指针指向下一结点，最后一个指向第一个
- 出列操作：将m结点的前驱指针指向m结点的后继结点
6.2.3 树结构
1. 树的定义
树是由一个或多个结点组成的有限集合。
核心特点：
- 必有一个特定的根结点（ROOT）
- 根的每个分支称为子树（Subtree），子树也是一棵树
- 每个结点可以有多个直接后继
- 除根结点外，所有结点有且只有一个直接前驱
术语：
- 父结点（Parent）：前驱结点
- 子结点（Children）：后继结点
- 兄弟（Sibling）：同一父结点的子结点
- 叶子（Leaf）：不再有分支的结点
2. 二叉树
- 每个结点最多只有两棵子树（度≤2）
- 子树有左右之分（左子树、右子树）
- 左右次序重要，即使只有一棵子树也应分清楚
3. 二叉树的遍历
按一定规则和顺序访问所有结点，每个结点访问且仅访问一次。
三种基本遍历方式（以根的访问位置区分）：
| 遍历方式 | 顺序 | 示例结果（A为根，B/C为左右子，D/E为B的左右，F为C的右，G为D的左） |
|---|---|---|
| 先序遍历（根→左→右） | 访问根 → 遍历左子树 → 遍历右子树 | A → B → D → G → E → C → F |
| 中序遍历（左→根→右） | 遍历左子树 → 访问根 → 遍历右子树 | G → D → B → E → A → C → F |
| 后序遍历（左→右→根） | 遍历左子树 → 遍历右子树 → 访问根 | G → D → E → B → F → C → A |
6.2.4 图结构
定义：G = (V, E)，其中 V 为顶点（Vertices）的有限集合，E 为边（Edge）的有限集合。
典型应用：带权有向图表示交通运输网络
- 顶点 = 城市
- 边 = 交通路线
- 权值 = 距离 / 时间 / 费用
- 有向边反映方向差异（如上/下山，顺/逆水）
6.2.5 集合
- 数据元素之间不考虑关系（无前驱/后继之分）
- 各元素是”平等”的
- 共同关系：都属于同一个集合
6.3 算法
6.3.1 算法的五大特性
算法定义：对问题求解过程的描述，为解决一个或一类问题给出的一个确定的、有限长的操作序列。
| 特性 | 含义 |
|---|---|
| 有穷性 | 对任何合法输入，必须在执行有穷步之后结束，且每一步都在有穷时间内完成 |
| 确定性 | 每一条指令必须有确切含义，不会产生二义性；相同输入只能得出相同输出 |
| 可行性 | 描述的操作都可以通过已实现的基本运算执行有限次来实现 |
| 有输入 | 0个或多个输入，取自特定数据对象集合；可外部提供或算法内赋初值 |
| 有输出 | 一个或多个输出，输出与输入有特定关系 |
6.3.2 “好”算法的评价标准
四个层次：
- 正确性（可靠性/有效性）：
- 不含语法错误
- 对几组输入数据能得出满足规格的结果
- 对典型、苛刻、刁难性的输入能得出正确结果
- 对一切合法输入都能产生满足要求的结果
- 可读性（算法可读性摆在第一位）：
- 有助于理解
- 难懂的程序易隐藏错误，难以调试修改
- 健壮性：
- 对非法输入能做出恰当反映或处理
- 识别非法数据并处理，不产生误动作或瘫痪
- 高效率与低存储量：
- 时间代价（运行速度）
- 空间代价（存储器消耗）
6.3.3 算法复杂性
- 时间复杂性：算法运行需要的时间资源量
- 空间复杂性：算法运行需要的存储器空间资源量
- 是评价算法优劣的重要依据
6.3.4 算法的四种表示方法
| 表示方法 | 特点 | 优点 | 缺点 |
|---|---|---|---|
| 自然语言 | 汉语/英语等日常语言 | 通俗易懂 | 不严谨，易歧义 |
| 流程图 | ANSI 规定的图形符号 | 直观清晰 | 绘制麻烦，修改困难 |
| 伪代码 | 介于自然语言和计算机语言之间 | 书写方便、格式紧凑、易于理解、便于向程序过渡 | 无统一标准 |
| 程序设计语言 | 具体编程语言（C/Python等） | 精确、可直接执行 | 限制交流，易陷入细节而忽视算法本质 |
6.4 程序设计方法
6.4.1 计算机程序的性质
程序 = 数据结构 + 算法：
- 对象及对象之间关系 = 数据结构
- 加工规则 = 算法
五大性质：
- 目的性：有明确目的，运行时能完成赋予的功能
- 分步性：由一系列可执行的步骤组成
- 有序性：执行步骤有序，不可随意改变顺序
- 有限性：有限的指令序列
- 操作性：对某些对象进行操作，使其改变状态
6.4.2 程序设计与数据结构、算法的关系
数据结构是数据构造的逻辑表示形式，算法是处理问题的方法和步骤，最后问题的解由计算机程序给出。
—— 程序员在程序设计时应考虑的主要问题
6.4.3 结构化程序设计
1. 程序的控制结构
- 顺序、选择、循环三种基本结构构成最小完备集
- 顺序、选择、循环 + goto 能解决的问题，只用前三种也一定能解决
- 但不存在任何两种结构能解决所有问题
2. 结构化程序设计方法
- 自顶向下：先全局后局部，一层一层分解
- 模块化设计：将复杂问题分解为多个独立模块
6.4.4 程序设计的七步流程
- 分析问题：明确要求，列出已知量，确定求解范围和解的精度
- 建立数学模型：找出内在规律，建立数学模型
- 确定算法：根据数据结构确定算法（逻辑简单、存储量少、计算量小）
- 编写程序：自顶向下分解，相同子问题用子程序
- 调试运行
- 分析结果
- 写出程序文档：变量/函数说明、编程思路、流程图、运行结果讨论
关键概念速查表
| 概念 | 核心要点 |
|---|---|
| 数据结构 = 数据集合 + 操作集合 | 逻辑结构 vs 物理结构 |
| 四种逻辑结构 | 集合 / 线性 / 树 / 图 |
| 线性结构三杰 | 栈（LIFO） / 队列（FIFO） / 链表（指针连接） |
| 二叉树三遍历 | 先序（根左右）/ 中序（左根右）/ 后序（左右根） |
| 算法五特性 | 有穷 / 确定 / 可行 / 输入 / 输出 |
| 好算法四标准 | 正确 / 可读 / 健壮 / 高效低耗 |
| 算法四表示法 | 自然语言 / 流程图 / 伪代码 / 程序语言 |
| 程序三结构 | 顺序 / 选择 / 循环（最小完备集） |
| 程序设计七步 | 分析→建模→定算法→编程→调试→分析→写文档 |
章节关联
- 第01章-信息信息科学与信息技术-信息技术导论 — 第1章 信息本质与信息技术概述
- 第02章-计算与计算科学-信息技术导论 — 第2章 计算本质与计算学科
- 第05章-信息媒体的表示及数字化-信息技术导论 — 第5章 多媒体信息数字化
- 《算法导论》-Introduction to Algorithms-第3版-CLRS — 算法深度进阶
- 《数据结构与算法》-Rust实现-Shieber — Rust 语言的数据结构与算法
- 《结构化计算机组成》-Structured-Computer-Organization-第6版-Tanenbaum — 计算机组成视角的数据表示