课程设计哈夫曼编码.doc

数据结构课程设计报告设计题目 哈夫曼（Huffman）编译码器学院名称 信息工程学院 专 业 班 级 13计本1 姓 名 hhh 学 号 1312219999 目录 一、实验题目-哈夫曼(Huffman)编/译码器 -二、问题描述-三、设计目标-四、需求分析-五、概要设计- 1-系统结构图- 2-各个模块功能的详细描述-六、 详细设计- 1详细代码- a）头文件代码- b）主函数代码- 2系统流程图-七、测试分析-八、使用说明- 1、白盒- 2、黑盒-九、课程设计总结-一 、实验题目 哈夫曼(Huffman)编/译码器二 、问题描述利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。三、设计目标 设计一个程序，该程序可以实现哈夫曼的编码及译码过程。四、需求分析 一个完整的系统应具有以下功能：1) I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值（见下表），建立哈夫曼树，并将它存于文件hfmTree.txt中。2) E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件hfmTree.txt中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。3) D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。4) P：打印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。 5)T：打印哈夫曼树（Tree Printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表 形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中五、 概要设计 1、系统结构功能图 2 各个模块功能的详细描述 int reaData(mytype d)/载入数据 int reaHFData(HuffM d)/从hfmTree.txt文件读取数据 int printData(mytype d) /数据显示 字符 频度 int printHFData(HuffM d) /显示哈夫曼树 字符 编码 int sort(mytype d)/对数据频度大小排序 建哈夫曼树时调用 int sortHMC(HuffM d)/对哈夫曼树字符排序 译码文件时调用 int sort1(bitree* tempN,int n)/对新的数据重新 频度大小排序 建树时调用 bitree * createbt(mytype d)/建哈夫曼树 bitree * destroybt(bitree * head)/销毁哈夫曼树，释放空间 递归调用 void HuffManCoding(bitree *BT, int len,FILE *fp) /哈夫曼树编码 利用 static函数 并写入文件 int printHuffManfile() /输出哈夫曼树 字符 频度 编码 int Encoding(HuffM d)/编码 int Decoding(HuffM d)/编码 void PrintCodeFile() void PreOrderPrint(bitree *HT)六、 详细设计1 详细代码 a）头文件#include "stdio.h" #include "string.h"#define N 30typedef struct hmchar ch;char code20;HuffM;typedef struct schar ch;int frq;mytype;typedef struct btstruct bt *lchild;mytype dt;struct bt *rchild;bitree;int g_flag=0;int Encoding(HuffM d);int PreOrderPrint(bitree *HT);void PrintCodeFile();int Decoding(HuffM d); b）主函数#include "myhead.h"int reaData(mytype d)/载入数据FILE * fp;int i=0;fp=fopen("data.txt","r");if(NULL=fp)return -1;while(!feof(fp)fscanf(fp,"%c",&(di.ch);fscanf(fp,"%d",&(di.frq);fseek(fp,2,SEEK_CUR);i+;if(i=N-2)break;g_flag=1;fclose(fp);return 0;int reaHFData(HuffM d)/从hfmTree.txt文件读取数据FILE * fp;int i=0,td;char c,data20;fp=fopen("hfmTree.txt","r");if(NULL=fp)printf("打开哈夫曼编码数据文件出错。n");return -1;while(1)fscanf(fp,"%c%d%s",&c,&td,data);if(feof(fp)break;/printf("%ct%dt%sn",c,td,data);di.ch=c;strcpy(di.code,data);i+;fseek(fp,2,SEEK_CUR);=g_flag=1;fclose(fp);return 0;int printData(mytype d) /数据显示 字符 频度int i=0;if(g_flag<1)printf("请先载入数据文件。n");return 0;for(;i<N-3;i+)printf("%ct%dn",di.ch,di.frq);return 0;int printHFData(HuffM d) /显示哈夫曼树 字符 编码int i=0;if(g_flag<1)printf("请先载入数据文件。n");return 0;for(;i<N-3;i+)printf("%ct%sn",di.ch,di.code);return 0;int sort(mytype d)/对数据频度大小排序 建哈夫曼树时调用int i,j;mytype temp;if(g_flag<1)printf("请先载入数据文件。n");return 0;for(i=0;i<N-4;i+)for(j=0;j<N-4-i;j+)if(dj.frq>dj+1.frq)temp=dj;dj=dj+1;dj+1=temp;int sortHMC(HuffM d)/对哈夫曼树字符排序 译码文件时调用int i,j;HuffM temp;if(g_flag<1)printf("请先载入数据文件。n");return 0;for(i=0;i<N-4;i+)for(j=0;j<N-4-i;j+)if(dj.ch>dj+1.ch)temp=dj;dj=dj+1;dj+1=temp;int sort1(bitree* tempN,int n)/对新的数据重新 频度大小排序 建树时调用int i,j;bitree* tmp;for(i=0;i<n-1;i+)for(j=0;j<n-1-i;j+)if(tempN-3-n+j->dt.frq>tempN-3-n+j+1->dt.frq)tmp=tempN-3-n+j;tempN-3-n+j=tempN-3-n+j+1;tempN-3-n+j+1=tmp;bitree * createbt(mytype d)/建哈夫曼树bitree* head=NULL;bitree* tempN=NULL;int i=0;if(g_flag<1)printf("请先载入数据文件。n");return 0;sort(d);while(i<N-3)tempi=(bitree *)malloc(sizeof(bitree);tempi->dt=di;tempi->lchild=NULL;tempi->rchild=NULL;i+;i=0;while(i<N-4)head=(bitree *)malloc(sizeof(bitree);head->dt.ch='*'head->dt.frq=tempi->dt.frq + tempi+1->dt.frq;head->lchild=tempi;head->rchild=tempi+1;tempi+1=head;tempi=NULL;sort1(temp,N-i-4);i+;g_flag = 11;return head;bitree * destroybt(bitree * head)/销毁哈夫曼树，释放空间 递归调用bitree *temp;if(head=NULL)return NULL;temp=head;if(head->lchild)head->lchild=destroybt(temp->lchild);if(head->rchild)head->rchild=destroybt(temp->rchild);free(head);head=NULL;return NULL;void HuffManCoding(bitree *BT, int len,FILE *fp) /哈夫曼树编码 利用 static函数 并写入文件 static int a10;int i;if(g_flag<11)printf("请先建立哈夫曼树。n");return 0; if(BT!=NULL)if(BT->lchild=NULL&&BT->rchild=NULL)/printf("字符%c的权值为%d的编码:",BT->dt.ch,BT->dt.frq);fprintf(fp,"%ct%dt",BT->dt.ch,BT->dt.frq);for(i=0;i<len;i+)/printf("%d ",ai);fprintf(fp,"%d",ai);fprintf(fp,"n");/printf("n");elsealen=0;HuffManCoding(BT->lchild, len+1,fp);alen=1;HuffManCoding(BT->rchild, len+1,fp); int menu()int n;printf("*n");printf("字符集和频度操作：n");printf("t1.载入数据文件。n");printf("t2.显示数据。n");printf("t3.排序。n");printf("哈夫曼树操作：n");printf("t4.建立哈夫曼树。n");printf("t5.写入哈夫曼编码文件。n");printf("t6.显示哈夫曼编码文件。n");printf("t7.销毁哈夫曼树。n");printf("哈夫曼编译码操作：n");printf("t8.载入哈夫曼编码。n");printf("t9.显示哈夫曼编码。n");printf("t10.编码ToBeTran文件.n");printf("t11.译码CodeFile文件.n");printf("t12.打印CodeFile文件.n");printf("t13.打印哈夫曼树.n");printf("t14.退出n");printf("*n");printf("请输入选择：");while(1)scanf("%d",&n);if(n>0&&n<15)break;printf("输入错误，请重输：");system("cls");return n;int printHuffManfile() /输出哈夫曼树 字符 频度 编码FILE * fp;char data50,c;int d;fp=fopen("hfmTree.txt","r");if(NULL=fp)printf("打开文件哈夫曼编码错误。n");return -1;while(1)fscanf(fp,"%c%d%s",&c,&d,data);if(feof(fp)break;printf("%ct%dt%sn",c,d,data);fseek(fp,2,SEEK_CUR);fclose(fp);main()mytype dataN=0;HuffM hmdataN=0;int flag;int choose,count;FILE *fp;bitree * bthead=NULL;count=0;g_flag=0;/刚开始时数据为空。while(1)choose=menu();switch(choose)case 1:flag=reaData(data);if(-1=flag)printf("Open data.txt file error!n");return;break;case 2:printData(data);break;case 3:sort(data);break;case 4:bthead=createbt(data);break;case 5:fp=fopen("hfmTree.txt","w+");if(NULL=fp)printf("写入哈夫曼编码错误！n");return;HuffManCoding(bthead,0,fp);g_flag=111;fclose(fp);break;case 6:printHuffManfile();break;case 7:if(g_flag<11)printf("请先建立哈夫曼树。n");break;bthead=destroybt(bthead);g_flag=1;break;case 8:flag=reaHFData(hmdata);if(-1=flag)printf("Open data.txt file error!n");return;sortHMC(hmdata);break;case 9:printHFData(hmdata);break;case 10:Encoding(hmdata);break;case 11:Decoding(hmdata);break;case 12:PrintCodeFile();break;case 13:PreOrderPrint(bthead,count);break;case 14:destroybt(bthead);return 0;break;int Encoding(HuffM d)/编码FILE *fp,*pfc;char data256=0,c;fp=fopen("ToBeTran.txt","r");pfc=fopen("CodeFile.txt","w+");if(NULL=fp)printf("打开文件ToBeTran.txt出错，编码未完成.n");return -1;if(NULL=pfc)fclose(fp);printf("CodeFile.txt出错，编码未完成.n");return -1;while(1)fread(&c,1,1,fp);if(c>='a'&&c<='z')c-=32;if(c>='A'&&c<='Z')/printf("%s",dc-'A'+1.code);fprintf(pfc,"%s",dc-'A'+1.code);else if (c=' ')/printf("%s",d0.code);fprintf(pfc,"%s",d0.code);else/printf("%c",c);fprintf(pfc,"%c",c);/printf("%c",c);if(feof(fp)break;fclose(fp);fclose(pfc);int Decoding(HuffM d)/编码FILE *fp, *pfc;char data20 = 0 ,c;int i;/, flagfp = fopen("ToBeTran.txt", "r");pfc = fopen("TextFile.txt", "w+");if (NULL = fp)printf("打开文件ToBeTran.txt出错，译码未完成.n");return -1;if (NULL = pfc)fclose(fp);printf("TextFile.txt出错，译码未完成.n");return -1;while (1)fread(&c, 1, 1, fp);if (c='1' | c='0')/return 1; for(i=0;i<27;i+)datai=c;while (strcmp(di.code,data)=0)fprintf(pfc,"%c",di.ch);else/printf("%c",c);fprintf(pfc,"%c",c);/printf("%c",c);if (feof(fp)break;fclose(fp);fclose(pfc);return 1;void PrintCodeFile()FILE *fc;int flag; char ch;printf("打印编码后的文件:n ");fc=fopen("CodeFile.txt", "r");if (NULL=fc)printf("打印编码后的文件失败! ");exit(0);flag = 1;while (!feof(fc)ch = fgetc(fc);if (ch = -1)printf("结束打印n");else printf("%c", ch);if (flag <= 49)flag+;elseflag = 1;printf("n");fclose(fc); /关闭文件int PreOrderPrint(bitree *HT,int count)int n = 2 * (N - 3) - 1, i;if(NULL!=HT)for (i = 0; i<count; i+)printf(" ");printf("%c%dn",HT->dt.ch,HT->dt.frq);PreOrderPrint(HT->lchild, +count);PreOrderPrint(HT->rchild, +count);return 1;2 流程图1、 载入数据 2 、hfmTree.txt文件读取数据3、哈夫曼树字符排序 4、建哈夫曼树5、 销毁哈夫曼树 6、哈夫曼树编码 7、译码 8、译码保存 七 、测试分析1、白盒2 黑盒运行结果选择1，载入数据文件 选择2显示数据 选择3，排序 选择2,显示数据选择4建立哈夫曼树，选择5写入哈夫曼编码文件文件，选择6显示哈夫曼编码文件选择7，销毁哈夫曼树，销毁哈夫曼树选择8，载入哈夫曼编码，选择9，显示哈夫曼编码文件选择10编码ToBeTran文件，选择11译码CodeFile文件，选择12.打印CodeFile文件.ToBeTran.txt文件GodeFile.txt文件选择13，打印哈夫曼树选择14，退出八、使用说明运行程序，在菜单界面，根据菜单的提示选择您想要实现的功能： 1：载入数据； 2：数据显示 字符 频度； 3：对数据频度大小排序 建哈夫曼树时调用； 4：建哈夫曼树； 5： 从hfmTree.txt文件读取数据 将编码拷贝到di.code中；6：显示哈夫曼树 字符 频度 编码；7：销毁哈夫曼树，释放空间 递归调用；8：将 hfmTree.txt文件数据载入；9：输出哈夫曼树 字符 编码；10：哈夫曼树编码 利用 static函数 并写入文件；11： 译码；12：打印CodeFile文件；13：打印哈夫曼树； 14：退出系统。九 课程设计总结在本次课程设计过程，我对自己所掌握的知识感到深深地惭愧，当面对本次题目是，我甚至感到手足无措，不知道该如何下手。但是，在经过老师的指导之后，我有了一些思绪，在经过看书及问同学之后，我一次次的努力，终于将本次程序编写完成。对于本次代码，我从开始的完全不理解，到经过反复的思考推敲之后，我对大部分代码都有了一定的理解，虽然还是存在一些小小的疑惑，但我一定会解决。当然，在看老师编写代码的过程中，我懂得了该如何正确的调试代码，而不是像无头苍蝇一样，面对错误，没有任何方法。不论干什么事，我们都要脚踏实地，不能因为一些困难，而半途而废，应该迎难而上，积极地思考，积极的解决，将身边的资源利用起来，丰富自己的知识。