C语言算法:查找

时间：2010-11-21 来源：osullishuai80

一、查找
(1)根据给定的某个值，在查找表中确定一个关键字等于给定值的记录或数据元素，若表中存在这样的一个记录，则成查找成功.
(2)在文件系统中，经常要对磁盘上文件的记录进行各种检索操作，如根据歌曲名找到相应的音频文件路径播放歌曲.
(3)常见的有顺序查找、二分查找、哈希表等. 二、顺序查找
(1)从文件的第一个记录开始，将每个记录的关键字与给定的关键字key进行比较，如果查找到该记录，就返回该记录的地址，否则返回失败.
(2)这种查找方法最笨，时间复杂度最高0(n).
【例程】根据学生的某一项数据，查找该学生的其它数据.该例程以学生成绩作为关键字.
     typedef struct student
     {
        int id;         /*学生编号*/
        char name[20];   /*学生名字*/
        float score;    /*学生分数*/
     }Student;
            /*初始化结构体*/
     Student stu[4] = {
           {100,"beibei",98.5},
           {101,"jingjing",96.5},
           {102,"huanhuan",94.5},
           {103,"yingying",95}
                   };
     /*顺序查找算法*/
     int search(Student stu[] ,int n ,int key)
    {
        int i;
        for(i=0;i<n;i++)
        {
           if( stu[i].id == key )
               return i;   /*查找成功*/
        }
        return -1;         /*查找失败*/
    } 三、二分查找
(1)如果从文件中读取的记录关键字是有序排列的，则可以用一种效率更高的查找访法来实现，即二分查找.
(2)二分查找的基本思路是，每次都将关键字与中间的元素对比，如果不香灯再判断关键字范围并移动上下限指针，继续折半比较.
(3)二分查找的时间复杂度最高为0(n/2).
【例程】以二分法查找有序序列中的元素
      #include <stdio.h>
      int main(void)
     {
        int value;
        int array[10]={0,1,2,3,4,5,6,7,8,9};
        int ret;         while(1)
       {
           printf("\n请输入你要查找的数字:\n");
           scanf("%d",&value);
           ret = search(array,value,10);
           if(ret==-1)
              printf("数字没找到!\n");
           else
              printf("查找数据的下标是：%d\n",ret);
       }
     }
     //二分法对以排好序的数据进行查找
     int search(int array[],int value,int size)
    {
       int low=0,high=size-1,mid;     //这3个变量均为数组元素的下标

       while(low<=high)               //只要高低不碰头就继续二分查找
      {
          mid=(low+high)/2;
          if(value==array[mid])      //比较是不是与中间元素相等
             return mid;
          else if(value > array[mid])//每查找一次，就判断一次所要查找变量所在范围，并继续二分
             low=mid+1;           //如果大小中间值，下限移到中间的后一个位，上限不变，往高方向二分
          else
             high=mid-1;          //上限移到中间的前一个位，往低方向二分
      }
      return -1;
   }