赫夫曼编码的设计与实现(C++)

Question

进行赫夫曼编码类的设计并实现，包括以下功能：
1.设计类的数据成员和成员函数，实现赫夫曼树的存储；
2.根据给定的通信字符出现的概率，实现赫夫曼树的建立；
3.遍历赫夫曼树，求赫夫曼编码；
4.给出一段字符串，进行赫夫曼编码；
5.将上述功能作为类的成员函数实现，编写主函数测试上述功能。
以为把c程序简单改一下就可以,但是怎么都做不对.希望编程高手帮帮忙!!要完整的程序代码+简单解说.是想学真正的弄明白,所以不用编的太复杂,符合要求就行 拜托了!!!
明天答辩 但可以推一两天.会给帮忙的仁兄多加分的

Answer 1

#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
#include <iomanip.h>
#include "string.h"
#define MAX 100
struct HafNode
{
int weight;
int parent,lchild,rchild;
char ch;
}*myHaffTree;
struct Coding
{
char bit[MAX];
char ch;
int weight;
}*myHaffCode;
void Haffman(int n)/* 构造哈弗曼树 */
{
int i,j,x1,x2,s1,s2;
for (i=n+1;i<=2*n-1;i++)//求出最小的两个节点，总节点数为2n-1
{
s1=s2=10000;
x1=x2=0;
for (j=1;j<=i-1;j++)
{
if(myHaffTree[j].parent==0&&myHaffTree[j].weight<s1)//s1、s2记录两个最小权值，s1最小
{
s2=s1;
x2=x1;
s1=myHaffTree[j].weight;
x1=j;
}
else if(myHaffTree[j].parent==0&&myHaffTree[j].weight<s2)
{
s2=myHaffTree[j].weight;
x2=j;
}
}
myHaffTree[x1].parent=i;
myHaffTree[x2].parent=i;
myHaffTree[i].weight=s1+s2;
myHaffTree[i].lchild=x1;
myHaffTree[i].rchild=x2;
}

}
void HaffmanCode(int n)
{
int start,c,f,i,j,k;
char *cd;
cd=(char *)malloc(n*sizeof(char));
myHaffCode=(struct Coding *)malloc((n+1)*sizeof(struct Coding));
cd[n-1]='\0';
for(i=1;i<=n;++i)//循环对每个节点编码
{
start=n-1;
for(c=i,f=myHaffTree[i].parent;f!=0;c=f,f=myHaffTree[f].parent)
if(myHaffTree[f].lchild==c) cd[--start]='0';
else cd[--start]='1';
for(j=start,k=0;j<n;j++)//将节点的编码记录下来
{
myHaffCode[i].bit[k]=cd[j];
k++;
}
myHaffCode[i].ch=myHaffTree[i].ch;//对应编码结构体赋字符
myHaffCode[i].weight=myHaffTree[i].weight;//对应编码结构体赋权值
}
free(cd);
}
void print()
{
printf("*******************************************************************************\n");
printf("* HuffmanCode and HUffmanTranslate System \n");
printf("* ***********哈夫曼编码/译码系统***********\n");
printf("* *************欢迎使用本系统****************\n");
printf("* 北京石油化工学院 计G102班 \n");
printf("* 制作人：邱广威 庞国辉 李花 陈永伟\n");
printf("*******************************************************************************\n");

printf("****在本系统中您可以进行如下操作： \n");
printf("****第一部分功能：\n");
printf("**** 1 :初始化(Initialization)\n");
printf("****第二部分功能： \n");
printf("**** 2 :编码(Encoding)\n");
printf("**** 3 :译码(Decoding)\n");
printf("**** 4 :打印哈夫曼树(Tree printing)\n");
printf("****第三部分功能： \n");
printf("**** 5 :退出本系统 \n");
printf("*******************************************************************************\n");
printf("************************ Copyright by WeiWei ********************\n");
printf("*******************************************************************************\n");
}
Init()//哈夫曼树初始化
{

int i,n,m;
FILE *codef;
printf("初始化中···\n");
printf("请输入字符个数:\n");
scanf("%d",&n);
m=2*n-1;
myHaffTree=(struct HafNode *)malloc(sizeof(struct HafNode)*(m+1));//申请内存空间
for(i=1;i<=n;i++)//为每个叶子节点置权值和字符，并且父节点和孩子节点都为空。
{
printf("请输入字符和权值:\n");
scanf("%s%d",&myHaffTree[i].ch,&myHaffTree[i].weight);
myHaffTree[i].parent=0;
myHaffTree[i].lchild=0;
myHaffTree[i].rchild=0;
}
for(i=n+1;i<=m;i++)//对二度节点置空值
{
myHaffTree[i].ch ='#';
myHaffTree[i].lchild=0;
myHaffTree[i].parent=0;
myHaffTree[i].rchild=0;
myHaffTree[i].weight=0;
}
Haffman(n);//构造哈夫曼树
HaffmanCode(n);//编码
for(i=1;i<=n;i++)
{
printf("%c \t%d\t%s\t",myHaffCode[i].ch,myHaffCode[i].weight,myHaffCode[i].bit );
printf("\n");

}
if((codef=fopen("codef.txt","a"))==NULL)
{printf("创建文件失败");
exit(0);
}

for(i=1;i<=n;i++)
{
fprintf(codef,"%c \t%d\t%s\t\n",myHaffCode[i].ch,myHaffCode[i].weight,myHaffCode[i].bit );
}
printf("初始化成功!\n");
fclose(codef);
printf("编码已经输出到codef.txt中！！！\n");
return n;
}
void Caozuo_C(int m)/* 对字符进行编码 */
{
int n,i,j;
FILE *confile;
if((confile=fopen("file.txt","a"))==NULL)
{printf("创建文件失败");
exit(0);
}
char string[50],*p;
printf("请输入要编码的字符：\n");
scanf("%s",string);
n=strlen(string);
for(i=1,p=string;i<=n;i++,p++)
{
for(j=1;j<=m;j++)
if(myHaffCode[j].ch==*p)
{ printf("%s\n",myHaffCode[j].bit);
fprintf(confile,"%c\t%s\t\n",*p,myHaffCode[j].bit);
}
}
fclose(confile);
printf("字母编码已经写入到file.txt中！\n");
}
void Caozuo_D(int n)
{
int c;
FILE * text;
char code[1000],*p;
if((text=fopen("t.txt","a"))==NULL)
{printf("创建文件失败");
return;
}
printf("请输入要译码的的数：\n");
scanf("%s",code);

for(p=code,c=2*n-1;*p!='\0';p++)
{
if(*p=='0')
{
c=myHaffTree[c].lchild;
if(myHaffTree[c].lchild==0)
{
printf("%c",myHaffTree[c].ch);
fprintf(text,"%c",myHaffTree[c].ch);
c=2*n-1;
continue;
}
}
else if(*p=='1')
{
c=myHaffTree[c].rchild;
if(myHaffTree[c].lchild==0)
{
printf("%c",myHaffTree[c].ch);
fprintf(text,"%c\t",myHaffTree[c].ch);
c=2*n-1;
continue;
}
}

else if(*p!=0&&*p!=1)
{
printf("输入错误，请重新输入！！！\n");
return;

}
}
printf("\n");
fclose(text);
printf("译码字符已经写入到text.txt文件中！\n");
}
void Caozuo_T(int n)
{
int i;
printf("叶子节点号\t叶子节点\t权值\t左孩子\t右孩子\t双亲节点\t节点编码\n");
for(i=1;i<=2*n-1;i++)
printf("%d\t%c\t\t%d\t%d\t %d\t %d\t%s\n",i,myHaffTree[i].ch,myHaffTree[i].weight,myHaffTree[i].lchild,myHaffTree[i].rchild,myHaffTree[i].parent,myHaffCode[i].bit);
}

void main()
{
int n;
char char1;
print();
n=Init();
while(1)
{
printf("A.编码 B.译码 C.打印哈夫曼树 D.退出\n请输入操作代码:\n");
scanf("%s",&char1);
if(char1=='D')
break;
switch(char1)
{case'A':Caozuo_C(n);break;/* 执行编码操作 */
case'B':Caozuo_D(n);break;/* 执行译码操作 */
case'C':Caozuo_T(n);break;/* 打印哈弗曼树 */
default: printf("输入错误。\n");break;
}
}
}

Answer 2

哈弗曼树的构造和编码
#include <iostream.h>
int n;
class Huffcode
{
public:
char std[20];
int start;
};
class Huffman
{
public:
int left;
int right;
int parent;
char val;
int weight;
};
Huffcode q[20];
Huffman p[40];
//p=new Huffman [n];
void creatcode(Huffman *p)
{
int i;
Huffcode d;
// d.std=new char [n];
//q=new Huffcode [n];
//for(i=0;i<n;i++)
// q[i].std=new char [n];
for(i=0;i<n;i++)
{
int t=i;
d.start=n;
int temp=p[t].parent;
while(temp!=0)
{
if(t==p[temp].left)
d.std[--d.start]='0';
else
d.std[--d.start]='1';
t=temp;
temp=p[t].parent;
}
q[i]=d;
}
}
void display()
{
cout<<"please putout the huffcode:\n";
for(int i=0;i<n;i++)
{
for(int j=q[i].start;j<n;j++)
cout<<q[i].std[j];
cout<<endl;
}
}

void creat()
{
//Huffman *p;
int i;
//p=new Huffman [2*n];
for(i=0;i<n;i++)
{
p[i].left=p[i].right=p[i].parent=p[i].weight=0;
p[i].val='0';
}
for(i=0;i<n;i++)
{
cout<<"please enter the val and weight:\n";
cin>>p[i].val>>p[i].weight;
}
for(int j=n;j<2*n;j++)
{
int temp1,temp2,l,r;
temp1=temp2=32567;
l=r=0;
for(i=0;i<j;i++)
if(p[i].parent==0)
{
if(p[i].weight<temp1)
{
temp2=temp1;
temp1=p[i].weight;
r=l;
l=i;
}
else if(p[i].weight<temp2)
{
temp1=p[i].weight;
r=i;
}
}
p[j].left=l;
p[j].right=r;
p[j].weight=temp1+temp2;
p[l].parent=j;
p[r].parent=j;
}
// return p;
}
void main()
{
//Huffman k;
//Huffman *p;
cout<<"please enter number:\n";
cin>>n;
// p=new Huffman [n];
//k.getnum();
creat();
creatcode(p);
display();
}本回答被提问者采纳