数据结构——第1章.ppt

第1章 绪论 1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示和实现 1.4 算法和算法分析 * 数据类型(data type) 定义 数据类型是一个值的集合和定义在这个值集合上的一组操作的总称。 作用 屏蔽实现细节，程序设计人员只需了解其抽象特性即可。 分类 原子类型、结构类型、多形数据类型 * * 抽象数据类型(abstract data type, ADT) 概念: 一个数学模型以及定义在该模型上的一组 操作。它不管这些操作如何在计算机中表示和实现。 定义格式 　ADT抽象数据类型名｛ 　　数据对象：数据对象定义 　　数据关系： 数据关系定义 　　基本操作： 基本操作定义 　｝ADT抽象数据类型名 初始条件 操作结果 Q 数据类型与抽象数据类型的区别？ 数据类型：是一个值的集合和定义在该值上 的一组操作的总称。 抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作） 抽象数据类型与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。 * 抽象数据类型定义的例子1 ADT Compare{ 数据对象：D={e1, e2| e1, e2为可比较的同类型的元素} 数据关系：R={ e1, e2 } 基本操作： InitCom(C, ee1, ee2) 操作结果：构造一个二元组c，元素e1,e2分别被赋成ee1,ee2。 FirElemBig(C) 初始条件：二元组已经存在。 操作结果：如果首元素大，则返回1，否则返回0。 ... } ADT Compare * 抽象数据类型定义的例子2 ADT square { 数据对象： length//非负实数，表示正方形的边长； 数据关系： 无 基本操作： Init( S, length ) 　 初始条件：无 　操作结果：将正方形S的边长初始化成length Area( S) 　 初始条件：圆C存在 　 操作结果：若正方形S存在返回正方形的面积，否则返回false ZhouChang( S) 　 初始条件：圆C存在 　 操作结果：若正方形S存在返回正方形的周长，否则返回false } ADT square * 抽象数据类型的表示 typedef float square ; // 定义圆的存储结构 // 操作目的：对正方形s初始化 // 初始条件：无 // 操作结果：将正方形s的边长初始化成 l bool Init(square *s , float l); // 操作目的：求正方形s的面积 // 初始条件：正方形s存在 // 操作结果：若正方形s存在返回正方形的面积，否则返回false float Area(square s); // 操作目的：求正方形s的周长 // 初始条件：正方形s存在 // 操作结果：若正方形s存在返回正方形的周长，否则返回false float ZhouChang(square s); * 抽象数据类型的实现 本质：数据与关系的存储、操作的实现。 根据具体的程序设计语言实现具体的ADT,本课程统一要求用c语言来实现。 推荐学有余力的同学尝试用c++实现。 演示刚才正方形ADT的实现。 * 正方形ADT的实现 typedef double square; // 采用双精度类型存储square bool init(square *s , square l){//初始化 if(l0){ *s=l; return true; } else return false; }; square Area(square s){//求面积 return s*s; }; square ZhouChang(square s){//求周长 return 4*s; };