数据结构毫无疑问是计算机科学既经典又核心的课程之一，不管是从事计算机软件还是硬件的开发工作，如果没有系统地学习数据结构或者是没有专心自学过，很容易被人打上“非专业”的标签。对于任何在信息技术行业工作的专业人员或者想进入此行业的人来说，什么时候开始学数据结构都不会晚，更不会过时。
从“数据结构”的名字看，它不仅仅只是讲授数据的结构以及在计算机内如何存储和组织数据的方式，这些只是它的表面现象。数据结构背后真正蕴含的是与之息息相关的算法，精心选择的数据结构配合恰如其分的算法就意味着数据或者信息在计算机内被高效率地存储和高效率地处理。算法其实就是数据结构的灵魂，它既神秘又神奇“好玩”，当然对初学者也比较难，算法可以说是“聪明人在计算机上的游戏”。
本书是一本综合而且全面讲述数据结构及其算法分析的教科书，为了便于高校的教学或者读者自学，作者在描述数据结构原理和算法时文字清晰并且严谨，为每个算法及其数据结构提供了演算的详细图解。另外，为了适合在教学中让学生上机实践或者自学者上机“操练”，本书为每个经典的算法都提供了C语言编写的完整范例程序的源代码，每个范例程序都不需要经过修改，直接通过编译就可以运行，目的就是让本书的学习者以这些范例程序作为参照迅速掌握数据结构和算法的要点。
全书的所有范例程序都可以在标准的C语言编程环境中编译通过并且成功运行，我们在改编本书的过程中选用了免费的Dev C++ 5.11集成开发环境，对原书的所有范例程序进行编译、修改、调试和测试，并确保它们都可以准确无误地运行。附录A包含了“C/C++编译程序的介绍与安装”，其中重点就介绍了Dev C++。附录B则包含了“C语言快速入门”。
第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]\n",i+1,data[i]);
find++;
}
}
if(find==0 && val !=-1)
printf("######没有找到 [%3d]######\n",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("查找过程中......\n");
while(low <= high && val !=-1)
{
mid=(low+high)/2;
if(val
{
printf("%d 介于位置 %d[%3d]和中间值 %d[%3d]，找左半边\n",val,low+1, data[low],mid+1,data[mid]);
high=mid-1;
}
else if(val>data[mid])
{
printf("%d 介于中间值位置 %d[%3d] 和 %d[%3d]，找右半边\n",val,mid+1, data[mid],high+1,data[high]);
low=mid+1;
}
else
return mid;
}
return -1;
……
新书资讯