数据结构实验三哈夫曼树实验报告文档格式.docx
《数据结构实验三哈夫曼树实验报告文档格式.docx》由会员分享，可在线阅读，更多相关《数据结构实验三哈夫曼树实验报告文档格式.docx（18页珍藏版）》请在冰点文库上搜索。
intlchild;
intrchild;
charvalue;
}HNode;
/*结点结构体*/
函数：
void
DEMONHuffmanTree
（HNode
HuffNode[MAXNODE],intn）
作用：
构造一个哈夫曼树，并循环构建
intmain（）
运用已经构建好的哈弗曼树，进行节点的处理，达到成功解码编译
三、详细设计：
哈夫曼树的建立：
voidDEMONHuffmanTree（HNode
inti=0,j,m1,m2,x1,x2;
charx;
3
/*初始化存放哈夫曼树数组HuffNode[]中的结点*/
while（i<
n）
{
HuffNode[i].weight=0;
//权值
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
scanf（%c,&
x）;
HuffNode[i].value）;
//实际值，可根据情况替换为字母
i++;
}
/*输入n个叶子结点的权值*/
for（i=0;
i<
n;
i++）
scanf（%d,&
HuffNode[i].weight）;
for（i=n;
i<
2*n-1;
i++）
4
HuffNode[i].value=i;
/*循环构造Huffman树*/
for（i=0;
n-1;
m1=m2=MAXQZ;
//m1、m2中存放两个无父结点且结点权值最小的两个结点
x1=x2=0;
//找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树
for（j=0;
j<
n+i;
j++）
if（HuffNode[j].weight<
m1&
&
HuffNode[j].parent==-1）
中是最小m2=m1;
//m15
x2=x1;
m1=HuffNode[j].weight;
x1=j;
elseif（HuffNode[j].weight<
m2&
m2=HuffNode[j].weight;
x2=j;
}/*endfor*/
/*设置找到的两个子结点x1、x2的父结点信息*/
HuffNode[x1].parent=n+i;
HuffNode[x2].parent=n+i;
HuffNode[n+i].weight=HuffNode[x1].weight
+HuffNode[x2].weight;
HuffNode[n+i].lchild=x1;
HuffNode[n+i].rchild=x2;
}
6
叶子节点的哈夫曼编码的保存：
for（j=cd.start+1;
HuffCode[i].bit[j]=cd.bit[j];
HuffCode[i].start=cd.start;
主函数展示：
intmain（）
HNodeHuffNode[MAXNODE];
HCodeTypeHuffCode[MAXLEAF],cd;
inti,j,c,p,n,k=0;
charwen[100];
charz;
scanf（%d,&
n）;
HuffmanTree（HuffNode,n）;
for（i=0;
i<
n;
cd.start=n-1;
c=i;
7
p=HuffNode[c].parent;
while（p!
=-1）/*父结点存在*/
if（HuffNode[p].lchild==c）
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;
cd.start--;
/*求编码的低一位*/
c=p;
p=HuffNode[c].parent;
/*设置下一循环条件*/
}/*endwhile*/
for（j=cd.start+1;
HuffCode[i].bit[j]=cd.bit[j];
HuffCode[i].start=cd.start;
z=getchar（）;
for（;
z!
='
\n'
;
z=getchar（））
8
wen[k++]=z;
for（i=0;
if（z==HuffNode[i].value）
for（j=HuffCode[i].start+1;
j<
printf（%d,HuffCode[i].bit[j]）;
break;
else;
printf（\
）;
k;
printf（%c,wen[i]）;
return0;
9
/译码器实验报告3：
哈夫曼编
调试分析与心得体会：
四、
虽然哈夫曼树的建立有书上的参考，但是实际写整
个代码的时候还是问题重重。
首先就是哈弗曼树忘记了初始的赋值，导致最后出现了问题。
这样的错误还是很的情况。
在同学的帮WA容易解决，但是之后就出现了助下，最后发现是因为在选取节点的时候，循环出现了问题，虽然看起来编译没有错，但是边缘情况就会出现数据错误，这个还是很令人警醒，而这种思考的不全面的过程中会耗去大量的时间，这是要debug的问题，在注意的。
户操作说明：
用五、输入表示字符集大小为n（n<
=100）的正整数，以及n个字符和n个权值（正整数，值越大表示该字符出现的概率越大）；
的目标报文。
100输入串长小于或等于
六、运行结果：
附带自己的算法完成的结果图，可以通过PrtSc和图片编辑器获得；
10
附录：
七、#include<
stdio.h>
#include<
stdlib.h>
11
#defineMAXBIT100
#defineMAXLEAF30
#defineMAXNODEMAXLEAF*2-1
#defineMAXQZ10000//权值
*/编码结构体}HCodeType;
/*
*/结点结构体}HNode;
*/
构造一颗哈夫曼树/*
12
voidHuffmanTree（HNodeHuffNode[MAXNODE],int
inti=0,j,m1,m2,x1,x2;
charx;
13
i=0;
14
m2=m1;
//m1中是最小
m2
HuffNode[j].parent==-1）
15
HuffNode[n+i].weight=
HuffNode[x1].weight+HuffNode[x2].weight;
HuffNode[n+i].rchild=x2;
定义一个结点结构体数组*/
定义一个编码结构体数组，同时定义一个临时变量来存放求解编码时的信息*/
inti,j,c,p,n,k=0;
charwen[100];
charz;
16
HuffmanTree（HuffNode,n）;
cd.start=n-1;
c=i;
/*保存求出的每个叶结点的哈夫曼编码和编码的起始位*/
17
for（j=HuffCode[i].start+1;
j
<
printf（%d,
HuffCode[i].bit[j]）;
18
printf（\
k）
i++;
return0;
?
19
上机实习要求：
1、认真准备，按时参加上机实习，不得无故缺席，抽查不到者扣分；
2、独立完成老师布置的题目，上机完成程序并调试正确，课后完成实验报告的编写，将上机程序和实验报告打包后交给辅导老师评定分数，实验报告要求和评分标准见后面；
3、提倡创新，可对课本上提供的算法进行改进；
4、上机程序必须在程序中提供足够的注释，详细为好。
5、实验报告不用写出算法，只要写出对课程设计的见解，如对某一算法的改进思想，算法设计思想，调试算法过程中出现的问题及改进方法，调试程序的体会等。
只要是自己编程和调试就会写出相应的报告。
考核标准
1、机试程序和结果、设计报告缺一不可，机试程序和结果压缩打包后上交给辅导老师，设计报告主要是自己的设计过程和调试心得，报告中不必附带全部的源程序）。
机试成绩占总成绩60%，设计报告占40%。
2、上机程序和设计报告必须独立完成，严禁抄袭，若发现雷同，原创者视上机结果最多60分，抄袭者按0分计，若找不到原创，都按0分计。
所以原创同学注意，我们的检查专门针对抄袭情况，一旦发现将严肃处理！
！
20
升级会员 