一、 实验目的

掌握哈夫曼算法

二、 实验内容

实验题目

哈夫曼树哈夫曼编码

三、  设计文档

四、   源程序

 #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、 实验设计思路，实验后的感想。

实验设计思路

首先，通过输入叶子节点个数和权值来构建哈夫曼树。

根据输入数据，使用优先队列（例如二叉堆）构建哈夫曼树。具体实现过程包括将节点按照权值大小插入队列中，然后每次从队列中取出两个最小的节点合并成一个新的节点，并将新节点插入队列中，直到队列中只剩下一个节点为止。

然后，使用哈夫曼树进行编码，将每个叶子节点的权值转化为对应的二进制编码。

输出每个叶子节点的权值和对应的二进制编码。

计算出带权路径长度，即所有叶子节点权值与它们对应的二进制编码长度的乘积之和。

输出带权路径长度。

实验后的感想：

通过实验，我更加深入地了解了哈夫曼编码的原理和实现方法。在构建哈夫曼树的过程中，需要考虑如何选择节点和如何合并节点，这些操作需要细心思考和尝试。我还发现了自己在编程方面的一些不足之处，例如对细节的把握和对算法的理解不够深入，内存分配问题。 我深刻地认识到了学习和实践的重要性。只有不断地学习和实践，才能够不断提高自己的能力和水平。同时，我也意识到了在未来的学习和工作中，需要更加注重细节和思考问题的全面性。