[理学]Ch_1 绪论.ppt

课时安排： 上课——52学时 上机——12学时 例1 书目检索系统自动化问题 例2 人机对弈问题 例3 多叉路口交通灯管理问题 例4 制定教学计划 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作(包括对数据进行查找,插入,删除,合并,排序,统计以及简单计算)等的学科. 数据（data)—对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称.如整数，实数，字符串，图像，声音是数据。 数据元素（data element）—数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。是数据结构中讨论的基本单位 数据项（data item）—数据的不可分割的最小单位.一个数据元素可由若干个数据项组成。如一本书的书目信息为一个数据元素，书目信息中的每一项（如书名，作者名）为一个数据项。 数据对象是性质相同的数据元素的集合，是数据的一个子集。如整数数据对象是集合N ={ 0, ±1, ±2, … }，字母字符数据对象是集合C={‘A’,’B’,’C’,……，’Z’}。 数据结构（data structure)—是相互之间存在一种或多种特定关系的数据元素的集合。数据元素相互之间的关系称为结构。带结构的数据元素的集合。 1.4 算法和算法分析 数据类型 在用高级程序语言编写的程序中， 必须对程序中出现的每个变量、常量 或表达式，明确说明它们所属的数据 类型。 例如，C 语言中提供的基本数据类型有: 整型 int 浮点型 float 字符型 char 逻辑型 bool （ C++语言） 双精度型 double 实型（ C++语言） 数据类型 是一个 值的集合和定义在此集合上的 一组操作的总称。 不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。 1.3、抽象数据类型 (Abstract Data Type 简称ADT) 是指一个数学模型以及定义在此数学模型上的一组操作。 抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要数学特性不变，都不影响其外部的使用。 抽象数据类型的描述方法 抽象数据类型可用（D，S，P）三元组表示。 其中：D 是数据对象； S 是 D 上的关系集； P 是对 D 的基本操作集。 ADT 抽象数据类型名 { 数据对象：〈数据对象的定义〉 数据关系：〈数据关系的定义〉 基本操作：〈基本操作的定义〉 } ADT 抽象数据类型名 其中基本操作的定义格式为: 基本操作名（参数表） 初始条件：〈初始条件描述〉 操作结果：〈操作结果描述〉 赋值参数 只为操作提供输入值。 引用参数 以打头，除可提供输入值外， 还将返回操作结果。 初始条件 描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。 操作结果 说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。 例如，抽象数据类型复数的定义： 数据对象： D＝{e1,e2｜e1,e2∈RealSet } 数据关系： R1＝{e1,e2 | e1是复数的实数部分 | e2 是复数的虚数部分 } ADT Complex { 基本操作： AssignComplex( Z, v1, v2 ) 操作结果：构造复数 Z,其实部和虚部 分别被赋以参数 v1 和 v2 的值。 DestroyComplex( Z) 操作结果：复数Z被销毁。 GetReal( Z, realPart ) 初始条件：复数已存在。 操作结果：用realPart返回复数Z的实部值。 GetImag( Z, ImagPart ) 初始条件：复数已存在。 操作结果：用ImagPart返回复数Z的虚部值。 Add( z1,z2, sum ) 初始条件：z1, z2是复数。 操作结果：用sum返回两个复数z1, z2 的 和值。 } ADT Complex 抽象数据类型的表示和实现 抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。 例如，对以上定义的复数。 typedef struct { float realpart； float imagpart； }complex； // -----存储结构的定义 // ----