11-10.c

这些是数据结构结构的经典实现算法

#include "stdio.h"
#define k	100
#define MINKEY 0
#define MAXKEY 200
typedef int KeyType;
typedef int LoserTree[k]; /*败者树是完全二叉树且不含叶子，可采用顺序存储结构*/
typedef struct{
	KeyType key;
}ExNode,External[k]; /*外结点，只存放待归并记录的关键码*/
External	b;
void Adjust(LoserTree *ls,int s) /*选得最小关键码记录后，从叶到根调整败者树，选下一个最小关键码*/
{ /*沿从叶子结点b[s]到根结点ls[0]的路径调整败者树*/
	int t;
	t=(s+k)/2; /*ls[t]是b[s]的双亲结点*/
	while(t>0)
	{ 
		if(b[s].key>b[*ls[t]].key) 
			s=*ls[t]; /*s指示新的胜者*/
		t=t/2;
	}
	*ls[0]=s;
}
void CreateLoserTree(LoserTree *ls) /*建立败者树*/
{ /*已知b[0]到b[k-1]为完全二叉树ls的叶子结点存有k个关键码，沿从叶子到根的k条路径*/
/*将ls调整为败者树*/
	int i;
	b[k].key=MINKEY; /*设MINKEY为关键码可能的最小值*/
	for(i=0;i<k;i++) 
		*ls[i]=k; /*设置ls中“败者”的初值*/
	for(i=k-1;k>0;i--) 
		Adjust(ls,i); /*依次从b[k-1],b[k-2],…,b[0]出发调整败者*/
}
void K_Merge(LoserTree *ls,External *b) /*k-路归并处理程序*/
{ /*利用败者树ls将编号从0到k-1的k个输入归并段中的记录归并到输出归并段*/
	/*b[0]到b[k-1]为败者树上的k个叶子结点，分别存放k个输入归并段中当前记录的关键码*/
	int i,q;
	for(i=0;i<k;i++) 
		//scanf("%d",&b[i].key); /*分别从k个输入归并段读入该段当前第一个记录的*/
	/*关键码到外结点*/
	CreateLoserTree(ls); /*建败者树ls，选得最小关键码为b[0].key*/
	while(b[*ls[0]].key!=MAXKEY)
	{ 
		q=ls[0]; /*q指示当前最小关键码所在归并段*/
		//output(q); /*将编号为q的归并段中当前(关键码为b[q].key的记录写至输出归并段)*/
		//input(b[q].key); /*从编号为q的输入归并段中读入下一个记录的关键码*/
		Adjust(ls,q); /*调整败者树，选择新的最小关键码*/
	}
	//output(ls[0]); /*将含最大关键码MAXKEY的记录写至输出归并段*/
}
void main()
{
	LoserTree *ls;
	External *b
	//初始化*ls,*b
	K_Merge(ls,b);
}