2019数据结构电子教案-深圳大学-自动化课件-ds-06.ppt
《2019数据结构电子教案-深圳大学-自动化课件-ds-06.ppt》由会员分享,可在线阅读,更多相关《2019数据结构电子教案-深圳大学-自动化课件-ds-06.ppt(175页珍藏版)》请在三一文库上搜索。
1、1,第六章 集合与字典,数据结构电子教案,殷人昆 王 宏,2,集合及其表示 并查集与等价类 字典 跳表 散列,第六章 集合与字典,3,集合及其表示,集合是成员(元素)的一个群集。集合中的成员可以是原子(单元素),也可以是集合。 集合的成员必须互不相同。 在算法与数据结构中所遇到的集合,其单元素通常是整数、字符、字符串或指针,且同一集合中所有成员具有相同的数据类型。 例:colour = red, orange, yellow, green, black, blue, purple, white ,集合基本概念,4,集合中的成员一般是无序的,但在表示它时,常写在一个序列里。 常设定集合中的单元素
2、具有线性有序关系,此关系可记作“”,表示“优先于”。 整数、字符和串都有一个自然线性顺序。指针也可依据其在序列中安排的位置给予一个线性顺序。 在某些集合中保存实际数据值,某些集合中保存标示元素是否在集合中的指示信息。如学校开设的所有课程的编码属于前者,一个学期开设的课程构成的集合属于后者。,5,AB 或 A+B AB 或 AB A-B,A,A,A,B,B,B,集合(Set)的抽象数据类型,template class Set public: virtual Set() = 0; /构造函数 virtual makeEmpty() = 0; /置空集合 virtual bool addMembe
3、r (const T x) = 0;,6,virtual bool delMember (const T x) = 0; virtual Set intersectWith (Set,7,用位向量实现集合抽象数据类型,当集合是全集合 0, 1, 2, , n 的一个子集,且 n 是不大的整数时,可用位(0, 1)向量来实现集合。 当全集合是由有限个可枚举的成员组成时,可建立全集合成员与整数 0, 1, 2, 的一一对应关系,用位向量来表示该集合的子集。 一个二进位两个取值1或0,分别表示在集合与不在集合。如果采用16位无符号短整数数组bitVector 作为集合的存储,就要考虑如何求出元素 i
4、 在bitVector数组中的相应位置。,8,集合的位向量(bit Vector)类的定义,#include #include const int DefaultSize = 50; class bitSet /用位向量来存储集合元素, 集合元素的范围在0到 /setSize-1之间。数组采用16位无符号短整数实现 public: bitSet (int sz = DefaultSize); /构造函数 bitSet (const bitSet /取集合元素x,9,void putMember (const T x, int v); /改集合元素x void makeEmpty () /置空集
5、合 for (int i = 0; i /判x是否集合this的成员,10,bool subSet (bitSet,11,使用示例,Set s1, s2, s3, s4, s5; int index, equal; for (int k = 0; k 10; k+) /集合赋值 s1.AddMember (k); s2.AddMember(k+7); /s1: 0, 1, 2, , 9, s2: 7, 8, 9, , 16 s3 = s1+s2; /求s1与s2的并 0, 1, , 16 s4 = s1*s2; /求s1与s2的交 7, 8, 9 s5 = s1-s2; /求s1与s2的差 0
6、, 1, , 6,12,/s1: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 index = s1.SubSet (s4); /判断s1是否为s4子集 cout index endl; /结果,index = 0 /s1: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 /s4: 7, 8, 9 equal = s1 = s2; /集合s1与s2比较相等 cout equal endl; /为0, 两集合不等,13,构造函数的实现,template bitSet:bitSet (int sz) : setSize (sz) /构造函数 assert (setSize 0
7、); /检查参数的合理性 vectorSize = (setSize+15) 4; /存储数组大小 bitVector = new int vectorSize; /分配空间 assert (bitVector != NULL); /检查存储分配是否成功 for (int i = 0; i vectorSize; i+) bitVectori = 0; /初始化 ;,14,template bitSet:bitSet (const bitSet,15,映射函数的实现,template int bitSet:getMember (const T x) /读取集合元素x int ad = x/16
8、, id = x%16; /计算数组元素下标 unsigned short elem = bitVector ad; /取x所在数组元素 return int (elem (16-id) % 1); /取第id位的值 ;,16,template void bitSet:putMember (const T x, int v) /将值v送入集合元素x int ad = x/16, id = x%16; /计算数组元素下标 unsigned short elem = bitVector ad; /取x所在数组元素 int temp = elem (16-id); /右移,该位移至末尾 if (te
9、mp%2 = 0 ,17,template bool bitSet:addMember (const T x) assert (x = 0 ,18,if (getMember(x) = 1) putMember(x, 0); return true; return false; ; template bitSet bitSet: /求集合this与R的并 operator + (const bitSet,19,for (int i = 0; i bitSet bitSet: /求集合this与R的交 operator * (const bitSet /按位求“与”, 由第三个集合返回,20,;
10、 template bitSet bitSet: /求集合this与R的差 operator - (const bitSet,21,集合的并,集合的交,集合的差,22,template bool bitSet:subSet (bitSet,23,template bool bitSet:operator = (bitSet,24,用带表头结点的有序链表表示集合,用有序链表实现集合抽象数据类型,用有序链表来表示集合时,链表中的每个结点表示集合的一个成员。 各结点所表示的成员 e0, e1, , en 在链表中按升序排列,即 e0 e1 en。 集合成员可以无限增加。因此,用有序链表可以表示无穷全
11、集合的子集。,25,集合的有序链表类的定义,template struct SetNode /集合的结点类定义 T data; /每个成员的数据 SetNode *link; /链接指针 SetNode() : link (NULL); /构造函数 SetNode (const T template class LinkedSet /集合的类定义,26,private: SetNode *first, *last; /有序链表表头指针, 表尾指针 public: LinkedSet () first = last = new SetNode; LinkedSet (LinkedSet,27,L
12、inkedSet operator * (LinkedSet,28,集合的加入和删除操作,template bool LinkedSet:addMember (const T /链入,29,if (p = NULL) last = s; /链到链尾时改链尾指针 return true; ; template bool LinkedSet:delMember (const T /重新链接,30,表示集合的几个重载函数,if (p = last) last = pre; /删链尾时改尾指针 delete p; /删除含x结点 return true; else return false; /集合中
13、无此元素 ; template LinkedSet LinkedSet: operator + (LinkedSet& R) /求集合this与集合R的并,31,SetNode *pb = R.first-link; /R扫描指针 SetNode *pa = first-link; /this扫描指针 LinkedSet temp; /创建空链表 SetNode *p, *pc = temp.first; /结果存放指针 while (pa != NULL ,32, else /R集合元素值小 pc-link = new SetNode(pb-data); pb = pb-link; pc =
14、 pc-link; if (pa != NULL) p = pa; /this集合未扫完 else p = pb; /或R集合未扫完 while (p != NULL) /向结果链逐个复制 pc-link = new SetNode(p-data); pc = pc-link; p = p-link; ,33,pc-link = NULL; temp.last = pc; /链表收尾 return temp; ;,34,bool LinkedSet: operator = (LinkedSet,35,等价关系与等价类(Equivalence Class),等价类与并查集,在求解实际应用问题时常
15、会遇到等价类问题。 从数学上看,等价类是对象(或成员)的集合,在此集合中所有对象应满足等价关系。 若用符号“”表示集合上的等价关系,则对于该集合中的任意对象x, y, z,下列性质成立: 自反性:x x (即等于自身)。 对称性:若 x y, 则 y x。 传递性:若 x y且 y z, 则 x z。,36,确定等价类的方法,因此,等价关系是集合上的一个自反、对称、传递的关系。 “相等”(=)就是一种等价关系,它满足上述的三个特性。 一个集合 S 中的所有对象可以通过等价关系划分为若干个互不相交的子集 S1, S2, S3, ,它们的并就是 S。这些子集即为等价类。 确定等价类的方法分两步走:
16、,37,读入并存储所有的等价对( i, j ); 标记和输出所有的等价类。 void equivalence ( ) 初始化; while ( 等价对未处理完 ) 读入下一个等价对 ( i, j ); 存储这个等价对 ; 输出初始化; for ( 尚未输出的每个对象 ) 输出包含这个对象的等价类 ; ,38,给定集合 S = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ,及如下等价对: 0 4, 3 1, 6 10, 8 9, 7 4, 6 8, 3 5, 2 11, 11 0 进行归并的过程为: 初始0,1,2,3,4,5,6,7,8,9,10,11 0 4 0
17、,4,1,2,3,5,6,7,8,9,10,11 3 1 0,4,1,3,2,5,6,7,8,9,10,11 6 10 0,4,1,3,2,5,6,10,7,8,9,11 8 9 0,4,1,3,2,5,6,10,7,8,9,11 7 4 0,4,7,1,3,2,5,6,10,8,9,11,39,0,4,7,1,3,2,5,6,10,8,9,11 6 8 0,4,7,1,3,2,5,6,8,9,10,11 3 5 0,4,7,1,3,5,2,6,8,9,10,11 2 11 0,4,7,1,3,5,2,11,6,8,9,10 11 0 0,2,4,7,11,1,3,5,6,8,9,10 设等价
18、对个数为m, 对象个数为n。一种可选的存储表示为单链表。 可为集合的每一对象建立一个带表头结点的,确定等价类的链表方法,40,单链表,并建立一个一维的指针数组 seqn 作为各单链表的表头结点向量。 seqi 是第 i 个单链表的表头结点, 第 i 个单链表中所有结点的 data 域存放在等价对中与 i 等价的对象编号。 当输入一个等价对 (i, j) 后, 就将集合元素 i 链入第 j 个单链表,且将集合元素 j 链入第 i 个单链表。 在输出时设置一个布尔数组 outn,用 outi 标记第 i 个单链表是否已经输出。,41,算法的输出从编号 i = 0 的对象开始, 对所有的对象进行检测
19、。 在 i = 0 时, 循第0个单链表先找出形式为(0, j)的等价对, 把 0 和 j 作为同一个等价类输出。,42,再根据等价关系的传递性, 找所有形式为( j, k)的等价对,把 k 也纳入包含 0 的等价类中输出。如此继续,直到包含 0 的等价类完全输出为止。 接着再找一个未被标记的编号, 如 i = 1,该对象将属于一个新的等价类,再用上述方法划分、标记和输出这个等价类。 在算法中使用了一个栈。每次输出一个对象编号时,都要把这个编号进栈,记下以后还要检测输出的等价对象的单链表。,43,等价类链表的定义,struct ListNode /定义链表结点类 int data; /结点数据
20、 ListNode *link; /结点链指针 ListNode (int d) data = d; link = NULL; ; typedef ListNode *ListNodePtr; void equivalence () ifstream inFile (“equiv.in”, ios:in); /输入文件 if (!inFile) cerr “不能打开输入文件“ endl; exit (1); ,44,typedef ListNode *ListNodePtr; 建立等价类算法 (输入等价对并输出等价类) 每当一个对象的单链表检测完,就需要从栈中退出一个指针,以便继续输出等价类中
21、的其它对象。如果栈空,说明该等价类所有对象编号都已输出,再找一个使得 outi = False 的最小的 i,标记并输出下一个等价类。 void equivalence ( ) ifstream inFile ( “equiv.in“, ios:in ); /输入文件,45,int i, j, n; inFile n; /读入对象个数 seq = new ListNodePtrn; out = new Booleann; /初始化seq和out for (i = 0; i i j; /输入等价对 (i, j) while (inFile.good () /文件结束出循环 x = new Lis
22、tNode(j); /创建结点 j x-link = seqi; seqi = x; /链入第 i 个链表 y = new ListNode(i); /创建结点 i y-link = seqj; seqj = y; /链入第 j 个链表,46, for (i = 0; i data; /成员j if (outj = false) /未输出, 输出 cout “,” j; outj=true;,47,ListNode *y = x-link; x-link = top; top = x; /x进栈 x = y; /x进到链表下一个结点 else x = x-link; /已输出过,跳过 if (
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2019 数据结构 电子 教案 深圳大学 自动化 课件 ds 06
链接地址:https://www.31doc.com/p-2781839.html