#include
#include
#include
#include
using namespace std;
typedef struct
{
unsigned int weight; //结点权值
unsigned int parent, lchild, rchild; //结点的父指针，左右孩子指针
}HTNode, HuffmanTree; //动态分配数组存储哈夫曼树
typedef char **HuffmanCode; //动态分配数组存储哈夫曼编码表
HuffmanTree HT; //哈夫曼树HT
HuffmanCode HC; //哈夫曼编码表HC
unsigned int *w; //w存放叶子结点权值

char * source_code;//source_code 存放原始码
void CreateHuffmanTree(HuffmanTree &, unsigned int
, int); //生成一棵哈夫曼树
void HuffmanCoding(HuffmanTree, HuffmanCode &, int); //对哈夫曼树进行编码
void PrintHuffmanCode(HuffmanCode, unsigned int*, int); //显示哈夫曼编码
void Select(HuffmanTree, int, int&, int&); //在数组中寻找权值最小的两个结点
int main()
{
int n, i; //n是哈夫曼树叶子结点数
char choose = 'y'; //用于选择程序是否退出
//程序解说
printf("本程序将演示构造哈夫曼树.\n");
printf("首先输入叶子结点数目.\n例如:2\n");
printf("然后输入原始码以及权值.\n");
printf("第1个原始码及其权值 :");
printf("a 5\n");
printf("第2个原始码及其权值 :");
printf("b 3\n");
printf("程序会构造一棵哈夫曼树并显示哈夫曼编码.\n");
cout << "权值" << " " << "原始码" << " " << "哈夫曼编码" << endl;
printf(" 5 a 1\n");
printf(" 3 b 0\n");
putchar('\n');
putchar('\n');
while (choose != 'N'&&choose != 'n')
{
printf("请输入叶子结点数目:");
scanf("%d", &n); //输入叶子结点数
if (n <= 1)
{
printf("该数不合理!\n"); continue;
}
w = (unsigned int*)malloc(n * sizeof(unsigned int)); //开辟空间存放权值
source_code = (char *)malloc(n * sizeof(char)); //开辟空间存放原始码
//printf("请输入各原始码以及权值 :\n");
for (i = 0; i < n; i++)
{
printf("第%d个原始码及其权值 :", i + 1);
cin >> source_code[i]; //输入原始码
cin >> w[i]; //输入各叶子结点权值
}
CreateHuffmanTree(HT, w, n); //生成哈夫曼树
HuffmanCoding(HT, HC, n); //进行哈夫曼编码
putchar('\n');
PrintHuffmanCode(HC, w, n); //显示哈夫曼编码
printf("哈夫曼树构造完毕，还要继续吗?(Y/N)");
scanf(" %c", &choose);
}
}
void CreateHuffmanTree(HuffmanTree &HT, unsigned int *w, int n)
{//w存放n个结点的权值，将构造一棵哈夫曼树HT
int i, m;
int s1, s2;
HuffmanTree p;
if (n <= 1) return;
m = 2 * n - 1; //n个叶子结点的哈夫曼树，有2*n-1个结点
HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode)); //开辟2*n各结点空间，0号单元不用
for (p = HT + 1, i = 1; i <= n; ++i, ++p, ++w) //进行初始化
{
p->weight = *w;
p->parent = 0;
p->lchild = 0;
p->rchild = 0;
}
for (; i <= m; ++i, ++p)
{
p->weight = 0;
p->parent = 0;
p->lchild = 0;
p->rchild = 0;
}
for (i = n + 1; i <= m; ++i) //建哈夫曼树
{
//从HT[1...i-1]中选择parent为0且weight最小的两个结点，其序号分别为s1和s2
Select(HT, i - 1, s1, s2);
HT[s1].parent = i; HT[s2].parent = i; //修改s1和s2结点的父指针parent
HT[i].lchild = s1; HT[i].rchild = s2; //修改i结点的左右孩子指针
HT[i].weight = HT[s1].weight + HT[s2].weight; //修改权值
}
}
void HuffmanCoding(HuffmanTree HT, HuffmanCode &HC, int n)
{
//将有n个叶子结点的哈夫曼树HT进行编码， 所编的码存放在HC中
//方法是从叶子到根逆向求每个叶子结点的哈夫曼编码
int i, c, f, start;
char *cd;
HC = (HuffmanCode)malloc((n + 1) * sizeof(char *)); //分配n个编码的头指针向量
cd = (char *)malloc(n * sizeof(char)); //开辟一个求编码的工作空间
cd[n - 1] = '\0'; //编码结束符
for (i = 1; 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'; //若是左孩子编为'0'
else
cd[--start] = '1'; //若是右孩子编为'1'
HC[i] = (char *)malloc((n - start) * sizeof(char)); //为第i个编码分配空间
strcpy(HC[i], &cd[start]); //将编码从cd复制到HC中
}
free(cd); //释放工作空间
}
void PrintHuffmanCode(HuffmanCode HC, unsigned int *w, int n)
{
//显示有n个叶子结点的哈夫曼树的编码表
int i;
printf("哈夫曼编码如下 :\n");
putchar('\n');
cout << "权值" << " " << "原始码" << " " << "哈夫曼编码" << endl;
for (i = 1; i <= n; i++)
{
printf(" %d", w[i - 1]);
printf(" %3c\t ", source_code[i - 1]);
puts(HC[i]);
}
printf("\n");
}
void Select(HuffmanTree HT, int t, int&s1, int&s2)
{
//在HT[1...t]中选择parent不为0且权值最小的两个结点，其序号分别为s1和s2,s1存放最小的，s2存放次小的
int i = 0;
int j = 0;
int k = 0;
int least = 0;
int second = 0;

``````for (i = 1; i <= t; i++)
{
if (HT[i].parent == 0)

break;
}

for (j = i + 1; j <= t; j++)
{
if (HT[j].parent == 0)

break;
}

if (HT[i].weight < HT[j].weight)
{
least = i;
second = j;
}
else
{
least = j;
second = i;
}
for (k = j + 1; k <= t; k++)
{
if (HT[k].parent == 0)
{
if (HT[k].weight < HT[least].weight)
{
second = least;
least = k;
}
else if (HT[k].weight >= HT[least].weight && HT[k].weight < HT[second].weight)
second = k;
}
}
s1 = least;
s2 = second;
``````

}

0

1个回答

2

1. 背景 在通讯、计算机网络、数据压缩、图像处理中，哈夫曼编码是一项极其重要的技术。哈夫曼编码是建立在二叉哈夫曼树的基础上，如果能够找到比二叉哈夫曼树更好的数据结构，那么对数据压缩等将起到促进作用。本文通过论述二叉哈夫曼树编码算法以及普通的三叉哈夫曼树编码算法，给出一种优化的三叉哈夫曼编码算法。 2. 哈夫曼编码2.1 哈夫曼编码 哈夫曼编码是根据每个字符出现的频率进行编码的，依据字符出现

#include #include #include using namespace std;enum {ERROR,OK,OVERFLOW = 0};int Nil = ;typedef struct BiTNode{ int data; BiTNode *lchild,*rchild,*parent;}BiTNode,*BiTree;bool

【哈夫曼树的定义】：     哈夫曼树又称为最优二叉树，它是加权路径最短的二叉树。     不同于普通的二叉树，它的每个节点都有相应的权值，当我们构建的时候最终离根节点远的节点权重小，反之就比较大。 【哈夫曼树的实现】: 1、利用的核心思想：贪心算法      贪心算法：是指在问题进行求解的时候，总是做出当前看起来最好的选择。即就是说贪心算法做出不是整体的最优解，而是某种

1、问题描述       利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。构造哈夫曼树时，首先将由n个字 符形成的n个叶子结点存放到数组HuffNode的前n个分量中，然后根据哈夫曼方法的基本思想，不断将两个较小的子树合并为一个 较大的子树，每次构成的新子树的根结点顺序放到HuffNode数组中的前n个分量的后面。        通俗的来讲，哈弗曼树就是一种广...
【数据结构】哈夫曼树编码/译码器

//三叉链表 #ifndef _PBITREE_H #define _PBITREE_H #incldue "BiTree.h" //包含二叉链表的头文件(见上一篇文章)//结点结构体templatestruct PBiTNode{T data;PBiTNode *lchild,*rchild,*parent;};  //类模板：继承自BiTree template class PBi

&amp;lt;!--[if !supportLists]--&amp;gt;一、&amp;lt;!--[endif]--&amp;gt;什么是链表？ 链表是使用指针进行连接的一种数据结构，他可以提供比数组更加灵活的数据存储。 认识一下链表之前，先知道节点。 Class Node { Object data;/用于存储数据； Node next;//指向下一个的指针 } 一、哈夫曼编码 以哈夫曼树─即最...

c++ 哈夫曼树简便构造(数据结构作业篇)
// 用最小栈方式构建哈弗曼树// 定义一个哈夫曼树的节点struct MinHeapNode {    // One of the input characters    char data;    // Frequency of the character    unsigned freq;    // 哈夫曼的编码值, #号表示无编码    string code_huff = &quot;#&quot;;  ...

#include #include #include using namespace std; int head, tail; typedef struct treenode { char data; treenode *lchild; treenode *rchild; treenode *parent; }node, *Tree; node *q[100];

/** 输入格式是 输入每个字符的次数 然后依次输出每个字符的编码 样例输入 3 a 10 b 5 c 8 4 a 1 b 1 c 1 d 1 样例输出 a:0 b:10 c:11 a:00 b:01 c:10 d:11 */  #include #include typedef struct tree {     char ch;
c++ 数据结构 *** 哈夫曼树的应用——压缩软件

1、Huffman(哈夫曼)树的一些基本概念 1、1哈夫曼树的定义 最简哈夫曼树是一种数据结构，是由德国数学家冯·哈夫曼发现的，又称最优二叉树，是一种带权路径长最短的树。所以Huffman树是一种二叉树。 1、2哈夫曼树的经典应用 哈夫曼树最经典的应用时在通信领域的哈夫曼编码上面。经哈夫曼编码的信息消除了冗余的数据，加提高了通信信道的传输效率，目前，Huffman编码计数还是数据压缩的重要...
C语言实现Huffman树并计算带权路径长度
More Code,More progress #include #include typedef int ElemType; typedef struct _BTreeNode { ElemType data; struct _BTreeNode* left; struct _BTreeNode* right; }BTreeNode; //根据数组 a

1.问题描述从键盘接收一串电文字符，输入对应的Huffman编码。同时，能翻译由Huffman编码生成的代码串，输出对应的电文字符串。2.设计要求1） 构造一棵 Huffman树。 2） 实现Huffman编码，并用Huffman编码生成的代码串进行译码。 3） 程序中字符和权值是可变的，实现程序的灵活性。3.代码实现参考文章： http://blog.csdn.net/TW_345/a
JAVA数据结构与算法实现-哈夫曼树
JAVA数据结构与算法实现-哈夫曼树 哈夫曼树，是一种特殊的二叉树，由一个叫做哈夫曼的人实现出来的，由于他的一致性所以数据统一。在这里我使用数组实现二叉树的原理。 在这里我们首先创建一个二叉树节点的类，名为point： /** * Created by jim_D on 2018/10/11. */ public class point { int info;//定义节点的值 point lef...
《C++实现数据结构》：哈夫曼树

#include<stdio.h> #include<string.h> #include<stdlib.h> #define N 20//叶子结点最大值 #define M 2*N-1//所有结点最大值 //静态三叉链表实现哈夫曼树 typedef struct Huffman{ int weight; int parent; int lchild; int r

/* 根据Huffman树的构造原理进行构造 ... 哈夫曼树在编码压缩的领域有很好的应用,利用Huffman进行编码可以保证数据传输 的无二义性 。 但是要注意的是 对于出现频率大的数据我们应该尽量放在离根节点近的地方进行编码 , 出现频率小的数据我们可以放在距离根节点小的地方。 这样可以提高数据的传输效率 。 */ #include "stdio.h" #include "malloc.h
【C++数据结构】哈夫曼树代码实现
HuffeManTree.h#pragma once #include "Stack.h" // 我自己写的栈 #include "Stack.cpp"template<class T> class CTree { public: CTree(void);public: T data = NULL; int weight = 1; CTree* lNode = nu

【数据结构】哈夫曼树实现编码译码

【数据结构】二叉树（哈夫曼树）的JAVA代码实现

（1）递归实现二叉树的中序线索化 （2）非递归实现二叉树的中序线索化 （3）实现中序线索二叉树上遍历二叉树