没有合适的资源？快使用搜索试试~ 我知道了~

文库首页前端Node.js北邮数据结构实验3哈夫曼编码 (2).pdf

北邮数据结构实验3哈夫曼编码 (2).pdf

1.该资源内容由用户上传，如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款（资源遇到问题，请及时私信上传者）

版权申诉

0 下载量 169 浏览量 2022-10-30 16:50:08 上传评论收藏 431KB PDF 举报

温馨提示

试读

15页

北邮数据结构实验3哈夫曼编码 (2).pdf北邮数据结构实验3哈夫曼编码 (2).pdf

资源推荐

资源详情

资源评论

数据结构实验报告

实验名称：实验 3——哈夫曼编码

学生姓名：

班级：

班内序号：

学号：

日期： 2013 年 11 月 24 日

1．实验要求

利用二叉树结构实现赫夫曼编/解码器。

基本要求：

1、初始化(Init)：能够对输入的任意长度的字符串 s 进行统计，统计每个

字符的频度，并建立赫夫曼树

2、建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每

个字符的编码输出。

3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的

字符串输出。

4、译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译

码，并输出译码结果。

5、打印(Print)：以直观的方式打印赫夫曼树（选作）

6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼

编码的压缩效果。

2. 程序分析

2.1 存储结构：

struct HNode

{

char c;//存字符内容

int weight;

int lchild, rchild, parent;

};

struct HCode

{

char data;

char code[100];

}; //字符及其编码结构

class Huffman

{

private:

HNode* huffTree; //Huffman树

HCode* HCodeTable; //Huffman编码表

public:

Huffman(void);

void CreateHTree(int a[], int n); //创建huffman树

void CreateCodeTable(char b[], int n); //创建编码表

void Encode(char *s, string *d); //编码

void Decode(char *s, char *d); //解码

void differ(char *,int n);

char str2[100];//数组中不同的字符组成的串

int dif;//str2[]的大小

~Huffman(void);

};

结点结构为如下所示：

三叉树的节点结构：

struct HNode//哈夫曼树结点的结构体

{ int weight;//结点权值

int parent;//双亲指针

int lchild;//左孩子指针

int rchild;//右孩子指针

char data;//字符

};

示意图为：

int weight int parent int lchild int rchild Char c

编码表节点结构：

struct HCode//编码表结构体

{

char data;//字符

char code[100];//编码内容

};

示意图为：

char data char code[100]

基本结构体记录字符和出现次数:

struct node

{

int num;

char data;

};

示意图为:

int num char data

2.关键算法分析

(1).初始化:

伪代码：

1. 输入需要编译的文本内容

2. 将输入的内容保存到数组 str1 中

3. 统计出现的字符数目,并且保存到变量 count 中

4. 统计出现的不同的字符，存到 str2 中，将 str2 的大小存到 dif 中

时间复杂度 O(n！)

（2）.创建哈夫曼树

算法伪代码：

1. 创建一个长度为 2*n-1 的三叉链表

2. 将存储字符及其权值的链表中的字符逐个写入三叉链表的前 n 个结点的 data 域，并将对

应结点的孩子域和双亲域赋为空

3. 从三叉链表的第 n 个结点开始，

3.1 从存储字符及其权值的链表中取出两个权值最小的结点 x,y，记录其

下标 x,y。

3.2 将下标为 x 和 y 的哈夫曼树的结点的双亲设置为第 i 个结点

3.3 将下标为 x 的结点设置为 i 结点的左孩子，将下标为 y 的结点设置为

i 结点的右孩子，i 结点的权值为 x 结点的权值加上 y 结点的权值，i

结点的双亲设置为空

4. 根据哈夫曼树创建编码表

时间复杂度 O(n)

（3）．创建编码表

算法伪代码：

1.初始化编码表

2.初始化一个指针，从链表的头结点开始，遍历整个链表

2.1 将链表中指针当前所指的结点包含的字符写入编码表中

剩余14页未读，继续阅读

评论收藏

内容反馈

1.该资源内容由用户上传，如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款（资源遇到问题，请及时私信上传者）

版权申诉

资源评论

资源反馈

评论星级较低，若资源使用遇到问题可联系上传者，3个工作日内问题未解决可申请退款~

xxpr_ybgg

粉丝: 6552
资源: 3万+

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

北邮数据结构实验3哈夫曼编码 (2).pdf

数据结构课程设计(哈夫曼编码).pdf

北邮数据结构实验3哈夫曼编码.pdf

北邮数据结构实验3哈夫曼编码 (2).docx

北邮数据结构实验3哈夫曼编码.docx

北邮数据结构实验三-哈夫曼树.pdf

北邮数据结构实验三-哈夫曼树 (2).docx

北邮数据结构实验三-哈夫曼树.docx

哈夫曼树和进行哈夫曼编码.pdf

实验七哈夫曼编码实验.pdf

数据结构哈夫曼编码译码.pdf

北邮信通院数据结构实验报告三哈夫曼编码器.docx

北邮数据结构实验报告三题目2-哈夫曼树.pdf

北邮信通院数据结构实验_哈夫曼树

北邮哈夫曼数据结构实验报告.pdf

数据结构实验-哈夫曼树与哈夫曼编码

北邮数据结构哈夫曼树实验报告

实验四--哈夫曼树与哈夫曼编码 (2).pdf

数据结构哈夫曼编码实验报告.doc

北邮信通院数据结构实验报告三哈夫曼编码器.doc

哈夫曼编码译码系统实验报告,数据结构课程设计.pdf

2022年数据结构哈夫曼编码实验报告.pdf

Matlab函数实现哈夫曼编码算法.pdf

实验六 哈夫曼树及哈夫曼编码.pdf

实验四 哈夫曼树与哈夫曼编码.pdf

实验四哈夫曼树及哈夫曼编码.pdf

实验四--哈夫曼树与哈夫曼编码.pdf

实验四哈夫曼树及哈夫曼编码 (2).pdf

最新资源

实验六哈夫曼树及哈夫曼编码.pdf

实验四哈夫曼树与哈夫曼编码.pdf