文件k路归并.cpp

用归并的算法思想实验文件的k路归并

#include <stdio.h>
#define MAX 100
int move(int cost[],int len,int off)//归并一次并调整存放文件长度的数组
{
	int i,j;
	for(i=1;i<off;i++)
	{
		cost[0]+=cost[i];
	}//将有序数组的前k个文件进行成本归并
	for(j=off;j<len;j++)
	{	
		cost[j-off+1]=cost[j];
	}//将成本数组k以后的元素向前移动k-1个位置
	return cost[0];//返回的是本次归并所的到的文件的长度
}

void sort(int a[],int len)
{
	int i,j,temp;
	for(i=len-1;i>=0;i--)
		for(j=0;j<i;j++)
			if(a[j]>a[j+1])
			{
				temp=a[j];
				a[j]=a[j+1];
				a[j+1]=temp;
			}
}//冒泡排序法对现有文件序列进行排序以待归并

void out(int cost[],int len,int k,FILE *f)//将每次归并的情况输出的文件中记录下来
{
	int i,j;
	fprintf(f,"Merge:");
	for(i=0;i<k;i++)
	{
		fprintf(f,"%d ",cost[i]);
	}
	j=move(cost,len,k);//调用单步归并函数move，得到该次归并的归并成本
	fprintf(f,"Merge cost: %d\n",j);
}

void merge(int cost[],int n,int k,FILE *f)
{
	int i,all=0;
	int len;
	len=n;
	while(len>=k)//循环条件为成本数组cost的长度大于等于k，由于对待归并的文件序列进行的补0处理，
		         //因此必能保证最后一次归并时数组的长度恰好为k，所以循环结束后归并已经完成
	{
		sort(cost,len);//调用冒泡排序算法对cost进行排序
		out(cost,len,k,f);//将每次的归并过程输出到文件中记录下来
		all+=cost[0];//每次归并完后总的归并成本
		len=len-(k-1);//每归并一次后，归并文件序列长度减k-1
	}
	fprintf(f,"********************************************\n");
	fprintf(f,"Merge  %d in all \t Merge cost: %d\n",n,all);
}

int main(void)
{	int i,j,n,k;
	int a[MAX];//定义一长度为MAX的数组用于存放待归并文件的长度
	FILE *f0;//定义一文件指针用于指向结果输出文件的句柄
	printf("please input k:");
	scanf("%d",&k);//输入归并参数k
	printf("please input the number of the array:n<100\n");
	printf("the len is:");
	scanf("%d",&n);//输入待归并的文件个数
	for(j=0;n%(k-1)!=1;j++)
	{
		a[j]=0;
		n++;
	}//通过输入的n和k值确定需要补充的文件长度为0的个数
	for(i=0;i<j;i++)
	{
		printf("number %d  is %d :\n",i+1,a[i]);
	}//输出先前补的文件长度为0的个数
	for(i=j;i<n;i++)
	{	printf("input number %d:",i+1);
		scanf("%d",&a[i]);
	}//输入将要进行归并的各个文件的长度
	f0=fopen("outputklu.txt","w+");//打开输出结果文件，并将句柄赋给f0文件指针
	fprintf(f0,"待归并的文件序列如下:\n");
	for(i=0;i<n;i++)
	{
		fprintf(f0,"%2d ",a[i]);
	}//向输出文件中输出待归并的文件序列
	fprintf(f0,"\n");
	merge(a,n,k,f0);//调用归并函数对待归并的文件序列进行归并，注意同时将
					//指向文件的指针作为参数传进merge里，以便于结果输出
	fclose(f0);//关闭输出文件
	printf(":you will see the result in file output.txt!!");
}