数据结构课程设计报告哈夫曼编码译码器

1、哈弗曼编码译码器专 业 班 级 ：XXXX学 号 ：XXXX姓 名 ：XXXX指 导 教 师 ：XXXX课程设计时间：XXXX计算机专业 数据结构 课程设计任务书学生姓名XXXX专业班级XXXX学号XXXX题 目哈弗曼编码译码器课题性质工程设计课题来源XXXX指导教师XXXX同组姓名XXXX 主要内容 设计一个哈弗曼编码译码器，实现哈夫曼树的建立，树形输出，编码和解码。任务要求1研究哈弗曼树的数据存储方式2实现哈弗曼编码译码器的主要算法3分析算法的运行效率4具有良好的运行界面5算法具有良好的健壮性6按要求撰写课程设计报告和设计总结。参考文献1数据结构（C语言版），严蔚敏、吴伟民，清华大学出版社

2、，1997.审查意见指导教师签字： 教研室主任签字： 年 月 日 1 需求分析 设计一个哈弗曼编码译码器，实现哈夫曼树的建立，树形输出，编码和解码。2 概要设计main 退出系统帮助 哈夫曼文件解码 哈夫曼文件编码 树形输出哈夫曼树查看哈夫曼编码建立哈夫曼树 3 运行环境（软、硬件环境）1) 硬件：PC机2) 操作系统：Windows 2000/XP/20033) 编译环境：Visual C+6.04 开发工具和编程语言开发工具：VISCALL c+6.0；编程语言：C语言。5 详细设计 #include<stdio.h> #include<stdlib.h> #inc

3、lude<string.h> typedef struct / 结点的结构 unsigned int weight; / 结点的权值unsigned int parent,lchild,rchild; HTNode,*HuffmanTree; / 动态分配数组存储哈夫曼树 typedef char *HuffmanCode; / 动态分配数组存储哈夫曼编码 HuffmanTree HT; HuffmanCode HC; int n=8;const char menu="|1 建立哈夫曼树 |n""|2 查看哈夫曼编码 |n""|3

4、树形输出哈夫曼树 |n""|4 哈夫曼文件编码 |n""|5 哈夫曼文件解码 |n""|6 帮助 |n""|7 退出系统 |n"const char helpsabout="|主要功能: |n" "| 利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息的传输时间，降低 |n""|传输成本。但是，这要求在发送端通过一个编码系统对待传输的数据预先编码，在接收 |n""|端将传来的数据进行译码（复原）。对于双工信道，每端都要有一个完整的

5、编/译码系 |n""|统。本系统即是为这样的信息收发站写一个哈夫曼码的编/译系统。 |n""| |n""| |n" void Huffmantree(); void Huffmancode(); void preorder(); void stringcopy(); int min(); void select(); void decode(); void encode(); void int_huffmantree(); void print_end(); void print_title(); void print_me

6、nu(); void print_helpabout(); void print_huffmancode(); void print_tree();/-先序遍历-void preorder(int root,int depth)int i;for(i=1;i<=depth;i+)printf(" ");if(depth!=0)printf("");elseprintf(" ");printf("%d",HTroot.weight,depth);if(root<=n)printf(" : %sn

7、",HCroot); / 依次输出哈夫曼编码elseprintf("n");if(HTroot.lchild!=0)depth+;preorder(HTroot.lchild,depth);if(HTroot.rchild!=0)preorder(HTroot.rchild,depth);/-字符串拷贝函数-void stringcopy(char *strDest,char *strSrc) char *strDestCopy=strDest; if (!(strDest&&strSrc) printf("ERROR!");

8、while (*strDest+=*strSrc+)!='0'); /-返回哈夫曼树t的前i个结点中权值最小的树的根结点序号，函数select()调用- int min(HuffmanTree t,int i) int j,m; unsigned int k=0xffffffff; / k存最小权值，初值取为不小于可能的值 for(j=1;j<=i;j+) / 对于前i个结点 if(tj.weight<k&&tj.parent=0) / tj的权值小于k，又是树的根结点 k=tj.weight; / tj的权值赋给k m=j; / 序号赋给m tm.

9、parent=1; / 给选中的根结点的双亲赋非零值，避免第2次查找该结点 return m; / 返回权值最小的根结点的序号 /-在哈夫曼树t的前i个结点中选择2个权值最小的树的根结点序号，s1为其中序号(权值)较小的- void select(HuffmanTree t,int i,int &s1,int &s2) int j; s1=min(t,i); / 权值最小的根结点序号 s2=min(t,i); / 权值第2小的根结点序号 if(s1>s2) / s1的序号大于s2的 / 交换 j=s1; s1=s2; / s1是权值最小的2个中序号较小的 s2=j; /

10、s2是权值最小的2个中序号较小的 /-w存放n个字符的权值(均>0)，构造哈夫曼树HT- void Huffmantree(int *w) int m,i,s1,s2; HuffmanTree p; if(n<=1) / 叶子结点数不大于n return ; m=2*n-1; / n个叶子结点的哈夫曼树共有m个结点 HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); / 0号单元未用 for(p=HT+1,i=1;i<=n;+i,+p,+w) / 从1号单元开始到n号单元，给叶子结点赋值 / p的初值指向1号单元 (*p).weight=*

11、w; / 赋权值 (*p).parent=0; / 双亲域为空(是根结点) (*p).lchild=0; / 左右孩子为空(是叶子结点，即单结点树) (*p).rchild=0; for(;i<=m;+i,+p) / i从n+1到m (*p).parent=0; / 其余结点的双亲域初值为0 for(i=n+1;i<=m;+i) / 建哈夫曼树 / 在HT1i-1中选择parent为0且weight最小的两个结点，其序号分别为s1和s2 select(HT,i-1,s1,s2); HTs1.parent=HTs2.parent=i; / i号单元是s1和s2的双亲 HTi.lchi

12、ld=s1; / i号单元的左右孩子分别是s1和s2 HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; / i号单元的权值是s1和s2的权值之和 /-并求出n个字符的哈夫曼编码HC-void Huffmancode() int start; unsigned int f; int i; unsigned int c; char *cd; HC=(HuffmanCode)malloc(n+1)*sizeof(char*);/ 分配n个字符编码的头指针 cd=(char*)malloc(n*sizeof(char); / 分配求编码的字符数组 c

13、dn-1='0' for(i=1;i<=n;i+) / 逐个字符求哈夫曼编码 start=n-1; / 编码结束符位置 for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) / 从叶子到根逆向求编码 if(HTf.lchild=c) / c是其双亲的左孩子 cd-start='0' / 由叶子向根赋值'0' else / c是其双亲的右孩子 cd-start='1' / 由叶子向根赋值'1' HCi=(char*)malloc(n-start)*sizeof(char); /

14、 为第i个字符编码分配空间 stringcopy(HCi,&cdstart); / 从cd复制编码串到HC矩阵 free(cd); / 释放工作空间/-译码- void encode() FILE *fp1=NULL,*fp2=NULL;char input20="input.txt",output20="output.txt"printf("请输入输入文件名(input.txt)：");scanf("%s",input);if (fp1=fopen(input,"r")=NULL)pr

15、intf("无此文件！");getchar();getchar();return ;printf("请输入输出文件名(output.txt)：");scanf("%s",output);if(fp2=fopen(output,"w")=NULL)printf("不能创建文件！");getchar();getchar();return ;int i,k;unsigned int *w,p,m=0,j;for(k=0;!feof(fp1);k+)if(fgetc(fp1)=' ')m

16、+;printf("哈夫曼编码为:");fp1=fopen(input,"r"); w=(unsigned int*)malloc(m*sizeof(unsigned int); / 动态生成存放m个权值的空间 for(j=0;j<=m-1;j+) fscanf(fp1,"%d",w+j); / 依次输入原码 for(p=0;p<m;p+) for(i=0;i<n;i+) if(*(w+p)=HTi+1.weight) fprintf(fp2,"%s",HCi+1); printf("%

17、s",HCi+1); fclose(fp1); fclose(fp2);printf("n输出完成.按任意键继续.");getchar();getchar(); /-解码-void decode()FILE *fp1=NULL,*fp2=NULL;char input20,output20;char *code;code=(char*)malloc(n*sizeof(char);printf("请输入输入文件名(input.txt)：");scanf("%s",input);if (fp1=fopen(input,"

18、;r")=NULL)printf("无此文件！");getchar();getchar();return ;printf("请输入输出文件名(output.txt)：");scanf("%s",output);if(fp2=fopen(output,"w")=NULL)printf("不能创建文件！");getchar();getchar();return ;int i,j;printf("哈夫曼译码为:");for(i=0;!feof(fp1);i+)*(code

19、+i)=fgetc(fp1);*(code+i+1)='0'for(j=0;j<n;j+)if(strcmp(code,HCj+1)=0)fprintf(fp2,"%d ",HTj+1.weight);printf("%d ",HTj+1.weight);i=-1;break;fclose(fp1); fclose(fp2);printf("n输出完成.按任意键继续.");getchar();getchar();/-初始化哈夫曼树-void int_huffmantree()system("cls&qu

20、ot;);print_title();int *w,i; printf("请输入权值的个数(>1)："); scanf("%d",&n); w=(int*)malloc(n*sizeof(int); / 动态生成存放n个权值的空间 printf("请依次输入%d个权值(整型)：n",n); for(i=0;i<n;i+) scanf("%d",w+i); Huffmantree(w); / 根据w所存的n个权值构造哈夫曼树HT， Huffmancode(); /n个哈夫曼编码存于HC print

21、_end(); printf("哈夫曼编码为：n"); for(i=1;i<=n;i+) printf("%5d: %sn",*(w+i-1),HCi); print_end(); printf("按任意键返回.");getchar();getchar();/-哈夫曼编码菜单-void print_huffmancode()int i;system("cls");print_title(); printf("哈夫曼编码为：n"); for(i=1;i<=n;i+) printf(&q

22、uot;%5d: %sn",HTi.weight,HCi); print_end(); printf("按任意键返回.");getchar();getchar();/-帮助菜单-void print_helpabout()system("cls");print_title();printf(helpsabout);print_end();printf("按任意键返回.");getchar();getchar();/-树形输出菜单-void print_tree()system("cls");print_t

23、itle();printf("哈夫曼树为：n");preorder(2*n-1,0);print_end();printf("按任意键返回.");getchar();getchar();/-选择菜单输出-void print_menu()while(1)int selected=0;system("cls");print_title();printf(menu);print_end();printf(">请选择17");scanf("%d",&selected);if(select

24、ed<1|selected>7)printf("错误的选择！（请输入17）.按任意键继续.");getchar();getchar();switch(selected)case 1:int_huffmantree();break;case 2:print_huffmancode();break;case 3:print_tree();break;case 4:encode();break;case 5:decode();break;case 6:print_helpabout();break;case 7:exit(0);break;void print_title() printf("+=+n"); printf("