哈弗曼编码译码器 求高手看看这个程序哪里错了
求高手看看这个程序哪里错了 要求用下表给出的字符集和频度的实际统计数据建立赫夫曼树,并实现以下报文的编码和译码:“THIS PROGRAME 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 57 1 5 32 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
#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<fstream.h>
typedef struct{ //赫夫曼树的结构体
char ch;
int weight; //权值
int parent,lchild,rchild;
}htnode,*hfmtree;
typedef char **hfmcode;
void Select(hfmtree &HT,int a,int *p1,int *p2) //Select函数,选出HT树到a为止,权值最小且parent为0的2个节点
{
int i,j,x,y;
for(j=1;j<=a;++j){
if(HT[j].parent==0){
x=j;
break;
}
}
for(i=j+1;i<=a;++i){
if(HT[i].weight<HT[x].weight&&HT[i].parent==0){
x=i; //选出最小的节点
}
}
for(j=1;j<=a;++j) {
if(HT[j].parent==0&&x!=j)
{
y=j;
break;
}
}
for(i=j+1;i<=a;++i)
{
if(HT[i].weight<HT[y].weight&&HT[i].parent==0&&x!=i)
{
y=i; //选出次小的节点
}
}
if(x>y){
*p1=y;
*p2=x;
}
else
{
*p1=x;
*p2=y;
}
}
void hfmcoding(hfmtree &HT,hfmcode &HC,int n) //构建赫夫曼树HT,并求出n个字符的赫夫曼编码HC
{
int i,start,c,f,m,w;
int p1,p2;
char *cd,z;
if(n<=1){
return;
}
m=2*n-1;
HT=(hfmtree)malloc((m+1)*sizeof(htnode));
for(i=1;i<=n;++i) //初始化n个叶子结点
{
printf("请输入第%d字符信息和权值:",i);
scanf("%c%d",&z,&w);
while(getchar()!='\n')
{
continue;
}
HT[i].ch=z;
HT[i].weight=w;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(;i<=m;++i) //初始化其余的结点
{
HT[i].ch='0';
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(i=n+1;i<=m;++i) //建立赫夫曼树
{
Select(HT,i-1,&p1,&p2);
HT[p1].parent=i;HT[p2].parent=i;
HT[i].lchild=p1;HT[i].rchild=p2;
HT[i].weight=HT[p1].weight+HT[p2].weight;
}
HC=(hfmcode)malloc((n+1)*sizeof(char *));
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=1;i<=n;++i) //给n个字符编码
{
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);
}
int main(){
char code[100],h[100],hl[100];
int n,i,j,k,l;
ifstream input_file; //文件输入输出流
ofstream output_file;
char choice,str[100];
hfmtree HT;
hfmcode HC;
cout<<"\n";
cout<<" "<<"计算机(3)班"<<" "<<"Q07620307"<<" "<<"XXX\n";
while(choice!='Q'&&choice!='q') //当choice的值不为q且不为Q时循环
{
cout<<" "<<"*************************赫夫曼编码/译码器*************************\n";
cout<<" "<<"I.Init"<<" "<<"E.Encoding"<<" "<<"D.Decoding"<<" "<<"Q.Exit\n";
cout<<"请输入您要操作的步骤:";
cin>>choice;
if(choice=='I'||choice=='i') //初始化赫夫曼树
{
cout<<"请输入字符个数:";
cin>>n;
hfmcoding(HT,HC,n);
for(i=1;i<=n;++i)
{
cout<<HT[i].ch<<":"<<HC[i]<<endl;
}
output_file.open("hfmTree.txt");
if(!output_file){
cout<<"can't oen file!"<<endl;
return 1;
}
for(i=1;i<=n;i++)
{
output_file<<"("<<HT[i].ch<<HC[i]<<")";
}
output_file.close();
cout<<"赫夫曼树已经创建完毕,并且已经放入hfmTree.txt文件中!"<<endl;
}
else if(choice=='E'||choice=='e') //进行编码,并将字符放入ToBeTran.txt,码值放入CodeFile.txt中
{
printf("请输入字符:");
gets(str);
output_file.open("ToBeTran.txt");
if(!output_file)
{
cout<<"can't oen file!"<<endl;
return 1;
}
output_file<<str<<endl;
output_file.close();
output_file.open("CodeFile.txt");
if(!output_file){
cout<<"can't oen file!"<<endl;
return 1;
}
for(i=0;i<strlen(str);i++){
for(j=0;j<=n;++j)
{
if(HT[j].ch==str[i])
{
output_file<<HC[j];
break;
}
}
}
output_file.close();
cout<<"\n";
cout<<"编码完毕,并且已经存入CodeFile.txt文件!\n";
input_file.open("CodeFile.txt"); //从CodeFile.txt中读入编码,输出在终端
if(!input_file)
{
cout<<"can't oen file!"<<endl;
return 1;
}
input_file>>code;
cout<<"编码码值为:"<<code<<endl;
input_file.close();
}
else if(choice=='D'||choice=='d') //读入CodeFile.txt中的编码进行译码,将译出来的字符放入Textfile.txt中
{
input_file.open("CodeFile.txt");
if(!input_file){
cout<<"can't oen file!"<<endl;
return 1;
}
input_file>>h;
input_file.close();
output_file.open("Textfile.txt");
if(!output_file)
{
cout<<"can't oen file!"<<endl;
return 1;
}
k=0;
while(h[k]!='\0') //先用编码中的前几个和字符的编码相比较,然后往后移
{
for(i=1;i<=n;i++){
l=k;
for(j=0;j<strlen(HC[i]);j++,l++){
hl[j]=h[l];
}
hl[j]='\0';
if(strcmp(HC[i],hl)==0)
{
output_file<<HT[i].ch;
k=k+strlen(HC[i]);
break;
}
}
}
output_file.close();
input_file.open("Textfile.txt");
if(!input_file){
cout<<"can't oen file!"<<endl;
return 1;
}
input_file>>h;
cout<<h<<endl;
input_file.close();
cout<<"译码结束,字符已经存入Textfile.txt文件中!"<<endl;
}
else if(choice=='Q'||choice=='q') //退出程序
{
exit(0);
}
else //如果选了选项之外的就让用户重新选择
{
cout<<"您没有输入正确的步骤,请重新输入!"<<endl;
}
cout<<endl;
}
return 0;
}