[原创][求救]哈夫曼编／译码器代码

主题：[原创][求救]哈夫曼编／译码器代码

zhangyan1016 [专家分：0] 发布于 2006-05-15 16:56:00

一、问题描述：
利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编／译码系统。试为这样的信息收发站写一个哈夫曼码的编／译码系统。

二、基本要求：
1、I：初始化（Initialization），从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。
2、E：编码（Encoding），利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读人），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。
3、D：译码（Decoding），利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。
4、P：输出代码文件（Print），将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。
5、T：输出哈夫曼树（TreePrinting），将已在内存中的哈夫曼树以直观的方式（树或凹人表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。

三、测试数据：]
用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。

字符　 A B C D E F G H I J K L M
频度 186 64 13 22 32 103 21 15 47 1 5 32 20 20

字符 N O P Q R S T U V W X Y Z
频度 57 63 15 1 48 51 80 23 8 18 1 16 1

四、实现提示：
1、哈夫曼编码采用一个字符串数组存储。
2、用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“Q”为止。
3、在程序的一次执行过程中，第一次执行I、D或C命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。

本帖地址： http://bbs.pfan.cn/post/166131.html

回复列表（共6个回复）

沙发

cctv7 [专家分：0] 发布于 2006-06-06 12:24:00

04 xing ji

板凳

Emmanuel [专家分：0] 发布于 2006-06-06 14:56:00

同问，急！！！！！！！！！！

3 楼

wujunyue [专家分：0] 发布于 2006-12-23 15:12:00

#include <stdio.h>
#define MAX 21
typedef struct
{
    char data; /*结点值*/
    int weight; /*权值*/
    int parent; /*父结点*/
    int left; /*左结点*/
    int right;/*右结点*/
}huffnode;

typedef struct
{
    char cd[MAX];
    int start;
}huffcode;

main()
{
    huffnode ht[2*MAX];
    huffcode hcd[MAX],d;
    int i,k,f,l,r,n,c,m1,m2;

    printf("输入元素个数:");
    scanf("%d",&n);

    for (i=1;i<=n;i++)
    {
        getchar();
        printf("第%d个元素=>\n\t结点值:",i);
        scanf("%c",&ht[i].data);
        printf("\t权重:");
        scanf("%d",&ht[i].weight);
    }

    for (i=1;i<=2*n-1;i++)
        ht[i].parent=ht[i].left=ht[i].right=0;

    for(i=n+1;i<=2*n-1;i++)/*构造哈夫曼树*/
    {
        m1=m2=32767;
        l=r=0;             /*l和r是最小权重的两个结点位置*/
        for(k=1;k<=i-1;k++)
            if  (ht[k].parent==0)
                if(ht[k].weight<m1)
                {
                    m2=m1;
                    r=l;
                    m1=ht[k].weight;
                    l=k;
                }
                else if (ht[k].weight<m2)
                {
                    m2=ht[k].weight;
                    r=k;
                }

                ht[l].parent=i;
                ht[r].parent=i;
                ht[i].weight=ht[l].weight+ht[r].weight;
                ht[i].left=l;
                ht[i].right=r;
    }
    for(i=1;i<=n;i++)    /*根据哈夫曼树求哈夫曼编码*/
    {
        d.start=n+1;
        c=i;
        f=ht[i].parent;

        while(f!=0)
        {
            if(ht[f].left==c)
                d.cd[--d.start]='0';
            else
                d.cd[--d.start]='1';
            c=f;
            f=ht[f].parent;
        }
        hcd[i]=d;
    }

    printf("输出哈夫曼编码: \n");
    for(i=1;i<=n;i++)
    {
        printf("%c: ",ht[i].data);
        for(k=hcd[i].start;k<=n;k++)
            printf("%c",hcd[i].cd[k]);
        printf("\n");
    }
}

4 楼

wujunyue [专家分：0] 发布于 2006-12-23 15:13:00

不知道可不可以用

5 楼

yunweiwang1012 [专家分：0] 发布于 2006-12-28 11:34:00

#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#include"Queue.h"
struct field {
    int coding[10];
    char name;
    int Weight;
};

const  int DefaultSize = 30;
    /* 声明“扩充二叉树”的类 */
template <class Type> class ExtBinTree;
//定义“扩充二叉树”的结点
template <class Type> class Element {
friend class ExtBinTree<Type>;
private:
    Type data;
    char name;
    Element<Type> * leftChild, * rightChild;
public:
    Element ( ) : leftChild (NULL),
        rightChild (NULL) { }
    Element ( Type item,char d,
        Element<Type> *left = NULL,
        Element<Type> *right = NULL ) :
        data (item), name(d), leftChild (left), rightChild
            (right) { }
    void SetData ( const Type& item )
        { data = item; }
    void SetName ( const char& item )
        { name = item; }
    void SetLeft ( Element<Type> * L )
        { leftChild = L; }
    void SetRight ( Element<Type> * R )
        { rightChild = R; }
    Type GetData ( )  { return data; }
    char GetName ( )  { return name; }
    friend void Huffman_code (Element<Type> *p,int i,field *q,int l);
    friend int WelightPathLength(Element<Type> *p,int i);
};
template <class Type> class ExtBinTree {
private:
    Element<Type> *root;
public:
    ExtBinTree()
    {
        root= new Element<Type>;
    }
    ExtBinTree (ExtBinTree<Type> bt1,
        ExtBinTree<Type>  bt2 )
    {
        root= new Element<Type>(
            bt1.GetRootData( ) +bt2.GetRootData( ),
            0,bt1.root,bt2.root);
    }
    void SetRootData(Type x,char s,
        Element<Type> *left,
            Element<Type> *right)
    {
        root->SetData(x);
        root->SetName(s);
        root->SetLeft(left);
        root->SetRight(right);
    }
    Type GetRootData( )
    {
        return root->GetData();
    }
    char GetRootname( )
    {
        return root->Getname();
    }
    Element <Type> * Getroot( )
    {
        return root;
    }
    void  PreOrder(Element <Type> *p ) const
    {
        if ( p != NULL ) { //输出根结点数据域
            cout << p->data<< ' ';
            //递归输出p的左子树
            PreOrder ( p->leftChild );
            //递归输出p的右子树
            PreOrder ( p->rightChild );
        }
    }
    void  InOrder(Element <Type> *p ) const
    {
        if ( p != NULL ) {
            InOrder ( p->leftChild );
            cout << p->data << ' ';
            InOrder ( p->rightChild );
        }
    }
};
template <class Type> class MinHeap  {
private:
    Type * heap;
    int CurrentSize;
    int HeapMaxSize;
    void FilterDown ( int i, int m );
    void FilterUp ( int i );
public:
    MinHeap (){ }  //无参构造函数
    MinHeap ( Type arr[ ], int n );
    ~MinHeap ( ) { delete [ ] heap; }
    bool RemoveMin ( Type& x );
    bool Insert ( const Type x );
    bool IsEmpty ( ) const

                //不用调了
        else {  //向上调整
            heap[j] = heap[i];
            j = i;  i = (i -1)/2;
        }
    }

6 楼

yunweiwang1012 [专家分：0] 发布于 2006-12-28 11:35:00

频率数组数组长度  */
{
    if ( n > DefaultSize ) {
        cerr << "大小 n " << n
            << "超出了数组边界 " << endl;
        exit(0);
    }
        //两棵根结点的权值最小的扩充二叉树
    ExtBinTree <Type>  first, second;
        // first和second的合并树
    ExtBinTree <Type> * newtree;
        //具有 n 棵扩充二叉树的森林
    ExtBinTree <Type> Node[DefaultSize];
        //每棵扩充二叉树 Node[i] 只有一个带权值
        // fr[i] 的根结点, 其左、右子树均为空。
    for ( int i = 0; i < n; i++ )
        Node[i].SetRootData(fr[i],s[i],NULL,NULL);
    //定义一个最小堆，数据类型为扩充二叉树
    MinHeap < ExtBinTree <Type> > hp( Node, n );
        //建立存储扩充二叉树森林的最小堆
    //hp.MinHeap ( Node, n );
        //重复 n-1趟, 逐步形成霍夫曼树
    for ( i = 0; i < n-1; i++ ) {
        hp.RemoveMin ( first );
        hp.RemoveMin ( second );
        newtree = new ExtBinTree<Type> (first, second);
        hp.Insert ( *newtree );
    }
    return *newtree;
}
template <class Type>
int WelightPathLength(Element<Type> *p,int i)
{
    if(p==NULL)return 0;
    else
    {
        if(p->leftChild==NULL&&p->rightChild==NULL)
        {
            return p->data*i;
        }
        else
        {
            return   WelightPathLength(p->leftChild,i+1)+
                        WelightPathLength(p->rightChild,i+1);
        }
    }
}
//**函数模板：建立自动打印霍夫曼代码的算法**//
template <class Type>
void Huffman_code (Element<Type> *p,int i,field *q,int l)
{

    if(p!=NULL)
    {
        static int a[10];
        if(p!=NULL)
        {
            if(p->leftChild==NULL&&p->rightChild==NULL)
            {

            q[l].name=p->GetName();
                cout<<p->GetName()<<": ";
                for(int j=0;j<i;j++)
                cout<<a[j];
                cout<<endl;
            }
        else
            a[i]=0;Huffman_code(p->leftChild,i+1,q,l);
            a[i]=1;Huffman_code(p->rightChild,i+1,q,l);

        }
    }
}
int * weight(int *f)
{
    int *a=f,c;
    for(int i=0;i<26;i++)
        a[i]=0;
    FILE *fp;
    char *filename="out.txt";
    if((fp=fopen(filename,"r"))==NULL)
    {   printf("cannot open file\n");
         exit(0);
    }
    while((c=fgetc(fp))!=EOF)
    {
        if(96<c&&c<123)
        a[c-97]=a[c-97]+1;
    }
    fclose(fp);//主函数
void main()
{
    int i=0,len=0,l=0;
    field ss[26];
    char c[26];
    //叶子结点的频率（权重）表
    int f[26];
    weight(f);
    for(int v=0;v<26;v++)
    {
        c[v]=v+97;
    }
    int n=26; //叶子结点数目
    //生成霍夫曼树
    ExtBinTree <int> H=HuffmanTree(f,c,n);
    Huffman_code(H.Getroot(),i,ss,l);
    H.PreOrder(H.Getroot());
    cout<<endl;
    cout<<"路径长度: "<<WelightPathLength(H.Getroot(),len)<<endl;
}

    return a;
}

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：[原创][求救]哈夫曼编／译码器代码

回复列表（共6个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：[原创][求救]哈夫曼编／译码器 代码

回复列表 （共6个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：[原创][求救]哈夫曼编／译码器代码

回复列表（共6个回复）