清华大学课程讲义数据结构01.ppt

数据结构DATA STRUCTURE —— C++ 描述 什么是数据结构 抽象数据类型及面向对象概念 数据结构的抽象层次 用C++描述面向对象程序 算法定义 模板 性能分析与度量 “学生”表格 “课程”表格 选课单包含如下信息 学 号 课程编号 成 绩 时 间  学生选课系统中实体构成的网状关系 UNIX文件系统的系统结构图 数据：数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。 数值性数据 非数值性数据 数据对象：数据的子集。具有相同性质的数据成员（数据元素）的集合。 整数数据对象 N = { 0, ?1, ?2, … } 学生数据对象 什么是数据结构 抽象数据类型及面向对象概念 数据类型 定义：一组性质相同的值的集合, 以及定义于这个值集合上的一组操作的总称. C语言中的数据类型 char int float double void 字符型 整型 浮点型 双精度型 无值 抽象数据类型 (ADTs: Abstract Data Types) 由用户定义，用以表示应用问题的数据模型 由基本的数据类型组成, 并包括一组相关的服务（或称操作） 信息隐蔽和数据封装，使用与实现相分离 自然数的抽象数据类型定义 ADT NaturalNumber is objects: 一个整数的有序子集合,它开始于0, 结束于机器能表示的最大整数(MaxInt)。 Function: 对于所有的 x, y ? NaturalNumber; 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 Successor (x) : if (x==MaxInt) 返回 x NaturalNumber else 返回 x+1 end NaturalNumber 面向对象的概念  面向对象 = 对象＋类＋继承＋通信 对象 在应用问题中出现的各种实体、事件、规格说明等 由一组属性值和在这组值上的一组服务（或称操作）构成 类 (class)，实例 (instance) 具有相同属性和服务的对象归于同一类，形成类 类中的一个对象为该类的一个实例 继承 派生类：载重车，轿车，摩托车，… 子类 特化类(特殊化类) 基类：车辆 父类 泛化类(一般化类) 通信 消息传递 用于描述数据结构的语言 Smalltalk Effel C++ Java 数据结构的抽象层次 线形聚类 直接存取类 顺序存取类 广义索引类 非线形聚类 层次聚集类 树，二叉树，堆 群聚集类 集合，图 数据结构的抽象层次 线性聚集类中各数据成员之间的线性关系 堆结构 群聚类 用C++描述面向对象程序 C++的函数特征 C++的数据声明 C++的作用域 C++的类 C++的对象