败者树（多路归并）

落日映苍穹つ 2022-03-26 01:48 253阅读 0赞

已知顺串 R1\[10,15,16\],R2\[9,20,38\].R3\[20,20,30\], R4\[6,15,25\],R5\[8,15,20\],R6\[9,11,16\], R7\[90,100,110\],R8\[17,18,20\]建立败者树

编程工具：Dev-C++

读入文件losertree.txt:

8  
3  
10 15 16  
3  
9 20 38  
3  
20 20 30  
3  
6 15 25  
3  
8 15 20  
3  
9 11 16  
3  
90 100 110  
3  
17 18 20

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgyMTg3NA_size_16_color_FFFFFF_t_70][]

#include <iostream>
    #include <stdio.h>
    #include <stdlib.h> 
    using namespace std;
    #define LEN 10			//最大归并段长 
    #define MINKEY -1     //默认全为正数
    #define MAXKEY 1000    //最大值,当一个段全部输出后的赋值
     
    struct Array
    {
    	int arr[LEN];
    	int length;  //顺串长度 
    	int current; //当前顺串扫描的位置 
    }*A;
     
    int *LoserTree,*leave;
    int k,count;
     
    void Adjust(int s)
    /*从叶子结点leave[s]到根结点的父结点LoserTree[0]调整败者树*/
    {
    	int t=(s+k)/2;  //t是leave[s]父节点在败者树的下标 
    	int temp;
    	while(t>0)
    	{
    		if(leave[s] > leave[LoserTree[t]])
    		{
    			temp = s;
    			s = LoserTree[t];
    			LoserTree[t]=temp;
    		}
    		t=t/2;
    	}
    	LoserTree[0]=s;
    }
     
    void CreateLoserTree()
    {
    	leave[k]=MINKEY;
    	int i;
    	for(i=0;i<k;i++)LoserTree[i]=k; //依次调整败者 
    	for(i=k-1;i>=0;i--)Adjust(i);
    }
     
    void K_Merge()
    {
    	int i,p;
    	for(i=0;i<k;i++)
    	{
    		p = A[i].current;  //分别读取k个顺串的第一个数据 
    		leave[i]=A[i].arr[p];
    		//cout<<leave[i]<<"  ";
    		A[i].current++;
    	}
    	CreateLoserTree();
    	int flag = 0;
    	while(flag<count)
    	{
    		p=LoserTree[0];  //p为当前最小关键字所在的顺串 
    		cout<<leave[p]<<"  ";
    		flag++;
    		if(A[p].current>=A[p].length)leave[p]=MAXKEY;
    		else 
    		{
    			leave[p]=A[p].arr[A[p].current];
    			A[p].current++;
    		}
    		Adjust(p);
    	}
    	cout<<endl;
    }
     
    int main()
    {
    	freopen("losertree.txt","r",stdin);  //代替键盘输入 
    	int i,j;
    	count=0;
    	cin>>k;    //顺串的个数 
    	A=(Array *)malloc(sizeof(Array)*k);
    	for(i=0;i<k;i++)
    	{
    		cin>>A[i].length;  //顺串数组的长度 
    		count=count+A[i].length;  //数据总数 
    		for(j=0;j<A[i].length;j++)
    		{
    			cin>>A[i].arr[j];  //顺串各元素 
    		}
    		A[i].current=0;
    	}
    	LoserTree=(int *)malloc(sizeof(int)*k);
    	leave=(int *)malloc(sizeof(int)*(k+1));
     	printf("多路归并排序结果：\n");
    	K_Merge();
     
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgyMTg3NA_size_16_color_FFFFFF_t_70]: /images/20220326/86b356aad37f4d1f871776f0e54f85a5.png