The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

Exploring in The Art Of Programming about Huffman Tree's Creation.

 

/*数据结构作业之——哈弗曼树的构造以及WPL的计算;
给出叶子结点的权值,然后求出其WPL 
程序中出现的叶子结点均为正数,并以0结束
*/

//Get Guidance By Mr ZhangHong
//Student: abilitytao

#include
<iostream>
#include
<cmath>
#include
<cstring>
using namespace std;
#define MAX 10000000

struct node 
{
    
int w;
    
int p;
    
int lch;
    
int rch;
}
huffman[MAX];




int search_min(int l,int r)
{

    
int min=999999999;
    
int mark=0;
    
int i;
    
for(i=l;i<=r;i++)
    
{
        
if(huffman[i].w<min&&huffman[i].p==0)
        
{
            min
=huffman[i].w;
            mark
=i;
        }

    }

    
return mark;
    
}


int search_second_min(int l,int r)
{
    
int min=search_min(l,r);
    
int secondmin=999999999;
    
int mark=0;
    
int i;
    
for(i=l;i<=r;i++)
    
{

        
if(huffman[i].w>=huffman[min].w&&huffman[i].w<=secondmin&&huffman[i].p==0&&i!=min)
        
{
            secondmin
=huffman[i].w;
            mark
=i;
            
        }


    }

    
return mark;
}


int main()
{

    
int n;
    
int i;
    
int num;
    
for(i=1;;i++)
    
{

        scanf(
"%d",&n);
        huffman[i].w
=n;
        huffman[i].p
=0;
        huffman[i].lch
=0;
        huffman[i].rch
=0;
        
if(n==0)
            
break;
    }

    num
=i-1;

    
int pos=num;
    
for(i=1;i<=num-1;i++)
    
{
        
int max_mark=search_min(1,i+num-1);
        
int secondmax_mark=search_second_min(1,i+num-1);
        
++pos;
        huffman[pos].w
=huffman[max_mark].w+huffman[secondmax_mark].w;
        huffman[pos].p
=0;
        huffman[pos].lch
=secondmax_mark;
        huffman[pos].rch
=max_mark;
        huffman[max_mark].p
=pos;
        huffman[secondmax_mark].p
=pos;
    }

    printf(
"这棵树的WPL为:%d\n",huffman[pos].w);
    system(
"pause");
    
return 0;
}





posted on 2009-03-23 20:57 abilitytao 阅读(1076) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理