数据结构课程设计-哈夫曼（Huffman）编译码器.doc

数据结构课程设计报告设计题目 哈夫曼（Huffman）编译码器学院名称 信息工程学院 专 业 班 级 13计本1 姓 名 hhh 学 号 1312219999 目录 一、实验题目-哈夫曼(Huffman)编/译码器 -二、问题描述-三、设计目标-四、需求分析-五、概要设计- 1-系统结构图- 2-各个模块功能的详细描述-6、 详细设计- 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中5、 概要设计 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)6、 详细设计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.hint 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_flag1)printf(请先载入数据文件。n);return 0;for(;iN-3;i+)printf(%ct%dn,di.ch,di.frq);return 0;int printHFData(HuffM d) /显示哈夫曼树 字符 编码int i=0;if(g_flag1)printf(请先载入数据文件。n);return 0;for(;iN-3;i+)printf(%ct%sn,di.ch,di.code);return 0;int sort(mytype d)/对数据频度大小排序 建哈夫曼树时调用int i,j;mytype temp;if(g_flag1)printf(请先载入数据文件。n);return 0;for(i=0;iN-4;i+)for(j=0;jdj+1.frq)temp=dj;dj=dj+1;dj+1=temp;int sortHMC(HuffM d)/对哈夫曼树字符排序 译码文件时调用int i,j;HuffM temp;if(g_flag1)printf(请先载入数据文件。n);return 0;for(i=0;iN-4;i+)for(j=0;jdj+1.ch)temp=dj;dj=dj+1;dj+1=temp;int sort1(bitree* tempN,int n)/对新的数据重新 频度大小排序 建树时调用int i,j;bitree* tmp;for(i=0;in-1;i+)for(j=0;jdt.frqtempN-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_flag1)printf(请先载入数据文件。n);return 0;sort(d);while(idt=di;tempi-lchild=NULL;tempi-rchild=NULL;i+;i=0;while(idt.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_flaglchild=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;ilchild, 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(n0&n15)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=a&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;i27;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; idt.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显示哈