没有合适的资源?快使用搜索试试~ 我知道了~
用哈夫曼编码实现文件压缩实验报告.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 50 浏览量
2022-11-04
09:36:12
上传
评论
收藏 531KB PDF 举报
温馨提示
试读
16页
。。。
资源推荐
资源详情
资源评论
《用哈夫曼编码实现文件压缩》
实 验 报 告
课程名称 数据结构 B
实验学期 2013 至 2014 学年 第 一 学期
学生所在系部 计算机学院
年级 2013 专业班级
学生姓名 学号
任课教师
实验成绩
一、实验题目:
用哈夫曼编码实现文件压缩
二、实验目的:
1、了解文件的概念。
2、掌握线性链表的插入、删除等算法。
3、掌握 Huffman 树的概念及构造方法。
4、掌握二叉树的存储结构及遍历算法。
5、利用 Huffman 树及 Huffman 编码,掌握实现文件压缩的一般原理。
三、实验设备与环境:
四、实验内容:
根据输入小写英文字母和输入的对应权值创建哈夫曼树,可以求出每个小写英文字母的哈夫
曼编码,将文本中的字母对应的哈夫曼编码写入文本中,实现对文本的编码。
五、概要设计:
(1)构造 Hufffman 树的 Hufffman 算法
构造 Huffman 树步骤:
1. 根据给定的 n 个权值{w1,w2,……wn},构造 n 棵只有根结点的二叉树,起权
值为 wj。
2. 在森林中选取两棵根结点权值最小和次小的树作左右子树,构造一棵新的二
叉树,置新二叉树根结点权值为其左右子树根结点权值之和。
3. 在森林中删除这两棵树,同时将新得到的二叉树加入森林中。
重复上述两步,直到只含一棵树为止,这棵树即哈夫曼树。
算法结构如图:
(2)Huffman 编码:数据通信用的二进制编码
思想:根据字符出现频率编码,使电文总长最短
编码:根据字符出现频率构造 Huffman 树,然后将树中结点引向其左孩子的
分支标“0”,引向其右孩子的分支标“1”;每个字符的编码即为从根到每
个叶子的路径上得到的 0、1 序列。
(3) 文本编码
读取存放在文本中的字母,一对一的进行编译,将对应的编码存放到另一个
文本中。
六、详细设计:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
//树结点定义
typedef struct
{
int weight;
int parent;
int lchild;
int rchild;
}HTNode,*HuffmanTree;
static char N[100];//用于保存字符
//赫夫曼编码,char 型二级指针
typedef char **HuffmanCode;
//封装最小权结点和次小权结点
typedef struct
{
int s1;
int s2;
}MinCode;
//函数声明
void Error();
HuffmanCode HuffmanCoding(HuffmanTree &HT,HuffmanCode HC,int *w,int n);
MinCode Select(HuffmanTree HT,int n);
//当输入 1 个结点时的错误提示
void Error()
{
printf("一个字符不进行编码!\n");
exit(1);
}
//构造赫夫曼 HT,编码存放在 HC 中,w 为权值,n 为结点个数
HuffmanCode HuffmanCoding(HuffmanTree &HT,HuffmanCode HC,int *w,int n)
{
int i,s1=0,s2=0;
HuffmanTree p;
char *cd;
int f,c,start,m;
MinCode min;
if(n<=1)
{
Error();//只有一个结点不进行编码,直接 exit(1)退出
}
m=2*n-1;//赫夫曼码需要开辟的结点大小为 2n-1
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//开辟赫夫曼树结点空间 m+1
//初始化 n 个叶子结点
for(p=HT,i=0;i<=n;i++,p++,w++)
{
p->weight=*w;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
//将 n-1 个非叶子结点的初始化
for(;i<=m;i++,p++)
{
p->weight=0;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
//构造赫夫曼树
for(i=n+1;i<=m;i++)
{
min=Select(HT,i-1);//找出最小和次小的两个结点
s1=min.s1 ; //最小结点下标
剩余15页未读,继续阅读
资源评论
春哥111
- 粉丝: 1w+
- 资源: 5万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功