最新北京师范大学数据结构教学资料 第6章——集合与字典ppt课件.ppt
《最新北京师范大学数据结构教学资料 第6章——集合与字典ppt课件.ppt》由会员分享,可在线阅读,更多相关《最新北京师范大学数据结构教学资料 第6章——集合与字典ppt课件.ppt(167页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、北京师范大学数据结构教学资北京师范大学数据结构教学资料料 第第6章章集合与字典集合与字典2 2集合及其表示集合及其表示n集合是成员集合是成员( (元素元素) )的一个群集。集合中的成的一个群集。集合中的成员可以是原子员可以是原子( (单元素单元素) ),也可以是集合。,也可以是集合。n集合的成员必须互不相同。集合的成员必须互不相同。n在算法与数据结构中所遇到的集合,其单元在算法与数据结构中所遇到的集合,其单元素通常是整数、字符、字符串或指针,且同素通常是整数、字符、字符串或指针,且同一集合中所有成员具有相同的数据类型。一集合中所有成员具有相同的数据类型。n例:例:colour = red, o
2、range, yellow, green, black, blue, purple, white 集合基本概念集合基本概念9 9 bool subSet (bitSet& R); /判this是否R的子集 bool operator = (bitSet& R); /判集合this与R相等 friend istream& operator (istream& in, bitSet& R); /输入 friend ostream& operator (ostream& out, bitSet& R); /输出private: int setSize;/集合大小 int vecterSize;/位数
3、组大小 unsigned short *bitVector; /存储集合元素的位数组;1010使用示例使用示例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, 1, , 611 1
4、1/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, 两集合不等1212构造函数的实现构造函数的实现template bitSet:bitSet (int sz) : setSize (sz) /构造函数 assert (setSize 0); /检查
5、参数的合理性 vectorSize = (setSize+15) 4;/存储数组大小 bitVector = new int vectorSize;/分配空间 assert (bitVector != NULL);/检查存储分配是否成功 for (int i = 0; i vectorSize; i+) bitVectori = 0;/初始化;1313template bitSet:bitSet (const bitSet& R) /复制构造函数 setSize = R.setSize; /集合元素个数 vectorSize = R.vectorSize; /存储数组大小 bitVector
6、= new int vectorSize; /分配空间 assert (bitVector != NULL); /检查存储分配是否成功 for (int i = 0; i vectorSize; i+) /初始化 bitVectori = R.bitVectori;1414映射函数的实现映射函数的实现template int bitSet:getMember (const T x) /读取集合元素x int ad = x/16, id = x%16; /计算数组元素下标 unsigned short elem = bitVector ad;/取x所在数组元素 return int (elem
7、(15-id) & 1);/取第id位的值;1515template void bitSet:putMember (const T x, int v) /将值v送入集合元素x int ad = x/16, id = x%16; /计算数组元素下标 unsigned short elem = bitVector ad; /取x所在数组元素 unsigned short temp = elem (15-id); /右移,该位移至末尾 elem = elem (id + 1); if (temp%2 = 0 & v = 1) temp = temp+1; /根据v的值,修改该位 else if (t
8、emp%2 = 1 & v = 0) temp = temp-1; bitVectorad = (temp (id + 1); ;1616thisRtemp0 1 1 1 0 0 0 0 1 1 00 0 1 0 0 1 0 1 0 1 00 1 1 1 0 1 0 1 1 1 0thisRtemp0 1 1 1 0 0 0 0 1 1 00 0 1 0 0 1 0 1 0 1 00 0 1 0 0 0 0 0 0 1 0thisRtemp0 1 1 1 0 0 0 0 1 1 00 0 1 0 0 1 0 1 0 1 00 1 0 1 0 0 0 0 1 0 0集合的并集合的并集合的交集合的
9、交集合的差集合的差1717template bool bitSet:addMember (const T x) assert (x = 0 & x setSize); if (getMember(x) = 0) putMember(x, 1); return true; return false;template bool bitSet:delMember (const T x) assert (x = 0 & x setSize);1818 if (getMember(x) = 1) putMember(x, 0); return true; return false;templatebit
10、Set bitSet: /求集合this与R的并operator + (const bitSet& R) assert (vectorSize = R.vectorSize); bitSet temp (setSize);1919 for (int i = 0; i vectorSize; i+) temp.bitVectori = bitVectori | R.bitVectori; return temp; /按位求或, 由第三个集合返回;template bitSet bitSet: /求集合this与R的交operator * (const bitSet& R) assert (vec
11、torSize = R.vectorSize); bitSet temp (setSize); for (int i = 0; i vectorSize; i+) temp.bitVectori = bitVectori & R.bitVectori; return temp; /按位求“与”, 由第三个集合返回2020;template bitSet bitSet:/求集合this与R的差operator - (const bitSet& R) assert (vectorSize = R.vectorSize); bitSet temp (setSize); for (int i = 0;
12、 i vectorSize; i+) temp.bitVectori = bitVectori & !R.bitVectori; return temp;/由第三个集合返回;2121template bool bitSet:subSet (bitSet& R) /判this是否R的子集 assert (setSize = R.setSize); for (int i = 0; i vectorSize; i+) /按位判断 if (bitVectori & !R.bitVectori) return false; return true;thisR0 0 1 1 1 0 1 0 1 1 00
13、0 1 1 1 0 0 1 0 1 01 1 0 0 0 1 1 0 1 0 1 2222thisR0 0 1 1 0 0 0 0 1 1 00 0 1 0 0 1 0 1 0 1 0itemplate bool bitSet:operator = (bitSet& R) /判集合this与R相等 if (vectorSize != R.vectorSize) return false; for (int i = 0; i vectorSize; i+) if (bitVectori != R.bitVectori) return false; return true;/对应位全部相等;232
14、3用带表头结点的有序链表表示集合用带表头结点的有序链表表示集合firstfirst081723354972用有序链表实现集合抽象数据类型用有序链表实现集合抽象数据类型n用有序链表来表示集合时,链表中的每个结用有序链表来表示集合时,链表中的每个结点表示集合的一个成员。点表示集合的一个成员。n各结点所表示的成员各结点所表示的成员 e0, e1, , en 在链表中按在链表中按升序排列,即升序排列,即 e0 e1 en。n集合成员可以无限增加。因此,用有序链表集合成员可以无限增加。因此,用有序链表可以表示无穷全集合的子集。可以表示无穷全集合的子集。2424集合的有序链表类的定义集合的有序链表类的定义
15、template struct SetNode /集合的结点类定义 T data;/每个成员的数据 SetNode *link;/链接指针 SetNode() : link (NULL);/构造函数 SetNode (const T& x, SetNode *next = NULL) : data (x), link (next);/构造函数;template class LinkedSet /集合的类定义2525private: SetNode *first, *last; /有序链表表头指针, 表尾指针public: LinkedSet () first = last = new SetN
16、ode; LinkedSet (LinkedSet& R);/复制构造函数 LinkedSet () makeEmpty(); delete first; void makeEmpty();/置空集合 bool addMember (const T& x); bool delMember (const T& x); LinkedSet& operator = (LinkedSet& R); LinkedSet operator + (LinkedSet& R);2626 LinkedSet operator * (LinkedSet& R); LinkedSet operator - (Lin
17、kedSet& R); bool Contains (const T x);/判x是否集合的成员 bool operator = (LinkedSet& R);/判集合this与R相等 bool Min (T& x);/返回集合最小元素的值 bool Max (T& x);/返回集合最大元素的值 bool subSet (bitSet& R); /判this是否R的子集;2727集合的加入和删除操作集合的加入和删除操作template bool LinkedSet:addMember (const T& x) /把新元素x加入到集合之中 SetNode *p = first-link, *pr
18、e = first; while (p != NULL & p-data link; if (p != NULL & p-data = x) return false; /集合中已有此元素, 不加入 SetNode *s = new SetNode(x); /创建结点 s-link = p; pre-link = s; /链入2828 if (p = NULL) last = s;/链到链尾时改链尾指针 return true;template bool LinkedSet:delMember (const T& x) /把集合中成员x删去 SetNode *p = first-link, *
19、pre = first; while (p != NULL & p-data link; if (p != NULL & p-data = x) /找到,可删 pre-link = p-link; /重新链接2929表示集合的几个重载函数表示集合的几个重载函数 if (p = last) last = pre;/删链尾时改尾指针 delete p; /删除含x结点 return true; else return false;/集合中无此元素;template LinkedSet LinkedSet:operator + (LinkedSet& R) /求集合this与集合R的并3030 Se
20、tNode *pb = R.first-link; /R扫描指针 SetNode *pa = first-link;/this扫描指针 LinkedSet temp;/创建空链表 SetNode *p, *pc = temp.first; /结果存放指针 while (pa != NULL & pb != NULL) if (pa-data = pb-data) /两集合共有 pc-link = new SetNode(pa-data); pa = pa-link; pb = pb-link; else if (pa-data data) /this元素值小 pc-link = new Set
21、Node(pa-data); pa = pa-link;3131 else /R集合元素值小 pc-link = new SetNode(pb-data); pb = pb-link; pc = 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; 3232 pc-link = NULL; temp.last = pc; /链表收尾 return tem
22、p;;firstR.first08172349temp.first231735papbpc08172335493333bool LinkedSet:operator = (LinkedSet& R) SetNode *pb = R.first-link; SetNode *pa = first-link; while (pa != NULL & pb != NULL) if (pa-data = pb-data) pa = pa-link; pb = pb-link; else return false; /扫描途中不等时退出 if (pa != NULL | pb != NULL) retu
23、rn false; /链不等长时, 返回0 return true;3434等价关系与等价类等价关系与等价类(Equivalence Class)(Equivalence Class)等价类与并查集等价类与并查集n在求解实际应用问题时常会遇到等价类问题。在求解实际应用问题时常会遇到等价类问题。n从数学上看,等价类是对象(或成员)的集合,从数学上看,等价类是对象(或成员)的集合,在此集合中所有对象应满足等价关系。在此集合中所有对象应满足等价关系。n若用符号若用符号“ ”表示集合上的等价关系,则对表示集合上的等价关系,则对于该集合中的任意对象于该集合中的任意对象x, y, z,下列性质成立:,下列
24、性质成立:u自反性:自反性:x x (即等于自身即等于自身)。u对称性:若对称性:若 x y, 则则 y x。u传递性:若传递性:若 x y且且 y z, 则则 x z。3535确定等价类的方法确定等价类的方法n因此,等价关系是集合上的一个自反、对称、因此,等价关系是集合上的一个自反、对称、传递的关系。传递的关系。n“相等相等”(=)就是一种等价关系,它满足上述就是一种等价关系,它满足上述的三个特性。的三个特性。n一个集合一个集合 S 中的所有对象可以通过等价关系划中的所有对象可以通过等价关系划分为若干个互不相交的子集分为若干个互不相交的子集 S1, S2, S3, ,它,它们的并就是们的并就
25、是 S。这些子集即为等价类。这些子集即为等价类。n确定等价类的方法分两步走确定等价类的方法分两步走3636 读入并存储所有的等价对读入并存储所有的等价对( i, j );标记和输出所有的等价类。标记和输出所有的等价类。 void equivalence ( ) 初始化初始化; while ( 等价对未处理完等价对未处理完 ) 读入下一个等价对读入下一个等价对 ( i, j ); 存储这个等价对存储这个等价对 ; 输出初始化输出初始化; for ( 尚未输出的每个对象尚未输出的每个对象 ) 输出包含这个对象的等价类输出包含这个对象的等价类 ;3737n给定集合给定集合 S = 0, 1, 2,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最新北京师范大学数据结构教学资料 第6章集合与字典ppt课件 最新 北京师范大学 数据结构 教学 资料 集合 字典 ppt 课件
限制150内