第一章 绪论 1.1 引言 1.2 逻辑结构和存储结构 1.3 算法.

Presentation on theme: "第一章 绪论 1.1 引言 1.2 逻辑结构和存储结构 1.3 算法."— Presentation transcript:

1 第一章 绪论 1.1 引言 1.2 逻辑结构和存储结构 1.3 算法

2 1.1 引言 研究数据的特性以及数据之间存在的关系——数据结构（Date Structure）
数据结构是研究程序设计中计算机操作的对象以及它们之间的关系和运算的一门学科。

3 程序 ＝ 算法 ＋ 数据结构 瑞士科学家沃思（Niklaus Wirth，1984年图灵奖得主）在1976年出版了著名的《程序＝算法＋数据结构》一书。 软件：刻画现实世界，解决现实世界中的问题 语言：实现的工具 算法：问题的解的描述 数据结构：现实世界的数据模型 程序就是在数据的某些特定的表示方式和结构的基础上对抽象算法的具体表述。 不了解施加于数据上的算法就无法决定如何构造数据，反之，算法的结构和选择却常常在很大程度上依赖于作为基础的数据结构。 简而言之，程序的构成（算法）与数据结构是两个不可分割地联系在一起的问题。

4 1.2 逻辑结构和存储结构 数据之间的逻辑关系称为数据的逻辑结构 数据在计算机中的存储表示称为数据的存储结构
一种逻辑结构可以用多种存储结构表示

5 常见的逻辑结构 线性表 树 图

6 线性表 学号 姓名 性别 出生日期 政治面貌 0001 王 军 男 1983/09/02 团员 0002 李 明 1982/12/25 党员
王 军 男 1983/09/02 团员 0002 李 明 1982/12/25 党员 0003 汤晓影 女 1984/03/26 …

7 树 家谱

8 图 如何表示课程之间的先修关系？ C1 C2 C3 C4 C6 C5 C7 先修课 课程名称 编号 C4, C5, C6 数据库原理 C7
计算机原理 C6 C3, C4 数据结构 C5 C1, C2 程序设计 C4 C1 离散数学 C3 无 计算机导论 C2 高等数学 先修课 课程名称 编号 C1 C2 C3 C4 C6 C5 C7

9 常见的存储结构 顺序存储 链式存储 例：（bat, cat, eat） … cat 0325 bat 0200 eat ∧ 0200
0208 0300 0325 … cat 0325 bat 0200 eat ∧

10 1.3 算法 算法分析（Algorithm Analysis）：对算法所需要的计算机资源——时间和空间进行估算。
1.3 算法 算法分析（Algorithm Analysis）：对算法所需要的计算机资源——时间和空间进行估算。 时间复杂性（Time Complexity） 空间复杂性（Space Complexity）