《数据结构课程设计-赫夫曼编码的实现》由会员分享，可在线阅读，更多相关《数据结构课程设计-赫夫曼编码的实现（26页珍藏版）》请在金锄头文库上搜索。
1、河南工程学院数据结构与算法课程设计成果报告赫夫曼编码的实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程1342班 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 26 日题 目赫夫曼书编码的实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成
2、 绩指导教师评语： 日期： 年 月 日目 录一 课程设计目标与任务11.1 课程设计目标11.2 课程设计任务11.3 课程设计要求1二 分析与设计22.1 题目需求分析22.2 存储结构设计22.3 算法描述32.4 程序流程图7三 程序清单8四 测试124.1测试数据124.2测试结果分析12五 总结15参考文献16一 课程设计目标与任务1.1 课程设计目标利用本次课程设计，使我们了解并掌握数据结构与算法结构的设计方法，增加独立分析和设计的能力，在算法的设计与实现方面得到更强的训练，加深对数据结构基本内容的理解和灵活应用，提高合理运用所学知识解决实际问题的能力。同时，培养初步的独立分析和设
3、计的能力，在程序设计方法及上机操作方面得到更多的训练，也能培养上机所需要的动手能力。数据结构课程主要是研究非数值计算的程序设计问题中所现在的计算机操作对象以及它们之间的关系和操作的学科。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理，理解面向对象程序设计思想，初步具备运用面向对象程序设计方法进行程序设计的能力。1.2 课程设计任务根据所学的内容完成以下课程设计的任务：（1）任意输入若干个大写英文字母存入文件中，统计每个字母的频率并根据其频率构造赫夫曼树并使程序输出对应字母的赫夫曼编码；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来
4、，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所写程序来实现相关问题的求解。1.3 课程设计要求本次设计程序的要求是把随机输入的字符串中不同字符作为叶子结点元素，把其在该字符串中出现的次数作为权值构造一个赫夫曼树，并得到结点的赫夫曼编码，要求先对问题进行分析，了解题目的要求，画出流程图，然后用函数具体实现，认真完成软件设计的全部过程。同时通过课程设计来提高思维能力，促进综合应用能力和专业素质的提高。 二 分析与设计2.1 题目需求分析首先在一个文件中随机输入一个字符串，然后读取该文件中的字符并统计该文件中各个字符的频率，以频率作为权值，根据算法建立赫夫曼树，在根据对
5、应字符的频率对出现的每个字符进行赫夫曼编码并输出。2.2 存储结构设计 1.构造赫夫曼树的步骤：（1）根据给定的n个权值w1,w2,.,wn构成n棵二叉树的集合F=T1，T2，.,Tn,其中每棵二叉树Ti中只有一个带权为wi的根节点，其左右子树均为空。（2）在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。（3）在F中删除这两棵树，同时将新得到的二叉树加入F中。（4）重复（2）和（3），直到F只含一棵树为止。这棵树便是赫夫曼树。2.赫夫曼编码：数据通信用的二进制编码。（1）思想：根据字符总频率编码，使电文总长最短。（2
6、）编码规则：对于一棵二叉树规定左分支表示字符0，右分支表示字符1，则可以从根结点到叶子结点的路径上分支字符组成的字符串作为该叶子结点字符的编码，如此得到的必为二进制前缀编码。2.3 算法描述1.在一个文件中任意输入一段字符串，读取文件中的字符：int fileopen(char string) /读入文件 FILE *fp; if(fp=fopen(E:file.txtfll.txt,r)=NULL) printf(不能打开文件!n); exit(1); while(fgets(string,100,fp)!=NULL) printf(%sn,string); fclose(fp); retu
7、rn 0; 2.在ht中选择parent为0且权值最小的两个根结点的算法：void select_min(HuffmanTree T,int k,int &x1,int &x2) /选择权值最小的两个根结点,其序号为x1和x2 int i,j; int min1=1000; for(i=1;i=k;i+) /找最小值if(Ti.weightmin1 &Ti.parent=0) j=i; min1=Ti.weight; x1=j;min1=1000; for (i=1;i=k;i+) /找次小值if(Ti.weightmin1 & Ti.parent=0 & i!=x1) j=i; min1=T
8、i.weight; x2=j; 1. 统计字符串中的各个字母的个数：int tongji(char *s,int cishu,char str) /统计字符串中各种字母的个数以及字符的种类int i,j,k; char *p; int t27; for(i=1;i=A&*p=Z) k=*p-64; tk+; for(i=1,j=0;i=26;+i) if(ti!=0 ) j+; strj=i+64; /送对应的字母到数组中cishuj=ti; /存入对应字母的权值 return j; /j是输入字母种数 3.根据字符的个数构造赫夫曼树：void Create_huffmanTree(Huffm
9、anTree ht,HuffmanCode hc,int cishu,char str) /生成哈夫曼树HT int i,s1,s2; for(i=0;i2*num-1;i+) hti.left=0; hti.right=0; hti.parent=0; hti.weight=0; for(i=1;i=num;i+) /输入num个叶 结点的权值hti.weight=cishui; for(i=num+1;i=2*num-1;i+) /选择parent为0且权值最小的两个根结点，其序号为s1和s2,i为双亲select_min(ht,i-1,s1,s2); hts1.parent=i;hts2
10、.parent=i; hti.left=s1; hti.right=s2; hti.weight=hts1.weight+hts2.weight; for(i=0;i=num;i+) hci.ch=stri; /字符的种类i=1;while(i=num) printf(字符%c次数:%8dn,hci.ch,cishui+); 4.输出赫夫曼编码：void Huffman_bianma(HuffmanTree T,HuffmanCode H) /根据哈夫曼树T求哈夫曼编码H int child,parent,i; /child和parent分别指示t中孩子和双亲char coden; /存放编码
11、int start; /指示码在code中的起始位置codenum=0; /最后一位（第num个）放上串结束符for(i=1;i0) /直至tchild是树根为止 /若tchild是tparent的左孩子,则生成0;否则生成1 if(Tparent.left=child) code-start=0; else code-start=1; child=parent; strcpy(Hi.co,&codestart); Hi.len=num-start; 2.4 程序流程图本程序流程为开始后先建立一个文件，若打开文件，在文件中任意输入若干个英文字母，读取文件的内容，统计字符的总数及频率。根据字符的
12、频率构造赫夫曼树并输出赫夫曼编码，若不打开文件则结束程序。 建立赫夫曼树赫夫曼编码 结束输入字符存入文档字符总数num统计字符个数及频率 开始打开文件？否 是图2-1 程序流程图三 程序清单#include #include #include #include /类型相关变量的定义#define n 100 #define m 2*n-1 typedef struct char ch; char co9; /存放编码int len; CodeNode; typedef CodeNode HuffmanCoden+1; typedef struct int weight; int left,right,parent; HTNode; typedef HTNode HuffmanTreem+1; int num; void select_min(HuffmanTree T,int k,int &x1,int &x2) /选择权值最小的两个根结点,其序号为x1和x2 int i,j; int min1=1000; for(i=1;i=k;i+) /找最小值if(Ti.weightmin1 &Ti.parent=0) j=i; min1=Ti.weight;
