第一章概述 数据结构的兴起与发展 数据结构的存储 数据结构的研究对象 数据的基本操作 数据结构的概念 ·算法的基本概念 数据结构的图示 面向对象方法 数据结构的分类 面向对象与数据结构
1 第一章 概述 • 数据结构的兴起与发展 • 数据结构的研究对象 • 数据结构的概念 • 数据结构的图示 • 数据结构的分类 • 数据结构的存储 • 数据的基本操作 • 算法的基本概念 • 面向对象方法 • 面向对象与数据结构
s1.1数据结构的兴起与发展 数据结构问题起源于程序设计的发展。 程序设计现在已经历了三个阶段: 无结构阶段 结构化程序设计阶段 面向对象阶段
2 §1.1 数据结构的兴起与发展 • 数据结构问题起源于程序设计的发展。 • 程序设计现在已经历了三个阶段： –无结构阶段 –结构化程序设计阶段 –面向对象阶段
§12数据结构的研究对象 ·计算机应用系统中的两个关键问题: 表示 对象/实体及其关系在计算机中的表 示。只有对象及其相互关系已存储(表示)在计算 机中,才能被进一步处理; 操作 对对象/实体进行处理、访问
3 §1.2 数据结构的研究对象 • 计算机应用系统中的两个关键问题： – 表示 ----- 对象/实体及其关系在计算机中的表 示。只有对象及其相互关系已存储（表示）在计算 机中，才能被进一步处理； – 操作 ------ 对对象/实体进行处理、访问
51.2数据结构的研究对象 例1:解一元二次方程ax2+bx+C=0. 问题:如何在计算机中表示该方程? 用三个系数的线性排列在来表示 -3x2x+1=0表示为(3,-1,1) ×2-3=0表示为(1,0,-3) 元二次方程ax2+bx+C=0在计算机中表示为线性表 (a, b, c) 解方程实质上是对线性表(a,b,C进行操作
4 §1.2 数据结构的研究对象 • 例1：解一元二次方程ax2+bx+c=0. 问题：如何在计算机中表示该方程？ • 用三个系数的线性排列在来表示 –3x 2 -x+1=0表示为（3, -1, 1） –x 2 -3=0 表示为(1, 0, -3) • 一元二次方程ax2+bx+c=0在计算机中表示为线性表 （a, b, c） • 解方程实质上是对线性表(a, b, c)进行操作
51.2数据结构的研究对象 例2:计算机管理家谱:主要实现家庭成员的登记、查询及变 更处理等 在数据结构中,该层次结构称为树 W11 w12 W13 w21w122/W31/W32/W133 W1112 wI221 图一个家族结构的树表示
5 §1.2 数据结构的研究对象 • 例2：计算机管理家谱 ：主要实现家庭成员的登记、查询及变 更处理等 • 在数据结构中，该层次结构称为树。 W1 W12 W111 W121 W122 W11 W131 W132 W133 W13 W1111 W1112 W1221 图 - 一个家族结构的树表示
51.2数据结构的研究对象 除了确定表示方式外,数据结构的任务还有对这棵 树的计算机物理存储、操作的抽象化。 ·数据结构的研究内容为: 数据的组织方式 相应的抽象操作
6 §1.2 数据结构的研究对象 • 除了确定表示方式外，数据结构的任务还有对这棵 树的计算机物理存储、操作的抽象化。 • 数据结构的研究内容为： 数据的组织方式 相应的抽象操作
§1.3数据结构的概念 数据:描述客观事物的信息的符号化,是计算机系 统可加工处理的对象 数据类型:一个值的集合和定义在这个值集上的 组操作的总称。 原子类型 复合类型(或导出类型或结构类型)
7 §1.3 数据结构的概念 • 数据：描述客观事物的信息的符号化，是计算机系 统可加工处理的对象 • 数据类型：一个值的集合和定义在这个值集上的一 组操作的总称。 –原子类型 –复合类型（或导出类型或结构类型）
51.3数据结构的概念 数据元素、数据项: 能独立、完整地描述问题世界中的实体的最小数据 单位称为数据元素(也称记录)。构成数据元素的不 可分割的数据单位,称为数据项 数据对象:同类数据元素的集合称为数据象
8 §1.3 数据结构的概念 • 数据元素、数据项： 能独立、完整地描述问题世界中的实体的最小数据 单位称为数据元素（也称记录）。构成数据元素的不 可分割的数据单位，称为数据项 • 数据对象：同类数据元素的集合称为数据对象
51.3数据结构的概念 数据结构: 相互之间存在着一定关系的数据元素的集合及定义在其上的操 作(运算)为数据结构 如果不考虑定义在数据结构上的操作,则称数据结构为数据的 逻辑结构 数据的逻辑结构也可借助集合论述语定义: 数据逻辑结构是一个二元组(D,S),其中D是数据元素的有限 集,S是D上的关系的有限集 型为的二元关系中,称d1为关系的前件,d2为后件 称d2为d1的后继,而dl为d2的前驱
9 §1.3 数据结构的概念 • 数据结构: 相互之间存在着一定关系的数据元素的集合及定义在其上的操 作（运算）为数据结构. 如果不考虑定义在数据结构上的操作，则称数据结构为数据的 逻辑结构. • 数据的逻辑结构也可借助集合论述语定义： 数据逻辑结构是一个二元组（D,S），其中D是数据元素的有限 集，S是D上的关系的有限集。 型为的二元关系中，称d1为关系的前件，d2为后件。 称d2为d1的后继，而d1为d2的前驱
§1.4数据结构的图示 若d1和d2表示两个数据元素,它们具有关系 则表示为 d2 数据元素 数据元素之间的关系
10 §1.4 数据结构的图示 • 若d1和d2表示两个数据元素，它们具有关系＜d1,d2＞， 则表示为 d1 d2 数据元素 数据元素之间的关系