《数据结构：第9章查找A》由会员分享，可在线阅读，更多相关《数据结构：第9章查找A（42页珍藏版）》请在金锄头文库上搜索。
1、章章内内容容学时学时章章内内容容学时学时1绪绪论论27图图62线性表线性表68动态存储管理动态存储管理略略3栈和队列栈和队列49查找查找44串串410内部排序内部排序65数组和广义表数组和广义表411外部排序外部排序略略6树和二叉树树和二叉树812文件文件略略第第3次上机地点：南一楼次上机地点：南一楼204、208，中，中202第第12周周周一晚周一晚18:3021:30第第7章章作业作业7.17.1 7.37.3 （今天交）今天交）今天交）今天交）1数据结构课程的内容数据结构课程的内容29.1 9.1 基本概念基本概念9.2 9.2 静态查找表静态查找表9.9.3 3 动态查找表动态查找表9
2、.4 9.4 哈希表哈希表第第9 9章章 查找查找教材第教材第8 8、1111和和1212章省略，因章省略，因操作系统操作系统课程会涉及。课程会涉及。第第9章章作业作业9.39.89.319.339.39.89.319.3339.1 9.1 基本概念基本概念若表中存在特定元素，称查找成功，应输出该记录；若表中存在特定元素，称查找成功，应输出该记录；否则，称查找不成功（否则，称查找不成功（也应输出失败标志或失败位置也应输出失败标志或失败位置）查找表查找表查查找找查找成功查找成功查找不成功查找不成功静态查找静态查找动态查找动态查找关键字关键字主关键字主关键字次关键字次关键字由同一类型的数据元素（或
3、记录）构成的集合。由同一类型的数据元素（或记录）构成的集合。查询查询(Searching)特定元素特定元素是否在表中。是否在表中。只查找，不改变集合内的数据元素。只查找，不改变集合内的数据元素。既查找，又改变（增减）集合内的数据元素。既查找，又改变（增减）集合内的数据元素。记录中某个数据项的值，可用来识别一个记录记录中某个数据项的值，可用来识别一个记录(预先确定的记录的某种标志预先确定的记录的某种标志)可以可以唯一唯一标识一个记录的关键字标识一个记录的关键字例如例如“学号学号”例如例如“女女”是一种数据结构是一种数据结构识别若干记录的关键字识别若干记录的关键字4讨论讨论讨论讨论2 2：对查找表
4、常用的操作有：对查找表常用的操作有：对查找表常用的操作有：对查找表常用的操作有哪些？哪些？哪些？哪些？v查询某个查询某个“特定的特定的”数据元素是否在表中；数据元素是否在表中；v查询某个查询某个“特定的特定的”数据元素的各种属性；数据元素的各种属性；v在查找表中插入一元素；在查找表中插入一元素；v从查找表中删除一元素。从查找表中删除一元素。讨论讨论讨论讨论3 3：有哪些查找方法？：有哪些查找方法？：有哪些查找方法？：有哪些查找方法？查找方法取决于表中数据的排列方式查找方法取决于表中数据的排列方式;讨论：讨论：讨论讨论讨论讨论1 1：查找的过程是怎样的？：查找的过程是怎样的？：查找的过程是怎样的
5、？：查找的过程是怎样的？ 给定一个值给定一个值K，在含有在含有n n个记录的文件中进行搜索，寻找个记录的文件中进行搜索，寻找一个关键字值等于一个关键字值等于K的记录，如找到则输出该记录，否则输的记录，如找到则输出该记录，否则输出查找不成功的信息。出查找不成功的信息。例如查字典例如查字典针对静态查找表和动态查找表的查找方法也有所不同针对静态查找表和动态查找表的查找方法也有所不同。“特定的特定的”=关键关键字字5讨论讨论讨论讨论4 4：如何评估查找方法的优劣？如何评估查找方法的优劣？如何评估查找方法的优劣？如何评估查找方法的优劣？明确：明确：查找的过程就是将给定的查找的过程就是将给定的K值与文件中
6、各记录的关值与文件中各记录的关键字项进行比较的过程。所以用比较次数的平均值来评键字项进行比较的过程。所以用比较次数的平均值来评估算法的优劣。称为估算法的优劣。称为平均查找长度平均查找长度ASLASL。其中：其中：n n是文件记录个数；是文件记录个数；P Pi i是查找第是查找第i i个记录的查找概率（通常取个记录的查找概率（通常取等概率等概率, ,即即P Pi i =1/n =1/n）; ;C Ci i是找到第是找到第i i个记录时所经历的比较次数。个记录时所经历的比较次数。统计意义上的统计意义上的数学期望值数学期望值物理意义：物理意义：假设每一元素被查找的概率相同，则查找每一假设每一元素被查
7、找的概率相同，则查找每一元素所需的比较次数之总和再取平均，即为元素所需的比较次数之总和再取平均，即为ASLASL。显然，显然，ASLASL值越小，时间效率越高值越小，时间效率越高Average Search LengthAverage Search LengthASL=Pi.Ci6针对静态查找表的查找算法主要有：针对静态查找表的查找算法主要有：9.2 9.2 静态查找表静态查找表静态查找表的定义静态查找表的定义（抽象数据类型）（抽象数据类型）参见教材参见教材P216一、一、顺序查找（线性查找）顺序查找（线性查找）二、二、折半查找（二分或对分查找）折半查找（二分或对分查找）三、三、分块查找（索引
8、顺序查找）分块查找（索引顺序查找）四、四、静态树表的查找静态树表的查找ADTStaticSearchTable数据对象数据对象D:数据关系数据关系R：基本操作基本操作P：ADTStaticSearchTable7一、顺序查找一、顺序查找一、顺序查找一、顺序查找（Linearsearch，又称线性查找又称线性查找）（1）顺序表的机内存储结构：）顺序表的机内存储结构：typedefstructElemType*elem;/表基址，表基址，0 0号单元留空。表容量为全部元素号单元留空。表容量为全部元素intlength;/表长，即表中数据元素个数表长，即表中数据元素个数SSTable;顺序查找：用逐
9、一比较的办法顺序查找关键字，这显然是最直顺序查找：用逐一比较的办法顺序查找关键字，这显然是最直接的办法。接的办法。v对对顺序结构顺序结构如何线性查找？如何线性查找？v对对单链表结构单链表结构如何线性查找？如何线性查找？v对对非线性非线性树结构树结构如何顺序查找如何顺序查找? ?见下页之例见下页之例或教材或教材P216P216从从头头指指针针始始 “顺顺藤藤摸摸瓜瓜”借助各种遍历操作！借助各种遍历操作！8intSearch_Seq(SSTableST,KeyTypekey)ST.elem0.key=key;for(i=ST.length;ST.elemi.key!=key;-i);returni
10、;/Search_Seq（2）算法的实现：）算法的实现：技巧：技巧：把待查关键字把待查关键字keykey存入存入表头表头或或表尾表尾（俗称（俗称“哨兵哨兵”），），这样可以加快执行速度。这样可以加快执行速度。例：例：若将待查找的特定值若将待查找的特定值keykey存入顺序表的存入顺序表的首部首部（如（如0 0号单元）号单元），并，并从后向前从后向前逐个比较逐个比较, ,就不必担心就不必担心“查不到查不到”。/在顺序表在顺序表STST中，查找关键字与中，查找关键字与keykey相同的元素；相同的元素；若成功，返回其位置信息，否则返回若成功，返回其位置信息，否则返回0 0/设立哨兵，可免去查找过程
11、中每一步都要检设立哨兵，可免去查找过程中每一步都要检测是否查找完毕。当测是否查找完毕。当n1000n1000时，查找时间将减时，查找时间将减少一半。少一半。/找不到找不到= =不成功，返回值必为不成功，返回值必为i=0i=0； 找得到找得到= =成功，返回值成功，返回值i i正好代表所找元素的位置。正好代表所找元素的位置。/不要用不要用for(i=1; i=n; i+ +) for(i=1; i0; - -i)for(i=n; i0; - -i)9返回特殊标志，例如返回空记录或空指针。前例中设立了返回特殊标志，例如返回空记录或空指针。前例中设立了“哨兵哨兵”，就是将关键字送入末地址，就是将关键
12、字送入末地址ST.elemST.elem0 0.key.key使之结束，并返回使之结束，并返回 i=0i=0。讨论讨论讨论讨论2 2：查找效率怎样计算？查找效率怎样计算？查找效率怎样计算？查找效率怎样计算？用平均查找长度用平均查找长度ASL衡量。衡量。讨论讨论讨论讨论1 1：查找失败怎么办？查找失败怎么办？查找失败怎么办？查找失败怎么办？讨论讨论讨论讨论3 3：如何计算如何计算如何计算如何计算ASLASL？分析：分析：查找第查找第1个元素所需的比较次数为个元素所需的比较次数为1；查找第查找第2个元素所需的比较次数为个元素所需的比较次数为2；查找第查找第n个元素所需的比较次数为个元素所需的比较次
13、数为n；总计全部比较次数为：总计全部比较次数为：12n=(1+n)n/2未考虑查找不成功的情况：查未考虑查找不成功的情况：查找哨兵所需的比较次数为找哨兵所需的比较次数为n+1n+1这是查找成功的情况这是查找成功的情况若求某一个元素的平均查找次数，还应当除以若求某一个元素的平均查找次数，还应当除以n（等概率），等概率），即：即：ASL（1n）/2，时间效率为时间效率为O(n)10二、折半查找二、折半查找二、折半查找二、折半查找（又称（又称二分查找二分查找或或对分查找对分查找）优点：优点：算法简单，且对顺序结构或链表结构均适用。算法简单，且对顺序结构或链表结构均适用。缺点：缺点：ASL太大，时间效
14、率太低。太大，时间效率太低。这是一种容易想到的查找方法。这是一种容易想到的查找方法。先给数据排序先给数据排序（例如按升序排好），形成（例如按升序排好），形成有序表有序表，然后再将，然后再将keykey与与正中正中元素相比，若元素相比，若keykey小，则缩小至右半部内查找；再取小，则缩小至右半部内查找；再取其其中值中值比较，每次缩小比较，每次缩小1/21/2的范围，直到查找成功或失败为止。的范围，直到查找成功或失败为止。v对对顺序表结构顺序表结构顺序表结构顺序表结构如何编程实现折半查找算法？如何编程实现折半查找算法？见下页之例见下页之例，或见教材（，或见教材（P219P219）v对对单链表结构
15、单链表结构单链表结构单链表结构如何折半查找？如何折半查找？无法实现！无法实现！因全部元素的定位只能从头指针因全部元素的定位只能从头指针headhead开始开始v对对非线性非线性非线性非线性( (树树树树) )结构结构结构结构如何折半查找？如何折半查找？可借助可借助二叉排序树二叉排序树来查找（属动态查找表形式）。来查找（属动态查找表形式）。讨论讨论讨论讨论4 4：顺序查找的特点：顺序查找的特点：顺序查找的特点：顺序查找的特点：如何改进如何改进？11 运算步骤运算步骤：(1) low =1,high =11 ,(1) low =1,high =11 ,故故mid =6 mid =6 ，待查范围是待
16、查范围是 1,111,11；(2) (2) 若若 ST.elemmid.keyST.elemmid.key key keykey，说明说明keykey low ,midlow ,mid-1-1 ， 则令：则令：high =mid1high =mid1; ;重算重算 mid mid ；(4)(4)若若 ST.elemST.elem mid .key mid .key = key= key，说明查找成功，元素序号说明查找成功，元素序号=mid;=mid;结束条件：结束条件： （1 1）查找成功）查找成功 ： ST.elemmid.keyST.elemmid.key = key = key （2 2
17、）查找不成功查找不成功 ： highlowhighdata: 查找成功，return Kdata : q=p；p=p-L_child /继续向左搜索 K p-data : q=p；p=p-R_child /继续向右搜索 /查找不成功则插入到二叉排序树中介绍一个查找、插入介绍一个查找、插入“二合一二合一”的非递归程序：的非递归程序：23s =(BiTree)malloc(sizeof(BiTNode); s-data=K; s -L_child=NULL; s -R_child=NULL; /查找不成功，生成一个新结点s，插入到二叉排序树叶子处case t=NULL： t=s; /若t为空，则插
18、入的结点s作为根结点K data: q-L_child=s; /若K比叶子小，挂左边K q-data: q-R_child=s; /若K比叶子大，挂右边 return OK插入模块（插入模块（非递归方式非递归方式）参见教材参见教材P228P228算法算法9.59.5（b b）; ;查找模块（查找模块（递归方式）递归方式） 参见教材参见教材P228P228算法算法9.59.5（a a）; ;以上为以上为查找、插入查找、插入二合一的非递归程序二合一的非递归程序该模块就是该模块就是“建树建树”的非递归算法！的非递归算法！24对于二叉排序树，删除树上一个结点相当于删除有序序列中对于二叉排序树，删除树上
19、一个结点相当于删除有序序列中的一个记录，要求删除后仍需保持二叉排序树的特性。的一个记录，要求删除后仍需保持二叉排序树的特性。讨论讨论讨论讨论2 2 2 2：二叉排序树的删除操作如何实现？：二叉排序树的删除操作如何实现？：二叉排序树的删除操作如何实现？：二叉排序树的删除操作如何实现？如何删除一个结点？如何删除一个结点？假设：假设：* *p p表示被删结点的指针；表示被删结点的指针； P PL和和PR分别表示分别表示* *P P的左、右孩子指针；的左、右孩子指针；* *f f表示表示* *p p的的双亲结点指针；并假定双亲结点指针；并假定* *p p是是* *f f的的左孩子左孩子；则可能有三种情
20、况：；则可能有三种情况：* *p p为叶子：为叶子： 删除此结点时，直接修改删除此结点时，直接修改* *f f指针域即可；指针域即可；* *p p只有一棵子树（或左或右）：只有一棵子树（或左或右）：令令P PL或或PR为为* *f f的左孩子即可；的左孩子即可；* *p p有两棵子树：情况最复杂有两棵子树：情况最复杂 f fp pP PLPR25分析：分析：设删除前的设删除前的中序中序遍历序列为：遍历序列为：.PLspPRf. /显然显然p p的直接前驱是的直接前驱是s s /s /s是是* *p p左子树最右下方的结点左子树最右下方的结点希望删除希望删除p p后，其它元素的相对位置不变。有两
21、种解决方法：后，其它元素的相对位置不变。有两种解决方法：法法1 1：令令* *p p的左子树为的左子树为 * *f f的左子树，的左子树，* *p p的右子树接为的右子树接为* *s s的右的右子树；子树； /即即 fL=PL ; SR=PR ;法法2 2：直接令直接令* *s s代替代替* *p p / *s*s为为* *p p左子树最右下方的结点左子树最右下方的结点难点：难点：* *p p有两棵子树时，如何进行删除操作？有两棵子树时，如何进行删除操作？f fp pP PLPRs26F FC CCLS SSLQLPPRQPRF FC CCLS SSLQLPPRQ法法2:2:F FC CCLS
22、 SSLQLPPRQ法法1:1:例：例：请从下面的二叉排序树中删除结点请从下面的二叉排序树中删除结点P。S SSL27三、二叉排序树的查找分析三、二叉排序树的查找分析最坏情况最坏情况（单支树）单支树）：插入的插入的n个元素从一开始就有序个元素从一开始就有序此时树深为此时树深为n;ASL=(n+1)/2;与顺序查找情况相同。与顺序查找情况相同。最好情况最好情况（形态均衡）（形态均衡）：与折半查找中的判定树相同与折半查找中的判定树相同此时树深为：此时树深为： log2n +1；ASL=log2(n+1)1；与折半查找情况相同。与折半查找情况相同。一般情况：一般情况：（与（与logn同阶）同阶）思考
23、：思考：如何提高二叉排序树的查找效率？如何提高二叉排序树的查找效率？尽量让二叉树的形状均衡尽量让二叉树的形状均衡平衡二叉树平衡二叉树ASL=2(1+1/n)lnn28平衡二叉树的特点：平衡二叉树的特点：平衡二叉树的特点：平衡二叉树的特点：任一结点的平衡因子只能取：任一结点的平衡因子只能取：-1、0或或1。对于一棵有对于一棵有n个结点的个结点的AVL树树，其其高度高度保持在保持在O(log2n)数量级数量级则则ASL也保持在也保持在O(log2n)量级量级(a) (a) 平衡树平衡树 (b) (b) 不平衡树不平衡树0001 11 1-1-12 2 2 20001-129如果在一棵如果在一棵AV
24、L树中插入一个新结点，就有可能造树中插入一个新结点，就有可能造成失衡，此时必须成失衡，此时必须重新调整树的结构重新调整树的结构，使之恢复，使之恢复平衡。我们称调整平衡过程为平衡。我们称调整平衡过程为平衡旋转平衡旋转。平衡旋转可以归纳为四类：平衡旋转可以归纳为四类：v LL平衡旋转平衡旋转v RR平衡旋转平衡旋转v LR平衡旋转平衡旋转v RL平衡旋转平衡旋转这种调整规则可以保证二叉排序树的次序不变这种调整规则可以保证二叉排序树的次序不变这种调整规则可以保证二叉排序树的次序不变这种调整规则可以保证二叉排序树的次序不变300 013130 037370 02424例：例：请将下面序列构成一棵请将下
25、面序列构成一棵平衡平衡二叉二叉排序排序树：树：（13，24，37，90，53）0 013130 03737-1-113130 02424-1-12424-2-2-2-21313需要需要RR平衡旋转平衡旋转(绕绕B逆转逆转,B为根）为根）0 09090-1-12424-1-137370 053531 19090-2-2-2-23737需要需要RL平衡旋转平衡旋转(绕绕C先顺后逆）先顺后逆）0 037370 090900 053530 037370 090900 05353跳过跳过跳过跳过31若在若在A的的左左子树的子树的左左子树上插入子树上插入结点，使结点，使A的平衡因子从的平衡因子从1增加至增
26、加至2，需要进行一次，需要进行一次顺时针旋转顺时针旋转。A AB BC CA AB BC C若在若在A的的右右子树的子树的右右子树上插入子树上插入结点，使结点，使A的平衡因子从的平衡因子从-1增加增加至至-2，需要进行一次，需要进行一次逆时针旋转逆时针旋转。2 2）RRRR平衡旋转：平衡旋转：平衡旋转：平衡旋转：A AB BC CA AB BC C1 1）LLLL平衡旋转：平衡旋转：平衡旋转：平衡旋转：以以B为旋转轴为旋转轴以以B为旋转轴为旋转轴32A AB BC C若在若在A的的右右子树的子树的左左子树上插入结子树上插入结点，使点，使A的平衡因子从的平衡因子从-1增加至增加至-2，需要先进行
27、，需要先进行顺时针顺时针旋转，再旋转，再逆逆时针时针旋转。旋转。4 4）RLRL平衡旋转：平衡旋转：平衡旋转：平衡旋转：A AB BC C A AB BC C若在若在A的的左左子树的子树的右右子树上插入子树上插入结点，使结点，使A的平衡因子从的平衡因子从1增加至增加至2，需要先进行，需要先进行逆时针逆时针旋转，再旋转，再顺时针顺时针旋转。旋转。3 3）LRLR平衡旋转：平衡旋转：平衡旋转：平衡旋转：A AB BC C这种调整规则可以保证二叉排序树的次序不变这种调整规则可以保证二叉排序树的次序不变这种调整规则可以保证二叉排序树的次序不变这种调整规则可以保证二叉排序树的次序不变以插入的结点以插入的
28、结点C为旋转轴为旋转轴以插入的结点以插入的结点C为旋转轴为旋转轴A AB BC CA AB BC CB BA AC C339.1 9.1 基本概念基本概念9.2 9.2 静态查找表静态查找表9.9.3 3 动态查找表动态查找表9.4 9.4 哈希查找表哈希查找表第第9 9章章 查找查找教材第教材第8 8、1111和和1212章省略，因章省略，因操作系统操作系统课程会涉及。课程会涉及。1、顺序查找（线性查找）顺序查找（线性查找）2、折半查找（二分或对分查找）折半查找（二分或对分查找）3、分块查找（索引顺序查找）分块查找（索引顺序查找）4、静态树表的查找静态树表的查找（次优树次优树）二叉排序树二叉
29、排序树第第第第9 9章作业章作业章作业章作业9.39.89.319.339.39.89.319.33349.4 9.4 哈希查找表哈希查找表一、一、哈希表的概念哈希表的概念二、哈希函数的构造方法哈希函数的构造方法三、冲突处理方法冲突处理方法四、四、哈希表的查找及分析哈希表的查找及分析是一种查找效率高达是一种查找效率高达是一种查找效率高达是一种查找效率高达O(1)O(1)的算法！的算法！的算法！的算法！35一、哈希表的概念一、哈希表的概念哈希表：哈希表：即散列存储结构。即散列存储结构。 散列法存储的基本思想：散列法存储的基本思想：建立建立关键码字关键码字与其与其存储位置存储位置的的对应对应关系，
30、关系，或者说，由关键码的或者说，由关键码的值值决定数据的存储决定数据的存储地址地址。 优点：优点：查找速度极快（查找速度极快（O(1)O(1)）, ,查找效率与元素个数查找效率与元素个数n n无关！无关！例例1 1：若将学生信息按如下方式存入计算机，如：若将学生信息按如下方式存入计算机，如：将将20010118102200101181020101的所有信息存入的所有信息存入VV0101 单元；单元；将将20010118102200101181020202的所有信息存入的所有信息存入VV0202 单元；单元；将将20010118102200101181023131的所有信息存入的所有信息存入V3
31、1V31单元。单元。欲查找学号为欲查找学号为20010118102200101181021616的信息，便可直接访问的信息，便可直接访问V16V16！36例例2：有有数数据据元元素素序序列列(14(14，2323，3939，9 9，2525，11)11)，若若规规定定每个元素每个元素k k的存储地址的存储地址H H（k k）k k，请画出存储结构图。请画出存储结构图。解：解：根据散列函数根据散列函数H H（k k）k k ，可知元素可知元素1414应当存入地址为应当存入地址为1414的单元，元素的单元，元素2323应当存入地址为应当存入地址为2323的单元，的单元，对应散列存储表（哈希表）如下
32、：对应散列存储表（哈希表）如下：讨论：如何进行散列查找？讨论：如何进行散列查找？根据存储时用到的散列函数根据存储时用到的散列函数H(k)H(k)表达式表达式，迅即可查到结果！，迅即可查到结果！例如，查找例如，查找key=9,key=9,则访问则访问H(9)=9H(9)=9号地址，若内容为号地址，若内容为9 9则成功；则成功；若查不到，应当设法返回一个特殊值，例如空指针或空记录。若查不到，应当设法返回一个特殊值，例如空指针或空记录。 地址地址 9 11 14 23 24 25 39 内容内容14119232539明显缺点：空间效率低明显缺点：空间效率低明显缺点：空间效率低明显缺点：空间效率低如何
33、解决？如何解决？如何解决？如何解决？H(k)H(k)称为散列函数称为散列函数37选取某个函数，依该函数选取某个函数，依该函数按关键字计算元素的存储位置按关键字计算元素的存储位置并按此存放；查找时也并按此存放；查找时也由同一个函数由同一个函数对给定值对给定值k k计算地址计算地址，将将k k与地址中内容进行比较，确定查找是否成功。与地址中内容进行比较，确定查找是否成功。通常关键码的集合比哈希地址集合大得多，因而经通常关键码的集合比哈希地址集合大得多，因而经过哈希函数变换后，过哈希函数变换后，可能将不同的关键码映射到同可能将不同的关键码映射到同一个哈希地址上一个哈希地址上，这种现象称为，这种现象称
34、为冲突冲突。Hash查找法查找法哈希方法哈希方法( (杂凑法杂凑法) )哈希函数哈希函数( (杂凑函数杂凑函数) )哈希表哈希表( (杂凑表杂凑表) ) 冲冲 突突哈希方法中使用的转换函数称为哈希方法中使用的转换函数称为哈希函数哈希函数( (杂杂凑函数凑函数) )按上述思想构造的表称为按上述思想构造的表称为哈希表哈希表( (杂凑表杂凑表) ) 用尽量少的冗余空间实现用尽量少的冗余空间实现O(1)O(1)的查找效率的查找效率38有有6个元素的关键码分别为：（个元素的关键码分别为：（14，23，39，9，25，11）。）。选取关键码与元素位置间的函数为选取关键码与元素位置间的函数为H(k)=kmo
35、d7通过哈希函数对通过哈希函数对6 6个元素建立哈希表：个元素建立哈希表：253923914冲突现象举例：冲突现象举例：冲突现象举例：冲突现象举例：6个元素用个元素用7个个地址应该足够地址应该足够!H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4有有有有冲突！冲突！冲突！冲突！012345639所以，所以，所以，所以，哈希方法必须解决以下两个问题：哈希方法必须解决以下两个问题：哈希方法必须解决以下两个问题：哈希方法必须解决以下两个问题：1 1）构造好的哈希函数构造好的哈希函数构造好的哈希函数构造好的哈希函数（a a）所选函数尽可能所选函数尽可能简单简单，以便提高转换
36、速度；，以便提高转换速度；（b b）所选函数对关键码计算出的地址，应在哈希地址内集所选函数对关键码计算出的地址，应在哈希地址内集中并大致中并大致均匀均匀分布，以减少空间浪费。分布，以减少空间浪费。2 2 2 2）制定一个好的解决冲突的方案）制定一个好的解决冲突的方案）制定一个好的解决冲突的方案）制定一个好的解决冲突的方案查查找找时时，如如果果从从哈哈希希函函数数计计算算出出的的地地址址中中查查不不到到关关键键码码，则则应当依据解决冲突的规则，应当依据解决冲突的规则，有规律地查询其它有规律地查询其它相关单元。相关单元。在哈希查找方法中，在哈希查找方法中，在哈希查找方法中，在哈希查找方法中，冲突是
37、不可能避免的冲突是不可能避免的冲突是不可能避免的冲突是不可能避免的，只能，只能，只能，只能尽可能减少。尽可能减少。尽可能减少。尽可能减少。40关于实验报告要求：关于实验报告要求：参加参加参加参加“ “种子杯种子杯种子杯种子杯” ”比赛的同学，可以用赛题撰写报告；其他同比赛的同学，可以用赛题撰写报告；其他同比赛的同学，可以用赛题撰写报告；其他同比赛的同学，可以用赛题撰写报告；其他同学建议以学建议以学建议以学建议以“ “HuffmanHuffman编编编编/ /译码器的译码器的译码器的译码器的设计与实现设计与实现设计与实现设计与实现” ”或接近商业软件或接近商业软件或接近商业软件或接近商业软件的内
38、容为主题撰写报告。的内容为主题撰写报告。的内容为主题撰写报告。的内容为主题撰写报告。交报告截止时间：交报告截止时间：交报告截止时间：交报告截止时间：1212周四最后一次课前提交打印的纸质文档周四最后一次课前提交打印的纸质文档周四最后一次课前提交打印的纸质文档周四最后一次课前提交打印的纸质文档给任课教师；给任课教师；给任课教师；给任课教师； 报告格式请按严蔚敏习题集报告格式请按严蔚敏习题集报告格式请按严蔚敏习题集报告格式请按严蔚敏习题集P75P75的的的的“ “实习报告规范实习报告规范实习报告规范实习报告规范” ”撰写；撰写；撰写；撰写； 正文一律用小四号仿宋，附录源码一律用正文一律用小四号仿宋
39、，附录源码一律用正文一律用小四号仿宋，附录源码一律用正文一律用小四号仿宋，附录源码一律用5 5号或小五号字体；号或小五号字体；号或小五号字体；号或小五号字体；文档封面一律用：文档封面一律用：文档封面一律用：文档封面一律用：第第9章章作业作业9.39.89.319.339.39.89.319.3341数据结构数据结构数据结构数据结构课程实验报告课程实验报告课程实验报告课程实验报告题目：题目：题目：题目：XXXXXXXXXXXX班级：班级：班级：班级：姓名：姓名：姓名：姓名：学号：学号：学号：学号：同组者：同组者：同组者：同组者：指导教师：指导教师：指导教师：指导教师：华中科技大学电信系华中科技大学电信系华中科技大学电信系华中科技大学电信系20102010年年年年1111月月月月42
