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 阅读(1132) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理