网志栈编辑推荐
数据结构毫无疑问是计算机科学既经典又核心的课程之一，不管是从事计算机软件还是硬件的开发工作，如果没有系统地学习数据结构或者是没有专心自学过，很容易被人打上“非专业”的标签。对于任何在信息技术行业工作的专业人员或者想进入此行业的人来说，什么时候开始学数据结构都不会晚，更不会过时。
从“数据结构”的名字看，它不仅仅只是讲授数据的结构以及在计算机内如何存储和组织数据的方式，这些只是它的表面现象。数据结构背后真正蕴含的是与之息息相关的算法，精心选择的数据结构配合恰如其分的算法就意味着数据或者信息在计算机内被高效率地存储和高效率地处理。算法其实就是数据结构的灵魂，它既神秘又神奇“好玩”，当然对初学者也比较难，算法可以说是“聪明人在计算机上的游戏”。
本书是一本综合而且全面讲述数据结构及其算法分析的教科书，为了便于高校的教学或者读者自学，作者在描述数据结构原理和算法时文字清晰并且严谨，为每个算法及其数据结构提供了演算的详细图解。另外，为了适合在教学中让学生上机实践或者自学者上机“操练”，本书为每个经典的算法都提供了C语言编写的完整范例程序的源代码，每个范例程序都不需要经过修改，直接通过编译就可以运行，目的就是让本书的学习者以这些范例程序作为参照迅速掌握数据结构和算法的要点。
全书的所有范例程序都可以在标准的C语言编程环境中编译通过并且成功运行，我们在改编本书的过程中选用了免费的Dev C 5.11集成开发环境，对原书的所有范例程序进行编译、修改、调试和测试，并确保它们都可以准确无误地运行。附录A包含了“C/C 编译程序的介绍与安装”，其中重点就介绍了Dev C 。附录B则包含了“C语言快速入门”。
；
内容简介
本书用最轻松的图解方式来讲解数据结构，全书采用丰富的图例阐述数据结构的基本概念及应用，并将重要理论、演算方法做最详细的诠释与举例，是一本兼具内容及专业的数据结构的教学用书。 由于作者长期从事信息教育及写作，在文字的表达上简洁明了、逻辑清晰，并安排了大量的习题，供读者检验学习成果。
作者简介
胡昭民现任荣钦科技股份有限公司董事长，美国Rochester Institute of Technology计算机科学研究所毕业，长期从事信息教育及计算机图书写作的工作，并监制过多套游戏及教学软件的研发。
目录
目 ；录
第1章 ；数据结构导论 1
1-1 ； 数据结构简介 2
1-1-1 ； 数据与信息 2
1-1-2 ； 算法 3
1-1-3 ； 算法的条件 3
1-1-4 ； 数据结构的应用 6
1-2 ； 数据抽象化 7
1-2-1 ； 基本数据类型 7
1-2-2 ； 抽象数据类型 7
1-3 ； 算法与程序设计 8
1-3-1 ； 认识程序设计 8
1-3-2 ； 程序开发流程 9
1-3-3 ； 程序设计的风格 9
1-4 ； 面向对象程序设计 11
1-4-1 ； 封装（Encapsulation） 12
1-4-2 ； 继承（Inheritance） 13
1-4-3 ； 多态（Polymorphism） 13
1-5 ； 模块化设计与C语言 13
1-5-1 ； 函数的基本概念 13
1-5-2 ； 参数类型的介绍 14
1-5-3 ； 参数的传递方式 15
1-6 ； 递归算法 15
1-6-1 ； 递归的定义 15
1-6-2 ； 斐波拉契数列 17
1-6-3 ； 汉诺塔问题 18
1-7 ； 程序效率的分析 23
1-7-1 ； Big-oh 25
1-7-2 ； Ω(omega)26
1-7-3 ； θ(theta)27
本章习题 27
第2章 ； 线性表 32
2-1 ； 线性表的定义 33
2-1-1 ； 线性表的用途 33
2-2 ； 数组 34
2-2-1 ； 一维数组 34
2-2-2 ； 二维数组 36
2-2-3 ； 多维数组 40
2-2-4 ； 结构数组 44
2-2-5 ； 字符数组 46
2-2-6 ； 字符串数组 48
2-2-7 ； 指针数组 49
2-3 ； 矩阵 50
2-3-1 ； 矩阵的运算 51
2-3-2 ； 稀疏矩阵 53
2-3-3 ； 上三角形矩阵 55
2-3-4 ； 下三角形矩阵 59
2-3-5 ； 带状矩阵 64
本章习题 65
第3章 ； 链表 69
3-1 ； 动态分配内存 70
3-1-1 ； C的动态分配变量70
3-1-2 ； C 的动态分配变量72
3-2 ； 单向链表 73
3-2-1 ； 建立单向链表 74
3-2-2 ； 遍历单向链表 75
3-2-3 ； 释放单向链表节点的空间 76
3-2-4 ； 单向链表插入新节点77
3-2-5 ； 单向链表删除节点79
3-2-6 ； 单向链表的反转 81
3-3 ； 环形链表 83
3-3-1 ； 环形链表的建立与遍历83
3-3-2 ； 环形链表中插入新节点85
3-3-3 ； 环形链表节点的删除86
3-3-4 ； 环形链表的连接功能88
3-4 ； 双向链表 89
3-4-1 ； 双向链表的建立与遍历90
3-4-2 ； 双向链表中加入新节点92
3-4-3 ； 双向链表节点的删除94
3-5 ； 链表相关应用简介 96
3-5-1 ； 多项式表式法 96
3-5-2 ； 稀疏矩阵表示法100
本章习题 102
第4章 ； 堆栈与队列 109
4-1 ； 堆栈简介 110
4-1-1 ； 堆栈的基本操作111
4-1-2 ； 用数组实现堆栈111
4-1-3 ； 用链表实现堆栈112
4-1-4 ； 堆栈类样板的实现114
4-1-5 ； 老鼠走迷宫 116
4-1-6 ； 八皇后问题 119
4-2 ； 算术表达式的表示法120
4-2-1 ； 中序转为前序与后序121
4-2-2 ； 前序与后序转为中序126
4-2-3 ； 中序表示法求值129
4-2-4 ； 前序法的求值运算130
4-2-5 ； 后序法的求值运算131
4-3 ； 队列 132
4-3-1 ； 队列的基本操作133
4-3-2 ； 用数组实现队列133
4-3-3 ； 环形队列 135
4-3-4 ； 双向队列 139
4-3-5 ； 双向队列 141
4-3-6 ； 优先队列 143
本章习题 144
第5章 ； 树状结构 156
5-1 ； 树的基本概念 157
5-1-1 ； 专有名词介绍 158
5-2 ； 二叉树 159
5-2-1 ； 二叉树的特性 159
5-2-2 ； 特殊二叉树简介160
5-3 ； 二叉树的存储方式 161
5-3-1 ； 一维数组表示法161
5-3-2 链表表示法 164
5-4 二叉树的遍历 166
5-4-1 中序遍历 166
5-4-2 后序遍历 167
5-4-3 前序遍历 167
5-4-4 二叉树节点的插入与删除 170
5-4-5 二叉运算树 174
5-5 线索二叉树 176
5-5-1 二叉树转为线索二叉树176
5-6 树的二叉树表示法 180
5-6-1 树转化为二叉树180
5-6-2 二叉树转换成树182
5-6-3 森林化为二叉树183
5-6-4 二叉树转换成森林184
5-6-5 树与森林的遍历185
5-6-6 确定唯一二叉树189
5-7 优化二叉查找树 191
5-7-1 扩充二叉树 191
5-7-2 霍夫曼树 192
5-8 平衡树 194
5-8-1 平衡树的定义 194
5-9 高级树状结构的研究196
5-9-1 决策树 196
5-9-2 B树 198
5-9-3 二叉空间分割树198
5-9-4 四叉树与八叉树199
本章习题 200
第6章 图形结构 210
6-1 图形简介 211
6-1-1 图的定义 212
6-1-2 无向图 212
6-1-3 有向图 214
6-2 图的数据表示法 215
6-2-1 邻接矩阵法 215
6-2-2 邻接表法 218
6-2-3 邻接复合链表法220
6-2-4 索引表格法 222
6-3 图的遍历 225
6-3-1 深度优先遍历法225
6-3-2 广度优先遍历法227
6-4 生成树 229
6-4-1 DFS生成树和BFS生成树 229
6-4-2 最小生成树 231
6-4-3 Kruskal算法231
6-4-4 Prim算法 235
6-5 图的最短路径 236
6-5-1 单点对全部顶点237
6-5-2 两两顶点间的最短路径240
6-6 AOV网络与拓扑排序244
6-6-1 拓扑排列简介 244
6-7 AOE网络 246
6-7-1 关键路径 246
本章习题 248
第7章 排序 257
7-1 排序简介 258
7-1-1 排序的分类 259
7-2 内部排序法 260
7-2-1 冒泡排序法 260
7-2-2 选择排序法 262
7-2-3 插入排序法 264
7-2-4 希尔排序法 266
7-2-5 合并排序法 268
7-2-6 快速排序法 269
7-2-7 堆积排序法 271
7-2-8 基数排序法 278
7-3 外部排序法 280
7-3-1 直接合并排序法280
7-3-2 k路合并法 284
7-3-3 多相合并法 284
本章习题 285
第8章 查找 295
8-1 常见的查找方法 296
8-1-1 顺序查找法 296
8-1-2 二分查找法 297
8-1-3 插值查找法 299
8-1-4 斐波那契查找法301
8-2 哈希查找法 305
8-2-1 哈希法简介 305
8-3 常见的哈希函数 306
8-3-1 除留余数法 306
8-3-2 平方取中法 307
8-3-3 折叠法 308
8-3-4 数字分析法 308
8-4 碰撞与溢出问题的处理309
8-4-1 线性探测法 309
8-4-2 平方探测 310
8-4-3 再哈希 310
8-4-4 链表 311
本章习题 312
附录A C/C 编译程序的介绍与安装 318
A-1 C/C 编译程序简介319
A-1-1 Visual C 2010 Express 319
A-1-2 C Builder 320
A-1-3 Visual C 320
A-1-4 Dev C 321
A-1-5 GCC 322
A-2 Dev C 的安装与介绍 322
A-2-1 下载Dev-C 323
A-2-2 安装Dev C 323
附录B C语言快速入门介绍与安装 329
B-1 轻松学C程序 330
B-1-1 编译与执行 331
B-1-2 编译程序 332
B-1-3 开始执行程序 333
B-2 C的基本数据处理 333
B-2-1 变量 333
B-2-2 常数 334
B-2-3 数据类型简介 334
B-3 C语言的输出与输入 335
B-3-1 printf()函数336
B-3-2 scanf()函数337
B-4 流程控制 338
B-4-1 顺序结构 338
B-4-2 选择结构 339
B-4-3 重复结构 343
B-5 数组简介 346
B-5-1 字符串简介 347
B-5-2 字符串数组 347
B-6 函数介绍 349
B-6-1 传递参数的方式350
B-6-2 标准函数库 352
前沿
序
数据结构一直是计算机信息相关学科的必修科目，对于第一次接触数据结构课程的学生来说，内容过多及表达不清楚常常是造成学习障碍最主要的因素，为了让读者能用最轻松的方式快速理解数据结构，本书特别征询多位教师意见，采用丰富的图例来阐述基本概念及应用，并且将重要理论和演算方法做了非常详实的诠释，是一本兼具内容及专业的数据结构教学用书。
由于笔者长期从事咨询教育及写作工作，在文句的表达上尽量以简洁有力、逻辑清楚阐述为主。为了验收各章的学习成果，特别搜集了大量的习题，并参阅重要考试，提供给读者更多的实战演练经验。
另外，为了减轻读者的学习压力及经济负担，在整本书所涉及的主题分量不减的情况下，书中仅收录精华的演算方法及程式范例的执行画面，本书所有的程序代码在提供的下载地址中可以下载，读者可直接下载并运行验证。最后希望本书能带给各位对数据结构更完整的认识。
胡昭民 敬笔
免费在线读
第8章 查找
在数据处理过程中，是否能在最短时间内查找到所需要的数据，是一个相当值得信息从业人员关心的问题。所谓查找（search，或搜索）指的是从数据文件中找出满足某些条件的记录。用以查找的条件称为“键值”（key），就如同排序所用的键值一样。
例如联系人中找某人的电话号码，那么这个人的姓名就成为在联系人中查找电话号码的键值。通常影响查找时间长短的主要因素包括算法的选择、数据存储的方式和结构。
8-1 常见的查找方法
如果根据数据量的大小，可将查找分为：
1. 内部查找：数据量较小的文件，可以一次性全部加载到内存中进行查找。
2. 外部查找：数据量大的文件，无法一次加载到内存中处理，而需使用辅助存储器来分次处理。
如果从另一个角度来看，查找的技巧又可分为“静态查找”和“动态查找”两种。定义如下所示。
1. 静态查找：指的是在查找过程中，查找的表格或文件的内容不会被改动。例如符号表的查找就是一种静态查找。
2. 动态查找：指的是在查找过程中，查找的表格或文件的内容可能会被改动，例如在树状结构中所谈的B-tree查找就属于一种动态查找。
至于查找技巧中比较常见的方法有顺序法、二分查找法、斐波那契法、插值法、哈希法、m路查找树、B-tree等。为了让大家能确实掌握各种查找的技巧和基本原理，以便应用于日后的各种领域，现将几个主要的查找方法分述于后。
8-1-1 顺序查找法
顺序查找通常用于未经组织化的文件，又称为线性查找。查找的过程从文件第一项数据开始，按序比较每个键值。由于顺序查找法是逐项对比，因此只要一找到数据就可以结束数据的查找。以n项数据为例，使用顺序查找法来查找数据时，有可能在第1项就找到了，在这种情形下仅需执行一次比较操作。如果数据在第2项、第3项…第n项，则其需要的比较次数分别为2、3、4、…、n次。因此，在平均情况下，顺序查找法，查找一项数据需要的平均比较次数为 (n 1)/2。
现在以一个例子来说明，假设已有数列74、53、61、28、99、46、88，若要查找28，则需要比较4次；要查找74仅需比较1次；要查找88则需查找7次，这表示当查找的数列长度n很大时，利用顺序查找是不太适合的，它是一种适用于小数据文件的查找方法。
另外，在最差的情况下，逐一对比后没有找到数据，则必须花费n次，其最坏情况下（Worst Case）的时间复杂度为O(n)。也就是说，除非可以预知要查找的数据大概位于文件的前端，否则当文件的数据项数过大时，顺序查找法在查找的效率上显然不如其他的查找法。
线性查找法的优点是文件或数据事前不需要经过任何的处理与排序，也由于它未考虑到数据的特征对于查找的影响，所以在应用上适合于各种情况，其缺点则是查找的速度较慢。
顺序查找法的C语言算法如下所示。
while (val!=-1)
{
find=0;
printf("请输入查找键值(1-150)，输入-1离开：");
scanf("%d",&val);
for (i=0;i<80;i )
{
if(data[i]==val)
{
printf("在第 %3d个位置找到键值 [%3d]
",i 1,data[i]);
find ;
}
}
if(find==0 && val !=-1)
printf("######没有找到 [%3d]######
",val);
}
8.1.1
请设计一个C程序，以随机数生成1~150之间的80个整数，然后实现顺序查找法的过程。
请参考程序CH08_01.c，本范例程序的运行结果如图8-1所示。
图8-1 实现顺序查找法的范例程序的运行结果
8-1-2 二分查找法
如果要查找的数据已经事先排好序了，则可使用二分查找法来进行查找。二分查找法是将数据平均分割成两份，再比较键值与中间值的大小，如果键值小于中间值，可确定要查找的数据在前半段，否则在后半部。如此分割数次直到找到或确定不存在为止。例如，以下已排序的数列 2、3、5、8、9、11、12、16、18 ，而所要查找值为11时：
首先跟第5个数值 9 比较，如图8-2所示。
图8-2 先和中值比较
因为11＞9，所以和后半部的中间值 12 比较，如图8-3所示：
图8-3 再和后半部的中值比较
因为 11＜12，所以和前半部的中间值 11比较，如图8-4所示：
图8-4 再和后半部的前半部中值比较
因为 11=11，表示查找到了即查找完成，如果不相等则表示没有找到。
二分查找法的C语言算法如下所示。
int bin_search(int data[50],int val)
{
int low,mid,high;
low=0;
high=49;
printf("查找过程中......
");
while(low <= high && val!=-1)
{
mid=(low high)/2;
if(val
{
printf("%d 介于位置 %d[%3d]和中间值 %d[%3d]，找左半边
",val,low 1, data[low],mid 1,data[mid]);
high=mid-1;
}
else if(val>data[mid])
{
printf("%d 介于中间值位置 %d[%3d] 和 %d[%3d]，找右半边
",val,mid 1, data[mid],high 1,data[high]);
low=mid 1;
}
else
return mid;
}
return -1;
}
使用二分法查找要求被查找的数列事先已排好序，而且数据量不能太大，必须要能直接在内存中执行。此法适合用于不需增删的静态数据，因为每次的查找都会比上一次少一半的范围，所以最多只需要比较log2n 1或log2(n 1) 次，时间复杂度为O(log n)。
8.1.2
请设计一个C程序，以随机数生成1~150之间的80个整数，然后实现二分查找法的过程与步骤。
请参考程序CH08_02.c，本范例程序的运行结果如图8-5所示。
图8-5 实现二分查找法的范例程序的运行结果
8-1-3 插值查找法
插值查找法（interpolation search）又叫作插补查找法，是二分查找法的改进版。它是按照数据位置的分布，利用公式预测数据所在的位置，再以二分法的方式渐渐逼近。使用插值法是假设数据平均分布在数组中，而每一项数据的差距相当接近或有一定的距离比例。插值法的公式为：
Mid = low (( key - data[low] ) / ( data[high] - data[low] )) * ( high - low )
其中key是要查找的键，data[high]、data[low]是剩余待查找记录中的最大值和最小值，假设数据项数为n，其插值查找法的步骤如下所示。
? 将记录从小到大的顺序给予1、2、3、…、n的编号。
? 令low=1，high=n
? 当low
? 令Mid = low (( key - data[low] ) / ( data[high] - data[low] )) * (high - low )
? 若key
? 若key＝keyMid表示成功查找到键值的位置
? 若key>keyMid且low≠Mid 1，则令low=Mid 1
二分查找法的C语言算法如下所示。
int bin_search(int data[50],int val)
{
int low,mid,high;
low=0;
high=49;
printf("查找过程中......
");
while(low<= high && val !=-1)
{
mid=low ((val-data[low])*(high-low)/(data[high]-data[low]));
/*内插法公式*/
if (val==data[mid])
return mid;
else if (val < data[mid])
{
printf("%d 介于位置 %d[%3d]和中间值 %d[%3d]，找左半边
",val,low 1,data[low],mid 1,data[mid]);
high=mid-1;
}
else if(val > data[mid])
{
printf("%d 介于中间值位置 %d[%3d] 和 %d[%3d]，找右半边
",val,mid 1,data[mid],high 1,data[high]);
low=mid 1;
}
}
return -1;
}
一般而言，使用插值查找法要求数据需先经过排序，这样查找速度才能优于顺序查找法，而如果数据的分布越平均，则查找速度越快，甚至可能第一次就找到数据。此法的时间复杂度取决于数据分布的情况，平均而言优于O(log n)。
8.1.3
请设计一个C程序，以随机数生成1~150之间的50个整数，然后实现插值查找法的过程与步骤。
请参考程序CH08_03.c，本范例程序的运行结果如图8-6所示。
图8-6 实现插值查找法的范例程序的运行结果
8-1-4 斐波那契查找法
斐波那契查找法（fibonacci search）又称为Fibonacci查找法，此法和二分法一样都是以分割范围来进行查找，不同的是斐波那契查找法不以对半分割而是以斐波那契级数的方式来分割。
斐波那契级数F(n)的定义如下所示。
斐波那契级数：0、1、1、2、3、5、8、13、21、34、55、89、……。也就是除了第0个和第1个元素外，级数中的每个值都是前两个值的和。
斐波那契查找法的好处是只用到加减运算而不需用到乘除运算，这从计算机运算的过程来看效率会高于前两种查找法。在尚未介绍斐波那契查找法之前，我们先来认识斐波那契查找树。所谓斐波那契查找树是以斐波那契级数的特性来建立的二叉树，其建立的原则如下所示。
（1）斐波那契树的左右子树均为斐波那契树。
（2）当数据个数n确定，若想确定斐波那契树的层数k值是多少，必须找到一个最小的k值，使得斐波那契层数的Fib(k 1)≥n 1。
（3）斐波那契树的树根一定是一个斐波那契数，且子节点与父节点差值的绝对值为斐波那契数。
（4）当k≥2时，斐波那契树的树根为Fib(k)，左子树为 (k-1) 层斐波那契树（其树根为Fib(k-1)），右子树为 (k-2) 层斐波那契树（其树根为Fib(k) Fib(k-2)）。
（5）若n 1值不为斐波那契数的值，则可以找出存在一个m使用Fib(k 1)-m=n 1，m=Fib(k 1)-(n 1)，再按斐波那契树的建立原则完成斐波那契树的建立，最后斐波那契树的各节点再减去差值m即可，并把小于1的节点去掉。
斐波那契树建立过程的示意图如图8-7所示。
图8-7 斐波那契树建立过程的示意图
也就是说当数据个数为n，且找到一个最小的斐波那契数Fib(k 1)使得Fib(k 1)>n 1，则Fib(k) 就是这棵斐波那契树的树根，而Fib(k-2) 则是与左右子树开始的差值，左子树用减的；右子树用加的。例如实际求取n=33的斐波那契树。
由于n=33，且n 1=34为一个斐波那契树，并知道斐波那契数列的3项特性。
Fib(0) = 0
Fib(1) = 1
Fib(k) = Fib(k-1) Fib(k-2)
得知 Fib(0) = 0、Fib(1) = 1、Fib(2) = 1、Fib(3) = 2、Fib(4) = 3、Fib(5) = 5、Fib(6) = 8、Fib(7) = 13、Fib(8) = 21、Fib(9) = 34
从上式可得知Fib(k 1) = 34 à k = 8，建立二叉树的树根为Fib(8) = 21
左子树的树根为Fib(8-1) = Fib(7) = 13
右子树的树根为Fib(8) Fib(8-2) = 21 8 = 29
按此原则可以建立如图8-8所示的斐波那契树。
图8-8 斐波那契树
斐波那契查找法是以斐波那契树来查找数据，如果数据的个数为n，而且n比某一个斐波那契数小，且满足如下表达式。
Fib(k 1)≥n 1
此时Fib(k) 就是这棵斐波那契树的树根，而Fib(k-2)则是与左右子树开始的差值，若要查找的键值为key，首先比较数组下标Fib(k) 和键值key，此时可以有下列3种比较情况。
? 当key值比较小，表示所查找的键值key落在1到Fib(k)-1之间，故继续查找1到Fib(k)-1之间的数据。
? 如果键值与数组下标Fib(k) 的值相等，表示成功查找到所要的数据。
? 当key值比较大，表示所找的键值key落在Fib(k) 1到Fib(k 1)-1之间，故继续查找Fib(k) 1到Fib(k 1)-1之间的数据。
斐波那契查找法的C语言算法如下所示。
#define MAX 20
int fib(int n)
{
if(n==1 || n==0)
return n;
else
return fib(n-1) fib(n-2);
}
int fib_search(int data[MAX],int SearchKey)
{
int index=2;
/*斐波拉契数列的查找*/
while(fib(index)<=MAX)
index ;
index--;
/* index >=2 */
/*起始的斐波拉契数*/
int RootNode=fib(index);
/*上一个斐波拉契数*/
int diff1=fib(index-1);
/*上两个斐波拉契数即diff2=fib(index-2)*/
int diff2=RootNode-diff1;
RootNode--;/*这个表达式是配合数组的下标是从0开始存储数据*/
while(1)
{
if(SearchKey==data[RootNode])
{
return RootNode;
}
else
{
if(index==2) return MAX; /*没有找到*/
if(SearchKey
{
RootNode=RootNode-diff2;/*左子树的新斐波拉契数 */
int temp=diff1;
diff1=diff2;/*上一个斐波拉契数*/
diff2=temp-diff2;/*上两个斐波拉契数*/
index=index-1;
}
else
{
if(index==3) return MAX;
RootNode=RootNode diff2;/*右子树的新斐波拉契数 */
diff1=diff1-diff2;/*上一个斐波拉契数*/
diff2=diff2-diff1;/*上两个斐波拉契数*/
index=index-2;
}
}
}
}
平均而言，斐波那契查找法的比较次数会少于二分查找法，但在最坏的情况下二分查找法较快，其平均时间复杂度为O(log2N)。另外，斐波那契查找算法较为复杂，需额外产生斐波那契树。
8.1.4
请设计一个斐波那契查找法的C程序，实现斐波那契查找法的过程与步骤。
请参考程序CH08_04.c，本范例程序的运行结果如图8-9所示。
图8-9 实现斐波那契查找法的范例程序的运行结果
8-2 哈希查找法
哈希法（或称散列法）这个主题通常和查找法一起讨论，主要原因是哈希法不仅被用于数据的查找，在数据结构的领域中，还能将它应用在数据的建立、插入、删除与更新。
例如符号表在计算机上的应用领域很广泛，包含汇编程序、编译程序、数据库使用的数据字典等，都是利用提供的名称来找到对应的属性。符号表按其特性可分为两类：静态表（static table）和动态表（dynamic table）。而“哈希表”（hash table）则是属于静态表中的一种，将相关的数据和键值存储在一个固定大小的表格中。
8-2-1 哈希法简介
基本上，所谓哈希法（hashing）就是将本身的键值，通过特定的数学函数运算或使用其他的方法，转换成相对应的数据存储地址。哈希法所使用的数学函数就称为“哈希函数”（hashing function）。现在先来介绍有关哈希函数的相关名词。
bucket（桶）：哈希表中存储数据的位置，每一个位置对应到唯一的一个地址（bucket address）。桶就好比一个记录。
slot（槽）：每一个记录中可能包含好几个字段，而slot指的就是“桶”中的字段。
collision（碰撞）：若两项不同的数据，经过哈希函数运算后，对应到相同的地址时，就称为碰撞。
溢出：如果数据经过哈希函数运算后，所对应到的bucket已满，则会使bucket发生溢出。
哈希表：存储记录的连续内存。哈希表是一种类似数据表的索引表格，其中可分为n个bucket，每个bucket又可分为m个slot，如下表所示：
索引 姓名 电话
bucket→ 0001 Allen 07-772-1234
0002 Jacky 07-772-5525
0003 May 07-772-6604
↑slot ↑slot
同义词（Synonym）：当两个标识符I1和I2，经哈希函数运算后所得的数值相同，即f(I1) = f(I2)，则称I1与I2对于f这个哈希函数是同义词。
加载密度（loadingfactor）：所谓加载密度是指标识符的使用数目除以哈希表内槽的总数：
a(加载密度) = n (标识符的使用数目) / s (每一个桶内的槽数)b(桶的数目)
如果a值越大，则表示哈希空间的使用率越高，碰撞或溢出的概率也会越高。
完美哈希（perfecthashing）：指没有碰撞也没有溢出的哈希函数。
在此建议大家，通常在设计哈希函数应该遵循以下几个原则：
（1）降低碰撞和溢出的产生。
（2）哈希函数不宜过于复杂，越容易计算越佳。
（3）尽量把文字的键值转换成数字的键值，以利于哈希函数的运算。
（4）所设计的哈希函数计算得到的值，尽量能均匀地分布在每一桶中，不要太过于集中在某些桶内，这样就可以降低碰撞，并减少溢出的处理。
8-3 常见的哈希函数
常见的哈希法有除留余数法、平方取中法、折叠法和数字分析法。下面分别介绍如下。
8-3-1 除留余数法
最简单的哈希函数是将数据除以某一个常数后，取余数来当索引。例如在一个有13个位置的数组中，只使用到7个地址，值分别是12、65、70、99、33、67、48。可以把数组内的值除以13，并以其余数来当数组的下标（即作为索引），可以用以下这个式子来表示：
h(key) = key mod B
在这个例子中，所使用的B=13。一般而言，建议大家在选择B时，B最好是质数。而上例所建立出来的哈希表为：
下标 下标 数据
0 0 65
1 1
2 2 67
3 3
4 4
5 5 70
6 6
7 7 33
8 8 99
9 9 48
10 10
11 11
12 12 12
以下将用除留余数法作为哈希函数，将下列数字存储在11个空间：323,458, 25, 340, 28, 969, 77，请问其哈希表外观如何？
令哈希函数为h(key) = key mod B，其中B=11为一个质数，这个函数的计算结果介于0~10之间（包括0和10两个数），则h(323)=4、h(458)=7、h(25)=3、h(340)=10、h(28)=6、h(969)=1、h(77)=0。所建立的哈希表如下所示。
下标 下标 数据
0 0 77
1 1 969
2 2
3 3 25
4 4 323
5 5
6 6 28
7 7 458
8 8
9 9
10 10 340
8-3-2 平方取中法
平方取中法和除留余数法相当类似，就是先计算数据的平方，之后再取中间的某段数字作为索引。在下例中，用平方取中法，并将数据存放在100个地址空间中，其操作步骤如下：
将12、65、70、99、33、67、51平方后如下所示。
144、4225、4900、9801、1089、4489、2601
再取百位数和十位数作为键值，分别如下所示。
14、22、90、80、08、48、60
上述这7个数字的数列就对应于原先的7个数12、65、70、99、33、67、517存放在100个地址空间的索引键值，即
f(14) = 12
f(22) = 65
f(90) = 70
f(80) = 99
f(8) =33
f(48) = 67
f(60) = 51
若实际空间介于0~9（即10个空间），但取百位数和十位数的值介于0～99（共有100个空间），所以我们必须将平方取中法第一次所求得的键值，再压缩1/10才可以将100个可能产生的值对应到10个空间，即将每一个键值除以10取整数（下例以DIV运算符作为取整数的除法），可以得到下列的对应关系：
f(14 DIV 10)=12 f(1)=12
f(22 DIV 10)=65 f(2)=65
f(90 DIV 10)=70 f(9)=70
f(80 DIV 10)=99 à f(8)=99
f(8 DIV 10) =33 f(0)=33
f(48 DIV 10)=67 f(4)=67
f(60 DIV 10)=51 f(6)=51
8-3-3 折叠法
折叠法是将数据转换成一串数字后，先将这串数字拆成几个部分，最后再把它们加起来，就可以计算出这个键值的BucketAddress（桶地址）。例如有一个数据，转换成数字后为2365479125443，若以每4个数字为一个部分则可拆为：2365、4791、2544、3。将这4组数字加起来后即为索引值：
2365
4791
2544
3
9703 →bucketaddress（桶地址）
在折叠法中有两种做法，如上例直接将每一部分相加所得的值作为其bucket address，这种做法我们称为“移动折叠法”。但哈希法的设计原则之一就是降低碰撞，如果希望降低碰撞的机会，就可以将上述每一部分的数字中的奇数或偶数反转，再相加来取得其bucket address，这种改进式的做法称为“边界折叠法（folding atthe boundaries）”。
请看下面的说明：
① 情况一：将偶数反转
2365(第1个是奇数故不反转)
1974(第2个是偶数要反转)
2544(第3个是奇数故不反转)
3(第4个是偶数要反转)
6886 →bucketaddress
② 情况二：将奇数反转
5632(第1个是奇数要反转)
4791(第2个是偶数故不反转)
4452(第3个是奇数要反转)
3(第4个是偶数故不反转)
14878 →bucketaddress
8-3-4 数字分析法
数字分析法适用于数据不会更改，且为数字类型的静态表。在决定哈希函数时先逐一检查数据的相对位置和分布情况，将重复性高的部分删除。例如下面这个电话号码表，它是相当有规则性的，除了区码全部是07外，中间3个数字的变化不大，假设地址空间的大小m=999，我们必须从下列数字提取适当的数字，即数字不要太不集中，分布范围较为平均（或称随机度高），最后决定提取最后那4个数字的末尾3码。故最后可得哈希表为：
电话
索引 电话
07-772-2234 234 07-772-2234
07-772-4525 525 07-772-4525
07-774-2604 604 07-774-2604
07-772-4651 651 07-772-4651
07-774-2285 285 07-774-2285
07-772-2101 101 07-772-2101
07-774-2699 699 07-774-2699
07-772-2694 694 07-772-2694
看完上面几种哈希函数之后，相信大家可以发现哈希函数并没有一定的规则可寻，可能是其中的某一种方法，也可能同时使用好几种方法，所以哈希常常被用来处理数据的加密和压缩。但是，哈希法常会遇到“碰撞”和“溢出”的情况。接下来，要了解如果遇到上述两种情况时，该如何解决。
8-4 碰撞与溢出问题的处理
没有一种哈希函数能够确保数据经过哈希运算处理后所得到的索引值都是唯一的，当索引值重复时就会产生碰撞的问题，而碰撞的情况在数据量大的时候特别容易发生。因此，如何在碰撞后处理溢出的问题就显得相当的重要。常见的溢出处理方法如下所示。
8-4-1 线性探测法
线性探测法是当发生碰撞情况时，若该索引对应的存储位置已有数据，则以线性的方式往后寻找空的存储位置，一旦找到位置就把数据放进去。线性探测法通常把哈希的位置视为环形结构，如此一来若后面的位置已被填满而前面还有位置时，可以将数据放到前面。
C语言的线性探测算法如下所示。
int creat_table(int num,int *index) /*建立哈希表子程序*/
{
int tmp;
tmp=num%INDEXBOX; /*哈希函数=数据%INDEXBOX*/
while(1)
{
if(index[tmp]==-1) /*如果数据对应的位置是空的*/
{
index[tmp]=num; /*则直接存入数据*/
break;
}
else
tmp=(tmp 1)%INDEXBOX; /*否则往后找位置存放*/
}
}
8.4.1
请设计一个C程序，以除留余数法的哈希函数取得索引值，再以线性探测法来存储数据。
请参考程序CH08_05.c，本范例程序的运行结果如图8-10所示。
图8-10 以除留余数法和线性探测法实现哈希查找和存储的范例程序的运行结果
8-4-2 平方探测
线性探测法有一个缺点，就是相类似的键值经常会聚集在一起，因此可以考虑以平方探测法来加以改进。在平方探测中，当溢出发生时，下一次查找的地址是 (f(x) i2) mod B与(f(x)-i2) mod B，即让数据值加或减i的平方，例如数据值key，哈希函数f：
第一次查找：f(key)
第二次查找：(f(key) 12)%B
第三次查找：(f(key)-12)%B
第四次查找：(f(key) 22)%B
第五次查找：(f(key)-22)%B
．
．
．
第n次查找：(f(key)±((B-1)/2)2)%B，其中，B必须为4j 3型的质数，且1≤i≤(B-1)/2
8-4-3 再哈希
再哈希就是一开始就先设置一系列的哈希函数，如果使用第一种哈希函数出现溢出时就改用第二种，如果第二种也出现溢出则改用第三种，一直到没有发生溢出为止。例如h1为key%11，h2为key*key，h3为key*key%11，h4……。
8-4-4 链表
将哈希表的所有空间建立n个链表，最初的默认值只有n个链表头。如果发生溢出就把相同地址的键值连接在链表头的后面，形成一个键表，直到所有的可用空间全部用完为止，如图8-11所示。
图8-11 以再哈希和链表来解决哈希的溢出问题
C语言的再哈希（利用链表）算法。
void creat_table(int val) /*建立哈希表子程序*/
{
link newnode;
link current;
int hash;
hash=val%7; /*哈希函数除以7取余数*/
newnode=(link)malloc(sizeof(node));
current=(link)malloc(sizeof(node));
newnode->val=val;
newnode->next=NULL;
*current=indextable[hash];
if(current->next==NULL)
indextable[hash].next=newnode;
else
while(current->next!=NULL)current=current->next;
current->next=newnode; /*将节点加在链表*/
}
8.4.2
请设计一个C程序，使用链表来进行再哈希处理。
请参考程序CH08_06.c，本范例程序的运行结果如图8-12所示。
图8-12 使用链表来进行再哈希处理的范例程序的运行结果
8.4.3
在范例8.4.2中已经把原始数据值存在哈希表中，如果现在要查找一个数据，只需将它先经过哈希函数的处理后，直接到索引值对应的链表中查找，如果没找到，则表示数据不存在。如此一来可大幅减少读取数据和进行数据对比的次数，甚至可能第一次的读取和对比就找到想找的数据。请设计一个C程序，加入查找的功能，并打印出对比的次数。
请参考程序CH08_07.c，本范例程序的运行结果如图8-13所示。
图8-13 实现哈希查找的范例程序的运行结果
1. 若有n项数据已排序完成，请问用二分查找法查找其中某一项数据，其查找时间约为：
（A）O(log2n) （B）O(n) （C）O(n2) （D）O(log2n)
（D）
2. 请问使用二分查找法（Binary Search）的前提条件是什么？
必须存放在可以直接存取且已排好序的文件中。
3. 有关二分查找法，下列叙述哪一个是正确的？
（A）文件必须事先排序
（B）当排序数据非常小时，其时间会比顺序查找法慢
（C）排序的复杂度比顺序查找法要高
（D）以上都正确
（D）
4. 下图为二叉查找树（Binary Search Tree），试绘出当插入键值（Key）为“42”后的新二叉树。注意，插入这个键值后仍需保持高度为3的二叉查找树。
5. 用二叉查找树去表示n个元素时，最小高度和最大高度的二叉查找树（Height of Binary Search Tree）其值分别是什么？
（1）最大高度二叉查找树的高度为n（例如：斜二叉树）
（2）最小高度二叉查找树为完全二叉树，高度为“log2(n 1)”。
6. 斐波那契查找法查找的过程中算术运算比二分查找法简单，请问上述说明是否正确？
正确。因为它只会用到加减运算而不像二分法有除法运算。
7. 假设A[i]=2i，1≤i≤n。若欲查找键值为2k-1，请以插值查找法进行查找，试求需要比较几次才能确定此为一次失败的查找？
2次。
8. 用哈希法将下列7个数字存在0、1、…、6的7个位置：101、186、16、315、202、572、463。若欲存入1000开始的11个位置，又应该如何存放？
f(X)=X mod 7
f(101)=3
f(186)=4
f(16)=2
f(315)=0
f(202)=6
f(572)=5
f(463)=1
同理取：
f(X)=(X mod 11) 1000
f(101)=1002
f(186)=1010
f(16)=1005
f(315)=1007
f(202)=1004
f(572)=1000
f(463)=1001
9. 什么哈希函数？试以除留余数法和折叠法（Folding Method），并以7位电话号码作为数据进行说明。
以下列6组电话号码为例：
（1）9847585
（2）9315776
（3）3635251
（4）2860322
（5）2621780
（6）8921644
1 除留余数法：
利用fD(X)=X mod M，假设M=10
fD(9847585)=9847585 mod 10=5
fD(9315776)=9315776 mod 10=6
fD(3635251)=3635251 mod 10=1
fD(2860322)=2830322 mod 10=2
fD(2621780)=2621780 mod 10=0
fD(8921644)=8921644 mod 10=4
2 折叠法：
将数据分成几段，除最后一段外，每段长度都相同，再把每段值相加。
f(9847585)=984 758 5=1747
f(9315776)=931 577 6=1514
f(3635251)=363 525 1=889
f(2860322)=286 032 2=320
f(2621780)=262 178 0=440
f(8921644)=892 164 4=1060
10. 试述哈希查找与一般查找技巧有何不同？
一般而言，判断一个查找法的好坏主要由其比较次数和查找时间来决定，一般的查找技巧主要是通过各种不同的比较方式来查找所要的数据项，反观哈希则直接通过数学函数来取得对应的地址，因此可以快速找到所要的数据。也就是说，在没有发生任何碰撞的情况下，其比较时间只需O(1)的时间复杂度。除此之外，它不仅可以用来进行查找的工作，还可以很方便地使用哈希函数来进行创建、插入、删除与更新等操作。重要的是，通过哈希函数来进行查找的文件，事先不需要排序，这也是它和一般的查找有较大的差异之处。
11. 什么是完美哈希？在何种情况下可使用？
所谓完美哈希是指该哈希函数在存入与读取的过程中，不会发生碰撞或溢出，一般而言，只有在静态表的情况下才可以使用。
12. 假设有n个数据记录（Data Record），我们要在这个记录中查找一个特定键值（Key Value）的记录。
（1）若用顺序查找（Sequential Search），平均查找长度（Search Length）是多少？
（2）若用二分查找（Binary Search），平均查找长度是多少？
（3）在什么情况下才能使用二分查找法去查找一个特定记录？
（4）若找不到要查找的记录，在二分查找法中要进行多少次比较（Comparison）？
答：
（1） 次
（2） 次
（3）已排序完成的文件
（4）O(log2n)
13. 采用哪一种哈希函数可以使用下列的整数集合：{74, 53, 66, 12, 90, 31, 18,77, 85, 29}存入数组空间为10的哈希表不会发生碰撞？
采用数字分析法，并取键值的个位数作为其存放地址。
14. 解决哈希碰撞有一种叫Quadratic的方法，请证明碰撞函数为h(k)，其中k为key，当哈希碰撞发生时 h(k)±i2，1≤i≤ ，M为哈希表的大小，这样的方法能涵盖哈希表的每一个位置，即证明该碰撞函数h(k) 将产生0 ~ (M-1) 之间的所有正整数。
提示：可以导出，h(i)为一个哈希函数值，
15. 当哈希函数f(x)=5x 4时，请分别计算下列7项键值所对应的哈希值。
87、65、54、76、21、39、103
? f(87)=5×87 4=439
? f(65)=5×65 4=329
? f(54)=5×54 4=274
? f(76)=5×76 4=384
? f(21)=5×21 4=109
? f(39)=5×39 4=199
? f(103)=5×103 4=519
16. 请解释下列哈希函数的相关名词。
Bucket（桶）
同义词
完美哈希
碰撞
bucket（桶）：哈希表中存储数据的位置，每一个位置对应到唯一的一个地址（bucket address）。桶就好比存在一个记录的位置。
同义词：当两个标识符I1和I2，经哈希函数运算后所得的数值相同，即f(I1)=f(I2)，则称I1与I2对于f这个哈希函数是同义词。
完美哈希（perfecthashing）：指没有碰撞又没有溢出的哈希函数。
若两项不同的数据，经过哈希函数运算后，对应到相同的地址时，就称为碰撞。
17. 有一个二叉查找树（Binary Search Tree）
（1）键值key平均分配在[1,100]之间，求在该查找树查找平均要比较几次。
（2）假设k=1时，其概率为0.5，k=4时其概率为0.3，k=9时其概率为0.103，其余97个数，概率为0.001。
（3）假设各key的概率如（2），是否能将此查找树重新安排？
（4）以得到的最小平均比较次数，绘出重新调整后的查找树。
（1）2.97次
（2）2.997次
（3）可以重新安排此查找树
（4）
18. 试写出下列一组数据（1, 2, 3, 6, 9, 11, 17, 28, 29, 30, 41,47, 53, 55, 67, 78）以插值查找法找到9的过程。
（1）先找到m=2，键值为2
（2）再找到m=4，键值为6
（3）最后找到m=5，键值为9
图解数据结构 （第二版） pdf下载声明
本pdf资料下载仅供个人学习和研究使用，不能用于商业用途，请在下载后24小时内删除。如果喜欢，请购买正版
