一、 实验目的
掌握哈夫曼算法
二、 实验内容
实验题目
哈夫曼树哈夫曼编码
三、 设计文档
四、 源程序
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
struct node{
int num,fa,ch;
};
bool st[N];
int n;
node* nodes;
int find(int n){
int p=0;
for(int i=1;i<=n;i++){
if(st[i]==0&&(p==0||nodes[i].num<nodes[p].num)){
p=i;
}
}
return p;
}
void add(int lc,int rc,int p){
nodes[lc].fa=p;
nodes[lc].ch=-1;
nodes[rc].fa=p;
nodes[rc].ch=1;
nodes[p].num=nodes[lc].num+nodes[rc].num;
}
string huffman(int k){
string s;
if(nodes[k].fa){
s=huffman(nodes[k].fa);
}
if(nodes[k].ch){
s+=nodes[k].ch==-1?"0":"1";
}
return s;
}
int main(){
cin>>n;
nodes=new node[2*n];
for(int i=1;i<=n;i++){
cin>>nodes[i].num;
}
if(n==1||n==0){
cout<<"error";
}else{
int l=n+1,r=2*n-1;
while(l<=r){
int c1=find(l-1);
st[c1]=1;
int c2=find(l-1);
st[c2]=1;
add(c1,c2,l++);
}
int wpl=0;
for(int i=1;i<=n;i++){
string s=huffman(i);
cout<<nodes[i].num<<"编码为"<<s<<endl;
wpl+=nodes[i].num*s.size();
}
cout<<"WPL:"<<wpl;
}
return 0;
}
五、 个人体会(此部分与拼题a上主观题提交应一致)
1.实验中遇到的具体问题
1）输入数据的异常值或错误：在输入权值时，可能会输入异常值（例如负数、0或非整数）或错误的数据类型。这可能导致程序崩溃或产生错误的结果。
2）内存问题，开始用的nodes[n]报错。
2、 问题如何解决的
1）进行一个异常数值的判断，如果节点数量为1或者0，输出错误信息并结束程序 。
2）程序使用了一个大小为n*2的nodes数组来存储节点信息。
3、 实验设计思路，实验后的感想。
实验设计思路
首先，通过输入叶子节点个数和权值来构建哈夫曼树。
根据输入数据，使用优先队列（例如二叉堆）构建哈夫曼树。具体实现过程包括将节点按照权值大小插入队列中，然后每次从队列中取出两个最小的节点合并成一个新的节点，并将新节点插入队列中，直到队列中只剩下一个节点为止。
然后，使用哈夫曼树进行编码，将每个叶子节点的权值转化为对应的二进制编码。
输出每个叶子节点的权值和对应的二进制编码。
计算出带权路径长度，即所有叶子节点权值与它们对应的二进制编码长度的乘积之和。
输出带权路径长度。
实验后的感想：
通过实验，我更加深入地了解了哈夫曼编码的原理和实现方法。在构建哈夫曼树的过程中，需要考虑如何选择节点和如何合并节点，这些操作需要细心思考和尝试。我还发现了自己在编程方面的一些不足之处，例如对细节的把握和对算法的理解不够深入，内存分配问题。 我深刻地认识到了学习和实践的重要性。只有不断地学习和实践，才能够不断提高自己的能力和水平。同时，我也意识到了在未来的学习和工作中，需要更加注重细节和思考问题的全面性。