2基本数据结构1-二元关系与抽象数据类型_15808469.pdf

2010-2011春季学期数据结构课程讲义 基础数据结构 吴 及 wuji_ee@tsinghua.edu.cn 清华大学电子工程系 2011年3月 内容提要  二元关系与抽象数据类型  线性表 栈与队列  串 树与二叉树  图 数据与算法 2 吴及 电子工程系 内容提要  二元关系与抽象数据类型  线性表 栈与队列  串 树与二叉树  图 数据与算法 3 吴及 电子工程系 二元关系  集合的笛卡尔积     M x N y  集合M ，N ：  集合M和N的笛卡尔积,记作: M ×N , 定义为:    M N  x, y | x M且y N  例: M ={ a , a } ，N ={ 0, 1, 2 } 则: 1 2  M ×N ={ (a , 0), (a , 1), (a , 2), (a , 0), (a , 1), (a , 2) } 1 1 1 2 2 2 数据与算法 4 吴及 电子工程系 二元关系  定义：设有集合M、N , M ×N的仸意一个子集 R M N 称为 M到N的一个二元关系；  二元关系表示了集合M 和集合N中元素间的某种相关性。    若 a, b R ，则称a为R的前件，b称为R的后件 R  M M  如果M ＝N ，则 称为M上的二元关系 数据与算法 5 吴及 电子工程系 二元关系  例如某学生学习语文,数学,外语, 表示为M ＝{语文,数学,外语}  功课的成绩分四个等级,记作N ＝{A,B,C,D}  该生成绩的全部可能为： M ×N ＝{ 语文, A ,语文, B,语文, C,语文, D, 数学, A ,数学, B,数学, C,数学, D, 外语, A ,外语, B,外语, C,外语, D