k_merge.c

K路归并算法 * 本程序用来实现K路归并算法 * 在Turbo C2.0编译器下编译通过 * 算法过程中 * K由用户输入 * 用户选择需要归并的数据的个数 * 由程序生成随机

/**
 * @(#)K_Merge.c
 *
 *
 * @author ztssky
 * @version 1.00 2007/1/2
 * 说明如下：
 * 本程序用来实现K路归并算法
 * 在Turbo C2.0编译器下编译通过
 * 算法过程中
 * K由用户输入
 * 用户选择需要归并的数据的个数
 * 由程序生成随机数据，数据结构为链表，并展示给用户
 * 然后程序告诉用户需要增加的虚节点的个数
 * 并把虚节点加入到链表中去，最后进行归并
 */
#include<stdio.h>
#include<stdlib.h>

struct intnode{
  long key;
  struct intnode *next;
};/*用链表存储待归并的数据*/

void create(struct intnode * ,int * ,int * );
/*创建数据链表函数，第一个参数为头指针，第二和第三个参数用于传回数据的个数和K值*/
int AddImNode(struct intnode * ,int ,int );
/*增加虚节点函数*/
void Sort(struct intnode * ,int );
/*排序函数，由于生成的数据随机，需要进行排序后再归并*/
struct intnode * Merge(struct intnode * ,int );
/*归并函数，用于某一趟归并*/

void main()/*主函数*/
{
	int i;/*计数器*/
	
	int K;/*K路归并中的K值*/
	int num;/*进行归并数据的个数*/
	int numtmp;/*一趟或者几趟归并后剩下的要归并数据的个数*/
	int numOfAdd;/*增加的虚节点的个数*/
  struct intnode *head,*q;/*head为头指针，指针q用于操作*/
    
	create(head,&K,&num);/*创建*/
	Sort(head,num);/*排序*/
	printf("The data to be merged are as follows:\n");
	for(q=head->next;q;q=q->next){
		  printf("%ld  ",q->key);
		}/*将生成并排序的数据展示给用户*/
	printf("\n");
	printf("There are %d data to be merged.\n",num);
	numOfAdd=AddImNode(head,num,K);/*增加虚节点*/
	numtmp=num;
	for(i=1,q=head->next;q->next;i++){
		printf("#%d\n",i);/*表示归并的趟数，比如#3表示第三趟归并*/
		q=Merge(head,K);
		numtmp-=(K-1);
		Sort(head,numtmp);/*一趟归并后数据不再有序，重新排序*/
  }/*归并，直到只剩一个节点为止*/
  printf("Done!\n");
  getch();
}/*主函数结束*/

void create(struct intnode *head,int *K,int *num)
{
	int i;
	struct intnode *p;
	printf("Input the value of K of K_Merge:");
  scanf("%d",K);
	printf("How many data do you want to merge:");
	scanf("%d",num);
	printf("Now creating data...\n");
	head->next=NULL;
	for(i=0;i<(*num);i++){
		p=(struct intnode *)malloc(sizeof(struct intnode));
		p->key=rand();/*随机生成数据*/
		p->next=head->next;
		head->next=p;
	}
	printf("Successfully created!\n");
	getch();
}/*create函数结束*/

int AddImNode(struct intnode *head,int num,int K)
{
	int mod;
	int i;
	struct intnode *p;
	if(K==2){
		mod=1;
		printf("For K=2.\n");
	}
	else{
	  mod=num%(K-1);
	  printf("For K=%d,(%d mod (K-1))=%d\n",K,num,mod);
	}
	switch(mod){
		case 0:/*增加一个虚节点*/
			printf("So we need to add one imaginary node.\nPress any key to add it.\n");
			getch();
			p=(struct intnode *)malloc(sizeof(struct intnode));
		  p->key=0;
	   	p->next=head->next;
	  	head->next=p;
	  	printf("Successfully added!\n");
	  	getch();
	  	return 1;
	  case 1:/*不需要增加虚节点*/
	  	printf("So we doesn't need any imaginary node.\n");
	  	return 0;
	  default:/*增加K-mod个虚节点*/
	  	printf("So we need to add K-%d=%d imaginary nodes.\n",mod,K-mod);
	  	printf("Press any key to add it.\n");
	  	for(i=0;i<K-mod;i++){
	  			p=(struct intnode *)malloc(sizeof(struct intnode));
		      p->key=0;
	   	    p->next=head->next;
	  	    head->next=p;
	  	}
	  	printf("Successfully added!\n");
	  	getch();
	  	return K-mod;
	}
}/*AddImNode函数结束*/

void Sort(struct intnode *head,int num)
{/*冒泡排序*/
	long temp;
	int i,j;
	struct intnode *p;
	for(i=num;i>1;i--){
		for(p=head->next,j=1;j<i;p=p->next,j++){
			if(p->key>p->next->key){
				temp=p->key;
				p->key=p->next->key;
				p->next->key=temp;
			}
		}
	}
}/*Sort函数结束*/

struct intnode * Merge(struct intnode *head ,int K)
{
	int i;/*计数器*/
	long cost=0;/*成本*/
	struct intnode *p;
	printf("Data to be merged:");
	for(i=0,p=head->next;i<K&&p;i++,p=p->next){
		printf("%ld  ",p->key);
		cost+=p->key;
		head->next=p->next;
		free(p);
	}/*归并，将归并过的数据删除*/
	printf("\ncost:%ld\n",cost);/*打印成本*/
	p=(struct intnode *)malloc(sizeof(struct intnode));
	p->key=cost;
	p->next=head->next;
	head->next=p;/*将归并得到的数据放入链表，参加下一趟归并*/
	return p;
}/*Merge函数结束*/

/*程序结束*/