频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
哈夫曼树
2013-02-18 13:11:38           
收藏   我要投稿
主要是记录一道九度的哈夫曼树的题目

 

题目

[html] 

题目描述:  

哈夫曼树,第一行输入一个数n,表示叶结点的个数。需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出所有结点的值与权值的乘积之和。  

输入:  

输入有多组数据。  

每组第一行输入一个数n,接着输入n个叶节点(叶节点权值不超过100,2<=n<=1000)。  

输出:  

输出权值。  

样例输入:  

5    

1 2 2 5 9  

样例输出:  

37  

 

ac代码

[cpp] 

#include <stdio.h>  

#include <stdlib.h>  

#define max 1001  

  

struct htree  

{  

    int weight;  

    struct htree *lchild;  

    struct htree *rchild;  

    struct htree *next;  

};  

  

void addNode(struct htree *, struct htree *);  

struct htree* createHfmtree(int *, int);  

int getWpl(struct htree *, int);  

  

int main()  

{  

    int w[max];  

    int i, n, wpl;  

    struct htree *ht;  

  

    while(scanf("%d", &n) != EOF)  

    {  

        for(i = 0; i < n; i ++)  

        {  

            scanf("%d", &w[i]);  

        }  

          

        ht = createHfmtree(w, n);  

        wpl = getWpl(ht, 0);  

        printf("%d\n", wpl);  

    }  

    return 0;  

}  

  

struct htree* createHfmtree(int *w, int n)  

{  

    int i;  

    struct htree *head, *pl, *pr, *proot;  

    head = (struct htree *)malloc(sizeof(struct htree));  

    head->next = NULL;  

  

    for(i = 0; i < n; i ++)  

    {  

        struct htree *pnode = malloc(sizeof(struct htree));  

        pnode->weight = *(w + i);  

        pnode->lchild = pnode->rchild = pnode->next = NULL;  

        addNode(head, pnode);  

    }  

  

    while(head->next)  

    {  

        if(head->next->next == NULL)  

            break;  

        pl = head->next;  

        pr = pl->next;  

        head->next = pr->next;  

        proot = (struct htree *)malloc(sizeof(struct htree));  

        proot->weight = pl->weight + pr->weight;  

        proot->lchild = pl;  

        proot->rchild = pr;  

        addNode(head, proot);  

    }  

    return head->next;  

}  

  

void addNode(struct htree *head, struct htree *pnode)  

{  

    struct htree *t = head;  

  

    while(t->next && t->next->weight < pnode->weight)  

        t = t->next;  

    pnode->next = t->next;  

    t->next = pnode;  

}  www.2cto.com

  

int getWpl(struct htree *ht, int level)  

{  

    if(ht == NULL)  

        return 0;  

    if(!ht->lchild && !ht->rchild)   

    {  

        return ht->weight * level;  

    }  

  

    return getWpl(ht->lchild, level + 1) + getWpl(ht->rchild, level + 1);  

}  

 

点击复制链接 与好友分享!回本站首页
相关TAG标签 哈夫曼
上一篇:ZeroMQ指南-第1章-基础-放出消息
下一篇:ZeroMQ指南-第1章-基础-分而治之
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站