查找与排序

查找方法有：顺序查找、折半查找等。今天主要讲解的是查找，后续在讲解排序的方法。并附有源代码。

在文件系统中，经常要对文件的记录进行各种各样的操作，主要包括：文件的查找：对用户指定的文件中的记录进行查找，也称为检索。

插入记录：将一个新的记录插入到文件的指定位置。

记录的删除：从文件中删除指定的记录。

文件的排序：对文件中的记录按指定的关键字的顺序进行排序。

修改文件的记录：修改文件中记录的内容，并更新。

顺序查找

如果一个文件具有n个连续的记录，可将该文件读到内存中的一个顺序表中进行各种操作。顺序查找就是在文件的关键字集合key[1,2,...,n]中找出与给定的关键字key相等的文件记录。如图2-2所示，磁盘中有这样一个顺序文件。对文件中记录的查找就是对其关键字的查找，找到了关键字就找到了该关键字对应的那条记录。

#include "stdio.h"
typedef struct student{
    int id;            	/*学生编号*/
    char name[10];    	/*学生姓名*/
    float score;        	/*成绩*/ 
}Student;
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; 							/*查找失败*/
 
}
main()
{
    Student stu[4] = {{1004,"TOM",100} ,	
                      {1002,"LILY",95},
                      {1001,"ANN",93},
                      {1003,"LUCY",98}
                      };						/*初始化结构体数组*/
    int addr;									/*要查找的记录的地址*/
    addr = search(stu,4,1001);
	if (addr == -1) {							/*查找无此记录,程序返回*/
		printf("There is no this record\n");
		return;
	}
    printf("Student ID:   %d\n",stu[addr].id);	/*输出查找到的记录的信息*/
    printf("Student name: %s\n",stu[addr].name);
    printf("Student score: %f\n",stu[addr].score);
    getche();
	return;
}

折半查找

如果从文件中读取的数据记录的关键字是有序排列的，则可以用一种效率更高的查找方法来查找文件中的记录，这就是折半查找法，又称为二分搜索。

折半查找的基本思想是：减小查找序列的长度，分而治之地进行关键字的查找。它的查找过程是：先确定待查找记录的所在的范围，然后逐渐缩小查找的范围，直至找到该记录为止（也可能查找失败）。

#include "stdio.h"
bin_search(int A[],int n,int key){
    int low,high,mid;
    low = 0;
    high = n-1;
    while(low<=high)
    {
        mid = (low + high)/2;
        if(A[mid]==key)return mid;			/*查找成功，返回mid*/
        if(A[mid]<key){
            low = mid + 1;					/*在后半序列中查找*/
        }
        if(A[mid]>key){
            high = mid - 1;					/*在前半序列中查找*/
        }
    }
    return -1;								/*查找失败，返回-1*/
}
main()
{
    int A[10] = {2,3,5,7,8,10,12,15,19,21},i,n ,addr;
    printf("The contents of the Array A[10] are\n");
    for(i=0;i<10;i++)
    printf("%d ",A[i]);					/*显示数组A中的内容*/
    printf("\nPlease input a interger for search\n");
    scanf("%d",&n);						/*输入待查找的元素*/
    addr = bin_search(A,10,n);			/*折半查找，返回该元素在数组中的下标*/
    if(-1 != addr)						/*查找成功*/
                printf("%d is at the %dth unit is array A\n ",n,addr);
    else printf("There is no %d in array A\n",n);		/*查找失败*/
    getche();
}