什么是数据结构抽象数据类型及面向对象概念数据结构的抽象.ppt

什么是数据结构 抽象数据类型及面向对象概念 数据结构的抽象层次 算法定义 性能分析与度量 “学生”表格 “课程”表格 “选课单”包含如下信息 学号 课程编号 成绩 时间  学生选课系统中实体构成的网状关系 UNIX文件系统的系统结构图 数据（data） 数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。 数值性数据； 非数值性数据。 数据对象 (data object) 数据的子集。具有相同性质的数据成员（数据元素）的集合。 整数数据对象 ： N = { 0, ?1, ?2, … } 学生数据对象。 什么是数据结构 N 个网点之间的连通关系 抽象数据类型及面向对象概念 数据类型 定义：一组性质相同的值的集合, 以及定义于这个值集合上的一组操作的总称。 C语言中的数据类型 char int float double void 字符型 整型 浮点型 双精度型 无值 抽象数据类型 (ADTs: Abstract Data Types) 由用户定义，用以表示应用问题的数据模型。 由基本的数据类型组成, 并包括一组相关的服务（或称操作）。 信息隐蔽和数据封装，使用与实现相分离。 自然数的抽象数据类型定义 ADT NaturalNumber is objects: 一个整数的有序子集合,它开始于0, 结束于机器能表示的最大整数(MaxInt)。 Function: 对于所有的 x, y ? NaturalNumber; False, True ? Boolean, +、-、、==、=等都是可用的服务。 Zero( ) : NaturalNumber 返回自然数0 IsZero(x) : if (x==0) 返回True Boolean else 返回False Add (x, y) : if (x+y=MaxInt)返回 x+y NaturalNumber else 返回MaxInt Subtract (x, y) : if (x y) 返回 0 NaturalNumber else 返回 x - y Equal (x, y) : if (x==y) 返回True Boolean else 返回 False Successor (x) : if (x==MaxInt) 返回 x NaturalNumber else 返回 x+1 end NaturalNumber 继承 派生类：四边形，三角形，… 子类 特化类(特殊化类) 基类：多边形 父类 泛化类(一般化类) 通信 消息传递 数据结构的抽象层次 线性结构 直接存取类 数组, 文件； 顺序存取类 表, 栈, 队列, 优先队列； 广义索引类 线性索引, 有哪些信誉好的足球投注网站树。 非线性结构 层次结构类 树, 二叉树, 堆； 群结构类 集合, 图。 算法定义 定义：一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列。 特性： 输入 有0个或多个输入； 输出 有一个或多个输出(处理结果)； 确定性 每步定义都是确切无歧义的； 有穷性 算法应在执行有穷步后结束； 有效性 每一条运算应足够基本。 事例学习：选择排序问题。 明确问题：递增排序。 解决方案：逐个选择最小数据。 算法框架： for ( int i = 0; i n-1; i++ ) { //n-1趟 从a[i]检查到a[n-1]; 若最小整数在a[k], 交换a[i]与a[k]; } 细化程序：程序 SelectSort 性能分析与度量 算法的性能标准 算法的后期测试 算法的事前估计 算法的性能标准 正确性 可使用性 可读性 效率 健壮性 算法的后期测试 在算法中的某些部位插装时间函数 time ( ) 测定算法完成某一功能所花费时间。 算法的事前估计 空间复杂度 时间复杂度 空间复杂度度量 存储空间的固定部分程