Question

哈夫曼编/译码器问题:C语言版的数据结构，我急啊！那位朋友帮帮忙，结果必需是我的问题的结果，不能有错啊

问题是：哈夫曼编/译码器问题：利用哈夫曼编码进行信息通讯可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码(复原)。设计要求如下：
一个完整的系统应具有以下功能：
(1)I:初始化 (Initialization)。从终端读入字符集大小n，及n个字符和m个权值，建立哈夫曼树。
(2)C:编码 (Coding)。利用已建好的哈夫曼树对正文进行编码，然后将结果输出。
(3)D:译码 (Decoding)。利用已建好的哈夫曼树编码后的代码进行译码。
[实现提示]
可以根据题目要求把程序划成3个模块，设计成菜单方式，每次执行一个模块后返回菜单。

Answer 1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//////////////////////////////////////////////////////////////////////////////
/*定义赫夫曼树结点的结构体变量，存放结点的权值、字符、双亲、坐孩子和右孩子*/
typedef struct{
int weight;
char ch; //增加一个域用于存放该节点的字符
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode; //指向赫夫曼编码的指针

//////////////////////////////////////////////////////////////////////////////
/*本程序用到的函数原型*/
void welcome(); //打印操作选择界面
void HuffmanCoding(HuffmanTree &,char *,int *,int);//建立赫夫曼树的算法
void select(HuffmanTree HT,int j,int *s1,int *s2); //从目前已建好的赫夫曼树中选择parent为0且weight最小的两个结点
void Init(); //输入n个字符及其对应的权值，根据权值建立哈夫曼树
void Coding(); //编码
void Decoding(); //译码
void Print_code(); //打印译码好的代码文件
void Print_tree(); //以凹凸表形式打印哈夫曼树
int Read_tree(HuffmanTree &); //从文件中读入赫夫曼树
void find(HuffmanTree &HT,char *code,char *text,int i,int m);//译码时根据01字符串寻找相应叶子节点的递归算法
void Convert_tree(unsigned char T[100][100],int s,int *i,int j);//将内存中的赫夫曼树转换成凹凸表形式的赫夫曼树

HuffmanTree HT; //全局变量，指向存放赫夫曼树的存储空间
int n=0; //全局变量，存放赫夫曼树叶子结点的数目

int main()
{
char select;

while(1)
{
welcome();
scanf("%c",&select);
switch(select)
{
case 'i':
case 'I':Init();break;
case 'c':
case 'C':Coding();break;
case 'd':
case 'D':Decoding();break;
case 'p':
case 'P':Print_code();break;
case 't':
case 'T':Print_tree();break;
case 'e':
case 'E':exit(1);
default :printf("Input error!\n");
}
getchar();
}
return 0;
}

void welcome() //打印操作选择界面
{
printf("*-----------------------------------------------------*\n");
printf("| What do you want to do? |\n");
printf("|-----------------------------------------------------|\n");
printf("| |\n");
printf("| I--------------------------Init the Huffman tree. |\n");
printf("| C--------------------------Code your file. |\n");
printf("| D--------------------------Decode the code. |\n");
printf("| P--------------------------Print the codefile. |\n");
printf("| T--------------------------Print the Huffman tree. |\n");
printf("| |\n");
printf("*-----------------------------------------------------*\n");
}

//////////////////////////////////////////////////////////////////////////////////////
/*初始化函数，输入n个字符及其对应的权值，根据权值建立哈夫曼树，并将其存于文件hfmtree中*/
void Init()
{
FILE *fp;
int i,n,w[52]; //w数组存放n个字符的权值
char character[52]; //存放n个字符
printf("\n输入字符个数 n:");
scanf("%d",&n); //输入字符集大小
printf("输入%d个字符及其对应的权值:\n",n);
for (i=0;i<n;i++)
{
char b=getchar();
scanf("%c",&character[i]);
scanf("%d",&w[i]); //输入n个字符和对应的权值
}
HuffmanCoding(HT,character,w,n); //建立赫夫曼树

if((fp=fopen("hfmtree.txt","w"))==NULL)
printf("Open file hfmtree.txt error!\n");
for (i=1;i<=2*n-1;i++)
{
if(fwrite(&HT[i],sizeof(HTNode),1,fp)!=1) //将建立的赫夫曼树存入文件hfmtree.txt中
printf("File write error!\n");
}
printf("\n建立赫夫曼树成功，已将其存于文件hfmtree.txt中\n");
fclose(fp);

}

///////////////////////////////////////////////////////////////////////////////////
//////建立赫夫曼树的算法///////////////////////////////////////////////////////////
void HuffmanCoding(HuffmanTree &HT,char *character,int *w,int n)
{
int m,i,s1,s2;
HuffmanTree p;
if(n<=1) return;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(p=HT+1,i=1;i<=n;++i,++p,++character,++w)
{p->ch=*character;p->weight=*w;p->parent=0;p->lchild=0;p->rchild=0;}
for(;i<=m;++i,++p) {p->ch=0;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;
}

}

///////////////////////////////////////////////////////////////////////////////
/*从HT[1]到HT[j]中选择parent为0且weight最小的两个结点，用s1和s2返回其序号*/
void select(HuffmanTree HT,int j,int *s1,int *s2)
{
int i;
//找weight最小的结点
for (i=1;i<=j;i++)
if (HT[i].parent==0)
{*s1=i;break;}
for (;i<=j;i++)
if ((HT[i].parent==0)&&(HT[i].weight<HT[*s1].weight))
*s1=i;
HT[*s1].parent=1;
//找weight次小的结点
for (i=1;i<=j;i++)
if (HT[i].parent==0)
{*s2=i;break;}
for (;i<=j;i++)
if ((HT[i].parent==0)&&(i!=*s1)&&(HT[i].weight<HT[*s2].weight))
*s2=i;

}

///////////////////////////////////////////////////////////////////////////////
/*对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中*/
void Coding()
{
FILE *fp,*fw;
int i,f,c,start;
char *cd;
HuffmanCode HC;
if(n==0)
n=Read_tree(HT);//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数

/////以下程序段求赫夫曼树中各叶子节点的字符对应的的编码，并存于HC指向的空间中
{
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);
}
/////////////////////////////////////////////////////////////////////////////////////

if((fp=fopen("tobetrans.txt","rb"))==NULL)
printf("Open file tobetrans.txt error!\n");
if((fw=fopen("codefile.txt","wb+"))==NULL)
printf("Open file codefile.txt error!\n");
char temp;
fscanf(fp,"%c",&temp); //从文件读入第一个字符
while(!feof(fp))
{
for(i=1;i<=n;i++)
if(HT[i].ch==temp) break; //在赫夫曼树中查找字符所在的位置
for(int r=0;HC[i][r]!='\0';r++) //将字符对应的编码存入文件
fputc(HC[i][r],fw);
fscanf(fp,"%c",&temp); //从文件读入下一个字符

}
fclose(fw);
fclose(fp);
printf("\n对文件hfmtree.txt编码成功,结果已存入codefile.txt中。\n\n");
}

/////////////////////////////////////////////////////////////////////////
/*将文件codefile中的代码进行译码，结果存入文件textfile中*/
void Decoding()
{
FILE *fp,*fw;
int m,i;
char *code,*text,*p;

if(n==0)
n=Read_tree(HT);//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数

if((fp=fopen("codefile.txt","rb"))==NULL)
printf("Open file codefile.txt error!\n");
if((fw=fopen("textfile.txt","wb+"))==NULL)
printf("Open file textfile.txt error!\n");
code=(char *)malloc(sizeof(char));
fscanf(fp,"%c",code); //从文件读入一个字符
for(i=1;!feof(fp);i++)
{
code=(char *)realloc(code,(i+1)*sizeof(char)); //增加空间
fscanf(fp,"%c",&code[i]); //从文件读入下一个字符
}
code[i-1]='\0';
/////////到此codefile.txt文件中的字符已全部读入，存放在code数组中
text=(char *)malloc(100*sizeof(char));
p=text;
m=2*n-1;
if(*code=='0')
find(HT,code,text,HT[m].lchild,m); //从根节点的左子树去找
else
find(HT,code,text,HT[m].rchild,m); //从根节点的右子树去找

for(i=0;p[i]!='\0';i++) //把译码好的字符存入文件textfile.txt中
fputc(p[i],fw);

fclose(fp);
fclose(fw);

printf("\n对codefile.txt文件译码成功，结果已存入textfile.txt文件。\n\n");
}

//////////////////////////////////////////////////////////////////////////////////////////////////////
/*将文件codefi1e以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码文件写入文件codeprint中。*/
void Print_code()
{
FILE *fp,*fw;
char temp;
int i;

if((fp=fopen("codefile.txt","rb"))==NULL)
printf("Open file codefile.txt error!\n");
if((fw=fopen("codeprint.txt","wb+"))==NULL)
printf("Open file codeprint.txt error!\n");

printf("\n文件codefi1e以紧凑格式显示如下:\n");
fscanf(fp,"%c",&temp); //从文件读入一个字符
for (i=1;!feof(fp);i++)
{
printf("%c",temp);
if(i%50==0) printf("\n");
fputc(temp,fw); //将该字符存入文件codeprint.txt中
fscanf(fp,"%c",&temp); //从文件读入一个字符
}
printf("\n\n此字符形式的编码已写入文件codeprint.txt中.\n\n");

fclose(fp);
fclose(fw);

}

//////////////////////////////////////////////////////////////////////////////////////////////////
/*将已在内存中的哈夫曼树以凹凸表形式显示在屏幕上，同时将此字符形式的哈夫曼树写入文件treeprint中。*/
void Print_tree()
{
unsigned char T[100][100];
int i,j,m=0;
FILE *fp;
if(n==0)
n=Read_tree(HT);//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数

Convert_tree(T,0,&m,2*n-1); //将内存中的赫夫曼树转换成凹凸表形式的树，存于数组T中

if((fp=fopen("treeprint.txt","wb+"))==NULL)
printf("Open file treeprint.txt error!\n");
printf("\n以凹凸表形式打印已建好的赫夫曼树：\n");
for(i=1;i<=2*n-1;i++)
{
for (j=0;T[i][j]!=0;j++)
{
if(T[i][j]==' ') {printf(" ");fputc(T[i][j],fp);}
else
{printf("%d",T[i][j]);fprintf(fp,"%d\n",T[i][j]);}
}
printf("\n");
}
fclose(fp);
printf("\n此字符形式的哈夫曼树已写入文件treeprint.txt中.\n\n");

}

//////////////////////////////////////////////////////////////////////////////////
/*从文件hfmtree.txt中读入赫夫曼树，返回叶子节点数*/
int Read_tree(HuffmanTree &HT)
{
FILE *fp;
int i,n;
HT=(HuffmanTree)malloc(sizeof(HTNode));
if((fp=fopen("hfmtree.txt","r"))==NULL)
printf("Open file hfmtree.txt error!\n");
for (i=1;!feof(fp);i++)
{
HT=(HuffmanTree)realloc(HT,(i+1)*sizeof(HTNode)); //增加空间
fread(&HT[i],sizeof(HTNode),1,fp); //读入一个节点信息
}
fclose(fp);
n=(i-1)/2;
return n;
}

////////////////////////////////////////////////////////////////
/*译码时根据01字符串寻找相应叶子节点的递归算法*/
void find(HuffmanTree &HT,char *code,char *text,int i,int m)
{

if(*code!='\0') //若译码未结束
{
code++;
if(HT[i].lchild==0&&HT[i].rchild==0) //若找到叶子节点
{

*text=HT[i].ch; //将叶子节点的字符存入text中

text++;
if((*code=='0'))
find(HT,code,text,HT[m].lchild,m); //继续从根节点的左子树找
else
find(HT,code,text,HT[m].rchild,m); //继续从根节点的右子树找
}
else //如果不是叶子节点
if(*code=='0')
find(HT,code,text,HT[i].lchild,m); //从该节点的左子树去找
else
find(HT,code,text,HT[i].rchild,m); //从该节点的右子树去找

}
else
*text='\0'; //译码结束

}

////////////////////////////////////////////////////////////////////////
/*将内存中的赫夫曼树转换成凹凸表形式的赫夫曼树*/
void Convert_tree(unsigned char T[100][100],int s,int *i,int j)
{
int k,l;
l=++(*i);
for(k=0;k<s;k++)
T[l][k]=' ';
T[l][k]=HT[j].weight;
if(HT[j].lchild)
Convert_tree(T,s+1,i,HT[j].lchild);
if(HT[j].rchild)
Convert_tree(T,s+1,i,HT[j].rchild);
T[l][++k]='\0';
}

为了您的安全，请只打开来源可靠的网址
打开网站 取消
来自: http://hi.baidu.com/laizhij/blog/item/4f3edefb6008321e6c22eb34.html

Answer 2

同样期待高手的解答

Answer 3

你哭吧.........