Untitled Document

五、（6分）函数 binary（）实现折半查找，即查寻给定的单词 word是否在关键字表 tab中（关键字按字典顺序排列），折半查找每次把word与tab表中相应部分的位于中间位置的关键字进行比较，最终结果：或者与某个关键字相同，或者与所有关键字都不相同。

#include <string.h>
struct key{char *keyword; int count;};
struct key *binary(char *word,struct key tab[],int n)
//word: a searching word
//tab: keyword table
//n: the sum of keywords
{
int cond;
struct key *low=tab;
struct key *high=&tab[n-1];
struct key *mid;

while(low<=high){
mid=_____①______; //low+(high-low)/2或(high+low)/2
if((cond=strcmp(word,mid->keyword))<0)
high=mid-1;
else if (cond>0)
______②_______; //low=mid+1
else return mid;
}
return(NULL);
}

六、（8分）下面程序实现汉诺塔游戏。规则是：三个立柱（分别为A、B、C），开始A上串有n个（用户输入值）大小不等的圆盘，大的在下，小的在上。要求借助于B把它们从A移到C。每次只能移一个盘，而且三个柱上的盘总是大的在下，小的在上

#include <stdio.h>
int i=0;
void main( )
{
int n;
void movetower(int m,char from, char to,char usg);
for (;;){
printf("input the number of disks of hanoi tower:");
scanf("%d",&n);
if (n==0) ____①____; //break或return
printf("\n\n");
printf("The moving step is as below:\n");
movetower(n,'A','C','B');
printf("\tTotal:%d\n",i);
}
}

void movetower (int m,char from, char to,char usg)
{
void movedisk(char source,char destination);

if (____②____){ //m!=1或m>1
movetower(m-1,from,usg,to);
____③____; //movedisk(from,to)
movetower(m-1, ____④____); //usg,to,from
}
else movedisk(from,to);
}

void movedisk(char source,char destination)
{
i++;
printf("%c------->%c\n",source,destination);
}