《数据结构与算法设计》课程设计报告题目：哈夫曼树及其应用学生姓名：刘信宏学号： ************班级： 1121808指导教师：**2013年1 月11 日数据结构课程设计任务书使用班级：1121805-8/1121813-16/1121821-22使用时间：2012-2013学年第1学期一、课程设计目的本课程设计的目的考察学生对常见数据结构及相关算法的综合应用能力，达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，解决实际问题中数据的合理存储表示，并根据相应的存储结构设计效率较高的算法实现对问题的求解；通过此次课程设计进一步培养学生良好的程序设计技巧和分析问题解决问题的能力。
二、课程设计题目哈夫曼树及其应用设计目的：熟悉树的各种存储结构及其特点。
掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算。
设计内容：欲发一封内容为AABBCAB ……(共长100 字符,其中:A 、B 、C 、D 、E 、F分别有7 、9 、12 、22 、23、27个)的电报报文,实现哈夫曼编码和译码。
设计要求：分析系统需求。
建立哈夫曼树。
进行哈夫曼编码,并求出平均编码长度。
译码。
对编码好的内容进行译码。
三、课程设计要求：1、每人一题，且需独立完成。
2、每人的设计程序必须为可执行的exe文件，且需指导教师验收合格。
学生程序必须在课程设计的最后一天交由指导教师验收合格。
过期不再验收程序，如程序验收不合格或在规定时间内未经指导教师验收，则视为该生程序没有完成。
3、每人必须在规定时间内到机房做程序，指导老师将严格考勤，上机期间严禁做与课程设计无关的事情。
指导教师将随时抽查。
4、每人必须撰写课程设计报告并上交纸质稿（格式附后）。
5、上交材料包括课程设计报告电子稿和程序代码电子稿（每位同学先建立一个文件夹，取名规则为“学号姓名”，文件夹里存放上交电子内容，分别是“学号+姓名+报告”和“学号+姓名+程序”，每班取一文件夹名，取名规则为班级号，内放该班同学上交内容，每班学习委员统一收齐后拷贝给指导老师。
特别注意，上交的程序必须是在相应的编程环境下存在的源程序文件，不能是*.txt或*.doc文件等。
四、课程设计评分标准：1．程序设计质量（占40%）2．课程设计报告质量（占30%）3．平时表现（占30%）五、上机时间安排表（以实验课表为准）课程设计的时间及教师安排附：课程设计报告格式。
1、需求分析说明（说明为何做该题目，程序最终需要完成的功能，从其需求上说明。
）2、总体设计（从总体上说明该题目的框架，用文字和图表说明）3、详细设计（对数据结构进行详细的描述，设计好相应数据结构以及其操作功能，要求用C++设计成类；用文字详细描述每个功能实现的算法及思路。
）4、实现部分（主要描述程序调试过程，报告中只要贴入核心代码）5、程序测试（给出各测试数据及其对应的测试结果，和程序运行图贴于此处。
并能对程序运行结果分析之，且需提出改进算法。
）6、总结:通过此次课程设计，对所学的知识有了比较全面的了解和应用，真正尝试了理论联系实际的趣味，明白了“说是说，做是做，说和做是两码事”的古语，此次设计巩固了理论基础知识，加强了对VC++6.0软件的熟悉与使用，学会了在实验中应注意的各种细节，怎样最住最快的查出错误，通过对程序的调试使理论更接近实际。
在这里，我要感谢我的认可老师邹国华老师，和指导老师杨勇，感谢他们的悉心指导与亲切的关怀。
注：全文字体用宋体小四，标题用黑体小三，所有行间距为1.25，段落间距为0。
源代码如下：//哈夫曼树的建立与应用#include<iostream.h>#include<iomanip.h>#include<windows.h>const int n=6;const int m=2*n-1;struct tree{float weight;int parent;int lch,rch;};struct codetype{int bits[n+1];int start;char ch;};tree hftree[m+1];codetype code[n+1];void creathuffmantree(){int i,j,p1,p2;float s1,s2;for(i=1;i<=m;i++){hftree[i].parent=0;hftree[i].lch=0;hftree[i].rch=0;hftree[i].weight=0;}cout<<" ★★★★★★★★★★★★★★★★★★★★★ "<<endl;cout<<" ★您好，欢迎使用哈夫曼树系统！★"<<endl;cout<<" ★★"<<endl;cout<<" ★★"<<endl;cout<<" ★★"<<endl;cout<<" ★★"<<endl;cout<<" ★班级：1121808 ★"<<endl;cout<<" ★学号：201120180823 ★"<<endl;cout<<" ★姓名：刘信宏★"<<endl;cout<<" ★指导老师：杨勇★"<<endl;cout<<" ★任课老师：邹国华★"<<endl;cout<<" ★★"<<endl;cout<<" ★根据您的需要，本次编译请输入"<<n<<"个权值★ "<<endl;cout<<" ★★"<<endl;cout<<" ★》》》》》》》》》★"<<endl;cout<<" ★★★★★★★★★★★★★★★★★★★★★"<<endl;cout<<" "<<endl;cout<<" "<<endl;cout<<"★请输入：>>>";for(i=1;i<=n;i++)cin>>hftree[i].weight; //输入权值for(i=n+1;i<=m;i++) //进行次合作{p1=p2=0; //p1.p2分别指向两个最小的值的位置s1=s2=32767; //s1.s2代表两个最小权值for(j=1;j<=i-1;j++) //选两个最小值if(hftree[j].parent==0)//该权值还没有被选中if(hftree[j].weight<s1){s2=s1;s1=hftree[j].weight;p2=p1;p1=j;}elseif(hftree[j].weight<s2){s2=hftree[j].weight;p2=j;}//以下为合并hftree[p1].parent=i;hftree[p2].parent=i;hftree[i].lch=p1;hftree[i].rch=p2;hftree[i].weight=hftree[p1].weight+hftree[p2].weight;}}void huffcode() //哈弗曼编码{codetype cd;int c,p;for(int i=1;i<=n;i++){cd.start=n+1;cd.ch=64+i; //第一个树叶对应字母A，其余依次类推c=i;p=hftree[i].parent;while(p!=0){cd.start--;if(hftree[p].lch==c) cd.bits[cd.start]=0;else cd.bits[cd.start]=1;c=p;p=hftree[p].parent;}code[i]=cd;}cout<<endl;system("cls");cout<<"*******************************欢迎使用哈夫曼树系统*****************************"<<endl;for(i=1;i<=n;i++){cout<<"字符"<<code[i].ch<<"的权值为:"<<hftree[i].weight<<setw(5)<<"编码为:";for(int j=code[i].start;j<=n;j++)cout<<code[i].bits[j]<<" ";cout<<endl;}}void trancode() //哈弗曼译码{int i=m;char b;cout<<"★请输入您所需要发送的电报二进制编码报文（0.1以外的数结束）："<<endl;cin>>b;cout<<" "<<endl;cout<<""<<endl;cout<<" "<<endl;cout<<" "<<endl;cout<<"★您输入的电报报文内容为："<<endl;while((b=='0')||(b=='1')){if(b=='0')i=hftree[i].lch;else i=hftree[i].rch;if(hftree[i].lch==0){cout<<code[i].ch;i=m;}cin>>b;}cout<<" "<<endl;cout<<" "<<endl;cout<<"★感谢老师的检阅，您辛苦了!"<<endl;}void main(){creathuffmantree(); //建立哈夫曼树huffcode(); //实现哈夫曼编码trancode();}截图如下：。