-
哈夫曼树的生成以及编码
2019-11-11 00:08:47哈夫曼树的生成以及编码 #include <stdio.h> #include <stdlib.h> #include <string.h> #include<iostream> using namespace std; typedef int ELEMTYPE; typedef struct HuffmanTree { ...哈夫曼树的生成以及编码
#include <stdio.h> #include <stdlib.h> #include <string.h> #include<iostream> using namespace std; typedef int ELEMTYPE; typedef struct HuffmanTree { ELEMTYPE weight; char value; struct HuffmanTree* lchild; struct HuffmanTree* rchild; }HuffmanNode; // 构建哈夫曼树 HuffmanNode* createHuffmanTree(int* a,char* b,int n) { int i, j; HuffmanNode **temp, *hufmTree; temp = (HuffmanNode **)malloc(n * sizeof(HuffmanNode)); for (i = 0; i < n; ++i) // 将数组a中的权值赋给结点中的weight { temp[i] = (HuffmanNode*)malloc(sizeof(HuffmanNode)); temp[i]->weight = a[i]; temp[i]->lchild = temp[i]->rchild = NULL; temp[i]->value = b[i]; } for (i = 0; i < n - 1; ++i) // n-1次合并 { int small1 = -1, small2; // small1、small2分别作为最小和次小权值的下标 for (j = 0; j < n; ++j) // 先将最小的两个下标赋给small1、small2(注意:对应权值未必最小) { if (temp[j] != NULL && small1 == -1) { small1 = j; continue; } else if (temp[j] != NULL) { small2 = j; break; } } if (small1 > small2) { int t = small1; small1 = small2; small2 = t; } for (j = small2; j < n; ++j) // 比较权值,挪动small1和small2使之分别成为最小和次小权值的下标 { if (temp[j] != NULL) { if (temp[j]->weight < temp[small1]->weight) { small2 = small1; small1 = j; } else if (temp[j]->weight < temp[small2]->weight) { small2 = j; } } } hufmTree = (HuffmanNode*)malloc(sizeof(HuffmanNode)); hufmTree->weight = temp[small1]->weight + temp[small2]->weight; hufmTree->lchild = temp[small1]; hufmTree->rchild = temp[small2]; temp[small1] = hufmTree; temp[small2] = NULL; } return hufmTree; } // 递归进行哈夫曼编码 void HuffmanCode(HuffmanNode* hufmTree, int depth,int*code) // depth是哈夫曼树的深度 { if (hufmTree) { if (hufmTree->lchild == NULL && hufmTree->rchild == NULL) { printf("%c的哈夫曼编码为 ", hufmTree->value); int i; for (i = 0; i < depth; ++i) { printf("%d", code[i]); } printf("\n"); } else { code[depth] = 0; HuffmanCode(hufmTree->lchild, depth + 1,code); code[depth] = 1; HuffmanCode(hufmTree->rchild, depth + 1,code); } } } int main() { int i, n; char string[100]; printf("请输入叶子结点的个数:\n"); scanf("%d", &n); int* arr; arr = (int*)malloc(n * sizeof(ELEMTYPE)); printf("请输入%d个叶子结点的权值及其各自代表的字符:\n", n); for (i = 0; i < n; ++i) { printf("第%d个",i+1); scanf("%d", &arr[i]); scanf("%c", &string[i]); } HuffmanNode* hufmTree = NULL; hufmTree = createHuffmanTree(arr,string,n); int code[100]; printf("\n各叶子结点的哈夫曼编码为:\n"); HuffmanCode(hufmTree, 0,code); return 0; }
注意输入时权值与字符之间不加符号,否则会将空格当作字符,可以加一个getchar()来实现。
本文改编自
https://blog.csdn.net/F__shigang/article/details/65442550
删改了一些内容。 -
哈夫曼树的生成及哈夫曼编码
2017-12-20 22:43:07首先构造哈夫曼树结构体,初始化哈夫曼树的四个无符号整型域,输入文本,统计各个字符的权值,然后构建哈夫曼树,从根到叶子逆向求哈夫曼树的编码。#include"stdio.h" #include"string.h" #include"malloc.h" #...首先构造哈夫曼树结构体,初始化哈夫曼树的四个无符号整型域,输入文本,统计各个字符的权值,然后构建哈夫曼树,从根到叶子逆向求哈夫曼树的编码。
#include"stdio.h" #include"string.h" #include"malloc.h" #include"iostream" using namespace std; typedef struct{ unsigned int weight; unsigned int parent,lchild,rchild; }HTNode,*HuffTree; typedef char **HuffCode; void Select(HuffTree &Ht, int m, int &S1, int &S2) {/* Select函数,每次从前面数据中选择2个权值(weight值)最小的,将 最小的两个下标赋给s1,s2 */ int j; S1 = 0; S2 = 0; for (j = 1; j <= m; j++) { if (Ht[j].parent == 0 && Ht[j].weight != 0) { if (Ht[j].weight<Ht[S1].weight) S1 = j; } } for (j = 1; j <= m; j++) { if (Ht[j].parent == 0 && j != S1&&Ht[j].weight != 0) { if (Ht[j].weight<Ht[S2].weight) S2 = j; } } } void HuffmanCoding(HuffTree &Ht,HuffCode &Hc,int n){ //哈夫曼编码函数 if(n<=1)return; int m,i,s1, s2; HuffTree p; m =2*n-1; Ht = (HuffTree)malloc((m + 1) * sizeof(HTNode)); char ch[100]; for (p = Ht + 1, i = 1; i <= m; ++i, ++p) { //初始化哈夫曼树各个值 p->weight = 0; p->parent = 0; p->lchild = 0; p->rchild = 0; } cin >> ch; //读入一段文本 for (int i = 0; ch[i] !='\0'; i++) { Ht[ch[i] - 'a'+1].weight++; //当文本还没有结束时,统计各个字符的权值 } for(i=n+1;i<=m;++i){ //建哈夫曼树 Select(Ht,i-1,s1,s2); Ht[s1].parent=i;Ht[s2].parent=i; Ht[i].lchild=s1;Ht[i].rchild=s2; Ht[i].weight=Ht[s1].weight+Ht[s2].weight; } // 从叶子到根逆向求每个字符的哈夫曼编码 Hc=(HuffCode)malloc((n+1)*sizeof(char*)); char * cd=(char*)malloc((n)*sizeof(char)); int c,f; cd[n-1]='\0'; //编码结束符 int start; 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'; } //cd[n-1]='\0'; Hc[i]=(char *)malloc((n-start)*sizeof(char)); strcpy(Hc[i],&cd[start]); } free(cd); } void show(HuffCode &Hc, int n)//输出哈夫曼编码 { int i, k; cout<<" 输出哈夫曼编码:\n"; //输出哈夫曼编码 for (i = 1; i<=n; i++) { cout<< Hc[i]; cout<<"\n"; } }
然后在主函数中调用,加入输入输出语句即可
#include"1.h" using namespace std; int main() { HuffTree ht; HuffCode hc; int n; cout << "请输入文本"; HuffmanCoding(ht,hc,26); show(hc,26); system("pause"); }
-
构造哈夫曼树和生成哈夫曼编码
2019-01-25 17:12:36哈夫曼树是一种带权路径长度最短的二叉树,也称为最优二叉树。用一幅图来说明: 它们的带权路径长度分别为: 图a: WPL=5*2+7*2+2*2+13*2=54 图b: WPL=5*3+2*3+7*2+13*1=48 可见,图b的带权路径长度较小,...一、什么是哈夫曼树?
哈夫曼树是一种带权路径长度最短的二叉树,也称为最优二叉树。用一幅图来说明:
它们的带权路径长度分别为:
图a: WPL=5*2+7*2+2*2+13*2=54
图b: WPL=5*3+2*3+7*2+13*1=48
可见,图b的带权路径长度较小,可以证明图b就是哈夫曼树(也称为最优二叉树)。
二、如何构建哈夫曼树
一般按下面步骤构建:
1,将所有左,右子树都为空的作为根节点。
2,在森林中选出两棵根节点的权值最小的树作为一棵新树的左,右子树,且置新树的附加根节点的权值为其左,右子树上根节点的权值之和。注意,左子树的权值应小于右子树的权值。
3,从森林中删除这两棵树,同时把新树加入到森林中。
4,重复2,3步骤,直到森林中只有一棵树为止,此树便是哈夫曼树。
下面是构建哈夫曼树的图解过程:
三、哈夫曼编码
利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子节点都有一条路径,对路径上的各分支约定指向左子树的分支表示"0"码,指向右子树的分支表示"1"码,取每条路径上的"0"或"1"的序列作为各个叶子节点对应的字符编码,即是哈夫曼编码。
上图例子来说:
A,B,C,D对应的哈夫曼编码分别为:111,10,110,0
用图说明如下:
记住,设计电文总长最短的二进制前缀编码,就是以n个字符出现的频率作为权构造一棵哈夫曼树,由哈夫曼树求得的编码就是哈夫曼编码。
四、算法实现
/**
* 实验题目:
* 构造哈夫曼树和生成哈夫曼编码
* 实验目的:
* 领会哈夫曼的构造过程以及哈夫曼编码的生成过程
* 实验内容:
* 设计程序,构造一颗哈夫曼树,输出对应的哈夫曼
* 编码和平均查找长度。并用如下数据进行验证:
* 单词以及出现的频度
* The of a to and in that he is at on for His are be
* 1192 677 541 518 462 450 242 195 190 181 174 157 138 124 123
* 备注:二叉树中叶子结点个数为n,则二叉树中结点总数为(2 * n - 1)
*/#include <stdio.h>
#include <string.h>#define N (50) // 树中叶子结点数最大值
#define M (2 * N - 1) // 树中结点总数最大值typedef struct
{
char data[5]; // 结点值
int weight; // 权重
int parent; // 双亲结点
int lchild; // 左孩子结点
int rchild; // 右孩子结点
}HTNode; // 声明哈夫曼树结点类型typedef struct
{
char cd[N]; // 存放哈夫曼编码
int start;
}HCode; // 声明哈夫曼编码类型/*-------------由含有n个叶子结点的ht构造完整的哈夫曼树-----------------*/
static void create_huffman_tree(HTNode ht[], int n)
{
int i;
int k;
int lnode;
int rnode;
int min1;
int min2;// 所有结点的相关域设置初值为-1
for(i = 0; i < 2 * n - 1; i++)
ht[i].parent = ht[i].lchild = ht[i].rchild = -1;
for(i = n; i < 2 * n - 1; i++) // 构造哈夫曼树的分支结点
{
min1 = min2 = 32767;
lnode = rnode = -1;
for(k = 0; k <= i - 1; k++) // 查找最小和次小的结点
{
if(ht[k].parent == -1) // 只在尚未构造二叉树的结点中查找
{
if(ht[k].weight < min1)
{
min2 = min1;
rnode = lnode;
min1 = ht[k].weight;
lnode = k;
}
else if(ht[k].weight < min2)
{
min2 = ht[k].weight;
rnode = k;
}
}
}
ht[lnode].parent = i; // 合并两个最小和次小的结点
ht[rnode].parent = i;
ht[i].weight = ht[lnode].weight + ht[rnode].weight; // 计算双亲结点的权重
ht[i].lchild = lnode; // 设置双亲结点的左孩子
ht[i].rchild = rnode; // 设置双亲结点的右孩子
}
}/*-------------由哈夫曼树ht构造哈夫曼编码hcd-----------------*/
static void create_huffman_code(HTNode ht[], HCode hcd[], int n)
{
int i;
int f;
int c;
HCode hc;for(i = 0; i < n; i++) // 根据哈夫曼树构造所有叶子结点的哈夫曼编码
{
hc.start = n;
c = i;
f = ht[i].parent;
while(f != -1) // 循环直到树根结点
{
if(ht[f].lchild == c) // 处理左孩子结点
hc.cd[hc.start--] = '0';
else // 处理右孩子结点
hc.cd[hc.start--] = '1';
c = f;
f = ht[f].parent;
}
hc.start++; // start指向哈夫曼编码最开始字符
hcd[i] = hc;
}
}/*-------------输出哈夫曼编码-----------------*/
static void display_huffman_code(HTNode ht[], HCode hcd[], int n)
{
int i;
int k;
int sum = 0;
int m = 0;
int j;printf("输出哈夫曼编码:\n");
for(i = 0; i < n; i++)
{
j = 0;
printf(" %s:\t", ht[i].data);
for(k = hcd[i].start; k <= n; k++)
{
printf("%c", hcd[i].cd[k]);
j++;
}
m += ht[i].weight;
sum += ht[i].weight * j;
printf("\n");
}printf("\n平均长度 = %g\n", 1.0 * sum / m);
}int main(void)
{
int n = 15;
int i;
HTNode ht[M];
HCode hcd[N];
char *str[] = {"The", "of", "a", "to", "and", "in", "that", "he", "is", "at", "on", "for", "His", "are", "be"};
int fnum[] = {1192, 677, 541, 518, 462, 450, 242, 195, 190, 181, 174, 157, 138, 124, 123};for(i = 0; i < n; i++)
{
strcpy(ht[i].data, str[i]);
ht[i].weight = fnum[i];
}
create_huffman_tree(ht, n); // 创建哈夫曼树
create_huffman_code(ht, hcd, n); // 构造哈夫曼编码
display_huffman_code(ht, hcd, n); // 输出哈夫曼编码return 0;
}
测试结果:输出哈夫曼编码:
The: 01
of: 101
a: 001
to: 000
and: 1110
in: 1101
that: 11110
he: 11001
is: 11000
at: 10011
on: 10010
for: 10001
His: 10000
are: 111111
be: 111110平均长度 = 3.56208
-
C/C++实现哈夫曼树和生成哈夫曼编码
2019-07-01 14:52:39然后将相加得到的值从新放入,然后又从中找到最小的两个值,然后用这个两个值一直相加,直到只剩最后一个值,将这个值作为哈夫曼树的根。 生成哈夫曼编码,如果是左子树的话为0,右子树的话为1,从父节点还是往下找...用C语言实现哈夫曼树和生成哈夫曼编码,首先生成哈夫曼树,哈夫曼树是从中选取权值最小的两个进行相加,将这两个分别做为生成的左子树和右子树,左子树要比右子树小。然后将相加得到的值从新放入,然后又从中找到最小的两个值,然后用这个两个值一直相加,直到只剩最后一个值,将这个值作为哈夫曼树的根。
生成哈夫曼编码,如果是左子树的话为0,右子树的话为1,从父节点还是往下找。然后这串代码就是哈夫曼编码。上代码
#include <iostream> #include <stdio.h> #include <stdlib.h> #include<bits/stdc++.h> using namespace std; const int Lsize = 1000000; typedef struct{ int order;//序号 char character;//字符值 int weight;//权重 int parent; int lift_Child; int right_Child; int deep; int code[100];//哈夫曼编码 }Nodetree,*HuffmanTree; typedef struct node{ char symbol; int quantity; struct node *next; }Node; int getListSize(char *pStr){ int len=0; char *start = pStr; while(*start){ len++; start++; } return len; } int getLIstLink(Node *head){ int a = 0; Node *p = head->next; while(p){ a++; p = p->next; } return a; }; //打印链表 void print(struct node *head){ struct node *p ; printf("开始打印\n"); p=head->next ; if(p == NULL){ printf("值为空\n"); } while(p!=NULL){ printf(" %c",p->symbol); printf(" %d\n",p->quantity); p=p->next; } }; int QueryNOde(Node *head,char ch){ Node *p; p = head->next; while(p!=NULL){ if(p->symbol == ch){ p->quantity = p->quantity + 1;//字符存在节点加1 return 1;//这个字符已经存在 } p = p->next; } return 0;//这个字符不存在 }; //生成权值 Node *createWeight(char *str){ Node *head , *q ,*p; int list_size = getListSize(str); q=head=(struct node*)malloc(sizeof(struct node)); for(int i = 0 ; i < list_size ; i++){ //printf("当前的值:%c\n",*str); if(QueryNOde(head,*str)==1){//如果该数据已经存在,则节点加1 // printf("开始遍历\n"); // Node *boos = head = (struct node*)malloc(sizeof(struct node)); // printf("开始查找\n"); // while(boos){ // printf("进入查找\n"); // printf("当前遍历值为:%c\n",boos->symbol); // if(boos->symbol == *str){ // printf("开始修改值\n"); // boos->quantity = boos->quantity + 1; // printf("值相同\n"); // break; // } // boos = boos->next; //} } else{//生成新的权值 p = (struct node*)malloc(sizeof(struct node)); p->quantity = 1; p->symbol = *str; p->next = NULL; q->next = p; q = p; //printf("值不同\n"); } str++; } return head; }; void createTree(HuffmanTree &root,int n,Node *head){ if(n<=0){ return; } Node *q; q = head->next; int length = 2*n - 1; printf("n is %d\n",n); int HFCode[100];//哈夫曼编码数组 root = new Nodetree[length+1]; //初始化哈夫曼树 for(int i = 1;i<=length;i++){ root[i].order = i; root[i].character = 0; root[i].parent = 0; root[i].lift_Child = 0; root[i].right_Child = 0; } //给哈夫曼树赋值 for(int i = 1;i<=n;i++){ root[i].character = q->symbol; root[i].weight = q->quantity; q = q->next; } //开始建立哈夫曼树 for(int i = n+1; i <=length; i++){ //进行 n-1 次循环建立哈夫曼树 //k1表示森林中具有最小权值的树根结点的下标,k2为次最小的下标 int k1 = -1 , k2; for(int j = 0; j < i; j++){ if ( root[j].parent == 0 && k1 == -1 && root[j].weight > 0){ k1 = j; continue; } if (root[j].parent == 0 && root[j].weight > 0){ k2 = j; break; } } //将指针数组中的指针指向的最小值赋值给索引号为k1的,次小值赋值给索引号为k2的 for (int j = k2; j < i; j++){ if(root[j].parent == 0 ){ if(root[j].weight < root[k1].weight){ k2 = k1; k1 = j; }else if(root[j].weight < root[k2].weight){ k2 = j; } } } //开始生成新的哈夫曼树节点 root[k1].parent = i; root[k2].parent = i; // printf(" i is:%d\n",i); // printf("k1 is :%d\n",k1); // printf("k2 is :%d\n",k2); // printf(" k1 weight is:%d\n",root[k1].weight); // printf(" k2 weight is:%d\n",root[k2].weight); root[i].order = i; root[i].lift_Child = k1; root[i].right_Child = k2; root[i].weight = root[k1].weight + root[k2].weight; } int start; // HFCode[n-1]='\0'; //生成哈夫曼编码 for(int i = 1;i<=n;i++){ start = 0; int deep = 0;//节点的深度 int c = i; int f = root[i].parent; while(f!=0){ //printf("tart is:%d\n",start); if(root[f].lift_Child == c){ root[i].code[start] = 0;//如果为左子树就为0 }else{ root[i].code[start] = 1;//右子树就为1 } deep++; start++; c = f; f = root[f].parent; } root[i].deep = deep; // printf("code is:%d\n",root[i].code[start]); } }; //void CreatHFCode(Nodetree *root,) //打印哈夫曼树的表态结构 void printTree(Nodetree *root,int n){ int length = 2*n -1; for(int i = 1 ;i<=length;i++){ printf("order is %d character is %c" " parent is %d LiftC is %d rightC is %d weight is %d deep is %d ",root[i].order, root[i].character, root[i].parent,root[i].lift_Child,root[i].right_Child, root[i].weight,root[i].deep); int deep = root[i].deep; printf("HFCode is :"); for(int j=deep-1;j>=0;j--){ printf("%d",root[i].code[j]); } printf("\n"); } }; void QueryCOde(Nodetree *root,int n){ int query_list[100];//哈夫曼编码整数数组 int flag ;//哈夫曼编码匹配判断标志 int c; int code_Size; char query_char[100];//用来接收哈夫曼编码 scanf("%s",&query_char); //printf("%s\n",query_char); code_Size = getListSize(query_char);//输入的哈夫曼编码长度 //将输入的哈夫曼编码有字符数组转换为整数数组 for(int i = 0;i<code_Size;i++){ c = query_char[i]-'0'; query_list[i] = c; // printf("n is:%d\n",c); } // for(int i=0;i<code_Size;i++){ // printf("%d ",query_list[i]); // } for(int i=1;i<=n;i++){ int deep = root[i].deep; int j ; //若哈夫曼的深度和输入的哈夫曼编码长度相同则开始查找 if(deep==code_Size){ //printf("deep is:%d code_size is:%d\n",deep,code_Size); j=0; int code = code_Size-1; deep--; //开始匹配值 flag = i; while(deep>=0){ // printf("开始匹配deep %d\n",deep); if(root[i].code[j]!=query_list[code]){ //printf("值不相同\n"); flag = -1; break; } j++; code--; //printf("%d deep is %d\n",i,deep); deep--; } } //判断是否找到对应的权重的值 // printf("deep is:%d\n",deep); if(deep<0){ flag = i; i = n+1; } } // printf("flag is:%d\n",flag); if(flag>0){ printf("翻译结果值:%c\n",root[flag].character); } else{ printf("没有与编码匹配的数据值\n"); } }; int main() { int Link_size ; struct node *head; Nodetree *root; char input_list[Lsize]; printf("........................功能列表...................\n"); printf(".............. 输入报文 ................\n"); printf(".............. 打印频度 ................\n"); printf(".............. 建立哈夫曼树 ................\n"); printf(".............. 翻译报文 ................\n"); //printf(".............. 5.退出 ................\n"); printf("..............输入想要赋值的字符串\n"); scanf("%s",&input_list); gets(input_list); printf("%s\n",input_list); head = createWeight(input_list); printf("..............出现频度为\n"); print(head); Link_size = getLIstLink(head); printf("..............链表长度为:%d\n",Link_size); createTree(root,Link_size,head); printTree(root,Link_size); int flag = 1; while(flag==1){ printf("..............输入你想要查找的代码\n"); QueryCOde(root,Link_size); printf("..............想继续查找输入1,不想输入0\n"); scanf("%d",&flag); } }
代码里面有备注,不清楚的可以留言,有错误的欢迎指出。
-
C语言利用哈夫曼树实现哈夫曼树生成和哈夫曼编码的实现
2018-10-26 15:20:06//哈夫曼编码里的权值,赋值给哈夫曼树里面的权值 HT[i].lchild = HT[i].rchild = HT[i].parent = 0;//双亲,左右子树全部赋值为0 } /*整个树的节点数是2*length-1,刨去第0个,就是2*length 上面一个循环已经... -
C++构造哈夫曼树生成哈夫曼编码
2020-12-06 18:22:32构造哈夫曼树生成哈夫曼编码 参考 程序员小灰-漫画:什么是 “哈夫曼树” ? 程序员小灰-漫画:“哈夫曼编码” 是什么鬼? 编写一个程序exp7-5.cpp,构造一棵哈夫曼树, 输出对应的哈夫曼编码和平均查找长度, 并对... -
哈夫曼树生成优化与哈夫曼编码的实现
2020-05-07 00:05:42#include <iostream> using namespace std; #define MAX 50 ...typedef struct //哈夫曼树结点结构 { char data; int weight; int parent; int lchild; int rchild; }HuffNode; typedef struct ... -
哈夫曼编码生成哈夫曼树
2017-05-21 19:41:59哈夫曼编码:从队列中取出权重最小的两个节点,进行构造树 将新生成的节点作为父节点 使用结构体: Node(node1,node2,weight) //权重边信息保存 HuffmanTree(weight,family,lchild,rchil -
数据结构编程实践(七)创建哈夫曼树、生成哈夫曼编码、完成图片的压缩与解压缩
2018-07-11 15:30:18一、对图片的压缩与解压缩,涉及以下内容:1.文件读写2.创建Huffman树3.生成Huffman编码4.压缩图片文件5 ....任务三:解压压缩文件,恢复原文件下面开始完整的步骤:三、统计权值、生成Huffman树1.Huffma... -
生成哈夫曼树
2020-01-05 20:43:23哈夫曼树的模板题,每次去两个最小的数,相加,再把它们的和加入数组。 #include<iostream> #include<string> #include<cstring> #include<cmath> #include<cstdio> #include<qu... -
哈夫曼树与哈夫曼编码
2016-12-16 20:37:171、使学生熟练掌握哈夫曼树的生成算法。 2、熟练掌握哈夫曼编码的方法。 二、实验内容 本次实验提供4个题目,难度相当,学生可以根据自己的情况选做,其中题目一是必做题,其它选作! 题目:哈夫曼树和哈夫曼... -
最小生成树与哈夫曼树
2019-08-25 10:41:44转载自添加链接描述 最小生成树 定义:在连通网的所有生成树中,所有边的代价和最小的生成树,称为最小生成树。 算法: Kruskal算法(加边法):初始最小生成树边数为0,每迭代一次就选择一条...哈夫曼树 定义:... -
哈夫曼树和哈夫曼编码——二叉排序树——最小生成树
2018-04-10 13:02:39哈夫曼树的左分支为0,右分支为1,从根节点到每个节点比如经历两次右分支则,编码就是11.二叉排序树选取第一个为根节点,然后把下一个要插入的节点与根节点进行比较,大的放在右子树,小的放在左子树位置。最小生成... -
对应生成树的基本回路_c++哈夫曼树学习笔记(亮点:融合了求哈夫曼树编码长度的代码)...
2021-01-01 08:21:07二叉树带权路径长度:设二叉树有n个带有权值的叶子结点,每个叶子到根的路径长度乘以其...哈夫曼树的构造过程假定有n个具有权值的结点,则哈夫曼树的构造算法如下: ① 根据n个权值,构造n棵二叉树,其中每棵二叉树... -
哈夫曼树 (100分)哈夫曼树
2020-05-18 21:07:25需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出哈夫曼树的带权路径长度(WPL)。 输入格式: 第一行输入一个数n,第二行输入n个叶结点(叶结点权值不超过1000,2<=n&... -
【哈夫曼树】牛客 哈夫曼树
2019-01-28 00:31:56需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出所有结点的值与权值的乘积之和。 输入描述: 输入有多组数据。 每组第一行输入一个数n,接着输入n个叶节点(叶节点... -
哈夫曼树
2017-08-05 23:34:19生成哈夫曼树的第一步就是在结点集合中找到两个权值最小的结点,然后生成一棵二叉树 树中任意节点的权值一定大于自己的左右孩子,但不能保证一定不小于其他下一任结点的权值。设哈夫曼树中的叶子结点总数为m,若用... -
哈夫曼树生成、编码、译码
2019-10-11 16:38:26编程得出哈夫曼的码表;输入一段英文字符,利用码表对其编码、译码。 开发环境: VS2015(C++) 2.数据处理 数据归一化,使各英文字符概率之和为1。由于文献中各字符概率之和大于1,对数据进行归一化。将当前各... -
哈夫曼树的建立
2018-06-26 08:54:00掌握生成哈夫曼树的算法。 二、实验原理 哈夫曼树,即最优树,是带权路径长度最短的树。有着广泛的应用。在解决某些判定问题上,及字符编码上,有着重要的价值。 构造一棵哈夫曼树,哈夫曼最早给出了算法,称为... -
图形化生成树(二叉树 哈夫曼树 和 最小树)
2017-12-08 10:13:12没啥好说的 本来只想免费分享出去很早以前的课程设计 资源分最低最低只能选2,我就把二叉树 哈夫曼树 和 最小树放到一起了 作为参考啊 -
树3-2、哈夫曼树(利用最小堆生成的最优二叉树)与哈夫曼编码
2019-10-03 03:27:532、哈夫曼树的构造 ——>——>——>——> 算法:先选取两个权值最小的——用最小堆 二、哈夫曼编码 a:00 u:01 x:10 z:11 可以发现,如果他们都在叶结点上,那么任意一个字母... -
利用优先级队列生成 哈夫曼树
2017-05-17 08:17:13#include #include #include #include #include using namespace std;...//根据哈夫曼树的概念,这些结点有权值,即weight, //题目需要输出所有节点的值与权值的乘积之和 priority_queue , greater > Q; //建立一 -
解题思路:对 n 个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有 115 个结点,则 n 的值是:
2020-06-10 20:30:22哈夫曼树的特点性质:(节点为的度数为0 表示 n0,以此类推) ①哈夫曼树中只存在度为2和度为0的节点,及n1=0。 ②哈夫曼树中,度为0和度为2的节点关系:n2=n0-1 由以上两个性质,本题就很好解出答案: n0+n2=115 =&...
-
掌声:跨平台移动开发工具包,其中包括用于定义移动应用程序的DSL和用于为iOS,Android,Windows Phone 7和Google App Engine创建本机应用程序的代码生成器。 基于Eclipse和Xtext。 官方回购在掌声中-源码
-
精通编译Makefile,Nina, 从底层uboot到Android
-
cookie和session的区别及原理
-
access应用的3个开发实例
-
4.1 网络层提供的两种服务
-
织梦响应式新闻技术博客类织梦模板(自适应手机端)
-
ssm整合开发知识总结以及大概流程
-
2021-03-01
-
tangt-and-song-dynasties-SSM-master.zip
-
Java: @Inject注解
-
华为1+X认证——网络系统建设与运维(初级)
-
d3_js:d3.js-源码
-
【硬核】一线Python程序员实战经验分享(1)
-
SpringSecurity.rar
-
织梦响应式日化食品零食类网站织梦模板(自适应手机端)
-
MySQL NDB Cluster 负载均衡和高可用集群
-
PAT甲级题库考点
-
2021-03-01
-
关于异常后继续执行的笔记
-
FTP 文件传输服务