数据结构哈夫曼编码（数据结构哈夫曼编码问题，请高手帮忙）

本文目录

• 数据结构哈夫曼编码问题，请高手帮忙
• 一个关于数据结构的问题，有关哈夫曼编码的，解答看不懂，求解答，谢谢！
• c++数据结构哈夫曼编码问题
• 数据结构，第二题，哈夫曼编码， 过程详细说明一下，谢谢
• 求数据结构哈夫曼编码译码器

数据结构哈夫曼编码问题，请高手帮忙

用c编的程序如下

#include 《iostream.h》

#define MAX 21

typedef struct

{

 char data;    //节点值

 int weight;   //权重

 int parent;   //父节点

 int left;

 int right;

} huffnode;

typedef struct

{

 char cd;

 int start;

}huffcode;

void main()

{

 huffnode ht;

 huffcode hcd,d;

 int i,k,f,l,r,n,c,m1,m2;

 cout《《"元素个素：";

 cin》》n;

 for (i=1;i《=n;i++)

 {

  cout《《"第"《《i《《"个元素=》\t节点值：";

  cin》》ht.data;

  cout《《"\t\t权  重：";

  cin》》ht.weight;

 }

 for (i=1;i《=2*n-1;i++)

  ht.right=0;

 for (i=n+1;i《=2*n-1;i++)   //构造HUFFMAN树

 {

  m1=m2=32767;     //l和r为最小权重的两个节点位置

  l=r=0;

  for(k=1;k《=i-1;k++)

   if(ht.parent==0)

    if(ht.weight《m1)

    {m2=m1;

    r=l;

    m1=ht.weight;

    l=k;

    }

    else if(ht.weight《m2)

    {

     m2=ht.weight;

     r=k;

    }

    ht.parent=i;

    ht.parent=i;

    ht.weight;

    ht.left=l;

    ht.right=r;

    }

 for (i=1;i《=n;i++)  //根据huffman树求huffman编码

 {

  d.start=n+1;

  c=i;

  f=ht.parent;

  while (f!=0)

  {

   if(ht.left==c)

    d.cd=’0’;

   else

    d.cd=’1’;

   c=f;

   f=ht.parent;

  }

  hcd=d;

 }

 cout《《"输出huffman编码:\n";

 for(i=1;i《n;i++)

 {

  cout《《" "《《ht.data《《":";

  for (k=hcd.start;k《=n;k++)

   cout《《hcd;

  cout《《endl;

 }

}

运行结果见图片

一个关于数据结构的问题，有关哈夫曼编码的，解答看不懂，求解答，谢谢！

根据题意哈夫曼树的形状类似如下 o / \ o Y / \ o Y / \ o o / \ / \A B C D或者 o / \ o Y / \ o Y / \ o C / \ A B第1点，编码长度不超过4，每一个“/”边表示为0 ，“\”边表示为1，如上图A的编码是：0000，B是0001，如果深度超过5，有六层的话，最下面的叶子结点编码有5位，所以编码长度不超过4，说明哈夫曼树深度不超过5第2点，编码1 和 01 是在深度为2、3层，如上面的图Y。第3点，其他字符有可能是00或者 0000 0001 0010 0011或者 001 0000 0001 在第三层 第四层 第五层，这里说只能在第四层和第五层，不严谨。有可能只有是三个字符的时候，只有三层了。还可以多少个字符编码：1个或者3个或者4个。

c++数据结构哈夫曼编码问题

我们也有这个实验，只有生成树和编码的后面可以自己做哦!#include《iostream》#include《cstring》using namespace std;const char ch = { ’A’, ’B’, ’C’, ’D’, ’E’, ’F’, ’G’, ’H’, ’I’, ’J’, ’K’, ’L’,’M’, ’N’, ’O’, ’P’, ’Q’, ’R’, ’S’, ’T’, ’U’, ’V’, ’W’, ’X’, ’Y’, ’Z’ };const double w = { 8.19, 1.47, 3.83, 3.91, 12.25, 2.26, 1.71, 4.57, 7.10,0.14, 0.41, 3.77, 3.34, 7.06, 7.26, 2.89, 0.09, 6.85, 6.36, 9.41, 2.58,1.09, 1.59, 0.21, 1.58, 0.08 }; //百分比%const int n = sizeof(w) / sizeof(w);const double MAX = 10000;struct element {double weight; // 字符出现的概率为实数int lchild, rchild, parent;};void HuffmanCode(element huffTree, int n) {for (int i = 0; i 《 n; i++) {string strc="";int j = i,t=0; //暂存i,不破坏循环变量while (huffTree.parent != 0) {if (huffTree.lchild == j)strc = ’1’+strc;elsestrc = ’0’+strc;j = huffTree.parent;t++;}cout 《《 ch 《《 ":"+strc;for(t=12-t;t》0;t--)cout《《" ";if(i%6==5)cout《《endl;}}void Select(element huffTree, int& i1, int& i2) {double MIN1 = MAX, MIN2 = MAX;for (int i = 0; i 《 2 * n - 1; i++) {if ((huffTree.weight != 0)) {if ((huffTree.weight 《 MIN2)) {if (MIN1 《 MIN2) {MIN2 = huffTree.weight;i2 = i;} else {MIN1 = huffTree.weight;i1 = i;}}}}}void HuffmanTree(element huffTree) {for (int i = 0; i 《 2 * n - 1; i++) {huffTree.parent = 0;huffTree.lchild = 0;huffTree.rchild = 0;}for (int i = 0; i 《 n; i++)huffTree;for (int k = n; k 《 2 * n - 1; k++) {int i1 = -1, i2 = -1;Select(huffTree, i1, i2);huffTree.parent = k;huffTree.parent = k;huffTree.weight;huffTree.lchild = i1;huffTree.rchild = i2;}}element huffTree;int main() {HuffmanTree(huffTree, w);HuffmanCode(huffTree, n);return 0;}

数据结构，第二题，哈夫曼编码， 过程详细说明一下，谢谢

频率 0.07，0.19， 0.02， 0.06， 0.32， 0.03，0.21， 0.10，排序一下

0.02，0.03，0.06, 0.07, 0.10, 0.19, 0.21, 0.32

构造哈夫曼树

                 0.1        /                    \     0.40                     0.60    /     \              /            \             0.19    0.21         0.28           0.32                   /         \              0.11           0.17              /   \         /    \           0.05    0.06  0.07   0.10           /  \        0.02  0.03 以/ 用0表示  \用1表示 结果0.19频率出现的字符编码：00     0.21                  ：01     0.32                  : 11     0.06                  : 1001     0.07                  : 1010            0.10                  : 1011     0.02                  : 10000     0.03                  : 10001 哈夫曼编码时频率出现越高的字符编码越短，越低的编码越长。 0-7二进制表示字符的编码是等长的， 000  001  010  011 100 101 110 111

哈夫曼编码可以起到压缩的作用。

求数据结构哈夫曼编码译码器

#ifndef Huffman_Tree_h#define Huffman_Tree_h#endif#include 《stdio.h》typedef struct { unsigned int weight; unsigned int parent,lchild,rchild;}HTNode, * HuffmanTree; //存储赫夫曼树的结点类型typedef char * * HuffmanCode; //用于存储字符集中各个字符相应的赫夫曼编码void strcpy(char *S1,char *S2){ //将字符串S2复制到S1 int i = 0; while( S2 != ’\0’ ){ S1; i++; } S1 = ’\0’;}void Select(HuffmanTree HT,int t,int &s1,int &s2){ //在HT中找出权值最小的两个S1和S2 int i = 1; s1 = s2 = 0; HT.weight = 65535; while( i 《= t ){ //遍历查找权值最小的结点S1 if( HT.weight ) s1 = i; i++; } i = 1; while( i 《= t ){ //遍历查找除S1外权值最小的结点S2 if( i != s1 && HT.weight ) s2 = i; i++; }}int HuffmanCoding( HuffmanTree &HT,HuffmanCode &HC,int *w,int n){ //根据各个字符的权值构造赫夫曼树HT，将对应的赫夫曼编码存储在HC中 int s1,s2,m,i,start; unsigned int c,f; HTNode * p; char *cd; if( n 《= 1 ) return 0; m = 2 * n - 1; //赫夫曼树的总结点树为m HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode)); //申请存储赫夫曼树的空间 for(p = HT + 1, i = 1; i 《= n; ++i, ++p, ++w){ //将各个叶子结点的weight赋以相应的权值，parent,lchild,rchild均赋为0 p-》weight = *(w+1); p-》parent = p-》lchild = p-》rchild = 0; } for( ; i 《= m; ++i, ++p ){ //将各个非叶子结点的weight,parent,lchild,rchild均赋为0 p-》weight = p-》parent = p-》lchild = p-》rchild = 0; } for( i = n + 1; i 《= m; ++i ){ //构造赫夫曼树，给各个非叶子结点赋值 Select(HT, i - 1, s1, s2); HT.parent = i; HT.rchild = s2; HT.weight; } HC = (HuffmanCode)malloc((n + 1) * sizeof(char *)); //申请空间，用于存储指向存储各个字符相应赫夫曼编码的字符数组的指针 cd = (char *)malloc(n * sizeof(char)); //申请用于求赫夫曼编码 cd = ’\0’; //编码结束符 for( i = 1; i 《= n; ++i){ //逐个字符求赫夫曼编码 start = n -1; //编码在数组cd中的最前位置 for(c = i,f = HT.parent) //从叶子到根逆向求编码 if(HT.lchild == c) cd = ’0’; else cd = ’1’; HC = (char *)malloc((n - start)*sizeof(char)); //为第i个字符编码分配空间 strcpy(HC } free(cd); //释放空间 return 1;}以上为第一部分#include 《stdio.h》#include 《stdlib.h》#include "Huffman_Tree.h"#define Yes 1 //当程序已经调用过初始化赫夫曼树的InitHuff_T()函数，或已从htfTree文件读取过，则将Init_Mode置为Yes，否则为No#define No 0void InitHuff_T( HuffmanTree &HT, HuffmanCode &HC, char ch,int &n ){ //初始化赫夫曼数，要求用户输入字符和相应权值 int i = 1,w,tem,j; char a; FILE *save; printf("请输入编码字符集的大小n:"); scanf("%d",&n); //获取用户输入的字符集个数 while( i 《= n ){ //获取用户输入的字符和相应权值，分别存储在ch数组中 printf("请输入第%d个字符和该字符的权值w:",i); fflush(stdin); scanf("%c%d",&ch); i++; } ch = ’\0’; HuffmanCoding(HT,HC,w,n); //根据用户的输入，生成赫夫曼数及各个字符相应的赫夫曼编码，分别存在HT树和HC中 if(( save = fopen("htfTree","w")) == NULL ){ //打开用于存储赫夫曼树的文件 printf("Open file fail......\n"); exit(0); } tem = n; //接下来的14行是将字符集大小转换成字符形式写入到文件中 j = 0; while( tem != 0 ){ tem = tem / 10; j++; } tem = n; a = ’\0’; while( tem != 0 ){ a = (char)(tem % 10 + 48); tem = tem / 10; j--; } fputs(a,save); printf("%d\n",n); //向屏幕输出字符集大小n fputc(’\n’,save); for( i = 1; i 《= n; i++ ){ //分别向文件和屏幕输出各个字符和相应的赫夫曼编码 fputc(ch); fputc(’\t’,save); fputs(HC); fputc(’\n’,save); } for(i = 1; i 《= 2 * n - 1; i++ ){ //将赫夫曼树各个结点的parent,lchild,rchild分别写入到文件中 tem = HT.parent; //将i结点的parent转换成字符并写入到文件中 if(tem == 0){ fputc(tem + 48,save); fputc(’ ’,save); } else{ j = 0; while( tem != 0 ){ tem = tem / 10; j++; } tem = HT.parent; a = ’\0’; while( tem != 0 ){ a = (char)(tem % 10 + 48); tem = tem / 10; j--; } fputs(a,save); fputc(’ ’,save); }tem = HT.lchild; //将i结点的lchild转换成字符并写入到文件中 if(tem == 0){ fputc(tem + 48,save); fputc(’ ’,save); } else{ j = 0; while( tem != 0 ){ tem = tem / 10; j++; } tem = HT.lchild; a = ’\0’; while( tem != 0 ){ a = (char)(tem % 10 + 48); tem = tem / 10; j--; } fputs(a,save); fputc(’ ’,save); }tem = HT.rchild; //将i结点的rchild转换成字符并写入到文件中 if(tem == 0){ fputc(tem + 48,save); fputc(’\n’,save); } else{ j = 0; while( tem != 0 ){ tem = tem / 10; j++; } tem = HT.rchild; a = ’\0’; while( tem != 0 ){ a = (char)(tem % 10 + 48); tem = tem / 10; j--; } fputs(a,save); fputc(’\n’,save); } } fclose(save);}void Encoding(HuffmanTree &HT, HuffmanCode &HC, char ch){ //根据赫夫曼编码将用户指定的文件中的字符编成相应的编码,并将所得编码存储到用户指定文件 FILE *ToBeTran,*CodeFile; char ToBeTran_Name; //存储用户指定文件的文件名 int i; char c; printf("请输入所要进行编码的文件的文件名:"); scanf("%s",ToBeTran_Name); //获得所要进行编码的文件的文件名 if(( ToBeTran = fopen(ToBeTran_Name,"r")) == NULL ){ //打开文件 printf("Open file fail......\n"); exit(0); } printf("请输入编码后编码表示的信息所存储到的文件的文件名:"); scanf("%s",CodeFile_Name); //获得编码后编码表示的信息所存储到的文件的文件名 if(( CodeFile = fopen(CodeFile_Name,"w")) == NULL ){ //打开文件 printf("Open file fail......\n"); exit(0); } c = fgetc(ToBeTran); //从文件读取一个字符 while( c != EOF ){ //对文件中的各个字符进行编码，直至文件结尾 i = 1; while( c != ch数组中查找从文件读取的字符 i++; if(ch数组中，c无法被识别，程序出错，退出 printf("字符%c无法识别，程序将退出。\n",c); exit(0); } fputs(HC,CodeFile); //若找到，则将c相应的赫夫曼编码写入到文件中 printf("%s",HC); //将c相应的赫夫曼编码输出到屏幕 c = fgetc(ToBeTran); //读入文件中的下一个字符 } printf("\n"); fclose(ToBeTran); fclose(CodeFile);}void Decoding(HuffmanTree HT, char ch , int n){ //对指定的存储由赫夫曼编码表示的信息的文件进行译码，翻译成相应的字符表示，并存储到指定文件 int p,i = 1; char code,c; char CodeFile_Name; //存储用户指定文件的文件名 p = 2 * n - 1; FILE *CodeFile,*TextFile; printf("请输入所要译的文件名:"); scanf("%s",CodeFile_Name); //获得所要译的文件的文件名 if(( CodeFile = fopen("CodeFile","r")) == NULL ){ //打开文件 printf("Open file fail......\n"); exit(0); } printf("请输入译后的字符存储到的文件的文件名:"); scanf("%s",TextFile_Name); //获得译后的字符存储到的文件的文件名 if(( TextFile = fopen(TextFile_Name,"w")) == NULL ){ //打开文件 printf("Open file fail......\n"); exit(0); } c = fgetc(CodeFile); while( c != EOF ){ code = c; i++; c = fgetc(CodeFile); } code数组中 i = 1; while ( code中的赫夫曼编码进行译码 if ( code == ’0’ ) p=HT.lchild; //进入左分支 else p = HT.rchild; //进入右分支 if (!HT.rchild){ //进入叶子结点 fputc(ch, TextFile); //将相应的字符写入到文件中 printf("%c",ch); //将相应的字符输出到屏幕 p = 2 * n - 1; //重新从树根出发进行译码 } i++; } printf("\n");}void ReadHuff_T( HuffmanTree &HT, HuffmanCode &HC, char ch, int &n){ //从文件读取赫夫曼树 FILE *htfTree; char c,ch1; int i,j,t; if(( htfTree = fopen("htfTree","r")) == NULL ){ //打开存有赫夫曼树信息的文件 printf("Open file fail......\n"); exit(0); } fgets(c,10,htfTree); //获取赫夫曼树叶子结点个数的字符串表示形式 i = 0; //以下6行将字符串形式转换成整数形式 while( c != ’\n’ ) i++; n = 0; for( j = 0; j 《 i; j++ ) n = 10 * n + c - ’0’; //求出叶子结点数n HC = (HuffmanCode)malloc((n + 1) * sizeof(char *)); //申请HC空间 HT = (HuffmanTree)malloc((2 * n) * sizeof(HTNode)); //申请赫夫曼树存储空间 i = 1; while( i 《= n ){ ch = fgetc(htfTree); //读取字符集中的一个字符 HC = (char *)malloc((10)*sizeof(char)); //申请用于存储读取到的字符集中的字符的赫夫曼编码的空间 fgetc(htfTree); //将‘\t’输出 ch1 = fgetc(htfTree); //读取赫夫曼编码，存储在相应的HC数组里 int j = 0; while( ch1 != ’\n’ ){ HC = ch1; j++; ch1 = fgetc(htfTree); } HC = ’\0’; i++; } ch = ’\0’; i = 0; while( i 《 2 * n - 1 ){ //读取赫夫曼树的各个结点的parent,lchild,rchild.并赋值到赫夫曼树HT中 ch1 = fgetc(htfTree); //读取parent的字符串形式,存储在c.parent j = 0; while( ch1 != ’ ’ ){ c = ch1; j++; ch1 = fgetc(htfTree); } HT.parent = 0; for( t = 0; t 《 j; t++ ) HT - ’0’; ch1 = fgetc(htfTree); //读取lchild的字符串形式，并将其转换成整数形式，赋给HT.lchild j = 0; while( ch1 != ’ ’ ){ c = ch1; j++; ch1 = fgetc(htfTree); } HT.lchild = 0; for( t = 0; t 《 j; t++ ) HT - ’0’; ch1 = fgetc(htfTree); //读取rchild的字符串形式，并将其转换成整数形式，赋给HT.rchild j = 0; while( ch1 != ’\n’ ){ c = ch1; j++; ch1 = fgetc(htfTree); } HT.rchild = 0; for( t = 0; t 《 j; t++ ) HT - ’0’; i++; }}int main(){ HuffmanTree HT; HuffmanCode HC; char ch; //用于存储字符集 int n,Init_Mode = No; //n为字符集的大小，Init_Mode = No 表示内存中没有赫夫曼树的信息 char mode; //让用户选择不同的操作 printf("请输入你要选择的功能\n"); printf("\t\tI -- 初始化\t\tE -- 编码\n"); printf("\t\tD -- 译码 \t\tQ -- 退出程序\n"); scanf("%c",&mode); //获得用户选择的操作 while( mode != ’Q’ && mode != ’q’ ){ //当用户输入不为Q或q时，执行相应操作 switch(mode){ case ’I’ : InitHuff_T(HT,HC,ch,n); Init_Mode = Yes; break; case ’i’ : InitHuff_T(HT,HC,ch,n); Init_Mode = Yes; break; case ’E’ : if( No == Init_Mode ) ReadHuff_T(HT,HC,ch,n); Encoding(HT,HC,ch); Init_Mode = Yes; break; case ’e’ : if( No == Init_Mode ) ReadHuff_T(HT,HC,ch,n); Encoding(HT,HC,ch); Init_Mode = Yes; break; case ’D’ : if( No == Init_Mode ) ReadHuff_T(HT,HC,ch,n); Decoding(HT,ch,n); Init_Mode = Yes; break; case ’d’ : if( No == Init_Mode ) ReadHuff_T(HT,HC,ch,n); Decoding(HT,ch,n); Init_Mode = Yes; default : printf("您的输入有错，请重新选择.\n"); } printf("请输入你要选择的功能\n"); printf("\tI -- 初始化\tE -- 编码\n"); printf("\tD -- 译码 \tQ -- 退出程序\n"); fflush(stdin); scanf("%c",&mode); //让用户继续选择相应的操作，直至用户选择退出 } return 0;} 第二部分1。进vc++6.02。新建一个新工程 选择Win32 Console application 一个空工程 确认 3。新建一个c++源文件 命名为Huffman_Tree.h 记住 命名很重要 然后将第一部分烤贝 粘贴 一定得是这个名字 然后编译保存 4。在新建一个c++源文件命名为 赫夫曼.cpp 然后将第二部分拷贝 粘贴 编译保存 然后就大功告成了 可以执行了 需要注意的是 编译后生成的可执行文件保存在 你新建工程是的那个默认文件夹里 当然你也可以在新建工程是选择你想要保存可执行文件的文件夹 方便查找