数据结构中哈夫曼树的应用（C语言）

#include
#include
typedef int DataType;
#define MaxValue 10000
#define MaxBit 10
#define MaxN 100
#define N 100;
int n1=0;
char c[100];
typedef struct Node
{
DataType data;
struct Node *leftChild;
struct Node *rightChild;
}BiTreeNode;
typedef struct
{
int weight;
int flag;
int parent;
int leftChild;
int rightChild;
}HaffNode;

typedef struct
{
int bit[MaxN];
int start;
int weight;
}Code;

struct worder
{
char words; /*字符*/
}word[100];
struct weighted
{
int weighter; /*转换权值有利于文件的存储*/
}weight[100] ;
void Initiate(BiTreeNode **root) /*初始化二叉树*/
{
*root=(BiTreeNode * )malloc(sizeof(BiTreeNode));
(*root)->leftChild=NULL;
(*root)->rightChild=NULL;
}
BiTreeNode *InsertLeftNode(BiTreeNode *curr,DataType x) /*插入左子树*/
{
BiTreeNode *s,*t;
if(curr==NULL) return NULL;
t=curr->leftChild;
s=(BiTreeNode *)malloc(sizeof(BiTreeNode));
s->data=x;
s->leftChild=t;
s->rightChild=NULL;
curr->leftChild=s;
return curr->leftChild;
}

BiTreeNode *InsertRightNode(BiTreeNode *curr ,DataType x) /*插入右子树*/
{
BiTreeNode *s,*t;
if(curr==NULL)
return NULL;
t=curr->rightChild;
s=(BiTreeNode *)malloc(sizeof(BiTreeNode));
s->data=x;
s->rightChild=t;
s->leftChild=NULL;
curr->rightChild=s;
return curr->rightChild;
}

void Haffman(int weigh[],int n,HaffNode haffTree[],int a[][3]) /*建立哈夫曼树*/
{
int i,j,m1,m2,x1,x2;

for(i=0;i<2*n-1;i++)
{

if(i haffTree[i].weight=weigh[i];
else haffTree[i].weight=0;
haffTree[i].parent=-1;
haffTree[i].flag=0;
haffTree[i].leftChild=-1;
haffTree[i].rightChild=-1;
}

for(i=0;i {
m1=m2=MaxValue;
x1=x2=0;
for(j=0;j {
if(haffTree[j].weight {
m2=m1;
x2=x1;
m1=haffTree[j].weight;
x1=j;
}
else if(haffTree[j].weight {
m2=haffTree[j].weight;
x2=j;
}
}
haffTree[x1].parent=n+i;
haffTree[x2].parent=n+i;
haffTree[x1].flag=1;
haffTree[x2].flag=1;
haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight;
haffTree[n+i].leftChild=x1;
haffTree[n+i].rightChild=x2;
a[i+1][0]=haffTree[x1].weight;
a[i+1][1]=haffTree[x2].weight; /*将每个权值赋值给二维数组a[][],利用这个二维数组可以进行建立二叉树*/
a[i+1][2]=haffTree[n+i].weight;
}
}

void HaffmanCode(HaffNode haffTree[],int n,Code haffCode[]) /*对已经建立好的哈夫曼树进行编码*/
{
Code *cd=(Code *)malloc(sizeof(Code));
int i,j,child,parent;

for(i=0;i {
cd->start=n-1;
cd->weight=haffTree[i].weight;
child=i;
parent=haffTree[child].parent;
while(parent!=-1)
{
if(haffTree[parent].leftChild==child)
cd->bit[cd->start]=0;
else
cd->bit[cd->start]=1;
cd->start--;
child=parent;
parent=haffTree[child].parent;
}

for(j=cd->start+1;j haffCode[i].bit[j]=cd->bit[j];
haffCode[i].start=cd->start+1;
haffCode[i].weight=cd->weight;
}
}

void PrintBiTree(BiTreeNode *bt ,int n) /*将哈夫曼树转换成的二叉树进行打印*/
{
int i;
if(bt==NULL)
return;
PrintBiTree(bt->rightChild,n+1);
for(i=0;iprintf(" ");
if(bt->data!=0&&bt->data<100)
{
if(n>0)
{
printf("---");
printf("%d\n\n",bt->data);
}
}
PrintBiTree(bt->leftChild,n+1);
}

int search(int a[][3],int m) /*查找和a[][2]相等的权值*/
{
int i=1;
if(m==1) return 0;
while(a[i][2]!=a[m][0]&&i i++;
if(i==m) return 0; /*查找失败返回数字0 查找成功返回和a[][2]相等的数的行数 i*/
else return i;
}

int searcher(int a[][3],int m) /*查找和a[][1]相等的权值*/
{
int i=1;
if(m==1) return 0;
while(a[i][2]!=a[m][1]&&i i++;
if(i==m) return 0;
else return i;
}

void creat(BiTreeNode *p,int i,int a[][3]) /*建立哈夫曼树*/（利用递归）
{
int m,n;
BiTreeNode *p1,*p2,*p3;
if(i<=0) return;
p1=p;
if(a[i][0]!=a[i][1]) /*如果a[][0]和a[][1]不相等*/
{
p2=InsertLeftNode(p,a[i][0]); /*a[][0]为左子树*/
n=search(a,i);
if(n)
creat(p2,n,a);
p3=InsertRightNode(p1,a[i][1]); /*a[][1]为右子树*/
m=searcher(a,i);
if(m)
creat(p3,m,a);
} /*如果a[][0]和a[][1]相等则只要进行一个的查找*/
else
{
p2=InsertLeftNode(p,a[i][1]);
n=searcher(a,i);
if(n)
creat(p2,n,a);
p3=InsertRightNode(p1,a[i][1]);
}
}

void code(Code myHaffCode[],int n ) /*编码*/
{
FILE *fp,*fp1,*fp2;
int i=0,k,j;
int text_len = strlen(c);
int *p2;
struct worder *p1;
if((fp2=fopen("CodeFile","wb"))==NULL) /*建立存储编码的文件*/
{
printf("Error,cannot open file\n" );
exit(0);
}
if((fp1=fopen("hfmTree","rb"))==NULL) /*读取存储字符的文件*/
{
printf("\n\n Please,increase records first~!! \n" );
return;
}
for(p1=word;p1 {
fread(p1,sizeof(struct worder),1,fp1) ;
printf("word=%c Weight=%d Code=",p1->words,myHaffCode[i].weight); /*输出每个权值的编码*/
for(j=myHaffCode[i].start;j printf("%d",myHaffCode[i].bit[j]);
printf("\n");
printf("\n");
i++;
}
j=0;
printf("\n\nThe codes :") ;
for(i=0;i< text_len;i++)
{
while(c[i]!=word[j].words) /*查找字符找到对应的编码*/
{
j++;
}
for(k=myHaffCode[j].start;k {
printf("%d",myHaffCode[j].bit[k]); /*输出相应的编码*/
fprintf(fp2,"%d",myHaffCode[j].bit[k]);
}
j=0;
}

fclose(fp2);
}

void sava(int n) /*建立文件*/
{
FILE *fp,*fp1,*fp2;
int *p2,i,j;
struct worder *p1;
struct weighted *p3;
if((fp2=fopen("NO.","wb"))==NULL) /*建立存储权值个数的文件*/
{
printf("Error,cannot open file\n" );
exit(0);
}
fprintf(fp2,"%d",n) ;
if((fp=fopen("hfmTree","wb"))==NULL) /*建立存储字符的文件*/
{
printf("Error,cannot open file\n" );
exit(0);
}
for(p1=word;p1 {
if(fwrite(p1,sizeof(struct worder),1,fp)!=1)
printf("file write error\n");
}
fclose(fp);
if((fp1=fopen("hfmTree-1","wb"))==NULL) /*建立存储权值的文件*/
{
printf("Error,cannot open file\n" );
exit(0);
}
for(p3=weight;p3 {
if(fwrite(p3,sizeof(struct weighted),1,fp1)!=1)
printf("file write error\n");
}
fclose(fp1);
printf("Please input any key !\n") ;

printf("Please input any key !\n") ;
if(n>MaxN)
{
printf("error!\n\n");
exit(0);
}
}

void menu() /*界面*/
{

printf("\n\n\n\t\t*************************************\n\n");
printf("\t\t\t1. To Code:\n\n"); /*编码*/
printf("\t\t\t2. Decoding:\n\n"); /*译码*/
printf("\t\t\t3. Output the huffman Tree:\n\n"); /*打印哈夫曼树*/
printf("\t\t\t4. New data\n\n");
printf("\t\t\t5. Quit up...\n\n");
printf("\n\t\t************************************\n\n");
printf("Input you choice :\n");
}

void main()
{ FILE *fp,*fp1,*fp2,*fp3,*fp4;
int i,j;
int b[100][3],m=100,n,w,k=0,weigh[100];
struct worder *d;
struct weighted *p2;
char h;
BiTreeNode *root,*p;

HaffNode *myHaffTree=(HaffNode *)malloc(sizeof(HaffNode)*(2*m+1));
Code *myHaffCode=(Code *)malloc(sizeof(Code)*m);
Initiate(root);
if(((fp1=fopen("hfmTree","rb"))==NULL)&&((fp=fopen("hfmTree-1","rb"))==NULL))
{
loop:
printf("how many number do you want input?\n");
scanf("%d",&n);
if((fp=fopen("hfmTree-1","wb"))==NULL)
{
printf("Error,cannot open file\n" );
exit(0);
}
for(i=0;i {
printf("\nword[%d]=",i) ;
scanf("%s",&word[i].words) ;
printf("\nweight[%d]=",i);
scanf("%d",&weight[i].weighter);
}
sava(n) ;
}
else
{
if((fp3=fopen("NO.","rb"))==NULL)
{
printf("\n\n Please,increase records first~!! \n" );
return;
}
fscanf(fp3,"%d",&n);
if((fp=fopen("hfmTree-1","rb"))==NULL)
{
printf("\n\n Please,increase records first~!! \n" );
return;
}
for(p2=weight;p2 {
fread(p2,sizeof(struct weighted),1,fp) ;
weigh[k]=p2->weighter ;
k++;
}
Haffman(weigh,n,myHaffTree,b);
HaffmanCode(myHaffTree,n,myHaffCode);
while(1)
{
do
{
clrscr();
menu();
scanf("%d",&w);
}while(w!=1&&w!=2&&w!=3&&w!=4&&w!=5);
switch(w)
{
case 1: clrscr();
printf("plesase input :\n");
scanf("%s",&c) ;
if((fp2=fopen("ToBeTran","wb"))==NULL)
{
printf("Error,cannot open file\n" );
exit(0);
}
fprintf(fp2,"%s",c) ;
fclose (fp2);
code(myHaffCode,n) ;
getch();
break;
case 2: if((fp2=fopen("ToBeTran","rb"))==NULL)
{
printf("\n\n Please,increase records first~!! \n" );
return;
}
fscanf(fp2,"%s",&c);
printf("The words:");
printf("%s",c);
if((fp4=fopen("TextFile.","wb"))==NULL)
{
printf("Error,cannot open file\n" );
exit(0);
}
fprintf(fp4,"%s",c) ;
fclose (fp4);
getch();
break;
case 3: clrscr();
printf("The huffman Tree:\n\n\n\n\n\n");
p=InsertLeftNode(root,b[n-1][2]);
creat(p,n-1,b);
PrintBiTree(root->leftChild,n);
printf("\n");
getch();
clrscr();
break;
case 4:goto loop;

case 5:exit(0);
}
}
}
getch();
}

/* 哈夫曼编码*/
#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 { 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 { 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 printf("(%c,%s) ",mm[i].c,mm[i].s);
dispCode(n);
}

dispCode(int n) /*将各字符的编码存入数组mm*/
{ int i,j;
CODE *p;
for(i=0;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 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 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 { 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 { 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();
}