数据结构(严蔚敏)课件 第1章 绪论(new).ppt

* 1.4 什么是抽象数据类型 1.4.1 数据类型与抽象数据类型的区别？ 1.4.2 抽象数据类型如何定义？ 1.4.3 抽象数据类型如何表示和实现？ 讨论： 抽象数据类型和伪码是学习数据结构的工具 * 1.4.1 数据类型与抽象数据类型的区别 数据类型：是一个值的集合和定义在该值上的一组操作的总称。 抽象数据类型(ADT)：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作） 它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机） * 1.4.2 抽象数据类型如何定义 抽象数据类型可以用以下的三元组来表示： ADT = （D，R，P） ADT抽象数据类型名{ 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作 ：基本操作的定义 } ADT抽象数据类型名 ADT常用定义格式 数据对象 D上的关系集 D上的操作集 例：给出自然数(Natural Number )的抽象数据类型定义。 ADT Natural_Number is objects: 一个整数的有序子集合，它开始于0，结束于机器能表示的最大整数 (MAX INT) functions: 对于所有的 x, y ? Natural_Number； TRUE, FALSE ? Boolean； +, -, , = = ,=等都是可用的服务。 Zero ( )： Natural Number 返回 0 IsZero(x)： Boolean if (x==0) 返回TRUE else 返回 FALSE Add(x, y)： Natural Number if (x+y = MAX INT)返回 x+y else 返回 MAX INT Subtract(x,y): Natural Number if (xy)返回0 else 返回x-y Equal(x,y): Boolean if (x== y)返回TRUE else 返回FALSE Successor(x) : Natural Number if (x == MAX INT)返回x else 返回x+1 end Natural_Number 数 据 结 构 * 数据结构课程的地位 ——针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作。 ——是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。 关系 对象 关系 操作 数学 软件 硬件 对象 关系 操作 Data_Structure=（D, R） * 内 容 安 排(50+30) 章 内 容 学时 章 内 容 学时 1 绪 论 2 7 图 6 2 线性表 8 8 动态存储管理 略 3 栈和队列 4 9 查找 4 4 串 4 10 内部排序 8 5 数组和广义表 4 11 外部排序 略 6 树和二叉树 10 12 文件 略 上机地点：逸夫楼五楼专业机房 * 第1章 绪论 第2章 线性表 第3章 栈和队列 第4章 串 第5章 数组和广义表 第6章 树和二叉树 第7章 图 第9章 查找 第10章 排序 目 录 * 第1章　绪　论 讨论5个问题： 1.1 什么是数据结构 1.2 学习数据结构的意义 1.3 数据结构涵盖的主要内容 1.4 什么是抽象数据类型 1.5 算法效率的度量 * 1.1 什么是数据结构 计算机处理问题分几个步骤 从具体问题中抽象出数学模型； 设计算法； 写出程序并测试完成得到最终解。 * 数据结构讨论的范畴 Niklaus Wirth： Algorithm + Data Structures = Programs 程序设计: 算法: 数据结构: 为计算机处理问题编制 一组指令集 处理问题的策略 问题的数学模型 1.1 什么是数据结构 * 非数值计算的程序设计问题 例1: 求一组整数中的最大值 例3：人机对弈 例2：学生的数据库管理 * 例1: 求一组(n个)整数中的最大值 1 3 7 9 32 50 20 2 6 非数值计算的程序设计问题 * 例2：学生的数据库管理 * 例1、例2——线性结构 例3：人机对弈 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?