注册 登录
编程论坛 → 数据结构与算法

Huffman树的完整代码

牛虻 发布于 2005-07-13 23:05， 9398 次点击

这个是完全根据教材的设计课程要求写的,前段时间由于考前复习一直没时间发上来给大家参考,还有上次的不成品代码竟然有11人购买,在这里向购买的哥们说声THX,这次发的代码完全是免费的,这次的程序包含一整棵树的编码&&译码&&画树. 为了画树,我整了一个星期哦,找到一个较为满意的角度组合,精确到小数点后面3位,接下来大家慢慢看,请菜鸟或高手多提点意见改进改进 #include<stdio.h> #include<string.h> #include<graphics.h> #include<math.h> #include<conio.h> #define MAXVALUE 10000 /*权值最大值*/ #define MAXLEAF 30 /*叶子最多个数*/ #define MAXNODE MAXLEAF*2-1 /* 结点数的个数*/ #define MAXBIT 50 /*编码的最大位数*/ #define r 8 /*圆的半径*/

typedef struct node /*结点类型定义*/ {char letter; int weight; int parent; int lchild; int rchild; }HNodeType;

typedef struct /*编码类型定义*/ {char letter; int bit[MAXBIT]; int start; }HCodeType;

typedef struct /*输入符号的类型*/ {char s; int num; }Bowen; HNodeType HuffNode[MAXNODE]; void HuffmanTree(HNodeType HuffNode[],int n,Bowen a[]) {int i,j,m1,m2,x1,x2,temp1;char temp2;

for(i=0;i<2*n-1;i++) /*结点初始化*/ {HuffNode[i].letter=NULL; HuffNode[i].weight=0; HuffNode[i].parent=-1; HuffNode[i].lchild=-1; HuffNode[i].rchild=-1;}

for(i=0;i<n;i++){HuffNode[i].weight=a[i].num;HuffNode[i].letter=a[i].s;} for(i=0;i<n-1;i++) /*构造huffman树*/ {m1=m2=MAXVALUE; x1=x2=0; for(j=0;j<n+i;j++) /*寻找权值最小与次小的结点*/ { if(HuffNode[j].parent==-1&&HuffNode[j].weight<m1) {m2=m1;x2=x1; m1=HuffNode[j].weight; x1=j;} else if(HuffNode[j].parent==-1&&HuffNode[j].weight<m2) {m2=HuffNode[j].weight; x2=j;} } HuffNode[x1].parent=n+i;HuffNode[x2].parent=n+i; /*权值最小与次小的结点进行组合*/ HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight; HuffNode[n+i].lchild=x1; HuffNode[n+i].rchild=x2;}}

void draw(float x,float y,float alph,float beta,float l,float derta,int c) {float x1,x2,y1,y2; int left,right; char t[2]="",*p=&t[0]; beta-=0.0773;alph-=beta; setcolor(RED); *p=HuffNode[c].letter; circle(x,y,r); if(*p==' '){outtextxy(x-2,y-3,"^");}else outtextxy(x-2,y-3,p); if(HuffNode[c].lchild!=-1&&HuffNode[c].rchild!=-1) {x1=x-l*sin(alph);y1=y+l*cos(alph); x2=x+l*sin(alph);y2=y+l*cos(alph); line(x-r*sin(alph),y+r*cos(alph),x1+r*sin(alph),y1-r*cos(alph)); line(x+r*sin(alph),y+r*cos(alph),x2-r*sin(alph),y2-r*cos(alph)); left=HuffNode[c].lchild;right=HuffNode[c].rchild; l-=derta,derta-=11.5; draw(x1,y1,alph,beta,l,derta,left);draw(x2,y2,alph,beta,l,derta,right);} }

void HuffmanCode(int n,Bowen a[],FILE *fp) { HCodeType HuffCode[MAXLEAF],cd; int i,j,k,c,p,*q;

FILE *fp1,*fp2;int ch1;char filename1[10],filename2[10],filename3[10],ch;

float x=320,y=100,alph=90,beta=6.95,l=120,derta=33; HuffmanTree(HuffNode,n,a);

for(i=0;i<n;i++) /*按结点位置进行编码*/ {cd.start=n-1; c=i; p=HuffNode[c].parent; while(p!=-1) {if(HuffNode[p].lchild==c) cd.bit[cd.start]=0; else cd.bit[cd.start]=1; cd.start--; c=p; p=HuffNode[c].parent;} for(j=cd.start+1;j<n;j++) /*储存编码*/ HuffCode[i].bit[j]=cd.bit[j]; HuffCode[i].start=cd.start;} for(i=0;i<n;i++) {HuffCode[i].letter=HuffNode[i].letter; printf("%c: ",HuffCode[i].letter); for(j=HuffCode[i].start+1;j<n;j++) printf("%d",HuffCode[i].bit[j]); printf("\n");}

ch=fgetc(fp); printf("Input filename to save these codes:\n"); scanf("%s",filename2); if((fp1=fopen(filename2,"w"))==NULL) {printf("Cannot open file %s",filename2);exit(0);} while(ch!=EOF) {for(j=0;j<n;j++) {if(ch==HuffCode[j].letter) for(k=HuffCode[j].start+1;k<n;k++) putc(HuffCode[j].bit[k],fp1); continue;} ch=fgetc(fp); } fclose(fp); fclose(fp1);

printf("\nThe following codes have been saved in the '%s':\n",filename2); fp1=fopen(filename2,"r"); ch1=fgetc(fp1); /* 用来验证译码是否存入codefile中 */ while(ch1!=EOF) {printf("%d",ch1);ch1=fgetc(fp1);} fclose(fp1);printf("\n");

fp1=fopen(filename2,"r"); printf("\nInput filename to save these codes' translation:\n"); scanf("%s",filename3); fp2=fopen(filename3,"w"); ch1=fgetc(fp1); printf("\nThe following traslation have been saved in the '%s':\n",filename3); while(ch1!=EOF) {if(ch1==0) {c=i=HuffNode[c].lchild; if(HuffNode[c].lchild==-1&&HuffNode[c].rchild==-1) {printf("%c",HuffNode[i].letter);c=2*n-2;fputc(HuffNode[i].letter,fp2);}} if(ch1==1) {c=i=HuffNode[c].rchild; if(HuffNode[c].lchild==-1&&HuffNode[c].rchild==-1) {printf("%c",HuffNode[i].letter);c=2*n-2;fputc(HuffNode[i].letter,fp2);}} ch1=fgetc(fp1); } getch(); fclose(fp1); fclose(fp2);

cleardevice();directvideo=0; setbkcolor(CYAN); setcolor(BLUE); outtextxy(205,10,"Press anykey to draw HuffTree:"); getch(); c=2*n-2; draw(x,y,alph,beta,l,derta,c);

}

void save() {FILE *fp;char ch,filename[10]; printf("Input filename to save datas:\n"); scanf("%s",filename); if((fp=fopen(filename,"wb"))==NULL) {printf("Cannot open file\n");exit(0);} printf("Input datas:\n"); ch=getchar(); ch=getchar(); while(ch!='\n') {fputc(ch,fp); ch=getchar();} fclose(fp);}

void main() {Bowen data[50]; FILE *fp; char ch,*p,filename[10]; int i,count=0;

int gdriver,gmode; gdriver=DETECT; initgraph(&gdriver,&gmode,""); setcolor(RED); line(236,226,410,226); line(236,226,236,280); line(410,280,410,226); line(410,280,236,280); bar(236,226,410,280); outtextxy(240,230,"PROJECT:HuffmanTree"); outtextxy(240,250," CLASS:j0303"); outtextxy(240,240," NAME:牛虻"); outtextxy(240,260," N33"); outtextxy(240,270,"TEACHER:Lin Fang"); getch(); cleardevice();

for(i=0;i<50;data[i].s=NULL,data[i].num=0,i++);

save();

printf("Input filename to load datas:\n"); scanf("%s",filename); if((fp=fopen(filename,"rb"))==NULL) {printf("Cannot open file\n"); exit(0);} ch=fgetc(fp); while(ch!=EOF) {for(i=0;i<=count+1;i++) {if(data[i].s==NULL) {data[i].s=ch;data[i].num++;count++;break;} else if(data[i].s==ch) {data[i].num++;break;}} ch=fgetc(fp);} printf("different datas:%d\n",count); for(i=0;i<count;printf("%c weight:%d\n",data[i].s,data[i].num),i++); fp=fopen(filename,"rb");

HuffmanCode(count,data,fp);fclose(fp);

setcolor(BLUE); outtextxy(100,320,"Do you want to try again?"); outtextxy(100,340,"'Y'to be continue,'N' to be break:"); ch=getch(); if(ch=='y'||ch=='y')main();

else closegraph(); }

[此贴子已经被作者于2005-7-23 10:47:38编辑过]

31 回复
#2
牛虻2005-07-13 23:15
测试数据:(仅做参考)
hfmtree   //给下面即将输入的数据指定一个文件进行储存,名字可以任意
abcdefghijklmnop //输入数据,然后将这些数据储存进刚刚指定的文件hfmtree
hfmtree   //再次输入要进行加载的文件名,然后进行统计,建树,编码
codefile   //再指定一个文件用来储存刚刚输入数据的编码形式
textfile     //再制定一个文件来储存刚刚被译码过的数据,即以字符形态进行储存
#3
牛虻2005-07-13 23:17
这个是上面数据的Huffman树图形状:
只有本站会员才能查看附件，请 登录


[此贴子已经被作者于2005-7-13 23:17:48编辑过]
#4
牛虻2005-07-13 23:22

还有另外一个以前写的没有画图的版本,纯属实现最基本功能的那种版本,一起发上来给大家共享: #include<stdio.h> #define MAXVALUE 10000 /*权值最大值*/ #define MAXLEAF 30 /*叶子最多个数*/ #define MAXNODE MAXLEAF*2-1 /* 结点数的个数*/ #define MAXBIT 50 /*编码的最大位数*/

typedef struct node /*结点类型定义*/ {char letter; int weight; int parent; int lchild; int rchild; }HNodeType;

typedef struct /*编码类型定义*/ {char letter; int bit[MAXBIT]; int start; }HCodeType;

typedef struct /*输入符号的类型*/ {char s; int num; }Bowen;

void HuffmanTree(HNodeType HuffNode[],int n,Bowen a[]) {int i,j,m1,m2,x1,x2,temp1;char temp2;

for(i=0;i<2*n-1;i++) /*结点初始化*/ {HuffNode[i].letter=NULL; HuffNode[i].weight=0; HuffNode[i].parent=-1; HuffNode[i].lchild=-1; HuffNode[i].rchild=-1;} for(i=0;i<n-1;i++) for(j=i+1;j<n-1;j++) /*对输入字符按权值大小进行排序*/ if(a[j].num>a[i].num) {temp1=a[i].num;a[i].num=a[j].num;a[j].num=temp1; temp2=a[i].s;a[i].s=a[j].s;a[j].s=temp2;} for(i=0;i<n;i++){HuffNode[i].weight=a[i].num;HuffNode[i].letter=a[i].s;} for(i=0;i<n-1;i++) /*构造huffman树*/ {m1=m2=MAXVALUE; x1=x2=0; for(j=0;j<n+i;j++) /*寻找权值最小与次小的结点*/ { if(HuffNode[j].parent==-1&&HuffNode[j].weight<m1) {m2=m1;x2=x1; m1=HuffNode[j].weight; x1=j;} else if(HuffNode[j].parent==-1&&HuffNode[j].weight<m2) {m2=HuffNode[j].weight; x2=j;} } HuffNode[x1].parent=n+i;HuffNode[x2].parent=n+i; /*权值最小与次小的结点进行组合*/ HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight; HuffNode[n+i].lchild=x1; HuffNode[n+i].rchild=x2;}}

void HuffmanCode(int n,Bowen a[]) {HNodeType HuffNode[MAXNODE]; HCodeType HuffCode[MAXLEAF],cd; int i,j,c,p,*q;char code[30],*m; HuffmanTree(HuffNode,n,a);

for(i=0;i<n;i++) /*按结点位置进行编码*/ {cd.start=n-1; c=i; p=HuffNode[c].parent; while(p!=-1) {if(HuffNode[p].lchild==c) cd.bit[cd.start]=0; else cd.bit[cd.start]=1; cd.start--; c=p; p=HuffNode[c].parent;} for(j=cd.start+1;j<n;j++) /*储存编码*/ HuffCode[i].bit[j]=cd.bit[j]; HuffCode[i].start=cd.start;} for(i=0;i<n;i++) {HuffCode[i].letter=HuffNode[i].letter; printf("%c ",HuffCode[i].letter); for(j=HuffCode[i].start+1;j<n;j++) printf("%d",HuffCode[i].bit[j]); printf("\n");} printf("Now,input the code(1/0):\n"); for(i=0;i<30;i++) code[i]=NULL; scanf("%s",&code); m=code; /*输入'0','1'码进行译码*/ /* while(*m!=NULL) {if(*m=='1')printf("f"); else if(*m=='0') printf("t");m++;} */ c=2*n-2; while(*m!=NULL) /*按路径寻找进行译码(树的左孩子为0,右孩子为1)*/ {if(*m=='0') {c=i=HuffNode[c].lchild;

if(HuffNode[c].lchild==-1&&HuffNode[c].rchild==-1) {printf("%c",HuffNode[i].letter);c=2*n-2;}} if(*m=='1') {c=i=HuffNode[c].rchild; if(HuffNode[c].lchild==-1&&HuffNode[c].rchild==-1) {printf("%c",HuffNode[i].letter);c=2*n-2;}} m++; } }

main() {Bowen data[30]; char s[100],*p; int i,count=0;clrscr(); printf("Input some letters:"); scanf("%s",&s);

for(i=0;i<30;i++) {data[i].s=NULL; data[i].num=0;} p=s; while(*p) /*计算字符个数与出现次数(即权值)*/ {for(i=0;i<=count+1;i++) {if(data[i].s==NULL) {data[i].s=*p;data[i].num++;count++;break;} else if(data[i].s==*p) {data[i].num++;break;}} p++;} printf("\n"); printf("different letters:%d\n",count); for(i=0;i<count;i++) {printf("%c ",data[i].s); printf("weight:%d",data[i].num); printf("\n\n");} HuffmanCode(count,data); getch();} 给点建议或者批评，谢绝灌水。。。^_^

[此贴子已经被作者于2005-8-18 9:45:46编辑过]
#5
tary2005-07-15 10:42
支持一下！
#6
sunfenggui2005-07-18 21:26
谢谢斑竹了!!!!感激不尽
#7
梧桐2005-11-17 21:31
我是新手
刚学数据结构
对C语言中文件的操作看不懂

想请教一下对哈夫曼编码怎么输出呢？
可以这样 00 010 0110 10 110 1110 1111的编码吗？
#8
king13592005-11-27 14:16

果然是高手,程序我借去应付老师了,先谢谢咯
#9
ぺЖ楓Ж仐2005-11-27 19:13
真是强啊
#10
谁能真的懂得爱2005-11-30 17:15

高手!!!!
谢啦!!!!
我什么时候有这个水平@#@#@@$$#$%$#^@%%$#^&%^
#11
fang8408262006-01-11 13:40

强人，谢了
#12
skyland842006-10-16 09:17
厉害～！佩服～！
#13
pepe05032006-12-25 12:01

对我很有启发，非常感谢。
#14
haha_fly2007-01-08 16:55
很不错!只是画图目前老师在设计的时候没这样要求是有难度!

[此贴子已经被作者于2007-1-8 16:55:58编辑过]
#15
wcxwxl2007-04-18 23:10

我怎么在WinTc中无法运行改程序呀
#16
liuminghui2007-04-19 09:26
以下是引用梧桐在2005-11-17 21:31:00的发言：
我是新手
刚学数据结构
对C语言中文件的操作看不懂

想请教一下对哈夫曼编码怎么输出呢？
可以这样 00 010 0110 10 110 1110 1111的编码吗？

可以的，关键看你给的是那些数据。
#17
anlingdiao2007-06-07 22:40

再次感叹LZ的神奇天赋,比起那些破书,不知要强多少倍啊!!!!!!!!!!
感激涕零ING.............
#18
曾小2007-06-08 14:25
太牛了！望尘莫及啊！
#19
nuciewth2007-06-08 21:50
强帖.支持一下.
#20
菜鸟也疯狂2007-06-09 11:44
斑主也灌水？
#21
wangwang1682007-06-09 12:16

不错!!!又一个强人
#22
wxj120bw2007-06-09 13:12
先慢慢欣赏你的程序........................
#23
zx5202007-06-12 08:12
#24
zx5202007-06-12 08:20
太好拉,做的太好拉,厉害呀
#25
小小R2007-06-29 14:44
真系感激不尽啊～
#26
突破重围2007-07-02 11:23
include<graphics.h>
VC版说这里出现错误,是什么原因啊,高手指点
#27
hcl3827102007-08-17 22:50

#28
wingyip2007-08-19 08:46
樓主，我五體投地了。
#29
肖付2010-11-11 19:34
哈哈，LZ好哇。。。我现在数据结构的项目就是这个了，不过放心，我虽然会照搬，但是我还是会认真看的，我会好好地研究一下你这个的，研究不透我也就只有不研究就给老师的了哈。
谢谢LZ 了哦。。
#30
leizisdu2011-11-06 11:22
回复 26楼 突破重围
“graphics.h是borland公司编译器特有的东西，不是标准的库，所以VC里没有
处理方法：使用TC,BC”。
注：http://topic.
#31
leizisdu2011-11-06 11:35
回复 楼主 牛虻
楼主，！
就是缩进不太好，看着有些费劲
#32
lidonghaha2012-10-23 15:31
学习一下，谢谢分享
1
©2025, BC-CN.NET
电脑版