这个是完全根据教材的设计课程要求写的,前段时间由于考前复习一直没时间发上来给大家参考,还有上次的不成品代码竟然有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编辑过]
