哈夫曼课程设计报告哈夫曼编译码器

1、西安郵電大學数据结构课程设计报告题 目： 哈夫曼编/译码器院系名称： 计算机学院 专业名称： 软件工程班 级： 1101班 学生姓名： 武妍娜学号（8位）： 04113027指导教师： 李培 设计起止时间：2012年12月3日2012年12月14日15 / 15文档可自由编辑打印一. 设计目的1.巩固和加深对数据结构的理解，提高综合运用本课程所学知识的能力；2.深化对算法课程中基本概念、理论和方法的理解；3.巩固构造哈夫曼树的算法；4.设计试验用程序实验哈夫曼树的构造，编码和译码。二. 设计内容利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送

2、端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。试为这样的信息收发站写一个哈夫曼的编/译码器。 主程序模块三概要设计1功能模块图； 编码模块 译码模块 文件模块 密码模块2各个模块详细的功能描述。（1）主程序模块打印菜单；让用户选择是编码还是译码；让用户决定是否观看一些信息。（2） 密码模块void Login()密码函数，用户输入用户名和密码，密码正确方能进入系统，否则重新输入。（3）编码模块void OpenSource s)打开源文件，并将其内容存到s中void Code(char s,char str,char code,int freq,HFMTree *

3、HT,CodeNode HC)编码函数，调用编码所需的所有函数void Search(char s,char str,int freq)查找各个字符，将其存到str中，并统计其出现的频数，即权值，存放在freq中void CreateHFMTree(HFMTree *HT,int freq)创建哈夫曼树void HFMCode(HFMTree HT,CodeNode HC,char str)按左0右1的顺序进行编码AllCode(s,HC,code)将所有字符的编码连起来，存放到code中Save(code)将编码结果保存到文件code.txt中（4）译码模块void DeCode(char

4、code,char str,char ss,HFMTree *HT,CodeNode HC) 译码函数，调用译码所需的所有函数void OpenCode code)打开编码文件Decoding(code,*HT,str,ss)从根结点开始按编码顺序进行译码Save(ss)将译码结果保存到文件decode.txt中查找权值查找字符四详细设计创建哈夫曼树密码1功能函数的调用关系图编码连接编码编码主函数保存编码打开源文件菜单打开文件译码显示哈夫曼信息保存译码译码开始2.各功能函数的数据流程图（1）创建哈夫曼树函数 int i=0;HFMTree p,HT1,HT2;p=*HT=(HFMTree)ma

5、lloc(sizeof(HFMNode);p->next=p->LChild=p->RChild=p->Parent=NULL;i<2n-1 是 否i+;p=*HT;p->next=(HFMTree)malloc(sizeof(HFMNode);p=p->next;p->next=p->LChild=p->RChild=p->Parent=NULL;i+; i<ni<2n-1 否p->weight=freqi;p=p->next;i+; 是Select(*HT,i,&HT1,&HT2);H

6、T1->Parent=HT2->Parent=p;p->LChild=HT1;p->RChild=HT2;p->weight=HT1->weight+HT2->weight;p=p->next; i+;开始（2）编码函数 int i=0;HFMTree q,p=HT; i<n 是HCi.ch=stri;HCi.coden-1='0'i=0; i<nHCi.flag=n-1;p=q;q->Parent!=Null; 否 是q=q->Parent->Lchild HCi.code-HCi.flag=

7、9;0'q=q->Parent; 是 否HCi.code-HCi.flag='1'p=p->next3重点设计及编码（1）密码设计：void Login()char username15;char password9; char c; int i = 0; printf("nn请输入用户名:");gets(username);printf("n请输入密码:"); while (c=getch()!='r') if (i<8 && isprint(c) passwordi+ = c;

8、 putchar('*'); putchar('n'); passwordi = '0'if(!(strcmp(password,"04113027")printf("nn恭喜您，登陆成功!nn欢迎使用该系统!nn");system("pause");elseprintf("nn密码错误,您无权使用该系统!nn请重新输入!nn");system("pause");system("cls");Login();（2） 创建哈夫曼树：

9、void CreateHFMTree(HFMTree *HT,int freq)int i;HFMTree p,HT1,HT2;p=*HT=(HFMTree)malloc(sizeof(HFMNode); p->next=p->LChild=p->RChild=p->Parent=NULL;for(i=1;i<2*n-1;i+)p->next=(HFMTree)malloc(sizeof(HFMNode);p=p->next;p->next=p->LChild=p->RChild=p->Parent=NULL;for(i=0,p

10、=*HT;i<n;i+)p->weight=freqi;p=p->next;for(i=n;i<2*n-1;i+)Select(*HT,i,&HT1,&HT2);HT1->Parent=HT2->Parent=p;p->LChild=HT1;p->RChild=HT2;p->weight=HT1->weight+HT2->weight;p=p->next; 5 测试数据及运行结果1正常测试数据和运行结果 2.异常测试数据及运行结果 六调试情况，设计技巧及体会1 改进方案通过一周的课程设计使我对哈夫曼树以及哈

11、夫曼编码有了更深的认识和理解，也使我更加明白哈夫曼编码译码在信息技术中的重要性和地位。由于时间问题，对于哈夫曼的压缩和解压缩暂时不能实现了。这也是我比较遗憾的一件事了。不过在空闲时间我还会继续研究这个问题的。2体会开始的时候，代码中有许多的错误，让我束手无策，最后我耐心的一步一步慢慢地改正错误才让我看到了希望。在实现文章的读入时， 由于对文件不是太熟悉，只好翻开C语言书本仿照其模式编写。许多的错误让我明白了细心是非常重要的。同时，对于编程者而言，思路清晰也是相当重要的。在适当的时候和同学一起交流探讨是一个十分好的学习机会。及时的向老师请教也是很有帮助的，因为毕竟我们是新手，对于某些问题很难弄清

12、楚。而且，某些错误对于我们来说有时候想半天都弄不来，但老师几下下就搞好了，这样就更加有效地节约了时间。这次课程设计不但让我又学得了一些编程知识，还学会了系统的做一份课程设计报告， 学会了如何更好的画流程图，明白了做事情只有认真，才能真正做得更好！通过这次课程设计，我看清楚了自己的编程功底和动手能力还不如人意，这主要是平时实践太少的缘故。我想，在即将到来的寒假中，我会努力尝试编写一些较大的程序。由于我们是软件工程专业的学生，就应该更加严格要求自己。七参考文献1. 耿国华主编，数据结构C语言描述，高等教育出版社，2005年2. 陈锐，数据结构（C语言版），清华大学出版社 2012年8 附录#inc

13、lude <stdio.h> #include <stdlib.h>#include <string.h> #include <conio.h>#include <ctype.h>#define M 500 #define N 128typedef struct node int weight;/权值struct node *Parent,*LChild,*RChild;/双亲结点，左孩子结点，右孩子结点struct node *next;/下一个结点HFMNode,*HFMTree;typedef struct char ch;/字

14、符 char codeN+1;/编码 int flag;/标记CodeNode;int n;/叶子结点个数/密码void Login()char username15;char password9; char c; int i = 0; printf("nn请输入用户名:");gets(username);printf("n请输入密码:"); while (c=getch()!='r') if (i<8 && isprint(c) passwordi+ = c; putchar('*'); putch

15、ar('n'); passwordi = '0'if(!(strcmp(password,"04113027")printf("nn恭喜您，登陆成功!nn欢迎使用该系统!nn");system("pause");elseprintf("nn密码错误,您无权使用该系统!nn请重新输入!nn");system("pause");system("cls");Login();void Menu(void)/菜单printf("tt*n&quo

16、t;);printf("tt* *n");printf("tt* 欢迎进入 *n");printf("tt* 哈夫曼编/译码系统 *n");printf("tt* *n");printf("tt* 1.显示源文件。 *n");printf("tt* 2.编码。 *n");printf("tt* 3.译码。 *n");printf("tt* 4.显示哈夫曼信息。 *n");printf("tt* 0.退出。 *n");

17、printf("tt* *n");printf("tt*n");printf("tt* *n");printf("tt* 请输入相应操作的序号(0-3) *n");printf("tt* *n");printf("tt*n");/打开源文件void OpenSource s)FILE *fp;int i=0;system("cls");if(fp=fopen("source.txt","rt")=NULL)/打开文件

18、source.txtprintf("打开文件失败！n");exit(1);si+=fgetc(fp);while(si-1!=EOF)/将文件中的字符串存入s中si+=fgetc(fp);si='0' fclose(fp);/存储文件void Save(char s)char name10;FILE *fp;printf("请输入要保存的文件名：");gets(name);if(fp=fopen(name,"wt")=NULL) printf("存储文件失败！n");exit(1);fputs(s,

19、fp);printf("n文件保存成功，文件名为:%s。nn",name);system("pause");fclose(fp);void Search(char s,char str,int freq)/查找各个字符，并统计其出现的频数int i,j,k=0;for(i=0;i<N;i+)/初始化freq freqi=0; for(i=0;si;i+)for(j=0;j<k;j+)/统计各个字符出现的频数，即权值，并将其存放在freqif(strj=si) freqj+; break; if(j=k)/查找各个字符，并将其存放在str中 s

20、trk=si;freqk+; strk='0'n=k-1;/n为查找后字符的总个数void Select(HFMTree HT,int k,HFMTree *HT1,HFMTree *HT2)/查找权值最小的两个结点inti,min;HFMTreep;min=1000;for(i=0,p=HT;i<k;i+,p=p->next)/查找权值最小的结点if(p->weight<min&&p->Parent=0)min=p->weight;*HT1=p;min=1000;for(i=0,p=HT;i<k;i+,p=p->

21、next)/查找权值次小的结点if(p->weight<min&&p->Parent=0&&p!=*HT1)min=p->weight;*HT2=p;void CreateHFMTree(HFMTree *HT,int freq)/创建哈夫曼树int i;HFMTree p,HT1,HT2;p=*HT=(HFMTree)malloc(sizeof(HFMNode); /申请空间p->next=p->LChild=p->RChild=p->Parent=NULL;/初始化for(i=1;i<2*n-1;i+)/

22、申请空间，并初始化所有结点，共2n-1个p->next=(HFMTree)malloc(sizeof(HFMNode);p=p->next;p->next=p->LChild=p->RChild=p->Parent=NULL;for(i=0,p=*HT;i<n;i+)/给前n个结点赋权值p->weight=freqi;p=p->next;for(i=n;i<2*n-1;i+)/开始创建哈夫曼树Select(*HT,i,&HT1,&HT2);/查找权值最小的两个结点HT1->Parent=HT2->Paren

23、t=p;p->LChild=HT1;p->RChild=HT2;p->weight=HT1->weight+HT2->weight;/更改双亲结点的权值p=p->next; void HFMCode(HFMTree HT,CodeNode HC,char str)/编码int i; HFMTree q,p=HT; for(i=0;i<n;i+)HCi.ch=stri;HCi.coden-1='0'/处理编码的结束符for(i=0;i<n;i+)/开始解码HCi.flag=n-1;/根结点for(q=p;q->Parent;q

24、=q->Parent)if(q=q->Parent->LChild)HCi.code-HCi.flag='0'/左0else HCi.code-HCi.flag='1'/右1 p=p->next; void AllCode(char s,CodeNode HC,char code)/所有的编码int i,j;code0='0'for(i=0;si;i+)for(j=0;j<n;j+) if(si=HCj.ch)strcpy(code+strlen(code),HCj.code+HCj.flag);/将所有字符的编码连

25、接起来存放到code中 void Decoding(char code,HFMTree HT,char str,char ss)/译码int i,j,k=0;HFMTree root,p,q; for(root=HT;root->Parent;root=root->Parent); /从根结点开始按编码顺序进行译码for(i=0,p=root;codei;i+)if(codei='0')p=p->LChild; elsep=p->RChild;if(p->LChild=NULL&&p->RChild=NULL)for(j=0,

26、q=HT;q!=p;q=q->next,j+); ssk+=strj;/到根结点时将该字符存放到ss中p=root;/回到根结点 ssk='0' void Code(char s,char str,char code,int freq,HFMTree *HT,CodeNode HC) /编码函数 system("cls");Search(s,str,freq);/查找各个字符，并统计其出现的频数CreateHFMTree(HT,freq);/创建哈夫曼树HFMCode(*HT,HC,str);/编码AllCode(s,HC,code);/将各个字符的编

27、码连起来printf("n哈夫曼编码为:nn");puts(code);/输出编码printf("n保存编码,"); Save(code);void DeCode(char code,char str,char ss,HFMTree *HT,CodeNode HC) /译码函数FILE *fp;int i=0;system("cls");if(fp=fopen("code.txt","rt")=NULL)/打开编码文件code.txtprintf("打开文件失败！n");ex

28、it(1);fclose(fp);Decoding(code,*HT,str,ss);/译码 printf("n译码后的字符串为:nn"); puts(ss);/输出译码后的字符串printf("n保存译码，");Save(ss);/将创建好的哈弗曼树的字符，权值和密码存入文件hfmtree.txt中void HFM freq,CodeNode HC)int i;FILE *fp;if (fp=fopen("hfmtree.txt","wt")=NULL)printf("打开文件出错！n");exit(0);for(i=0;i<n;i+)fprintf(fp,"%ct%dt%sn",HCi.ch,freqi,&(HCi.codeHCi.flag);printf("n哈夫曼树创建成功，并已存入文件hfmtree.txt中。nn");fclose(fp);void main() char sM;/存放从文件source.txt中读取的字符串char ssM;/存放译码后的字符串char s