哈夫曼编码课_程_设_计_报_告

1、课 程 设 计 报 告题目： 哈夫曼编码 院 系： 计算机科学与应用系 专业年级： 计算机科学与技术 学 号： 学生姓名： 指导老师： 2013年06月25日目 录1设计任务书31.1题目与要求31.2涉及知识点31.3输入输出分析31.4测试数据分析32概要设计4 2.1结构体类型定义及函数声明4 2.2主程序流程5 3详细设计73.1数据类型实现73.2程序伪码3.3程序主要流程图4调试分析 4.1问题分析及回顾 4.2算法时空分析 4.3设想改进 4.4经验和体会5用户使用说明 5.1操作说明及详细步骤6测试结果 6.1测试数据及结果7参考文献8致谢1、 设计任务书 1.1题目与要求 题

2、目：哈夫曼编码要求：1、I：初始化（Initialization），从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。2、E：编码（Encoding），利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读人），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。3、D：译码（Decoding），利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。4、P：输出代码文件（Print），将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件C

3、odePrin中。5、T：输出哈夫曼树（TreePrinting），将已在内存中的哈夫曼树以直观的方式（树或凹人表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。1.2设计知识点哈夫曼树的建立，哈夫曼编码的生成，对编码信息的翻译，文件、结构体、指针、链表、数组、循环语句、选择语句、输入输出控制等。1.3输入输出分析对于用户输入数据进行存储，统计各字符出现的频率，然后通过Huffman编码得到的各种字符的Huffman编码。此时程序需要输入一串Huffman代码串。输入完毕程序会判断输入的代码串是否合法，若合法则输出译码结果。1.4测试数据分析用下表给出的字符集和频度

4、的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“aabbccdd”。字符 a b c d e f g h ij k l m n o p q r s t u v w x y z权值 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 262、 概要设计2.1结构体类型及函数声明1. 哈夫曼树类型（树形结构）：void main(void) int i; void settree(void); /建立树 void code(void); /对文件编码 void decode(void); / 译码 void

5、disp(void); root=(struct node*)malloc(sizeof(struct node); puts(*哈夫曼编/译码器演示*);2. 建立编码void settree(void) int i,j,k; struct node *p1,*p2,*tmp,*p; void go(struct node *); void setcode(struct node *);/建立每一个字符的编码 void printtree(struct node *); puts(输入字符集的大小：); scanf(%d,&n); while(getchar()!=n) continue;3

6、. 详细设计3.1数据类型实现1、哈夫曼编码采用一个字符串数组存储。2、用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“Q”为止。3、在程序的一次执行过程中，第一次执行I、D或C命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。3.Main函数流程图开始构造haffman树生成haffman编码译码输入字符串;存在相应代码串结束NY 图2main函数流程图flag=0YN4. 问题分析及回顾4.1问题一：哈夫曼树的建立问题二

7、：编译进行4.4经验与体会此次课程设计，我编写程序的时候遇到了不少问题，在攻克这些问题，最终实现课题任务的过程中，我学到了不少东西：首先，在完成一个课题之前，要仔细理解课题要求。通过这次课程设计，我更加深入了理解了哈夫曼编码的过程，以及利用哈夫曼编码对数据进行压缩的优越性，并且使我能够更熟练地运用树形的数据结构。并且体会到了在学习中，要严格要求自己，不能因为一点点的成功就骄傲自满，停止不前。5用户使用说明进入程序：图 1.程序开始程序提示：图2. 输入字符集的大小输入编译7. 参考文献1.数据结构（C语言描述）；出版社：中国水利水电出版社；主编：马秋菊；2.严蔚敏 数据结构（C语言版） 清华大

8、学出版社 ；百度文库源程序：#include#include#include#include int n; struct node int w; int flag; char c; struct node *plink,*llink,*rlink; char code20; *num20,*root; FILE *fp; char tmpcode20; int t=0;void main(void) int i; void settree(void); /建立树 void code(void); /对文件编码 void decode(void); / 译码 void disp(void); r

9、oot=(struct node*)malloc(sizeof(struct node); puts(*哈夫曼编/译码器演示*); while(1)start: puts(1. 初始化 2.显示编码表 3. 退出); while(scanf(%d,&i)!=1) while(getchar()!=n) continue; puts(输入错误!); puts(请重新输入！); puts(1. 初始化 2.显示编码表 3. 退出); switch (i) case 1: settree(); break; case 2: disp(); break; case 3: exit(0); break;

10、 default: puts(输入错误！); puts(请重新输入！); goto start; void settree(void) int i,j,k; struct node *p1,*p2,*tmp,*p; void go(struct node *); void setcode(struct node *);/建立每一个字符的编码 void printtree(struct node *); puts(输入字符集的大小：); scanf(%d,&n); while(getchar()!=n) continue; for(i=0;ic); while(getchar()!=n) con

11、tinue; puts(请输入该字符的权值:); scanf(%d,&p-w); while(getchar()!=n) continue; p-plink=NULL; p-rlink=NULL; p-llink=NULL; numi=p; for(i=0;in-1;i+) /（递增）排序 for(j=i+1;jwnumj-w) tmp=numi; numi=numj; numj=tmp; /*开始建立树*/ numn=NULL; /结束标志 k=n; while(num1!=NULL) p=(struct node *)malloc(sizeof(struct node); p1=num0;

12、 p2=num1; p-llink=p1; p-rlink=p2; p-plink=NULL; p1-plink=p; p2-plink=p; p-w=p1-w+p2-w; for(i=1;ik;i+) numi=numi+1; k-; num0=p; for(i=0;ik-1;i+) /排序 for(j=i+1;jwnumj-w) tmp=numi; numi=numj; numj=tmp; root=num0; /*建立完毕*/ /*写入文件，前序*/ if(fp=fopen(c:hfmtree.wxl,wb)=NULL) puts(文件打开错误！); getchar(); exit(0)

13、; setcode(root); go(root); fclose(fp);void setcode(struct node *p) if(p-llink=NULL&p-rlink=NULL) tmpcodet=0; strcpy(p-code,tmpcode); else tmpcodet+=0; setcode(p-llink); t-; tmpcodet+=1; setcode(p-rlink); t-; void go(struct node *p) if(p-llink=NULL&p-rlink=NULL) fputc(,fp); fputc(p-c,fp); fputs(p-cod

14、e,fp); fputc(),fp); else go(p-llink); go(p-rlink); void code(void) FILE *fp1,*fp2,*fp3; char ch1,ch2,c; if(fp1=fopen(c:hfmtree.wxl,rb)=NULL) puts(文件打开错误！); getchar(); exit(0); if(fp2=fopen(c:tobetrans.txt,wb)=NULL) puts(文件打开错误！); getchar(); exit(0); if(fp3=fopen(c:codefile.wxl,wb)=NULL) puts(文件打开错误！

15、); getchar(); exit(0); while(ch1=fgetc(fp2)!=EOF) t=0;while(ch2=fgetc(fp1)!=EOF) if(ch1=ch2) while(c=fgetc(fp1)!=) tmpcodet+=c; tmpcodet=0; fputs(tmpcode,fp3); fputc(,fp3); rewind(fp1); break; fclose(fp1); fclose(fp2); fclose(fp3);void decode(void) FILE *fp1,*fp2,*fp3; char ch1,ch2,ch3; char temp_32

16、0; char temp_120; int t1,t3; if(fp1=fopen(c:hfmtree.wxl,rb)=NULL) puts(文件打开错误！); getchar(); exit(0); if(fp2=fopen(c:textfile.txt,wb)=NULL) puts(文件打开错误！); getchar(); exit(0); if(fp3=fopen(c:codefile.wxl,rb)=NULL) puts(文件打开错误！); getchar(); exit(0); while(ch3=fgetc(fp3)!=EOF) t3=0; while(ch3!=) temp_3t

17、3+=ch3; ch3=fgetc(fp3); temp_3t3=0; while(ch1=fgetc(fp1)!=EOF) if(isalpha(ch1) ch2=ch1; t1=0; while(ch1=fgetc(fp1)!=) temp_1t1+=ch1; temp_1t1=0; if(strcmp(temp_1,temp_3)=0) fputc(ch2,fp2); rewind(fp1); break; fclose(fp1); fclose(fp2); fclose(fp3);void disp(void) FILE *fp1,*fp2; char ch1,ch2; char tm

18、p20; int t; if(fp1=fopen(c:hfmtree.wxl,rb)=NULL) puts(文件打开错误！); getchar(); exit(0); if(fp2=fopen(c:hfmcode.txt,wb)=NULL) puts(文件打开错误！); getchar(); exit(0); while(ch1=fgetc(fp1)!=EOF) if(ch1=() t=0; ch1=fgetc(fp1); ch2=ch1; while(ch1=fgetc(fp1)!=) tmpt+=ch1; tmpt=0; printf(%c-%sn,ch2,tmp); fputc(ch2,fp2); fputc(-,fp2); fputc(-,fp2); fputc(-,fp2); fputs(tmp,fp2); fputc(n,fp2); fclose(fp1); fclose(fp2);数据结构课程设计评分标准课程名称：数据结构课程设计 指导教师：姓名性别学号班级程序运行情况（占总成绩20%） 能正确运行（20分） 基本能正确运行（15分）能运行但结果不完善（10分） 程序功能的完善程度（占总成绩10%）完善（10分） 基本完善（8分） 不完善（5分）程序结构的