程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 用敗者樹做的多路歸並程序

用敗者樹做的多路歸並程序

編輯:關於C語言

 

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的專欄

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved