二进制文件排序及文件二分法查询

小鱼儿 2022-09-25 10:24 280阅读 0赞

二进制文件排序，注意这个使用的场景：

如果文件较大，无法一次性读入到内存中，可以使用这样的排序法对文件进行排序，排序好的文件可以使用 文件二分查询法 对文件进行查询。 注意这儿的 文件二分查询法与普通 的 二分查询法的不同，这儿是操作的文件指针进行移动来查询。详见下面的代码：

#define _CRT_SECURE_NO_WARNINGS
    #include<stdio.h>
    #include<stdlib.h>
    
    #define N 100
    //文件排序：
    //适用的场景为，当文件很大，内存不能完全读入时可以使用文件排序。
    //排序好后，可以使用 二分查找法查询文件。
    
    //从文件中读出
    void read()
    {
    	printf("开始读文件！\n");
    	FILE *pf = fopen("c:\\test.txt", "rb");		
    	while (!feof(pf))
    	{
    	int num;
    	fread(&num, sizeof(int), 1, pf);
    	printf("%4d\n", num);
    	}
    
    
    	fclose(pf);
    }
    //写入到文件
    void write()
    {
    	time_t times;
    	unsigned int num = time(×);	
    	srand(num);		//产生随机数种子
    	FILE *pfw = fopen("c:\\test.txt", "wb");
    	for (int i = 0; i < N; i++)
    	{
    		int num = rand() % 100;
    		//printf("%3d\n", num);
    		fwrite(&num, sizeof(int), 1, pfw);	//写到文件中
    	}
    
    	fclose(pfw);
    }
    
    //文件排序，这里操作的是文件。
    void sort()
    {
    	FILE *pfr = fopen("c:\\test.txt", "rb+");
    	if (pfr == NULL)
    	{
    		printf("打开失败！\n");
    		return;
    	}
    	
    	//for (int i = 0; i < N; i++)
    	//{
    	//	for (int j = 0; j < N - 1 - i; j++)
    	//	{
    	//		int datai = 0;
    	//		fseek(pfr, j*sizeof(int), SEEK_SET);	//定位到当			
    	//		fread(&datai, sizeof(int), 1, pfr);	//取出定位的值。
    
    	//		int dataj = 0;
    	//		fseek(pfr, (j + 1)*sizeof(int), SEEK_SET);	//定位到当						
    	//		fread(&dataj, sizeof(int), 1, pfr);	//取出定位的值。		
    
    	//		//上面二步是取出定位的当值，然后进行比较。
    	//		if (datai > dataj)
    	//		{
    	//			//交换数据			
    	//			fseek(pfr, j*sizeof(int), SEEK_SET);
    	//			fwrite(&dataj, sizeof(int), 1, pfr);
    	//			fseek(pfr, (j + 1)*sizeof(int), SEEK_SET);
    	//			fwrite(&datai, sizeof(int), 1, pfr);
    	//		}
    	//		//printf("%2d %2d\n", datai, dataj);
    	//	}
    	//}
    
    
    	for (int i = 0; i < N-1;i++)
    	{
    		for (int j = i+1; j < N ; j++)
    		{
    			int datai = 0;
    			int dataj = 0;
    			fseek(pfr, i*sizeof(int), SEEK_SET);
    			fread(&datai, sizeof(int), 1, pfr);
    			fseek(pfr, j*sizeof(int), SEEK_SET);
    			fread(&dataj, sizeof(int),1, pfr);
    			//printf("%2d %2d\n", datai, dataj);
    			if (datai>dataj)
    			{
    				fseek(pfr, i*sizeof(int), SEEK_SET);
    				fwrite(&dataj, sizeof(int), 1, pfr);
    				fseek(pfr, j*sizeof(int), SEEK_SET);
    				fwrite(&datai, sizeof(int), 1, pfr);				
    			}
    			//printf("%2d %2d\n", datai, dataj);
    		}
    	}
    	fclose(pfr);
    }
    
    //二分查找法，先要文件排好序。
    void binesearch(int data)
    {
    	FILE *pfr = fopen("c:\\test.txt", "rb");
    	if (pfr == NULL)
    	{
    		printf("文件打开失败！\n");
    		return;
    	}
    
    	int start = 0;
    	int end = 99;
    	int sum = 0;
    	while (start <= end)
    	{
    		int mid = (start + end) / 2;
    		fseek(pfr, sizeof(int)*mid, SEEK_SET);	//文件指针移到mid处
    		int num;
    		fread(&num, sizeof(int), 1, pfr);	//读出数值到 num 中
    		if (data == num)
    		{
    			printf("找到数据:%d\n", num);
    			break;
    		}
    		if (data > num)
    		{
    			start = mid + 1;
    			mid = (start + end) / 2;
    		}
    		if (data < num)
    		{
    			end = mid - 1;
    			mid = (start + end) / 2;
    		}
    		sum++;
    	}
    	printf("查找了 %d 次。", sum);
    
    }
    
    
    void main()
    {
    	write();
    
    	read();
    	printf("开始排序：\n");
    	sort();
    	printf("排序后的文件：\n");
    	read();
    	while (1)
    	{
    		int data;
    		printf("请输入要查询的数据：");
    		scanf("%d", &data);
    		binesearch(data);
    	}
    	system("pause");
    }