数据结构哈夫曼树和哈夫曼编码 适合新手学习因为本人也是新手，嘻嘻嘻
【摘要】
哈夫曼树和哈夫曼编码
给大家两句口诀 “选择两小造新树，删除两小造新人” 先看懂图这里有篇代码 大家可以对照一下 都是大同小异
#include <stdio.h>
#include...
哈夫曼树和哈夫曼编码
给大家两句口诀 “选择两小造新树，删除两小造新人”
先看懂图这里有篇代码 大家可以对照一下 都是大同小异
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>
#define MAX 17
typedef struct
{
unsigned int weight;
unsigned int parent, lchild, rchild;
}HTnode, *Huffmantree;
typedef char * *Huffmancode;
void select(Huffmantree HT, int n, int *s1, int *s2)
{
int i, t;
t = 1000;
for (i = 1; i <= n; i++)
if (HT[i].parent == 0 && HT[i].weight < t)
{
t = HT[i].weight;
*s1 = i;
}
t = 1000;
for (i = 1; i <= n; i++)
if (HT[i].parent == 0 && HT[i].weight < t&&i!= *s1)
{
t = HT[i].weight;
*s2 = i;
}
}
void Huffmancoding(Huffmantree HT, Huffmancode HC, int *w, int n)
{
int p1, q2;
int *s1, *s2;
int m, i, f, start, c;
char *cd;
Huffmantree p;
s1 = &p1;
s2 = &q2;
if (n <= 1) return;
m = 2 * n - 1; w = w + 1;
HT = (Huffmantree)malloc((m + 1) * sizeof(HTnode));
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)
{
select(HT, i - 1, s1, s2);
HT[p1].parent = i;
HT[q2].parent = i;
HT[i].lchild = p1;
HT[i].rchild = q2;
HT[i].weight = HT[p1].weight + HT[q2].weight;
}
HC = (Huffmancode)malloc((n + 1) * sizeof(char *));
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';
else cd[--start] = '1';
HC[i] = (char *)malloc((n - start) * sizeof(char));
strcpy(HC[i], &cd[start]);
}
free(cd);
printf("Print the Huffmantree:\n");
printf(" weight parent lchild rchild\n");
for (i = 1; i <= 2 * n - 1; i++)
{
printf("%2d %3d %3d", i, HT[i].weight, HT[i].parent);
printf(" %3d %3d\n", HT[i].lchild, HT[i].rchild);
}
printf("Print the Humancode :\n");
for (i = 1; i < n + 1; i++)
printf("the code of %2d is %s\n", i, HC[i]);
}
void main()
{
Huffmantree HT = NULL;
Huffmancode HC = NULL;
int n = 1, data, i, w[MAX];
printf("Please input the weight of the elements of huffmantree (input -1 to exit)\n");
scanf_s("%d", &data);
while (data != -1)
{
w[n] = data;
n++;
scanf_s("%d", &data);
}
n = n - 1;
Huffmancoding(HT, HC, w, n);
_getch();
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
#include<stdio.h>
#include<iostream>
#include<malloc.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>//算法,头文件包含求最大最小等
#define MAX_NUM 100//最大数字个数为100
#define inf 2000000000 //最大值为
using namespace std;
using namespace std;
typedef struct {
unsigned int weight;//权值 数字无符号
unsigned int parent, lchild, rchild;//父节点，孩子结点的权值
}HTNode, *HuffmanTree;
typedef char * * HuffmanCode;//二维字符数组
int s1, s2;//最小的两个结点
void Select(HuffmanTree &HT, int x)
{//选出无父结点，并且权值最小的两个结点，赋值给s1，s2
int i, min1 = inf, min2 = inf;
for (i = 1; i <= x; i++) {//找最小
if (HT[i].weight < min1&&HT[i].parent == 0)
{
min1 = HT[i].weight;
s1 = i;//选出该权值是第几个
}
for (i = 1; i <= x; i++) {//找次小
if (HT[i].weight < min2&&i != s1 && HT[i].parent == 0)
{
min2 = HT[i].weight;
s2 = i;
}
}
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)
{//根据输入的结点的权值和个数来构建赫夫曼树 //创建数 和编码的地址
if (n <= 1)return;
int m = 2 * n - 1;//n个叶子，有2*n-1个结点
int i;
HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode));//0号单元未用 开辟空间
HuffmanTree p;
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++)
{
Select(HT, i - 1);//选出最小的两个无父节点的结点
HT[s1].parent = i; //找到第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 *));//申请一段以HC为首地址的内存，可以看成二维字符数组 ，这里先申请了第一维
char *cd = (char *)malloc(n * sizeof(char));//申请一段临时工作空间
cd[n - 1] = '\0';//编码结束符
for (i = 1; i <= n; i++) {
int start = n - 1, c, f;
for (c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent) {//从叶子到根逆向求编码
if (HT[f].lchild == c)
cd[--start] = '0';//如果当前结点是父节点的左孩子，则存一个1
else
cd[--start] = '1';//反之
}
HC[i] = (char *)malloc((n - start) * sizeof(char));//申请第二维
strcpy(HC[i], &cd[start]);//将编码从工作空间存入赫夫曼编码表中
}
free(cd); //释放临时空间
}
int main() {
HuffmanTree HT;//自定义结构体 ht
HuffmanCode HC;
int w[MAX_NUM], n;
int i;
printf("输入结点的个数:\n");
scanf_s("%d", &n);
printf("输入每个结点的权值:\n");
for (i = 0; i < n; i++)
scanf_s("%d", &w[i]);
HuffmanCoding(HT, HC, w, n);
for (i = 1; i <= n; i++)
printf("%d的赫夫曼编码为：%s\n", HT[i].weight, HC[i]);
return 0;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
文章来源: blog.csdn.net，作者：肥学，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/jiahuiandxuehui/article/details/110200699
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）