第九章 查找⒈⒈教学内容：教学内容：9.1 基本概念与术语9.2 静态查找表9.3 动态查找表9.4 哈希表查找7/25/20241 在英汉字典中查找某个英文单词的中文解释；在新华字典中查找某个汉字的读音、含义；在对数表、平方根表中查找某个数的对数、平方根；邮递员送信件要按收件人的地址确定位置等等可以说查找是为了得到某个信息而常常进行的工作 计算机、计算机网络使信息查询更快捷、方便、准确要从计算机、计算机网络中查找特定的信息，就需要在计算机中存储包含该特定信息的表如要从计算机中查找英文单词的中文解释，就需要存储类似英汉字典这样的信息表，以及对该表进行的查找操作本章将讨论的问题即是“信息的存储和查找” 查找是许多程序中最消耗时间的一部分操作因而，一个好的查找方法可以大大提高运行速度另外，由于计算机的特性，象对数、平方根等是通过函数求解，无需存储相应的信息表7/25/20242 9.1 基本概念与术语7/25/20243 以学校招生录取登记表为例，来讨论计算机中表的概念 学学 号号姓姓 名名性性别别出生日期出生日期来来 源源总分总分录取专业录取专业年年月月日日┆ ┆200109832001098420010985┆ ┆┆ ┆赵剑平赵剑平蒋伟峰蒋伟峰郭郭 娜娜┆ ┆┆ ┆男男男男女女┆ ┆┆ ┆198219821983┆ ┆┆ ┆110901┆ ┆┆ ┆051225┆ ┆┆ ┆石家庄一石家庄一中中保定三中保定三中易县中学易县中学┆ ┆┆ ┆593601598┆ ┆┆ ┆计算机计算机计算机计算机计算机计算机┆ ┆图 9.１ 学校招生录取登记表7/25/20244 1.1.数据项 (也称项或字段) 项是具有独立含义的标识单位，是数据不可分割的最小单位。
如表中“学号”、“姓名”、 “年”等项有名和值之分，项名是一个项的标识，用变量定义，而项值是它的一个可能取值，表中“20010983”是项“学号”的一个取值项具有一定的类型，依项的取值类型而定2.2.组合项 由若干项、组合项构成，表中“出生日期”就是组合项，它由“年”、“月”、“日”三项组成7/25/20245 3.3.数据元素（记录） 数据元素是由若干项、组合项构成的数据单位，是在某一问题中作为整体进行考虑和处理的基本单位数据元素有型和值之分，表中项名的集合，也即表头部分就是数据元素的类型；而一个学生对应的一行数据就是一个数据元素的值，表中全体学生即为数据元素的集合4.4.关键码关键码 关键码是数据元素（记录）中某个项或组合项的值，用它可以标识一个数据元素（记录）能唯一确定一个数据元素（记录）的关键码，称为主关键码；而不能唯一确定一个数据元素（记录）的关键码，称为次关键码表中“学号”即可看成主关键码，“姓名”则应视为次关键码，因可能有同名同姓的学生7/25/20246 5.查找表 是由具有同一类型（属性）的数据元素（记录）组成的集合分为静态查找表和动态查找表两类静态查找表：仅对查找表进行查找操作，而不能改变的表；动态查找表：对查找表除进行查找操作外，可能还要进行向表中插入数据元素，或删除表中数据元素的表。
6.查找 按给定的某个值kx，在查找表中查找关键码为给定值kx的数据元素（记录） 关键码是主关键码时：由于主关键码唯一，所以查找结果也是唯一的，一旦找到，查找成功，结束查找过程，并给出找到的数据元素（记录）的信息，或指示该数据元素（记录）的位置要是整个表检测完，还没有找到，则查找失败，此时，查找结果应给出一个“空”记录或“空”指针关键码是次关键码时：需要查遍表中所有数据元素（记录），或在可以肯定查找失败时，才能结束查找过程7/25/20247 7.数据元素类型说明 在手工绘制表格时，总是根据有多少数据项，每个数据项应留多大宽度来确定表的结构，即表头的定义然后，再根据需要的行数，画出表来在计算机中存储的表与手工绘制的类似，需要定义表的结构，并根据表的大小为表分配存储单元以图 9.１为例，用C语言的结构类型描述之 /* 出生日期类型定义 */typedef struct { char year[5]； /* 年：用字符型表示，宽度为4个字符 */ char month[3]； /* 月：字符型，宽度为 2 */ char date[3]； /* 日：字符型，宽度为 2 */ }BirthDate；； 7/25/20248 /* 数据元素类型定义 */typedef struct { char number[7]； /* 学号：字符型，宽度为6 */ char name[9]； /* 姓名：字符型，宽度为8 */ char sex[3]； /* 性别：字符型，宽度为2 */ BirthDate birthdate； /* 出生日期：构造类型，由该类型的宽度确定 */ char comefrom[21]； /* 来源：字符型，宽度为20 */ int results； /* 成绩：整型，宽度由 “程序设计C语言工具软件”决定 */ } ElemType；7/25/20249 以上定义的数据元素类型，相当于手工绘制的表头。
要存储学生的信息，还需要分配一定的存储单元，即给出表长度可以用数组分配，即顺序存储结构；也可以用链式存储结构实现动态分配 本章以后讨论中，涉及的关键码类型和数据元素类型统一说明如下：typedef struct { KeyType key； /* 关键码字段，可以是整型、字符串型、构造类型等*/ …… /* 其它字段 */ } ElemType； 7/25/202410 9.2 静态查找表 静态查找表结构顺序查找有序表的折半查找7/25/202411 静态查找表是数据元素的线性表，可以是基于数组的顺序存储或以线性链表存储 /* 顺序存储结构 */ typedef struct{ ElemType *elem； /* 数组基址 */ int length； /* 表长度 */ }S_TBL； 9.2.1 静态查找表结构7/25/202412 /* 链式存储结构结点类型 */ typedef struct NODE{ ElemType elem； /* 结点的值域 */ truct NODE *next； /* 下一个结点指针域 */ }NodeType； 7/25/202413 9.2.2 顺序查找顺序查找又称线性查找，是最基本的查找方法之一。
其查找方法为：从表的一端开始，向另一端逐个按给定值kx与关键码进行比较，若找到，查找成功，并给出数据元素在表中的位置；若整个表检测完，仍未找到与kx相同的关键码，则查找失败，给出失败信息7/25/202414 【算法9.1】以顺序存储为例，数据元素从下标为1的数组单元开始存放，0号单元留空 int s_search(S_TBL tbl，KeyType kx) { /*在表tbl中查找关键码为kx的数据元素，若找到返回该元素在数组中的下标，否则返回0 */ tbl.elem[0].key = kx；/* 存放监测，这样在从后向前查找失败时，不必判表是否检测完，从而达到算法统一*/ for (i = tbl.length;tbl.elem[i].key<>kx;i--)； /* 从标尾端向前找 */ return i； }7/25/202415 【性能分析】 分析查找算法的效率，通常用平均查找长度ASL来衡量 定义：在查找成功时，平均查找长度ASL是指为确定数据元素在表中的位置所进行的关键码比较次数的期望值。
对一个含n个数据元素的表，查找成功时 其中：Pi为表中第i个数据元素的查找概率， Ci为表中第i个数据元素的关键码与给定值kx相等时，按算法定位时关键码的比较次数显然，不同的查找方法，Ci可以不同ASL=Pi·Ci n∑i=1n∑i=1Pi=17/25/202416 Ci为表中第i个数据元素的关键码与给定值kx相等时，按算法定位时关键码的比较次数显然，不同的查找方法，Ci可以不同 就上述算法而言，对于n个数据元素的表，给定值kx与表中第i个元素关键码相等，即定位第i个记录时，需进行n-i+1次关键码比较，即Ci=n-i+1则查找成功时，顺序查找的平均查找长度为: 设每个数据元素的查找概率相等，则等概率情况下有 查找不成功时，关键码的比较次数总是 n+1 次 算法中的基本工作就是关键码的比较，因此，查找长度的量级就是查找算法的时间复杂度，其为O(n)ASL=Pi·（n-i+1） n∑i=1 n∑i=1 ASL=（n-i+1）=１─ｎｎ＋１─── ２7/25/202417 许多情况下，查找表中数据元素的查找概率是不相等的。
为了提高查找效率，查找表需依据查找概率越高，比较次数越少；查找概率越低，比较次数就较多的原则来存储数据元素 顺序查找缺点是当n很大时，平均查找长度较大，效率低；优点是对表中数据元素的存储没有要求另外，对于线性链表，只能进行顺序查找7/25/202418 有序表即是表中数据元素按关键码升序或降序排列 折半查找的思想为：在有序表中，取中间元素作为比较对象，若给定值与中间元素的关键码相等，则查找成功；若给定值小于中间元素的关键码，则在中间元素的左半区继续查找；若给定值大于中间元素的关键码，则在中间元素的右半区继续查找不断重复上述查找过程，直到查找成功，或所查找的区域无数据元素，查找失败9.2.3 有序表的折半查找7/25/202419 【步骤】 ① low=1；high=length； // 设置初始区间 ② 当low>high时，返回查找失败信息 //表空，查找失败 ③ low≤high，mid=(low+high)/2; //取中点 a. 若kxtbl.elem[mid].key，low=mid+1；转② // 查找在右半区进行 c. 若kx=tbl.elem[mid].key，返回数据元素在表中位置 // 查找成功 7/25/202420 【例9.１】有序表按关键码排列如下： 7，14，18，21，23，29，31，35，38，42，46，49，52在表中查找关键码为14和22的数据元素。
7/25/202421 ⑴ 查找关键码为14的过程 ↑ ↑ low=1 ①设置初始区间 high=13 ─────────────────────────── ↑ ②表空测试，非空； mid=7 ③得到中点，比较测试为a情形 ↑ ↑ low=1 high=6 high=mid-1，调整到左半区 ─────────────────────────── 0 1 2 3 4 5 6 7 8 91011121371418212329313538424649527/25/202422 0 1 2 3 4 5 6 7 8 9101112137141821232931353842464952 ↑ ②表空测试，非空； mid=3 ③得到中点，比较测试为a情形 ↑ ↑ low=1 high=2 high=mid-1，调整到左半区 ─────────────────────────── ↑ ②表空测试，非空； mid=1 ③得到中点，比较测试为b情形 ↑↑ low=2 high=2 low=mid+1，调整到右半区 7/25/202423 0 1 2 3 4 5 6 7 8 9101112137141821232931353842464952 ↑ ②表空测试，非空； mid=2 ③得到中点，比较测试为c情形 查找成功，返回找到的数据元素位置为2 ⑵ 查找关键码为22的过程7/25/202424 0 1 2 3 4 5 6 7 8 9101112137141821232931353842464952 ↑ ↑ low=1 ①设置初始区间 high=13 ─────────────────────────── ↑ ②表空测试，非空； mid=7 ③得到中点，比较测试为a情形 ↑ ↑ low=1 high=6 high=mid-1，调整到左半区 ────────────────────────── ↑ ②表空测试，非空； mid=3 ③得到中点，比较测试为b情形 ↑ ↑ low=4 high=6 low=mid+1，调整到右半区 ───────────────────────────7/25/202425 0 1 2 3 4 5 6 7 8 9101112137141821232931353842464952 ↑ ②表空测试，非空； mid=5 ③得到中点，比较测试为a情形 ↑↑ low=4 high=4 high=mid-1，调整到左半区 ──────────────────────────── ↑ ②表空测试，非空； mid=4 ③得到中点，比较测试为b情形 ↑ ↑ high=4 low=5 low=mid+1，调整到右半区 ──────────────────────────── ②表空测试，为空；查找失败，返回查找失败信息为0 ────────────────────────────7/25/202426 【算法9.2】int Binary_Search(S_TBL tbl，KEY kx){ /* 在表tbl中查找关键码为kx的数据元素，若找到返回该元素在表中的位置，否则，返回0 */ int mid，flag=0； low=1；high=length； /* ①设置初始区间 */ while(low<=high) /* ②表空测试 */ { /* 非空，进行比较测试 */ mid=(low+high)/2； /* ③得到中点 */ if (kxtbl.elem[mid].key) low=mid+1； /* 调整到右半区 */ else { flag=mid；break；} /* 查找成功，元素位置设置到flag中 */ } return flag; }7/25/202427 【性能分析】【性能分析】 从折半查找过程看，以表的中点为比较对象，并以中点将表分割为两个子表，对定位到的子表继续这种操作。
所以，对表中每个数据元素的查找过程，可用二叉树来描述，称这个描述查找过程的二叉树为判定树4938291874252312346351421图9.2 例9.１描述折半查找过程的判定树7/25/202428 可以看到，查找表中任一元素的过程，即是判定树中从根到该元素结点路径上各结点关键码的比较次数，也即该元素结点在树中的层次数对于n个结点的判定树，树高为k，则有2k-1-1
7/25/202430 9.3 动态查找表 7/25/202431 一.二叉排序树定义 二叉排序树（Binary Sort Tree）或者是一棵空树；或者是具有下列性质的二叉树： ⑴ 若左子树不空，则左子树上所有结点的值均小于根结点的值；若右子树不空，则 右子树上所有结点的值均大于根结点的值 ⑵ 左右子树也都是二叉排序树 9.3.1 二叉排序树7/25/202432 由图中可以看出，对二叉排序树进行中序遍历，便可得到一个按关键码有序的序列，因此，一个无序序列，可通过构一棵二叉排序树而成为有序序列5842987090634555836710二.二叉排序树查找过程 从其定义可见，二叉排序树的查找过程为： ①若查找树为空，查找失败 ②查找树非空，将给定值kx与查找树的根结点关键码比较 7/25/202433 ③ 若相等，查找成功，结束查找过程，否则， a．当给kx小于根结点关键码，查找将在以左子女为根的子树上继续进行，转① b．当给kx大于根结点关键码，查找将在以右子女为根的子树上继续进行，转① 以二叉链表作为二叉排序树的存储结构，则查找过程算法程序描述如下：typedef struct NODE{ ElemTypeelem; /*数据元素字段*/ struct NODE*lc,*rc;/*左、右指针字段*/ }NodeType; /*二叉树结点类型*/7/25/202434 【算法9.4】Int SearchElem(NodeType *t,NodeType *p,NodeType *q,KeyType kx){ /*在二叉排序树t上查找关键码为kx的元素，若找到，返回1，且q指向该结点，p指向其父结点；否则，返回0，且p指向查找失败的最后一个结点*/ int flag=0; *q=t; while(*q)/*从根结点开始查找*/ if(kx>(*q)->elem.key) /*kx大于当前结点*q的元素关键码*/ { *p=*q;*q=(*q)->rc;}/*将当前结点*q的右子女置为新根*/ else if(kx<(*q)->elem.key) /*kx小于当前结点*q的关键码*/ {*p=*q;*q=(*q)->lc;} /*将当前结点*q的左子女置为新根*/ else {flag=1;break;}/*查找成功，返回*/ return flag; }7/25/202435 三.二叉排序树插入操作和构造一棵二叉排序树 先讨论向二叉排序树中插入一个结点的过程：设待插入结点的关键码为kx，为将其插入，先要在二叉排序树中进行查找，若查找成功，按二叉排序树定义，待插入结点已存在，不用插入；查找不成功时，则插入之。
因此，新插入结点一定是作为叶子结点添加上去的 构造一棵二叉排序树则是逐个插入结点的过程7/25/202436 【算法9.5】int InsertNode (NodeType *t,KeyType kx){ /*在二叉排序树*t上插入关键码为kx的结点*/ NodeType *p=t,*q,*s; int flag=0; if (!SearchElem(t,&p,&q,kx)); /*在*t为根的子树上查找*/ { s=(NodeType *)malloc(sizeof(NodeType)); /*申请结点，并赋值*/ s->elem.key=kx; s->lc=NULL; s->rc=NULL; flag=1;/*设置插入成功标志*/ if (!p) t=s;/*向空树中插入时*/ else if (kx>p->elem.key)p->rc=s; /*插入结点为p的右子女*/ else p->lc=s; /*插入结点为p的左子女*/ } return flag;}7/25/202437 【例9.3】记录的关键码序列为：63，90，70，55，67，42，98，83，10，45，58，则构造一棵二叉排序树的过程如下：φ6370556742988363906390706390557063906755706390426755706390984267557063907/25/202438 839842675570639010455883984267557063901045839842675570639010从空树开始建立二叉排序树的过程7/25/202439 9.4 9.4 哈希表哈希表查找（杂凑法）查找（杂凑法） 9.4.1 哈希表与哈希方法哈希表与哈希方法 以上讨论的查找方法，由于数据元素的存储位置与关键码之间不存在确定的关系，因此，查找时，需要进行一系列对关键码的查找比较，即“查找算法”是建立在比较的基础上的，查找效率由比较一次缩小的查找范围决定。
理想的情况是依据关键码直接得到其对应的数据元素位置，即要求关键码与数据元素间存在一一对应关系，通过这个关系，能很快地由关键码得到对应的数据元素位置 7/25/202440 【【例例9.69.6】】11个元素的关键码分别为 18，27，1，20，22，6，10，13，41，15，25选取关键码与元素位置间的函数为 f(key)=key mod 11 1、 通过这个函数对11个元素建立查找表如下：012345678910221132525276184120102、查找时，对给定值kx依然通过这个函数计算出地址，再将kx与该地址单元中元素的关键码比较，若相等，查找成功 7/25/202441 哈哈希希表表与与哈哈希希方方法法：：选取某个函数，依该函数按关键码计算元素的存储位置，并按此存放；查找时，由同一个函数对给定值kx计算地址，将kx与地址单元中元素关键码进行比，确定查找是否成功，这就是哈希方法(杂凑法)；哈希方法中使用的转换函数称为哈希函数(杂凑函数)；按这个思想构造的表称为哈希表(杂凑表) 对于n个数据元素的集合，总能找到关键码与存放地址一一对应的函数若最大关键为m，可以分配m个数据元素存放单元，选取函数f(key)=key即可，但这样会造成存储空间的很大浪费，甚至不可能分配这么大的存储空间。
通常关键码的集合比哈希地址集合大得多，因而经过哈希函数变换后，可能将不同的关键码映射到同一个哈希地址上，这种现象称为冲突(Collision)，映射到同一哈希地址上的关键码称为同义词可以说，冲突不可能避免，只能尽可能减少所以，哈希方法需要解决以下两个问题：7/25/202442 1. 构造好的哈希函数 （1）所选函数尽可能简单，以便提高转换速度 （2）所选函数对关键码计算出的地址，应在哈希地址集中大致均匀分布，以减少空间 浪费 2. 制定解决冲突的方案9.4.2 常用的哈希函数常用的哈希函数一一. . 直接定址法直接定址法 Hash(key)=a·key+b (a、b为常数)即取关键码的某个线性函数值为哈希地址，这类函数是一一对应函数，不会产生冲突，但要求地址集合与关键码集合大小相同，因此，对于较大的关键码集合不适用 7/25/202443 【【例例9.79.7】】关键码集合为{100，300，500，700，800，900}，选取哈希函数为 Hash(key)=key/100，则存放如下：0123456789100300500700800900二二. . 除留余数法除留余数法 Hash(key)=key mod p (p是一个整数)即取关键码除以p的余数作为哈希地址。
使用除留余数法，选取合适的p很重要，若哈希表表长为m，则要求p≤m，且接近m或等于mp一般选取质数，也可以是不包含小于20质因子的合数7/25/202444 三三. . 乘余取整法乘余取整法（A、B均为常数，且0
若哈希地址是两位，则可取这四位中的任意两位组合成哈希地址，也可以取其中两位与其它两位叠加求和后，取低两位作哈希地址7/25/202447 五、平方取中法五、平方取中法 对关键码平方后，按哈希表大小，取中间的若干位作为哈希地址六、折叠法六、折叠法(Folding)(Folding) 此方法将关键码自左到右分成位数相等的几部分，最后一部分位数可以短些，然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希地址这种方法称为折叠法 有两种叠加方法： 1. 移 位 法 ── 将各部分的最后一位对齐相加 2. 间界叠加法 ── 从一端向另一端沿各部分分界来回折叠后，最后一位对齐相加7/25/202448 【【例例9.119.11】】关键码为 key=05326248725，设哈希表长为三位数，则可对关键码每三位一部分来分割 关键码分割为如下四组： 253 463 587 05用上述方法计算哈希地址253463587＋＋ 051308Hash(key)=308移位法移位法253364587＋＋ 501254Hash(key)=254间界叠加法间界叠加法 对于位数很多的关键码，且每一位上符号分布较均匀时，可采用此方法求得哈希地址 。
7/25/202449 9.4.3 处理冲突的方法处理冲突的方法 一一. 开放定址法开放定址法 所谓开放定址法，即是由关键码得到的哈希地址一旦产生了冲突，也就是说，该地址已经存放了数据元素，就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入 找空哈希地址方法很多，下面介绍三种： 1. 线性探性探测法法 Hi=(Hash(key)+di) mod m ( 1≤i < m ) 其中： Hash(key)为哈希函数 m为哈希表长度 di 为增量序列 1，2，……，m-1，且di=i7/25/202450 【【例例9.129.12】】关键码集为 {47，7，29，11，16，92，22，8，3}，哈希表表长为11， Hash(key)=key mod 11，用线性探测法处理冲突，建表如下： 01234567891011224792163729847、7、11、16、92均是由哈希函数得到的没有冲突的哈希地址而直接存入的； Hash(29)=7，哈希地址上冲突，需寻找下一个空的哈希地址： 由H1=(Hash(29)+1) mod 11=8，哈希地址8为空，将29存入。
另外，22、8同样在哈希地址上有冲突，也是由H1找到空的哈希地址的； 7/25/202451 而Hash(3)=3，哈希地址上冲突，由 H1=(Hash(3)+1) mod 11=4 仍然冲突； H2=(Hash(3)+2) mod 11=5 仍然冲突； H3=(Hash(3)+3) mod 11=6 找到空的哈希地址，存入 线性探测法可能使第i个哈希地址的同义词存入第i+1个哈希地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词，……，因此，可能出现很多元素在相邻的哈希地址上“堆积”起来，大大降低了查找效率为此，可采用二次探测法，或双哈希函数探测法，以改善“堆积”问题7/25/202452 2. 二次二次探探测法法 Hi=(Hash(key)±di) mod m 其中： Hash(key)为哈希函数 m为哈希表长度，m要求是某个4k+3的质数(k是整数) di 为增量序列 12，-12，22，-22，……，q2，-q2且q≤ (1/2)*(m-1)【【例例9.139.13】】关关键键码码集集为为 {47，，7，，29，，11，，16，，92，，22，，8，，3}，，用二次探测法处理冲突，建表如下：用二次探测法处理冲突，建表如下： 0123456789101122347921672987/25/202453 对关键码寻找空的哈希地址只有3这个关键码与上例不同， Hash(3)=3，哈希地址上冲突，由 H1=(Hash(3)+12) mod 11=4 仍然冲突； H2=(Hash(3)-12) mod 11=2 找到空的哈希地址，存入。
3. 双哈希函数探测法双哈希函数探测法 Hi=(Hash(key)+i*ReHash(key)) mod m (i=1，2，……，m-1) 其中： Hash(key)，ReHash(key)是两个哈希函数， m为哈希表长度7/25/202454 双哈希函数探测法，先用第一个函数Hash(key)对关键码计算哈希地址，一旦产生地址冲突，再用第二个函数ReHash(key)确定移动的步长因子，最后，通过步长因子序列由探测函数寻找空的哈希地址 比如，Hash(key)=a时产生地址冲突，就计算ReHash(key)=b，则探测的地址序列为 H1=(a+b) mod m，H2=(a+2b) mod m，……，Hm-1=(a+(m-1)b) mod m 二二. 拉链法拉链法 设哈希函数得到的哈希地址域在区间[0，m-1]上，以每个哈希地址作为一个指针，指向一个链，即分配指针数组 ElemType *eptr[m]；建立m个空链表，由哈希函数对关键码转换后，映射到同一哈希地址i的同义词均加入到*eptr[i]指向的链表中。
7/25/202455 【例【例9.l4】】关键码序列为关键码序列为47,7,29,11,16,92,22,8,3,50,37,89,47,7,29,11,16,92,22,8,3,50,37,89,94,2194,21，哈希函数为，哈希函数为 Hash(key)=key mod 11 Hash(key)=key mod 11，建表如下图，建表如下图 012^3456789^102289^33716^94298^21^11^47^92^50^7^拉拉链链法法处处理理冲冲突突时时的的哈哈希希表表（（向向链链表表中中插插入入元元素素均均在在表表头头进进行行））7/25/202456 【算法【算法9.109.10】】#define m 11#define m 11int CreateHashTbl(NodeType **l_tbl,ElemType *eptr)int CreateHashTbl(NodeType **l_tbl,ElemType *eptr){ { /* /* 建建立立哈哈希希表表，，l_tbl l_tbl 为为指指向向m m个个哈哈希希地地址址对对应应的的链链表表指指针针数数组组基基址址，，eptreptr为为待待放放入入哈哈希希表表的的元元素素基基址址，， 建建表表成成功功返返回回 1 1，否则，，否则， 返回返回0 */0 */intintfinished;finished;InitLinkTbl(l_tbl);InitLinkTbl(l_tbl); /* /* 初初始始化化指指向向链链表表的的指指针针数数组组 */ */for(;eptr->key!=0;eptr++)for(;eptr->key!=0;eptr++){ { /* /* 待待放放入入哈哈希希表表的的元元素素表表，， 关关键键码码0 0表表示示结结束束位位置置 */*/finished=MovElemToHashTbl(eptr,linktbl,Hash(eptr-finished=MovElemToHashTbl(eptr,linktbl,Hash(eptr->key)); >key)); if(!finished)if(!finished)break;break;} }return finished;return finished;} }7/25/202457 InitLinkTbl(NodeType **l_tbl)InitLinkTbl(NodeType **l_tbl){int i;{int i;for(i=0;ielem=*e_addr;q->elem=*e_addr;q-q->nptr=*(l_tbl+h_addr);>nptr=*(l_tbl+h_addr);*(l_tbl+h_addr)=q;*(l_tbl+h_addr)=q;status=1;status=1;} }return status;return status;} }7/25/202458 三三三三. . . . 建立一个公共溢出区建立一个公共溢出区建立一个公共溢出区建立一个公共溢出区 设设哈哈希希函函数数产产生生的的哈哈希希地地址址集集为为[0[0，，m-1]m-1]，，则则分分配两个表：配两个表： 一一个个基基本本表表 ElemType ElemType base_tbl[m]base_tbl[m]；；每每个个单单元元只只能存放一个元素；能存放一个元素； 一一个个溢溢出出表表 ElemType ElemType over_tbl[k]over_tbl[k]；；只只要要关关键键码码对对应应的的哈哈希希地地址址在在基基本本表表上上产产生生冲冲突突，，则则所所有有这这样样的的元元素素一一律律存存入入该该表表中中。
查查找找时时，，对对给给定定值值kxkx通通过过哈哈希希函函数数计计算算出出哈哈希希地地址址i i，，先先与与基基本本表表的的base_tbl[i]base_tbl[i]单单元元比比较较，，若若相相等等，，查查找找成成功功；；否否则则，，再再到到溢溢出出表表中中进进行查找7/25/202459 9.4.4 哈希表的查找分析哈希表的查找分析 哈哈希希表表的的查查找找过过程程基基本本上上和和造造表表过过程程相相同同一一些些关关键键码码可可通通过过哈哈希希函函数数转转换换的的地地址址直直接接找找到到，，另另一一些些关关键键码码在在哈哈希希函函数数得得到到的的地地址址上上产产生生了了冲冲突突，，需需要要按按处处理理冲冲突突的的方方法法进进行行查查找找在在介介绍绍的的三三种种处处理理冲冲突突的的方方法法中中，，产产生生冲冲突突后后的的查查找找仍仍然然是是给给定定值值与与关关键键码码进进行行比比较较的的过过程程所所以以，，对对哈哈希希表表查查找找效效率率的量度，依然用平均查找长度来衡量的量度，依然用平均查找长度来衡量 查查找找过过程程中中，，关关键键码码的的比比较较次次数数，，取取决决于于产产生生冲冲突突的的多多少少，，产产生生的的冲冲突突少少，，查查找找效效率率就就高高，，产产生生的的冲冲突突多多，，查查找找效效率率就就低低。
因因此此，，影影响响产产生生冲冲突突多多少少的的因因素素，，也也就就是是影影响响查查找找效效率率的的因因素素影影响响产产生生冲突多少有以下三个因素：冲突多少有以下三个因素： 1. 1. 哈希函数是否均匀；哈希函数是否均匀； 2. 2. 处理冲突的方法；处理冲突的方法； 3. 3. 哈希表的装填因子哈希表的装填因子7/25/202460 分析这三个因素，尽管哈希函数的分析这三个因素，尽管哈希函数的“好坏好坏”直直接影响冲突产生的频度，但一般情况下，我们总认接影响冲突产生的频度，但一般情况下，我们总认为所选的哈希函数是为所选的哈希函数是“均匀的均匀的”，因此，可不考虑，因此，可不考虑哈希函数对平均查找长度的影响就线性探测法和哈希函数对平均查找长度的影响就线性探测法和二次探测法处理冲突的例子看，如【例二次探测法处理冲突的例子看，如【例9.129.12】和【】和【例例9.139.13】相同的关键码集合、同样的哈希函数，但】相同的关键码集合、同样的哈希函数，但在数据元素查找等概率情况下，它们的平均查找长在数据元素查找等概率情况下，它们的平均查找长度却不同：度却不同：线性探测法的平均查找长度线性探测法的平均查找长度ASL=(5ASL=(5×1+31+3×2+12+1×4)/9=5/34)/9=5/3二次探测法的平均查找长度二次探测法的平均查找长度 ASL=(5ASL=(5×1+31+3×2+12+1×2)/9=13/92)/9=13/9哈希表的装填因子定义为：哈希表的装填因子定义为：αα =填入表中的元素个数填入表中的元素个数哈希表的长度哈希表的长度7/25/202461 α是哈希表装满程度的标志因子。
由于表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大；α越小，填入表中的元素较少，产生冲突的可能性就越小实际上，哈希表的平均查找长度是装填因子α的函数，只是不同处理冲突的方法有不同的函数以下给出几种不同处理冲突方法的平均查找长度：7/25/202462 处理冲突的方法平均查找长度查找成功时查找不成功时线性探测法二次探测法与双哈希法拉链法 哈希方法存取速度快，也较节省空间，静态查找、动态查找均适用，但由于存取是随机的，因此，不便于顺序查找7/25/202463 。