这是今天的第二篇博客，也是有关数据结构的实验题，实现哈夫曼编码
题目要求：
输入一组整型权值，构建哈夫曼树，实现哈夫曼编码，并输出带权路径长度。
输入格式:
第一行输入叶子结点个数，接着依次输入权值。
输出格式:
输出哈夫曼编码，输出带权路径长度。
输入样例:
在这里给出一组输入。例如：
8
5 29 7 8 14 23 3 11
输出样例:
在这里给出相应的输出。例如：
5编码为0001
29编码为10
7编码为1110
8编码为1111
14编码为110
23编码为01
3编码为0000
11编码为001
WPL:271
源码如下
#include<iostream>
#include<cstdio>
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;
}
实验体会
在做实验之前，我观看了老师的视频指导，知道了本次实验主要关于二叉树和哈夫曼编码，在实验过程中我先根据自己的理解在纸上画了一个哈夫曼树，根据这个图来进行编码。首先我对于如何编码有些模糊，在查阅资料后发现可以通过递归来进行编码。在整个实验题目中主要分为了三个函数和一个主函数分别用来查找，计算权值，进行哈夫曼编码，通过调用三个子函数来实现功能。