779-数据结构抽象数据类型及面向对象概念数据结构的抽象层次.ppt
《779-数据结构抽象数据类型及面向对象概念数据结构的抽象层次.ppt》由会员分享,可在线阅读,更多相关《779-数据结构抽象数据类型及面向对象概念数据结构的抽象层次.ppt(72页珍藏版)》请在三一文库上搜索。
1、什么是数据结构 抽象数据类型及面向对象概念 数据结构的抽象层次 用C+描述面向对象程序 算法定义 模板 性能分析与度量 小结,第一单元 绪论,“学生”表格,“课程”表格,选课单包含如下信息 学号 课程编号 成绩 时间 学生选课系统中实体构成的网状关系,学生 (学号,姓名,性别,籍贯),课程 (课程号,课程名,性别,籍贯),选课 (学号,课程号,成绩),UNIX文件系统的系统结构图,/ (root),bin,lib,user,etc,math,ds,sw,yin,tao,xie,Stack.cpp,Queue.cpp,Tree.cpp,数据:数据是信息的载体,是描述客观事物的数、字符、以及所有能
2、输入到计算机中,被计算机程序识别和处理的符号的集合。 数值性数据 非数值性数据 数据对象:数据的子集。具有相同性质的数据成员(数据元素)的集合。 整数数据对象 N = 0, 1, 2, 学生数据对象,什么是数据结构,定义: 由某一数据对象及该对象中所有数据成员之间的关系组成。记为: Data_Structure = D, R 其中,D是某一数据对象,R是该对象中所有数据成员之间的关系的有限集合。,n个网站之间的连通关系,树形关系,网状关系,1,5,2,6,4,3,1,5,2,6,4,3,抽象数据类型及面向对象概念,数据类型 定义:一组性质相同的值的集合, 以及定义于这个值集合上的一组操作的总称
3、. C语言中的数据类型 char int float double void 字符型 整型 浮点型 双精度型 无值,抽象数据类型 (ADTs: Abstract Data Types),由用户定义,用以表示应用问题的数据模型 由基本的数据类型组成, 并包括一组相关的服务(或称操作) 信息隐蔽和数据封装,使用与实现相分离,抽象数据类型,查找 登录 删除 修改,符 号 表,自然数的抽象数据类型定义,ADT NaturalNumber is objects: 一个整数的有序子集合,它开始于0, 结束于机器能表示的最大整数(MaxInt)。 Function: 对于所有的 x, y NaturalNu
4、mber; False, True Boolean, +、-、=、=等都是可用的服务。 Zero( ) : 返回自然数0 NaturalNumber,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
5、Successor (x) : if (x=MaxInt) 返回 x NaturalNumber else 返回 x+1 end NaturalNumber,面向对象的概念 面向对象 = 对象类继承通信 对象 在应用问题中出现的各种实体、事件、规格说明等 由一组属性值和在这组值上的一组服务(或称操作)构成 类 (class),实例 (instance) 具有相同属性和服务的对象归于同一类,形成类 类中的一个对象为该类的一个实例,继承 派生类:载重车,轿车,摩托车, 子类 特化类(特殊化类) 基类:车辆 父类 泛化类(一般化类) 通信 消息传递 用于描述数据结构的语言 Smalltalk Eff
6、el C+ Java,线性聚类 直接存取类 顺序存取类 广义索引类 非线性聚类 层次聚集类 树,二叉树,堆 群聚集类 集合,图,数据结构的抽象层次,数据结构的抽象层次,线性关系,树形结构,树 二叉树 二叉搜索树,14,13,12,11,1,2,3,4,5,6,7,8,9,10,3,1,5,8,7,10,11,9,9,8,7,4,5,6,6,2,3,13,1,bin,dev,etc,lib,user,堆结构,“最大”堆 “最小”堆,12,3,5,4,8,7,11,10,2,9,1,6,4,10,12,11,5,1,2,3,6,9,8,7,群聚类,图结构 网络结构,1,2,5,6,4,3,1,2,
7、5,4,3,6,11,33,18,14,6,6,5,16,19,21,用C+描述面向对象程序,C+的函数特征 C+的数据声明 C+的作用域 C+的类 C+的对象 C+的输入/输出 C+的函数 C+的参数传递,C+的函数名重载和操作符重载 C+的动态存储分配 友元(friend)函数 内联(inline)函数 结构(struct)与类 联合(Union)与类,算法定义,定义:一个有穷的指令集,这些指令为解决某一特定任务规定了一个运算序列 特性: 输入 有0个或多个输入 输出 有一个或多个输出(处理结果) 确定性 每步定义都是确切、无歧义的 有穷性 算法应在执行有穷步后结束 有效性 每一条运算应足
8、够基本,事例学习:选择排序问题 明确问题:非递减排序 解决方案:逐个选择最小数据 算法框架: for ( int i = 0; i n-1; i+ ) /n-1趟 从ai检查到an-1; 若最小的整数在ak, 交换ai与ak; 细化程序:程序 SelectSort,算法设计 自顶向下,逐步求精,void selectSort ( int a , const int n ) /对n个整数a0,a1,an-1, 按非递减顺序排序 for ( int i = 0; i n-1; i+ ) int k = i; /从ai检查到an-1, 找最小的整数, 在ak for ( int j = i+1; j
9、 n; j+ ) if ( aj ak ) k = j; /k指示当前找到的最小整数 int temp = ai; ai = ak; ak = temp; /交换ai与ak ,模板 (template),定义 适合多种数据类型的类定义或算法,在特定环境下通过简单地代换,变成针对具体某种数据类型的类定义或算法,用模板定义用于排序的数据表(dataList)类 #ifndef DATALIST_H #define DATALIST_H #include template class dataList private: Type *Element; int ArraySize; void Swap
10、(const int m1, const int m2); int MaxKey (const int low, const int high);,public: dataList (int size = 10) : ArraySize (size), Element (new Type Size) dataList ( ) delete Element; void Sort ( ); friend ostream #endif,dataList类中所有操作作为模板函数的实现 #ifndef SELECTTM_H #define SELECTTM_H #include “datalist.h”
11、 template void dataList : Swap (const int m1, const int m2) /交换由m1, m2为下标的两个数组元素的值 Type temp = Element m1; Element m1 = Element m2; Element m2 = temp; ,template int dataList: MaxKey (const int low, const int high) /查找数组ElementlowElementhigh中 /的最大值,函数返回其位置 int max = low; for (int k = low+1, k = high,
12、 k+) if ( Elementmax Elementk ) max = k; return max; ,template ostream ,template istream ,template void dataList:Sort ( ) /按非递减顺序对ArraySize个关键码 /Element0ElementArraySize-1排序。 for ( int i = ArraySize -1; i 0; i- ) int j = MaxKey (0, i); if ( j != i ) swap (j, i); #endif,使用模板的选择排序算法的主函数 #include “sele
13、cttm.h” const int SIZE = 10; int main ( ) dataList TestList (SIZE); cin TestList; cout “Testing Selection Sort : n” TestList endl; TestList.Sort ( ); cout “After sorting : n” TestList endl; return 0; ,性能分析与度量,算法的性能标准 算法的后期测试 算法的事前估计,算法的性能标准,正确性 可使用性 可读性 效率 健壮性,算法的后期测试,在算法中的某些部位插装时间函数 time ( ) 测定算法完成
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 779 数据结构 抽象 数据类型 面向 对象 概念 层次
链接地址:https://www.31doc.com/p-3024108.html