推荐课程设计报告哈夫曼编码Word格式.doc
- 文档编号:846109
- 上传时间:2023-04-29
- 格式:DOC
- 页数:22
- 大小:238.50KB
推荐课程设计报告哈夫曼编码Word格式.doc
《推荐课程设计报告哈夫曼编码Word格式.doc》由会员分享,可在线阅读,更多相关《推荐课程设计报告哈夫曼编码Word格式.doc(22页珍藏版)》请在冰点文库上搜索。
对输入的一段英文中的每个字符统计其权值,建立哈夫曼树;
(2)E:
编码(Encoding)。
利用已建好的哈夫曼树,对每个字符进行编码。
(3)D:
译码(Decoding)。
利用已建好的每个编码,对输入的一个由0、1组成的序列进行译码;
(4)P:
印代码文件(Print)。
将每个字符编的哈夫曼码和译码结果显示在终端上。
测试用例见题集p149。
要求完成的主要任务:
(包括课程设计工作量及其技术要求,以及说明书撰写等具体要求)
课程设计报告按学校规定格式用A4纸打印(书写),并应包含如下内容:
1、问题描述
简述题目要解决的问题是什么。
2、设计
存储结构设计、主要算法设计(用类C语言或用框图描述)、测试用例设计;
3、调试报告
调试过程中遇到的问题是如何解决的;
对设计和编码的讨论和分析。
4、经验和体会(包括对算法改进的设想)
5、附源程序清单和运行结果。
源程序要加注释。
如果题目规定了测试数据,则运行结果要包含这些测试数据和运行输出,
6、设计报告、程序不得相互抄袭和拷贝;
若有雷同,则所有雷同者成绩均为0分。
时间安排:
1、第18周(6月28日至7月2日)完成。
2、7月2日08:
30到计算中心检查程序、交课程设计报告、源程序(CD盘)。
指导教师签名:
年月日
系主任(或责任教师)签名:
年月日
目录
1设计题目 1
2问题描述 1
3.1数据结构设计 1
3.2主要算法设计 3
3.3测试用例设计 6
4调试报告 7
5结束语 7
六、课程设计参考资料 8
附录 9
F1源代码 9
F2运行结果 16
1设计题目
哈夫曼编码
2问题描述
输入一段英文字符,试为该文中的每个字符编制相应的哈夫曼码。
3.设计
3.1数据结构设计
抽象数据类型二叉树的定义如下:
ADTBinaryTree{
数据对象D:
D是具有相同特性的数据元素的集合。
数据关系R:
基本操作P:
InitBiTree(&
T);
操作结果:
构造空二叉树T。
DestroyBiTree(&
二叉树T存在。
销毁二叉树T。
CreateBiTree(&
T,definition);
definition给出二叉树T的定义。
按definition构造二叉树T。
ClearBiTree(&
将二叉树T清为空树。
BiTreeEmpty(T);
若T为空二叉树。
则返回TRUE,否则FALSE。
BiTreeDepth(T);
返回T的深度。
Root(T);
返回T的根。
Value(T,e);
二叉树T的存在,e是T中某个结点。
返回e的值。
Assign(T,&
e,value);
二叉树T存在,e是T中某个结点。
结点e赋值为value。
Parent(T,e);
二叉树T存在,e是T中某个结点。
若e是T的非根结点,则返回它的双亲,否则返回“空”。
DeleteChild(T,p,LR);
二叉树T存在,p指向T中某个结点,LR为0或1。
根据LR为0或1,删除T中p所指结点的左或右子树。
InsertChild(T,p,LR,c);
二叉树的T存在,p指向T中某个结点,LR为0或1,非空二叉树c与T不相交且右子树为空。
根据LR为0或1,插入c为T中p所指结点的左或右子树。
P所指结点的原有左或右子树则成为c的右子树。
}
3.2主要算法设计
程序中一共定义了一个结构体和三个函数如下:
structHuffman//定义指向结点的结构体
{
intweight;
//权值
intparent,lchild,rchild;
//父亲结点和左右结点的位置
};
voidselect(Huffman*ht,inti,int&
s1,int&
s2)
{//选择权值较小的两个作为新的叶子结点,用于huffman的构造。
intj,k;
k=s1;
for(j=0;
j<
i+1;
j++)
if(s1!
=j&
&
j!
=s2&
ht[j].parent==0)
{
s1=j;
break;
}
for(j=0;
if(s2!
s1!
=k&
s2=j;
for(j=1;
=i;
if(ht[j].weight<
ht[s1].weight&
ht[j].parent==0)s1=j;
if(s1==s2)
for(j=0;
if(s2!
{
}
ht[s2].weight&
ht[j].parent==0&
=s1)s2=j;
voidHuffmancoding(Huffman*ht,char**&
hc,intk)
{//对haffman进行编码
intm,s1=0,s2=0,start,c,i,f,j;
char*cd;
m=2*k-1;
for(i=k;
i<
m;
i++)//构建huffman树
{
select(ht,i-1,s1,s2);
//调用select函数
ht[s1].parent=i;
ht[s2].parent=i;
ht[i].lchild=s1;
ht[i].rchild=s2;
ht[i].weight=ht[s1].weight+ht[s2].weight;
}
for(i=0;
=k-1;
i++)//对每个叶子结点进行编码
cd=newchar[k];
hc[i]="
"
;
for(j=0;
k;
cd[j]='
'
start=k-1;
for(c=i,f=ht[i].parent;
f!
=0;
c=f,f=ht[f].parent)
if(ht[f].lchild==c){cd[start--]='
0'
elsecd[start--]='
1'
hc[i]=&
cd[start+1];
voidfrequency(int*&
w,charstr[100],int*&
c,intn,int&
k)
{//涵数用于统计输入的字符的权w(出现的次数)。
inti,j,m;
n;
i++)
if(i==0){c[0]=0;
continue;
i;
if(str[j]==str[i]){c[i]=c[j];
if(j==i){c[i]=++k;
=k;
for(m=0;
m<
m++)
if(c[m]==j)w[j]++;
3.3测试用例设计
已知某系统在通信联络中只可能出现八种字符,其概率分别为0.05;
0.29;
0.07;
0.08;
0.14;
0.23;
0.03;
0.11,试设计哈夫曼编码。
设权w=(5,29;
7;
8;
14;
23;
3;
11),n=8,则m=15,构造哈夫曼树。
如下图:
23
11
14
5
3
7
8
29
1
哈夫曼编码:
2
4
6
0110
10
1110
1111
110
00
0111
010
4调试报告
程序调试:
(1.)当01序列解码成字符串时,要注意是否与已得出的字符串的编码匹配,如果不匹配,就把它后面的01序列截掉,不进行解码。
(2.)&
表示函数的参数是按地址传递的,当函数有多个返回值而无法用return实现时,通常使用这种。
比如:
voidfrequency(int*&
5结束语
经验和体会:
通过一个星期的努力,总算把课程设计给完成了,这是一个坚苦而又漫长的过程。
是啊,读了那么多年的书,课程设计可是第一次。
看着劳动成果,很欣慰!
通过这次课程设计之后我觉得自己对书上知识的掌握有很大的欠缺,看了题目都不知道怎么下手,一点头绪都没有,之后自己认真看了一遍书上的知识,查阅了一些网上资料,我能熟练掌握了二叉树,然后在此基础上掌握理解haffman树和编码,熟知了二叉树的性质。
可是这点小进展远远不够,这只是一个小小的开始,只能程序的大概轮廓可以写出来了。
但是有很多的细节和特殊情况没法写上去,例如:
用于huffman的构造;
用于对haffman进行编码;
用于统计输入的字符的权w(出现的次数);
实现这些的程序不知道该怎么写。
后来经过同学的帮助和指导慢慢地程序里用到的函数通过哪些语句来实现它,那些关键的函数怎样把它们有机结合起来等等,总之,在同学的多次指导下一个完整的程序写出来了,我也努力地去读懂它,发现自己隐约读懂了它!
真正的收获更多是思想上的,让我认识程序的复杂,自己的微不足道,“学无止境”头一次认识的这么深刻,察觉自己的不足。
在这次编程中,同学帮了我很多,我一个人是不能完成的。
查书,查资料,请教同学的过程就是我提高的过程,总之,通过这次的课程设计,我发现程序设计最重要的就是上机实践,以前只是看书,觉得看懂了,但是真正到机子上写程序时感觉无从下手,没有什么头绪,可能就是因为实际上机操作的太少了,以后需要在这方面好好地加强了。
以后的学习生活真的要踏踏实实,自己的计算机生涯必定是坎坷的,信心受挫了。
六、课程设计参考资料
[1]《数据结构(STL框架)》,王晓东编著,清华大学出版社,出版或修订时间:
2009年9月
[2]《数据结构(C语言版)》,严蔚敏,吴伟民编著,出版社:
清华大学出版社,出版或修订时间:
1997年4月
[3]《数据结构习题集(C语言版)》,严蔚敏,吴伟民,米宁编著,清华大学出版社,出版或修订时间:
1999年2月
起草人:
杨克俭
2010-6-22
附录
F1源代码
#include<
iostream>
usingnamespacestd;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 推荐 课程设计 报告 哈夫曼 编码