none
霍夫曼编码的问题 请大家帮帮忙! RRS feed

  • 问题

  • 在C++环境下写的,主函数写不下去了,前面不知道有没有什么问题,请大家帮我看看

    #include<iostream>
    #include<string>
    #include <iomanip>
    #include <malloc.h>
    #include <stdio.h>


    typedef struct{
     int weight;
     int parent, lchild, rchild;
    }Hnode, *huffmantree;

    typedef char * * huffmancode;

    void huffmancoding(huffmantree & ht, huffmancode & hc, int * w, int n);
    void select(huffmantree &ht, int i , int &s1, int &s2);
    int min(huffmantree t,int i);
    void show(huffmancode & s);
    void Decoding(huffmantree ht, int n, char *buff);


    void show(huffmancode & s)
    {
     cout<<s;
    }

    void huffmancoding(huffmantree & ht, huffmancode & hc, int * w, int n)
    {
     int m , i ,f, start, c;
     int s1 , s2;
     char* cd;
     huffmantree p;
     if( n <= 1 ) return;
     m = 2 * n - 1;
     ht = (huffmantree)malloc((m + 1) * sizeof(Hnode));
     for( p = ht, i =1 ; i <= n  ; ++i, ++p, ++w) 
     {
      p->weight = w[i-1];
      p->parent = 0;
      p->lchild = 0;
      p->rchild = 0;
     }
     for( ; i<=m ; ++i ,++p){
      p->weight = 0;
      p->parent = 0;
      p->lchild = 0;
      p->rchild = 0;
      }
     for(i= n + 1; i<= m; ++i ){
      select(ht, i-1, s1, s2);
      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 *));
     cd = (char *)malloc(n * sizeof(char));
     cd[n - 1] = '\0';
     for (i= 1; i <= n; ++i){
      start = n - 1;
      for (c = i, f = ht[i].parent; f!=0; c = f, f = ht[f].parent)
      if (ht[f].lchild == c)  cd[ --start ] = '0';
      else cd[--start] = '1';
      hc[i] = (char * )malloc((n - start) * sizeof(char));
      strcpy(hc[i] , & cd[ start ]);
     }
     free(cd);
    }

    void select(huffmantree &ht, int i , int &s1, int &s2)
    {
     int j;
     s1=min(ht,i);
     s2=min(ht, i);
     if(s1>s2)
     {
      j=s1;
      s1=s2;
      s2=j;
     }
    }

    int min(huffmantree t,int i)
    {
            int j,flag;
            int k ;
            for(j=1;j<=i;j++)
                    if(t[j].weight<k&&t[j].parent==0)
                    k=t[j].weight,flag=j;
            t[flag].parent=1;
            return flag;
    }

     

    void Decoding(huffmantree ht, int n, char *buff)

    {

    int p = 2 * n -1;
    while (*buff)

    {

           if ((*buff) ==  0) 
        { p = ht[p].lchild; }

           else p = ht[p].rchild;

          

           if ( ht[p].lchild==0 && ht[p].rchild==0 )

           {

                  printf("%c", ht[p].parent);

                  p = 2 * n - 1;
    buff++;
    }

    }

     




    int main()
    {
     int n;
     int w[50]={5,29,7,8,14,23,3,11};
     huffmantree ht;
     huffmancode hc;
     cout<<"qing shu ru ni yao bian ma de zi fu"<<endl;
     huffmancoding(ht,hc,w,n);
     show(hc);
     cout<<"zmhuishia"<<endl;
    }

    2009年12月13日 13:46

答案

  • 先建立霍夫曼树,在编码,在主函数里调用编码函数对abcd26个字母进行编码,成2进制数,再把编码直接打印出来,但是我不知道用户应该怎么输入,比如abcd到z26个字母频度已知,应该是我预先在程序里设置好他们的权重?还是可以由用户输入呢?
    2009年12月14日 12:40
  • 霍夫曼编码是一种压缩编码方式。既然根据用户输入进行编码。就要根据用户输入的每个字母出现的次数进行编码。出现次数越多的字母权重越大。这样在编码后该字母获得的代码长度越短。从而降低整个输入的长度。


    麻烦把正确答案设为解答。
    2009年12月15日 1:10
    版主

全部回复

  • 你能把你的思路说一下吗?
    麻烦把正确答案设为解答。
    2009年12月14日 1:23
    版主
  • 先建立霍夫曼树,在编码,在主函数里调用编码函数对abcd26个字母进行编码,成2进制数,再把编码直接打印出来,但是我不知道用户应该怎么输入,比如abcd到z26个字母频度已知,应该是我预先在程序里设置好他们的权重?还是可以由用户输入呢?
    2009年12月14日 12:40
  • 霍夫曼编码是一种压缩编码方式。既然根据用户输入进行编码。就要根据用户输入的每个字母出现的次数进行编码。出现次数越多的字母权重越大。这样在编码后该字母获得的代码长度越短。从而降低整个输入的长度。


    麻烦把正确答案设为解答。
    2009年12月15日 1:10
    版主