哈夫曼树的算法编码

是要这个吗?
哈夫曼编码的原代码

/*
HuffmanCode BY Turbo C 2.0
Filename: Huffman.cAuthor: dcyu.Ver 1.00
*/#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <malloc.h>
#include <conio.h>typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
} HTNode,*HuffmanTree;typedef char **HuffmanCode;typedef struct {
unsigned int s1;
unsigned int s2;
} MinCode;void Error(char *message);
HuffmanCode HuffmanCoding(HuffmanTree HT,HuffmanCode HC,unsigned int *w,unsigned int n);
MinCode Select(HuffmanTree HT,unsigned int n);void Error(char *message)
{
fprintf(stderr,"Error:%s\n",message);
exit(1);
}HuffmanCode HuffmanCoding(HuffmanTree HT,HuffmanCode HC,unsigned int *w,unsigned int n)
{
unsigned int i,s1=0,s2=0;
HuffmanTree p;
char *cd;
unsigned int f,c,start,m;
MinCode min;
if(n<=1) Error("Code too small!");
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(p=HT,i=0;i<=n;i++,p++,w++)
{
p->weight=*w;
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++)
{
min=Select(HT,i-1);
s1=min.s1;
s2=min.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;
}
printf("HT List:\n");
printf("Number\t\tweight\t\tparent\t\tlchild\t\trchild\n");
for(i=1;i<=m;i++)
printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\n",
i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
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);
return HC;
}MinCode Select(HuffmanTree HT,unsigned int n)
{
unsigned int min,secmin;
unsigned int temp;
unsigned int i,s1,s2,tempi;
MinCode code;
s1=1;s2=1;
for(i=1;i<=n;i++)
if(HT[i].parent==0)
{
min=HT[i].weight;
s1=i;
break;
}
tempi=i++;
for(;i<=n;i++)
if(HT[i].weight<min&&HT[i].parent==0)
{
min=HT[i].weight;
s1=i;
}
for(i=tempi;i<=n;i++)
if(HT[i].parent==0&&i!=s1)
{
secmin=HT[i].weight;
s2=i;
break;
}
for(i=1;i<=n;i++)
if(HT[i].weight<secmin&&i!=s1&&HT[i].parent==0)
{
secmin=HT[i].weight;
s2=i;
}
if(s1>s2)
{
temp=s1;
s1=s2;
s2=temp;
}
code.s1=s1;
code.s2=s2;
return code;
}void main()
{
HuffmanTree HT=NULL;
HuffmanCode HC=NULL;
unsigned int *w=NULL;
unsigned int i,n;
printf("Input n:\n");
scanf("%d",&n);
w=(unsigned int *)malloc((n+1)*sizeof(unsigned int *));
w[0]=0;
printf("Enter weight:\n");
for(i=1;i<=n;i++)
{
printf("w[%d]=",i);
scanf("%d",&w[i]);
}
HC=HuffmanCoding(HT,HC,w,n);
printf("HuffmanCode:\n");
printf("Number\t\tWeight\t\tCode\n");
for(i=1;i<=n;i++)
printf("%d\t\t%d\t\t%s\n",i,w[i],HC[i]);}

我正好给同学写了一个：
#include<iostream.h>struct elem{
char name;
float weight;
int *code;
};struct node{
node* leftson;
node* rightson;
float weight;
elem elementary;
};
class Huffman
{
public:
Huffman();
~Huffman();
private://viarables
int M;
elem *nodes;
node *tree;
int index;
int *code;
int flag;
private://functions
void MakeupTree();
void coding(int,node*);
public://functions
void doCode();//coding：编码
elem* deCode(int*);//decode：译码};
void main()
{
Huffman huffman;
huffman.doCode();}//fuctions of class Huffman
Huffman::Huffman()
{
char name;
int i=0;
cout<<endl<<"Please input the number of codes(if M<=0 to use defualt):";
cin>>M;
if(M>0)
{
index=2*M-2;
tree=new node[2*M-1];
code=new int[2*M];
nodes=new elem[M];
for(i=0;i<M;i++)
{
cout<<endl<<"Please input name:";
cin>>nodes[i].name;
cout<<"Please input weight:";
cin>>nodes[i].weight;
}
}
else
{
M=5;
index=2*M-2;
tree=new node[2*M-1];
code=new int[2*M];
nodes=new elem[M];
nodes[0].name='a';
nodes[0].weight=2;
nodes[1].name='b';
nodes[1].weight=54;
nodes[2].name='c';
nodes[2].weight=16;
nodes[3].name='d';
nodes[3].weight=9;
nodes[4].name='e';
nodes[4].weight=34;
}
//initialize nodes[i].codes
for(i=0;i<M;i++)
{
nodes[i].code=new int[2*M];
}
//initialize code
for (i=0;i<2*M;i++)
code[i]=-1;
//sort
for(i=0;i<M-1;i++)
{
for(int j=i+1;j<M;j++)
{
if(nodes[j-1].weight>nodes[j].weight)
{
nodes[j-1].weight=nodes[j-1].weight+nodes[j].weight;
nodes[j].weight=nodes[j-1].weight-nodes[j].weight;
nodes[j-1].weight=nodes[j-1].weight-nodes[j].weight;
name=nodes[j-1].name;
nodes[j-1].name=nodes[j].name;
nodes[j].name=name;
}
}
}
for(i=0;i<M;i++)
{
tree[i].elementary=nodes[i];
tree[i].weight=nodes[i].weight;
tree[i].leftson=NULL;
tree[i].rightson=NULL;
}}Huffman::~Huffman()
{
//free the recource
delete []tree;
delete []code;
for(int i=0;i<M;i++)
{
delete []nodes[i].code;
}
delete []nodes;
}void Huffman::MakeupTree()
{
node node0,node1,node2; if(index==2*M-2)flag=M;
if(index>0)
{
node0.weight=tree[0].weight+tree[1].weight;
node1=tree[0];
node2=tree[1];
tree[index]=node1;
node0.leftson=&tree[index--];
tree[index]=node2;
node0.rightson=&tree[index--];
for(int i=0;i<flag-2;i++)
{
tree[i]=tree[i+2];
}
flag--;
for(i=0;i<flag-1;i++)
{
if(node0.weight<tree[i].weight)
break;
}
for(int j=flag-1;i<j;j--)
{
tree[j]=tree[j-1];
}
tree[i]=node0;
MakeupTree();
}
return;
}void Huffman::coding(int sign,node *head)
{
if(head!=NULL)
{
code[sign]=0;
coding(sign+1,head->leftson);
code[sign]=1;
coding(sign+1,head->rightson);
}
else
{

return;
}
if(head->rightson==NULL)
{
for(int i=0;i<=sign;i++)
head->elementary.code[i]=code[i];
head->elementary.code[sign]=-1;
code[sign]=-1;
for(int j=0;head->elementary.name!=nodes[j].name;j++);
for(i=0;code[i]>=0;i++)
{
nodes[j].code[i]=code[i];
}
nodes[j].code[i]=-1;
//cout
cout<<endl<<head->elementary.name<<":";
//cout
for(i=0;head->elementary.code[i]!=-1;i++)
cout<<head->elementary.code[i];
return;
}
}void Huffman::doCode()
{
MakeupTree();
coding(0,&tree[0]);
}elem* Huffman::deCode(int*matchingCode)//the end of matchingCode is integer -1
{
bool judge=false;
for(int i=0;i<M&&judge==false;i++)
{
for(int j=0;matchingCode[j]==nodes[i].code[j]&&matchingCode[j]>=0;j++);
if(matchingCode<0)judge=true;
}
if(judge)return &nodes[i];
else return NULL;
}

顺便问一下，csdn改版后，我怎么找不到提问的那个按钮呢？？？？？？？

My code:（实验课做的多媒体压缩算法编码）
/*
   Name: Huffman
   Author: Catzuru
   Description: The process of writing Huffman codes on 7 signals in C++.
   Date: 02/10/20
   Copyright: Public domain
*/
#include <iostream.h>
#include <math.h>
#include <stdlib.h>
#include <malloc.h>#define Null 0     //在此定义：空地址指针Null值为0 struct Node                   //这个结构用来描述二叉树每个接点的数据内容
{
struct Node *left;        //二叉树节点左孩子的地址
char symbol[2];           //二叉树节点的命名标识
struct Node *right;       //二叉树节点右孩子的地址
};struct Sarray                 //这个结构用来记录输入的数据
{
char symbol[2];           //输入信号的标识
float prb;                //该信号的发生概率
struct Node *addr;        //这个信号在二叉树当中对应节点的地址
};struct Result                 //这个结构用来保存二叉树遍历时信号（包括新建节点）的相关内容
{
   char symbol[2];            //该节点（信号）的标识
   int length;                //该节点（信号）Huffman编码的长度
   char path[7];              //这个数组保存了该信号Huffman编码的码值
};static struct Result result[7];   //这个结构数组在二叉树遍历时开始使用，记录7个原始信号的相关内容 //主程序从这里开始
void main()
{
struct Sarray Array[7];    //这个结构数组保存了7个原始数据的输入
float temp=0;
float total=0;             //该变量用来记录每两个信号合成后，新节点（信号）的发生概率
    int i,j,k;                   //中间计数器

    void Traverse(struct Node *T,int step);    //二叉树遍历函数 //Input the data.
cout<<"\nNow the beginning of the Huffman!";
cout<<"\nPlease input the odds of each symbol:";
for(i=0;i<7;i++)
{
cout<<"\n a"<<i<<": ";
cin>>temp;
if(temp<=0||temp>1)         //核查输入是否合法
{
cout<<"/nError data!";
exit(1);;
}
else {                     //如果单个输入是正确的，则
     //_itoa(i, Array[i].symbol, 10);
     Array[i].symbol[0]='a';  //该信号命名为ai
        Array[i].symbol[1]=(char)i;
Array[i].prb=temp;                         //发生概率为刚才输入的数值
total+=temp;                               //在这里total用来统计所有信号发生概率之和是否等于1
temp=0;                                    //为确保不影响后面的数据输入，这里temp置0
//Array[i].addr=Null;                        //暂时不为该信号分配（在二叉树当中的）存储空间
};
}
if(total!=1)                         //如果所有信号的发生概率之和不等于1
{
cout<<"\nTatal>1,error data!";
exit(1);
  };

  //sort
  char t_symbol[2];
  for(i=0;i<6;i++)               //以下是冒泡排序过程
     for(j=i+1;j<7;j++)
{
  if(Array[i].prb<Array[j].prb)
{
  temp=Array[i].prb;
  t_symbol[0]=Array[i].symbol[0];
  t_symbol[1]=Array[i].symbol[1];
  Array[i].prb=Array[j].prb;
  Array[i].symbol[0]=Array[j].symbol[0];
  Array[i].symbol[1]=Array[j].symbol[1];
  Array[j].symbol[0]=t_symbol[0];
  Array[j].symbol[1]=t_symbol[1];
  Array[j].prb=temp;
  }
}
   struct Node *p;
for(i=0;i<7;i++)   //输出各个信号的概率，并为它们分配（在二叉树中的）存储空间
{
    p=(struct Node *)malloc(sizeof(struct Node));
Array[i].addr=p;
p->left=Null;
p->right=Null;
p->symbol[0]='a';
p->symbol[1]=(char)i;
cout<<"\n"<<Array[i].symbol[0]<<Array[i].symbol[1]<<i<<" : "<<Array[i].prb<<Array[i].addr;
                cout<<"   "<<Array[i].addr;
}

    //Huffman
    temp=0.0;
    int time=0;   //该变量用来记录Huffman过程进行的次数
    total=0.0;    //重置

    struct Node *pleft,*pright;
    while(total<1.0)      //当概率和小雨1时，Huffman就还可以继续
    {
         total=Array[6-time].prb+Array[6-time-1].prb;  //概率相加，新节点的概率等于它们的和
         cout<<"\ntotal="<<total;
         system("PAUSE");
         pleft=Array[6-time-1].addr;     //新节点的左孩子为概率较大的节点
             pright=Array[6-time].addr;      //新节点的右孩子为概率较小的节点
             j=0;
Array[6-time].prb=0;            //产生新节点前，先在Array[]中将相应信号的概率置0
             Array[6-time-1].prb=0;
             while(total<Array[j].prb)       //找出新节点在Array[]中的合适位置（排序）
                 {  j++;}
             if(j<(6-time-1))           //如果合适的位置不在最后，则
             {
                    for(k=6-time-2;k>=j;k--)   //从这里起，后面所有的信号都要依次后挪
{
Array[k+1].symbol[0]=Array[k].symbol[0];
Array[k+1].symbol[1]=Array[k].symbol[1];
Array[k+1].prb=Array[k].prb;
                     Array[k+1].addr=Array[k].addr;
}
}
              Array[j].symbol[1]=(char)time;     //新节点的标识为Q0,Q1,Q2...，下标也就是Huffman过程的次数
          Array[j].symbol[0]='Q';
              p=(struct Node *)malloc(sizeof(struct Node));  //为新节点分配存储空间
              if(!p) exit(1);
              Array[j].addr=p;    //把这个地址填充到Array[]当中
              Array[j].prb=total;     //新节点的概率为两个信号概率之和
              p->left=pleft;      //左指针，即左孩子的地址
              p->right=pright;    //右指针
              p->symbol[0]=Array[j].symbol[0];   //把新节点的标识填到二叉树当中
              p->symbol[1]=Array[j].symbol[1];
  time++;        //Huffman过程的次数加一
                cout<<"\nGood!";
}
         cout<<"\nVery Good!";
         system("pause");


        //output
             p=Array[0].addr;   //头指针（根节点的地址）置为数组第一个元素的指针
             Traverse(p,-1);    //遍历二叉树，传入二叉树头节点的指针
             cout<<"\nThe final codes are :"; //输出原始信号的Huffman编码码值
             for(i=0;i<7;i++)
                {
                   cout<<"\nA"<<i<<" :   ";
                   for(j=0;j<=result[i].length;j++)
                      cout<<result[i].path[j];
                }
             system("pause");

         //calculation

     }void Traverse(struct Node *T,int step)    //step记录了到达该节点时，该节点的深度（处于二叉树中的第几层）
{                                         //这个层数也就是该节点Huffman编码码值的长度
static char dpath[7];                //该数组记录了从头节点一路走来碰到的所有"1"和"0"，也就是Huffman编码码值
     static int value;                    //value用来提取叶子节点标识当中的数字下标，如'a1'中的'1'
     if(T->left!=NULL)                    //如果左指针不为空，即下面还有孩子，则
     {
          step++;                         //步长递增
          dpath[step]='1';                //进入左孩子之前，左边置1
          Traverse(T->left,step);         //搜寻左子树
          dpath[step]='0';                //此时已经从左子树返回了，将进入右子树，所以右边置0
          Traverse(T->right,step);        //搜寻右子树
  step--;                         //此时可以从该节点返回了，所以步长递减
     }
     else {                                         //如果它下面没有孩子了，即它是叶子节点，则
            value=T->symbol[1];                     //提取下标，因为所有的原始信号都在叶子节点，且只有原始信号在叶子节点上
            result[value].symbol[0]=T->symbol[0];   //按下标把该叶子节点的标识拷贝到输出表中
            result[value].symbol[1]=T->symbol[1];
            result[value].length=step;              //信号的Huffman编码码值长度等于步长
            cout<<"\n   ";
            for(int j=0;j<=step;j++)                 //拷贝码值
             {
                result[value].path[j]=dpath[j];
                cout<<result[value].path[j];
               }
           system("pause");
           };
}

调试易

哈夫曼树的算法编码

解决方案 »