哈夫曼树应用Word下载.docx
《哈夫曼树应用Word下载.docx》由会员分享，可在线阅读，更多相关《哈夫曼树应用Word下载.docx（24页珍藏版）》请在冰点文库上搜索。
;
Huff[i].weight=0;
Huff[i].parent=-1;
Huff[i].lchild=-1;
Huff[i].rchild=-1;
}
printf（"
输入%d个字符及它的权值:
\n"
n）;
//读入数据
getchar（）;
n;
i++）
请输入第%d个字符:
"
i+1）;
scanf（"
%c"
&
d）;
Huff[i].ch=d;
请输入第%d个字符的权值:
%d"
w）;
Huff[i].weight=w;
n-1;
//构造哈夫曼树并生成该树的n-1个分支结点
m1=m2=32767;
x1=x2=0;
for（j=0;
j<
n+i;
j++）
//选取最小和次小两个权值结点并将其序号送x1和x2
if（Huff[j].parent==-1&
&
Huff[j].weight<
m1）
{
m2=m1;
x2=x1;
m1=Huff[j].weight;
x1=j;
}
else
m2）
{
m2=Huff[j].weight;
x2=j;
}
//将找出的两棵子树合并为一棵新的子树
Huff[x1].parent=n+i;
Huff[x2].parent=n+i;
Huff[n+i].weight=Huff[x1].weight+Huff[x2].weight;
Huff[n+i].lchild=x1;
Huff[n+i].rchild=x2;
2.对哈夫曼树进行编码
voidHuffmanCode（HNodeHuff[],intn）
//生成哈夫曼编码
FILE*fw;
HCodeHuffCode[MAXSIZE/2],cd;
//MAXSIZE/2为叶结点的最大个数
inti,j,c,p;
//求每个叶结点的哈夫曼编码
HuffCode[i].weight=Huff[i].weight;
cd.start=MAXBIT-1;
c=i;
p=Huff[c].parent;
while（p!
=-1）
if（Huff[p].lchild==c）
cd.bit[cd.start]=0;
cd.bit[cd.start]=1;
cd.start--;
c=p;
for（j=cd.start+1;
MAXBIT;
//保存该叶结点字符的哈夫曼编码
HuffCode[i].bit[j]=cd.bit[j];
HuffCode[i].start=cd.start;
//保存该编码在数组bit中的起始位置
3.根据哈夫曼编码进行译码
voiddecode（HNodeHuff[],intn）
//依次读入电文，根据哈夫曼树译码
FILE*fs;
inti,j=0;
charb[MAXSIZE];
i=2*n-2;
//从根结点开始往下搜索
【输入电文，并进行译码】\n"
）;
输入发送的编码（以'
2'
为结束标志）：
\n"
gets（b）;
译码后的字符为:
while（b[j]!
='
）
if（b[j]=='
0'
i=Huff[i].lchild;
//走向左孩子
i=Huff[i].rchild;
//走向右孩子
if（Huff[i].lchild==-1）//tree[i]是叶结点
Huff[i].ch）;
i=2*n-2;
//回到根结点
j++;
if（Huff[i].lchild!
=-1&
b[j]!
）
//电文读完，但尚未到叶子结点
\nERROR\n"
//输入电文
4.菜单调用
voidmenu（）
菜单如下\n"
1-------建立哈夫曼树\n"
）;
2-------进行哈夫编码\n"
3-------进行哈夫译码\n"
0-------程序退出\n"
}
5.main函数进行调用
intmain（）
HNodeHuff[MAXSIZE];
intn,sel;
——哈夫曼编码与译码——\n"
printf（"
Inputnumbersofleaf:
//n为叶结点个数
n）;
do
menu（）;
请输入您的选择:
sel）;
switch（sel）
case1:
HuffTree（Huff,n）;
//建立哈夫曼树
break;
case2:
HuffmanCode（Huff,n）;
//生成哈夫曼编码
case3:
decode（Huff,n）;
//译码变代码
}while（sel!
=0）;
return0;
4．源代码
#include<
stdio.h>
stdlib.h>
#defineMAXSIZE1000
#defineMAXBIT1000//定义哈夫曼编码的最大长度
typedefstruct
charch;
//增加一个域用于存放该节点的字符
intweight,parent,lchild,rchild;
}HNode;
//哈夫曼树结点类型
intweight;
intbit[MAXBIT];
intstart;
}HCode;
//哈夫曼编码类型
i++）//对数组Huff初始化
哈夫曼树的列表:
\n_________________________________________________________|\n"
zifu|Huff|weight|lchild|rchild|parent|\n"
//输出哈夫曼树即数组Huff的信息
_____|_____|________|____________|___________|___________|\n"
%4c|%4d|%5d|%10d|%10d|%10d|\n"
Huff[i].ch,i,Huff[i].weight,
Huff[i].lchild,Huff[i].rchild,Huff[i].parent）;
_________________________________________________________|\n"
if（（fp=fopen（"
d:
\\hfmtree.txt"
"
w"
））==NULL）//建立hfmtree文件
cannotopenthefileofhfmtree\n"
fprintf（fp,"
zifuHuffweightlchildrchildparent\n"
%3c%3d%5d%10d%10d%10d\n"
Huff[i].ch,i,Huff[i].weight,
fclose（fp）;
voidHuffmanCode（HNodeHuff[],intn）//生成哈夫曼编码
i++）//求每个叶结点的哈夫曼编码
//保存该编码在数组bit中的起始位置
字母哈夫曼编码如下:
-----|--------|--------|-------|\n"
zifu|HuffCode|weight|bit|\n"
//输出数组HuffCode的有关信息
i++）//输出各叶结点对应的哈夫曼编码
%4c|%5d|%4d|"
Huff[i].ch,i,HuffCode[i].weight）;
for（j=HuffCode[i].start+1;
j++）
%d|"
HuffCode[i].bit[j]）;
if（（fw=fopen（"
\\CodeFile.txt"
））==NULL）//建立codeFile文件
cannotopenthefileofCodeFile\n"
fprintf（fw,"
zifuHuffCodeweightbit\n"
%4c%5d%8d"
fclose（fw）;
//从根结点开始往下搜索
//输入电文有错
if（（fs=fopen（"
\\textFile.txt"
））==NULL）
//建立textFile文件
cannotopenthetextFile.txtofCodeFile\n"
fprintf（fs,"
译码后的字符为"
//n为叶结点个数
五．测试内容
用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：
“THISPROGRAMISMYFAVORITE”
字符
ABCDEFGHIJKLM
频度
6413223210321154757153220
NOPQRSTUVWXYZ
5763151485180238181161
补充：
在字母后输入了空格‘’这个字符，及其频度为1，对其进行编码。
六．运行结果
1.输入树结点：
2.选择1，输入结点权值，构建哈夫曼树
3.选择2，进行哈夫编码
4.根据自己要编译的话输入对应的编码，进行翻译
七．收获及体会
经过一个周的课程设计，我发现了我平时学习方面的许多不足。
仅仅通过半学期的数据结构学习是不能够轻松完成任务的，我们必须在课外多多学习一些其他的函数来充实自己以及将书本上的一些思想融会贯通成为自己的知识。
此外学习是一个不间断的过程，我们应该适时温故而知新，否则学过的东西会很快遗忘。
就像这次的课设，编程之前我把数据结构书和C语言又前前后后的翻看了两遍，才回忆起好多原来学习过的知识，但在编程时仍然觉得很吃力。
后来我们在网上搜到了一些程序，结果有好多我们没有学过的函数，为此我们又一边编程一边学习一些能够对程序起一些作用的函数，这样我们才勉强把程序编完。
同时，让我体会到编程序难，调试程序更难，调试程序需要足够的耐心，在这个过程中需要我们一遍又一遍的修改数据或是结构，直到达到我们的目的。
这个过程让我学到了很多知识，也让我觉得好有成就感。
一个周的课设已经完了，但是它带给我的冲击还没有散去，在接下来的日子里我会继续深入地学习c语言和数据结构等，仅仅有课本上的知识是远不能达到需求的，我应该多学习，多实践，希望能在学习上更上一层楼。
只要相信自己能做到，自己就能做到，再难的程序，只要自己喜欢去做，就一定能取得成功，告诉了自己只有永不言弃，这就是我的原则；
八、参考文献
<
C语言程序设计>
>
<
数据结构>
升级会员 