哈夫曼树课程
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
哈夫曼树的编码,译码
广东技术师范学院天河学院
算法与数据结构
课程设计
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
目: 哈夫曼编/译码器
设 计 者:
专业班级: 本网络101
学 号: 02
指导教师:
所属系部: 计算机科学与技术系
2012年 06月 3 日
目 录
1 问题描述及要求........................................................................................................................... 1 2 需求分析....................................................................................................................................... 1
3 算法思想描述............................................................................................................................... 1
4 概要设计....................................................................................................................................... 2
1.创建哈夫曼树及函数调用过程 ........................................................................................... 2
2.输出哈夫曼数节点的权值的及调用过程 ........................................................................... 3
3.进行哈夫曼编码及调用过程 ............................................................................................... 3
4.字符串->哈夫曼码及调用过程 ........................................................................................... 4 5 详细设计....................................................................................................................................... 4
1.创建哈夫曼树 ........................................................................................................................ 4
2.显示HT的终结状态 ............................................................................................................ 5
3.打印哈夫曼编码 .................................................................................................................... 5
4.打印哈夫曼树 ........................................................................................................................ 5
5.字符串->哈夫曼编码 ............................................................................................................ 6
6.源程序清单............................................................................................................................ 7 6 测试数据及分析......................................................................................................................... 10
1.创建哈夫曼树 ...................................................................................................................... 10
2.显示HT的终结状态 .......................................................................................................... 10
3.打印哈夫曼编码 .................................................................................................................. 10
4.打印哈夫曼树 ...................................................................................................................... 11
5.字符串->哈夫曼编码 .......................................................................................................... 11 7课程设计
总结
初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf
.............................................................................................................................. 11
8 参考资料..................................................................................................................................... 12
哈夫曼编/译码器
1 问题描述及要求
利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码。对于双工信道(即可以双向传输信息的信道),每端都需要一个完成的编\译码系统。试为这样的信息收发站写一个哈夫曼的编\译码系统。
设计要求:
1. 初始化。从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树。
2. 编码。利用已建好的哈夫曼树,对正文进行编码。
3. 译码。对编码好的
内容
财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容
进行译码。
4. 打印编码。
5. 打印哈夫曼树
2 需求分析
(1)再通信过程中，为了提高信道利用率，缩短信息传输时间降，低传输成本 ，需要一编译码器。
(2)此哈夫曼编/译码器应具有编和译的双向功能,即在发送端通过编码系统对传入的数据进行编码,
在接受端将数据译码.将具有这两项功能的编译码器用于双工信道,就可满足 双工信道的双向编译功能.
(3) 输入某段报文时,系统将自动完成编译输出.
3 算法思想描述
1:初始化。从中端读入字符集大小n,以及n个字符和n各权值 ，建哈夫曼树，并存于hfmTree中
2:编码。利用已建好的树，对文件 ToBeTran中的正文进行编码，
然后将结果存入文件CodeFile .
3:译码。利用已建好的树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。
4:印代码文件CodeFile。将文件以紧凑格式显示在终端上，每行50个代码 。
同时将此字符形式的编码文件写入文件CodePrin中。
5:印哈夫曼树。将已在内存中的树以直观的方式(树或凹入表形式)显示在终端，同时将此字符形式的哈夫曼树写入文件TreePrin中。
1
4 概要设计
本程序主要定义了4个函数: void CreateHT(HuffmanTree &HT,int n);void preorderHT(HuffmanTree HT,int m);void GetHhffanCode(HuffmanTree HT,HuffmanCode
&HC,int n); void strHT(HuffmanTree HT,HuffmanCode HC,int n)
1.创建哈夫曼树及函数调用过程
函数:void CreateHT(HuffmanTree &HT,int n) 功能:构造哈夫曼树
for(i=0;i
n
for(c=i,f=HT[i].parent;f!=-1;c=f,f=HT[f].parent) delete cd
N
if(HT[f].lchild==c)
start=n-1;
Y HC[i]=new char[n-start];
strcpy(HC[i],&cd[start]);
cd[--start]='0' cd[--start]='1'
3
4.字符串->哈夫曼码及调用过程
函数:void strHT(HuffmanTree HT,HuffmanCode HC,int n)
功能:输入一个字符串，显示该字符的哈夫曼编码
for(nt=0;str[nt]!='\0';nt++) str[nt]='\0' for(nt=0;str[nt]!='\0';nt++)
str[nt]!='\0' for(i=0;i ")
])
Y if(str[nt]==ch[i]) printf("
%s",HC[
i])
5 详细设计
1.创建哈夫曼树
void CreateHT(HuffmanTree &HT,int n){//创建哈夫曼树
int i,k,Lnode,Rnode,Min1,Min2;
if(n<=1)return;
HT=new HNode[2*n-1];
strread(ch);
printf("请输入字符的权值\n");
for(i=0;i=0){
if(HT[m].lchild!=-1 || HT[m].rchild!=-1){//判断孩子节点是否为-1
printf("%d ",HT[m].weight);
preorderHT(HT,HT[m].lchild);
preorderHT(HT,HT[m].rchild);
}//if
else
printf("%d ",HT[m].weight);//输出孩子节点为-1的节点的权值
}//if
}
3.打印哈夫曼编码
void GetHhffanCode(HuffmanTree HT,HuffmanCode &HC,int n){//进行哈夫曼编码
int i,c,f,start;
HC=new char*[n];
char *cd;
cd=new char[n];
cd[n-1]='\0';//编码结束符
4.打印哈夫曼树
5
for(i=n;i<2*n-1;i++){//构造哈夫曼树
Min1=Min2=Max;
Lnode=Rnode=-1;//Lnode和rnode为权值最小的两个结点的位置
for(k=0;k<=i-1;k++)//在HT中找权值最小的两个结点
if(HT[k].parent==-1){//只在尚未构造二叉树的结点中查找
if(HT[k].weight哈夫曼编码
void strHT(HuffmanTree HT,HuffmanCode HC,int n){//输入一个字符串，显示该字符的哈
夫曼编码
char str[Max];
int nt,i;
GetHhffanCode(HT,HC,n);
printf("请输入要转换的字符:\n\n");
getchar();
gets(str);
system("cls");
6
printf("\n\t\t字符串转换为哈夫曼编码:\n\n\t\t");
for(nt=0;str[nt]!='\0';nt++)// 原样输出字符串
printf("%c",str[nt]);
printf(" -> ");
for(nt=0;str[nt]!='\0';nt++)//遍历字符串找出对应的哈夫曼编码
for(i=0;i
#include
#include
# define Max 1000
int n;
char ch[20];
typedef struct{
int weight;//结点的权值
int parent,lchild,rchild;//该结点的双亲结点、左孩子结点、右孩子结点在数组中的下标
}HNode,*HuffmanTree;//动态分配数组存储哈夫曼树
typedef char **HuffmanCode;//动态分配数组存储哈夫曼编码表
void main(){//主函数
int mt,i,flag=0;
HuffmanTree HT;
HuffmanCode HC;
printf("\n");
printf("\t\t*************************************************\n");
printf("\t\t*********** 欢迎使用哈夫曼编/译码器系统 *********\n");
while(1){
printf("\n\n\n\t\t1.创建哈夫曼树\t\t\t4.打印哈夫曼树");
printf("\n\n\t\t2.显示HT的终结状态\t\t5.字符串->哈夫曼编码");
printf("\n\n\t\t3.打印哈夫曼编码\t\t0.退出\n");
7
printf("\n\n请输入要进行下一步的操作是:>");
scanf("%d",&mt);
if(mt==0){
system("cls");
printf("\n\t\t退出系统\n");
exit(0);
}
if(mt==1) flag=1;
if(flag){
switch(mt){
case 1: system("cls");
printf("请输入要创建哈夫曼树的节点个数:");
scanf("%d",&n);
CreateHT(HT,n);
system("cls");
printf("\t\t哈夫曼树创建成功!\n");
getchar();
break;
case 2:
system("cls");
{
for(i=0;i<2*n-1;i++){
printf("第i=%d个节点的权值为:%d\t",i,HT[i].weight);
printf("双亲结点:%d\t",HT[i].parent);
printf("左孩子节点:%d\t",HT[i].lchild);
printf("右孩子节点:%d\t\n",HT[i].rchild);
}
}
break;
case 3:
system("cls");
{
GetHhffanCode(HT,HC,n);
printf("\n\t\t字符对应的哈夫曼编:\n");
8
for(i=0;i",ch[i]);
printf("%s \n",HC[i]);
}
}
break;
case 4:
system("cls");
printf("\n\t\t先序遍历输出各个节点的权值\n\n\t\t");
preorderHT(HT,2*n-2);
break;
case 5:
system("cls");
strHT(HT,HC,n); break;
case 0:
system("cls");
printf("\n\t\t退出系统\n\t\t");
exit(0);
default :
system("cls");
printf("\n\t\t输入有错,请从新输入!\n");
break;
}//switch
}//if
else{
system("cls");
printf("\n\t\t请先输入 1 创建哈夫曼树,才能进行下一个操作!\n\n");
}
}//while
}//main
9
6 测试数据及分析
1.创建哈夫曼树
2.显示HT的终结状态
3.打印哈夫曼编码
10
4.打印哈夫曼树
5.字符串->哈夫曼编码
7课程设计总结
为期一个星期的课程设计终于圆满落下了帷幕，回想这一个星期的前前后后，其过程有甜也有甜。苦的是:当接到通知要课程设计时，心里是那么的担心，果然就像担心的那样。前两天，做程序的代码时一点都不会做，看课本也不懂，课程设计的进度可以说是原地踏步～这都只能怪自己吧，在上课时总是不听课，玩手机，老师所讲的内容也是时听时不听，到头来也就呈现了今天的局面，当时自己是那么担心完成不了课程设计报告。说过程甜的是因为后来经过老师和小组成员的帮忙，总算是圆满完成了任务。通过本次实训让我重新学习了算法与数据结构这门课程，我也懂得了用代码来建立哈夫曼树，编码和译码双向功能。通过上
11
机实验，将理论的知识与实际结合在一起，增强了自己动手的能力和独立分析问题的能力，还有就是小组团队的协助能力。我觉得任何知识都不是轻而易举就能学会的，必须要付出努力，花点心思下去。在接下来的几个星期里，上课时不能再像以前那样不听课玩手机了。要好好学好，这样才不会辜负老师对我们的心意。最后在这里我衷心的向帮助我完成课程设计的龙君芳老师和我的小组成员表示感谢，谢谢～
8 参考资料
[ 1 ]徐凤生 数据结构与算法，C语言版.，机械工业出版社，2012
[ 2 ]严藯敏 数据结构[C语言版].，清华大学出版社，2009
[ 3 ]廖雷 《C程序设计实践教程》，2007
12
浙公网安备 33021202002483