哈夫曼树编译器实验心得体会
⑴ 哈夫曼树
这是我们的作业题，自己写 的……（可能输入的格式跟你要的不一致，自己改一下）
如果有什么不懂的就问我，我可以把其中所有相关的文件发给你 ^^
注：1、 初始化创建哈夫曼树有三种选择，其中选择编译课本测试数据时和编译源文件是，调用的输入文件分别是：test.txt和input.txt；字母的哈夫曼编码都保存在文件：hmfTree.txt；
2、 用户自定义模式下，需要编码的文件内容保存在ToBeTran.txt中；课本测试数据和源文件代码分别保存在course.txt和sorse.txt中，在（1）中选择不同的选项，则在编码时调用相应的文件进行编码，编码结果保存在文件CodeFile.txt中。
3、 文件译码时，调用文件CodeFile.txt进行译码，得到的结果保存在文件TextFile.txt中。
4、 打印代码文件：调用CodeFile.txt，结果显示在终端并保存在文件CodePrin.txt中。
5、 打印哈夫曼树：用凹入表形式把哈夫曼树显示在终端，同时将它保存在文件TreePrint..txt中。
#include <stdio.h>
#include<malloc.h>
#include <string.h>
#include<fstream>
#include<iostream>
using namespace std;
typedef struct {
unsigned int weight;
char ch1;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;
typedef struct {
char ch;
char code[7];
}codenode,*code;
void select(HuffmanTree HT,int n,int & s1,int &s2){ //从哈夫曼树中选择出最小的两个节点
for(int i=1;i<=n;i++)
if(!HT[i].parent){
s1=i; break;
}
for(i++;i<=n;i++)
if(!HT[i].parent){
s2=i; break;
}
if(HT[s1].weight-HT[s2].weight){
int temp; temp=s1; s1=s2; s2=temp;
}
for(i=1;i<=n;i++) //对数组进行遍历，寻找最小的两个节点
if(!HT[i].parent){
if(HT[i].weight<HT[s1].weight){
s2=s1; s1=i;
}
else if(HT[i].weight<HT[s2].weight&&i!=s1)
s2=i;
}
}
void prin(){ //终端输出选择菜单
cout<<"----------------------------------------------------\n\n"
<<" ∣ I---创建哈夫曼树 ∣\n"
<<" ∣ ∣\n"
<<" ∣ E---文件编码 ∣\n"
<<" ∣ ∣\n"
<<" ∣ D---文件译码 ∣\n"
<<" ∣ ∣\n"
<<" ∣ P---打印代码文件 ∣\n"
<<" ∣ ∣\n"
<<" ∣ T---印哈夫曼树 ∣\n"
<<" ∣ ∣\n"
<<" ∣ O---哈夫曼树的存储结构 ∣\n"
<<" ∣ ∣\n"
<<" ∣ Q---退出 ∣\n"
<<"\n-----------------------------------------------------\n\n";
printf("选择菜单功能选项：");
}
void output (HuffmanTree th,int n){ //输出哈夫曼树的存储结构
int i=0;
cout<<"序号"<<" "<<"字符"<<" "<<"双亲"<<" "<<"左孩子"<<" "<<"右孩子"<<" "<<"权值"<<endl;
for(;i<2*n-1;i++){
th++;
cout<<i<<" "<<th->ch1<<" "<<th->parent<<" "<<th->lchild<<" "<<th->rchild<<" "<<th->weight <<endl;
}
}
void initial(HuffmanTree &HT,HuffmanCode &HC,int w[],int &n,char ch[],int &k){ //创建哈夫曼树
cout<<"----------------------------------------------------\n\n"
<<" ∣ 1---自定义 ∣\n"
<<" ∣ ∣\n"
<<" ∣ 2---编码课本测试数据 ∣\n"
<<" ∣ ∣\n"
<<" ∣ 3---编码源程序 ∣\n"
<<"\n-----------------------------------------------------\n\n";
printf("选择菜单功能选项：");
scanf("%d",&k);
if(k==1){
printf("输入需要编码的字符总数: ");
scanf("%d",&n);
printf("\n输入需要编码字符的权值:\n");
for(int d=0;d<n;d++) {
scanf("%d",&w[d]);
}
printf("\n输入需要编码的字符串: ");
scanf("%s",ch);
}
else if(k==2){
ifstream fin2 ("test.txt");
fin2>>n;
for(int d=0;d<n;d++)
fin2>>w[d];
fin2>>ch;
fin2.close();
}
else if(k==3){
ifstream fin1 ("input.txt");
fin1>>n;
for(int d=0;d<n;d++)
fin1>>w[d];
fin1>>ch;
fin1.close();
}
if(n<=1)
return;
int s1,s2,i,num=2*n-1;
HuffmanTree p;
HT=(HuffmanTree)malloc((num+1)*sizeof(HTNode));
for(p=HT+1,i=1;i<=n;i++,p++){
p->weight=w[i-1]; p->lchild=0; p->parent=0; p->rchild=0; p->ch1 =ch[i-1];
}
for(;i<=num;p++,i++){
p->weight=0; p->lchild=0; p->parent=0; p->rchild=0; p->ch1 ='$';
}
for(i=n+1;i<=num;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 *));
char * temp=(char *)malloc(n*sizeof(char));
temp[n-1]='\0';
for(i=1;i<=n;i++){
int start=n-1;
for(int f=HT[i].parent,h=i;f;h=f,f=HT[f].parent)
if(HT[f].lchild==h)
temp[--start]='0';
else
temp[--start]='1';
HC[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(HC[i],&temp[start]);
}
ofstream fout ("hfmTree.txt");
fout<<ch<<endl;
for(int j=1;j<=n;j++)
fout<<HC[j]<<endl;
fout.close();
free(temp);
}
void encoding(int n,int select){ //编码：对文件TobeTran.txt进行译码
char a[100],b[100][20];
ifstream fin ("hfmTree.txt");
fin>>a;
for(int j=0;j<n;j++) fin>>b[j];
fin.close();
ifstream fin1 ("course.txt");
ifstream fin2 ("sorse.txt");
ifstream fin3 ("ToBeTran.txt");
char s[1000];
if(select==3)
fin2>>s;
else if(select==2)
fin1>>s;
else fin3>>s;
ofstream fout ("CodeFile.txt");
while(s[0]!='\0'){
for(int i=0;s[i]!='\n'&&s[i]!='\0'&&i<30;i++ ){
for(int g=0;a[g]!=s[i];g++) ;
fout<<b[g];
}
fout<<'\n';
if(select==3)
fin2>>s;
else if(select==2)
fin1>>s;
else fin3>>s;
}
fin3.close();
fin2.close();
fin1.close();
fout.close();
}
void decoding(HuffmanTree ht,int n){ //译码：对CodeFile.txt文件进行译码
ifstream fin ("CodeFile.txt");
ofstream fout ("TextFile.txt");
char s[500];
fin>>s;
HuffmanTree head=ht+2*n-1;
int i=0;
while(s[0]!='\0'){
while(s[i]!='\0'){
if(s[i]=='1') head=ht+head->rchild;
else if(s[i]=='0') head=ht+head->lchild;
if((head->lchild)==0&&(head->rchild) ==0) {
fout<<(head->ch1);
head=ht+2*n-1;
}
i++;
}
fout<<' ' ;
i=0;
fin>>s;
}
fin.close();
fout.close();
}
void Print(){ //打印代码文件，显示在终端，每行50个代码
ifstream fin ("CodeFile.txt");
char s[2000];
int j=0;
int i=1;
fin>>s;
ofstream fout ("CodePrin.txt");
while(s[0]!='\0'){
for(;s[j]!='\0';j++){
printf("%c",s[j]);
fout<<s[j];
if(i%50==0){
fout<<endl;
printf("\n");
}
i++;
}
j=0;
fin>>s;
}
fin.close();
printf("\n");
fout.close();
}
void printTree( HuffmanTree node,HuffmanTree node1, int level ) { //打印哈夫曼树形（在参数的传递上，是文科给自己提出的意见才很好的解决了之后的操作难题^^）
if( node == NULL ) return;
if( node1->rchild!=0) {
printTree( node,node+node1->rchild, level + 1 );
}
fstream fout ;
fout.open ("TreePrint.txt",ios::in | ios::out|ios::ate);//这个挺有用的：在文件末尾加入内容
for( int i = 0; i < level; i++ ) {
fout<<"|……";
printf( "……");
}
fout<<node1->weight<<endl;
printf( "%d\n", node1->weight );
if( node1->lchild!=0 ) {
printTree( node,node+node1->lchild, level + 1 );
}
fout.close();
}
void main(){
int select;
int n;
char ch[100];
int w[100];
HuffmanTree HT=NULL;
HuffmanCode hc=NULL;
prin();
char c='I';
scanf("%c",&c);
while(c!='Q'){
switch(c){
case 'I':
initial(HT,hc,w,n,ch,select);
prin();
break;
case 'E':
encoding(n,select);
prin();
break;
case 'D':
decoding(HT,n);
prin();
break;
case 'P':
Print();
prin();
break;
case 'T':
printTree(HT,HT+2*n-1,1);
prin();
break;
case 'O':
output(HT,n);
prin();
break;
}
scanf("%c",&c);
}
}
注：
input.txt文件中保存一下数据：
88
56
26
89
45
62
78
61
13
20
29
89
46
51
25
86
123
20
10
9
57
6
1
57
62
2
37
61
15
19
89
91
2
8
19
49
67
18
19
64
35
67
61
61
84
20
30
50
84
19
28
84
67
31
67
29
20
10
56
56
12
23
56
23
45
85
16
29
94
68
35
97
58
21
29
3
94
58
16
21
64
29
84
64
59
19
48
37
186
!,./;':[]\1234567890-=+)(*&%$#<>"|{}
⑵ 哈夫曼编/译码器问题:C语言版的数据结构，我急啊！那位朋友帮帮忙，结果必需是我的问题的结果，不能有错啊
#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..com/laij/blog/item/4f3edefb6008321e6c22eb34.html
⑶ 哈夫曼编/译码器的问题：请求高手帮帮忙，课程设计用的，自己写的错误太多了，万分感谢，c描述。拜托了
以下程序在c-free下测试成功。
算法参考 数据结构（C语言版）——清华大学出版社
请根据题目具体要求进行修改！有问题找我……
#include"stdio.h"
#include"stdlib.h"
#include"string.h"
typedef char ElemType;
typedef char** HuffmanCode;
typedef int Status;
typedef struct
{
ElemType elem;
unsigned int m_weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef struct weight
{
char elem;
unsigned int m_weight;
}Weight;
void HuffmanCoding(HuffmanTree *,HuffmanCode *,Weight *,int);
void Select(HuffmanTree,int,int *,int *);
void OutputHuffmanCode(HuffmanTree,HuffmanCode,int);
void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,Weight *w,int n)
{
//w存放n个字符的权值（均>0），构造Huffman树HT，并求出n个字符的Huffman编码HC
int i,m,s1,s2,start,c,f;
char *cd;
HuffmanTree p;
if(n<=1) return;
m=2*n-1;
(*HT)=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0号单元未用
for(p=HT,i=1;i<=n;++i,++p,++w)
{
(*HT)[i].elem=w[i-1].elem;
(*HT)[i].m_weight=w[i-1].m_weight;
(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0;
}
for(;i<=m;++i,++p)
{
(*HT)[i].elem='0';
(*HT)[i].m_weight=(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0;
}
for(i=n+1;i<=m;++i)
{
//在HT[1...i-1]选择parent为0且weight最小的两个结点，其序号分别为s1和s2
Select(*HT,i-1,&s1,&s2);
(*HT)[s1].parent=i;(*HT)[s2].parent=i;
(*HT)[i].lchild=s1;(*HT)[i].rchild=s2;
(*HT)[i].m_weight=(*HT)[s1].m_weight+(*HT)[s2].m_weight;
}
//从叶子到根逆向求每个字符的Huffman编码
(*HC)=(HuffmanCode)malloc(n*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]); //从cd复制编码到HC
}
}
void Select(HuffmanTree HT,int n,int *s1,int *s2)
{
int i;
(*s1)=(*s2)=0;
for(i=1;i<=n;i++)
{
if(HT[i].m_weight<HT[(*s2)].m_weight&&HT[i].parent==0&&(*s2)!=0)
{
if(HT[i].m_weight<HT[(*s1)].m_weight)
{
(*s2)=(*s1);
(*s1)=i;
}
else
(*s2)=i;
}
if(((*s1)==0||(*s2)==0)&&HT[i].parent==0)
{
if((*s1)==0) (*s1)=i;
else
if((*s2)==0)
{
if(HT[i].m_weight<HT[(*s1)].m_weight)
{
(*s2)=(*s1);
(*s1)=i;
}
else (*s2)=i;
}
}
}
if((*s1)>(*s2))
{
i=(*s1);
(*s1)=(*s2);
(*s2)=i;
}
}
void OutputHuffmanCode(HuffmanTree HT,HuffmanCode HC,int n)
{
int i;
printf("\nnumber---element---weight---huffman code\n");
for(i=1;i<=n;i++)
printf(" %d %c %d %s\n",i,HT[i].elem,HT[i].m_weight,HC[i]);
}
Status main(void)
{
HuffmanTree HT;
HuffmanCode HC;
Weight *w;
char c;
int i,n;
int wei;
printf("input the tatol number of the Huffman Tree:" );
scanf("%d",&n);
w=(Weight *)malloc(n*sizeof(Weight));
for(i=0;i<n;i++)
{
printf("input the element & its weight:");
scanf("%1s%d",&c,&wei);
w[i].elem=c;
w[i].m_weight=wei;
}
HuffmanCoding(&HT,&HC,w,n);
OutputHuffmanCode(HT,HC,n);
return 1;
}
⑷ 哈夫曼编码的译码过程的大致思路是什么（不要代码）
哈夫曼树和字符编码对应你都弄完了，得到是如a :01 b :101对应关系，通过这个关系直接将像“asdsdfdfg”直接转换为“01110101”这样二进制编码。译码的时候，读取二进制编码，先读取一位，然后在关系表中查找该二进制数对应的字符，如果没有找到，继续读取二位，然后继续在关系表中查找该二位二进制对应的字符。如此循环，知道找到字符位置，然后将二进制数替换为相应的字符，知道所有的数都替换完为止。
⑸ 哈夫曼树编码如何保证通信过程中以及译码的时候顺序不变呢
知道了编码用的哈夫曼树后。从根结点出发，逐个读入接收电文中的二进制码；然后又重新从根结点开始继续译码，直到二进制电文结束。 Huffman 编码 一
⑹ 题目：哈夫曼编码，译码系统
/* 哈夫曼编码*/
#include "graphics.h"
#include "stdlib.h"
#include "Stdio.h"
#include "Conio.h"
#define MAX 53
char bmfile[10];
char a[100];
typedef struct
{char c,s[10];}MM;
MM mm[53];
typedef struct /*以数组存储哈夫曼树时的结点类型*/
{char ch;
int w,lcd,rcd,pt; /*权值、左孩子、右孩子、双亲*/
}HuffNode;
HuffNode Hm[MAX];
typedef struct CNode /*Auffman编码的结点类型*/
{ char c;
struct CNode *prv;
}CODE;
CODE *cd;
wjbm1 (char a[])/*从文件中读取要进行编码的字符*/
{FILE *fp3;
char ch;
int i=0,n=0,k,t,m;
/*printf("\n输入要编码的文件名：");
scanf("%s",bmfile);*/
if((fp3=fopen("bmfile.txt","r"))==NULL)
{printf("\n文件不存在");
exit(0);}
while(!feof(fp3))
a[i++]=fgetc(fp3);
a[i]='\0';
for(i=0;a[i]!='\0';i++)
{if(a[i]>='A'&&a[i]<='Z') {Hm[a[i]-65].ch=a[i]; Hm[a[i]-65].w++;}
if(a[i]>='a'&&a[i]<='z') {Hm[a[i]-71].ch=a[i]; Hm[a[i]-71].w++;}
if(a[i]==' ') {Hm[52].ch=' ';Hm[52].w++;}
}
for(i=0;i<53;i++)
if(Hm[i].w!=0)
{ Hm[n].ch=Hm[i].ch;
Hm[n].w=Hm[i].w;
Hm[n].lcd=-1;
Hm[n].rcd=-1;
Hm[n].pt=-1;
n++;}
fclose(fp3);
return n;
}
zfbm1(char a[])
{
int n=0,i;
gets(a);
for(i=0;a[i]!='\0';i++)
{if(a[i]>='A'&&a[i]<='Z') {Hm[a[i]-65].ch=a[i]; Hm[a[i]-65].w++;}
if(a[i]>='a'&&a[i]<='z') {Hm[a[i]-71].ch=a[i]; Hm[a[i]-71].w++;}
if(a[i]==' ') {Hm[52].ch=' ';Hm[52].w++;}
}
printf("\n叶字信息(字符、权值):");
for(i=0;i<53;i++)
if(Hm[i].w!=0)
{printf("(%c,%d)",Hm[i].ch,Hm[i].w);
Hm[n].ch=Hm[i].ch;
Hm[n].w=Hm[i].w;
Hm[n].lcd=-1;
Hm[n].rcd=-1;
Hm[n].pt=-1;
n++;}
return n;
}
charTJ()
{char c;
int i;
printf("\n1-从文件中读取字符生成树;2-从键输入字母生成树;3-退出;\n");
while(1)
switch(c=getch())
{case '1':wjbm1(a);return;
case '2':puts("\n输入字母");zfbm1(a);return;
case '3':return;
default:printf("\n输入无效,重新输入");scanf("%d",&c);}
}
void HuffmanCode(int n) /*哈夫曼编码。n为哈夫曼树的叶子数*/
{ int i,k,t;
CODE *p,*h;
cd=(CODE*)malloc(sizeof(CODE)*n);/*用于存储每个叶子的编码(链栈)*/
for(i=0;i<n;i++) /*搜索第i+1个叶子*/
{ k=i;h=0;
while((Hm+k)->pt>=0)
{ if((Hm+(Hm+k)->pt)->lcd==k)t=0;else t=1;
p=(CODE*)malloc(sizeof(CODE));
p->c=48+t;p->prv=h;h=p;
k=(Hm+k)->pt;
}
cd[i].prv=h;
}
}
void dispCodes(int n) /*显示*/
{ int i,j=0;
CODE *p;
for(i=0;i<n;i++)
{ p=cd[i].prv;
/*printf("\n%c:",Hm[i].ch); */
mm[i].c=Hm[i].ch;
j=0;
while(p)
{{/*printf("%c",p->c);*/ mm[i].s[j++]=p->c;}
mm[i].s[j]='\0';
p=p->prv;
}
}
puts("\n显示结果：");
for(i=0;i<n;i++)
printf("(%c,%s) ",mm[i].c,mm[i].s);
dispCode(n);
}
dispCode(int n) /*将各字符的编码存入数组mm*/
{ int i,j;
CODE *p;
for(i=0;i<n;i++)
{ p=cd[i].prv;
/*printf("\n%c:",Hm[i].ch); */
mm[i].c=Hm[i].ch;
j=0;
while(p)
{{/*printf("%c",p->c);*/ mm[i].s[j++]=p->c;}
mm[i].s[j]='\0';
p=p->prv;
} }
}
Huffmanshu(int n) /*显示哈夫曼树的字符编码*/
{int i;
HuffmanCode(n);
dispCodes(n);
}
wjbm(int n)
{FILE *fp4;
char ch;
int i=0,j;
wjbm1(a);
HuffmanCode(n);
dispCode(n);
fp4=fopen("stfile.txt","w");
for(i=0;a[i]!='\0';i++)
{for(j=0;j<n;j++)
if(a[i]==mm[j].c) fputs(mm[j].s,fp4);
}
puts("结果已写入文件");
fclose(fp4);
}
zfbm(int n)
{int i,j;
puts(a);
HuffmanCode(n);
dispCode(n);
printf("译码:");
for(i=0;a[i]!='\0';i++)
{for(j=0;j<n;j++)
if(a[i]==mm[j].c) printf("%s",mm[j].s);}
}
Huffmanbm(int n,HuffNode Hm[])/*哈夫曼编码*/
{
int k;
char ch;
printf("\n1-结果输出到文件；2-结果显示在屏幕;3-退出;\n");
while(1)
switch(ch=getch())
{case '1':wjbm(n);return 0;
case '2':printf("\n源码:");zfbm(n);return;
case '3':return 0;
default:printf("输入无效,重新输入");scanf("%d",&ch);}
}
wjjm(int n,char a[])
{FILE *fp1,*fp2;
char ch;
int i=0,k,t,m;
if((fp1=fopen("jmfile.txt","r"))==NULL)
{printf("\n文件不存在");
exit(0);}
fp2=fopen("st.txt","w");
while(!feof(fp1)) a[i++]=fgetc(fp1);
a[i]='\0'; k=i;
printf("\n1-结果输出到文件；2-结果显示在屏幕;3-退出;\n");
t=2*n-2;
while(1)
switch(ch=getch())
{case '1':
for(i=0;i<=k;)
{ if(a[i]=='0')
if(Hm[t].lcd==-1) { putc(Hm[t].c,fp2); t=2*n-2;}else {t=Hm[t].lcd;i++;}
else
if(Hm[t].rcd==-1) { fputc(Hm[t].c,fp2); t=2*n-2;}else {t=Hm[t].rcd;i++;}
} return;
case'2':
for(i=0;i<=k;)
{ if(a[i]=='0')
if(Hm[t].lcd==-1) { printf("%c",Hm[t].c); t=2*n-2;}else {t=Hm[t].lcd;i++;}
else
if(Hm[t].rcd==-1) { printf("%c",Hm[t].c); t=2*n-2;}else {t=Hm[t].rcd;i++;}
} return;
case'3':return 0;
}
fclose(fp1);
fclose(fp2);
}
zfjm(int n,char a[])/*对输入的字符进行解码*/
{int i,t,k;
printf("\n输入要解码的信息:");
scanf("%s",a);
k=strlen(a);
t=2*n-2;
printf("生成源代码：");
for(i=0;i<=k;)
{ if(a[i]=='0')
if(Hm[t].lcd==-1) { printf("%c",Hm[t].c); t=2*n-2;}else {t=Hm[t].lcd;i++;}
else
if(Hm[t].rcd==-1) { printf("%c",Hm[t].c); t=2*n-2;}else {t=Hm[t].rcd;i++;}
}
}
void Huffmanjm(int n,HuffNode Hm[]) /*哈夫曼解码。n为哈夫曼树的叶子数*/
{ int m=n;
char *a,ch;
printf("\n1-对文件解码；2-对字符解码;3-退出;\n");
while(1)
switch(ch=getch())
{case '1':wjjm(m,a);return 0;
case '2':zfjm(m,a);return;
case '3':return 0;
}
}
void HuffmanTree() /*生成哈夫曼树*/
{ int i,j,x,y,n;
char c;
n=charTJ();
for(i=0;i<n-1;i++)
{ x=0;
while((Hm+x)->pt>=0)x++; /*搜索第一个未处理的结点*/
y=x+1;
while((Hm+y)->pt>=0)y++; /*搜索第二个未处理的结点*/
j=y;
if((Hm+x)->w>(Hm+y)->w){j=y;y=x;x=j;}
for(j=j+1;j<n+i;j++) /*搜索两个未处理且权值最小的结点*/
{ if((Hm+j)->pt<0&&(Hm+j)->w<(Hm+x)->w) {y=x;x=j;}
else
if((Hm+j)->pt<0&&(Hm+j)->w<(Hm+y)->w) y=j;
}
(Hm+x)->pt=n+i;(Hm+y)->pt=n+i;(Hm+n+i)->w=(Hm+x)->w+(Hm+y)->w;
(Hm+n+i)->lcd=x;(Hm+n+i)->rcd=y;(Hm+n+i)->pt=-1;
}
puts("\n1-显示字符的编码;2-编码;3-解码;4-退出;");
while(1)
switch(c=getch())
{case '1':Huffmanshu(n);break;
case '2':Huffmanbm(n,Hm);break;
case '3':Huffmanjm(n,Hm);break;
case '4':return;
}
}
int main()
{ char c;
gotoxy(29,1);
puts("文件编码解码系统");
window(1,3,80,25);
HuffmanTree();
getch();
clrscr();
}
⑺ 哈夫曼编码/译码器
注释非常详细，希望对你有所帮助！
#ifndef Huffman_Tree_h
#define Huffman_Tree_h
#endif
#include <stdio.h>
typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode, * HuffmanTree; //存储赫夫曼树的结点类型
typedef char * * HuffmanCode; //用于存储字符集中各个字符相应的赫夫曼编码
void strcpy(char *S1,char *S2){ //将字符串S2复制到S1
int i = 0;
while( S2[i] != '\0' ){
S1[i] = S2[i];
i++;
}
S1[i] = '\0';
}
void Select(HuffmanTree HT,int t,int &s1,int &s2){ //在HT[1]到HT[t-1]中找出权值最小的两个S1和S2
int i = 1;
s1 = s2 = 0;
HT[0].weight = 65535;
while( i <= t ){ //遍历查找权值最小的结点S1
if( HT[i].parent == 0 && HT[i].weight < HT[s1].weight )
s1 = i;
i++;
}
i = 1;
while( i <= t ){ //遍历查找除S1外权值最小的结点S2
if( i != s1 && HT[i].parent == 0 && HT[i].weight < HT[s2].weight )
s2 = i;
i++;
}
}
int HuffmanCoding( HuffmanTree &HT,HuffmanCode &HC,int *w,int n){ //根据各个字符的权值构造赫夫曼树HT，将对应的赫夫曼编码存储在HC中
int s1,s2,m,i,start;
unsigned int c,f;
HTNode * p;
char *cd;
if( n <= 1 ) return 0;
m = 2 * n - 1; //赫夫曼树的总结点树为m
HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode)); //申请存储赫夫曼树的空间
for(p = HT + 1, i = 1; i <= n; ++i, ++p, ++w){ //将各个叶子结点的weight赋以相应的权值，parent,lchild,rchild均赋为0
p->weight = *(w+1);
p->parent = p->lchild = p->rchild = 0;
}
for( ; i <= m; ++i, ++p ){ //将各个非叶子结点的weight,parent,lchild,rchild均赋为0
p->weight = p->parent = p->lchild = 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; //编码在数组cd[]中的最前位置
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)); //为第i个字符编码分配空间
strcpy(HC[i], &cd[start]); //将cd[]数组的start位置到n-1位置复制给HC[i]
}
free(cd); //释放空间
return 1;
}
以上为第一部分
#include <stdio.h>
#include <stdlib.h>
#include "Huffman_Tree.h"
#define Yes 1 //当程序已经调用过初始化赫夫曼树的InitHuff_T()函数，或已从htfTree文件读取过，则将Init_Mode置为Yes，否则为No
#define No 0
void InitHuff_T( HuffmanTree &HT, HuffmanCode &HC, char ch[],int &n ){ //初始化赫夫曼数，要求用户输入字符和相应权值
int i = 1,w[100],tem,j;
char a[20];
FILE *save;
printf("请输入编码字符集的大小n:");
scanf("%d",&n); //获取用户输入的字符集个数
while( i <= n ){ //获取用户输入的字符和相应权值，分别存储在ch[]和w[]数组中
printf("请输入第%d个字符和该字符的权值w:",i);
fflush(stdin);
scanf("%c%d",&ch[i],&w[i]);
i++;
}
ch[i] = '\0';
HuffmanCoding(HT,HC,w,n); //根据用户的输入，生成赫夫曼数及各个字符相应的赫夫曼编码，分别存在HT树和HC中
if(( save = fopen("htfTree","w")) == NULL ){ //打开用于存储赫夫曼树的文件
printf("Open file fail......\n");
exit(0);
}
tem = n; //接下来的14行是将字符集大小转换成字符形式写入到文件中
j = 0;
while( tem != 0 ){
tem = tem / 10;
j++;
}
tem = n;
a[j] = '\0';
while( tem != 0 ){
a[j - 1] = (char)(tem % 10 + 48);
tem = tem / 10;
j--;
}
fputs(a,save);
printf("%d\n",n); //向屏幕输出字符集大小n
fputc('\n',save);
for( i = 1; i <= n; i++ ){ //分别向文件和屏幕输出各个字符和相应的赫夫曼编码
fputc(ch[i],save); printf("%c\t",ch[i]);
fputc('\t',save);
fputs(HC[i],save); printf("%s\n",HC[i]);
fputc('\n',save);
}
for(i = 1; i <= 2 * n - 1; i++ ){ //将赫夫曼树各个结点的parent,lchild,rchild分别写入到文件中
tem = HT[i].parent; //将i结点的parent转换成字符并写入到文件中
if(tem == 0){
fputc(tem + 48,save);
fputc(' ',save);
}
else{
j = 0;
while( tem != 0 ){
tem = tem / 10;
j++;
}
tem = HT[i].parent;
a[j] = '\0';
while( tem != 0 ){
a[j - 1] = (char)(tem % 10 + 48);
tem = tem / 10;
j--;
}
fputs(a,save);
fputc(' ',save);
}
tem = HT[i].lchild; //将i结点的lchild转换成字符并写入到文件中
if(tem == 0){
fputc(tem + 48,save);
fputc(' ',save);
}
else{
j = 0;
while( tem != 0 ){
tem = tem / 10;
j++;
}
tem = HT[i].lchild;
a[j] = '\0';
while( tem != 0 ){
a[j - 1] = (char)(tem % 10 + 48);
tem = tem / 10;
j--;
}
fputs(a,save);
fputc(' ',save);
}
tem = HT[i].rchild; //将i结点的rchild转换成字符并写入到文件中
if(tem == 0){
fputc(tem + 48,save);
fputc('\n',save);
}
else{
j = 0;
while( tem != 0 ){
tem = tem / 10;
j++;
}
tem = HT[i].rchild;
a[j] = '\0';
while( tem != 0 ){
a[j - 1] = (char)(tem % 10 + 48);
tem = tem / 10;
j--;
}
fputs(a,save);
fputc('\n',save);
}
}
fclose(save);
}
void Encoding(HuffmanTree &HT, HuffmanCode &HC, char ch[]){ //根据赫夫曼编码将用户指定的文件中的字符编成相应的编码,并将所得编码存储到用户指定文件
FILE *ToBeTran,*CodeFile;
char ToBeTran_Name[100],CodeFile_Name[100]; //存储用户指定文件的文件名
int i;
char c;
printf("请输入所要进行编码的文件的文件名:");
scanf("%s",ToBeTran_Name); //获得所要进行编码的文件的文件名
if(( ToBeTran = fopen(ToBeTran_Name,"r")) == NULL ){ //打开文件
printf("Open file fail......\n");
exit(0);
}
printf("请输入编码后编码表示的信息所存储到的文件的文件名:");
scanf("%s",CodeFile_Name); //获得编码后编码表示的信息所存储到的文件的文件名
if(( CodeFile = fopen(CodeFile_Name,"w")) == NULL ){ //打开文件
printf("Open file fail......\n");
exit(0);
}
c = fgetc(ToBeTran); //从文件读取一个字符
while( c != EOF ){ //对文件中的各个字符进行编码，直至文件结尾
i = 1;
while( c != ch[i] && ch[i] != '\0' ) //在ch[]数组中查找从文件读取的字符
i++;
if(ch[i] == '\0'){ //未找到，c不在ch[]数组中，c无法被识别，程序出错，退出
printf("字符%c无法识别，程序将退出。\n",c);
exit(0);
}
fputs(HC[i],CodeFile); //若找到，则将c相应的赫夫曼编码写入到文件中
printf("%s",HC[i]); //将c相应的赫夫曼编码输出到屏幕
c = fgetc(ToBeTran); //读入文件中的下一个字符
}
printf("\n");
fclose(ToBeTran);
fclose(CodeFile);
}
void Decoding(HuffmanTree HT, char ch[] , int n){ //对指定的存储由赫夫曼编码表示的信息的文件进行译码，翻译成相应的字符表示，并存储到指定文件
int p,i = 1;
char code[1000],c;
char CodeFile_Name[100],TextFile_Name[100]; //存储用户指定文件的文件名
p = 2 * n - 1;
FILE *CodeFile,*TextFile;
printf("请输入所要译的文件名:");
scanf("%s",CodeFile_Name); //获得所要译的文件的文件名
if(( CodeFile = fopen("CodeFile","r")) == NULL ){ //打开文件
printf("Open file fail......\n");
exit(0);
}
printf("请输入译后的字符存储到的文件的文件名:");
scanf("%s",TextFile_Name); //获得译后的字符存储到的文件的文件名
if(( TextFile = fopen(TextFile_Name,"w")) == NULL ){ //打开文件
printf("Open file fail......\n");
exit(0);
}
c = fgetc(CodeFile);
while( c != EOF ){
code[i] = c;
i++;
c = fgetc(CodeFile);
}
code[i] = '\0'; //从文件读取字符，存储在code[]数组中
i = 1;
while ( code[i] != '\0' && p != 0 ){ //对数组code[]中的赫夫曼编码进行译码
if ( code[i] == '0' )
p=HT[p].lchild; //进入左分支
else
p = HT[p].rchild; //进入右分支
if (!HT[p].lchild&& !HT[p].rchild){ //进入叶子结点
fputc(ch[p], TextFile); //将相应的字符写入到文件中
printf("%c",ch[p]); //将相应的字符输出到屏幕
p = 2 * n - 1; //重新从树根出发进行译码
}
i++;
}
printf("\n");
}
void ReadHuff_T( HuffmanTree &HT, HuffmanCode &HC, char ch[], int &n){ //从文件读取赫夫曼树
FILE *htfTree;
char c[100],ch1;
int i,j,t;
if(( htfTree = fopen("htfTree","r")) == NULL ){ //打开存有赫夫曼树信息的文件
printf("Open file fail......\n");
exit(0);
}
fgets(c,10,htfTree); //获取赫夫曼树叶子结点个数的字符串表示形式
i = 0; //以下6行将字符串形式转换成整数形式
while( c[i] != '\n' )
i++;
n = 0;
for( j = 0; j < i; j++ )
n = 10 * n + c[j] - '0'; //求出叶子结点数n
HC = (HuffmanCode)malloc((n + 1) * sizeof(char *)); //申请HC空间
HT = (HuffmanTree)malloc((2 * n) * sizeof(HTNode)); //申请赫夫曼树存储空间
i = 1;
while( i <= n ){
ch[i] = fgetc(htfTree); //读取字符集中的一个字符
HC[i] = (char *)malloc((10)*sizeof(char)); //申请用于存储读取到的字符集中的字符的赫夫曼编码的空间
fgetc(htfTree); //将‘\t’输出
ch1 = fgetc(htfTree); //读取赫夫曼编码，存储在相应的HC[i][]数组里
int j = 0;
while( ch1 != '\n' ){
HC[i][j] = ch1;
j++;
ch1 = fgetc(htfTree);
}
HC[i][j] = '\0';
i++;
}
ch[i] = '\0';
i = 0;
while( i < 2 * n - 1 ){ //读取赫夫曼树的各个结点的parent,lchild,rchild.并赋值到赫夫曼树HT中
ch1 = fgetc(htfTree); //读取parent的字符串形式,存储在c[]中，并将其转换成整数形式，赋给HT[i].parent
j = 0;
while( ch1 != ' ' ){
c[j] = ch1;
j++;
ch1 = fgetc(htfTree);
}
HT[i+1].parent = 0;
for( t = 0; t < j; t++ )
HT[i+1].parent = 10 * HT[i+1].parent + c[t] - '0';
ch1 = fgetc(htfTree); //读取lchild的字符串形式，并将其转换成整数形式，赋给HT[i].lchild
j = 0;
while( ch1 != ' ' ){
c[j] = ch1;
j++;
ch1 = fgetc(htfTree);
}
HT[i+1].lchild = 0;
for( t = 0; t < j; t++ )
HT[i+1].lchild = 10 * HT[i+1].lchild + c[t] - '0';
ch1 = fgetc(htfTree); //读取rchild的字符串形式，并将其转换成整数形式，赋给HT[i].rchild
j = 0;
while( ch1 != '\n' ){
c[j] = ch1;
j++;
ch1 = fgetc(htfTree);
}
HT[i+1].rchild = 0;
for( t = 0; t < j; t++ )
HT[i+1].rchild = 10 * HT[i+1].rchild + c[t] - '0';
i++;
}
}
int main(){
HuffmanTree HT;
HuffmanCode HC;
char ch[100]; //用于存储字符集
int n,Init_Mode = No; //n为字符集的大小，Init_Mode = No 表示内存中没有赫夫曼树的信息
char mode; //让用户选择不同的操作
printf("请输入你要选择的功能\n");
printf("\t\tI -- 初始化\t\tE -- 编码\n");
printf("\t\tD -- 译码 \t\tQ -- 退出程序\n");
scanf("%c",&mode); //获得用户选择的操作
while( mode != 'Q' && mode != 'q' ){ //当用户输入不为Q或q时，执行相应操作
switch(mode){
case 'I' :
InitHuff_T(HT,HC,ch,n);
Init_Mode = Yes;
break;
case 'i' :
InitHuff_T(HT,HC,ch,n);
Init_Mode = Yes;
break;
case 'E' :
if( No == Init_Mode )
ReadHuff_T(HT,HC,ch,n);
Encoding(HT,HC,ch);
Init_Mode = Yes;
break;
case 'e' :
if( No == Init_Mode )
ReadHuff_T(HT,HC,ch,n);
Encoding(HT,HC,ch);
Init_Mode = Yes;
break;
case 'D' :
if( No == Init_Mode )
ReadHuff_T(HT,HC,ch,n);
Decoding(HT,ch,n);
Init_Mode = Yes;
break;
case 'd' :
if( No == Init_Mode )
ReadHuff_T(HT,HC,ch,n);
Decoding(HT,ch,n);
Init_Mode = Yes;
default :
printf("您的输入有错，请重新选择.\n");
}
printf("请输入你要选择的功能\n");
printf("\tI -- 初始化\tE -- 编码\n");
printf("\tD -- 译码 \tQ -- 退出程序\n");
fflush(stdin);
scanf("%c",&mode); //让用户继续选择相应的操作，直至用户选择退出
}
return 0;
}
⑻ 利用 数据结构 实现 哈夫曼编码/译码实现
//D:\2010 代码\haffman\haffman\Node_statement.h
#define MAXVALUE 1000//定义最大权值
#define MAXBIT 100//定义哈夫曼树中叶子结点个数
typedef struct
{
char data;//字符值
int num;//某个值的字符出现的次数
}TotalNode;
//统计结点，包括字符种类和出现次数
typedef struct
{
TotalNode tot[300];//统计结点数组
int num;//统计数组中含有的字符个数
}Total;
//统计结构体，包括统计数组和字符种类数
typedef struct
{
char mes[300];//字符数组
int num;//总字符数
}Message;
//信息结构体，包括字符数组和总字符数
typedef struct{
int locked[500];//密码数组
int num;//密码总数
}Locking;
//哈夫曼编码后的密文信息
typedef struct
{
char data;//字符
int weight;//权值
int parent;//双亲结点在数组HuffNode[]中的序号
int lchild;//左孩子结点在数组HuffNode[]中的序号
int rchild;//右孩子结点在数组HuffNode[]中的序号
}HNodetype;
//哈夫曼树结点类型，包括左右孩子，权值和信息
typedef struct
{
int bit[MAXBIT];
int start;
}HCodetype;
//哈夫曼编码结构体，包括编码数组和起始位
void reading_file(Message *message);//从文件中读取信息
int writing_file(Message *message);//将信息写进文件
void total_message(Message *message,Total *total);//统计信息中各字符的次数
void HaffmanTree(Total *total,HNodetype HuffNode[]);//构建哈夫曼树
void HaffmanCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total);//建立哈夫曼编码
void writing_HCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total);//将编码规则写进文件
void lock(Message *message,HNodetype HuffNode[],HCodetype HuffCode[],Total *total,Locking *locking);//给文件信息加密编码
void writing_lock(Locking *locking);//将已编码信息写进文件
void first_function(HNodetype HuffNode[],HCodetype HuffCode[],Total *total,Message *message);
void display(Total *total,HNodetype HuffNode[]);
void writing_translate(Locking *locking,HCodetype HuffCode[],HNodetype HuffNode[],Total *total);//将已编码信息翻译过来并写进文
//D:\2010 代码\haffman\haffman\function_mian.cpp
#include"Node_statement.h"
#include<iostream>
#include<fstream>
#include "cstdlib"
using namespace std;
int main()
{
int i,j,choice,mark=0;//mark标记文件信息是否读入到内存中
HNodetype HuffNode[500];//保存哈夫曼树中各结点信息
HCodetype HuffCode[300];
Locking *locking;
Total *total;
Message *message;
locking=new Locking;
locking->num=0;
total=new Total;
total->num=0;
message=new Message;
message->num=0;
//初始化变量
printf("┏ ┓\n");
printf("┣ haffman_code system ┫ \n");
printf("┗ ┛\n");
printf("\n\n");
choice=0;
while(choice!=7 )
{
printf("＃〓§〓〓〓〓〓§〓〓〓〓§〓〓〓〓§〓＃ \n ");
printf(" 0:go \n");
printf("※********** 1：从文件读取信息**********************※\n");
printf(" *********** 2：显示编码规则 ********************* \n");
printf(" ********** 3：将原文件信息写进文件 ************ \n");
printf(" ********* 4：将编码规则写进文件 ************ \n");
printf(" ********** 5：将编码后的信息写进文件 ********** \n");
printf(" *********** 6：将译码后的信息写进文件 *********\n");
printf("※***********7：退出 *****************************※\n");
printf("＃〓§〓〓〓〓〓§〓〓〓〓§〓〓〓〓§〓＃ \n ");
printf(" please input the choice ");
cin>>choice;
switch(choice)
{
case 1:
reading_file(message);//从文件中读取信息
mark=1;
break;
case 2://显示编码规则
if(mark==0)cout<<"请先从文件中读取信息!"<<endl;
else
{
first_function(HuffNode,HuffCode,total,message);
cout<<"编码规则为"<<endl;
for(i=0;i<total->num;i++)//显示编码规则
{
cout<<total->tot[i].data<<" ";
for(j=HuffCode[i].start+1;j<total->num;j++)
cout<<HuffCode[i].bit[j];
cout<<endl;
}
}
break;
case 3://将原文件信息写进文件a_test1.txt
if(mark==0)cout<<"请先从文件中读取信息!"<<endl;
else
writing_file(message);//将信息写进文件
break;
case 4://将编码规则写进文件
if(mark==0)cout<<"请先从文件中读取信息!"<<endl;
else
{
first_function(HuffNode,HuffCode,total,message);
writing_HCode(HuffNode,HuffCode,total);//将编码规则写进文件
}
break;
case 5://将编码后的信息写进文件
if(mark==0)cout<<"请先从文件中读取信息!"<<endl;
else
{
first_function(HuffNode,HuffCode,total,message);
writing_lock(locking);//将已编码信息写进文件
}
break;
case 6://将译码后的信息写进文件
if(mark==0)cout<<"请先从文件中读取信息!"<<endl;
else
{
first_function(HuffNode,HuffCode,total,message);
writing_translate(locking,HuffCode,HuffNode,total);//将已编码信息翻译过来并写进文件
}
break;
}
}
/**
打印haffman树
**/
display(total,HuffNode);
system("PAUSE");
return 0;
}
void display(Total *total,HNodetype HuffNode[])
{
int i,j;
for(i=0;i<2*total->num-1;i++)
{
printf("data weight lchild rchild parent \n");
printf(" %c %d %d %d %d\n",HuffNode[i].data,HuffNode[i].weight,HuffNode[i].lchild,HuffNode[i].rchild,HuffNode[i].parent);
}
}
void reading_file(Message *message)
/**
绝对路径下读取a_test.txt file
message 中的num记录suoyou字符总数 ，放在nes【】中
equal to the buffer
**/
{
int i=0;
char ch;
ifstream infile("a_test.txt",ios::in | ios::out);
if(!infile)//打开失败则结束
{
cout<<"打开a_test.txt文件失败"<<endl;
exit(1);
}
else
cout<<"读取文件成功"<<endl;
while(infile.get(ch) && ch!='#')//读取字符直到遇到#
{
message->mes[i]=ch;
i++;
}
message->num=i;//记录总字符数
infile.close();//关闭文件
}
int writing_file(Message *message)
/**
把从数组message 的信息write to disk，a_test1.txt to save
**/
{ /*
int i;
ifstream outfile("a_test1.txt",ios::in ); //打开文件
if( !outfile )//打开失败则结束
{
cout<<"打开a_test1.txt文件失败"<<endl;
return -1;
}
for(i=0;i<message->num;i++)//写文件
outfile.put(message->mes[i]);
cout<<"信息写进文件成功"<<endl;
outfile.close();//关闭文件
return 0;*/
int i;
FILE *fp1=NULL;
if((fp1 = fopen("a_test1.txt","at"))==NULL)
{
printf("can't open the file\n");
exit(0);
}
for(i=0;i<message->num;i++)
fprintf(fp1,"%d ",message->mes[i]);
printf("文件写入成功!\n");
i=fclose(fp1);
if(i==0)
printf("文件关闭成功!\n");
else
printf("文件关闭失败!\n");
}
void total_message(Message *message,Total *total)
/**
统计message中不同字符 的个数，和相同字符重复的次数，重复字符用mark标记，
total.tot[] 放不同字符，TotalNode 类型（char，num）
total.num 统计不同字符个数
使total这块内存空间有数据，
**/
{
int i,j,mark;
for(i=0;i<message->num;i++)//遍历message中的所有字符信息
{
if(message->mes[i]!=' ')//字符不为空格时
{
mark=0;
for(j=0;j<total->num;j++)//在total中搜索当前字符
if(total->tot[j].data==message->mes[i])//搜索到，则此字符次数加1，mark标志为1
{
total->tot[j].num++;
mark=1;
break;
}
if(mark==0)//未搜索到，新建字符种类，保存进total中，字符类加1
{
total->tot[total->num].data=message->mes[i];
total->tot[total->num].num=1;
total->num++;
}
}
}
}
void HaffmanTree(Total *total,HNodetype HuffNode[])
/**create the haffman tree
不同字符个数为叶子节点个数对应书上的n，
相同字符的个数为其权值weight；
get HuffNode to store the tree
**/
{
int i,j,min1,min2,x1,x2;
for(i=0;i<2*(total->num)-1;i++)//初始化哈夫曼树并存入叶子结点权值和信息
{
if(i<=total->num-1)
HuffNode[i].data=total->tot[i].data;
HuffNode[i].weight=total->tot[i].num;
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
}
for(i=0;i<total->num-1;i++)
{
min1=min2=MAXVALUE;
x1=x2=0;
for(j=0;j<total->num+i;j++)//选取最小x1和次小x2的两权值
{
if(HuffNode[j].parent==-1&&HuffNode[j].weight<min1)
{
min2=min1;
x2=x1;
min1=HuffNode[j].weight;
x1=j;
}
else
if(HuffNode[j].parent==-1&&HuffNode[j].weight<min2)
{
min2=HuffNode[j].weight;
x2=j;
}
}
HuffNode[x1].parent=total->num+i;//修改亲人结点位置
HuffNode[x2].parent=total->num+i;
HuffNode[total->num+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;
HuffNode[total->num+i].lchild=x1;//左孩子比右孩子权值小
HuffNode[total->num+i].rchild=x2;
}
}
void HaffmanCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total)
/***
haffman to code (0,10,110,)
得到每个不同字符（叶子）的编码，
存贮在数组HuffCode【】中,bit[] store the char,start store the loction
**/
{
int i,j,c,p;
HCodetype cd;
for(i=0;i<total->num;i++)//建立叶子结点个数的编码
{
cd.start=total->num-1;//起始位初始化
p=HuffNode[i].parent;
c=i;
while(p!=-1)//从叶结点向上爬直到到达根结点
{
if(HuffNode[p].lchild==c)//左分支则为0
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;//右分支则为1
cd.start--;//起始位向前移动
c=p;
p=HuffNode[p].parent;
}
for(j=cd.start+1;j<total->num;j++)//保存求出的每个叶结点编码和起始位
HuffCode[i].bit[j]=cd.bit[j];
HuffCode[i].start=cd.start;
}
}
void writing_HCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total)
/**
HuffNode[]to input the leaf
HuffCode[]to input the code
all is to the a_test2.txt ,save the code
**/
{
/*打开HCode文件，失败则结束。将信息写进文件*/
int i,j;
FILE *fp2=NULL;
if((fp2 = fopen("a_test2.txt","at"))==NULL)
{
printf("can't open the file\n");
exit(0);
}
for(i=0;i<total->num;i++)
{fprintf(fp2,"%d ",HuffNode[i].data);
printf(" ");
for(j=HuffCode[i].start+1;j<total->num;j++)
fprintf(fp2,"%d ",HuffCode[i].bit[j]);
}
printf("编码规则写进文件成功!\n");
i=fclose(fp2);
if(i==0)
printf("文件关闭成功!\n");
else
printf("文件关闭失败!\n");
}
void lock(Message *message,HNodetype HuffNode[],HCodetype HuffCode[],Total *total,Locking *locking)
/***
对messag操作，对所有字符加密，
结果存贮在数组locked[]中，locking 记录已经加密后的密文
**/
{
int i,j,m;
for(i=0;i<message->num;i++)//把相同的不同的字符全部 遍历
{
if(message->mes[i]==' ')//碰到空格则以-1形式保存进locked数组中
{
locking->locked[locking->num]=-1;
locking->num++;
}
else
for(j=0;j<total->num;j++)//从total中找到对应的字符
{
if(HuffNode[j].data==message->mes[i])
//找到在HuffNode 中对应字符，找到下标j
// 在HuffCode
for(m=HuffCode[j].start+1;m<total->num;m++)///////// !
{
locking->locked[locking->num]=HuffCode[j].bit[m];//加密
locking->num++;
}
}
}
}
void writing_lock(Locking *locking)
/*
将密文写到a_test3.txt
*/
{
int i;
FILE *fp3=NULL;
if((fp3= fopen("a_test3.txt","at"))==NULL)
{
printf("can't open the file\n");
exit(0);
}
for(i=0;i<locking->num;i++)
{
if(locking->locked[i]==-1)
printf(" ");
else
fprintf(fp3,"%d ",locking->locked[i]);
}
printf("已编码信息写进文件成功!\n");
i=fclose(fp3);
if(i==0)
printf("文件关闭成功!\n");
else
printf("文件关闭失败!\n");
}
void writing_translate(Locking *locking,HCodetype HuffCode[],HNodetype HuffNode[],Total *total)
/**
密文翻译成明文，然后存到文件 a_test4.txt
**/
{
int i,j,mark[100],start[100],min,max;
FILE *fp4=NULL;
if((fp4 = fopen("a_test4.txt","at"))==NULL)
{
printf("can't open the file\n");
exit(0);
}
for(i=0;i<total->num;i++)//start数组初始化
{
start[i]=HuffCode[i].start+1;//。。。。
}
for(i=0;i<total->num;i++)//mark数组初始化
{
mark[i]=1;
}
min=0;
for(max=0;max<locking->num;max++)//写文件
{
if(locking->locked[max]==-1)//碰到空格信息则直接输出空格
{
printf(" ");//把空格写到文件
min++;
}
else
{
for(i=min;i<=max;i++)//查找从min开始到max的编码对应的信息
{
for(j=0;j<total->num;j++)
{
if(start[j] == total->num+1)
mark[j]=0; //对应编码比所给编码短则不在比较
if(mark[j]==1&&locking->locked[i]==HuffCode[j].bit[start[j]])
start[j]++;
else
mark[j]=0;
}
}
for(i=0;i<total->num;i++)//找到对应信息，则写进文件
{
if(mark[i]==1&&start[i]==total->num)
{
fprintf(fp4,"%d ",HuffNode[i].data);//写到文件outfile
break;
}
}
if(i!=total->num)
min=max+1;
for(i=0;i<total->num;i++)//start数组初始化
{
start[i]=HuffCode[i].start+1;
}
for(i=0;i<total->num;i++)//mark数组初始化
{
mark[i]=1;
}
}
}
printf("文件写入成功!\n");
i=fclose(fp4);
if(i==0)
printf("文件关闭成功!\n");
else
printf("文件关闭失败!\n");
}
void first_function(HNodetype HuffNode[],HCodetype HuffCode[],Total *total,Message *message)
{
total_message(message,total);//统计信息中各字符的出现次数
HaffmanTree(total,HuffNode);//构建哈夫曼树
HaffmanCode(HuffNode,HuffCode,total);//建立哈夫曼编码
}
⑼ 在VC6.0下编的程序报错 cannot open file '.\Debug\StdAfx.sbr': No such file or directory
有如下几种解决办法:1.把release文件夹删掉,重新编译2.如果你有以前编译好的,找个StdAfx.sbr文件放到debug下.如果没有,你另存工程编译.3.打个sp6补丁
⑽ 哈夫曼树及哈夫曼编码译码的实现（根据程序画流程图及对每句程序注释）
这是以前写的，可是我不想加注释了，Huffman编码其实原理很简单的，你自己好好学下吧，一句一句注释也太夸张了啊。
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
int m,s1,s2;
typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char ** HuffmanCode;
void Select(HuffmanTree HT,int n)
{
int i,j;
for(i=1;i<=n;i++)
if(HT[i].parent==0)
{s1=i;
break;
}
for(j=i+1;j<=n;j++)
if(HT[j].parent==0)
{
s2=j;
break;
}
for(i=1;i<=n;i++)
{
if(HT[i].parent==0)
if(HT[s1].weight>HT[i].weight)
if(s2!=i)
s1=i;
}
for(j=1;j<=n;j++)
{
if(HT[j].parent==0)
if(HT[s2].weight>HT[j].weight)
if(s1!=j)
s2=j;
}
if(s1>s2)
{
int temp=s1;
s1=s2;
s2=temp;
}
}
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)
{
int i,j;
char *cd;
int p;
int cdlen;
if (n<=1) return;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode));
for (i=1; i<=n; i++)
{
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for (i=n+1; i<=m; i++)
{
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
//添加查看，便于调试
printf("构造过程显示：\n");
for(i=1;i<=m;i++)
printf("%4d%4d%4d%4d%4d\n",i,HT[i].weight, HT[i].parent,HT[i].lchild, HT[i].rchild);
system("pause");
for(i=n+1;i<=m;i++)
{
Select(HT,i-1);
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("s1=%d,s2=%d\n",s1,s2);
for(j=1;j<=i;j++)
printf("%d%4d%4d%4d",j,HT[j].weight,HT[j].parent,HT[j].lchild, HT[j].rchild);
system("pause");
*/
}
cd = (char *)malloc(n*sizeof(char));
p=m;
cdlen=0;
for(i=1;i<=m;i++)
HT[i].weight=0;
while(p)
{
if(HT[p].weight==0)
{
HT[p].weight=1;
if(HT[p].lchild!=0)
{
p=HT[p].lchild;
cd[cdlen++]='0';
}
else if(HT[p].rchild==0)
{
HC[p]=(char *)malloc((cdlen+1)*sizeof(char));
cd[cdlen]='\0';
strcpy(HC[p],cd);
}
}
else if(HT[p].weight==1)
{
HT[p].weight=2;
if(HT[p].rchild!=0)
{
p=HT[p].rchild;
cd[cdlen++]='1';
}
}
else
{
HT[p].weight=0;
p=HT[p].parent;
--cdlen;
}
}
}
int main()
{
HuffmanTree HT;
HuffmanCode HC;
int *w,n,i;
printf("请输入节点数：\n");
scanf("%d",&n);
HC = (HuffmanCode)malloc(n*sizeof(HuffmanCode));
w=(int *)malloc(n*sizeof(int));
printf("请输入节点的权值：\n");
for(i=0;i<n;i++)
scanf("%d",&w[i]);
HuffmanCoding(HT,HC,w,n);
printf("输出编码：\n");
for(i=1;i<=n;i++)
printf("%2d(%4d):%s\n",i,w[i-1],HC[i]);
return 0;
system("pause");
}