4.6　程序举例

例4-9　顺序查找。有7个数存放在一个数组中，从键盘输入1个数，查找这个数是否在数组中，如果在，输出其下标，如果不在，输出0。数组的下标i表示第i个元素，数组的下标0处不存储数。

算法思路　此例只需依次将数组元素与输入的数进行比较，如果相等则终止循环。如果元素比较完还未找到输入的数，则输出0。

方法1　从第1个元素到第n个元素依次与输入元素比较，若不相同，则继续比较下一个元素，若相等则退出循环。循环结束后，需根据i的值的不同来判断查找是否成功。

方法2　从第n个元素到第1个元素依次与输入元素比较，若不相同，则继续比较下一个元素，若相等则退出循环。循环结束后直接输出i的值即可。这个方法与方法1实际上是相同的，只是由于比较是从后到前进行的，因此循环结束后，不需对i的值进行比较，直接输出i的值即为所求的。

方法3　从第n个元素到第1个元素依次与输入元素比较，使用监视哨。

方法3的思想与方法2的实际上是一样的，只是方法3中先将a[0]的值赋为x，其目的是免去查找过程中每一步都要检测的数组是否越界的问题。这仅是一个程序设计技巧上的改进，然而实践证明，这个改进能使顺序查找在数据元素的个数大于1000时，进行一次查找所需的平均时间减少几乎一半。

使用方法3进行顺序查找的程序如下所示：

例4-10　折半查找。有7个数已经按从小到大的顺序存储在数组中，输入一个数，用折半查找法查找这个数是否在数组中，如果在，输出其下标，如果不在，输出0。数组的下标i表示第i个元素，数组的下标0处不存储数。

算法思路　折半查找又称对分查找，是对有序表进行的一种查找。

其基本思想是：先确定待查找的数据元素的范围，然后逐步缩小范围直到找到要查找的数据元素或无法找到该元素为止。

具体思路是：最初待查找的数据元素的范围是整个数组，找到数据元素范围的“中间元素”，将其与待查找的元素x比较：如果当前元素的值与给定值x相等，则查找成功；如果当前元素小于给定值x，则说明被查找数必在后半区间内；反之则在前半区间内。这样把查找区间缩小了一半，继续进行查找。

例如：已知数组中按顺序存储着以下7个数：7，14，18，20，23，31，40。现要查找18和25。

查找18的过程为：最初的查找范围是整个数组，其中间元素为a[4]即20，将其与待查找元素18进行比较，因为a[4]较大，因此待查找数一定在前半区间内，即查找范围应为a[1]到a[3]；其中间元素为a[2]即14，将其与待查找元素18进行比较，因为a[2]较小，因此待查找数一定在后半区间内，即查找范围应为a[3]到a[3]；其中间元素为a[3]即18，它与待查找的元素相等，因此查找成功，可以输出数组元素的下标3。

查找25的过程为：最初的查找范围是整个数组，其中间元素为a[4]即20，比25小，因此待查找数一定在后半区间内，即查找范围应为a[5]到a[7]；其中间元素为a[6]即31，大于25，因此待查找数一定在前半区间内，即查找范围为a[5]到a[5]；其中间元素为a[5]即23，它小于待排序元素，再细分区间将不包含任何元素，说明数组中没有值为25的元素，即查找不成功，输出0。

为了表示待查找元素所在的区间，可以用两个整型变量low、high分别表示区间的最左和最右边的数组下标，用整型变量mid表示区间的中间元素，其值为（low+high）/2；当x与a[mid]比较时，如果a[mid]较大，则待查找数在前半区间，其最左边的下标不变，最右边的下标high变为mid−1；如果a[mid]较小，则待查找数在后半区间，其最右边的下标不变，最左边的下标low变为mid+1；如果a[mid]与x相同，则查找成功，mid即为所求。当low〉high时，表示待查找元素所在的区间为空，此时查找不成功，返回0即可。

参考程序如下：

上面的程序中第20行到第28行是用于折半查找的核心程序段。

由《数据结构》的相关知识可知，对于长度为n的数组进行查找，使用折半查找平均只需比较log₂n次，而使用顺序查找则需比较n/2次。因此，当数组较大时，使用折半查找的效率远比顺序查找高。只是折半查找要求数组内的元素需按顺序排列，而顺序查找则无此要求。正因为如此，在用于解决实际问题的程序中，一般都要求使用排序算法将记录排序后，再进行查找，以提高效率。

例4-11　用直接插入排序法对7个整数按从小到大的顺序排序。

算法分析　直接插入排序法是最简单的排序方法之一，它的基本操作是将—个元素插入到已排好序的序列中，从而得到一个新的、元素个数增l的有序序列。

例如：待排序元素的初始序列如下：21，25，49，26，18，8，31。前3个元素已按从小到大的顺序排列，构成一个有3个元素的有序序列{21，25，49}，现要将第4个元素，即26插入到这个序列中，以得到一个新的含有4个元素的有序序列。则首先要在序列{21，25，49}中进行查找，以确定26所要插入的位置。假设从49开始依次向左进行查找，由于25〈26〈49，因此应将26插入到25和49之间，构成一个新的有序序列{21，25，26，49}。称上面的这个过程为一趟直接插入排序。

一般情况下，第i趟直接插入排序的操作为：在含有i−1个元素的有序序列a[1]，a[2]，…，a[i−1]中插入一个新的元素a[i]，使得序列a[1]，a[2]，…，a[i−1]，a[i]是一个有序序列；并且和例4-9顺序查找的方法3类似，为了在查找插入位置的过程中避免数组越界，可设a[0]为监视哨。另外，在自i−1向前查找插入位置的过程中，可同时后移元素。

整个排序的过程为进行n−1趟排序。即先将a[1]看做一个已排序的序列，将a[2]插入，构成含有两个元素的有序序列，再将a[3]，a[4]，…，a[n]依次插入到已排序的序列中，构成更大的有序序列，直到整个序列都变成了有序序列为止。

按照这个算法，对序列{21，25，49，26，18，8，31}进行排序的过程如图4.6.1所示。

因此，直接插入排序的算法为：

（1）用数组a存储待排序元素，n存储待排序的元素的个数；

（2）让i表示排序的遍数，其值为从2到n；

（3）在每趟排序中，a[1]，a[2]，…，a[i−1]已经排好序，以a[0]为监视哨，将a[i]依次与a[i−1]，a[i−2]，…，a[0]比较，即令循环变量j=i−1，i−2，…，0；

（4）如果a[0]〈a[j]，则将a[j]后移，否则终止此循环；

（5）将a[j+1]的值赋为a[0]。

图4.6.1　直接插入排序示例

参考程序如下：

例4-12　输入同学录中40位同学的信息。然后输入一个字符串，查找姓名为这个字符串的所有同学的位置，如果成功，则输出这些同学的生日，否则输出查询不成功的信息。本例希望能进行模糊查找，即可以只输入姓名的一部分来进行查找。

算法分析　本例希望进行模糊查找，比如可以只输入姓或名来查找相应的同学的信息，因此，即便同学的信息已按姓名排序，也无法使用折半查找，只能使用顺序查找。

因为要进行模糊查找，因此不能直接比较同学的姓名与输入的字符串相等，而要使用字符串的查找函数strstr（字符串1，字符串2），它用于查找字符串2是否在字符串1中，如果不在，则返回NULL（其值0）。

因此这个例子的主要算法是：用一个结构数组stu存储同学的信息，结构的定义与例4-8相同。存储时，数组元素stu[I]存储第I位同学的信息，stu[0]不存储同学信息。

在输入同学的信息后，输入要查找的字符串，再将监视哨stu[0].name置为输入的字符串，然后从数组尾部向前依次比较，如果待查找的字符串在当前同学的姓名中，则输出当前同学的生日。

参考程序如下：

上面程序中，第44到53行用于顺序查找，需注意的是：这里使用了C的库函数strstr来进行姓名的模糊查找。

例4-13　输入同学录中40位同学的信息，并在输入的同时对这些同学的信息按姓名排序，使得最终得到按姓名从小到大顺序排列的各位同学的信息。

算法分析　要在输入的同时排序，其算法类似于直接插入排序，即前i个同学的信息存储好后，要加入第i+1个同学的信息，只需从第i个同学开始依次向前查找，将第i+1位同学的信息放置在合适的地方。与前面例4-11不同之处在于，例4-11中数组元素为整型，因此排序时比较的是整型数，而这个例子中，要比较的是同学的姓名，这就不能使用“= =”来比较，而应使用C的库函数strcmp来进行比较。当然，在顺序查找之前，本例也需设置监视哨为stu[0]。

参考程序如下：

上面程序最需要注意的是，对两个字符串大小的判断必须使用strcmp函数，而不能直接用〈来进行判断，比如使用stu[0].name〈stu[j].name来比较两个人的姓名就是错误的，因为对这两个字符数组来说，用〈比较的将只是它们的存储位置，即内存地址，而不是其中的字符串。