ch8_2.c

本内容为清华大学严蔚敏版数据结构部分算法实现代码

#include<stdio.h>
#include<stdlib.h>
void main()
{
  int i,n,target,ans;
  int *data;
  int binary(int *, int, int);        /* 折半查找的子程序 */
  printf("How many data do you want to input? ");
  scanf("%d", &n);                     /* 要求输入数据的总数 */
  data=(int *)malloc(sizeof(int)*n);/* 指定数组给数据存储 */
  for(i=0; i<n; i++)
  {
    printf("Input data: ");
    scanf("%d", &data[i]);                  /* 依序存入数据 */
  }
  printf("Input target to search: ");    /* 输入查找目标 */
  scanf("%d", &target);
  // 开始查找，并输出结果
  ans=binary(data, n, target);           /* 查找结果的响应 */
  if(ans==0)
    printf("Data %d can't find!", target);
                                                /* 没查找到数据 */
  else
    printf("Data %d at %d.", target, ans+1);
                                            /* 查找到数据并列出 */
}
int binary(int *k, int n, int key)
{
  int u, l, m;
  u=n;
  l=1;
  while(u>=l)                          /* 数据比较的循环部分 */
  { 
    m=(u+l)/2;
    if(k[m]==key)
      return m;
    else if(k[m]<key)
      l=m+1;
    else
      u=m-1;
  }
  return 0;
}