集合与字典精选PPT.ppt

《集合与字典精选PPT.ppt》由会员分享，可在线阅读，更多相关《集合与字典精选PPT.ppt（46页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、集合与字典集合与字典第1页，此课件共46页哦6.1 集合及其抽象数据类型集合及其抽象数据类型6.1.1 基本概念基本概念n n数数学学中中集集集集合合合合是是一一些些互互不不相相同同元元素素的的无无序序汇汇集集。这这些些元元素素称称为为该该集集合合的的成成成成员员员员。集集合合中中的的成成员员可可以以是是一一个个原原子子（不不可可再再分分解解）；也也可可以以是是一一个个结构，甚至又是一个集合。集合中的各个元素应该是互不相同的。结构，甚至又是一个集合。集合中的各个元素应该是互不相同的。n n元素是或不是集合元素是或不是集合A A的成员，可表示为的成员，可表示为n n列列列列举举举举法法法法：定定

2、义义一一个个有有穷穷集集，可可以以将将成成员员放放在在一一对对花花括括号号中中，成成员员之之间间用用逗号隔开。逗号隔开。例如，例如，2 2，n n谓词描述法谓词描述法谓词描述法谓词描述法:n n集合的大小集合的大小集合的大小集合的大小:集合中所包含的元素的集合中所包含的元素的个数个数个数个数。n n空集不包含任何元素的集合，记作空集不包含任何元素的集合，记作。n n数数据据结结构构中中讨讨论论的的集集合合，一一般般有有以以下下限限限限制制制制：数数据据结结构构讨讨论论的的集集合合总总限限制制为为有有穷穷集集；假假定定集集合合中中所所有有元元素素属属同同一一类类型型；并并且且假假设设元素之间存在

3、一个元素之间存在一个小于关系小于关系小于关系小于关系“”，也称为，也称为有序集有序集有序集有序集。第2页，此课件共46页哦6.1.2 主要运算主要运算n n集合可以定义测试一个元素是否存在于集合中、增加一个元素、删除集合可以定义测试一个元素是否存在于集合中、增加一个元素、删除一个元素等运算，但集合更加关心下面的一些运算。一个元素等运算，但集合更加关心下面的一些运算。n n求求并集并集并集并集：n n求求交集交集交集交集：n n求求差集差集差集差集：n n子集子集子集子集：A A是是B B的子集的子集n n如果集合如果集合A A是是B B的子集，反过来也称集合的子集，反过来也称集合B B是是A

4、A的的超集超集超集超集。n n相等相等相等相等：两个集合互为子集，则称它们相等。：两个集合互为子集，则称它们相等。n n例如例如例如例如：若，则有：若，则有，。另外，不，。另外，不等于，同时和相互都不是子集关系。等于，同时和相互都不是子集关系。第3页，此课件共46页哦ADT Set is operationsSet createEmptySet(void)创建一个空集合。int member（Set，DataType）当时返回真值，否则取假值。int insert（Set，DataType）使作为的一个成员,如果本来就是的成员，则不变。int delete（Set，DataType）将从中删除

5、，如果本来就不在中，则不改变。int union（Set，Set，Set）求集合和的并集，结果在集合中。int intersection（Set，Set，Set）求集合和的交集，结果在集合中。int difference（Set，Set，Set）求集合和的差集，结果在集合中。int subset（Set，Set）当且仅当是的子集时，函数值才为真。endADT Set6.1.3 抽象数据类型抽象数据类型 第4页，此课件共46页哦6.2 集合的实现集合的实现 6.2.1 位向量表示位向量表示 n n在在实实际际应应用用中中的的许许多多集集合合，往往往往都都存存在在一一个个公公认认的的超超集集。例例

6、如如，ASCIIASCII码码字字符符集集是是各各种种算算机机能能够够表表示示的的字字符符集集的的超超集集；所所有有大大小小写英文字母的集合是各种字母集合的超集。写英文字母的集合是各种字母集合的超集。n n 对对于于字字母母集集合合，如如果果按按集集合合中中每每个个字字符符的的ASCIIASCII码码将将它它们们存存储储到到一一个个字字符符数数组组中中，则则集集合合将将占占用用较较多多的的存存储储空空间间（最最多多需需要要8*26*2=416bit8*26*2=416bit）。）。n n如如果果英英文文字字母母超超集集中中的的每每个个字字母母对对应应1-561-56中中的的一一个个数数值值，则

7、则字字母母集集可可以以表表示示为为一一个个有有5252个个分分量量的的向向量量，每每个个分分量量的的1 1或或0 0表表示示相相应应数数值值的的字字母母是是否否在在该该集集合合中中。这这样样每每个个字字母母集集合合只只占占用用很很少少的的存存储储空空间间（52bit52bit）。）。n n位位位位向向向向量量量量是是一一种种每每个个元元素素都都是是二二进进制制位位（即即0/10/1值值）的的数数组组。当当表表示示的的集集合合存存在在某某个个不不太太大大的的公公共共超超集集时时，采采用用位位向向量量的的方方式式来来表表示示这这种种集合往往十分有效。集合往往十分有效。第5页，此课件共46页哦存储结

8、构存储结构n n假假设设需需要要表表示示的的集集合合的的公公共共超超集集中中，共共有有个个不不同同的的元元素素，为为叙叙述述的的方便，不妨假设这些元素就是整数方便，不妨假设这些元素就是整数0 0，-1-1等。等。n n每每个个集集合合可可以以采采用用一一个个有有位位的的位位向向量量来来表表示示。若若整整数数是是这这个个集集合合的的一一个个元元素素，则则位位向向量量中中对对应应的的位位为为（真真），否否则为则为0 0（假）。（假）。n n由由于于C C语语言言中中无无法法直直接接定定义义位位数数组组，要要定定义义位位向向量量需需要要借借助助其其它它方方式式。一一种种比比较较自自然然的的方方式式，

9、是是用用长长度度为为n/8n/8的的字字符符数数组组表表示示长长度度为为n n的的字字位位数数组组。一一个个字字符符用用8 8位位二二进进制制编编码码，它它实实际际上上包包含含了了8 8个个二二进进制制位。位。typedef struct typedef struct int size;int size;/字符数组的长度字符数组的长度char*array;/char*array;/位向量空间。每一数组元素保存位向量空间。每一数组元素保存8 8位。位。BitSet;BitSet;第6页，此课件共46页哦n n假设假设n n是为向量的位数，因为是为向量的位数，因为n n不一定是不一定是8 8的整数

10、倍，所以由表达式的整数倍，所以由表达式（n+7n+7）/8/8计算出来的是能保证容纳下所有的位向量的最少字节数。计算出来的是能保证容纳下所有的位向量的最少字节数。n n为了便于操作的实现，位向量的下标在字符的为了便于操作的实现，位向量的下标在字符的8 8位中应该从右至左递位中应该从右至左递增排列。增排列。n n如图给出了公共超集从如图给出了公共超集从0 0到到9 9的整数集合采用位向量表示的存储结构示的整数集合采用位向量表示的存储结构示意图，以及集合意图，以及集合S=1,3,5,7,9S=1,3,5,7,9的实际存储。的实际存储。n n当用位向量表示集合时，所占空间的大小与公共超集的大小成正比

11、，当用位向量表示集合时，所占空间的大小与公共超集的大小成正比，而与要表示的集合的大小无关。而与要表示的集合的大小无关。第7页，此课件共46页哦算法实现算法实现n n以以位位向向量量表表示示集集合合，只只有有两两个个集集合合都都是是某某个个公公共共集集合合的的子子集集时时，它它们们互互相相运运算算才才是是有有效效的的。由由于于在在位位向向量量定定义义里里并并没没有有关关于于集集合合元元素素的的实实际际信信息息，只只能能要要求求参参与运算的两个位向量长度相同。与运算的两个位向量长度相同。n n位运算位运算n n假设假设x x和和y y都是都是8 8位的字符，其值分别是：位的字符，其值分别是：X=0

12、1010111 X=01010111 Y=11011010Y=11011010对对x x和和y y做各种字位运算，得到的结果如下：做各种字位运算，得到的结果如下：n nx 10101000 x 10101000n nx&y 01010010 x&y 01010010n nx y 10001101x y 10001101n nx|y 11011111x|y 11011111n nx 3 10111000 x 5 00000110y 5 00000110第8页，此课件共46页哦n n空集合的创建空集合的创建与空顺序表的的创建类似，不同之处在于这里省略了每个集与空顺序表的的创建类似，不同之处在于这里

13、省略了每个集合中实际元素个数的变量合中实际元素个数的变量:BitSet*createEmptySet(int n)BitSet*createEmptySet(int n)n n将整数将整数indexindex的元素插入集合的元素插入集合 将值为将值为indexindex的元素插入集合的元素插入集合S S的过程，通过将位向量中下标为的过程，通过将位向量中下标为indexindex的位置为的位置为1 1来完成：来完成：int insert(BitSet*s,int index)int insert(BitSet*s,int index)n n将整数将整数indexindex的元素从集合中删除的元素

14、从集合中删除 通过将位向量中下标为通过将位向量中下标为indexindex的位置为的位置为0 0来完成：来完成：int delete(BitSet*s,int index)int delete(BitSet*s,int index)n n判断整数判断整数indexindex的元素是否属于集合的元素是否属于集合 通过判断位向量中下标为通过判断位向量中下标为indexindex的位是否为的位是否为1 1来完成：来完成：int member(BitSet*s,int index)int member(BitSet*s,int index)第9页，此课件共46页哦n n集合与集合的并利用按位的利用按位

15、的“或或”运算实现。运算实现。int union(BitSet*s0,BitSet*s1,BitSet*s2)int union(BitSet*s0,BitSet*s1,BitSet*s2)n n集合与集合的交 这个运算很容易通过位这个运算很容易通过位“与与”操作实现。操作实现。int intersection(BitSet*s0,BitSet*s1,BitSet*s2)int intersection(BitSet*s0,BitSet*s1,BitSet*s2)n n集合与集合的差 将第一个集合与第二个集合的逆做与运算，就可以达将第一个集合与第二个集合的逆做与运算，就可以达到这个目的。到这个

16、目的。int difference(BitSet*s0,BitSet*s1,BitSet*s2)int difference(BitSet*s0,BitSet*s1,BitSet*s2)第10页，此课件共46页哦6.2.2 单链表表示单链表表示n n链链接接表表示示方方式式下下，在在链链表表中中存存放放的的是是集集合合中中元元素素的的实实际际数值，而不是元素是否属于集合的标记。数值，而不是元素是否属于集合的标记。n n链链表表中中的的每每个个结结点点表表示示集集合合中中的的一一个个元元素素，具具体体方方式式与与第二章单链表的结点第二章单链表的结点struct Nodestruct Node类似

17、。类似。n n不不同同之之处处在在于于：线线性性表表的的单单链链表表中中，linklink字字段段表表示示线线性性表表元元素素之之间间的的逻逻辑辑后后继继关关系系，而而在在这这里里仅仅仅仅是是把把属于同一集合的所有元素链接成一个整体。属于同一集合的所有元素链接成一个整体。n n因因为为我我们们讨讨论论的的是是有有序序集集，如如果果将将集集合合中中的的所所有有元元素素按按“”关关系系排排序序构构造造有有序序链链表表，给给集集合合的的某某些些运运算算会会带来方便。带来方便。第11页，此课件共46页哦struct Node;typedef struct Node *PNode;struct Node

18、 DataType info;PNode link;typedef struct Node *LinkSet;集合0，1，2，n-1采用带表头结点的有序链表表示：第12页，此课件共46页哦n n求单链表表示集合的交集求单链表表示集合的交集 int intersectionLink(LinkSet s0,LinkSet s1,LinkSet s2int intersectionLink(LinkSet s0,LinkSet s1,LinkSet s2）在在有有序序链链表表表表示示的的集集合合中中，在在s1s1中中找找到到第第一一个个与与s0s0中中相相同同元元素素后后，其其它它共共同同元元素素不

19、不需需要要从从头头开开始始比比较较，只只要要从刚才比较成功所结束的位置继续向后检索。从刚才比较成功所结束的位置继续向后检索。因因此此，只只要要用用两两个个指指针针，沿沿s0s0和和s1s1从从头头至至尾尾扫扫描描一一遍遍即即可可完完成成。当当这这两两个个表表的的长长度度为为和和时时，算算法法的的时时间总花费最多为（）。间总花费最多为（）。程序实现程序实现 算法实现算法实现第13页，此课件共46页哦n n集合的赋值集合的赋值 int assignLink(LinkSet s0,LinkSet s1)int assignLink(LinkSet s0,LinkSet s1)赋赋值值运运算算将将集集

20、合合s0s0拷拷贝贝成成集集合合s1s1，注注意意这这一一运运算算不不能能简简单单地地将将s0s0的的表表头头结结点点置置成成s1s1的的表表头头结结点点，因因为为若若这这样样处处理理，则则对对s1s1的的改改变变将会带来将会带来s0s0的改变。的改变。程序实现程序实现n n插入运算插入运算int insertLink(LinkSet s0,DataType x)int insertLink(LinkSet s0,DataType x)插插入入运运算算首首先先要要找找到到适适当当的的插插入入位位置置，它它有有两两个个参参数数：一一个个是是被被插插入入元素的信息元素的信息x x；另一个则是被插入

21、的集合；另一个则是被插入的集合s0s0。程序实现程序实现第14页，此课件共46页哦6.3 字典及其抽象数据类型字典及其抽象数据类型 6.3.1基本概念基本概念n n字字字字典典典典是是一一种种集集合合，其其中中每每个个元元素素由由两两部部分分组组成成，分分别别称称为为关关关关键键键键码码码码和和属属属属性性性性(或称为或称为值值值值)。这种包含关键码和属性的二元组称作。这种包含关键码和属性的二元组称作关联关联关联关联(Association)(Association)。n n抽抽象象地地看看，一一个个关关联联是是一一个个有有序序对对，它它可可以以看看成成是是由由关关键键码码值值k k到到属属性

22、性(值值)v)v的一个对应。字典就是由关键码集合到值集合的二元关系。的一个对应。字典就是由关键码集合到值集合的二元关系。n n字字典典中中的的元元素素之之间间能能够够根根据据其其关关键键码码进进行行比比较较大大小小，对对字字典典元元素素的的插入、删除和检索等操作一般也以关键码为依据进行。如英文字典。插入、删除和检索等操作一般也以关键码为依据进行。如英文字典。n n在实践中使用较多的字典里所有的关键码互不相同，这种关键码具有在实践中使用较多的字典里所有的关键码互不相同，这种关键码具有唯一性的字典，在数学中称为映射唯一性的字典，在数学中称为映射(mapping)(mapping)，数据结构里讲的就

23、是这种字，数据结构里讲的就是这种字典。典。n n字典关心的最主要的运算是字典关心的最主要的运算是检索检索检索检索。衡量一个字典检索算法效率的主要标。衡量一个字典检索算法效率的主要标准是检索过程中对关键码的平均比较次数以及算法的空间开销、算准是检索过程中对关键码的平均比较次数以及算法的空间开销、算法是否易于理解等因素。平均比较次数法是否易于理解等因素。平均比较次数第15页，此课件共46页哦6.3.2 抽象数据类型抽象数据类型n n假设用假设用DictionaryDictionary表示抽象数据类型字典，用表示抽象数据类型字典，用DicElementDicElement表示字表示字典元素类型，用典

24、元素类型，用KeyType KeyType 来表示元素中关键码的类型，用来表示元素中关键码的类型，用PositionPosition表示字典中元素的位置。表示字典中元素的位置。ADTADT Dictionary Dictionary is isoperationsoperationsDictionary createEmptyDictionary(void)Dictionary createEmptyDictionary(void)创建一个空字典。创建一个空字典。int search(Dictionary dic,KeyType key,Position p)int search(Dictio

25、nary dic,KeyType key,Position p)在字典在字典dicdic中检索关键码为中检索关键码为keykey的关联的位置的关联的位置p p。int insert(Dictionary dic,DicElement ele)int insert(Dictionary dic,DicElement ele)在字典在字典dicdic中插入关联中插入关联eleele。int delete(Dictionary dic,KeyType key)int delete(Dictionary dic,KeyType key)在字典在字典dicdic中删除关键码为中删除关键码为keykey的

26、关联。的关联。end ADTend ADT Dictionary Dictionary第16页，此课件共46页哦6.4 字典的顺序表示字典的顺序表示 6.4.1 存储结构存储结构n n从逻辑结构出发，字典中的元素是无序的，但为了实现的方便，从逻辑结构出发，字典中的元素是无序的，但为了实现的方便，可以把字典中的元素按关键码的大小组织成一个顺序表。可以把字典中的元素按关键码的大小组织成一个顺序表。typedef inttypedef intKeyType;KeyType;typedef inttypedef intDataType;DataType;typedef struct typedef s

27、truct KeyType key;KeyType key;/字典元素的关键码字段字典元素的关键码字段DataType value;DataType value;/字典元素的属性字段字典元素的属性字段 DicElement;DicElement;typedef struct typedef struct int MAXNUM;int MAXNUM;/字典中元素的个数上界字典中元素的个数上界 int n;int n;/为字典中实际元素的个数为字典中实际元素的个数 DicElement*element.;DicElement*element.;/存放字典中的元素存放字典中的元素 SeqDictio

28、nary;SeqDictionary;第17页，此课件共46页哦6.4.2 算法的实现算法的实现n n检检索索的的基基本本思思想想是是 从从字字典典的的一一端端开开始始顺顺序序扫扫描描，将将字字典典中中元元素素的的关关键键码码和和给给定定值值比比较较，如如果果相相等等，则则检检索索成成功功；当当扫扫描描结结束束时时，还还未未找找到到关关键键码码等于给定值的元素，则检索失败。这称为顺序检索算法。等于给定值的元素，则检索失败。这称为顺序检索算法。int seqSearch(SeqDictionary*pdic,KeyType key,int*position)int seqSearch(SeqDi

29、ctionary*pdic,KeyType key,int*position)n n在在 不不 考考 虑虑 检检 索索 失失 败败 的的 情情 况况 下下，顺顺 序序 检检 索索 的的 平平 均均 检检 索索 长长 度度 为为:ASL=1P1+2P2+ASL=1P1+2P2+nPn+nPnn n假假设设每每个个元元素素的的检检索索概概率率相相等等，即即Pi=1/nPi=1/n，则则平平均均检检索索长长度度为为 ASL=ASL=（1+n1+n）/2/2。n n成成功功检检索索的的平平均均比比较较次次数数约约为为字字典典长长度度的的一一半半。若若字字典典中中不不存存在在关关键键码码为为keykey

30、的元素，则需进行的元素，则需进行n n次比较。检索时间为次比较。检索时间为O(n)O(n)。n n顺顺序序检检索索的的优优点点是是算算法法简简单单且且适适应应面面广广。无无论论字字典典中中元元素素是是否否有有序序均均可可使使用用。缺缺点点是是平平均均检检索索长长度度较较大大，特特别别是是当当n n很很大大时时，检检索索效效率较低。率较低。n n一一 般般 情情 况况 下下，字字 典典 中中 各各 元元 素素 的的 检检 索索 概概 率率 不不 相相 等等。则则 当当P1P2P1P2PnPn时，平均检索长度最小。时，平均检索长度最小。n n因因此此，如如果果已已知知各各元元素素的的检检索索概概率

31、率，则则应应将将字字典典中中元元素素按按检检索索概概率率由大到小排序，以便提高检索效率。由大到小排序，以便提高检索效率。第18页，此课件共46页哦6.4.3 有序顺序表与二分法检索有序顺序表与二分法检索n n一种提高检索效率的方法是将字典元素按关键码递增(或者递减)的顺序排序，这种按照关键码大小排序的顺序表称为有序顺序表有序顺序表。n n对于有序顺序表，可还采用顺序检索的方法进行查找，当检索到元素的关键码大于(或者小于)给定值时，就可以返回检索失败的信息。n n二二分分法法检检索索是专门为有序顺序表设计的一种检索方法。第19页，此课件共46页哦二分法检索二分法检索n n二二二二分分分分法法法法

32、检检检检索索索索又又称称折折半半检检索索，是是一一种种效效率率较较高高的的检检索索方方法法，使使用用这这种种方方法法检检索索时时，要要求求字字典典的的元元素素在在顺顺序序表表中按关键码排序。中按关键码排序。n n基基本本思思想想：首首先先将将给给定定值值keykey与与数数组组中中间间位位置置上上元元素素的的关关键键码码比比较较，如如果果相相等等，则则检检索索成成功功；否否则则，若若keykey小小，则则在在数数组组前前半半部部分分中中继继续续进进行行二二分分法法检检索索，否否则则在在数数组组后后半半部部分分中中继继续续进进行行二二分分法法检检索索。这这样样，经经过过一一次次比比较较就就缩缩小

33、小一一半半的的查查找找区区间间，如如此此进进行行下下去去，直直到到能能够够确确定定检检索索成成功或检索失败为止。功或检索失败为止。int int binarySearch(SeqDictionary binarySearch(SeqDictionary*pdic,pdic,KeyType KeyType key,key,int int*position)*position)第20页，此课件共46页哦分析分析n n二二分分法法检检索索每每经经过过一一次次比比较较就就将将检检索索范范围围缩缩小小一一半半，第第i i次比较可能比较的元素数如下表次比较可能比较的元素数如下表:比较次数比较次数 可能比较

34、的元素个数可能比较的元素个数 1 1=21 1=20 0 2 2=2 2 2=21 1 3 4=2 3 4=22 2 j 2 j 2j-1j-1n n若若字字典典元元素素个个数数n n刚刚好好为为2 20 0+2+21 1+2+2j-1j-1=2=2j j-1-1则则最最大大检索长度为检索长度为j j；n n若若2 2j j-1n2-111时碰撞就不可避免。时碰撞就不可避免。n n用散列法表示的字典称为用散列法表示的字典称为散列表散列表散列表散列表（hash tablehash table）。主要应解决两个）。主要应解决两个问题：问题：n n一个是根据字典中元素的特点，选择适当的散列函数，使得

35、散列地址的分一个是根据字典中元素的特点，选择适当的散列函数，使得散列地址的分布尽可能均匀地分布在基本区域之中；布尽可能均匀地分布在基本区域之中；n n一个是根据存储空间的条件，设计具体的处理（同义词）碰撞的方法。一个是根据存储空间的条件，设计具体的处理（同义词）碰撞的方法。第23页，此课件共46页哦6.5.2 散列函数散列函数n n散列函数也称杂杂凑凑函函数数。要提高散列表的检索效率，散列函数的选取是关键。n n一般而言，散列函数的选取应根据具体问题具体分析的原则，针对具体字典元素关键码集合的特性，加上用户的需求和空间、时间的条件，去构造相对理想的散列函数。使散列函数计算出的地址尽可能均匀地分

36、布在希望的地址空间中。n n同时，为了提高关键码到地址的转换速度，散列函数应该尽可能简单。第24页，此课件共46页哦n n数字分析法数字分析法常常有这样的情况，关键码位数比基本区的地址码位常常有这样的情况，关键码位数比基本区的地址码位数多，这时可以对关键码的各位进行分析，丢掉分布数多，这时可以对关键码的各位进行分析，丢掉分布不均匀的位留下均匀的位作为地址。不均匀的位留下均匀的位作为地址。keykey h(key)h(key)0000003 319419426263263260000007 718318309097097090000006 6294294434364364300075861500

37、0758615715715000919697000919697997997000310329000310329329329 第25页，此课件共46页哦n n折叠法折叠法n n如果关键码的位数比地址位数多，且各位分布较均匀，如果关键码的位数比地址位数多，且各位分布较均匀，不适于用数字分析法，则可以考虑折叠法。不适于用数字分析法，则可以考虑折叠法。n n折叠法将关键码从某些地方断开，分为几部分，其中最大折叠法将关键码从某些地方断开，分为几部分，其中最大部分的长度等于地址码的长度，再加上其余部分，舍弃进部分的长度等于地址码的长度，再加上其余部分，舍弃进位。位。n n例如关键码为例如关键码为key=5

38、82422241key=582422241，要求转换为，要求转换为4 4位的地址码。位的地址码。下面两种折叠方法都是可行的：下面两种折叠方法都是可行的：58|2422|241 58|2422|241 移位折叠相加 移位相加 8 5 5 8 1 4 2 2 4 1 2 4 2 2 2 4 2 2 1 1 0 6 4 2 7 2 1h1(key)=1064,h2(key)=2721,第26页，此课件共46页哦n n中平方法中平方法n n先求出关键码的平方，然后取中间几位作为地址。先求出关键码的平方，然后取中间几位作为地址。n n例例如如：关关键键码码key=4731key=4731，4731473

39、12 2=22382361=22382361。如如果果地地址址长长度度为为3 3位位，则则可可以以取取第第三三位位到到第第五五位位作作为为散散列列地地址址，即即有有h1(4731)=382h1(4731)=382，当当然然也可以取也可以取4 46 6位，即有位，即有h2(4731)=823h2(4731)=823。n n基数转换法基数转换法n n把把关关键键码码看看作作是是另另一一个个进进制制的的表表示示，然然后后再再转转换换成成原原来来进进制制的的数数，最最后后用用数数字字分分析析法法取取其其中中几几位位作作为为散散列列地地址址。一一般般转转换换基基数数大大于于原原基基数数，且两个基数最好互

40、素。且两个基数最好互素。n n例例如如key=(236075)key=(236075)1010是是十十进进制制数数，把把它它看看作作十十三三进进制制数数(236075)(236075)1313，再转换成十进制数，再转换成十进制数 (236075)(236075)1313=213=2135 5+313+3134 4+613+6133 3+713+5=(841547)+713+5=(841547)1010n n然然后后参参考考其其它它关关键键码码的的分分布布和和地地址址空空间间大大小小，通通过过数数字字分分析析法法，选选 择择 其其 中中 几几 位位。假假 设设 选选 择择 了了 第第 二二 位位

41、 到到 第第 五五 位位，则则h(236075)=4154h(236075)=4154。第27页，此课件共46页哦除余法n n选选择择一一个个适适当当的的正正整整数数P P，用用P P去去除除关关键键码码，余余数数作作为为散散列列地地址址，即即h(key)=key%Ph(key)=key%P。这这个个方方法法的的关关键键是是选选取取适当的适当的P P。n n一般一般P P为不大于基本区域长度为不大于基本区域长度mm的最大素数比较好。的最大素数比较好。例如例如 m=8,16,32,64,128,256,512,1024m=8,16,32,64,128,256,512,1024可以取：可以取：p=

42、7,13,31,61,127,251,503,1019p=7,13,31,61,127,251,503,1019n n除除余余法法地地址址计计算算公公式式非非常常简简单单。但但是是对对于于动动态态字字典典和和关键码没有规律出现的情况，经常采用。关键码没有规律出现的情况，经常采用。第28页，此课件共46页哦6.5.3 碰撞的处理碰撞的处理-开地址法、拉链法开地址法、拉链法n n设给定一个元素，其关键码为key，首先使用选择的散列函数h,计算出散列地址h(key)。n n如何执行插入?n n如何执行检索?n n散列法要解决碰撞的问题：开地址法和拉链法第29页，此课件共46页哦n n在在基基本本区区

43、域域内内形形成成一一个个同同义义词词的的探探查查序序列列，沿沿着着探探查查序序列列逐逐个个查查找找，直直到到找找到到查查找找的的元元素素或或碰碰到到一一个个未未被被占占用用的的地地址址为为止止。若若插插入入元元素素，则则碰碰到到空空的的地地址址单单元元就就存存放放要要插插入入的的同同义义词词。若若检检索索元元素素，则则需需要要碰碰到到空空的的地地址址单单元元后后，才才能能说说明明表表中中没没有有待待查的元素查的元素(检索失败检索失败)。n n采采用用开开地地址址法法解解决决碰碰撞撞，是是在在基基本本区区域域内内存存放放同同义义词词，负负载载因因子子必必须须小小于于1 1，否否则则，一一定定有有

44、些些元元素素无无处处存存放放。负负载载因因子子越越小小，碰撞的可能性越小，查找速度越快，当然空间开销也越大。碰撞的可能性越小，查找速度越快，当然空间开销也越大。n n产产生生探探查查序序列列的的最最简简单单方方法法是是线线线线性性性性探探探探查查查查，即即将将基基本本存存储储区区看看作作一一个个循循环环表表。若若在在地地址址为为d=h(key)d=h(key)的的单单元元发发生生碰碰撞撞，则则依依次次探探查查下下述述地地址址单单元元 d+1,d+2,d+1,d+2,m-1,0,1,m-1,0,1,d-1,d-1(m(m为为基基本本存存储储区区的的长长度度)。直直到到找找到到一一个个空空单单元元

45、或或查查找找到到关关键键码码为为keykey的的元元素素为为止止。如如果果从从单单元元d d开开始始探探查查，查查找找一一遍遍后后，又又回回到到地地址址d d，则则表表示示基基本本存存储储区已经溢出。区已经溢出。碰撞的处理方法一：开地址法碰撞的处理方法一：开地址法第30页，此课件共46页哦n n已已知知关关键键码码集集合合K=18K=18，7373，1010，5 5，6868，9999，2727，4141，5151，3232，2525，设设散散列列表表基基本本区区域域用用数数组组elementelement表表示示，大大小小为为m(m=13)m(m=13)，散散列列函函数数h(key)=key

46、%13h(key)=key%13，用用线线性性探探查查法解决碰撞。法解决碰撞。n n按散列函数按散列函数d=key%13d=key%13计算每个元素的散列地址如下：计算每个元素的散列地址如下：h(18)=5,h(73)=8,h(10)=10,h(5)=5,h(68)=3,h(99)=8 h(27)=1,h(41)=2,h(51)=12,h(32)=6,h(25)=12n n最后的散列表为：最后的散列表为：线性探查法例子第31页，此课件共46页哦typedefintKeyType;typedefintDataType;typedefstructKeyTypekey;/*字典元素的关键码字段字典元

47、素的关键码字段*/DataTypevalue;/*字典元素的属性字段字典元素的属性字段*/DicElement;typedefstructintm;/*m为基本区域长度为基本区域长度*/DicElement*element;HashDictionary;/*DicElement是字典中元素类型是字典中元素类型*/存储结构存储结构第32页，此课件共46页哦算法算法n n创建空散列表创建空散列表创建空散列表创建空散列表PHashDictionary createEmptyDictionary(int m)PHashDictionary createEmptyDictionary(int m)创创建

48、建空空散散列列表表的的实实现现与与算算法法2.12.1类类似似,主主要要差差别别在在于于mm在在这这里里代代替替了了MAXNUMMAXNUM的的作作用用;另另外外,后后面面算算法法中中假假设设所所有有有有效效的的关关键键码码都都是是大大于于0 0的的整整数数，所所以以当当创创建建一一个个空空字字典典时时，所所有有元元素素的的关关键键码码初初始始化为一个不可能作为关键码的整数值化为一个不可能作为关键码的整数值0 0。程序实现程序实现n n检索算法检索算法检索算法检索算法int linearSearch(HashDictionary*phash,KeyType key,int*position)i

49、nt linearSearch(HashDictionary*phash,KeyType key,int*position)在在检检索索算算法法中中，返返回回1 1表表示示检检索索成成功功，*positionposition为为找找到到的的元元素素在在散散列列表表中中elementelement数数组组元元素素的的下下标标值值；返返回回0 0表表示示检检索索失失败败，这这时时如如果果散散列列表表中中还还有有可可插插入入的的空空间间，则则*positionposition给给出出合合适适的的插插入入位位置置，否否则则*positionposition中为中为1 1。n n插入算法插入算法插入算法

50、插入算法int linearInsert(HashDictionary*phash,DicElememt ele)int linearInsert(HashDictionary*phash,DicElememt ele)在在插插入入算算法法中中，首首先先调调用用检检索索算算法法，如如果果检检索索失失败败，再再根根据据提提供供的的位位置置信息将元素信息将元素eleele插入。插入。第33页，此课件共46页哦n n在上例中，h(32)=6，h(5)=5，32和5不是同义词，但是在解决5与18的碰撞时，5已经存入element6，使得在插入32时，32与5本来不冲突的两个非同义词之间发生了碰撞。用线