数据结构课程设计赫夫曼编码译码器

数据结构与算法 课程设计（2013/2014学年第一学期17周）班级： 学号： 姓名：指导教师： 杨东鹤 王敏丽目 录一、 题目二、 需求分析三、 概要设计四、 程序说明五、 详细设计六、 实验心得与体会七、 备注一、题目：赫夫曼编码/译码器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个代码。同时将此字符形式的编码文件写入文件CodePrin中。(5) T：印赫夫曼树（Tree printing）。将已在内存中的赫夫曼树以直观的方式（比如树）显示在终端上，同时将此字符形式的赫夫曼树写入文件TreePrint 中。3. 测试要求(1) 已知某系统在通信联络中只可能出现八种字符，其频率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，试设计赫夫曼编码。(2) 用下表给出的字符集和频度的实际统计数据建立赫夫曼树，并实现以下报文的编码和译码：“THIS PROGRAME IS MY FAVORITE”。字符 ABCDEFGHIJKLM频度1866413223210321154757153220字符NOPQRSTUVWXYZ频度57631514851802381811614. 实现提示(1) 编码结果以文本方式存储在文件Codefile中。(2) 用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“Q”为止。(3) 在程序的一次执行过程中，第一次执行I，D或C命令之后，赫夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。二、需求分析：数据结构与算法是计算机专业重要的核心课程之一，在计算机专业的学习过程中占有非常重要的地位。数据结构与算法课程设计就是要运用本课程以及到目前为止的有关课程中的知识和技术来解决实际问题。特别是面临非数值计算类型的应用问题时，需要选择适当的数据结构，设计出满足一定时间和空间限制的有效算法。本课程设计要求同学独立完成一个较为完整的应用需求分析。并在设计和编写具有一定规模程序的过程中，深化对数据结构与算法课程中基本概念、理论和方法的理解；训练综合运用所学知识处理实际问题的能力，强化面向对象的程序设计理念；使自己的程序设计与调试水平有一个明显的提高。 三、概要设计：开始退出建哈弗曼树哈弗曼译码哈弗曼编码DecodingCodingInitHuffmanCodingselect结束四、程序说明：（1） typedef struct/哈夫曼树结点结构（2） int weight; （3） char data; /存放该节点的字符（4） int parent,lchild,rchild;（5） HTNode,*HuffmanTree;（6） typedef char* HuffmanCode; /指向哈夫曼编码的指针（7） void HuffmanCoding(HuffmanTree &,char *,int *,int);/建立哈夫曼树（8） void select(HuffmanTree HT,int j,int *s1,int *s2); /选择parent为0且weight最小的两个结点（9） void Init(); /初始化（10） void Coding(); /编码（11） void Decoding(); /译码（12） void find(HuffmanTree &HT,char *code,char *text,int i,int m);/寻找相应叶子节点的递归算法（13） HuffmanTree HT; /指向存放哈夫曼树的存储空间（14） int n=0; /哈夫曼树叶子结点数目（15） int main()/主函数五、详细设计：/*主函数*/int main()char select;while(1)printf(n*-*-*n);printf(tttt请输入操作:n);printf(n);printf(ttttI-建哈夫曼树n);printf(ttttC-哈夫曼编码n);printf(ttttD-哈夫曼译码n);printf(ttttQ-退出n);printf(ntttt);scanf(%c,&select);switch(select)case I:Init();break;case C:Coding();break;case D:Decoding();break;case Q:exit(1);default :printf(操作错误n);getchar();return 0;/*初始化函数，输入n个字符及其对应的权值，根据权值建立哈夫曼树*/void Init() FILE *fp;int i,w52; /w数组存放n个字符的权值char character52; /存放n个字符printf(ntttt输入字符个数 n:);scanf(%d,&n); /输入字符集个数printf(tttt输入%d个字符及其对应的权值n,n);for(i=0;in;i+)char b=getchar();/读入空格scanf(%c,&characteri);scanf(%d,&wi); /输入个字符和对应的权值HuffmanCoding(HT,character,w,n); /建立哈夫曼树if(fp=fopen(hfmtree.txt,w)=NULL) /建立新文件进行只写printf(hfmtree.txt打开失败!n);for(i=1;i=2*n-1;i+)if(fwrite(&(HTi.data),sizeof(char),1,fp)!=1)printf(写入文件失败!n);if(fwrite(&(HTi.weight),sizeof(int),1,fp)!=1)printf(写入文件失败!n);if(fwrite(&(HTi.parent),sizeof(int),1,fp)!=1)printf(写入文件失败!n);if(fwrite(&(HTi.lchild),sizeof(int),1,fp)!=1)printf(写入文件失败!n);if(fwrite(&(HTi.rchild),sizeof(int),1,fp)!=1)printf(写入文件失败!n);printf(n哈夫曼树建立成功，已将其存于hfmtree.txtn);fclose(fp);/建立哈夫曼树的算法void HuffmanCoding(HuffmanTree &HT,char *character,int *w,int n)int m,i,s1,s2;HuffmanTree p;if(n=1)return;m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);for(p=HT+1,i=1;idata=*character;p-weight=*w;p-parent=0;p-lchild=0;p-rchild=0;/给前面个节点赋初值，p、character、w指针后移向下一个叶节点for(;idata=0;p-weight=0;p-parent=0;p-lchild=0;p-rchild=0;/给后面要生成的节点赋初值全为0for(i=n+1;i=m;+i)select(HT,i-1,&s1,&s2);/从HT1到HTi-1中选择parent为0且weight最小的两个?结点，用s1和s2返回其序号HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;/把最小值赋给s1次小值赋给s2HTi.weight=HTs1.weight+HTs2.weight;/生成新节点/*从HT1到HTj中选择parent为0且weight最小的两个结点，用s1和s2返回其序号*/void select(HuffmanTree HT,int j,int *s1,int *s2)int i;for(i=1;i=j;i+) if(HTi.parent=0)*s1=i;break;/有个没访问过的就跳出循环，以此为起点比较for(;i=j;i+)if(HTi.parent=0)&(HTi.weightHT*s1.weight)*s1=i;/则s1为最小结点的序号HT*s1.parent=1;/提前给HT*s1.parent赋值1，以免找次小结点、判断条件时受影响for(i=1;i=j;i+)if(HTi.parent=0)*s2=i;break;/有一个没访问过的就跳出循环，以此为起点比较for(;i=j;i+)if(HTi.parent=0)&(i!=*s1)&(HTi.weightHT*s2.weight)*s2=i; /找weight次小的结点void Coding() FILE *fp,*fw;int i,f,c,start;char *cd;HuffmanCode HC;/*以下程序段求赫夫曼树中各叶子节点的字符对应的编码，并存于HC指向的空间中*/HC=(HuffmanCode)malloc(n+1)*sizeof(char*);cd=(char *)malloc(n*sizeof(char);cdn-1=0;for(i=1;i=n;+i)start=n-1;/为了后面HC空间的分配中的n-start，没有编码就只分配一个sizeof空间，即结束符，即n-(n-1)=1for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c)cd-start=0;elsecd-start=1;HCi=(char *)malloc(n-start)*sizeof(char);/为第i个字符编码分配空间，用于下面语句的赋值strcpy(HCi,&cdstart);/取首地址开始赋值free(cd);if(fp=fopen(tobetran.txt,rb)=NULL)/打开文件进行只读printf(tobetran.txt打开失败!n);if(fw=fopen(codefile.txt,wb+)=NULL)/建立新文件进行读/写printf(codefile.txt打开失败!n);char temp;fscanf(fp,%c,&temp); /从fp所指的文件中读入第一个字符到temp变量while(!feof(fp)for(i=1;i=n;i+)if(HTi.data=temp)break; /若和1号节点相同则跳出循环，否则继续查找for(int r=0;HCir!=0;r+) /在哈夫曼树中查找字符所在的位置fputc(HCir,fw); /将字符对应的编码存入文件，把HCir写到fw所指示文件fscanf(fp,%c,&temp); /从文件读入下一个字符fclose(fw);fclose(fp);printf(nhfmtree.txt编码成功，已将其存于codefile.txtn);void Decoding() FILE *fp,*fw;int m,i;char *code,*text,*p;if(fp=fopen(codefile.txt,rb)=NULL)/打开文件进行只读printf(codefile.txt打开失败!n);if(fw=fopen(textfile.txt,wb+)=NULL)/建立新文件读/写,若已建立，内容会清空printf(textfile.txt打开失败!n);code=(char *)malloc(sizeof(char);fscanf(fp,%c,code); /从文件读入一个0或1字符for(i=1;!feof(fp);i+)code=(char *)realloc(code,(i+1)*sizeof(char); /增加空间，把code所指示的空间大小设置为(i+1)*sizeof(char)fscanf(fp,%c,&codei); /从文件读入下一个0或1的字符/至此codefile.txt文件中的0、1已全部读入，存放在code数组中text=(char *)malloc(100*sizeof(char);p=text;m=2*n-1;if(*code=0)find(HT,code,text,HTm.lchild,m); /从根节点的左子树找elsefind(HT,code,text,HTm.rchild,m); /从根节点的右子树找for(i=0;pi!=0;i+) /把译码好的字符存入文件textfile.txt中fputc(pi,fw);/把pi写到fw所指示的文件中fclose(fp);fclose(fw);printf(ncodefile.txt译码成功，已将其存于textfile.txtn);/*译码时根据01字符串寻找相应叶子节点的递归算法*/void find(HuffmanTree &HT,char *code,char *text,int i,int m)if(*code!=0) /若译码未结束code+;if(HTi.lchild=0&HTi.rchild=0) /若找到叶子节点*text=HTi.data; /将叶子节点字符存入text中text+;if(*code=0)find(HT,code,text,HTm.lchild,m); /继续从根节点的左子树找elsefind(HT,code,text,HTm.rchild,m); /继续从根节点的右子树找else /如果不是叶子节点if(*code=0)find(HT,code,text,HTi.lchild,m); /从该节点左子树找elsefind(HT,code,text,HTi.rchild,m); /从该节点右子树找else*text=0; /译码结束六、调试分析：由所给字符和权值建立哈弗曼树：由所建立的哈弗曼树编码hfmtree.txt:由哈弗曼树和哈弗曼编码译码codefile.txt:七、实验心得与体会：初始的创建是哈夫曼编码译码系统成功的关键，结点字符或者权重信息，作为检验，对验证和纠错起到了非常大的作用。在适当的地方调用它们，运行时可以看到验证编写程序的正确性；通过本次实验，提高了自已调试程序的能力。充分体会到了在程序执行时的提示性输出的重要性。编写大一点的程序，应先写出算法，再写程序，一段一段调试；对于没有实现的操作用空操作代替，这样容易找出错误所在。最忌讳将所有代码写完后再调试，这样若程序有错误，太难找。需要特别强调的是：1感觉文件操作自己并不是很熟练，尽管在向显示器输出的时候并没有什么错误但是读写文件的时候就没那么顺利了，是文件没有打开或者文件结束的缘故。2.用哈夫曼编码存储文件的时候还应注意数字0,1与字符0,1的不同，0在ASCII码中代表NULL。3.该程序函数清晰功能明确，程序具有通用性，对于不同的输入文章都可进行处理，由于采用哈夫曼编码对照表，使得查看哈夫曼编码是效率较高无需每次遍历哈夫曼树八、备注：一、具体要求：课程设计成果的内容必须由以下四个部分组成，缺一不可。(1) 上交源程序：学生按照实验题目的具体要求所开发的所有源程序（应该放到一个文件夹中）；(2) 上交程序的说明文件：（保存在.txt中）在说明文档中应该写明上交程序所在的目录，上交程序的主程序文件名，如果需要安装，要有程序的安装使用说明；(3) 设计报告：（保存在word 文档中，文件名要求： 按照“姓名_学号_设计题目”起名，如文件名为“ 张三_XXX_哈夫曼编码 ”.doc。打印稿用A4纸）。其中包括: 题目； 实验目的； 需求分析： 在该部分中叙述实现的功能要求； 概要设计：在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义）； 详细设计各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现）。源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量、重点功能部分要加上清晰的程序注释； 调试分析测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想； 总结： 总结可以包括 : 设计过程的收获、遇到问题及解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在设计过程中对数据结构课程的认识等内容。二、工作内容及工作计划：一周（17）时间地点工作内容指导教师12月 23日上午10-306实验要求，需求分析； 杨东鹤、王敏丽下