用败者树做的多路归并程序
1. 这个程序目前只考虑到是完全二叉树的叶子节点的情况。
2.每个有序序列的末尾都加上了一个MAX_BIG来表示最终的结束，这样做是为了简化程序设计，不然当一个序列的最后一个元素被合并到目的序列时候，不知道该往败者树里面加什么。
0 1 2 3 4 5 6 7 8 999999999
1 2 3 4 5 6 7 8 9 999999999
4 5 6 7 8 9 10 11 12 999999999
9 10 11 12 13 14 15 16 17 999999999
0 1 1 2 2 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9 10 10 11 11 12 12 13 14 15 16 17
￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥
#include <stdio.h>
#include <stdlib.h>
typedef struct wrap_data
{
int offset;
int path;
int *data;
}wrap_data;
int choosevec(int path)
{
if(path<=4)
{
return 4;
}
else if (path<=8)
{
return 8;
}
else if(path<=16)
{
return 16;
}
else
{
return 32;
}
}
wrap_data **vec;
int vecsize;
wrap_data * up ( int num )
{
int i,j,k;
wrap_data *first,*second;
i=num;
second=vec[i];
while(i)
{
j=i/2;
first=vec[j];
if(!first)
{
vec[j]=second;
if (!j)
{
return second;
}
else
{
return NULL;
}
}
if ( first->path==second->path)
{
i=j;
}
else if ( *( second->data + second->offset )> *( first->data + first->offset ))
{
vec[j]=second;
second=first;
i=j;
}
else
{
i=j;
}
}
return second;
}
int main()
{
#define PATH 4
#define LENGTH 10
#define MAX_BIG 999999999
wrap_data *result;
int i=0,j=0,k=0;
wrap_data a[PATH]={0};
vecsize=2* choosevec(PATH);
vec=(wrap_data **)calloc( vecsize ,sizeof (wrap_data*));
for(i=0;i<PATH;i++)
{
a[i].data=(int*) calloc (LENGTH , sizeof (int ));
a[i].offset=0;
a[i].path=i;
for(j=0;j<LENGTH;j++)
{
*(a[i].data+j)=(i*i+j)%40;
}
*(a[i].data+LENGTH-1)=MAX_BIG;
}
for(i=0;i<PATH;i++)
{
for(j=0;j<LENGTH;j++)
{
printf("%d ", *(a[i].data+j));
}
printf("/n");
}
k=vecsize/2;
for(i=0;i<PATH;i++)
{
vec[k+i]=&a[i];
}
for(i=0;i<PATH;i++)
{
result=up(i+k);
if(!result)
{
}
else
{
break;
}
}
while(result)
{
if (MAX_BIG == *(result->data+result->offset))
{
break;
}
printf(" %d ", *(result->data+result->offset));
result->offset++;
result=up(result->path+k);
}
printf("/n");
}
摘自chenbingchenbing的专栏