#include <stdio.h>
#include <stdlib.h>
typedef struct _Node{
float data;
struct _Node *lchild;
struct _Node *rchild;
int huffmanCode[10],pos;//保存编码,在数组中从后往前存储,最多10位
} Node,*Tree;
/* 排序算法,从大到小 */
void Sort(float a[],int low,int high)
{
int i;
float temp;
if(low == high)return;
for(i=low; i<=high; i++){
if(a[i] > a[low]){
temp = a[low];
a[low] = a[i];
a[i] = temp;
}
}
Sort(a,low+1,high);
}
/* 将一个字符型数组 char a[]转化为 Tree型数组,而且已经从大到小排序
* 为构建哈夫曼树做准备*/
Tree* InitHuffmanTree(float a[],int count)
{
int i,j;
Tree T ;
Sort(a,0,count-1);//先排序
Tree *HuffmanTrees = (Tree *)malloc(sizeof(Tree));
for(i=0; i<count; i++){
T = (Node *)malloc(sizeof(Node));
T->data = a[i];
T->lchild = T->rchild = NULL;
T->pos = 10;
HuffmanTrees[i] = T;
}
return HuffmanTrees;
}
/* 给一棵子树的节点赋哈夫曼编码 */
void Encoding(Tree head,int code)
{
if(!head)return;
head->huffmanCode[--(head->pos)] = code;
Encoding(head->lchild,code);
Encoding(head->rchild,code);
}
/* 构建哈夫曼树,打印哈夫曼编码
* huffmanTrees[]中存储的是所有huffman树的根,
* 而且已经从大到小排序*/
Tree CreateHuffmanTree(Tree *huffmanTrees,int count)
{
int i;
if(count <= 1)return huffmanTrees[0];
Node *newTree = NULL;
if(!(newTree=(Node *)malloc(sizeof(Node))))printf("overflow!\n");
newTree->data = huffmanTrees[count-1]->data + huffmanTrees[count-2]->data;
newTree->lchild = huffmanTrees[count-1];
Encoding(huffmanTrees[count-1],0);//修改子树的哈夫曼编码
newTree->rchild = huffmanTrees[count-2];
Encoding(huffmanTrees[count-2],1);
newTree->pos = 10;
count -= 2;
/*插入合适位置(从大到小顺序)*/
for(i=count; i>0 && newTree->data > huffmanTrees[i-1]->data; i--)
{
huffmanTrees[i] = huffmanTrees[i-1];
}
huffmanTrees[i] = newTree;
count++;
return CreateHuffmanTree(huffmanTrees,count);
}
/* 输出哈夫曼编码 : 左0右1*/
float printHuffmanCode(Tree head)
{
int i;
static float length = 0,TotLen=0,num=0;
if(!head)return length;
if (!head->lchild && !head->rchild)
{
for(i=head->pos; i<10; i++)printf("%d",head->huffmanCode[i]);
printf("\t%.2f\n",head->data);
TotLen += head->data * (10-head->pos);
num += head->data;
}
printHuffmanCode(head->lchild);
printHuffmanCode(head->rchild);
length = TotLen/num;
return length;
}
int main(int argc, char *argv[])
{
float a[] = {.23,.11,.05,.03,.29,.14,.07,.08},length;
int count = 8;
Tree *huffmanTrees = InitHuffmanTree(a,count);
Tree huffmanTree = CreateHuffmanTree(huffmanTrees,count);
printf("Here is the HuffmanCode :\n\n");
length = printHuffmanCode(huffmanTree);
printf("\nAverage length of the code : %.2f\n",length);
getchar();
}
分享到:
相关推荐
给定n个权值作为n的叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短...使用数组构建哈夫曼树,并可用该树构造哈夫曼编码。
头歌数据结构构建哈夫曼树及编码 第1关构建哈夫曼树 第2关根据哈夫曼树构建哈夫曼编码 通过哈夫曼树的构造,深刻理解二叉树的构造。 通过哈夫曼编/译码过程,深刻领会二叉树的基本操作和二叉树的应用,熟练掌握...
自己写的哈夫曼树还行 各位看官来下载吧 测试无错误
哈夫曼树 哈夫曼编码 最优二叉树 判定问题
构建哈夫曼树,对其进行编码,实现译码功能,数据结构的实验报告。。
哈夫曼树构造 输出
从终端读入字符集大小n , 以及n个字符和n个权值,建立哈夫曼树,并将它存于文件hfmTree中。 (2)E:编码(Encoding)。利用已建好的哈夫曼树(如不在内存,则从文件hfmTree中读人),对文件ToBeTran中的正文进行编码,...
构建哈夫曼树及哈夫曼编码,输出哈夫曼树及哈夫曼编码,完成编码与译码的算法。 (1)掌握树的有关操作算法 (2)熟悉树的基本存储方法 (3)学习利用树求解实际问题
哈夫曼编码、哈夫曼树构建、哈夫曼树Java实现.docx哈夫曼编码、哈夫曼树构建、哈夫曼树Java实现.docx
首先根据给定的n个字符的权值构造哈夫曼树。通过遍历此二叉树完成各字符的哈夫曼编码,另输入一组‘0’、‘1’代码构成的报文将其翻译成对应的字符信息。
用户键盘输入若干个整数作为待编码字符的权值,程序建立哈夫曼树并输出各字符的哈夫曼编码。
1) 从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式(比如树)显示在终端上; 2) 利用已经建好的哈夫曼树(如不在内存,则从文件htmTree中...
哈夫曼树的构造以及应用。其应用主要是信息编码。
数据结构课程设计:哈夫曼树及其应用 文档 ++代码 构建哈夫曼树,编码,译码
采用二叉树结构 构建哈夫曼树 并对字符串进行赫夫曼编码跟赫夫曼解码
上机后的代码,内容为构建哈夫曼树,并求最短编码长度。
1、根据给定的一个文本文件,读出其内容,统计各个字符出现的频度,建立哈夫曼树...打印哈夫曼树形结构,然后对文件进行编码;最后,对编码后的文件在解码,对哈夫曼算法进行验证。 扩展功能:对文件进行压缩、解压缩。
输入字符串 构建哈夫曼编码和相应的树型结构
本文主要针对输入的十个整型数,进行归一化之后,构建合适的哈夫曼树,在哈夫曼树的基础上进行哈夫曼编码设计,并就构造哈夫曼树和进行哈夫曼编码的算法进行了较为细致的描述。本文另附二叉树的遍历搜索源码,较为...
课 题:哈夫曼编码译码器系统 问题描述:打开一篇英文...3. 以字符出现字数作为权值,构建哈夫曼树,并将哈夫曼树的存储结构的初态和终态进行输出; 4. 对每个字符进行编码并将所编码写入文件然后对所编码进行破译。