哈夫曼树与哈夫曼编码

利用哈夫曼编码进行通信可以大大提高信道的利用率,缩短信息传输的时间,降低传输成本。根据哈夫曼编码的原理,编写一个程序,在用户输入结点权值的基础上求哈夫曼编码。
设计要求:从键盘输入若干字符及每个字符出现的频率,将字符出现的频率作为结点的权值,建立哈夫曼树,然后对各个字符进行哈夫曼编码,最后打印输出字符及对应的哈夫曼编码。

2个回答

#include
#include
#include
#define N 80
typedef struct
{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树
typedef char * HuffmanCode;//动态分配数组存储赫夫曼编码表
void Select(HuffmanTree &HT,int &i,int &s1,int s2);
//从i个节点中选出parent为0且weight最小的两个结点,其序号分别为s1和s2
void reverse(char a[],int &b);//把字符串逆置
void Huffmancoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int &n)
//存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码 HC
{
int m,i;
if(n<=1)return;
m=2*n-1;//赫夫曼树的结点总数
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));// 0号单元未用
HuffmanTree p;
p=NULL;
for(p=HT+1,i=1;i<=n;++i,++p,++w)
//构造n颗只有根结点的树,因0号单元未用,因此p指向HT+1
{
p->weight=*w;p->parent=0;p->lchild=0;p->rchild=0;
}
for(i=n+1;i<=m;++i,++p)
//新生成的结点各值都赋值为0
{
p->weight=0;p->parent=0;p->lchild=0;p->rchild=0;
}
printf("初态:\n");
printf("node\tweight\tparent\tlchild\trchild\n"); p=HT+1;
for(i=1;i<=m;i++,++p)
{
printf("%d\t%d\t%d\t%d\t%d\n",i,p->weight,p->parent,p->lchild,p->rchild);
}
printf("\n");
int s1,s2,t;//s1,s2分别为最小和次小结点
for(i=n+1;i<=m;++i)
//建赫夫曼树
{
t=i-1;//便于实参传递,因此把i-1赋值给t
s1=s2=0;Select(HT,t,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;
}printf("终态:\n");
printf("node\tweight\tparent\tlchild\trchild\n");
p=HT+1;
for(i=1;i<=m;i++,++p)
{
printf("%d\t%d\t%d\t%d\t%d\n",i,p->weight,p->parent,p->lchild,p->rchild);
}printf("\n");//从叶子到根逆向求每个字符的赫夫曼编码
int start,k;
unsigned int c,f;
char *cd;cd=NULL;
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));//分配n个字符编码的头指针向量,0号单元未用
cd=(char *)malloc(n*sizeof(char));//分配求编码的临时工作空间
void reverse(char a[],int &b);//把字符串逆置
for(i=1;i<=n;++i)
//逐个字符求赫夫曼编码
{
start=0;//从各个叶子结点到根结点的逆序编码依次存入 cd,start为编码开始府
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[start]='\0';//编码结束符'\0'存入cd

k=strlen(cd);//k为存入cd的编码的长度
reserve(cd,k);//把逆序存入的编码再逆置,此时cd中存入的即为从根结点到叶子结点的正序编码
HC[i]=(char*)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间
strcpy(HC[i],cd);//从cd复制编码(串)到HC[i]
}
free(cd);//释放工作空间
}
void Select(HuffmanTree &HT,int &i,int &s1,int &s2)
{
unsigned int m1,m2;
int k;
m1=m2=32767;//*m1,m2为最小和次小结点权值
for(k=1;k<=i;k++)
{
if((HT[k].parent==0)&&(HT[k].weight<m1))
{
m2=m1;
s2=s1;
m1=HT[k].weight;
s1=k;
}
else if((HT[k].parent==0)&&(HT[k].weight<m2))
{
m2=HT[k].weight;s2=k;
}
}
}
void reserve(char a[],int &b)
{
char t,*p=a;
for(int i=0,j=b-1;i<b/2;i++,j--)
{
t=*(p+i);
(p+i)=(p+j);
*(p+j)=t;
}
}
int main()
{
char u[N],str[N];
int i,n,k,w[N];
HuffmanTree HT;
HuffmanCode HC;
printf("输入字符的个数:");
scanf("%d",&n);
printf("分别输入这%d个字符:\n",n);
for(i=0;i<n;i++)
{
scanf("%c",&u[i]);
getchar();
}
printf("存放上述所输入\“字符\”的哈夫曼树的数组HT的状态如下:\n");
Huffmancoding(HT,HC,w,n);
printf("以下是每个字符所对应的哈夫曼编码是:\n");
for (i=1; i<=n; ++i)
{
printf("第%d 个字符所对应的哈夫曼编码是:",i);
printf("%s\n",HC[i]);
}
printf("\n");
printf("(把上次输入的每个字符再依次输入,并存到 str 字符串中)\n");
printf("请输入:");
scanf("%s",str);
k=strlen(str);
printf("字符串%s 所对应的\"电文编码\"是:",str);
for (i=1; i<=n; ++i)
printf("%s",HC[i]);
printf("\n");
}

[Error] E:\zsyc\h1226.cpp:74: error: `reserve' was not declared in this scope
求大神多多指教,感激不尽!

qq_37172680
qq_37172680 谢谢
3 年多之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
哈夫曼树算法设计编码译码

求大神帮忙用C++语言写一个算法设计 1)从键盘上输入要进行哈夫曼编码的字符集和对应的权值。 2)构造哈夫曼树的算法 3)完成哈夫曼编码的算法 4)完成哈夫曼译码算法。 5)利用编译码算法,对给定的文本文件t1.txt的英语内容进行编码,保存到指定文件code1.txt中。然后再编写一个函数对code1.txt中的内容进行译码。 要求输入哈夫曼编码时,能输出对应的字符。跪求了 真的没法写啊 想不到思路发到我哦空间或者是1511437725@qq.com都行啊

C++哈夫曼编码译码器设计与实现并对哈夫曼树进行先序遍历。

现在就是差一个先序遍历的要求没有做到 ``` #include<stdio.h> #include<string.h> #include<stdlib.h> //树结点定义 typedef struct { int weight; int parent; int lchild; int rchild; }HTNode,*HuffmanTree; static char N[100];//用于保存正文 //哈弗曼编码,char型二级指针 typedef char **HuffmanCode; //封装最小权结点和次小权结点 typedef struct { int s1; int s2; }MinCode; //函数声明 void Error(char *message); HuffmanCode HuffmanCoding(HuffmanTree &HT,HuffmanCode HC,int *w,int n); MinCode Select(HuffmanTree HT,int n); //当输入1个结点时的错误提示 void Error(char *message) { fprintf(stderr,"Error:%s\n",message); //根据指定的格式,向输出流写入数据 exit(1); } //构造哈夫曼树HT,编码存放在HC中,w为权值,n为结点个数 HuffmanCode HuffmanCoding(HuffmanTree &HT,HuffmanCode HC,int *w,int n) { int i,s1=0,s2=0; HuffmanTree p; char *cd; int f,c,start,m; MinCode min; if(n<=1) { Error("Code too small!");//只有一个结点不进行编码,直接exit(1)退出。 } m=2*n-1;//哈弗曼编码需要开辟的结点大小为2n-1 HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//开辟哈夫曼树结点空间 m+1 ,动态内存分配。 //初始化n个叶子结点,w[0] = 0,main函数已赋值 for(p=HT,i=0;i<=n;i++,p++,w++) { p->weight=*w; p->parent=0; p->lchild=0; p->rchild=0; } //将n-1个非叶子结点的初始化 for(;i<=m;i++,p++) { p->weight=0; p->parent=0; p->lchild=0; p->rchild=0; } //构造哈夫曼树 for(i=n+1;i<=m;i++) { min=Select(HT,i-1);//找出最小和次小的两个结点 s1=min.s1 ; //最小结点下标 s2=min.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; } //打印哈弗曼树 printf("HT List:\n"); printf("Number\t\tweight\t\tparent\t\tlchild\t\trchild\n"); for(i=1;i<=m;i++) { printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\t\n",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild); } //从叶子结点到根节点求每个字符的哈弗曼编码 HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); cd=(char *)malloc(n*sizeof(char *));//为哈弗曼编码动态分配空间 cd[n-1]='\0';//如:3个结点编码最长为2。cd[3-1] = '\0'; //求叶子结点的哈弗曼编码 for(i=1;i<=n;i++) { start=n-1; //定义左子树为0,右子树为1 /* 从最下面的1号节点开始往顶部编码(逆序存放),然后编码2号节点,3号...... */ 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'; } //为第i个字符分配编码空间 HC[i]=(char *)malloc((n-start)*sizeof(char *)); //将当前求出结点的哈弗曼编码复制到HC strcpy(HC[i],&cd[start]); } free(cd); return HC; } MinCode Select(HuffmanTree HT,int n) { int min,secmin; int temp = 0; int i,s1,s2,tempi = 0; MinCode code ; s1=1; s2=1; min = 9999; //找出权值最小的结点,下标保存在s1中 for(i=1;i<=n;i++) { if(HT[i].weight<min && HT[i].parent==0) { min=HT[i].weight; s1=i; } } secmin = 9999; //找出权值次小的结点,下标保存在s2中 for(i=1;i<=n;i++) { if((HT[i].weight<secmin) && (i!=s1) && HT[i].parent==0) { secmin=HT[i].weight; s2=i; } } //放进封装中 code.s1=s1; code.s2=s2; return code; } void HuffmanTranslateCoding(HuffmanTree HT, int n,char* ch) {//译码过程 int m=2*n-1; int i,j=0; printf("After Translation:"); while(ch[j]!='\0')//ch[]:你输入的要译码的0101010串 { i=m; while(0 != HT[i].lchild && 0 != HT[i].rchild)//从顶部找到最下面 { if('0' == ch[j])//0 往左子树走 { i=HT[i].lchild; } else//1 往右子树走 { i=HT[i].rchild; } ++j;//下一个路径 } printf("%c",N[i-1]);//打印出来 } printf("\n"); } void main() { HuffmanTree HT=NULL; HuffmanCode HC=NULL; int *w=NULL; int i,n; char tran[100]; printf("Input N(char):"); gets(N); fflush(stdin); n = strlen(N); w=(int *)malloc((n+1)*sizeof(int *));//开辟n+1个长度的int指针空间 w[0]=0; printf("Enter weight:\n"); //输入结点权值 for(i=1;i<=n;i++) { printf("w[%d]=",i); scanf("%d",&w[i]); } fflush(stdin); //清空输入缓冲区 //构造哈夫曼树HT,编码存放在HC中,w为权值,n为结点个数 HC=HuffmanCoding(HT,HC,w,n); //输出哈弗曼编码 printf("HuffmanCode:\n"); printf("Number\t\tWeight\t\tCode\n"); for(i=1;i<=n;i++) { printf("%c\t\t%d\t\t%s\n",N[i-1],w[i],HC[i]); } fflush(stdin); //译码过程 printf("Input HuffmanTranslateCoding:"); gets(tran); HuffmanTranslateCoding(HT, n, tran); return; } ```题目要求:九、哈夫曼编码译码器设计与实现 编写程序设计哈夫曼编码译码器。 (1)根据输入的权值建立哈夫曼树。 (2)对建立好的哈夫曼树进行先序遍历。 (3)利用建好的哈夫曼树生成哈夫曼编码,并显示生成的各字符的哈夫曼编码。 (4)根据输入的字符进行译码。 (5)显示功能:以先序遍历的顺序显示建立好的哈夫曼树。显示哈夫曼编码和译码的结果。

项目开发中哈夫曼树应用

在项目开发过程中碰到一个难点,请教各位高手指点: **应用场景** 由于项目需求,需要设计一个条形码(纯数字字符串),条形码长度小于30Byte. 条形码输入后程序需要解码识别. 个人思路: 1.将相关信息进行哈夫曼树编码,输入条形码数字后进行哈夫曼树解码; 难点: 1.条形码如何携带哈夫曼树动态树信息;

哈夫曼编码 程序设计报告

这个报告该怎么写? 哈夫曼编码/译码器 问题描述: 给定的一组电文,设计该电文的哈夫曼编码。 基本要求: (1)从终端读入字符集大小 n,及 n 个字符和 m 个权值,建立哈夫曼树, 并将它存于文件 hfmtree。 (2)利用已建好的哈夫曼树对文件中的正文进行编码,然后将结果存入文 件 codefile。 (3)利用已建好的哈夫曼树将文件中的代码进行译码,结果存入文件 textfile。 (4)输入表示权值的整数,且整数之和不超过 100。

数据结构作业,三叉哈夫曼树的实现

这是我用二叉哈夫曼树代码改的,但是无法实现,首先是叶子节点和节点数没法表示,然后就算自己输入固定节点也无法正确实现,请问怎么实现三叉哈夫曼树呢 #include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> 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序列标在哪里

基于哈夫曼树的数据压缩算法

A 基于哈夫曼树的数据压缩算法 时间限制(C/C++):1000MS/3000MS 运行内存限制:65536KByte 总提交:445 测试通过:131 描述 输入一串字符串,根据给定的字符串中字符出现的频率建立相应哈夫曼树,构造哈夫曼编码表,在此基础上可以对待压缩文件进行压缩(即编码),同时可以对压缩后的二进制编码文件进行解压(即译码)。 输入 多组数据,每组数据一行,为一个字符串(只考虑26个小写字母即可)。当输入字符串为“0”时,输入结束。 输出 每组数据输出2n+4行(n为输入串中字符类别的个数)。第一行为统计出来的字符出现频率(只输出存在的字符,格式为:字符:频度),每两组字符之间用一个空格分隔,字符按照ASCII码从小到大的顺序排列。第二行至第2n行为哈夫曼树的存储结构的终态(形如教材139页表5.2(b),一行当中的数据用空格分隔)。第2n+2行为每个字符的哈夫曼编码(只输出存在的字符,格式为:字符:编码),每两组字符之间用一个空格分隔,字符按照ASCII码从小到大的顺序排列。第2n+3行为编码后的字符串,第2n+4行为解码后的字符串(与输入的字符串相同)。 样例输入 aaaaaaabbbbbccdddd aabccc 0 样例输出 a:7 b:5 c:2 d:4 1 7 7 0 0 2 5 6 0 0 3 2 5 0 0 4 4 5 0 0 5 6 6 3 4 6 11 7 2 5 7 18 0 1 6 a:0 b:10 c:110 d:111 00000001010101010110110111111111111 aaaaaaabbbbbccdddd a:2 b:1 c:3 1 2 4 0 0 2 1 4 0 0 3 3 5 0 0 4 3 5 2 1 5 6 0 3 4 a:11 b:10 c:0 111110000 aabccc

C++版数据结构哈夫曼树程序设计:实现对26个英文字母的编码和译码

C++版数据结构哈夫曼树程序设计 项目一:实现对26个英文字母的编码和译码,设计完成以下功能: 1.能够对27个字符进行编码、并存储。 2.利用编码能够实现任意英文句子的编码操作,并存储编码。 3.能够将二进制的密码翻译成句子,并将译文存储。 4.能随时查看字母的编码。 5.使用文件去存储相关内容。

哈夫曼编码和译码,把相应的数据存入文件中

手动输入权值并进行哈夫曼编码和译码,将这些数据写入文件中,并以直观的方式输出哈夫曼树用C语言实现

数据结构哈夫曼树代码怎么写

哈夫曼树:输入一串只包含abcdefg8种字符的字符串,统计每种字符出现的次数,并据此创建相应的哈夫曼树。 这怎么写

哈夫曼树的构造技巧以及权值问题

数据结构中树的权值最优问题,还有怎样构造哈夫曼树,求详细的解答,谢谢啦!

哈夫曼树最基础的题,画出哈夫曼树,求出每个字符的编码

希望大神帮忙讲解一下,我是一枚小菜鸟![图片](https://img-ask.csdn.net/upload/201704/29/1493457350_342736.jpg)

C++哈夫曼树压缩的问题

在利用哈夫曼树进行压缩时,建立好哈夫曼树,得到得到每个叶子节点中的字符编码之后,如何使用位运算将编码中的每个位(BIT)设置到一个char类型的位缓冲中,可能多个编码才能填满一个位缓冲,每填满一次,将位缓冲区以单个字节的形式写入文件。这涉及到哪方面的知识,谢谢

求一段可以打印哈夫曼树的代码,能够在执行时看到的,谢谢!!

求一段可以将我写的哈夫曼树打印出来的代码,谢谢!!我正在写一个huffman的编码和译码的程序可是不会写打印的,请大家帮忙

用c++构建一个哈夫曼树

输入字符个数,权值,打印哈夫曼树,编码和译码,源代码,可以用c-free运行的那种,求各位大神帮忙解答,要完整的代码拜托了

求教,哈夫曼树问题,感觉好难

大佬们,哈夫曼编码的问题,编码完毕后,下次不初始化,怎么从文件中读出哈夫曼树?怎么打印哈夫曼树?

哈夫曼树构造过程中出现乱码?

程序是根据用户输入的一些列字符及其对应的权值,生成哈夫曼树,再根据生成的哈夫曼树进行编码,在测试时,发现输出每个元素对应的哈夫曼编码时,总会出现一些乱码的文字,知道原因的网友点拨一些,谢谢。程序如下: ``` #include <iostream> #include<string> using namespace std; class HuffNode { public: char c; // 结点的字符 int weight; // 权值 int parent, lChild, rChild; // 左右孩子指针 }; class HuffTree { private: int Node_cnt=0; HuffNode* huff=NULL; string* HuffCode = NULL; public: HuffTree(int n, char* c, int* weights); // 创建Huffman树 ~HuffTree(); // 析构函数 void setNode_cnt(int cnt){ Node_cnt = cnt; } void select(int end, int& index1, int& index2); // 选出最小和次小叶子结点 void printHuffTree(); void setHuffCode(); void printHuffCode(); }; HuffTree::~HuffTree() { delete[] huff; delete[] HuffCode; } void HuffTree::printHuffCode() { for (int i = 0; i < Node_cnt; i++) { cout << huff[i].c << "的哈夫曼编码为:" << HuffCode[i] << endl; } } void HuffTree::setHuffCode() // 左孩子为0,右孩子为1 { HuffCode = new string[Node_cnt]; for (int i = 0; i < Node_cnt; i++) { int son, father; // 孩子指针和双亲指针 int cnt = 0; string str; son = i; father = huff[son].parent; while (father != -1) { if (huff[father].lChild == son) { str.append("0"); } else { str.append("1"); } son = father; // 孩子指针为当前双亲指针 father = huff[father].parent; // 双亲指针为当前双亲指针的双亲 } HuffCode[i] = new char[str.size()]; for (unsigned int j = 0; j < str.size(); j++) // 由于求哈夫曼编码时是从叶子结点一直找到树根,故编码为之前的逆序 { HuffCode[i][j] = str[str.size() - 1-j];// 逆序 } } } HuffTree::HuffTree(int n,char* ch,int* weights){ Node_cnt = n; huff = new HuffNode[2 * Node_cnt - 1]; for (int i = 0; i < Node_cnt; i++) // 初始化 { huff[i].c = ch[i]; huff[i].weight = weights[i]; huff[i].lChild = -1; huff[i].rChild = -1; huff[i].parent = -1; } for (int i = Node_cnt; i < Node_cnt * 2 - 1; i++) { int index1 = -1, index2 = -1; select(i - 1, index1, index2);// 选出最小和次小中间树结点索引 huff[index1].parent = i; huff[index2].parent = i; huff[i].weight = huff[index1].weight + huff[index2].weight; huff[i].lChild = index1; huff[i].rChild = index2; huff[i].parent = -1; } } void HuffTree::printHuffTree() { cout << "所建哈夫曼静态链表示如下:" << endl; cout << "位置\t" << "字符\t" << "权值\t" << "双亲\t" << "左孩子\t" << "右孩子\t" << endl; for (int i = 0; i < Node_cnt*2-1; i++) { cout << i << "\t" << huff[i].c << "\t" << huff[i].weight << "\t" << huff[i].parent << "\t" << huff[i].lChild << "\t" << huff[i].rChild << endl; } } void HuffTree::select(int end, int& index1, int& index2) { int min1=100000,min2 = 100000; // 设m1为最小值,m2为次小值 for (int j = 0; j <=end; j++) { if (huff[j].parent == -1) { if (huff[j].weight < min1) // 如果当前权值比最小值小 { index2 = index1; index1 = j; min2 = min1; min1 = huff[j].weight; } else if (huff[j].weight < min2) // 如果当前权值比次小值小 { min2 = huff[j].weight; index2 = j; } } } } int main() { int n; cout << "请输入树叶结点的个数(小于等于1结束):" << endl; cin >> n; if (n < 1) return 0; char chs[256]; int weights[256]; for (int i = 0; i < n; i++){ cout << "请输入第" << i+1 << "个字符及权值" << endl; cin >> chs[i] >> weights[i]; } HuffTree tree(n,chs,weights); tree.printHuffTree(); tree.setHuffCode(); tree.printHuffCode(); return 0; } ```

如何用C++实现哈夫曼编码和译码

设计一个哈夫曼编码、译码系统。对一个 ASCII 编码的文本文件中的字符进行哈夫曼编码,生成编码 文件;反过来,可将编码文件译码还原为一个文本文件。 (1) 从文件中读入任意一篇英文短文(文件为 ASCII 编码扩展名为 txt); (2) 统计并输出不同字符在文章中出现的频率(空格、换行、标点等也按字符处理); (3) 根据字符频率构造哈夫曼树,并给出每个字符的哈夫曼编码;

哈夫曼编码长度问题,证明题

已知字符串中某一字符出现的频率大于0.4,证明该字符串中存在某一字符的哈夫曼编码长度为1;如果字符串中所有字符出现的频率都小于三分之一,证明字符串中不存在哈夫曼编码长度为1的字符

在中国程序员是青春饭吗?

今年,我也32了 ,为了不给大家误导,咨询了猎头、圈内好友,以及年过35岁的几位老程序员……舍了老脸去揭人家伤疤……希望能给大家以帮助,记得帮我点赞哦。 目录: 你以为的人生 一次又一次的伤害 猎头界的真相 如何应对互联网行业的「中年危机」 一、你以为的人生 刚入行时,拿着傲人的工资,想着好好干,以为我们的人生是这样的: 等真到了那一天,你会发现,你的人生很可能是这样的: ...

程序员请照顾好自己,周末病魔差点一套带走我。

程序员在一个周末的时间,得了重病,差点当场去世,还好及时挽救回来了。

技术大佬:我去,你写的 switch 语句也太老土了吧

昨天早上通过远程的方式 review 了两名新来同事的代码,大部分代码都写得很漂亮,严谨的同时注释也很到位,这令我非常满意。但当我看到他们当中有一个人写的 switch 语句时,还是忍不住破口大骂:“我擦,小王,你丫写的 switch 语句也太老土了吧!” 来看看小王写的代码吧,看完不要骂我装逼啊。 private static String createPlayer(PlayerTypes p...

和黑客斗争的 6 天!

互联网公司工作,很难避免不和黑客们打交道,我呆过的两家互联网公司,几乎每月每天每分钟都有黑客在公司网站上扫描。有的是寻找 Sql 注入的缺口,有的是寻找线上服务器可能存在的漏洞,大部分都...

上班一个月,后悔当初着急入职的选择了

最近有个老铁,告诉我说,上班一个月,后悔当初着急入职现在公司了。他之前在美图做手机研发,今年美图那边今年也有一波组织优化调整,他是其中一个,在协商离职后,当时捉急找工作上班,因为有房贷供着,不能没有收入来源。所以匆忙选了一家公司,实际上是一个大型外包公司,主要派遣给其他手机厂商做外包项目。**当时承诺待遇还不错,所以就立马入职去上班了。但是后面入职后,发现薪酬待遇这块并不是HR所说那样,那个HR自...

女程序员,为什么比男程序员少???

昨天看到一档综艺节目,讨论了两个话题:(1)中国学生的数学成绩,平均下来看,会比国外好?为什么?(2)男生的数学成绩,平均下来看,会比女生好?为什么?同时,我又联想到了一个技术圈经常讨...

总结了 150 余个神奇网站,你不来瞅瞅吗?

原博客再更新,可能就没了,之后将持续更新本篇博客。

副业收入是我做程序媛的3倍,工作外的B面人生是怎样的?

提到“程序员”,多数人脑海里首先想到的大约是:为人木讷、薪水超高、工作枯燥…… 然而,当离开工作岗位,撕去层层标签,脱下“程序员”这身外套,有的人生动又有趣,马上展现出了完全不同的A/B面人生! 不论是简单的爱好,还是正经的副业,他们都干得同样出色。偶尔,还能和程序员的特质结合,产生奇妙的“化学反应”。 @Charlotte:平日素颜示人,周末美妆博主 大家都以为程序媛也个个不修边幅,但我们也许...

如果你是老板,你会不会踢了这样的员工?

有个好朋友ZS,是技术总监,昨天问我:“有一个老下属,跟了我很多年,做事勤勤恳恳,主动性也很好。但随着公司的发展,他的进步速度,跟不上团队的步伐了,有点...

我入职阿里后,才知道原来简历这么写

私下里,有不少读者问我:“二哥,如何才能写出一份专业的技术简历呢?我总感觉自己写的简历太烂了,所以投了无数份,都石沉大海了。”说实话,我自己好多年没有写过简历了,但我认识的一个同行,他在阿里,给我说了一些他当年写简历的方法论,我感觉太牛逼了,实在是忍不住,就分享了出来,希望能够帮助到你。 01、简历的本质 作为简历的撰写者,你必须要搞清楚一点,简历的本质是什么,它就是为了来销售你的价值主张的。往深...

外包程序员的幸福生活

今天给你们讲述一个外包程序员的幸福生活。男主是Z哥,不是在外包公司上班的那种,是一名自由职业者,接外包项目自己干。接下来讲的都是真人真事。 先给大家介绍一下男主,Z哥,老程序员,是我十多年前的老同事,技术大牛,当过CTO,也创过业。因为我俩都爱好喝酒、踢球,再加上住的距离不算远,所以一直也断断续续的联系着,我对Z哥的状况也有大概了解。 Z哥几年前创业失败,后来他开始干起了外包,利用自己的技术能...

优雅的替换if-else语句

场景 日常开发,if-else语句写的不少吧??当逻辑分支非常多的时候,if-else套了一层又一层,虽然业务功能倒是实现了,但是看起来是真的很不优雅,尤其是对于我这种有强迫症的程序"猿",看到这么多if-else,脑袋瓜子就嗡嗡的,总想着解锁新姿势:干掉过多的if-else!!!本文将介绍三板斧手段: 优先判断条件,条件不满足的,逻辑及时中断返回; 采用策略模式+工厂模式; 结合注解,锦...

深入剖析Springboot启动原理的底层源码,再也不怕面试官问了!

大家现在应该都对Springboot很熟悉,但是你对他的启动原理了解吗?

离职半年了,老东家又发 offer,回不回?

有小伙伴问松哥这个问题,他在上海某公司,在离职了几个月后,前公司的领导联系到他,希望他能够返聘回去,他很纠结要不要回去? 俗话说好马不吃回头草,但是这个小伙伴既然感到纠结了,我觉得至少说明了两个问题:1.曾经的公司还不错;2.现在的日子也不是很如意。否则应该就不会纠结了。 老实说,松哥之前也有过类似的经历,今天就来和小伙伴们聊聊回头草到底吃不吃。 首先一个基本观点,就是离职了也没必要和老东家弄的苦...

2020阿里全球数学大赛:3万名高手、4道题、2天2夜未交卷

阿里巴巴全球数学竞赛( Alibaba Global Mathematics Competition)由马云发起,由中国科学技术协会、阿里巴巴基金会、阿里巴巴达摩院共同举办。大赛不设报名门槛,全世界爱好数学的人都可参与,不论是否出身数学专业、是否投身数学研究。 2020年阿里巴巴达摩院邀请北京大学、剑桥大学、浙江大学等高校的顶尖数学教师组建了出题组。中科院院士、美国艺术与科学院院士、北京国际数学...

男生更看重女生的身材脸蛋,还是思想?

往往,我们看不进去大段大段的逻辑。深刻的哲理,往往短而精悍,一阵见血。问:产品经理挺漂亮的,有点心动,但不知道合不合得来。男生更看重女生的身材脸蛋,还是...

为什么程序员做外包会被瞧不起?

二哥,有个事想询问下您的意见,您觉得应届生值得去外包吗?公司虽然挺大的,中xx,但待遇感觉挺低,马上要报到,挺纠结的。

当HR压你价,说你只值7K,你该怎么回答?

当HR压你价,说你只值7K时,你可以流畅地回答,记住,是流畅,不能犹豫。 礼貌地说:“7K是吗?了解了。嗯~其实我对贵司的面试官印象很好。只不过,现在我的手头上已经有一份11K的offer。来面试,主要也是自己对贵司挺有兴趣的,所以过来看看……”(未完) 这段话主要是陪HR互诈的同时,从公司兴趣,公司职员印象上,都给予对方正面的肯定,既能提升HR的好感度,又能让谈判气氛融洽,为后面的发挥留足空间。...

面试:第十六章:Java中级开发(16k)

HashMap底层实现原理,红黑树,B+树,B树的结构原理 Spring的AOP和IOC是什么?它们常见的使用场景有哪些?Spring事务,事务的属性,传播行为,数据库隔离级别 Spring和SpringMVC,MyBatis以及SpringBoot的注解分别有哪些?SpringMVC的工作原理,SpringBoot框架的优点,MyBatis框架的优点 SpringCould组件有哪些,他们...

面试阿里p7,被按在地上摩擦,鬼知道我经历了什么?

面试阿里p7被问到的问题(当时我只知道第一个):@Conditional是做什么的?@Conditional多个条件是什么逻辑关系?条件判断在什么时候执...

你期望月薪4万,出门右拐,不送,这几个点,你也就是个初级的水平

先来看几个问题通过注解的方式注入依赖对象,介绍一下你知道的几种方式@Autowired和@Resource有何区别说一下@Autowired查找候选者的...

面试了一个 31 岁程序员,让我有所触动,30岁以上的程序员该何去何从?

最近面试了一个31岁8年经验的程序猿,让我有点感慨,大龄程序猿该何去何从。

大三实习生,字节跳动面经分享,已拿Offer

说实话,自己的算法,我一个不会,太难了吧

程序员垃圾简历长什么样?

已经连续五年参加大厂校招、社招的技术面试工作,简历看的不下于万份 这篇文章会用实例告诉你,什么是差的程序员简历! 疫情快要结束了,各个公司也都开始春招了,作为即将红遍大江南北的新晋UP主,那当然要为小伙伴们做点事(手动狗头)。 就在公众号里公开征简历,义务帮大家看,并一一点评。《启舰:春招在即,义务帮大家看看简历吧》 一石激起千层浪,三天收到两百多封简历。 花光了两个星期的所有空闲时...

《Oracle Java SE编程自学与面试指南》最佳学习路线图2020年最新版(进大厂必备)

正确选择比瞎努力更重要!

《Oracle Java SE编程自学与面试指南》最佳学习路线图(2020最新版)

正确选择比瞎努力更重要!

字节跳动面试官竟然问了我JDBC?

轻松等回家通知

面试官:你连SSO都不懂,就别来面试了

大厂竟然要考我SSO,卧槽。

终于,月薪过5万了!

来看几个问题想不想月薪超过5万?想不想进入公司架构组?想不想成为项目组的负责人?想不想成为spring的高手,超越99%的对手?那么本文内容是你必须要掌握的。本文主要详解bean的生命...

自从喜欢上了B站这12个UP主,我越来越觉得自己是个废柴了!

不怕告诉你,我自从喜欢上了这12个UP主,哔哩哔哩成为了我手机上最耗电的软件,几乎每天都会看,可是吧,看的越多,我就越觉得自己是个废柴,唉,老天不公啊,不信你看看…… 间接性踌躇满志,持续性混吃等死,都是因为你们……但是,自己的学习力在慢慢变强,这是不容忽视的,推荐给你们! 都说B站是个宝,可是有人不会挖啊,没事,今天咱挖好的送你一箩筐,首先啊,我在B站上最喜欢看这个家伙的视频了,为啥 ,咱撇...

立即提问
相关内容推荐