哈夫曼树带权路径长度_c 哈夫曼树编码_数据结构哈夫曼树编码

哈夫曼(Huffman)树与哈夫曼码

1.输入一个文本，统计各字符出现的频度，输出结果;

2.使用二叉链表或三叉链表作存储结构，构造哈夫曼(Huffman)树;

3.确定和输出各字符的哈夫曼码;

4.输入一个由0和1组成的代码序列，翻译并输出与之对应的文本;

二、 数据结构及存储结构

在这个程序中我用了三叉链表tree作为哈夫曼树的结构：左、右儿子和父亲

节点;并且在开始，我还用此结构生成了单链表，用来存储读取的字符。编码的时候，我把编码放在栈结构stack中，然后逆序输出即为哈夫曼编码。存放叶节点时用到了指针数组。

struct tree(){

char data;

int m,sign;

struct tree *lchild,*rchild,*parent;

}

struct stack{

int data;

struct stack *next;

}

算法设计思想

先调用frequency函数读取字符，创建链表来存储字符及其相关信息;同时把字符放进数组中进行备份，因为后面编码时要用到这些字符(它们就是叶节点)。然后遍历这个链表输出个字符的频度。接着调用ctree函数来生成哈夫曼树。在ctree函数中，首先对刚才那个链表按照频度排序，变成频度递增链表;然后取其前两个节点作为新建哈夫曼树的左右儿子(注：左儿子的频度<=右儿子的频度)，再把它们从链表中删除，并且把新建的哈夫曼树的根结点插入到链表中。这样重复操作，就生成了哈夫曼树。然后调用ccode函数编码。我采用的是从叶到根的编码方式。先从数组中取出数据(即为一个叶节点)，看其m的值(0/1)，放进stack栈中，然后向根遍历，接着把栈中的数据取出输出，即为编码。最后调用translate函数进行译码。先读取01序列放进新创建的一个链表(队列形式)中，然后从根到叶进行遍历：从链表中取出一个数据，是0则到左子树，1则到右子树，如果其左右子树为空，则输出字符data，再取下一个数据从根重新遍历。这样就得到译码了。

心得体会

这次编程，从开始编到测试成功，我一共花了四天。这主要是因为之前我花了不少时间看书，把数据结构和存储结构都想好了，还看了大量程序，不管是相关还是不相关的。例如，有一个困扰我很久的问题：当询问是否继续时，输入y就继续，否则跳出;以前用getchar要等按了回车才进行判断，如果按了好几个y，则后面几个y被当成以后的输入处理了，这样就会出错。然而我在一个程序中看到了getche这个指令解决了这个问题，它不需等回车就进行处理。c 哈夫曼树编码另外在定义哈夫曼树结构时，我加了个sign变量来标志它是左子树还是右子树，这样后面编码时就很方便。这次编程使我认识到：要重视细节，虽然很小，但是它会使程序不能运行或出错。这个程序中我由于把‘y’写成y，结果浪费了我半天的时间去查错。

五、 程序清单

#include

#include

struct tree{ /*定义哈夫曼树的结构*/

char data; /*存放字符*/

int m,sign; /*m存放字符出现的频率 sign是左(0)或右(1)儿子的标志*/

struct tree *lchild,*rchild,*parent; /*左儿子 右儿子 父节点*/

};

struct stack{ /*定义栈的结构*/

int data;

struct stack *next;

};

struct tree * ps[50],*root,*head;

/*数组存放字符 root为二叉树的根结点 head为链表的头节点*/

int size; /*标志字符个数*/

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-35162-1.html