石 家 庄 铁 道 大 学
实 验 报 告
课程名称： 信2305-3 任课教师： 刘 丹 实验日期： 2024.12.15
班 级： 信2305-3 姓 名： 徐戌 学 号： 20234316
实验项目名称：实验三
一、 实验目的
1．掌握二叉树的定义；
2．掌握哈夫曼树和哈夫曼编码算法的实现
二、 实验内容
三、 设计文档
四、 源程序
7-1 哈夫曼树哈夫曼编码
include
include
include <string.h>
include <stdio.h>
using namespace std;
typedef struct{
int weight; //权重
int parent,lchild,rchild; //节点双亲,左右孩子
}HTNode,*HuffmanTree; //动态分配数组存哈夫曼树
int Select(HuffmanTree &HT, int n)
{
int p=0;
for(int i=1;i<=n;i++)
{
if(HT[i].parent0 && (p0||HT[i].weight < HT[p].weight))
{
p=i;
}
}
return p;
}
void CreateHuffmanTree(HuffmanTree &HT,int n)
{
if(n<=1) return;
int m = 2*n - 1;
HT = new HTNode[m+1];
for(int i = 1; i<=m ;i++) //初始化下标为0
{
HT[i].parent = 0;
HT[i].lchild = 0;
HT[i].rchild = 0;
}
for(int i = 1; i <= n; i++)
{
cin>>HT[i].weight; //输入节点
}
for(int i=n+1; i <= m ;i++) //n-1次选择
{
//选择双亲为0,权值最小的节点,返回他们的序号s1,s2
int s1 = Select(HT, i-1);
HT[s1].parent = i; //删除s1,s2,双亲改为i
int s2 = Select(HT, i-1);
HT[s2].parent = i;
//s1,s2作为i的孩子
HT[i].lchild = s1;
HT[i].rchild = s2;
//i的权值等于孩子的权值之和
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
}
typedef char **HuffmanCode;
void CreateHuffmanCode( HuffmanTree HT,HuffmanCode &HC , int n)
{
HC = new char*[n+1]; //编码数组
char cd[n]; //临时编码数组
cd[n-1] = '\0'; //结束符
for(int i = 1; i<=n ;i++)
{
int start = n-1; //开始指向最后
int c = i;
int f = HT[i].parent; //f指向c的双亲
while( f!=0 )
{
--start; //回溯
if(HT[f].lchild == c)
cd[start] = '0';
else
cd[start] = '1';
//回溯
c = f;
f = HT[f].parent;
}
HC[i] = new char[n-start];
strcpy(HC[i] , &cd[start]);
}
//delete cd;
}
void show(HuffmanTree HT,HuffmanCode &HC , int n)
{
int wpl = 0;
for(int i=1;i<=n;i++)
{
string s = HC[i];
cout<<HT[i].weight<<"编码为"<<HC[i]<<endl;
wpl+=HT[i].weight*s.length();
}
cout<<"WPL:"<<wpl;
}
int main()
{
int n;
HuffmanTree HT = new HTNode;
cin>>n;
if(n1||n0)
{
cout<<"error";
return 0;
}
CreateHuffmanTree(HT,n);
HuffmanCode HC;
CreateHuffmanCode(HT ,HC,n );
show(HT ,HC,n);
return 0;
}
五、 个人体会
构建哈夫曼树时节点选择错误
构建哈夫曼树的过程中，错误地选择频率较高的节点作为合并对象，导致树的结构不正确。
解决方案：使用优先队列（最小堆）来管理节点，每次从队列中取出频率最小的两个节点进行合并，确保每次选择的都是当前频率最小的节点。
实验感想
通过这次哈夫曼树哈夫曼编码实验，我深刻体会到了数据压缩算法的实际应用和重要性。哈夫曼编码不仅能够有效地减少数据存储空间，还能提高数据传输效率。在实验过程中，我遇到了一些具体的编程问题，如节点选择错误、路径记录错误和数据丢失等。通过使用优先队列、递归记录路径和确保数据格式一致等方法，这些问题得到了有效解决。这次实验不仅提升了我的编程能力，还增强了我对数据结构和算法的理解。未来，我将继续深入学习和探索更多的数据压缩技术，以应对更复杂的实际问题。