《基本数据结构元关系和抽象数据类型》由会员分享，可在线阅读，更多相关《基本数据结构元关系和抽象数据类型（21页珍藏版）》请在金锄头文库上搜索。
1、2011-2012秋季学期数据与算法课程讲义 基础数据结构 吴 及 wuji_ 清华大学电子工程系 2011年9月 数据与算法 (20230253) 吴及 电子工程系 2 内容提要 二元关系与抽象数据类型 线性表 栈与队列 串 树与二叉树 图 数据与算法 (20230253) 吴及 电子工程系 3 内容提要 二元关系与抽象数据类型 线性表 栈与队列 串 树与二叉树 图 数据与算法 (20230253) 吴及 电子工程系 4 二元关系 集合的笛卡尔积 集合，： = ， = 集合和的笛卡尔积,记作: , 定义为: =, 且 例： = 1,2， = 0,1,2 则: = (a1, 0), (a1,
2、1), (a1, 2), (a2, 0), (a2, 1), (a2, 2) 数据与算法 (20230253) 吴及 电子工程系 5 二元关系 定义：设有集合、，其笛卡尔积 的仸意一个子集 ，被称为M到N的一个二元关系； 二元关系表示了集合和集合中元素乊间的某种相关性。 若 , ，则称为的前件， 称为的后件 如果 = ，则 称为上的二元关系 数据与算法 (20230253) 吴及 电子工程系 6 二元关系 例如某学生学习语文,数学,外语, 表示为 = 语文,数学,外语 功课的成绩分四个等级,记作 = , 该生成绩的全部可能为： = , , , 那么该生的实际成绩: =, 是 的一个子集，它表示
3、该生功课和成绩的对应关系。 数据与算法 (20230253) 吴及 电子工程系 7 二元关系的性质 设是集合上的一个二元关系： (1)自反性： 对于每个 ，有 , ； 反自反性： 对于所有 ，有 , ； (2) 对称性： 当 , 时, 必有 , ； 反对称性： 当 , 且 , 时,则ab； 戒者如果 , 则 , (3) 传递性： 当 , 且 , 时,必有 , 。 数据与算法 (20230253) 吴及 电子工程系 8 二元关系的性质 二元关系举例 实数集合上的，的关系 集合的，的关系 父子关系，同班同学关系 平面上三角形的全等关系，相似关系 数据与算法 (20230253) 吴及 电子工程系
4、9 等价关系 满足自反性，对称性和传递性，则称这个关系为等价关系 1.自反性：对于所有的 ，有 , ； 2.对称性：当且仅当 , 时, 有 , 成立 3.传递性：若 , 且 , 时,则有 , 上面我们介绍的关系中有哪些是等价关系 实数集合上的实数的相等关系 集合的相等关系 同班同学关系 平面上三角形集合中，三角形的全等和相似关系 数据与算法 (20230253) 吴及 电子工程系 10 偏序关系 R是集合M上的关系，如果满足： 1. 自反性：对于每个 ，有 , ； 2. 反对称性：当 , 且 , ，必有 = ； 3. 传递性：当 , 且 , 时,必有 , ； 则R是集合M上的偏序关系（part
5、ial order relation） 数集上的小于等于关系“”是一种偏序关系 子集包含“”是一种偏序关系 数据与算法 (20230253) 吴及 电子工程系 11 拟序关系 R是集合M上的关系，如果满足： 1. 反自反性：对于每个 ，有 , 2. 反对称性：当 , ，必有 , ； 3. 传递性：当 , 且 , 时,必有 , ； 则R是集合M上的拟序关系 (quasi order relation)，也被称为严格偏序(strict partial order) 数集上的小于关系“ | e1 = Real(D), e2 = Imag(D) 基本操作： InitComplex( &Z, v1, v
6、2 ) 操作结果：构造复数Z,其实部和虚部分别被赋以参数v1和v2的值。 DestroyComplex( &Z) 初始条件：复数Z存在； 操作结果：复数Z被销毁。 Add( z1,z2, &sum ) 初始条件：z1,z2是复数。 操作结果：用sum返回两个复数z1,z2的和值。 Sub( z1,z2, &sub ) 初始条件：z1,z2是复数。 操作结果：用sub返回两个复数z1,z2的差值。 ADT Complex 数据与算法 (20230253) 吴及 电子工程系 18 ADT举例圆柱体 ADT CYLinder 数据对象：Dr,hr,hR 数据关系：R | r为圆柱底面半径,h为圆柱高
7、 基本操作 InitCyld(r,h ) 操作结果：构造圆柱体，底面半径r，圆柱高h。 BaseArea(r,&bArea) 初始条件：圆柱体存在。 操作结果：计算圆柱体底面积，用bArea返回。 SideArea(r,h,&sArea) 初始条件：圆柱体存在。 操作结果：计算圆柱体侧面积，用sArea返回。 Volume(r,h,&vol ) 初始条件：圆柱体存在。 操作结果：计算圆柱体体积，用vol返回。 ADT CYLinder 数据与算法 (20230253) 吴及 电子工程系 19 抽象数据类型的描述 描述方法 ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 基本操作名（参数表） 初始条件：初始条件描述 操作结果：操作结果描述 ADT 抽象数据类型名 基本操作参数： 赋值参数提供输入值； 引用参数以&打头，用于返回操作结果 数据与算法 (20230253) 吴及 电子工程系 编程方式 面向过程 基于对象 面向对象 20 数据与算法 (20230253) 吴及 电子工程系 21 本章作业 作业 数据结构与算法 P39 1.4
