东华理工大学C++课程设计(哈夫曼树)

1、东华理工大学软件学院软件工程系 据结构与算法设计课程设计报告题目.哈夫曼树及其应用学生姓名：刘信宏学号：班级：1121808指导教师：2013年1月11日数据结构课程设计任务书使用班级：1121805-8/1121813-16/1121821-22使用时间：2012-2013学年第1学期一、课程设计目的本课程设计的目的考察学生对常见数据结构及相关算法的综合应用能力，达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，解决实际问题中数据的合理存储表示，并根据相应的存储结构设计效率较高的算法实现对问题的求解；通过此次课程设计进一步培养学生良好的程序设计技巧和分析问题解决问

2、题的能力。二、课程设计题目哈夫曼树及其应用设计目的：熟悉树的各种存储结构及其特点。掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算。设计内容：欲发一封内容为AABBCAB（共长100字符,其中:A、B、C、D、E、F分别有7、9、12、22、23、27个）的电报报文,实现哈夫曼编码和译码。设计要求：分析系统需求。建立哈夫曼树。进行哈夫曼编码,并求出平均编码长度。译码。对编码好的内容进行译码。三、课程设计要求：1、每人一题，且需独立完成。2、每人的设计程序必须为可执行的exe文件，且需指导教师验收合格。学生程序必须在课程设计的最后一天交由指导教师验收合格。过期不再验收程序，如程序验收不合格

3、或在规定时间内未经指导教师验收，则视为该生程序没有完成。3、每人必须在规定时间内到机房做程序，指导老师将严格考勤，上机期间严禁做与课程设计无关的事情。指导教师将随时抽查。4、每人必须撰写课程设计报告并上交纸质稿（格式附后）。5、上交材料包括课程设计报告电子稿和程序代码电子稿（每位同学先建立一个文件夹，取名规则为“学号姓名”，文件夹里存放上交电子内容，分别是“学号+姓名+报告”和“学号+姓名+程序”，每班取一文件夹名，取名规则为班级号，内放该班同学上交内容，每班学习委员统一收齐后拷贝给指导老师。特别注意，上交的程序必须是在相应的编程环境下存在的源程序文件，不能是*.txt或*.doc文件等。四、

4、课程设计评分标准：1程序设计质量（占40%）2课程设计报告质量（占30%）3平时表现（占30%）五、上机时间安排表（以实验课表为准）课程设计的时间及教师安排专业班级周次机房安排上机时间指导老师软件工程1121805-8第19周软件工程1121813-16第19周软件工程1121821-22第19周附：课程设计报告格式。1、需求分析说明（说明为何做该题目，程序最终需要完成的功能，从其需求上说明。）2、总体设计（从总体上说明该题目的框架，用文字和图表说明）3、详细设计（对数据结构进行详细的描述，设计好相应数据结构以及其操作功能，要求用C+设计成类；用文字详细描述每个功能实现的算法及思路。）4、实现

5、部分（主要描述程序调试过程，报告中只要贴入核心代码）5、程序测试（给出各测试数据及其对应的测试结果，和程序运行图贴于此处。并能对程序运行结果分析之，且需提出改进算法。）6、总结:通过此次课程设计，对所学的知识有了比较全面的了解和应用，真正尝试了理论联系实际的趣味，明白了“说是说，做是做，说和做是两码事”的古语，此次设计巩固了理论基础知识，加强了对VC+6.0软件的熟悉与使用，学会了在实验中应注意的各种细节，怎样最住最快的查出错误，通过对程序的调试使理论更接近实际。在这里，我要感谢我的认可老师邹国华老师，和指导老师杨勇，感谢他们的悉心指导与亲切的关怀。注：全文字体用宋体小四，标题用黑体小三，所有

6、行间距为1.25，段落间距为0。源代码如下：/哈夫曼树的建立与应用#include#include#includeconstintn=6;constintm=2*n-1;structtreefloatweight;intparent;intlch,rch;structcodetypeintbitsn+1;intstart;charch;treehftreem+1;codetypecoden+1;voidcreathuffmantree()inti,j,p1,p2;floats1,s2;for(i=1;i=m;i+)hftreei.parent=0;hftreei.lch=0;hftreei.r

7、ch=0;couthftreei.weight=0;cout您好，欢迎使用哈夫曼树系统！endl;coutendl;coutendl;coutendl;coutendl;cout班级：1121808endl;cout学号：201120180823endl;cout姓名：刘信宏endl;cout指导老师：杨勇endl;endl;cout任课老师：邹国华endl;TOC o 1-5 h zcoutendl;cout根据您的需要，本次编译请输入n个权值endl;coutendl;coutendl;coutendl;coutendl;coutcou;for(i=1;ihftreei.weight;fo

8、r(i=n+1;i=m;i+)p1=p2=0;s1=s2=32767;for(j=1;j=i-1;j+)endl;/输/入权值/进/行次合作/pl.p分别指向两个最小的值的位置/si.S代表两个最小权值/选/两个最小值if(hftreej.parent=0)/该权值还没有被选中if(hftreej.weightsl)s2=sl;sl=hftreej.weight;p2=pl;pl=j;elseif(hftreej.weights2)s2=hftreej.weight;p2=j;/以下为合并hftreepl.parent=i;hftreep2.parent=i;hftreei.lch=pl;hf

9、treei.rch=p2;hftreei.weight=hftreepl.weight+hftreep2.weight;voidhuffcode()/哈弗曼编码codetypecd;intc,p;for(inti=1;i=n;i+)cd.start=n+1;cd.ch=64+i;/第一个树叶对应字母A,其余依次类推c=i;p=hftreei.parent;while(p!=0)cd.start-;if(hftreep.lch=c)cd.bitscd.start=0;elsecd.bitscd.start=1;c=p;p=hftreep.parent;codei=cd;coutendl;syst

10、em(cls);cout*欢迎使用哈夫曼树系统*endl;for(i=1;i=n;i+)cout字符codei.ch的权值为：hftreei.weightsetw(5)编码为：;for(intj=codei.start;j=n;j+)coutcodei.bitsj;coutendl;voidtrancode()/哈弗曼译码inti=m;charb;cout请输入您所需要发送的电报二进制编码报文(0.1以外的数结束)：b;coutendl;coutendl;coutendl;coutendl;cout*您输入的电报报文内容为：endl;while(b=0)|(b=1)if(b=0)i=hftre

11、ei.lch;elsei=hftreei.rch;if(hftreei.lch=0)coutb;coutendl;coutendl;cout感谢老师的检阅，您辛苦了！endl;voidmain()creathuffmantree();/建立哈夫曼树huffcode();/实现哈夫曼编码trancode();截图如下：东华理工大学软件学院软件工程系 *砂华&13勇国99取宏第i兰口iIJJ:11腿刘师师;老老级号名导课班学姓指任东华理工大学软件学院软件工程系 -hj.hroyhurn-斗/斗/亍.斗/日廿丹耳马马耳羊一riprap帀帀帀帀2匸I-E羽扁.扁.扁居更.LE.-LE.rKKKm_JrmT2237791222?rxrxrxrxrxr.r亠i直粥KKKKK&,-H.-HJ.fiBcDE(8-1的数給.宋j-E:言宏工乍室应讳程序MiceosoftVisua!StudioMyPrcyect5.lDebug.l.exe|)OOOOOOXXXXXX)OOOOOOOOOOOOOJ(J(J(J(欢使用1悬彳对系纟充豪MiMiMiMiMiMiMiMiif11101111