山大计算机数据结构ppt电子版资料DS01课件.ppt

数据结构DATASTRUCTURE;什么是数据结构 抽象数据类型及面向对象概念 数据结构的抽象层次 用C++描述面向对象程序 算法定义 模板 性能分析与度量;“学生”表格;“课程”表格; 选课单包含如下信息 学 号 课程编号 成 绩 时 间  学生选课系统中实体构成的网状关系;UNIX文件系统的系统结构图;数据：数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。 数值性数据 非数值性数据 数据对象：数据的子集。具有相同性质的数据成员（数据元素）的集合。 整数数据对象 N = { 0, ?1, ?2, … } 学生数据对象;什么是数据结构;抽象数据类型及面向对象概念;抽象数据类型 (ADTs: Abstract Data Types);自然数的抽象数据类型定义;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;面向对象的概念  面向对象 = 对象＋类＋继承＋通信 对象 在应用问题中出现的各种实体、事件、规格说明等 由一组属性值和在这组值上的一组服务（或称操作）构成 类 (class)，实例 (instance) 具有相同属性和服务的对象归于同一类，形成类 类中的一个对象为该类的一个实例;继承 派生类：载重车，轿车，摩托车，… 子类 特化类(特殊化类) 基类：车辆 父类 泛化类(一般化类) 通信 消息传递 用于描述数据结构的语言 Smalltalk Effel C++ Java;线形聚类 直接存取类 顺序存取类 广义索引类 非线形聚类 层次聚集类 树，二叉树，堆 群聚集类 集合，图; 数据结构的抽象层次;线性聚集类中各数据成员之间的线性关系;堆结构;群聚类;用C++描述面向对象程序;算法定义;事例学习：选择排序问题 明确问题：非递减排序 解决方案：逐个选择最小数据 算法框架： for ( int i=0; in-1; i++ ) { //n-1趟 从a[i]检查到a[n-1]; 若最小的整数在a[k], 交换a[i]与a[k]; } 细化程序：程序 SelectSort ; void selectSort ( int a[ ], const int n ) { //对n个整数a[0],a[1],…,a[n-1], 按非递减顺序排序 for ( int i=0; in-1; i++ ) { int k = i; //从a[i]检查到a[n-1], 找最小的整数, 在a[k] for ( int j=i+1; jn; j++ ) if ( a[j] a[k] ) k = j; //k指示当前找到的最小整数 int temp = a[i]; a[i] = a[k]; a[k] = temp; //交换a[i]与a[k] } } ;模板 (template