长春大学课程设计哈夫曼Word格式.docx
- 文档编号:4891840
- 上传时间:2023-05-04
- 格式:DOCX
- 页数:18
- 大小:278.46KB
长春大学课程设计哈夫曼Word格式.docx
《长春大学课程设计哈夫曼Word格式.docx》由会员分享,可在线阅读,更多相关《长春大学课程设计哈夫曼Word格式.docx(18页珍藏版)》请在冰点文库上搜索。
通过结构体构建哈夫曼树,实现哈夫曼的编码和译码功能。
结构体变量如下:
typedefstruct//结构体
{
chardata;
intweight;
//权值
intparent;
//双亲结点
intlchild;
//左孩子
intrchild;
右孩子
}HTNode;
HTNodeht[80];
功能:
该结构体储存相关数据包括输入的权值weight,构建哈夫曼树所需要的双亲parent,左孩子lchild,右孩子rchild。
同时建立结构体数组HTNodeht[80];
typedefstruct
charcd[30];
//字符串
intstart;
}
HCode;
HCodehcd[80];
该结构体储存输入的字符。
(2)算法设计
本程序在运行过程中用到的算法是哈弗曼算法,它是由n个带权叶子结点构成的所有二叉树中带权路径长度最短的二叉树,根据给定的n个权值构成n棵二叉树的集合,其中每棵二叉树中只有一个带权weight的根结点,左右子树均空,选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树,且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和,即为哈夫曼树算法。
本程序先定义结构体,通过创建哈弗曼树,对输入的字符进行编码和译码。
2.2设计表示
(1)函数调用关系图及其说明如下:
(2)函数接口说明:
函数中的参数均是使用的全局变量的传递,因而在函数间进行传递的过程
中比较简单,下面就将主要函数及他们之间的参数的关系列出如下:
voidCodeInput(intn,HTNodeht[])//输入字符及权值进行哈夫曼编码
voidCreateHCode(HTNodeht[],HCodehcd[],intn)//进行哈夫曼编码
voidCodeOutput(intn,HCodehcd[])函数输出哈夫曼编码。
voidshuchu(HCodehcd[],intn)//输出哈夫曼树
voidsave(intn)//将其存入data.text文件中
3.用户手册
点击运行程序,在弹出的窗口中,会提示要输入的信息:
(1)界面信息:
显示5个选项,分别为
1:
输入哈夫曼树
2:
哈夫曼编码
3:
显示哈夫曼树
4:
哈夫曼权值存储
5:
退出。
(2)操作:
用户输入界面的1-5选项,若输入其他选项则提示("
输入有误!
请输入<
1--5>
选项),程序分别调用相关函数。
(3)用户需要输入哈夫曼树,程序会生成哈夫曼编码和哈夫曼树并显示在屏幕上,可以对哈夫曼权值保存。
当退出时,选择5直接退出。
4.测试数据及测试结果
测试数据如下:
asdfgh
789452
程序运行结果如下:
图1:
菜单显示界面,选择操作类型。
图2:
选择1,输入哈夫曼树,先输入所有字符然后输入权值。
图3:
选择2,输出哈夫曼编码。
图4:
选择3,显示哈夫曼树。
图5:
选择4,保存哈夫曼权值到"
d:
\\data.txt"
。
图6:
选择5,退出程序。
5.课程设计总结
在这次课程设计过程中,遇到了很多困难,之前对哈夫曼算法不是很了解,在编写源代码时有很多知识都忘了,多次翻阅课本学习,网上查找相关资料,使得编写的效率很慢。
调试程序的过程中,出现了很多错误,逐个分析每一个错误,我学到了很多东西,比如一些课上没有懂的知识,我通过实践搞懂了,而且通过此次的课程设计,让我更深入的理解数据结构,并且还运用了以前所学的有关C语言的知识,并且应用到我的程序中去,对哈夫曼树也有了更深的了解,并且真正会用这种算法了,通过不断的改正错误,我的程序有了更高的质量。
在编写的时候也犯了很多不该犯的错误,不过我及时纠正了,遗憾的是,我的程序功能不是很全,某些部分没有按照要求去做,说明我的编程能力有待提高。
程序清单
#include<
stdio.h>
string.h>
stdlib.h>
//权值
intparent;
//双亲结点
intlchild;
//左孩子
intrchild;
//右孩子
}HTNode;
}HCode;
voidCreateHT(HTNodeht[],intn)//创建哈弗曼树
{
inti,k,lnode,rnode;
intmin1,min2;
for(i=0;
i<
2*n-1;
i++)
{
ht[i].parent=ht[i].lchild=ht[i].rchild=0;
}
for(i=n;
min1=min2=9999;
lnode=rnode=0;
for(k=0;
k<
=i-1;
k++)
if(ht[k].parent==0)
if(ht[k].weight<
min1)
min2=min1;
min1=ht[k].weight;
rnode=lnode;
lnode=k;
}
elseif(ht[k].weight<
min2)
{
min2=ht[k].weight;
rnode=k;
ht[lnode].parent=i;
ht[rnode].parent=i;
ht[i].weight=ht[lnode].weight+ht[rnode].weight;
ht[i].lchild=lnode;
ht[i].rchild=rnode;
voidCreateHCode(HTNodeht[],HCodehcd[],intn)//进行哈夫曼编码
inti,f,c;
HCodehc;
for(i=0;
n;
i++)
{
hc.start=n;
c=i;
f=ht[i].parent;
while(f!
=0)
if(ht[f].lchild==c)
hc.cd[hc.start--]='
0'
;
else
1'
c=f;
f=ht[f].parent;
hc.start++;
hcd[i]=hc;
voidCodeInput(intn,HTNodeht[])//输入字符及权值进行哈夫曼编码
inti;
charch[30];
scanf("
%s"
ch);
for(i=0;
i<
n;
scanf("
%ld"
&
ht[i].weight);
printf("
***************************************-\n"
);
voidCodeOutput(intn,HCodehcd[])//输出哈夫曼编码
inti,j;
printf("
所有字符的哈弗曼编码为:
"
for(i=0;
n;
for(j=hcd[i].start;
j<
=n;
j++)
{
printf("
%lc"
hcd[i].cd[j]);
}
printf("
\n"
for(i=0;
printf("
序号%d:
"
i);
for(j=hcd[i].start;
j<
=n;
j++)
);
inti;
\nHT[i]:
\t权值\t双亲\t左孩子\t右孩子\n"
for(i=1;
i<
2*n;
i++)//共打印(2*len-1)组
if(i<
=n)
%2d:
\t%2d;
\t%2d,\t%2d,\t%2d.\n"
i,ht[i].weight,ht[i].parent,ht[i].lchild,ht[i].rchild);
//打印代码相应的权值,双亲左右孩子
}
inti;
FILE*fp;
if((fp=fopen("
"
w"
))==NULL)
can'
topenthisfile!
!
);
exit(0);
else
for(i=1;
fprintf(fp,"
%ld"
ht[i].weight);
保存文件成功!
fclose(fp);
voidmain()//主函数
{intnum,n,i;
charflag='
y'
while(flag=='
||flag=='
Y'
)
system("
cls"
printf("
************************************\n"
*欢迎使用哈夫曼编码系统*\n"
*1.生成哈夫曼树*\n"
*2.哈夫曼编码*\n"
*3.显示哈夫曼树*\n"
*4.哈夫曼权值存储*\n"
*5.退出*\n"
请选择操作类型(1-5):
scanf("
%d"
num);
**********************************************\n"
switch(num)
case1:
printf("
请输入要输入的字符数量n为:
if((scanf("
%ld"
&
n))&
&
(n!
=0))
{
printf("
\n请输入%d个字符和%d个对应权值<
先将所有字符输入再输对应权值>
\n:
n,n);
CodeInput(n,ht);
CreateHT(ht,n);
printf("
对应的权值为:
\n"
for(i=0;
{
printf("
%d:
i,ht[i].weight);
if((i+1)%4==0){
printf("
}
}
}
\n**************************************-\n"
break;
case2:
CreateHCode(ht,hcd,n);
CodeOutput(n,hcd);
**********************************************"
case3:
shuchu(hcd,n);
case4:
save(n);
*******************************************"
case5:
************感谢使用本程序****************\n"
exit
(1);
******************************************"
default:
输入有误!
选项"
\n*************************************\n"
}
\n继续或退出(yorn):
getchar();
flag=getchar();
}
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 长春 大学 课程设计 哈夫曼