| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1032 人关注过本帖
标题:Huffman算法的程序
只看楼主 加入收藏
lzb1988826
Rank: 1
等 级:新手上路
帖 子:8
专家分:0
注 册:2008-9-29
收藏
 问题点数:0 回复次数:2 
Huffman算法的程序
小弟不材,刚写出来的Huffman算法的程序。。
请高手指点一下。。
#include "stdafx.h"
#include<iostream>
using namespace std;
#include<stdlib.h>
#include<conio.h>
#include<string.h>

typedef struct{
    char name;
    unsigned int weight;
    unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;

typedef struct{
    char name;
    unsigned int weight;
}character,*characterpointer;

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,characterpointer w,int n);
void Select(HuffmanTree HT,int i,int *p);

int main()
{
    HuffmanTree HT;

    HuffmanCode HC;

    //int p[3]={0,0,0};

    cout<<"请输入要求Huffman编码的个数n"<<endl;
    int n;
    cin>>n;
    
    characterpointer w;
    w=(characterpointer)malloc((n+1)*sizeof(character));
    //HT=w;
    for(int a=1;a<=n;a++)
    {
        cout<<"请输入第"<<a<<"个字符和权重"<<endl;
        cin>>w[a].name;
        cin>>w[a].weight;
    }

    HuffmanCoding(HT,HC,w,n);

    getch();
    return 0;
}

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,characterpointer w,int n)
{
    if(n<=1)return;
    int m=2*n-1;
    HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
    HuffmanTree p;
    p=HT;
    for(int i=1;i<=n;++i)
    {
        p[i].name=w[i].name;
        p[i].weight=w[i].weight;
        p[i].parent=0;
        p[i].lchild=0;
        p[i].rchild=0;
    }
    for(;i<=m;++i)
    {
        p[i].name=0;
        p[i].weight=0;
        p[i].parent=0;
        p[i].lchild=0;
        p[i].rchild=0;
    }
        
    for(i=n+1;i<=m;++i)
    {   
        int s1,s2;
        int p[3];
        Select(HT,i,p);
        s1=p[1];s2=p[2];
        HT[s1].parent=i;HT[s2].parent=i;
        HT[i].lchild=s1;HT[i].rchild=s2;
        HT[i].weight=HT[s1].weight+HT[s2].weight;
    }
    HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
    char* cd;
    cd=(char *)malloc(n*sizeof(char));
    cd[n-1]='\0';
    int start=0;
    for(i=1;i<=n;++i)
    {
        start=n-1;
        for(int c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
            if(HT[f].lchild==c) cd[--start]=48;
            else cd[--start]=49;
            HC[i]=(char *)malloc((n-start)*sizeof(char));
            strcpy(HC[i],&cd[start]);
            cout<<HT[i].name<<"的Huffman编码是"<<HC[i]<<endl;
    }
    free(cd);
}

void Select(HuffmanTree HT,int i,int *p)
{   
    int k,l;
    for(int a=1;a<=i-1;a++)
    {
        if(HT[a].parent==0)
        {
            p[1]=HT[a].weight;
            k=a;
            break;
        }
    }
    for(int j=1;j<=i-1;j++)
    {
        if((p[1]>HT[j].weight)&&(HT[j].parent==0)&&(j!=k))
        {
            p[1]=HT[j].weight;
            k=j;
        }
    }
   
    for(a=1;a<=i-1;a++)
    {
       if(HT[a].parent==0&&(a!=k))
       {
           p[2]=HT[a].weight;
           l=a;
           break;
       }
    }

    for(j=1;j<=i-1;j++)
    {   
        if((p[2]>HT[j].weight)&&(HT[j].parent==0)&&(j!=l)&&(j!=k))
        {
            p[2]=HT[j].weight;
            l=j;
        }
    }
    
    p[1]=k;
    p[2]=l;

}
搜索更多相关主题的帖子: Huffman 算法 
2008-12-06 12:51
shediao
Rank: 1
来 自:山东
等 级:新手上路
威 望:1
帖 子:52
专家分:0
注 册:2008-9-23
收藏
得分:0 
要指点你什么呀?你没有说清楚
2008-12-06 22:11
minge
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2008-12-11
收藏
得分:0 
回复 楼主 lzb1988826 的帖子
感觉很不错啊……
2008-12-11 21:09
快速回复:Huffman算法的程序
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.076746 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved