`````` #include "stdio.h"
#include "stdlib.h"
#include "string.h"
char alphabet[]={'A','B','C','D'};
typedef struct
{
int weight;     //权值
int parent;     //父节点序号
int left ;
int right;
}HuffmanTree;

typedef char *HuffmanCode;  //Huffman编码指针
void SelectNode (HuffmanTree *ht,int n,int *bt1,int *bt2)
//从n个节点中选择parent节点为0，权重最小的两个节点
{
int i;
HuffmanTree *ht1,*ht2,*t;
ht1=ht2=NULL;
for(i=1;i<=n;i++)
{
if(!ht[i].parent)               //父节点为空
{
if(ht1==NULL)
{
ht1=ht+i;               //
continue;
}
if(ht2==NULL)
{
ht2=ht+i;
if(ht1->weight>ht2->weight)
{
t=ht2;
ht2=ht1;
ht1=t;          //让ht1指向最小节点 ht2指向第二小
}
continue;
}
if(ht1 &&ht2)
{
if(ht[i].weight<=ht1->weight)
{
ht2=ht1;                    //如果还有比ht1更小的则把ht1赋给ht2 ，ht1继续等于最小
ht1=ht+i;
}
else if(ht[i].weight<ht2->weight){
ht2=ht+i;                       //没有比ht1更小的 但有比ht2小的
}
}
}
}
if(ht1>ht2){                    //按数组最初的位置排序
*bt2=ht1-ht;
*bt1=ht2-ht;
}
else
{
*bt1=ht1-ht;
*bt2=ht2-ht;
}
}
void CreateTree(HuffmanTree *ht,int n,int *w)
{
int i,m=2*n-1;    //总节点数
int bt1,bt2;
if(n<=1)
return ;
for(i=1;i<=n;++i)
{
ht[i].weight=w[i-1];
ht[i].parent=0;
ht[i].left=0;
ht[i].right=0;
}
for(;i<=m;++i)
{
ht[i].weight=0;
ht[i].parent=0;
ht[i].left=0;
ht[i].right=0;
}
for(i=n+1;i<=m;++i)
{
SelectNode(ht,i-1,&bt1,&bt2);
ht[bt1].parent=i;
ht[bt2].parent=i;
ht[i].left=bt1;
ht[i].right=bt2;
ht[i].weight=ht[bt1].weight+ht[bt2].weight;
}
}

void HuffmanCoding(HuffmanTree *ht,int n,HuffmanCode *hc)
{
char *cd;
int start,i;
int current,parent;
cd=(char*)malloc(sizeof(char)*n);
cd[n-1]='\0';
for(i=1;i<=n;i++)
{
start=n-1;
current=i;                          //获得当前节点序号
parent=ht[current].parent;          //获得当前节点父亲的序号
while(parent)           //当父节点不为空
{
if(current==ht[parent].left)    //若当前节点是父亲的左节点
cd[--start]='0';            //字符最后编码为0 注意这个编码是逆序的 最后其实根节点
else
cd[--start]='1';
current=parent;                 //从当前节点向根节点寻找
parent=ht[parent].parent;
}
hc[i-1]=(char*)malloc(sizeof(char*)*(n-start)); //分配保存编码的内存
strcpy(hc[i-1],&cd[start]);                     //复制生成的编码
}
free(cd);
}

void Encode(HuffmanCode *hc,char *alphabet,char *str,char *code)
{
int len=0,i=0,j;
code[0]='\0';
while(str[i])
{
j=0;
while(alphabet[j]!=str[i])   //搜索字母在编码表的位置
j++;
strcpy(code+len,hc[j]);     //字母在叶节点的编号到根节点的编号全部复制给code
len=len+strlen(hc[j]);      // 扩大len的长度（也就是节点深度）
i++;
}
code[len]='\0';
}

void Decode(HuffmanTree *ht,int m,char *code,char *alphabet,char *decode)//解码
{
int position=0,i,j=0;
m=2*m-1;
while(code[position])
{
for(i=m;ht[i].left &&ht[i].right;position++ )
{
if(code[position]=='0')
i=ht[i].left;
else
i=ht[i].right;
}
decode[j]=alphabet[i-1];
j++;
}
decode[j]='\0';
}
int main()
{
int i,n=4,m;
char code[100],code1[100];

int w[]={5,7,2,13};
HuffmanTree *ht;
HuffmanCode *hc;
m=2*n-1;
ht=(HuffmanTree *)malloc((m+1)*sizeof(HuffmanTree));
if(!ht)
{
printf("分配内存失败\n");
exit(0);
}
CreateTree(ht,n,w);
HuffmanCoding(ht,n,hc);
for(i=1;i<=n;i++)
printf("字母:%c，权重:%d，编码:%s\n",alphabet[i-1],ht[i].weight,hc[i-1]);
Encode(hc,alphabet,test,code);
printf("\n字符串：\n%s\n转换后：\n%s\n",test,code);
Decode(ht,n,code,alphabet,code1);
printf("\n编码：\n%s\n转换后：\n%s\n",code,code1);

return 0;
}
``````

3个回答

``````#include "stdio.h"
#include "stdlib.h"
#include "string.h"
char alphabet[]={'A','B','C','D'};
typedef struct
{
int weight;     //权值
int parent;     //父节点序号
int left ;
int right;
}HuffmanTree;

typedef char *HuffmanCode;  //Huffman编码指针
void SelectNode (HuffmanTree *ht,int n,int *bt1,int *bt2)
//从n个节点中选择parent节点为0，权重最小的两个节点
{
int i;
HuffmanTree *ht1,*ht2,*t;
ht1=ht2=NULL;
for(i=1;i<=n;i++)
{
if(!ht[i].parent)               //父节点为空
{
if(ht1==NULL)
{
ht1=ht+i;               //
continue;
}
if(ht2==NULL)
{
ht2=ht+i;
if(ht1->weight>ht2->weight)
{
t=ht2;
ht2=ht1;
ht1=t;          //让ht1指向最小节点 ht2指向第二小
}
continue;
}
if(ht1 &&ht2)
{
if(ht[i].weight<=ht1->weight)
{
ht2=ht1;                    //如果还有比ht1更小的则把ht1赋给ht2 ，ht1继续等于最小
ht1=ht+i;
}
else if(ht[i].weight<ht2->weight){
ht2=ht+i;                       //没有比ht1更小的 但有比ht2小的
}
}
}
}
if(ht1>ht2){                    //按数组最初的位置排序
*bt2=ht1-ht;
*bt1=ht2-ht;
}
else
{
*bt1=ht1-ht;
*bt2=ht2-ht;
}
}
void CreateTree(HuffmanTree *ht,int n,int *w)
{
int i,m=2*n-1;    //总节点数
int bt1,bt2;
if(n<=1)
return ;
for(i=1;i<=n;++i)
{
ht[i].weight=w[i-1];
ht[i].parent=0;
ht[i].left=0;
ht[i].right=0;
}
for(;i<=m;++i)
{
ht[i].weight=0;
ht[i].parent=0;
ht[i].left=0;
ht[i].right=0;
}
for(i=n+1;i<=m;++i)
{
SelectNode(ht,i-1,&bt1,&bt2);
ht[bt1].parent=i;
ht[bt2].parent=i;
ht[i].left=bt1;
ht[i].right=bt2;
ht[i].weight=ht[bt1].weight+ht[bt2].weight;
}
}

void HuffmanCoding(HuffmanTree *ht,int n,HuffmanCode *hc)
{
char *cd;
int start,i;
int current,parent;
cd=(char*)malloc(sizeof(char)*n);
cd[n-1]='\0';
for(i=1;i<=n;i++)
{
start=n-1;
current=i;                          //获得当前节点序号
parent=ht[current].parent;          //获得当前节点父亲的序号
while(parent)           //当父节点不为空
{
if(current==ht[parent].left)    //若当前节点是父亲的左节点
cd[--start]='0';            //字符最后编码为0 注意这个编码是逆序的 最后其实根节点
else
cd[--start]='1';
current=parent;                 //从当前节点向根节点寻找
parent=ht[parent].parent;
}

hc[i-1]=(char*)malloc(sizeof(char)*(n-start)); //分配保存编码的内存
strcpy(hc[i-1],&cd[start]);                     //复制生成的编码
}
free(cd);
}

void Encode(HuffmanCode *hc,char *alphabet,char *str,char *code)
{
int len=0,i=0,j;
code[0]='\0';
while(str[i])
{
j=0;
while(alphabet[j]!=str[i])   //搜索字母在编码表的位置
j++;
strcpy(code+len,hc[j]);     //字母在叶节点的编号到根节点的编号全部复制给code
len=len+strlen(hc[j]);      // 扩大len的长度（也就是节点深度）
i++;
}
code[len]='\0';
}

void Decode(HuffmanTree *ht,int m,char *code,char *alphabet,char *decode)//解码
{
int position=0,i,j=0;
m=2*m-1;
while(code[position])
{
for(i=m;ht[i].left &&ht[i].right;position++ )
{
if(code[position]=='0')
i=ht[i].left;
else
i=ht[i].right;
}
decode[j]=alphabet[i-1];
j++;
}
decode[j]='\0';
}
int main()
{
int i,n=4,m;
char code[100],code1[100];

int w[]={5,7,2,13};
HuffmanTree *ht;
HuffmanCode *hc;
m=2*n-1;
ht=(HuffmanTree *)malloc((m+1)*sizeof(HuffmanTree));
hc=(HuffmanCode *)malloc((n+1)*sizeof(HuffmanCode));
if(!ht)
{
printf("分配内存失败\n");
exit(0);
}
CreateTree(ht,n,w);
HuffmanCoding(ht,n,hc);
for(i=1;i<=n;i++)
printf("字母:%c，权重:%d，编码:%s\n",alphabet[i-1],ht[i].weight,hc[i-1]);
Encode(hc,alphabet,test,code);
printf("\n字符串：\n%s\n转换后：\n%s\n",test,code);
Decode(ht,n,code,alphabet,code1);
printf("\n编码：\n%s\n转换后：\n%s\n",code,code1);
free(hc);
hc = NULL;
free(ht);
ht = NULL;
return 0;
}
``````
foreach_break 回复bill1829: 请查看http://blog.csdn.net/gsky1986/article/details/45388915

foreach_break 请采纳！随后给你详解。

bill1829 就改了最后吗？ 为什么要这样？

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

*![图片说明](https://img-ask.csdn.net/upload/201606/14/1465887225_826935.png) ``` #include <iostream> #include <stdlib.h> #include <cstdio> #include <string.h> #define MAX 1000000 using namespace::std; struct huffnode{ int weight;//权值 int lchild,rchild,parent; }typedef huffnode; void select(int len,int weight[],int &s1,int &s2,huffnode* &hufftree){ int min1=MAX; int min2=MAX; s1=-1; s2=-1; for(int i=0;i<len;i++){ if(hufftree[i].parent==-1){//没有父结点 if(hufftree[i].weight<min1){ s2=s1; min2=min1; s1=i; min1=hufftree[i].weight; } else if(hufftree[i].weight<min2){ s2=i; min2=hufftree[i].weight; } } } } void HuffCode(int weight[],int n,huffnode* &hufftree,char** &code){ int m=2*n-1;//霍夫曼树结点总数 int s1,s2;//最小值、此小值 //初始化霍夫曼树 hufftree=(huffnode*)malloc(m*sizeof(huffnode)); for(int i=0;i<n;i++){ hufftree[i].lchild=-1; hufftree[i].rchild=-1; hufftree[i].parent=-1; hufftree[i].weight=weight[i]; } for(int i=n;i<m;i++){ hufftree[i].lchild=-1; hufftree[i].rchild=-1; hufftree[i].parent=-1; hufftree[i].weight=0; } //构建霍夫曼树 for(int i=n;i<m;i++){ select(i,weight,s1,s2,hufftree);//从i的前面选取最小值和次小值 hufftree[s1].parent=i; hufftree[s2].parent=i; hufftree[i].lchild=s1; hufftree[i].rchild=s2; hufftree[i].weight=hufftree[s1].weight+hufftree[s2].weight;//构建新结点 } //霍夫曼编码 code=(char**)malloc(n*sizeof(char*));//n个结点的霍夫曼编码地址 // char temp_code[n];//临时存储霍夫曼编码 char *temp_code=(char*)malloc(n*sizeof(char)); for(int i=0;i<n;i++){//从叶节点访问到根节点 int a,b; int start=n; temp_code[start]='\0';//字符串结尾 for(a=i,b=hufftree[a].parent; b!=-1 ;a=hufftree[a].parent,b=hufftree[b].parent){ if(a==hufftree[b].lchild){ temp_code[--start]='0';//左分支为0 } else{ temp_code[--start]='1';//右分支为1 } } code[i]=(char *)malloc((n-start+1)*sizeof(char));//n个节点霍夫曼代码的值 strcpy(code[i],&temp_code[start]); } } int main(){ int n,i,j,k;//叶子结点总数 char s[200];//存放字符 int weight[200];//存放权值 huffnode *hufftree;//创建结构体数组用来存储霍夫曼树 char **code;//存储霍夫曼编码 char ss[200];//用于转化哈夫曼编码的字符 scanf("%d\n",&n); for(i=0;i<n;i++) scanf("%c ",&s[i]); s[n]='\0';//s是字符数组，不是字符串数组 for(i=0;i<n;i++) scanf("%d",&weight[i]); HuffCode(weight,n,hufftree,code); fflush(stdin);//清空缓存区 gets(ss); for(i=0;ss[i]!='\0';i++){ for(k=0;k<n;k++) if(s[k]==ss[i]) break; for(j=0;code[k][j]!='\0';j++) cout<<code[k][j]; } printf("\n"); puts(ss); return 0; } ```

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++哈夫曼编码译码器设计与实现并对哈夫曼树进行先序遍历。

C语言文件/哈夫曼树/算法/二叉树

``` 在一个函数中，下面这两行运行无错误 fp=fopen("CodeFile.dat","wb"); fwrite(HC[i],sizeof(char),strlen(HC[i])+1,fp); //其中HC的类型是char ** //然后在另外一个函数中加入 fp=fopen("CodeFile.dat","rb"); for(int i=1;i<=n;i++) fread(HC[i].sizeof(char),strlen(HC[i])+1,fp); //就不行了，老是运行到这三行就出错。！！ //补充一些 typedef char ** HuffmanCode; HuffmanCode HC; HC = （HuffmanCode）malloc((n+1)*sizeof(char *)); //求救 ```

String s = new String(" a ") 到底产生几个对象？

Linux面试题（2020最新版）

JVM内存结构和Java内存模型别再傻傻分不清了

loonggg读完需要3分钟速读仅需 1 分钟大家好，我是你们的校长。我之前讲过，这年头，只要肯动脑，肯行动，程序员凭借自己的技术，赚钱的方式还是有很多种的。仅仅靠在公司出卖自己的劳动时...

85后蒋凡：28岁实现财务自由、34岁成为阿里万亿电商帝国双掌门，他的人生底层逻辑是什么？...

MySQL数据库面试题（2020最新版）

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