没有合适的资源?快使用搜索试试~ 我知道了~
哈弗曼编译器实验报告.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 79 浏览量
2022-11-11
21:28:10
上传
评论
收藏 423KB PDF 举报
温馨提示
试读
15页
。。。
资源推荐
资源详情
资源评论
实习报告
题目:哈弗曼编译码器
班级:电信系 通信工程 0902 班
完成日期:2010.11
一、 需求分析
1、编写哈弗曼编译码器,其主要功能有
(1)I:初始化(Initialization)。从终端读入字符集大小 n,以及 n 个字符
和 n 个权值,建立哈夫曼树。
(2)E:编码(Encoding)。利用已建好的哈夫曼树),对从终端输入的正文进行
编码,然后从终端输出。
(3)D:译码(Decoding )。利用已建好的哈夫曼树将从终端输入的代码进行译
码,结果从终端输出。
(4)P:印哈夫曼树(Print)。将已编码的的哈夫曼树显示在终端上,同时将此
字符形式的哈夫曼树。
2、测试数据:
输入的字符={a, b, c, d, e}
其对应的权值={5,29,7,8,14}
二、 概要设计
1、二哈弗曼树的抽象数据类型定义为:
ADT HuffmanTree{
数据对象 D:D 是具有相同性质的数据元素的集合
数据关系 R:
若 D=Φ,则 R= Φ,哈弗曼树为空
若 D≠Φ,则 R= {H},H 是如下二元关系:
(1) 在 D 中存在唯一的称为根的数据元素 root,它在关系 H 下无前驱
(2) 若 D-{root}≠Φ,则存在 D-{root}={Dl,Dr}。且 Dl∩Dr=Φ
(3) 若 Dl≠Φ,则 Dl 中存在唯一的数据元素 Xl,<root, Xl>属于 H,且
存在 Dl 上的关系 H1 属于 H。若 Dr≠Φ,则 Dr 中存在唯一的数据元
素 Xr,<root, X>属于 H,且存在 Dr 上的关系 Hr 属于 H
H={<root, Xl>,<root, X>,Hl,Hr};
(4) (Dl,{Hl})是一棵符合本定义的哈弗曼树,称为根的左子树。
(Dr,{Hr})是一棵符合本定义的哈弗曼树,称为根的右子树。
基本操作:
HuffmanCoding(&HT, &HC, &sum)
操作结果:建立哈弗曼树并进行编码将编码存放在 HC 中,并返回字符的个
数。
Encoding(HT, HC, sum)
操作结果:利用已建立的哈弗曼树对字符进行编码
Decoding(HuffmanTree HT,HuffmanCode HC,int sum)
操作结果:对输入的密码进行翻译
Print(HT, HC, sum)
操作结果:打印建立好的哈弗曼树
}ADT HuffmanTree
三、 详细设计
(1)哈弗曼树每个节点的定义:
typedef struct
{
unsigned int weight;
unsigned int parent,lchild,rchild;
char elemt[20];
}HTNode,*HuffmanTree;
(2)定义指向哈弗曼树的指针,用于动态分配空间
typedef char **HuffmanCode;
(3)哈弗曼树的基本操作
Void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int
n)
{ //建立哈弗曼树,求出哈弗曼编码
if (n<=1)return;
m=2*n-1; //n 个叶子的 HuffmanTree 共有
2n-1 个结点
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(p=HT+1,i=0; i<n; ++i,++p,++w)*p={*w,0,0,0};
//给前 n 个单元初始化
for(;i<=m; ++i,++p)*p ={0,0,0,0}; //从叶子之后的存储单元清零
for(i=n+1;i<=m; ++i)
{ /
/建 Huffman 树(从 n 个叶子后开始存内结点)
Select(HT, i-1, s1, s2);
//选择 parent 为 0 且 weight 最小的两个结点,
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;
} //以上建立了哈弗曼树,以下求哈弗曼编码
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
//分配 n 个字符编码的头指针向量(一维数组)
cd=(char*) malloc(n*sizeof(char)); //分配求编码的临时最长空间
cd[n-1]=“\0”; //编码结束符(从 cd[0]~cd[n-1]为合法空间)
for(i=1;i<=n;++i) //逐个字符求 Huffman 编码
{
start=n-1; //编码结束符位置
for(c=i,f=HT[i].parent; f!=0; c=f, f=HT[f].parent)
//从叶子到根逆向求编码
if(HT[f].lchild==c) cd[--start]=“0”;
else cd[--start]=“1”;
HC[i]=(char*)malloc((n-start)*sizeof(char));
//为第 i 个字符编码分配空间,并以数组形式存放各码串指针
strcpy(HC[i],&cd[start]); //从 cd 复制编码串到 HC 所指空间
}
free(cd); //释放临时空间
}//HuffmanCoding
for(i=0; 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) cd[--start]=“0”;
else cd[--start]=“1”;
} / /从叶子到根逆向求编码
}// HuffmanCoding
Void Encoding(HuffmanTree HT,HuffmanCode HC,int sum)
//利用已经建立的哈弗曼树对输入的字符进行哈弗曼编码
{
for(int i=0;a[i]!='\0';i++)
//依次判断字符的对应的哈弗曼编码
{
for(int n=0;HT[n].elemt[0];n++)
//查找 a[i]在哈弗曼树中的位置
{
strcpy(p,HC[n]);p=p+strlen(HC[n]);break;
//把编码复制接到 code 后
}
}
i=0;
printf("得到的编码是:\n");
while(code[i]!='\0') //输出字符对应的哈弗曼编码
{
printf("%c",code[i++]);
}
}// Encoding
Void Decoding(HuffmanTree HT,HuffmanCode HC,int sum) //译码
{
while(code1[i]!='\0')
{
if(code1[i]=='0') b=HT[b].lchild;
剩余14页未读,继续阅读
资源评论
若♡
- 粉丝: 6172
- 资源: 1万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功