### 本章学习目标
- 数据结构的定义
- 逻辑结构, 存储结构, 运算的相互关系
- 各种逻辑结构之间的差别
- 各种存储结构之间的差别
- 数据结构和数据类型的区别和联系
- 抽象数据类型的概念和描述方式
- 算法的定义和特性
- 算法的时间复杂度和空间复杂度分析
### 用计算机解决问题
- 分析问题, 确定数据模型
- 设计相应的算法
- 编写和调试程序, 直到得出正确的结果
### 用计算机解决问题
- 分析问题, 提取操作的对象
- 找出操作对象之间的关系
- 用数学语言加以描述
### 用计算机解决问题
- 完成对现实世界问题的抽象
- 了解待处理对象的特性及其之间的关系
- 将现实世界的问题转化为**数学问题**
#### Abstract - Picasso
### 为什么是数学
- 因为数学有严密的符号表述体系
- 有严密确定的推理系统
#### Mathematics
### 有穷观点的能行方法
- 由大卫·希尔伯特 (David Hilbert) 提出
- 由有限数量的明确有限指令构成
- 指令执行在有限步骤后终止
- 指令每次执行都总能得到唯一结果
- 原则上可以由人单独采用纸笔完成
- 每条指令可以机械地被精确执行
#### David Hilbert
### 图灵机 (Turing Machine)
- 一条无限长的纸带
- 一个读写头
- 一套控制规则数量有限的命令表
- 一个状态寄存器
#### Alan Turing
#### Turing Machine
#### Turing Machine Model
### 人类面临的问题
- 是什么? 通过树状分类解决
- 为什么? 通过推理规则解决
- 怎么做? 通过**特定流程**解决
#### What
#### Why
#### How
### 程序设计的实质
- 对确定的问题选择一种好的**数据结构**
- 设计一种好的**算法**
- 数据结构即一组拥有特定关系的数据
- 算法即一个有限长的操作序列
#### Data Structure
#### Algorithm - Bubble Sort
### 计算机解决问题的基本流程
- 分析问题, 确定数据模型
- 设计相应算法
- 编写, 运行, 调试程序
- 得到正确的结果
### 数据 (Data)
- 是描述客观事物的数和字符的集合
- 计算机操作的对象的总称
- 计算机所处理信息的某种特定的符号表示形式
#### Data
### 数据元素 (Data Element)
- 数据的基本单位
- 有时数据元素也称为元素, 结点, 顶点或记录
- 可以由若干个数据项组成
### 数据项 (Data Item)
- 具有独立含义的数据最小单位
- 也称为字段或域
### 数据对象 (Data Object)
- 性质相同的数据元素的集合
- 数据的一个子集
- 本课程中讨论的数据通常是指数据对象
### 数据结构 (Data Structure)
- 所有数据元素以及数据元素之间的关系
- 带结构的数据元素的集合
### 数据结构的组成
- 逻辑结构 (Logical Structure)
- 数据的存储结构 (Storage Structure)
- 运算 (Operation)
### 逻辑结构
- 从逻辑关系上描述数据
- 问题的抽象模型
- 与计算机无关
### 存储结构
- 在计算机中的实现
- 数据元素之间的关系在计算机中的表示
- 依赖于计算机语言
### 运算
- 对数据的基本操作
- 定义在逻辑结构上
- 依赖于存储结构
### 数据结构
- 描述现实世界实体的数学模型 (通常为非数值计算) 及其之上的运算在计算机中如何表示和实现
### 逻辑结构的表示
- 图表
- 二元组
### 图表
- 用表格或者图形直接描述数据的逻辑关系
- 表格
- 线性表
- 树
- 图
### 二元组
- $B = (D, R)$
- $B$ 是一种数据逻辑结构
- $D$ 是数据元素的集合
- $R$ 是$D$上二元关系的集合
- $D = \lbrace d\_i, | 0 \leq i \leq n-1, n \geq 0 \rbrace $
- $R = \lbrace r\_j, | 1 \leq j \leq m, m \geq 0 \rbrace $
### 逻辑结构中的数据
- 关系 $r\_j (1 \leq j \leq m)$ 是 $D$ 上序偶 (Ordered Pairs) 的集合
- 对 $r\_j$ 中的任意序偶 $ <x, y> (x, y \in D) $
- $x$ 叫做第一元素或 $y$ 的**前驱元素** (Predecessor)
- $y$ 叫做第二元素或 $x$ 的**后继元素** (Successor)
- 若某元素没有前驱, 则称为**开始元素** (Head)
- 若某元素没有后继, 则称为**终端元素** (Tail)
- 对称序偶用圆括号表示, 如 $(x, y) \in r$
### 逻辑结构的类型
- 集合
- 线性结构
- 树形结构
- 图形结构
### 集合
- 只有 "同属于一个集合" 的关系
#### Set
### 线性结构
- 若非空，则只有一个开始元素和一个终端元素
- 除终端元素外，每个元素都有一个后继元素
- 除开始元素外，每个元素都有一个前驱元素
#### Linear
### 树形结构
- 若非空，则只有一个开始元素
- 每个元素有零个或多个后继元素
- 除开始元素外, 每个元素都有一个前驱元素
#### Tree
### 图形结构
- 每个元素可以有多个后继元素
- 每个元素可以有多个前驱元素
#### Graph
### 数据的存储结构
- 存储数据元素
- 存储逻辑关系
### 常见存储结构
- 顺序存储结构
- 链式存储结构
- 索引存储结构
- 散列存储结构
### 顺序存储
- 使用一片地址连续的存储单元
- 数据元素的存储位置相邻
class Stud1
{
int no;
String name;
int score;
public Stud1(int no1,String name1,int score1)
{
no=no1; name=name1; score=score1;
}
public void disp()
{
System.out.println(no+" "+name+" "+score);
}
}
#### Sequential Storage
### 链式存储
- 使用任意存储单元
- 数据元素的存储位置不一定相邻
- 通过指针存储数据元素之间的逻辑关系
#### Linked Storage
### 索引存储
- 使用两个表: 数据表, 索引表
- 索引表中每个元素都包含一个指针
- 指针指向数据表中的某个元素
#### Indexed Storage
### 散列存储 (hash)
- 用哈希函数将数据元素关键字映射到地址上
- 地址称为散列 (哈希) 地址
- 散列地址与数据元素的逻辑关系无关
#### Hash Storage
### 数据的运算
- 运算是指对数据实施的操作
- 功能描述
- 功能实现
### 功能描述
- 基于逻辑结构
- 用户定义的
- 抽象的
### 功能实现
- 基于存储结构
- 程序员实现的
- 具体的
- 等同于算法设计
### 数据类型
- 一组性质相同的值的集合
- 定义在此集合上的一些操作
### 抽象数据类型 (Abstract Data Type, ADT)
- 逻辑数据结构的描述
- 逻辑数据结构上的运算
### 抽象数据类型的描述
- 数据对象
- 数据关系
- 基本操作
- $ADT = (D, S, P)$
### 抽象数据类型
- Set
- TwoSet
### Set
- $E$ 类型
- 遵循标准数学定义
- 求集合长度
- 求第 $i$ 个元素
- 判断一个元素是否在集合中
- 向集合中添加一个元素
- 从集合中删除一个元素
- 输出集合中的所有元素
### Set
ADT Set
{
数据对象:
$$ data = \lbrace d\_i | 0 \leq i \leq n-1, d\_i \in E \rbrace $$
int size;
数据关系:
无
基本运算:
int getSize();
E get(int i); boolean IsIn(E e);
boolean add(E e); boolean delete(E e);
void display();
} ADT Set
### TwoSet
- 集合并
- 集合交
- 集合差
### TwoSet
ADT TwoSet
{
数据对象:
$$ data = \lbrace s\_i | 1 \leq i \leq n, s\_i \in Set \rbrace; $$
数据关系:
无
基本运算:
Union(Set s1, Set s2);
Intersect(Set s1, Set s2);
Difference(Set s1, Set s2);
}
### 抽象数据类型的特征
- 数据抽象
- 数据封装
### 数据抽象
- 本质特征
- 能完成的功能
- 用户接口
### 数据封装
- 将外部特征与内部实现分离
- 对用户隐藏实现细节
### 8.1 什么是数据结构
- 数据的基本单位是什么? 如何定义?
- 什么是数据项? 有什么特点?
- 逻辑结构和存储结构分别是什么? 有什么区别?
- 描述集合, 线性结构, 树形结构和图形结构的特点.
- 顺序存储和链式存储的特点和区别是什么?
- 抽象数据类型是什么? 它包含哪些方面的描述?
----
[ 7.5 非关系数据库](dbds-7-5.html#/overview)
[| 练习 |](dbds-exec.html)
[ 8.2 算法及其描述](dbds-8-2.html#/overview)
黑公网安备23010302001726号