第1章_绪论概要.ppt

数据类型 数据类型：一个值的集合和定义在这个值集上的一组操作的总称。 在高级程序设计语言中，它明显或隐含地规定了程序执行期间变量或表达式所有可能取值的范围以及在这些值上允许进行的操作。 按“值”的不同特性，可分为： 非结构的原子类型：值是不可分解的。 结构类型：值由若干成分按某种结构组成，是可分解的，且他的成分可以是非结构的，也可以是结构的。 【例】在C语言中，基本类型（整型、实型、字符型和枚举型）、指针类型和空类型属于原子类型；数组、结构、联合、自定义类型等属于结构类型。 抽象数据类型 抽象数据类型（ADT）：指一个数学模型以及定义在该模型上的一组操作。 分类： 原子类型 固定聚合类型/静态类型 结构类型 可变聚合类型/动态类型 固定聚合类型：属于该类型的变量，其值由确定数目的成分按某种结构组成。 可变聚合类型：构成其值的成分的数目不确定。 抽象数据类型的形式定义 抽象数据类型的形式定义：用三元组（Ｄ，Ｓ，Ｐ）描述，其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。 抽象数据类型的定义格式：（见P8） 数据对象和数据关系的定义用伪码描述，基本操作的定义格式为：　　 基本操作的定义 两种参数： 赋值参数——只为操作提供输入值； 引用参数——以打头，除可提供输入值外，还将返回操作结果。 初始条件：描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败并返回相应出错信息。（若初始条件为空，则省略） 操作结果：说明操作完成之后，数据结构的变化和应返回的结果。 实例：三元组的抽象类型定义 多形数据类型（其值的成分不确定，见P9） 常见基本操作举例 检索/查找——在数据结构中查找满足一定条件的数据元素，如：给定某个数据项的值，查找具有该数据项值的数据元素。 插入——往数据结构中增加新的数据元素。 删除——把指定的数据元素从数据结构中去掉。 更新——改变指定的数据元素的一个或多个数据项的值。 插入、删除、更新操作中都包含着检索操作！ 排序——保持线性结构的数据元素个数不变，把数据元素按指定某种顺序重新排列，如：按某个数据项的值从小到大进行排列。 抽象数据类型（2） 抽象数据类型是模块化思想的发展，它为模块的划分提供了理论依据。 抽象数据类型用数学方法定义对象集合和运算集合，仅通过运算的性质刻画数据对象，而独立于计算机中可能的表示方法。其目的在于隐藏运算实现的细节和内部数据结构，同时向用户提供该数据类型的完整信息。 …… User1 User2 Usern 实现1 实现2 实现m …… ADT 抽象数据类型（2） 抽象数据类型概念实现了数据掩蔽与操作封装 可以使程序模块的实现与使用分离； 也可以使应用程序只要按抽象数据类型的观点统一其调用方式，有利于程序的维护和修改。 对ADT中数据的访问只能通过操作来进行，这对于保护数据与信息的安全，防止操作越界是有很多好处的。 在许多程序设计语言中预定义的类型，如整数类型、浮点类型、指针类型等，都可以看作是简单的抽象数据类型。 从原则上讲，数据结构课程中讨论的各种表、栈、队列、二叉树和字典等，也可以定义为程序设计语言预定义的抽象数据类型。 在抽象数据类型的基础上，以后又进一步发展了对象的概念，面向对象的描述方法和面向对象的程序设计语言与程序设计技术。 1.3 抽象数据类型的表示和实现 采用类C语言描述（C语言的一个核心子集），注意比较与C语言的异同点。（详见P10-11 ） 预定义常量和类型 辅助变量一般不作变量说明，一般约定： 1.3 抽象数据类型的表示和实现（2） 与C语言的主要区别： 一些简化描述，如成组赋值、交换赋值、开关语句等； 除值调用方式外，增加了C++中的引用调用的参数传递方式（即形参表中以打头的参数，称为引用参数）； 主要侧重抽象数据结构和算法的描述，不拘泥于C语言的实现细节；（注意与C语言代码的一些差异！） …… 1.4 算法和算法分析 算法：是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。 算法具有以下五个重要特性： （1）有穷性 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 这里的“有穷”指合理的、可接受的，而不是纯数学意义上的有穷！ （2）确定性 算法中每一条指令必须有确切的含义，不存在二义性。且对于相同的输入只能得到相同的输出。 （3）可行性 一个算法是可行的，即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。 （4）输入 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。 （5）输出 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。 算法与程序之间有什么区别呢？ 程序是算