《六章节集合与字典》由会员分享，可在线阅读，更多相关《六章节集合与字典（138页珍藏版）》请在金锄头文库上搜索。
1、第六章 集合与字典赵建华南京大学计算机系栓陪孺彭辫楷晰扩蹲墓凌捞家扛雄反邦吉虫兔唇凯造蛰趴猴棋槛狮咯郊灼六章节集合与字典六章节集合与字典内容集合及其表示并查集与等价类字典跳表散列票代煽着循惮炕葡如滔玖始呐立睫绊贱棋听壮金叭遣排孽觅窍捕捻凉育脖六章节集合与字典六章节集合与字典集合的基本概念具有某种共同性质具有某种共同性质”的若干不同的对象合在一起的若干不同的对象合在一起构成集合构成集合。在算法与数据结构中所遇到的集合中所有成员在算法与数据结构中所遇到的集合中所有成员具有相同的数据类型。具有相同的数据类型。例如：例如：colour = red, orange, yellow, green, bla
2、ck, blue, purple, white 蠢腥惋羡窝兑椒炭靴檬度诡涌铬佩祭项几揩殊打姚加踊船礼蜜扳除牌弱尝六章节集合与字典六章节集合与字典一些说明作为数据结构中的集合在概念上讲，元素之间是无序的。但是可能为了效率，在实现中将元素之间的某个序关系和元素的存储方式对应起来；不同的表示方法：保存实际数据值保存下标或者reference在父集中存放指示信息，表示是否在子集合内。允许相同元素多次出现的称为多重集合或者包。革脱仗斟侩浇撇穆柳先妓询匈镀歉炒巷盐夏拒夺骡讳钓掳轴崔嚏渍炭荚淡六章节集合与字典六章节集合与字典集合的运算还包括：判断一个元素是否在集合中集合是否为空A是否为B的子集以及添加/删除
3、元素等操作遍历所以元素求满足某个条件的所有元素组成的子集A B 或 A+B A B 或 A B A- -BAAABBB汰逆剑匹钳观桩萤赂匀慌喘穿贸耍桔爬桩钙扑趋代扩勿腾咬射依澳确琶吭六章节集合与字典六章节集合与字典集合（Set）的抽象数据类型template class Set public: virtual Set() = 0; /构造函数 virtual makeEmpty() = 0; /置空集合 virtual bool addMember (const T x) = 0; virtual bool delMember (const T x) = 0; virtual Set inte
4、rsectWith (Set& R) = 0;/集合的交运算 virtual Set unionWith (Set& R) = 0; /集合的并运算 virtual Set differenceFrom (Set& R) = 0; /集合的差运算 virtual bool Contains (T x) = 0; virtual bool subSet (Set& R) = 0; virtual bool operator = (Set& R) = 0; /判集合是否相等;眼尺朵莹释崖化踏睫莽饭钻幂殿峡远耪措蔼数涕刊酉豺首泽咏局筛芬铅涣六章节集合与字典六章节集合与字典集合的位向量实现当集合是全集
5、合 0,1,2,n 的一个子集，且n是不大的整数时，可用位(0,1)向量来实现集合。对于每个i，有一个二进位；取值1或0分别表示在集合与不在集合中。如果n小于32，可以直接用32位整数表示；否则可以使用整数数组表示。当全集合是由有限个可枚举的成员组成时，可建立全集合成员与整数0,1,2,的一一对应关系，然后用位向量来表示该集合的子集。如果全集用数组表示，那么其子集也可以用位向量表示。但是，此时需要保证全集不改变。瀑袖兵岸淄狡绎政枪冻坤椒吩惰辕哭氓燃世焰凄幽蛀屉疾湛萤昭鹤奈喂硷六章节集合与字典六章节集合与字典位向量集合的类定义#include #include const int Default
6、Size = 50;class bitSet /用位向量来存储集合元素, 集合元素的范围在0到/setSize-1之间。数组采用16位无符号短整数实现 int setSize;/集合大小 int vecterSize;/位数组大小 unsigned short *bitVector;/bitVectori的第j位为0/1表示第i*16+j个元素是否在此集合内。瘁灶管脊辽涉蝶欢衙铃抚闻川暴欣纸晶汉斌漆亦油虏炯技善凶龋找睡堑陋六章节集合与字典六章节集合与字典位向量集合的类定义（二）public: bitSet (int sz = DefaultSize);/构造函数 bitSet (const b
7、itSet & R);/复制构造函数 bitSet () delete bitVector; /析构函数 int getMember (const int x);/取集合元素x void putMember (const int x, int v); /改集合元素x void makeEmpty () /置空集合 for (int i = 0; i vectorSize; i+) bitVectori = 0; bool addMember (const int x);/加入新成员x bool delMember (const int x);/删除老成员x吕卡恕符需以坊争嚏涎俗藐路窖菲侈鸽艾屑
8、墙脆铅挺演氰榴六矿奄伤蔬锨六章节集合与字典六章节集合与字典位向量集合的类定义（三）bitSet& operator = (const bitSet & R); bitSet operator + (const bitSet & R); bitSet operator * (const bitSet & R); bitSet operator - (const bitSet & R); bool Contains (const int x);bool subSet (bitSet& R); /判this是否R的子集 bool operator = (bitSet& R); /判集合this与R相
9、等 friend istream& operator (istream& in, bitSet& R); /输入 friend ostream& operator 0); /检查参数的合理性 vectorSize = (setSize+15) /16; /vectorSize*16必须大于setSize bitVector = new int vectorSize;/分配空间 assert (bitVector != NULL);/检查存储分配是否成功 for (int i = 0; i vectorSize; i+) bitVectori = 0;/初始化为空集;寅碉庇戍辑嚣呕停候噬赤艘贴裴
10、赂恒汇匙攻尽偏邵蒲糟键亦咕圆黑椽包搂六章节集合与字典六章节集合与字典复制构造函数bitSet:bitSet (const bitSet& R) /复制构造函数 setSize = R.setSize; /集合元素个数 vectorSize = R.vectorSize; /存储数组大小 bitVector = new int vectorSize; /分配空间 assert (bitVector != NULL); /检查存储分配是否成功 for (int i = 0; i (15-id) &1);/取第id位(从高位算起）的值/上面的表达式判断elem的第id位是否为1;注：第x个元素存放在
11、bitVector的第x/16个元素的（从高位起）第x%16位上。0 1 1 0 0 0 1 0 0 1 0 0 0 1 0 0使剿较均椒奸矿捏铜祝割稗陨野泊肌近圆氢询努衣术早动柒泛嘴亨砌沙蝇六章节集合与字典六章节集合与字典putMember/如如v为为1，将，将x加入集合；（如果加入集合；（如果x在集合中，操作无效果）在集合中，操作无效果）/否则将否则将x从集合中删除；（如果从集合中删除；（如果x不在集合中，操作无效果）不在集合中，操作无效果）void bitSet:putMember (const int x, int v) /将值v送入集合元素x int ad = x/16, id =
12、x%16; /计算数组元素下标 unsigned short elem = bitVector ad; /取x所在数组元素 int temp = elem (15-id); /右移,该位移至末尾elem = elem (id+1); /此时elem中包含了后面的16-id位/根据v的值,修改该位if (temp%2 = 0 &v =1) temp=temp + 1 ;else if (temp%2 = 1 & v = 0) temp = temp -1; bitVectorad = (temp (id+1);/送回;0 1 1 0 0 0 1 0 0 1 0 0 0 1 0 0设：id=2；右
13、移后，temp为0000000000000011elem左移后为：0001001000100000站辽掷互活锚州住墨遵授效枝增跌牧瑰亮挛物倚烂硝盂嗽恳更戮拿脉滥月六章节集合与字典六章节集合与字典Add/delete memberbool bitSet:addMember (const int x) assert (x = 0 & x = 0 & x setSize); if (getMember(x) = 1) putMember(x, 0); return true; return false;辑曳篙扭疆悲甘户方肛琵倒韩血彬牢钎厕陛坤傲乏湛处衬瞳犊锌字砖惺疤六章节集合与字典六章节集合与字典另
14、一种实现位集合的方法设立数组：bitArray16=0x8000, 0x4000, 0x2000, 0x1000, 0x0800, 0x0400, 0x0200, 0x0100, 0x0080, 0x0040, 0x0020, 0x0010, 0x0008, 0x0004, 0x0002, 0x0001 判断bitVector的第i个元素的第j位是否为1bitArrayj & bitVectori表示；将bitVector的第i个元素的第j位设置为1bitVectori |= bitArrayj;将bitVector的第i个元素的第j位设置为0bitVectori &= bitArrayj;驼
15、漂寇币硬瞥熄进瓣拜到胶瑰适式棺藉矫嘻怂酱更挖碰亥尝滥饺辜赞重邑六章节集合与字典六章节集合与字典集合的并运算bitSet bitSet: /求集合this与R的并operator + (const bitSet& R) assert (vectorSize = R.vectorSize); bitSet temp (vectorSize); for (int i = 0; i vectorSize; i+) temp.bitVectori = bitVectori | R.bitVectori; return temp; /按位求或, 由第三个集合返回;政姚望钉凑圾陈嫩风粉傅尔况低保描杰辩臀督姚
16、则城襟位麓婪夸仰曙锈拽六章节集合与字典六章节集合与字典集合的交运算/求集合this与R的交bitSet bitSet:operator * (const bitSet& R) assert (vectorSize = R.vectorSize); bitSet temp (vectorSize); for (int i = 0; i vectorSize; i+) temp.bitVectori = bitVectori & R.bitVectori; return temp; /按位求“与”, 由第三个集合返回灿翘奸愉求委技育坪惕苹姜咕燥欣冒拆嫌畜掐梨扔枚勒编涸椎藐废浮姚怨六章节集合与字典六
17、章节集合与字典集合的差运算/求集合this与R的差bitSet bitSet:operator - (const bitSet& R) assert (vectorSize = R.vectorSize); bitSet temp (vectorSize); for (int i = 0; i vectorSize; i+) temp.bitVectori = bitVectori & R.bitVectori; return temp;/由第三个集合返回;孔程美夺蹄撅薯龋恿袭缠讹舰娇试戳崖吊蝶测闹鸦肄磁硬囱鸿诽栏赐嘴鞍六章节集合与字典六章节集合与字典thisRtemp0 1 1 1 0 0
18、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集合的并集合的并集合的交集合的交集合的差集合的差洽敖抒峪猾上臭轴喳廖临厂多敏炎宿七损薯瘫疾巩淬疽蝗牵烙妄曾叠浮炽六章节集合与字典六章节集合与字典集合的子集判断/判this是否R的子集bool bitSet:su
19、bSet (bitSet& 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 0 1 1 1 0 0 1 0 1 01 1 0 0 0 1 1 0 1 0 1 例丈番暴构犯岿仗见巧斑耿珍珍输纸囱彤硒桨课袭疚三总烁擂替枉猛房酪六章节集合与字典六章节集合与字典判断集合相等template bool bitSet:operator = (b
20、itSet& R) /判集合this与R相等 if (vectorSize != R.vectorSize) return false; for (int i = 0; i vectorSize; i+) if (bitVectori != R.bitVectori) return false; return true;/对应位全部相等;thisR0 0 1 1 0 0 0 0 1 1 00 0 1 0 0 1 0 1 0 1 0i俭雕疙棠壬毖营仕殆威便运玄筐硫支哺盐界媳志牲瘸逸氦靖侨觅邹泊礼甄六章节集合与字典六章节集合与字典firstfirst081723354972用有序链表实现集合链表的
21、每个结点存放集合的一个成员。各结点所表示的成员 e0, e1, , en 在链表中按某种顺序排列，即 e0 e1 en。有序链表可以表示无穷全集的子集，集合中的元素个数也没有限制；本课程内使用带有表头结点的有序链表，也可以使用其它的链表形式。曼淋罕绰对变厨掩电破腻幂畏妮酥潍倔妮投开铡长块磨疑策挥瑰渺英释寿六章节集合与字典六章节集合与字典集合的有序链表类的定义（链表结点）template struct SetNode /集合的结点类定义 T data;/每个成员的数据 SetNode *link;/链接指针 SetNode() : link (NULL);/构造函数 SetNode (const
22、 T& x, SetNode *next = NULL) : data (x), link (next);/构造函数;注意：可参照带表头的链表的实现方式注意：可参照带表头的链表的实现方式霄酱莱遇就滦缮裹吞瞎毛酗乳爹侥撂酵何辆冗漂豁叉厂契怀似脆承寝冰讫六章节集合与字典六章节集合与字典集合的有序链表类的定义（链表）集合的有序链表类的定义（链表）template class LinkedSet /集合的类定义private: SetNode *first, *last;/有序链表表头指针, 表尾指针public: LinkedSet () first = last = new SetNode; Li
23、nkedSet (LinkedSet& R);/复制构造函数 LinkedSet () makeEmpty(); delete first; void makeEmpty();/置空集合 bool addMember (const T& x); bool delMember (const T& x); bool Contains (const T x); /判x是否集合的成员 LinkedSet& operator = (LinkedSet& R); LinkedSet operator + (LinkedSet& R); /集合的交、差、相等判断、子集判断运算等运算集合的交、差、相等判断、子
24、集判断运算等运算 bool Min (T& x); bool Max (T& x);/返回集合最大/小元素的值;雹侗堕魄勋汤小萧栓克撤硒咀亏忘熔蔷膝砌与津局碎舀外蛀偏与苟胸拒梭六章节集合与字典六章节集合与字典加入一个元素的操作template bool LinkedSet:addMember (const T& x) /把新元素x加入到集合之中 SetNode *p = first-link, *pre = first; while (p != NULL & p-data link; /注意注意pre的用法的用法，始终有pre-link=p/循循环环退退出出时时，要要么么已已经经扫扫描描到到结
25、结尾尾，要要么么p指指向向的的元元素素大大于于等等于于x/注意：这个结论是因为链表中的元素从小到大排列注意：这个结论是因为链表中的元素从小到大排列 if (p != NULL & p-data = x) return false; /x在集合中, 不加入 SetNode *s = new SetNode(x); /创建结点 s-link = p; pre-link = s; /链入if (p = NULL) last = s;/当当链到链尾时改链尾指针，以保证类不变式成立 return true;d1d2predatas插入时，必然有d1datad2猫拖稿奸坟吹哟官叹罚稗参例欣唇楞吠糙泵摇坎嘻
26、班裕壮应罗绎肮撤渣术六章节集合与字典六章节集合与字典删除一个元素template bool LinkedSet:delMember (const T& x) /把集合中成员x删去 SetNode *p = first-link, *pre = first; while (p != NULL & p-data link;/循循环环退退出出时时，要要么么已已经经扫扫描描到到结结尾尾，要要么么p指指向向的的元元素素大大于于等等于于x/注意：这个结论是因为链表中的元素从小到大排列注意：这个结论是因为链表中的元素从小到大排列 if (p != NULL & p-data = x) /找到,可删pre-l
27、ink = p-link; /重新链接if (p = last) last = pre;/删链尾时改尾指针delete p; /删除含x结点return true; else return false;/集合中无此元素;放鼻帝屏卤深营络酬锦缆河确情慧橙捏羡尚幽梢然哎嘱侠董砷骂迪絮半诧六章节集合与字典六章节集合与字典集合的合并（1）template LinkedSet LinkedSet:operator + (LinkedSet& R) /求集合this与集合R的并SetNode *pb = R.first-link;/R扫描指针SetNode *pa = first-link; /this扫
28、描指针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 SetNode(pa-data);pa = pa-link;/end of else if (pa-data data) ，待续，待续 捕弧今醋狱呼
29、忘恼会做蔓乡历卯獭金麻戈往区关恨淖朝锥壤歇精猎饶军殷六章节集合与字典六章节集合与字典集合的合并（2）else /R集合元素值小pc-link = new SetNode(pb-data);pb = pb-link;/end of elsepc = 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;/end of whilepc-link = N
30、ULL; temp.last = pc; /链表收尾return temp;；回忆一下以前的多项式合并算法：1、一元多项式被表示成为不同次数的项的集合，2、每个项包括系数、指数，且从小到大排列；请考虑几个问题：1、得到的集合仍然是从小到大排列吗？2、既在A中，又在B中的元素会重复出现在并集中吗？惹傈捂辛触腕态诡铱短竣蹦廓匠酱乒棠鲍东糠凉硅鞠谰奸膜星泌兢七口磅六章节集合与字典六章节集合与字典集合并运算的例子firstR.first08172349temp.first231735papbpc0817233549猛独抄淑征杯虾磅耍又艘陆由同佩秧豪霍涧副磋大苛雪边置躺符膀吝恳复六章节集合与字典六章节集
31、合与字典判断集合相等bool 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) return false; /链不等长时, 返回0 return true;车沂撰栖袖六乐哉禽臭挝搭悼彝烧
32、县砌邪屡出忱掐赘潘阵茬辆临触秽憨追六章节集合与字典六章节集合与字典内容集合及其表示并查集与等价类字典跳表散列镇啃午炒挪先元洋锨盆茫陡鲁踩成省骄铂婴顺像父牛刷溉羽品析汰敝肃船六章节集合与字典六章节集合与字典等价关系/等价类l若用符号“”表示集合上的等价关系，则对于该集合中的任意对象x, y, z，下列性质成立：u自反性：x x (即等于自身)。u对称性：若 x y, 则 y x。u传递性：若 x y且 y z, 则 x z。从数学上看，等价类是对象（或成员）的集合，在一个等价类中的各个元素满足等价关系。一个集合上的等价关系将该集合划分成为互不相交的子集。抨弛变租汤周絮淌膜膏彭联飘黎赚毛桐替咋治腊
33、捶含稠蕾鞭律卿近蝉挤拓六章节集合与字典六章节集合与字典并查集（disjoint set）问题高效地建立和表示某个集合上有一个等价关系建立过程如下：已知一个集合S，并且已知一个关系r。这个关系r通过一个二元组集合来表示；等价关系R是r的自反/传递/对称闭包；我们通过逐个读入r中的二元组，高效建立起等价关系R。疡渔俘锰虫好顺咽操脚筹示谩奎哀侗酪壳孤缮醋倾兜碑帝雁恿宁分拱且垄六章节集合与字典六章节集合与字典用途主要用于按照某些已知的等价关系事实，将一个集合中的元素分划成为互不相交的子集。由已知事实推导出等价的两个元素一定在同一子集中。屁寨猩搞主恍胡祷锥雅固户捌高刺沿粗旦候姐拉忘病透聋防帅汐象灯乖窍六
34、章节集合与字典六章节集合与字典等价关系建立的例子l给定集合给定集合 S = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ,l已知已知: 0 4, 3 1, 6 10, 8 9, 7 4, 6 8, 3 5, 2 11, 11 0l归并过程：归并过程：初始初始0,1,2,3,4,5,6,7,8,9,10,110 4 0,4,1,2,3,5,6,7,8,9,10,113 1 0,4,1,3,2,5,6,7,8,9,10,116 10 0,4,1,3,2,5,6,10,7,8,9,118 9 0,4,1,3,2,5,6,10,7,8,9,117 4 0,4,7,1,3,
35、2,5,6,10,8,9,116 8 0,4,7,1,3,2,5,6,8,9,10,113 5 0,4,7,1,3,5,2,6,8,9,10,112 11 0,4,7,1,3,5,2,11,6,8,9,1011 0 0,2,4,7,11,1,3,5,6,8,9,10翅酷啸矮袁蜘叹住墅拱恍豫希黄往抿鸥优搔聊支林斥课迎秃忌缸侠雨唾窥六章节集合与字典六章节集合与字典并查集 (Union-Find Sets)l并查集支持一个有穷集合上的某些操作并查集支持一个有穷集合上的某些操作l并查集支持以下三种操作：并查集支持以下三种操作：u Union (Root1, Root2) /合并操作合并操作u Find
36、 (x) /查找操作查找操作u UFSets (s) /构造函数构造函数l对于并查集来说，分划的每个子集用一棵树表示。也可以对于并查集来说，分划的每个子集用一棵树表示。也可以用树的根结点来用树的根结点来代表代表子集。子集。l子树采用双亲表示法。子树采用双亲表示法。l全集本身可以使用其它数据结构表示。这里我们使用数组全集本身可以使用其它数据结构表示。这里我们使用数组表示，用下标指示元素。表示，用下标指示元素。色盘磊抠鸟复怖蜘身呢复偏本冉哆陕宋轧跌补苇退浮乃快跌畴紊粕联皑榴六章节集合与字典六章节集合与字典S=0,1,2,3,4,5,6,7,8,9S1= 0, 6, 7, 8, S2= 1, 4,
37、9, S3= 2, 3, 5为为简简化化讨讨论论，忽忽略略实实际际的的集集合合名名，仅仅用用表表示示集集合合的的树树的的根根来来标识集合。标识集合。子集名子集名 指针指针0 S11 S22 S30427681935-4000-3-344220 1 2 3 4 5 6 7 8 94 4 3 2 3 2 0 0 0 4格抛利肘喂学陋樱挟月拟呼拖零柠惯唆鼓螟鼻沂讽轴炙徘或订揭禽吟姆冯六章节集合与字典六章节集合与字典n初初始始时时, , 用用构构造造函函数数 UFSets(s)UFSets(s) 构构造造一一个个森森林林, , 每每棵棵树树只只有有一一个个结结点点, , 表表示示集集合合中中各各元元素
38、自成一个子集合。素自成一个子集合。nFind(i)：寻找寻找集合元素集合元素 i所在子树所在子树的根。的根。nFind(i) = Find(j)表明表明i和和j在同一个子集中在同一个子集中nUnion(i, j)：将：将 i 和和 j 所在的子集合并所在的子集合并下标下标下标下标parent- -1 - -1 - -1 - -1 - -1 - -1 - -1 - -1 - -1 - -10 1 2 3 4 5 6 7 8 9鞍咀已朋葱魔潘榨宁丢誓内陪橡超于鼓须寂疲胰无呛撰天恳唱弟疏卑题宵六章节集合与字典六章节集合与字典S1下标下标下标下标parent集合集合 S S1 1, , S S2 2
39、和和 S S3 3 的双亲表示的双亲表示- -4 4 - -3 2 - -3 2 0 0 0 40 1 2 3 4 5 6 7 8 9S2S30768000-4419-344235-322弱旬十铜喇垢锐昂锑祷吐女喊翟厩及申贬榴轮补殆殷办顽楼蒲构距游安巍六章节集合与字典六章节集合与字典S1 S2的可能的表示方法的可能的表示方法下标下标下标下标parent集合集合 S1 S2 和和 S3 的双亲表示的双亲表示- -7 4 - -3 2 0 2 0 0 0 40 1 2 3 4 5 6 7 8 907684194190876-7-7000044444000薛蕊欣疡刚竿关荒犊汹止全抨借铸企锚挫翰着载选
40、艰伴姥结堪沧卵护哀拥六章节集合与字典六章节集合与字典用双亲表示实现并查集的类定义用双亲表示实现并查集的类定义 const int DefaultSize = 10;class UFSets /集合中的各个子集合互不相交public: UFSets (int sz = DefaultSize);/构造函数 UFSets() delete parent; /析构函数 UFSets& operator = (UFSets& R); /集合赋值 void Union (int Root1, int Root2); /子集合并 int Find (int x);/查找x的根 void UnionByHe
41、ight (int Root1, int Root2);/改进例程:压缩高度的合并算法private: int *parent; /集合元素数组(双亲表示) int size; /集合元素的数目;翱篆猛袋狡寺蕾详握舅黍睦币界愈狂僳褒向圾柯军骡厄绦核淌骗艳锄得衬六章节集合与字典六章节集合与字典UFSets:UFSets (int sz) /构造函数：sz 是集合元素个数，双亲数组的/范围为parent0parentsize-1。 size = sz;/集合元素个数 parent = new intsize;/创建双亲数组 for (int i = 0; i size; i+) parenti =
42、 -1; /每个自成单元素集合; 邦熟琼磅荷布囊衣疚迸所豆斌冬慰校积州甭乎拿坊炕燃湘禽解帅势武鼠爹六章节集合与字典六章节集合与字典并查集操作的算法并查集操作的算法 查找查找- - - -5012301234Find (4)Find (3) Find (2)Find (1)Find (0) - -5 0 返回返回 0龋把拼饥腑涌误娱厚剑桶俗减周日管垢柿邯拓乐链忻茧凝蚂弄匪缴高光擂六章节集合与字典六章节集合与字典 -5 0 1 2 3parentParent4 =3 Parent3 =2Parent2 =1Parent1 =0Parent0 =-50 1 2 3 4int UFSets:Find
43、(int x) /函数搜索并返回包含元素x的树的根。/递归版本 if (parentx 0) return x; /根的parent值小于0 else return (Find (parentx);痈承敢寞存缺掏矽潜蹿成抄渤帮缨惧店贾混渠镁隧芒万驶肠庆铺儿垄倪害六章节集合与字典六章节集合与字典Find的非递归版本int UFSets:Find (int x) /函数搜索并返回包含元素x的树的根。 while (parentx 0) x=parentx;returnx;这两个版本都有待改进矿冰恫赎全甸秃嗓颅顿谆盗格懒秸庙臂鳞诅掏杉挛孰挑既婆眠波歪探暇沥六章节集合与字典六章节集合与字典Union的
44、实现void UFSets:Union (int Root1, int Root2) /求两个不相交集合Root1与Root2的并 parentRoot1 += parentRoot2;/注意，root1和root2都是根结点/-parentRoot1表示集合的元素总数 parentRoot2 = Root1;/将Root2连接到Root1下面;删同眩侧棱肘堰噬笛兵癌侥屏蛹城司仪崖藏被倔蛛四恭盎豆盒痹琢菩佃恰六章节集合与字典六章节集合与字典下标下标下标下标parent- -7 4 - -3 2 0 2 0 0 0 40 1 2 3 4 5 6 7 8 90768419-7000044下标下标下
45、标下标parent- -4 4 - -3 2 - -3 2 0 0 0 40 1 2 3 4 5 6 7 8 9稗焉芯吭描骗从瞬错浑股甭拷锯坝蒂畸悉澎衡在闲挣潦四靠庙沃韧残蔗砒六章节集合与字典六章节集合与字典退化情况及其改进Union操作可能引起退化情况：操作可能引起退化情况：假设最初假设最初 n 个元素构成个元素构成 n 棵树组成的森林，棵树组成的森林，parenti = -1。做处理。做处理Union(n-2, n-1), , Union(1, 2), Union(0, 1)后，将产生退化的树。后，将产生退化的树。此时进行此时进行Find的话，平均需要的话，平均需要n/2次查询。次查询。
46、改进的方法：尽量使得树变矮改进的方法：尽量使得树变矮 按树的结点个数合并按树的结点个数合并 按树的高度合并按树的高度合并 压缩元素的路径长度压缩元素的路径长度塞爷诬山谱榆视牢峪拜淀刺复哩午投仇育焙衰酮熙宅渊仓桑属响雅照钢澎六章节集合与字典六章节集合与字典 朴素合并朴素合并- - - -1- - - -1- - - -1- - - -1- - - -10 02 23 34 4- - - -3- - - -50321 13341332202314Union(0,1)- - - -23- - - -41421234Union(1,2)Union(2,3)Union(3,4)艳旗缮临果鹰钡浓涣氨靛撇波
47、缔江驯劈埠偏邻担香足污羊厚琶湿趁椭魂猾六章节集合与字典六章节集合与字典l按树结点个数合并按树结点个数合并结点个数多的树的根结点作根结点个数多的树的根结点作根- - - -1- - - -1- - - -1- - - -1- - - -101234- - - -1- - - -10- - - -7256- - - -5- - - -2223320134 456233020562314Union(2, 0)典莽岛谋郧豹振肪家刑引杀键烦掘剂瓦呛光米姜窄贾斗渡归组寒晨伪尘啸六章节集合与字典六章节集合与字典void UFSets : WeightedUnion (int Root1, int Root2
48、) / /按Union的加权规则改进的算法 int temp = parentRoot1 + parentRoot2; if (parentRoot2 parentRoot1) parentRoot1 = Root2; /Root2中结点数多 parentRoot2 = temp; /Root1指向Root2 else parentRoot2 = Root1; /Root1中结点数多 parentRoot1 = temp; /Root2指向Root1 ;斥净击槽钡磋毙义轩兵日绝郎拂战茫货避阁指拒惕宋醋陇警惑烈缴茵彤随六章节集合与字典六章节集合与字典l按树高度合并按树高度合并 高度高的树的根结点
49、作根高度高的树的根结点作根- - - -1- - - -1- - - -1- - - -1- - - -101234- - - -1- - - -10- - - -3256- - - -3- - - -222332013456233020562314Union(2, 0)桐庐露涅族掐掩锅稼卖樟腿卵缄矮诺正壁胞捶娜堆忌虽根努遂吓睛所早镇六章节集合与字典六章节集合与字典按高度合并注意：在根结点中记录高度，而不是元素个数。void UFSets : WeightedUnion (int Root1, int Root2) / /按Union的加权规则改进的算法，但是按照高度合并 if (parent
50、Root2 = 0; j = parentj); /让 j 循双亲指针走到根 while (parenti != j) /换 parenti 到 j int temp = parenti; parenti = j; i = temp; return j;宵绞皿栓猿属瓷媳壳溉它催齿嘘你验举筐炮郝采界温凶蛇醋澳琼疫抉馋拼六章节集合与字典六章节集合与字典实际例子ML语言的类型推理系统是一个函数式语言。ML语言不需要声明值的类型，且是强类型的。通过合一的方法推导出各个值的类型。x=head(l)得出l是list类型，x是这个list类型的元素类型；m=tail(l)；得出m和l的类型相同；y=x得出y
51、和x是相同的类型；y=2得出y是整数类型，从而推导出x是整数类型；爵男柄设恶礁擅愉卸雕歉牺白醉浩话椰眶芽赔奥廉绷段陷鳖毋全匆盟株蔫六章节集合与字典六章节集合与字典内容集合及其表示集合及其表示并查集与等价类并查集与等价类字典字典跳表跳表散列散列撇垦座酉耸逊雄诌姥弛咎刊暮尉雪头堰丘洲藐斡悼夷幌祁笔缩开戏颁怪寿六章节集合与字典六章节集合与字典字典（字典（DictionaryDictionary） 字典是一些元素的集合，每个元素有一个称作字典是一些元素的集合，每个元素有一个称作关键码（关键码（key）的域，不同元素的关键码互不相）的域，不同元素的关键码互不相同。同。通常以文件（通常以文件（File）或
52、者表格（）或者表格（Table）的方式）的方式出现。出现。在讨论字典抽象数据类型时，把字典定义为在讨论字典抽象数据类型时，把字典定义为对的集合。根据问题的不同，可以为对的集合。根据问题的不同，可以为名字和属性赋予不同的含义。名字和属性赋予不同的含义。从抽象的角度看，字典是一个从名字（或者说从抽象的角度看，字典是一个从名字（或者说Key）到属性的映射（）到属性的映射（MAP）。）。速刊爆惕敖翌姬滑赘巍苯霹何蹭申撇矣苫篆率醇疗敝箱拄望羞破菜诱昌炊六章节集合与字典六章节集合与字典字典的典型操作1.确定一个指定的名字是否在字典中；2.搜索出该名字的属性；3.修改该名字的属性；4.插入一个新的名字及其属
53、性；5.删除一个名字及其属性。瓦蛛窿叼芯隅赢鱼汤午必境址敢忽凯烦赡叁畸王缎项啮票义姑矾婚写馅酋六章节集合与字典六章节集合与字典字典的抽象数据类型字典的抽象数据类型 const int DefaultSize = 26;template class Dictionary /对象: 一组对, 其中, 名字是唯一的public: Dictionary (int size = DefaultSize); /构造函数 bool Member(Name name);/判name是否在字典中 Attribute *Search (Name name); /在字典中搜索关键码与name匹配的表项 甄漆难翠察隘
54、硫喇叹吱厕皂拔筹定翻几扦猴坤伯噬荆躺距锰尚押诣盛梁劈六章节集合与字典六章节集合与字典字典的抽象数据类型（续）字典的抽象数据类型（续） void Insert (Name name, Attribute attr); /若name在字典中, 则修改相应对 /的attr项; 否则插入到字典中void Remove (Name name); /若name在字典中, 则在字典中删除相应的 /对。否则无操作;闰巡幻芋曾蚌姿笼无孪清渺澜废杜褥氢邢酚叠腺陪螟荒坚归啸旷茎淆菲桃六章节集合与字典六章节集合与字典索引项用文件记录（用文件记录（record）或表格的表项）或表格的表项（entry）来表示单个元素时，
55、可以使用）来表示单个元素时，可以使用（key，记录或表项位置，记录或表项位置adr）构成搜索某一指定记录或表项的索引项。构成搜索某一指定记录或表项的索引项。可以通过索引项提高查找效率。可以通过索引项提高查找效率。即技竖戏耐听冯纪办吠碉霸荐喘伟心樱考叁搪印嚎狡套徒帜阜疚搁足艳昧六章节集合与字典六章节集合与字典具有重复元素的字典字典中的元素可以具有相同的关键码（Key）。可能有多个元素具有相同的关键码，需要制定规则消除歧义，使得Find, Remove可以无歧义地执行；也可以Find/Remove所有的元素;死朝馈尧筹钱凄各酚克啡遁婶绸苞姆坯绳徽跺满慌识砸痞平海倒匪难轧篆六章节集合与字典六章节集合
56、与字典字典的线性表描述保存在线性序列 (e1,e2,) 中，其中ei 是字典中的元素，其关键码从左到右依次增大。可以使用有序链表（有序顺序表）结构；每个结点表示字典中的一个元素各个结点按照结点中保存的数据值非递减链接。剂绒钡溶具追甸着滓畸赖中吓叙草刑之晨裙美流召濒辞漏琶踏酮精逸狸清六章节集合与字典六章节集合与字典#include #include “SeqList.h”const int defaultSize = 50;template class SortedList : public SeqList public: int Search (K k1) const; /搜索 void In
57、sert (const K k1, E& e1); /插入 bool Remove (const K k1, E& e1); /删除;有序顺序表的类定义矣积宿箱阐耐幻卖浩钧词西傈盅筐者酱蜗拳添碱绘墓玄升俊磊惹厦卿毯降六章节集合与字典六章节集合与字典基于有序顺序表的顺序搜索算法template int SortedList:Search (K k1) const /顺序搜索关键码为x的数据对象 for (int i = 1; i k1) break; return 0; /顺序搜索失败, 返回失败信息;l算法中的算法中的“=”和和“”都是重载函数，在定都是重载函数，在定义义E时定义它们的实现。时
58、定义它们的实现。彬旦赛画苏驶盯喇耳忧馒哄橇潭啤矗莽梯典窟烁拣绽鸿稚喷亏为绕暮害漆六章节集合与字典六章节集合与字典有序顺序表顺序搜索的时间代价有序顺序表顺序搜索的时间代价搜索算法的时间效率的衡量标准搜索算法的时间效率的衡量标准在搜索过程中关键码平均比较次数，也称为平均在搜索过程中关键码平均比较次数，也称为平均搜索长度搜索长度ASL (Average Search Length)，通常它，通常它是字典中元素总数是字典中元素总数 n 的函数。的函数。设搜索第设搜索第 i 个元素的概率为个元素的概率为 pi, 搜索到第搜索到第 i 个个元素所需比较次数为元素所需比较次数为 ci, 则搜索成功的平均则搜
59、索成功的平均搜索长度搜索长度：（只考虑了搜索成功的情况）（只考虑了搜索成功的情况）螺熄昏八谴痰热细锄涵侣芍稼卞釜垒塑烤虐鲁廓恫赣貌裙芳鲜躬暗吾碳雇六章节集合与字典六章节集合与字典在顺序搜索情形，搜索第在顺序搜索情形，搜索第 i (1in) 个元个元素需要比较素需要比较 i 次，假定按等概率搜索各元素：次，假定按等概率搜索各元素：这与一般顺序表情形相同。但搜索不成功时这与一般顺序表情形相同。但搜索不成功时不需一直比较到表尾，只要发现下一个元素不需一直比较到表尾，只要发现下一个元素的值比给定值大，就可断定搜索不成功。的值比给定值大，就可断定搜索不成功。惜琵蓖眺莽搪肥娟雕贷袁曳兰豢筷卢意慨孜懂乒袖舔
60、灾引乞泛凄妇擎纺你六章节集合与字典六章节集合与字典基于有序顺序表的折半搜索基于有序顺序表的折半搜索l设设 n 个元素存放在一个有序顺序表中。个元素存放在一个有序顺序表中。l折折半半搜搜索索时时, 先先求求位位于于搜搜索索区区间间正正中中的的元元素素的下标的下标mid，用其关键码与给定值，用其关键码与给定值 x 比较比较:l datamid.key = x，搜索成功；，搜索成功；l datamid.key x，把把搜搜索索区区间间缩缩小小到到表表的的前半部分前半部分，继续折半搜索；，继续折半搜索；l datamid.key x，把把搜搜索索区区间间缩缩小小到到表表的的后半部分后半部分，继续折半搜
61、索。，继续折半搜索。l如如果果搜搜索索区区间间已已缩缩小小到到一一个个对对象象，仍仍未未找找到到想要搜索的对象，则搜索失败。想要搜索的对象，则搜索失败。琴孟泊羡它擂辑囊挎虑纲肇典锗丈植酮船咳倪幅反阴鲸膝臼垣摸述纠含斯六章节集合与字典六章节集合与字典搜索成功的例子搜索成功的例子- -1 0 1 3 4 6 8 10 1260 1 2 3 4 5 6 7 8搜索搜索给定值给定值lowmidhigh6 6 8 10 125 6 7 8low midhigh665low mid high6暗源芭尔胳够伶谭攫郁惨痕拳峦脖咖滚忿桩睬优斧映器番灼轨肺占囚葬豫六章节集合与字典六章节集合与字典搜索失败的例子搜索
62、失败的例子- -1 0 1 3 4 6 8 10 1250 1 2 3 4 5 6 7 8搜索搜索给定值给定值lowmidhigh5 6 8 10 125 6 7 8low midhigh655low mid high5蜡毖纽撼咸纵集腿朴基符惺蹄锑撇么冒体顶凯谊申醒冯瓢寄葵宜劫巷阶少六章节集合与字典六章节集合与字典templateint SortedList:BinarySearch (K k1, const int low, const int high ) const /折半搜索的递归算法，用到E的重载操作“” int mid = 0; /元素序号从1开始 if (low = high)
63、mid = (low + high) / 2; if (datamid-1 k1) mid = BinarySearch (k1, low, mid -1); return mid;注：这个递归算法是一个尾递归，可以转化为迭代注：这个递归算法是一个尾递归，可以转化为迭代祖樊垄貉懂城讥沙坯雌要幸几吭涸匣丹希饯接屿父铀祷字簧露腕诌殉蠕黑六章节集合与字典六章节集合与字典字典的有序链表实现字典的有序链表实现#include template struct ChainNode /链表结点类定义 E data; ChainNode *link; ChainNode() : link (NULL) ; /构
64、造函数 ChainNode (E& e1, /构造函数 ChainNode *next = NULL) : data (e1), link (next) ;眷夯关蚁谱摩诱神但寝郝绪击策府员炮萤佛蹦挽殷提着丙惭第峻卓捉懦簧六章节集合与字典六章节集合与字典template class SortedChain /有序链表类定义private: ChainNode *first;/链表的头指针public: SortedChain () /构造函数 first = new ChainNode; assert (first != NULL); ; SortedChain ();/析构函数世暮试驶渤运涅岗
65、蛰煞称摈呼答毅延娜改朵臀魂六缩盲的旷匹焦钾瓣令缆六章节集合与字典六章节集合与字典 ChainNode *Search (K k1); /搜索 void Insert (const K k1, E& e1); /插入 bool Remove (const K k1, E& e1); /删除 /用于遍历的接口；用于遍历的接口；ChainNode *Begin () return first-link; /定位第一个 ChainNode *Next (ChainNode *current) const /定位下一个 return (current != NULL)? current-link : N
66、ULL; ;灸炸皖恋辕占蜘嘎咖涛践资锄沧他蓖鲸强智季毡啄偿嫉具棵带鼻客瓣务涅六章节集合与字典六章节集合与字典搜索算法template ChainNode *SortedChain:Search (const K k1) const ChainNode *p = first-link; while (p != NULL & p-data link; /重载：元素判小于 if ( p != NULL & p-data = k1) return p; /重载：元素判等于 else return NULL;类似于前面讲过的用链表实现集合时，判断一个值x是否在集合中的方法赐阵悯魁纹飘重浚神福轻救辈障酪屁
67、圣慧慈烫黄倾旷蚂除吊上救囱丫瞩欠六章节集合与字典六章节集合与字典template void SortedChain:Insert (const K k1, E& e1) ChainNode *p = first-link, *pre = first； ChainNode *newNode; while (p != NULL & p-data link; /寻找插入位置 if (p != NULL & p-data = k1) p-data = e1; else /插入结点，见后页插入结点，见后页newNode = new ChainNode(e1); if (newNode = NULL) c
68、err “存储分配失败！” link = p; pre-link = newNode; ;插入算法类似于前面讲过的用链表实现集合时，在集合中加入一个值x的方法烟悯昏远电筒侈碑同狼窟涟蓑馁乔媚忻喻涝睦出昔捅教冕邱帽寻熬干航射六章节集合与字典六章节集合与字典template bool SortedChain:Remove (const K k1, E& e1) ChainNode *p = first-link, *pre = first； while (p != NULL & p-data link; /寻找删除位置 if (p != NULL & p-data = k1) pre-link =
69、 p-link; e1 = p-data; delete p; return true; else return false; /未找到删除结点;类似于前面讲过的用链表实现集合时，在集合中删除一个值x的方法好夸维捅颧较哉裂扭傣演榆你营涧抽氦赡馅寺智股蚜禾逾缘峰盂苗阀杠言六章节集合与字典六章节集合与字典散列表（Hash Table）在元素存储位置与其关键码之间建立一个确定的对应函数关系 Hash()，即散列函数， 使得每个关键码与结构中某个唯一的存储位置相对应： Address Hash(key)在插入时，依此函数计算存储位置并按此位置存在插入时，依此函数计算存储位置并按此位置存放。放。在搜索时
70、对元素的关键码进行同样的计算，把求在搜索时对元素的关键码进行同样的计算，把求得的函数值当做元素存储位置，在结构中按此位得的函数值当做元素存储位置，在结构中按此位置搜索。置搜索。通常多个通常多个KeyKey对应于多个对应于多个AddressAddress。滓蛤榨眺借杖浪媳潦篙恶窃怠鹰累悼柒粱灯棚座尤贤福郑申啦凯粥跳哆匿六章节集合与字典六章节集合与字典 优点：优点：不必进行多次关键码的比较不必进行多次关键码的比较, , 搜索速度比较快搜索速度比较快, , 可以直接到可以直接到达或快速逼近具有此关键码的表项的实际存放地址。达或快速逼近具有此关键码的表项的实际存放地址。散列冲突：散列冲突：关键码集合比
71、散列表地址集合大得多。因此必然会把某些不关键码集合比散列表地址集合大得多。因此必然会把某些不同的关键码映射到同一个散列地址上，这就产生了冲突。同的关键码映射到同一个散列地址上，这就产生了冲突。这些散列地址相同的不同关键码被称为这些散列地址相同的不同关键码被称为同义词同义词。冲突的例子：冲突的例子：有一组表项，其关键码分别是有一组表项，其关键码分别是 12361, 07251, 03309, 30976 采用的散列函数是采用的散列函数是 hash(x) = x % 73 + 13420则有则有 hash(12361) = hash(07250) = hash(03309) = hash(3097
72、6) = 13444。邵雁把堡阅时装芜向撑桌耘冀继速示茂席尚笆渍窑拇峨驭导谦秃烫夸缸揪六章节集合与字典六章节集合与字典由于关键码集合通常比地址集合大得多, 冲突很难避免。所以对于散列方法, 需要讨论以下两个问题：对于给定的一个关键码集合，选择一个计算简单且地址分布比较均匀的散列函数，避免或尽量减少冲突；解决冲突的方案。搪祟口被肄狼皿要狄欺履湍酪涟醇蛊刚及目兰膀柳叹巷燃凄版铱山莉扼吨六章节集合与字典六章节集合与字典被用于根据关键码计算得到存储地址被用于根据关键码计算得到存储地址构造散列函数时的几点要求：构造散列函数时的几点要求：散列函数应是简单的，能在较短的时间内计算出结果。散列函数的定义域必须
73、包括需要存储的全部关键码；值域必须是存储地址的全集。散列函数计算出来的地址应能均匀分布在整个地址空间中 : 若 key 是从关键码集合中随机抽取的一个关键码, 散列函数应能以同等概率取0 到 m-1 中的每一个值。散列函数馈辐沏穷垂荣侦诗唾祁讨课烃诺杂喘蓑你叼货嚏畦蹈款杉粗剂佯茹刚睹宰六章节集合与字典六章节集合与字典直接定址法取关键码的某个线性函数值作为散列地址： Hash(key) = a*key+b a, b为常数这类散列函数是一对一的映射，一般不会产生冲突。但它要求散列地址空间的大小与关键码集合的大小相同。散列函数的例子（1）滴莹畸遵嫁袋摆舅茹芹琳新班橙儒屠妖赊窘培嫉哼跪选鹃仗虾底试操诱
74、回六章节集合与字典六章节集合与字典l示例：有一组关键码如下：示例：有一组关键码如下： 942148, 941269, 940527, 941630, 941805, 941558, 942047, 940001 。散列函数为散列函数为 Hash(key) = key-940000 Hash (942148) = 2148 Hash (941269) = 1269Hash (940527) = 527 Hash (941630) = 1630Hash (941805) = 1805 Hash (941558) = 1558Hash (942047) = 2047 Hash (940001) =
75、1l可以按计算出的地址存放记录。可以按计算出的地址存放记录。l l但是要求数组的大小为最大但是要求数组的大小为最大key值值-940000贞担走尘鄂即籍弹穴柴虾胖绚组锅翔者退晚稗受霍柱灰丽戊萌羞怪氟突卜六章节集合与字典六章节集合与字典散列函数的例子（2）除留余数法除留余数法设散列表中允许地址数为设散列表中允许地址数为m，取一个不大于，取一个不大于 m，但最接近，但最接近于或等于于或等于 m 的质数的质数 p 作为除数，用以下函数把关键码转作为除数，用以下函数把关键码转换成散列地址：换成散列地址： hash (key) = key % p p m要求这时的质数要求这时的质数 p 不接近不接近 2
76、 的幂。的幂。示例示例: 散列表大小散列表大小 m = 25，p = 23。关键码。关键码962148的散列的散列地址为地址为 hash(962148) = 962148 % 23 = 12。23、24 这几个地址实际上不能用散列函数计算出来，但这几个地址实际上不能用散列函数计算出来，但是可以在处理冲突时达到这些地址。是可以在处理冲突时达到这些地址。 丛狠类坤踩樊宗酋嗡靠服谎咬赴搔漳匹仙受存缅艇罐素旨坊渔搏鸿侠赂馈六章节集合与字典六章节集合与字典 数字分析法数字分析法设有设有 n 个个 d 位数位数, 每一位可能有每一位可能有 r 种不同种不同的符号。这的符号。这 r 种不同符号在各位上出现的
77、频种不同符号在各位上出现的频率不一定相同。根据散列表的大小率不一定相同。根据散列表的大小, 选取其选取其中各种符号分布均匀的若干位作为散列地址。中各种符号分布均匀的若干位作为散列地址。计算各位数字中符号分布均匀度计算各位数字中符号分布均匀度 k的公式：的公式：其中，其中， 表示第表示第 i 个符号在第个符号在第 k 位上出现的位上出现的次数，次数，n/r 表示各种符号在表示各种符号在 n 个数中均匀出个数中均匀出现的期望值。现的期望值。渺区野宫嫁阉捍撼扣咐虞妙纵饿央桓煎剖茬挽拨址在薛觅诊抱叼艰詹翱灰六章节集合与字典六章节集合与字典 计算出的计算出的 k k 值越小，表明在该位值越小，表明在该位
78、 ( (第第 k k 位位) ) 各种符号分布得越均匀。各种符号分布得越均匀。 9 4 2 1 4 8 位，位， 1 = 57.60 9 4 1 2 6 9 位，位， 2 = 57.60 9 4 0 5 2 7 位，位， 3 = 17.60 9 4 1 6 3 0 位，位， 4 = 5.60 9 4 1 8 0 5 位，位， 5 = 5.60 9 4 1 5 5 8 位，位， 6 = 5.60 9 4 2 0 4 7 9 4 0 0 0 1 咀涤娠摧悠喉烁阅血栏宜父儒稻显乡先铱戮赁眉蛰芯鼎抑决樱索眶睁天崖六章节集合与字典六章节集合与字典若散列表地址范围有若散列表地址范围有 3 3 位数字位数字
79、, , 取各取各关键码的关键码的 位做为记录的散列地位做为记录的散列地址。址。数字分析法仅适用于事先明确知道表中数字分析法仅适用于事先明确知道表中所有关键码每一位数值的分布情况，它所有关键码每一位数值的分布情况，它完全依赖于关键码集合。如果换一个关完全依赖于关键码集合。如果换一个关键码集合，选择哪几位要重新决定。键码集合，选择哪几位要重新决定。妊焙孔匝碎握闹良僻露肤宴往重垦锗磷被呼屎曙宫韩理凛杰节跺始氖煽弹六章节集合与字典六章节集合与字典平方取中法平方取中法它它首首先先计计算算构构成成关关键键码码的的标标识识符符的的内内码码的的平平方方, , 然然后后按按照照散散列列表表的的大大小小取取中中间
80、间的的若若干干位位作为散列地址。作为散列地址。设设标标识识符符可可以以用用一一个个计计算算机机字字长长的的内内码码表表示示。因因为为内内码码平平方方数数的的中中间间几几位位一一般般是是由由标标识识符符所所有有字字符符决决定定, , 所所以以对对不不同同的的标标识识符符计计算算出出的散列地址大多不相同。的散列地址大多不相同。在在平平方方取取中中法法中中, , 一一般般取取散散列列地地址址为为2 2的的某某次次幂幂。例例如如, , 若若散散列列地地址址总总数数取取为为 m m = = 8 8r r，则对内码的平方数取中间的，则对内码的平方数取中间的 r r 位。位。血带暖搬啦坡叔密女垫方碱澜三径闪
81、帅化姿杭容拱表铲萧晕菲忠霞姆扭急六章节集合与字典六章节集合与字典 标识符标识符内码内码内码平方内码平方散列地址散列地址A0101001A1013420420042A9014423420342B0204004DMAX0415013021526443617100443DMAX1 0415013034 5264473522151420352AMAX01150130135423617100236AMAX1 0115013034 3454246522151420652标识符的八进制内码表示及其平方值和散列地址标识符的八进制内码表示及其平方值和散列地址哦首晾搔茵从朝腺惯肺桨都撮库证呜溅身段奶吼壤簧鳞啮膀扬
82、衙裁眠柱愁六章节集合与字典六章节集合与字典折叠法此方法把关键码自左到右分成位数相等的几部分, 每一部分的位数应与散列表地址位数相同, 只有最后一部分的位数可以短一些。把这些部分的数据叠加起来, 就可以得到具有该关键码的记录的散列地址。有两种叠加方法：v 移位法：把各部分最后一位对齐相加；v 分界法：各部分不折断，沿各部分的分界来回折叠, 然后对齐相加。骋涪狞骆跺雇祁班肩乏濒拖腹碗梆木侮圭干从潞态让懈巾酱韦写箱泄罐途六章节集合与字典六章节集合与字典示例示例: 设给定的关键码为设给定的关键码为 key = 23938587841, 若存储空间限定若存储空间限定 3 位位, 则划分结果为每段则划分结
83、果为每段 3 位。位。 上述关键码可划分为上述关键码可划分为 4 段：段： 239 385 878 41把超出地址位数的最高位删去把超出地址位数的最高位删去, 仅保留最低的仅保留最低的3 位，做为可用的散列地址。位，做为可用的散列地址。 移移位位法法 分分界界法法个惕枪迈奢氰钝语料脸募其驻中蕊检牌遭师施舅偏隶卑腰焰赣绪浸显贱红六章节集合与字典六章节集合与字典一一般般当当关关键键码码的的位位数数很很多多，而而且且关关键键码码每每一一位位上上数数字字的的分分布布大大致致比比较较均均匀匀时时，可可用用这这种种方法得到散列地址。方法得到散列地址。假假设设地地址址空空间间为为HT400，利利用用以以上上
84、函函数数计计算算，取取其其中中3位位，取取值值范范围围在在0999，可可能能超超出出地地址址空空间间范范围围，为为此此必必须须将将0999压压缩缩到到0399。可可将将计计算算出出的的地地址址乘乘以以一一个个压压缩缩因子因子0.4，把计算出的地址压缩到允许范围。，把计算出的地址压缩到允许范围。诫搁滩放崖薛退基诅瘦罢渠屈巨韩锨剁屋泻凛鲜择嚏肤甜蒲痕祥傅舵岩翠六章节集合与字典六章节集合与字典散列冲突的处理散列冲突的处理任何散列函数都不能避免产生冲突，因此好任何散列函数都不能避免产生冲突，因此好的解决冲突的方法十分重要。的解决冲突的方法十分重要。对散列表的假定对散列表的假定若设散列表若设散列表HT有
85、有 m 个地址个地址, 将其看作将其看作 m 个桶。个桶。第第 i (0i =1)个表项个表项, 这些表项的关键这些表项的关键码互为同义词。码互为同义词。两个不同表项的关键码用散列函数计算得到两个不同表项的关键码用散列函数计算得到同一个散列地址，即产生冲突同一个散列地址，即产生冲突. .它们被放在同一个桶内。当同存放不下时，它们被放在同一个桶内。当同存放不下时，就需要解决冲突。就需要解决冲突。巧育塑村剑抑慑火咸丈坪翟筑临炽泄匠换掖辅填斗蔚滴湛帜青督焕扳费奢六章节集合与字典六章节集合与字典闭散列也叫做开地址法。所有的桶都直接放在散列表数组中。每个桶只有一个表项 ( s = 1 )。冲突的解决方法
86、：若设散列表中各桶的编址为 0 到 m-1, 当要加入一个表项 R2 时, 通过散列函数 hash (R2.key) 计算得到的桶号 j中已经有另一个表项，就需要把 R2 存放到表中“下一个下一个”空桶中。寻找下一个空桶的方法线性探查法二次探查法双散列法闭散列方法（开地址法）闭散列方法（开地址法）冠顾立渍厚替呆湘寅赎紊兽秉仔沸哟芬隘纵摈矫存智钙苹逊疡与肇捞八犁六章节集合与字典六章节集合与字典需要搜索或加入一个表项时，首先使用散列函数计算桶号作为初需要搜索或加入一个表项时，首先使用散列函数计算桶号作为初始地址：始地址： H0 = hash (key)一旦发生冲突，在表中顺次向后寻找一旦发生冲突，
87、在表中顺次向后寻找“下一下一 个个”空桶空桶 Hi 的递推公的递推公式为：式为： Hi = (Hi-1+1) % m， i =1, 2, , m-1 即用以下的线性探查序列在表中寻找即用以下的线性探查序列在表中寻找“下一下一 个个”空桶的桶号：空桶的桶号： H0+1, H0 +2, , m-1, 0, 1, 2, , H0-1亦可写成如下的通项公式：亦可写成如下的通项公式： Hi = (H0 + i) % m， i =1, 2, , m-1当发生冲突时探查下一个桶。当发生冲突时探查下一个桶。当循环当循环 m-1次后就会回到开始探查时的位置，说明待查关键码不次后就会回到开始探查时的位置，说明待查
88、关键码不在表内且表已满，不能再插入新关键码。在表内且表已满，不能再插入新关键码。线性探查法线性探查法 (Linear Probing) (Linear Probing)窒浦役尾早僚鉴塑呜遵宿纠傻概鹤郁置瓮臆镍能姜老芒蚤松孪尘档辙滥钥六章节集合与字典六章节集合与字典散列中的元素的删除：散列中的元素的删除：假设一个元素的假设一个元素的Hash值是值是i，实际上被存放在，实际上被存放在j中。中。那么在搜索这个元素时，需要从那么在搜索这个元素时，需要从i逐个搜索到逐个搜索到j。碰到空位是方。碰到空位是方可判定这个元素不在可判定这个元素不在Hash表中。因此表中。因此i、j之间的元素不能直之间的元素不能
89、直接删除。接删除。因此在散列中只能通过做记号删除元素；因此在散列中只能通过做记号删除元素；容易形成容易形成堆积堆积，导致搜索变慢。，导致搜索变慢。线性探查法的性能衡量以历冻苇拨郡脊辕统孪犹劳凰捷舔漠獭跪惨忆霸救搐最婚源陨疗碟殊椰脸六章节集合与字典六章节集合与字典假设给出一组表项，它们的关键码为假设给出一组表项，它们的关键码为 Burke, Ekers, Broad, Blum, Attlee, Alton, Hecht, Ederly。采用的散列函数是：取其第一个字母。采用的散列函数是：取其第一个字母在字母表中的位置。在字母表中的位置。 HashHash ( (x x) = ) = ord o
90、rd ( (x x)- )-ord ord ( (A A) ) / /ordord() () 求内求内求内求内码函数码函数码函数码函数线性探查法的例子线性探查法的例子欧季唉炒界美楚靖绿进纸够起瞳爷音幢域提腋蒜爷摘籍乔蛊舷狗驻捅禁讲六章节集合与字典六章节集合与字典 l可得可得 Hash (Burke) = 1 Hash (Ekers) = 4 Hash (Broad) = 1 Hash (Blum) = 1 Hash (Attlee) = 0 Hash (Hecht) = 7 Hash (Alton) = 0 Hash (Ederly) = 4设散列表设散列表 HT26, m = 26。采用线性
91、探查法处。采用线性探查法处理冲突理冲突, 则散列结果如图所示。则散列结果如图所示。 0 1 2 3 4Attlee Burke Broad Blum Ekers(1) (1) (2) (3) (1)(1) (1) (2) (3) (1)Alton Ederly Hecht 5 6 7 8 9 (6) (3) (1)(6) (3) (1)红色字体为搜索长度红色字体为搜索长度再各次砰泉构俩酵咆乃运窜蛰亦锗藻踞沽优蔼姨相狐霄撕涉刘核米姿闰样六章节集合与字典六章节集合与字典在使用线性探查法对示例进行搜索时，搜索成在使用线性探查法对示例进行搜索时，搜索成功的平均搜索长度为：功的平均搜索长度为：搜索不成功
92、的平均搜索长度为：搜索不成功的平均搜索长度为：考虑前一页的例子中，执行以下各步的情况考虑前一页的例子中，执行以下各步的情况删除删除BurkeBurke搜索搜索BroadBroad插入插入BikeBike费早瑶钳迫撬噬奎腰总北凰离壹烙谩绅面播测宋叮柬夕浮奢影浴固溅导停六章节集合与字典六章节集合与字典用线性探查法组织的散列表的类定义用线性探查法组织的散列表的类定义 const int DefaultSize = 100;enum KindOfStatus Active, Empty, Deleted;/元素分类 (活动/空/删)template class HashTable /散列表类定义pub
93、lic: HashTable (const int d, int sz = DefaultSize);/构造函数 HashTable() delete ht; delete info; /析构函数HashTable& operator = (const HashTable& ht2); /表赋值 罩许蛰造曰籽肮第半城责刺瘴馁獭拍彤寸作粗愁挖仿作间猜咐川谅宜纯出六章节集合与字典六章节集合与字典bool Search (K k1, E& e1) const; /搜索k1bool Insert (const E& e1); /插入e1bool Remove (const E& e1); /删除e1v
94、oid makeEmpty (); /置表空private:int divitor;/散列函数的除数int n, TableSize;/当前桶数及最大桶数E *ht; /散列表存储数组KindOfStatus *info;/状态数组int FindPos (K k1) const;int operator = (E& e1) return *this = e1; /重载函数：元素判等int operator != (E& e1) return *this != e1; /重载函数：元素判不等;挖向杜龋艘绩囱蛔迷箕殖非雹架尺灵惋又片续尝枢挨佐布肿报钟僚旬除闸六章节集合与字典六章节集合与字典/构造
95、函数templateHashTable:HashTable (int d, int sz) divitor = d;/除数TableSize = sz; n = 0;/表长ht = new ETableSize;/表存储空间info = new KindOfstatusTableSize;for (int i = 0; i TableSize; i+) infoi = empty;吃胶射澳土曾南傀泵旗舔瓦恿当秽勋侈峭算剂鹤厌发傍嘴村拉即朽考丘厂六章节集合与字典六章节集合与字典template int HashTable:FindPos (K k1) const /搜索在一个散列表中关键码与k1
96、匹配的元素，int i = k1 % divitor; /计算初始桶号int j = i; /j是检测下一空桶下标do if (infoj = Empty | infoj = Active & htj = k1) return j; /注意：碰到Deleted时需要继续寻找！ j = (j+1) % TableSize;/找下一个空桶 while (j != i); return j;/转一圈回到开始点, 表已满,;使用线性探查法的搜索算法（使用线性探查法的搜索算法（1）撵羊喻焕捕努堡民酱啡偏塌脚剩饥紊瞄纺懂抱崎食浅烽酚置枢们呆叛汉哎六章节集合与字典六章节集合与字典FindPosFindPos
97、返回后的三种情况：返回后的三种情况：infoj=Empty （没有找到）infoj！=Empty & htj!=k1（也没有找到）infoj = Active & htj = k1（找到）芦晒要顺番异料井阁殃财戊婚汉纫霞污臀器冤谚芬锈舟牌寂练爪斤砖亚寝六章节集合与字典六章节集合与字典bool HashTable:Search (K k1, E& e1) /使用线性探查法在散列表ht(每个桶容纳一个元素)/中搜索k1int i = FindPos (k1)； /搜索if (infoi != Active | hti != k1) return false;e1 = hti; return tru
98、e;FindPosFindPos返回后的三种情况：返回后的三种情况：linfoj=Emptylinfoj！=Empty & htj!=k1linfoj = Active & htj = k1；街鳖误腔昼战父自修痛盖已舌典枕荷队阜虱肄孝泪会药亚徊誓瘤桃法万警六章节集合与字典六章节集合与字典线性探查的插入操作template bool HashTable:Insert (K k1, const E& e1) /在ht表中搜索k1。若找到则不再插入, 若未找到, /但找到位置的标志是Empty或Deleted, x插入 int i = FindPos (k1);if (infoi != Active
99、) /该桶空(empty | deleted),存放新元素hti = e1; infoi = Active;n+; return true; if (infoi = Active & hti = e1) cout “此元素存在！此元素存在！n”; else cout “表已满！表已满！n”; return false;FindPosFindPos返回后的三种情况：返回后的三种情况：linfoj=Emptylinfoj!=Empty & htj!=k1linfoj = Active & htj = k1；醚颠辩脏烯砍装郭笑右脓坞醇怒贞赠屎逢瞥暴泌恐锥栽桓亨钻热卫畦鸽汀六章节集合与字典六章节集合与
100、字典线性探查的插入操作（修改版）template bool HashTable:MyInsert (K k1, const E& e1) /在ht表中搜索k1。若找到则不再插入, 若未找到, /则寻则寻找到第一个位置标志是Empty或Deleted的位置插入 int i = FindPos (k1); /用散列函数计算桶号if (infoi = Active & hti = e1) cout “表中已有此元素，不能插入！表中已有此元素，不能插入！n”; return false; else i=FindSlot(k1); /寻找的是第一个可以插入的位置if(i0) cout “表已满，不能插入
101、！表已满，不能插入！n”; return false;else hti = e1; infoi = Active;n+; return true;端佩兹口瓣摈瞬序君砚母诛书钡苫裔优恳滩岂肄蚀镶椭赔慷证螟拟炒腊皱六章节集合与字典六章节集合与字典FindSlot的定义template int HashTable:FindSlot (K k1) const /前提：前提：k1不在散列中；不在散列中；/在散列表中查找适当的插入k1的位置；若表满则返回-1；/和findPos类似，但是只要查找第一个可插入的空位即可；int i = k1 % divitor;/计算初始桶号int j = i;/j是检测下
102、一空桶下标do if (infoj = Empty | infoj = Deleted)return j; /找到可用的桶号j = (j+1) % TableSize;/找下一个空桶 while (j != i); return -1;/转一圈回到开始点, 表已满, 失败；;月被匣恫例疡晴阐疤塌虞宛油阿疵零锁簧商细糯悬杠借涩幅拢押瘸烤函播六章节集合与字典六章节集合与字典若想删除一个表项若想删除一个表项, 只能给它做一个删除标记只能给它做一个删除标记deleted进行逻辑删除进行逻辑删除, 不能把它不能把它真正删去。真正删去。看看FindPos函数可知，在探查时碰到函数可知，在探查时碰到Empt
103、y可返回可返回False，探查时碰到，探查时碰到Delete需要继续探查；需要继续探查；一个元素在插入时可能探查多个位置，这些位置上的元素删除后不能设一个元素在插入时可能探查多个位置，这些位置上的元素删除后不能设为为Empty。否则可能探查不到原先插入的元素。否则可能探查不到原先插入的元素。逻辑删除的副作用逻辑删除的副作用在执行多次删除后，虽然许多位置没有存放元素，但是探查时仍然当这在执行多次删除后，虽然许多位置没有存放元素，但是探查时仍然当这些位置存放了元素。些位置存放了元素。template bool HashTable:Remove (K k1, E& e1) /在ht表中删除元素k1,
104、 并在引用参数e1中得到它 int i = FindPos (k1); if (infoi = Active & hti = k1) /找到要删元素, 且是活动元素 infoi = Deleted; n-; /做逻辑删除标志, 并不真正物理删除 return true; else return false;使用线性探查法的删除操作努哆鳞颊耸泪戌晒倒峻废惯常惺程酌佃哩锣饥雄海犬硫片服熄谣有迫序枚六章节集合与字典六章节集合与字典二次探查法首先通过某一个散列函数对表项的关键码二次探查法首先通过某一个散列函数对表项的关键码 key 进行计算，进行计算，得到桶号（非负整数）。得到桶号（非负整数）。H0
105、= hash(key)然后使用二次探查法在表中寻找然后使用二次探查法在表中寻找“下一个下一个”空桶，其公式为：空桶，其公式为：H2i-1 = (H0+i2) % m, H2i = (H0-i2)% m（小于（小于0时，需要加上时，需要加上m）,i = 1, 2, 3, , (m-1)/2m 是表的大小，是一个值为是表的大小，是一个值为 4k+3 的质数，如的质数，如3, 7, 11, 19, 23, 31, 43, 59, 127, 251, 503, 。根据根据wike百科全书中的定义，二次探查法的公式为百科全书中的定义，二次探查法的公式为Hi = (H0+c1i+c2i2) % m, 书中
106、的方法称为书中的方法称为alternating quadratic probing二次探查法二次探查法 (quadratic (quadratic probing)probing)粒痞颊兴致氛钩阐区愈箕去优氟呆幅担亲悄啤煎比跃锈临阳紫账佬恩攫溅六章节集合与字典六章节集合与字典Hi = (H0+i2) % m当表的长度当表的长度m为质数且表的装载因子为质数且表的装载因子 （表明表（表明表的装满程度）的装满程度）不超过不超过0.5 时，新的表项时，新的表项e一定能够一定能够插入。插入。H2i-1 = (H0+i2) % m, H2i = (H0-i2)% m则不需要考虑则不需要考虑装载因子。装载因
107、子。因为每个位置不会被查两次，当因为每个位置不会被查两次，当i=1,2,(m-1)/2时遍时遍历了所有的历了所有的m个位置（含第一个位置）个位置（含第一个位置）假设有一个位置被探查假设有一个位置被探查2次，那么必然存在次，那么必然存在i和和j使得使得i2 + j2或者或者i2 - j2是是m(形如形如4k+3的质数的质数)的倍数。的倍数。斗来任看矿稍殖底窍难步舟抄定杠赏奎惯淤颤观莫悠枚矩襟筋膀弘聪郊租六章节集合与字典六章节集合与字典如果同一方向的第i次探查和第j次探查重合，那么必然(i2-j2)%m=0，即(i-j)(i+j)%m=0。因为m是质数，且|i-j|m, |i+j|m，所以不可能整
108、除。如果不同方向的i次探查和j次探查重合，必然有(i2+j2)%m=0。根据数论结论， (i2+j2)如果有形如4k+3的质因子的话，它必然可以被(4k+3)2整除。然而(i2+j2)m2，因此不成立。喊饵瘴她烙皇向歪慎誊肩嫡茁开米渗砷彦挂惑月蚂耪城彩仪敲列百子匙蔑六章节集合与字典六章节集合与字典示示例例：给给出出一一组组关关键键码码 Burke, Ekers, Broad, Blum, Attlee, Alton, Hecht, Ederly 。 散列函数为：散列函数为：Hash (x)ord (x)ord (A)用它计算可得用它计算可得 Hash (Burke) = 1 Hash (Eke
109、rs) = 4 Hash (Broad) = 1 Hash (Blum) = 1 Hash (Attlee) = 0 Hash (Hecht) = 7 Hash (Alton) = 0 Hash (Ederly) = 4因因为为可可能能桶桶号号是是025, 取取满满足足4k+3的的质质数数，表表的长度为的长度为TableSize = 31。勇孝啊莲绅贴涣叭积堡潭竞嚼誊陪峡役硬桅咖卒五上膏亲华潘催坝肃豁区六章节集合与字典六章节集合与字典依次插入依次插入Burke, Ekers, Broad, Blum, Attlee, Alton, Hecht, Ederly利用二次探查法得到的散列结果如图所示
110、。利用二次探查法得到的散列结果如图所示。0 1 2 3 4 5 Blum Burke Broad Ekers Ederly Hecht 6 7 8 9 10 11 Alton Attlee (3) (1) (2) (1) (2)(1)25 26 27 28 29 30 (5) (3)利用二次探查法处理溢出利用二次探查法处理溢出财尺琉识屈秉萝绅矗铲拎掀姆返裤尾娥史勒规豫淖喇改灶坪诬门柔洞仕阳六章节集合与字典六章节集合与字典使使用用二二次次探探查查法法处处理理冲冲突突时时的的搜搜索索成成功功的的平平均搜索长度为：均搜索长度为：搜索不成功的平均搜索长度为搜索不成功的平均搜索长度为：问问题题：当当两两
111、个个元元素素的的hash值值相相同同时时，仍仍然然产产生堆积情况。生堆积情况。原因：计算下一个位置的过程和原因：计算下一个位置的过程和key无关。无关。蛤羡峙林峡迸洞琢膘颊敌劣胶儒郡蔡汾驹阶姥傀蒙泉溉穗恶导外凉衡武惰六章节集合与字典六章节集合与字典使用双散列方法时使用双散列方法时, 需要两个散列函数。需要两个散列函数。第第一一个个散散列列函函数数 Hash() 按按表表项项的的关关键键码码 key 计算表项所在的桶号计算表项所在的桶号 H0 = Hash(key)。冲冲突突时时用用第第二二个个散散列列函函数数ReHash() 计计算算该该表表项到达项到达“下一个下一个”桶的移位量。桶的移位量。
112、它它的的取取值值与与 key 的的值值有有关关, 要要求求它它的的取取值值应应是是小小于于地地址址空空间间大大小小TableSize, 且且与与 TableSize 互互质质的的正整数正整数。双散列法拐氛阉八侩动剥崭泊辟掖仅亦穿间袜唁筏赞欠箱铝簇噬剑芍酥婴够睡谨滇六章节集合与字典六章节集合与字典若若设设表表的的长长度度为为 m = TableSize，则则在在表表中中寻寻找找“下下一个一个”桶的公式为桶的公式为 H0 = Hash(key)， p = ReHash(key)； Hi = (Hi-1+ p) % m； 利用双散列法跳跃式地寻找利用双散列法跳跃式地寻找“下一个下一个”桶时和桶时和K
113、ey有有关。不同关。不同Key的元素的跳跃步长不一样的元素的跳跃步长不一样, 减少了减少了“堆堆积积”的机会。的机会。双散列法的探查序列也可写成：双散列法的探查序列也可写成： Hi = (Hi-1+ ReHash(key) % m， i =1, 2, , m-1最多经过最多经过 m-1次探查次探查, 它会遍历表中所有位置，回它会遍历表中所有位置，回到到H0 位置。位置。蚕冀恤角褥挟妄匣班位潮赘挟熊稚玉脐慧好仁说煮顽桓闷哆厄求摩绵斥敛六章节集合与字典六章节集合与字典示例：示例：散列函数为：散列函数为：Hash(x)x % 11散列表散列表HT11 ReHash(x) = x % 10 +1。Hi
114、 = (Hi-1 + x % 10 +1) % 11, i = 1, 2, 给出一组表项关键码给出一组表项关键码 22, 41, 53, 46, 30, 13, 01, 67 。渣躯税败部球斧抹颜抵悍蒜非创愈峻祥族独瓶恳蕊诲逝徘幸企赃惑魏表瞳六章节集合与字典六章节集合与字典 22, 41, 53, 46, 30, 13, 01, 67 H0(22) = 0 H0(41) = 8 H0(53) = 9 H0(46) = 2 H0(30) = 8 冲突冲突 p = 1 H1 = 8+1 = 9 冲突冲突H2 = 9+1 = 10H0(13) = 2 冲突冲突 p = 4 H1 = 2+4 = 6H
115、0(01) = 1H0(67) = 1 冲突冲突p = 8 H1 = 1+8 = 9 冲突冲突 H2 = 9+8 = 6冲突冲突H3 = 6+8 = 3 0 1 2 3 4 5 6 7 8 9 10 22(1)141(1)253(1)346(1)430(3)513(2)601(1)767(4)8重乘电匝钻风神浪五饰碉瘤揖没苹褐舷意傻弘媒佩税比戮木蹈篆当穷痕浙六章节集合与字典六章节集合与字典搜索成功的平均搜索长度搜索成功的平均搜索长度搜索不成功的平均搜索长度搜索不成功的平均搜索长度u每一散列位置的移位量有每一散列位置的移位量有1010种：种：1, 2, 1, 2, , , 1010。先计算每一散
116、列位置各种移位量情形下。先计算每一散列位置各种移位量情形下找到下一个空位的比较次数找到下一个空位的比较次数, ,求出平均值；求出平均值；u再计算各个位置的平均比较次数的总平均值。再计算各个位置的平均比较次数的总平均值。 0 1 2 3 4 5 6 7 8 9 10 22(1)41(1)53(1)46(1)30(3)13(2)01(1)67(4)炮汁揍杏皿组间羔户懈晰劣腻铺壬朋卷阀铬羚凝压函讶嘱疟镶肇飞雀读豫六章节集合与字典六章节集合与字典Rehash()的的取取法法很很多多。例例如如, 当当m是是质质数数时时, 可可定义定义ReHash(key) = key % (m-2) +1ReHash(
117、key) = key / m % (m-2)+1当当 m 是是 2 的方幂时，的方幂时，ReHash(key) 可取从可取从 0 到到 m-1 中的任意一个奇数。中的任意一个奇数。将挛女媚骚烷窗郝原你勇尺邑娱徊前搽辕肆禹辣佩直茫陡荆汛洱膘鳃轰乘六章节集合与字典六章节集合与字典处理冲突的开散列方法（链地址法）处理冲突的开散列方法（链地址法）对关键码集合用某个散列函数计算存放位置。对关键码集合用某个散列函数计算存放位置。具有相同地址的关键码归于同一子集，称为一个桶。具有相同地址的关键码归于同一子集，称为一个桶。桶的大小不限，但是通常比较小；桶的大小不限，但是通常比较小；同一子集中的关键码互为同一子
118、集中的关键码互为同义词同义词。所所有有桶桶号号相相同同的的表表项项用用单单链链接接保保存存在在同同一一个个同同义词子表中。义词子表中。各链表的表头结点组成一个向量。各链表的表头结点组成一个向量。向量的元素个数即桶的个数。向量的元素个数即桶的个数。桶桶号号为为i的的同同义义词词子子表表的的表表头头结结点点是是向向量量中中第第 i 个个元元素。素。米炭公收横汇新题打去颜捡渗吊枉沏畅鼓炉膝请委运多厨雅长萨吼司卒牙六章节集合与字典六章节集合与字典示例：示例：一一组组表表项项关关键键码码 Burke, Ekers, Broad, Blum, Attlee, Alton, Hecht, Ederly 。散
119、列函数散列函数Hash (x)ord (x)ord (A)。计算可得：计算可得：Hash (Burke) = 1 Hash (Ekers) = 4Hash (Broad) = 1 Hash (Blum) = 1Hash (Attlee) = 0 Hash (Hecht) = 7Hash (Alton) = 0 Hash (Ederly) = 4地蠕纯耕持陇习毡翁徐嘲去媒篡峦差稚本阉崎腆家亲旦右埔郑胡子鬼纲嫩六章节集合与字典六章节集合与字典0 01 12 23 34 45 56 67 78 89 9AttleeAltonBurkeBroadBlumEkersEderlyHecht散列表为散列表为
120、 HT0.25，m = 26。能裁弟浇裕炒舀迈叮网杂淫法焦哥篇酷苞拈止犯萨榨出戳砂抑厅苇乏姬嘲六章节集合与字典六章节集合与字典设有n 个关键码通过某一个散列函数，存放到散列表中的 m 个桶中。那么每一个桶中的同义词子表的平均长度为 n / m。以搜索平均长度为 n / m 的同义词子表代替了搜索长度为 n 的顺序表，搜索速度快得多。漫斜惭科程瓦狰碍灼厄雌鬼抓访囚肢邓鸣个沿辗城肖鳖单丑远播微发剑胁六章节集合与字典六章节集合与字典使用开散列法的散列表类定义使用开散列法的散列表类定义 #include const int defaultSize = 100;template struct Chain
121、Node /各桶中同义词子表的链结点定义E data; /元素ChainNode *link; /链指针;template class HashTable /散列表(表头指针向量)定义public: bool Search (K k1, E& e1);/搜索 bool Insert (K k1, E& e1);/插入 bool Remove (K k1, E& e1);/删除private:int divisor; /除数（必须是质数） int TableSize; /容量(桶的个数)ChainNode *ht;/散列表定义ChainNode *FindPos (K k1);/散列查找;密耐娄
122、鸳浦则碱柞奥乖楔拂廊反填瑚瘤圆闹晶怠剂疾网备包瞎救临菠逾剧六章节集合与字典六章节集合与字典用开散列法定义的散列表的操作用开散列法定义的散列表的操作template ChainNode *HashTable:FindPos (K k1) /在散列表ht中搜索关键码为k1的元素。函数返回/一个指向散列表中某位置的指针 int j = k1 % divisor; /计算散列地址 /扫描第j链的同义词子表 /即单链表中的搜索算法ChainNode *p = htj; while (p != NULL & p-data != k1) p = p-link; return p; /返回;肌燎噪辽装理勿鹊烁
123、吠屑幢畔析美肥收苯卫岸凶棕艺韶榜聚聂闸庸胰币辙六章节集合与字典六章节集合与字典其他如插入、删除操作可参照单链表的插入、删除等算法来实现。 做洞屑铝国识夹箭寻暂子澡桑料沦芳士婶渴香俊恐广棠阵企燃是逼顷饮榆六章节集合与字典六章节集合与字典开散列法需要增设链接指针，增加了存储开销。闭散列法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装填因子0.5，而表项所占空间又比指针大得多，所以使用开散列法反而比闭散列法节省存储空间。开散列法/闭散列法的空间比较蚊驱疑乔砍过堵坯渐曝敖寺识选隐焉磋向典南话们贬灌肄马兰忍说架亲婆六章节集合与字典六章节集合与字典散散列列表表直直接接出出计计算算表表项项存存放放
124、地地址址，在在关关键键码码与与存存储储位位置之间直接建立了映象。置之间直接建立了映象。理想情况下，如果散列函数能够绝对均匀地计算地址理想情况下，如果散列函数能够绝对均匀地计算地址, ,那么搜索过程中很快找到位置。那么搜索过程中很快找到位置。很难避免冲突很难避免冲突, ,增加了搜索时间。冲突出现的频率和增加了搜索时间。冲突出现的频率和下面两个因素有关下面两个因素有关散列函数（地址分布是否均匀）散列函数（地址分布是否均匀）处理冲突方法（是否产生堆积）处理冲突方法（是否产生堆积）在实际应用中，不同的散列函数往往导致散列表具有在实际应用中，不同的散列函数往往导致散列表具有不同的搜索性能。不同的搜索性能
125、。散列表分析绢仪凄馅脓获泄键装党牛邦独饿矿凿全捕叙床茵焕扮噬月是谅牙悉憾敏皋六章节集合与字典六章节集合与字典搜索关键码时所需对桶的平均访问次数搜索关键码时所需对桶的平均访问次数一些实验结果一些实验结果抵光俯懂产解歪衅绥挨剐桓轰岭囚它邵飞您疙秆疚隘谦葛喷影赁箕料拭虐六章节集合与字典六章节集合与字典根据实验数据根据实验数据开散列法优于闭散列法开散列法优于闭散列法；在散列函数中，用除留余在散列函数中，用除留余数法作散列函数优于其他类型的散列函数数法作散列函数优于其他类型的散列函数，最差的，最差的是折叠法。是折叠法。对散列表技术进行的实验评估表明对散列表技术进行的实验评估表明,它具有很好的它具有很好的
126、平均性能平均性能,优于一些传统的技术优于一些传统的技术, 如平衡树。如平衡树。但散列表在最坏情况下性能很不好。如果对一但散列表在最坏情况下性能很不好。如果对一 个有个有 n 个关键码的散列表执行一次搜索或插入操作，最个关键码的散列表执行一次搜索或插入操作，最坏情况下需要坏情况下需要 O(n) 的时间。的时间。郝铂门枣挪雁奠公稻晴均程酚敌腻讹殖高程阮侦羔戒南慰玖响锌贺怔蛊鸽六章节集合与字典六章节集合与字典若设 是散列表的装载因子：Sn 是搜索一个随机选择的关键码 xi (1i n) 所需的关键码比较次数的期望值即搜索成功的平均搜索长度Un 是在长度为 m 的散列表中 n 个桶已装入表项的情况下，
127、装入第 n+1 项所需执行的关键码比较次数期望值。即在 = n / m时搜索不成功的平均搜索长度。薄往侵斑绥姓糖低鞭统卷舶旷佬胚窃侨士种圆烩胜案邱绿载剩炼兆培兑担六章节集合与字典六章节集合与字典平均搜索长度与装填因子的关系平均搜索长度与装填因子的关系犯谆挽乃驮舆盯懂荚抱威釉浊颗倍伴栖溢航摧痔血佃缠琅扣忙徊旧季莲姥六章节集合与字典六章节集合与字典装填因子 越大, 说明表越满, 再插入新元素时发生冲突的可能性就越大。散列表的搜索性能依赖于散列表的装填因子, 不直接依赖于 n 或 m。我们总能选择一个合适的装填因子, 以把平均搜索长度限制在一定范围内。努匆度誉疗椿惦蓝舅宗移恍距筐半葛笨啤视牺哪法政敝
128、哀贮店虱奄废堡宗六章节集合与字典六章节集合与字典例：设有一个含例：设有一个含200个表项的散列表，用二次个表项的散列表，用二次探查法解决冲突，按关键码查询时找到一个新探查法解决冲突，按关键码查询时找到一个新表项插入位置的平均探查次数不超过表项插入位置的平均探查次数不超过1.5，则，则散列表应能够至少容纳多少个表项。再设计散散列表应能够至少容纳多少个表项。再设计散列函数列函数（设搜索不成功的平均搜索长度为（设搜索不成功的平均搜索长度为 Un1 / (1-), 其中其中为装填因子）为装填因子）解答：设表中表项个数解答：设表中表项个数 n = 200，搜索不成功，搜索不成功的平均搜索长度的平均搜索长度 Un1 / (1-) 1.5 1/3 n / m = 200 / m = 1/3 m600 m = 607（满足（满足4k+3的质数且的质数且 0.5 ）泛诡盖祁她低傅坡身养逊坦适乏竞滞坑余蔚劫沫划什在鳖业甫轩讫蛾寡虑六章节集合与字典六章节集合与字典
