数据结构课程设计之赫夫曼编码译码器

#include"math.h" #include"graphics.h" #include"stdio.h" #define PI 3.1415 struct mark {int x,y; };/*存储赫夫曼树各结点的坐标值*/ struct HTNode { unsigned int weight; unsigned int parent,lchild,rchild; };/*赫夫曼树的存储结构*/ char **HC,*word;/*HC存储赫夫曼编码,word存储结点的字母*/ int s1,s2,*W,N,M;/*s1,s2返回当前权值最小两个结点， */ /*W存储权值，N,M分别存储赫夫曼数叶子结点数和总结点数*/ struct mark *Mark,*xy;/*Mark存储用定点法处理的坐标值，*/ /*xy存储用满二叉数法处理的坐标值*/ struct HTNode *HT;/*HT存储赫夫曼树*/ /*move_right()*/ void mark_fulltree() /*用满二叉树法处理赫夫曼树各个结点坐标值函数*/ { int i,j; for(i=63,j=16;i>=33;i-=2,j--) { xy[i].x=629-(16-j)*40; xy[i-1].x=xy[i].x-20; xy[i].y=320; xy[i-1].y=320; } for(i=31;i>=1;i--) { xy[i].x=(xy[2*i].x+xy[2*i+1].x)/2; if(i>=16&&i<=31)xy[i].y=280; else if(i>=8&&i<=15)xy[i].y=250; else if(i>=4&&i<=7)xy[i].y=210; else if(i>=2&&i<=3)xy[i].y=170; else if(i==1)xy[i].y=130; } }/*mark_fulltree()*/ void mark_number(int m,int n) /*用递归法给赫夫曼树各个结点标上满二叉树的标号*/ { Mark[m]=xy[n]; if(HT[m].lchild) mark_number(HT[m].lchild,2*n); if(HT[m].rchild) mark_number(HT[m].rchild,2*n+1); } /*mark_number()*/ void Draw_tree() /*画赫夫曼树函数（是在电脑荧屏够大的时候就给画树）*/ { int gdriver,gmode,i,j; char s[20],h='n'; void Input(); gdriver=DETECT; initgraph(&gdriver,&gmode,""); setbkcolor(1); setcolor(YELLOW); rectangle(6,390,632,472); rectangle(0,0,638,478); setcolor(YELLOW); outtextxy(10,395,"N is:"); sprintf(s,"%d",N); outtextxy(10,405,s); outtextxy(10,430,"Word and weight is:"); for(i=1;i<=N;i++) { sprintf(s,"%c:%d",word[i],W[i]); outtextxy(10+(i-1)*45,440,s); } for(i=1;i<=M;i++) /*模拟赫夫曼树生成过程中的生成各个叶子结点的过程*/ { setcolor(RED); settextstyle(0,0,0); sprintf(s,"Now born No.%d",i);/*用文字形式显示生成叶子过程*/ outtextxy(270,415,s); for(j=0;j<=360;j+=10) { setcolor(YELLOW); settextstyle(2,0,0); arc(30+(i-1)*25,377,j,j+10,10);delay(5000); if(i<=N){sprintf(s,"%d",HT[i].weight);outtextxy(30+(i-1)*25-5,373,s);} } setcolor(1); settextstyle(0,0,0); sprintf(s,"Now born No.%d",i); outtextxy(270,415,s); } for(i=N+1;i<=M;i++)/*开始模拟赫夫曼数连接过程*/ { if(HT[HT[i].lchild].weight<=HT[HT[i].rchild].weight) /*模拟s1,s2的过程*/ { setcolor(RED); settextstyle(0,0,0); sprintf(s,"Now select No.%d min",HT[i].lchild); /*用文字形式显示模拟s1,s2的过程*/ outtextxy(270,415,s); for(j=0;j<=360;j+=10) { setcolor(RED); arc(30+(HT[i].lchild-1)*25,377,j,j+10,10); setcolor(YELLOW); settextstyle(2,0,0); arc(Mark[HT[i].lchild].x,Mark[HT[i].lchild].y,j,j+10,10); sprintf(s,"%d",HT[HT[i].lchild].weight); outtextxy(Mark[HT[i].lchild].x-5,Mark[HT[i].lchild].y-5,s);delay(5000); } setcolor(1); settextstyle(0,0,0); sprintf(s,"Now select No.%d min",HT[i].lchild); outtextxy(270,415,s); setcolor(RED); settextstyle(0,0,0); sprintf(s,"Now select No.%d min",HT[i].rchild); outtextxy(270,415,s); for(j=0;j<=360;j+=10) { setcolor(RED); arc(30+(HT[i].rchild-1)*25,377,j,j+10,10); setcolor(YELLOW); settextstyle(2,0,0); arc(Mark[HT[i].rchild].x,Mark[HT[i].rchild].y,j,j+10,10); sprintf(s,"%d",HT[HT[i].rchild].weight); outtextxy(Mark[HT[i].rchild].x-5,Mark[HT[i].rchild].y-5,s);delay(5000); } setcolor(1); settextstyle(0,0,0); sprintf(s,"Now select No.%d min",HT[i].rchild); outtextxy(270,415,s); }/* if */ else /*模拟s1,s2的过程*/ { setcolor(RED); settextstyle(0,0,0); sprintf(s,"Now select No.%d min",HT[i].rchild); /*用文字形式显示模拟s1,s2的过程*/ outtextxy(270,415,s); for(j=0;j<=360;j+=10) { setcolor(RED); arc(30+(HT[i].rchild-1)*25,377,j,j+10,10); setcolor(YELLOW); settextstyle(2,0,0); arc(Mark[HT[i].rchild].x,Mark[HT[i].rchild].y,j,j+10,10); sprintf(s,"%d",HT[HT[i].rchild].weight); outtextxy(Mark[HT[i].rchild].x-5,Mark[HT[i].rchild].y-5,s);delay(5000); } setcolor(1); settextstyle(0,0,0); sprintf(s,"Now select No.%d min",HT[i].rchild); outtextxy(270,415,s); setcolor(RED); settextstyle(0,0,0); sprintf(s,"Now select No.%d min",HT[i].lchild); outtextxy(270,415,s); for(j=0;j<=360;j+=10) { setcolor(RED); arc(30+(HT[i].lchild-1)*25,377,j,j+10,10); setcolor(YELLOW); settextstyle(2,0,0); arc(Mark[HT[i].lchild].x,Mark[HT[i].lchild].y,j,j+10,10); sprintf(s,"%d",HT[HT[i].lchild].weight); outtextxy(Mark[HT[i].lchild].x-5,Mark[HT[i].lchild].y-5,s);delay(5000); } setcolor(1); settextstyle(0,0,0); sprintf(s,"Now select No.%d min",HT[i].lchild); outtextxy(270,415,s); } /*else */ setcolor(RED); settextstyle(0,0,0); sprintf(s,"Now Link No.%d",i); /*用文字形式显示连接过程*/ outtextxy(270,415,s); for(j=0;j<=360;j+=10) {setcolor(YELLOW); settextstyle(2,0,0); arc(Mark[i].x,Mark[i].y,j,j+10,10); sprintf(s,"%d",HT[i].weight); outtextxy(30+(i-1)*25-5,373,s); outtextxy(Mark[i].x-5,Mark[i].y-5,s); setcolor(RED); arc(30+(i-1)*25,377,j,j+10,10); delay(5000); } for(j=0;j<=360;j+=10)/*模拟连接过程*/ {setcolor(YELLOW); arc(30+(i-1)*25,377,j,j+10,10); delay(5000); } setcolor(1); settextstyle(0,0,0); sprintf(s,"Now Link No.%d:",i); outtextxy(270,415,s); setcolor(YELLOW); /*用直线模拟连接过程*/ line(Mark[i].x-10*sin(PI/4),Mark[i].y+10*sin(PI/4),Mark[HT[i].lchild].x+10*sin(PI/4),Mark[HT[i].lchild].y-10*sin(PI/4)); setcolor(WHITE); settextstyle(0,0,0); outtextxy((Mark[i].x-10*sin(PI/4)+Mark[HT[i].lchild].x+10*sin(PI/4))/2-10,(Mark[i].y+10*sin(PI/4)+Mark[HT[i].lchild].y-10*sin(PI/4))/2-10,"0"); setcolor(YELLOW); line(Mark[i].x+10*sin(PI/4),Mark[i].y+10*sin(PI/4),Mark[HT[i].rchild].x-10*sin(PI/4),Mark[HT[i].rchild].y-10*sin(PI/4)); setcolor(RED); settextstyle(0,0,0); outtextxy((Mark[i].x+10*sin(PI/4)+Mark[HT[i].rchild].x-10*sin(PI/4))/2+5,(Mark[i].y+10*sin(PI/4)+Mark[HT[i].rchild].y-10*sin(PI/4))/2-10,"1"); }/*for(i=N+1……）*/ setcolor(RED); settextstyle(0,0,0); rectangle(8,12,162,41); /*显示创建者*/ outtextxy(10,15," liu hai yang"); setcolor(RED); outtextxy(10,50,"Huffman Code:"); settextstyle(0,0,2); outtextxy(Mark[M].x+50,Mark[M].y-20,"Huffman Tree"); /*根据总结点的位置标志树的位置*/ settextstyle(0,0,0); for(i=1;i<=N;i++)/*显示赫夫曼编码*/ { setcolor(YELLOW); sprintf(s,"%c: %s",word[i],HC[i]); outtextxy(10,65+(i-1)*15,s); delay(5000); } while(1)/*给用户继续使用本程序的机会*/ { settextstyle(0,0,2); setcolor(RED); outtextxy(320,455,"You want continue!"); h=getch(); if(h=='Y'||h=='y') { free(Mark);free(xy);free(W);free(word);free(HT);free(HC); Input();closegraph();break; } else {closegraph(); break;} }/*while(1)*/ closegraph(); }/*Draw_tree() */ void Draw_nulltree() /*由于荧屏不够大，我们就不给出树，但我们给出赫夫曼编码*/ { int gdriver,gmode,i,j; char s[20]; void Input(); gdriver=DETECT; initgraph(&gdriver,&gmode,""); setbkcolor(1); setcolor(YELLOW); rectangle(6,390,632,472); rectangle(0,0,638,478); setcolor(YELLOW); outtextxy(10,395,"N is:"); sprintf(s,"%d",N); outtextxy(10,405,s); outtextxy(10,430,"Word and weight is:"); for(i=1;i<=N;i++) { sprintf(s,"%c:%d",word[i],W[i]); outtextxy(10+(i-1)*45,440,s); } setcolor( 2); rectangle(8,12,162,41); /*显示创建者*/ outtextxy(10,15," liu xue ying "); ou