《数据结构与算法》课程设计成果报告-赫夫曼编码的相关函数库实现.doc

河南工程学院数据结构与算法课程设计成果报告赫夫曼编码的相关函数库实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程 1342 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目赫夫曼编码的相关函数库实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录1 课程设计目标与任务41.1 课程设计目标41.2 课程设计任务41.3 课程设计基本要求42 分析与设计52.1 题目需求分析52.2 存储结构设计52.3 算法描述52.4 程序流程图62.5 测试程序说明73 程序清单84 测试184.1 测试数据184.2 测试结果分析235 总结24参考文献251 课程设计目标与任务1.1 课程设计目标通过本课程设计，使学生在数据结构的选择和应用、算法的设计与实现方面得到训练，加深对数据结构基本内容的理解和灵活应用，同时，在程序设计方法及上机操作方面受到比较系统严格的训练，培养软件工作所需要的动手能力。1.2 课程设计任务设计赫夫曼编码的相关函数库，以便在程序设计中调用，要求：（1）任意输入100个英文字母，根据每个字母的使用频率，构造赫夫曼树并输出每个字母的赫夫曼编码。（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。1.3 课程设计基本要求严格按照题意要求，独立进行设计，不能随意更改。若确因条件所限，必须要改变课题要求时，应在征得指导教师同意的前提下进行。学生应制定设计工作计划，认真完成设计的各个环节，并在老师的指导下认真组织设计工作，撰写设计做好设计总结。2 分析与设计2.1 题目需求分析1.我们需要一个功能函数对ASCII码的初始化并需要一个数组来保存们。2.定义代表森林的数组，在创建哈夫曼树的过程当中保存被选中的字符，即给定报文中出现的字符,模拟哈夫曼树选取和删除左右子树的过程；3.自底而上地创建哈夫曼树，保存根的地址和每个叶节点的地址，即字符的地址，然后自底而上检索，首尾对换调整为哈夫曼树实现哈弗曼编码；4.从哈弗曼编码文件当中读入字符，根据当前字符为0或者1的状况访问左子树或者右孩子，实现解码；2.2 存储结构设计在文件huffmantree.h中定义赫夫曼树以及其所需的函数内容。在HuffmanTree.cpp中定义主程序来实现及测试。2.3 算法描述创建哈夫曼树的描述：先把三叉链表中1-N个元素进行初始化，存放叶子节点，他们都没有孩子和双亲。2.再初始化后n-1个非叶子节点元素。3.从当前森林中（在森林中树的根节点的双亲为0）选择两棵根的权值最小的树；删除合并是将选到的两棵树的根权和存入数组当前最前面的空闲元素中，并置入相应的双亲与孩子的位置。4.重复上述步骤直到森林中只含有一棵二叉树为止。哈夫曼树编码的描述：申请存储哈夫曼编码串的头指针数组，申请一个字符型指针，用来存放临时的编码串；2.从叶子节点开始向上倒退，若其为它双亲节点的左孩子则编码标0，否则标1；直到根节点为止，最后把临时存储编码复制到对应的指针数组所指向的内存中；3.重复上述步骤，直到所有的叶子节点都被编码完。哈夫曼树译码的描述：从根结点开始向下递推，若其编码当前的数值为0，则到该节点的左孩子，否则转到其右孩子；重复上述步骤直到该编码中全部访问完，则树中对应的叶子节点则为所求2.依据上述步骤，对编码数组中所有编码全部进行译码。2.4 程序流程图程序流程如图2.4-1所示：图2.4-1程序流程图程序流程经历生成生成随机文件、随机概率、生成哈夫曼树、进行哈夫曼编码、进行哈夫曼译码五个步骤进行。2.5 测试程序说明测试程序定义于HuffmanTree.cpp中，用于定义所用main函数以及对算法的测试。定义choose用来对所需操作的选择。使用switch函数来构成整个main函数的主体部分。当输入17时分别对应如下操作：1.生成文件2.显示概率3.生成哈夫曼编码树及哈夫曼编码4.哈夫曼编码5.显示码文6.译码并输出7.退出3 程序清单程序使用C+语言在VC+6.0中编译通过，赫夫曼树所用函数存储于头文件huffmantree.h中，以结构体形式定义赫夫曼树并辅以函数。测试及使用函数定义于Huffmantree.cpp中，以switch函数作为main函数主体结构包含所实现的各种功能。/huffmantree.h#include#include#include#define Status int#define OK 1#define ERROR 0#define random(x) (rand()%x)/定义结构体typedef structdouble weight;unsigned int parent,lchild,rchild;char ch;HTNode, *HuffmanTree;typedef char *HuffmanCode;using namespace std;/生成随机文件Status CreatRandomNum()srand(time(NULL);fstream file;file.open(random.txt,ios:binary|ios:out);int RNum10000;for(int i=0;i10000;i+)RNumi=random(10);fileRNumi;file.close();puts(随机数已产生，保存在程序目录下的random.txt);return OK;/生成概率并显示Status GeHuffmanPos(double *n)ifstream file(random.txt);if(file.fail()return ERROR;char temp;while(file.get(temp)int t;t=(int)temp-48;nt+=1;file.close();for(int i=0;i10;i+)ni/=10000;cout(ni)endl;return OK;void Select(HuffmanTree HT,int t,int &s1,int &s2)int i;double m,n;m=n=1; for(i=1;i=t;i+)if(HTi.parent=0&(HTi.weightm|HTi.weightn)if(ms2) /s1放较小的序号i=s1;s1=s2;s2=i;/生成赫夫曼树Status HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,double *w,int n,Status &Huffcode)if(w0=0)return ERROR;if(n=1)return ERROR;puts(Ok);int m=2*n-1;int i;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);puts(OK);HuffmanTree p;for(p=HT+1,i=1;iweight=*w;p-lchild=0;p-rchild=0;p-parent=0;for(;iweight=0;p-lchild=0;p-rchild=0;p-parent=0;puts(OK);int j;for(i=0,j=0;i10;i+)HTj+1.ch=i+0;j+;int s1,s2;for(i=n+1;i=m;+i)Select(HT,i-1,s1,s2);HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild =s2;HTi.weight =HTs1.weight+HTs2.weight;HC=(HuffmanCode)malloc(n+1)*sizeof(char *);char *cd;cd=(char*)malloc(n*sizeof(char);cdn-1=0;int start,c;unsigned int f;for(i=1;i=n;+i)start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c)cd-start=0;else cd-start=1;HCi=(char *)malloc(n-start)*sizeof(char);strcpy(HCi,&cdstart);puts(HCi);free(cd);Huffcode=OK;return OK;Status PrintHuffman(HuffmanCode HC,Status &Huffcode)if(!Huffcode)return ERROR;for(int i=1;i=10;i+)printf(%d-%sn,i,HCi);return OK;/生成赫夫曼编码Status HuffEncrypt(HuffmanCode HC,Status &Huffcode,Status &Huffcrypt)if(!Huffcode)return ERROR;ifstream file(random.txt);if(file.fail()return ERROR;char temp;int i;fstream encryptfile;encryptfile.open(encrypt.txt,ios:out);while(file.get(temp)for(i=0;HCtemp-47i!=0;i+)encryptfile(HCtemp-47i-48);puts(编码结果存放在目录下的encrypt.txt);file.close();encryptfile.close();Huffcrypt=OK;return OK;/译码并输出Status HuffDecrypt(HuffmanTree HT,Status &Huffcrypt,int n)if(!Huffcrypt)return ERROR;int m=2*n-1;int mm;/if(!Huffcrypt) return ERROR;ifstream file1(encrypt.txt);char *CodeStr;int k=0;char chch;while(file1.get(chch)k+;file1.close();CodeStr=new chark+1;ifstream file2(encrypt.txt);k=0;while(file2.get(chch)CodeStrk+=chch;file2.close();ofstream file3(decrypt.txt);CodeStrk=0;mm=m;for(int i=0;iChooSe;switch(ChooSe)case 1:if(!CreatRandomNum()puts(随机数生成失败);break;case 2:if(!GeHuffmanPos(NumCount)puts(概率生成失败);break;case 3:if(!HuffmanCoding(HT,HC,NumCount,n,Huffcode)puts(哈夫曼树生成失败);break;case 4:if(!HuffEncrypt(HC,Huffcode,Huffcrypt)puts(未生成哈夫曼树及编码);break;case 5:if(!PrintHuffman(HC,Huffcode)puts(未生成哈夫曼树及编码);break;case 6:HuffDecrypt(HT,Huffcrypt,n);break;case 7:exit(NULL);break;default:puts(ERROR);getchar();4 测试4.1 测试数据打开界面如图4.1-1所示：图4.1-1 测试程序打开界面生成文件如图4.1-2所示：图4.1-2 生成随机数文件显示随机概率如图4.1-3所示：图4.1-3 显示随机概率生成赫夫曼树以及赫夫曼编码如图4.1-4所示：图4.1-4 生成哈夫曼树以及哈夫曼编码保存哈夫曼编码如图4.1-5所示图.14-5 哈夫曼编码显示码文如图4.1-6所示：图4.1-6 显示码文译码并输出如图4.1-7所示：图4.1-7 译码并输出退出如图4.1-8所示：图4.1-8 退出生成的随机数文件如图4.1-9所示：图4.1-9 生成的随机数文件生成的编码结果文件如图4.1-10所示图4.1-10 生成的编码结果文件生成的译码结果文件如图4.1-11所示图4.1-11 生成的译码结果文件4.2 测试结果分析测试结果基本满足预期目标。能够实现对所给内容的编码存储以及译码等功能。能生成正确的文件格式。完成既定的任务目标，对于出现问题能正确给出反映。5 总结这次实训活动中经过长时间的失败以及失败过后的尝试最终还是成功的完成。这让我意识到程序编写是一个并不简单的过程。设计出的算法基本实现了实验目的的要求，同时在算法中国还有多少的缺憾，比如无法生成一个可见的赫夫曼树而是依旧是无序的数字，这在以后还是需要克服的地方。参考文献1谭浩强著，C+语言设计题解与上机指导，清华大学出版社2谭浩强著，C+面向对象程序设计 谭浩强，清华大学出版社3百度百科，哈夫曼编码，/view/95311.htm#includehuffmantree.hvoid main()double NumCount10=0;int n=10;int