C语言程序设计-一维数组应用示例

【例6-3】假设整型数组a中已经存有10个数据,请用键盘输入一个整数x并判断x是否存在于数组a中,如存在则输出其在数组中的单元下标,否则输出“Not Found!”。　　

解题思路:

　　查找是计算机中常用的基础操作。对一般的、无规律的数据,最直接的查找方法就是逐个和待查找的数据进行比较。如果某个数据和待查找数据相等则查找成功,输出相等数据所对应存储单元下标即可;如果不相等则继续比较下一个,直到全部数据比较完,若仍不存在相等情况,则输出Not Found。

程序中的for循环有两种结束可能:一种情况是a[i]＝＝x,此时执行break提前结束了循环;另一种情况是一直没有找到和x相等的单元,当i不停自加直到i＝10时,由于循环条件不成立而停止。因此当循环终止执行后,应判读是哪一种情况导致了循环的终止,若循环终止后i值仍小于10,则说明是提前终止了循环的执行,输出单元下标i即可,否则输出Not Found!。

【例6-4】假设数组a中存放了10个从小到大有序的整数,请输入一个整数x并判断x是否存在于数组a中,如存在则输出其在数组中的单元下标,否则输出“Not Found!”。

　　解题思路:

　　基于有序数据的查找可以使用折半查找(又叫二分查找)。假设待查找范围的低下标为s,高下标为h,用m表示s和h的中间位置,三者关系如图6-2所示。

图6-2　折半查找示意

折半查找比较的第一个位置是m号单元,这里的m取值为(s＋h)/2,若x＝＝a[m]表示查找成功,输出m的值即可;若x＜a[m],则x只可能在s到m－1的范围内存在,令h＝m－1,继续在低一半中折半查找;若x＞a[m],则x只可能在m＋1到h的范围内存在,令s＝m＋1,继续在高一半中折半查找,算法描述如下:

(3)重复步骤(2)继续查找。

还存在一个问题,该算法中的查找过程什么时候结束?当然若存在和x相等的元素,程序可以提前结束循环并输出m的值。但如果数组中没有和x相等的元素,循环什么时候结束呢?从以上查找过程可以看出,折半查找是利用s和h逐步缩小查找范围并且一次“折”掉了一半的元素,此过程中s和h将逐渐靠拢,如果最后s＞h了,则说明这样的查找范围不存在,也就是查找失败的情况,此时输出Not Found!。综合以上分析,源程序如下:

在用数组存储一批有序数据的情况下,由于一次可以缩小一半的查找范围,折半是一种非常高效的查找方法,请大家认真体会。

【例6-5】　假设有一长度为n的从小到大有序的整型数组,请输入一个整数x并将x插入数组的适当位置,插入后仍保持数组从小到大有序。(www.xing528.com)

解题思路:

由于插入一个数据后数组中有n＋1个数据,因此数组长度最少应为n＋1。在有序数组中插入一个数据到合适的位置,可以分为三个步骤:

(1)查找该数据的插入位置。

(2)将此位置(包含该位置)以后的数据全部向后移动一个单元,为待插入数据腾出位置。

(3)在腾出的空位置中放入要插入的数据。

依照此思路,程序如下:

　　以上程序稍嫌烦琐,如果从数组的最后一个数据开始比较,采取边比较边向后移动数据的方法,则可以将第一步和第二部合在一起一次完成。程序如下所示:

两个程序采取的方法是一样的,只是后者将查找插入位置和移动数据元素腾出插入位置的操作合在一个循环中完成,书写形式上简洁一些。

【例6-6】找出一个数组中的最小值并输出该最小值及其对应的下标。

解题思路:

采取“打擂台”的方法来选出优胜者。在打擂台时,先有一个选手站在擂台上接受其他选手的挑战,胜者则留在擂台上,继续接受下一个选手的挑战。以此类推,直到所有的选手均挑战完毕,最后留在擂台上的选手即为获胜者。

程序中可以采取同样的方法选出最小值及其下标,源程序如下:

程序中用min表示擂台,用minindex记录最小值下标。a[0]为第一个上擂台的选手,其下标minindex为0。从1号单元开始,每一个单元和min值进行比较,若该单元比min中的当前值更小,就将其留在min中(min＝a[i]),同时用minindex记录其下标(minindex＝i)。全部数据比较完后,min中就是所有数据中的最小值,minindex就是该最小值的下标。