综合实验哈夫曼编码的实现

华北科技学院计算机系综合性实验华北科技学院计算机系综合性实验 实实 验验 报报 告告 课程名称课程名称 数据结构数据结构 B B 实验学期实验学期 20112011 至至 20122012 学年学年 第第 1 1 学期学期 学生所在系部学生所在系部 计算机学院计算机学院 年级年级 1010 级级 专业班级专业班级 学生姓名学生姓名 学号学号 任课教师任课教师 实验成绩实验成绩 计算机系制计算机系制 华北科技学院计算机系综合性实验报告 第 1 页 数据结构数据结构 B B 课程综合性实验报告课程综合性实验报告 开课实验室 开课实验室 实验题目 哈夫曼编码的实现哈夫曼编码的实现 一 实验目的一 实验目的 1 掌握线性链表的插入 删除等算法 3 掌握 Huffman 树的概念及构造方法 4 掌握二叉树的存储结构及遍历算法 5 构造 Huffman 树及 Huffman 编码 二 设备与环境二 设备与环境 微型计算机 Windows 系列操作系统 Visual C 6 0 软件 三 实验内容三 实验内容 根据字符出现的频率情况 创建 Huffman 树 再将各字符对应的哈夫曼编码显示在 屏幕上 四 实验结果及分析四 实验结果及分析 include include include typedef struct unsigned int weight parent lchild rchild HTNode HuffmanTree 动态分配数组存储哈夫曼树动态分配数组存储哈夫曼树 typedef char HuffmanCode 动态分布数组存储哈夫曼编码表动态分布数组存储哈夫曼编码表 void Select HuffmanTree HT int n int HT 0 weight 10000 for int i 1 i n i if HT i parent 0 if HT i weight HT min weight minn min min i else if HT i weight0 构造哈夫曼编码 构造哈夫曼编码HT 并求出 并求出n个字符的哈夫曼编码个字符的哈夫曼编码HC int i m s1 s2 HuffmanTree p if n 1 printf 结点数过少结点数过少 m n 2 1 HT HuffmanTree malloc m 1 sizeof HTNode 0号单元未用号单元未用 for p HT 1 i 1 i n i p h p weight h p lchild 0 p rchild 0 p parent 0 初始化赫夫曼树初始化赫夫曼树 for i m i p p weight 0 p parent 0 p lchild 0 p rchild 0 for i n 1 i m i 建立哈夫曼树建立哈夫曼树 Select HT i 1 s1 s2 在在HT 1 i 1 选择选择parent为且为且weight最小的两个结点 其序号分别最小的两个结点 其序号分别 为为s1和和s2 HT s1 parent i HT s2 parent i HT i lchild s1 HT i rchild s2 HT i weight HT s1 weight HT s2 weight 从叶子到根逆向求每个字符的哈夫曼编码从叶子到根逆向求每个字符的哈夫曼编码 char mr unsigned int start c f HC HuffmanCode malloc n 1 sizeof char 分配分配n个字符编码的头指针向量个字符编码的头指针向量 mr char malloc n sizeof char 分配求编码的工作空间分配求编码的工作空间 mr n 1 0 编码结束符编码结束符 for i 1 i n i 逐个字符求赫夫曼编码逐个字符求赫夫曼编码 start n 1 for c i f HT i parent f 0 c f f HT f parent 从叶子到根逆向求编码从叶子到根逆向求编码 if HT f lchild c mr start 0 else mr start 1 HC i char malloc n start sizeof char 为第为第i个字符编码分配空间个字符编码分配空间 strcpy HC i free mr 释放工作空间释放工作空间 HuffanCoding void main HuffmanTree HT HuffmanCode HC int w p i n k printf 输入结点个数 输入结点个数 k scanf d 华北科技学院计算机系综合性实验报告 第 3 页 w int malloc k sizeof int p w printf 请输入每个结点的权值请输入每个结点的权值 n for i 1 i k i w scanf d w HuffmanCoding HT HC p k printf 赫夫曼树赫夫曼树 n printf weight parent lchild rchild n n k 2 1 for i 1 i n i printf d 8d 8d 8d 8d n i HT i weight HT i parent HT i lchild HT i rchild printf 赫夫曼编码赫夫曼编码 n for i 1 i k i printf d i puts HC i 五 收获和体会五 收获和体会 Huffman 树 又称为最优树 是一类带权路径长度最短的树 有着广泛的应用 通过对数据结构的学习 让我更加的对 语言的编程有了深刻的理解和体会 虽然对数据结构的掌握还不够好 但是有 语言的编程做基础 就会很好的理解 对于 huffman 树的存储开始掌握的不是很好 但是看了其他同学的程序后 对它的 理解有了更深的体会 现在通过这次综合性试验我已完全的理解与掌握 也对今后 的数据结构地学习有了更深层次的提高 这次试验给我地学习之路带来了很大的启 蒙 华北科技学院计算机系综合性实验报告