下载文档原格式
C++哈夫曼树编码和译码的实现⼀．背景介绍： 给定n个权值作为n个叶⼦结点，构造⼀棵⼆叉树，若带权路径长度达到最⼩，称这样的⼆叉树为最优⼆叉树，也称为哈夫曼树(Huffman Tree)。
哈夫曼树是带权路径长度最短的树，权值较⼤的结点离根较近。
⼆．实现步骤： 1.构造⼀棵哈夫曼树 2.根据创建好的哈夫曼树创建⼀张哈夫曼编码表 3.输⼊⼀串哈夫曼序列，输出原始字符三．设计思想： 1.⾸先要构造⼀棵哈夫曼树，哈夫曼树的结点结构包括权值，双亲，左右孩⼦；假如由n个字符来构造⼀棵哈夫曼树，则共有结点2n-1个；在构造前，先初始化，初始化操作是把双亲，左右孩⼦的下标值都赋为0；然后依次输⼊每个结点的权值2.第⼆步是通过n-1次循环，每次先找输⼊的权值中最⼩的两个结点，把这两个结点的权值相加赋给⼀个新结点，，并且这个新结点的左孩⼦是权值最⼩的结点，右孩⼦是权值第⼆⼩的结点；鉴于上述找到的结点都是双亲为0的结点，为了下次能正确寻找到剩下结点中权值最⼩的两个结点，每次循环要把找的权值最⼩的两个结点的双亲赋值不为0（i）.就这样通过n-1循环下、操作，创建了⼀棵哈夫曼树，其中，前n 个结点是叶⼦（输⼊的字符结点）后n-1个是度为2的结点3.编码的思想是逆序编码，从叶⼦结点出发，向上回溯，如果该结点是回溯到上⼀个结点的左孩⼦，则在记录编码的数组⾥存“0”，否则存“1”，注意是倒着存；直到遇到根结点（结点双亲为0），每⼀次循环编码到根结点，把编码存在编码表中，然后开始编码下⼀个字符（叶⼦）4．译码的思想是循环读⼊⼀串哈夫曼序列，读到“0”从根结点的左孩⼦继续读，读到“1”从右孩⼦继续，如果读到⼀个结点的左孩⼦和右孩⼦是否都为0，如果是说明已经读到了⼀个叶⼦（字符），翻译⼀个字符成功，把该叶⼦结点代表的字符存在⼀个存储翻译字符的数组中，然后继续从根结点开始读，直到读完这串哈夫曼序列，遇到结束符便退出翻译循环四．源代码：1/***************************************2⽬的：1.根据输⼊的字符代码集及其权值集，3构造赫夫曼树，输出各字符的赫夫曼编码42.输⼊赫夫曼码序列，输出原始字符代码5作者：Dmego 时间：2016-11-116****************************************/7 #include<iostream>8#define MAX_MA 10009#define MAX_ZF 10010using namespace std;1112//哈夫曼树的储存表⽰13 typedef struct14 {15int weight; //结点的权值16int parent, lchild, rchild;//双亲，左孩⼦，右孩⼦的下标17 }HTNode,*HuffmanTree; //动态分配数组来储存哈夫曼树的结点1819//哈夫曼编码表的储存表⽰20 typedef char **HuffmanCode;//动态分配数组存储哈夫曼编码2122//返回两个双亲域为0且权值最⼩的点的下标23void Select(HuffmanTree HT, int n, int &s1, int &s2)24 {25/*n代表HT数组的长度26*/2728//前两个for循环找所有结点中权值最⼩的点（字符）29for (int i = 1; i <= n; i++)30 {//利⽤for循环找出⼀个双亲为0的结点31if (HT[i].parent == 0)32 {33 s1 = i;//s1初始化为i34break;//找到⼀个后⽴即退出循环35 }36 }37for (int i = 1; i <= n; i++)38 {/*利⽤for循环找到所有结点（字符）权值最⼩的⼀个39并且保证该结点的双亲为0*/40if (HT[i].weight < HT[s1].weight && HT[i].parent == 0)41 s1 = i;42 }43//后两个for循环所有结点中权值第⼆⼩的点（字符）44for (int i = 1; i <= n; i++)45 {//利⽤for循环找出⼀个双亲为0的结点，并且不能是s146if (HT[i].parent == 0 && i != s1)47 {48 s2 = i;//s2初始化为i49break;//找到⼀个后⽴即退出循环50 }51 }5253for (int i = 1; i <= n; i++)54 {/*利⽤for循环找到所有结点（字符）权值第⼆⼩的⼀个，55该结点满⾜不能是s1且双亲是0*/56if (HT[i].weight < HT[s2].weight && HT[i].parent == 0 && i!= s1)57 s2 = i;58 }5960 }6162//构造哈夫曼树63void CreateHuffmanTree(HuffmanTree &HT, int n)64 {65/*-----------初始化⼯作-------------------------*/66if (n <= 1)67return;68int m = 2 * n - 1;69 HT = new HTNode[m + 1];70for (int i = 1; i <= m; ++i)71 {//将1~m号单元中的双亲，左孩⼦，右孩⼦的下标都初始化为072 HT[i].parent = 0; HT[i].lchild = 0; HT[i].rchild = 0;73 }74for (int i = 1; i <= n; ++i)75 {76 cin >> HT[i].weight;//输⼊前n个单元中叶⼦结点的权值77 }78/*-----------创建⼯作---------------------------*/79int s1,s2;80for (int i = n + 1; i <= m; ++i)81 {//通过n-1次的选择，删除，合并来构造哈夫曼树82 Select(HT, i - 1, s1, s2);83/*cout << HT[s1].weight << " , " << HT[s2].weight << endl;*/84/*将s1,s2的双亲域由0改为i85 (相当于把这两个结点删除了，这两个结点不再参与Select()函数)*/86 HT[s1].parent = i;87 HT[s2].parent = i;88//s1,与s2分别作为i的左右孩⼦89 HT[i].lchild = s1;90 HT[i].rchild = s2;91//结点i的权值为s1,s2权值之和92 HT[i].weight = HT[s1].weight + HT[s2].weight;93 }94 }9596//从叶⼦到根逆向求每个字符的哈夫曼编码，储存在编码表HC中97void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n)98 {99 HC = new char*[n + 1];//分配储存n个字符编码的编码表空间100char *cd = new char[n];//分配临时存储字符编码的动态空间101 cd[n - 1] = '\0';//编码结束符102for (int i = 1; i <= n; i++)//逐个求字符编码103 {104int start = n - 1;//start 开始指向最后，即编码结束符位置105int c = i;106int f = HT[c].parent;//f指向结点c的双亲107while (f != 0)//从叶⼦结点开始回溯，直到根结点108 {109 --start;//回溯⼀次，start向前指向⼀个位置110if (HT[f].lchild == c) cd[start] = '0';//结点c是f的左孩⼦，则cd[start] = 0; 111else cd[start] = '1';//否则c是f的右孩⼦，cd[start] = 1112 c = f;113 f = HT[f].parent;//继续向上回溯114 }115 HC[i] = new char[n - start];//为第i个字符编码分配空间116 strcpy(HC[i], &cd[start]);//把求得编码的⾸地址从cd[start]复制到HC的当前⾏中117 }118delete cd;119 }120121//哈夫曼译码122void TranCode(HuffmanTree HT,char a[],char zf[],char b[],int n)123 {124/*125 HT是已经创建好的哈夫曼树126 a[]⽤来传⼊⼆进制编码127 b[]⽤来记录译出的字符128 zf[]是与哈夫曼树的叶⼦对应的字符（叶⼦下标与字符下标对应）129 n是字符个数，相当于zf[]数组得长度130*/131132int q = 2*n-1;//q初始化为根结点的下标133int k = 0;//记录存储译出字符数组的下标134int i = 0;135for (i = 0; a[i] != '\0';i++)136 {//for循环结束条件是读⼊的字符是结束符（⼆进制编码）137//此代码块⽤来判断读⼊的⼆进制字符是0还是1138if (a[i] == '0')139 {/*读⼊0，把根结点(HT[q])的左孩⼦的下标值赋给q140下次循环的时候把HT[q]的左孩⼦作为新的根结点*/141 q = HT[q].lchild;142 }143else if (a[i] == '1')144 {145 q = HT[q].rchild;146 }147//此代码块⽤来判断HT[q]是否为叶⼦结点148if (HT[q].lchild == 0 && HT[q].rchild == 0)149 {/*是叶⼦结点，说明已经译出⼀个字符150该字符的下标就是找到的叶⼦结点的下标*/151 b[k++] = zf[q];//把下标为q的字符赋给字符数组b[]152 q = 2 * n - 1;//初始化q为根结点的下标153//继续译下⼀个字符的时候从哈夫曼树的根结点开始154 }155 }156/*译码完成之后，⽤来记录译出字符的数组由于没有结束符输出的157时候回报错，故紧接着把⼀个结束符加到数组最后*/158 b[k] = '\0';159 }160//菜单函数161void menu()162 {163 cout << endl;164 cout << " ┏〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓┓" << endl;165 cout << " ┃★★★★★★★哈夫曼编码与译码★★★★★★★┃" << endl;166 cout << " ┃ 1. 创建哈夫曼树┃" << endl;167 cout << " ┃ 2. 进⾏哈夫曼编码┃" << endl;168 cout << " ┃ 3. 进⾏哈夫曼译码┃" << endl;169 cout << " ┃ 4. 退出程序┃" << endl;170 cout << " ┗〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓┛" << endl;171 cout << " <><注意：空格字符⽤'- '代替><>" << endl;172 cout << endl;173 }174void main()175 {176int falg;//记录要编码的字符个数177char a[MAX_MA];//储存输⼊的⼆进制字符178char b[MAX_ZF];//存储译出的字符179char zf[MAX_ZF];//储存要编码的字符180 HuffmanTree HT = NULL;//初始化树为空数181 HuffmanCode HC = NULL;//初始化编码表为空表182 menu();183while (true)184 {185int num;186 cout << "<><请选择功能(1-创建 2-编码 3-译码 4-退出)><>: ";187 cin >> num;188switch (num)189 {190case1 :191 cout << "<><请输⼊字符个数><>:";192 cin >> falg;193//动态申请falg个长度的字符数组，⽤来存储要编码的字符194/*char *zf = new char[falg];*/195 cout << "<><请依次输⼊" << falg << "个字符:><>: ";196for (int i = 1; i <= falg; i++)197 cin >> zf[i];198 cout << "<><请依次输⼊" << falg << "个字符的权值><>: ";199 CreateHuffmanTree(HT, falg);//调⽤创建哈夫曼树的函数200 cout << endl;201 cout << "<><创建哈夫曼成功！,下⾯是该哈夫曼树的参数输出><>：" << endl;202 cout << endl;203 cout << "结点i"<<"\t"<<"字符" << "\t" << "权值" << "\t" << "双亲" << "\t" << "左孩⼦" << "\t" << "右孩⼦" << endl;204for (int i = 1; i <= falg * 2 - 1; i++)205 {206 cout << i << "\t"<<zf[i]<< "\t" << HT[i].weight << "\t" << HT[i].parent << "\t" << HT[i].lchild << "\t" << HT[i].rchild << endl; 207 }208 cout << endl;209break;210case2:211 CreatHuffmanCode(HT, HC, falg);//调⽤创建哈夫曼编码表的函数212 cout << endl;213 cout << "<><⽣成哈夫曼编码表成功！,下⾯是该编码表的输出><>：" << endl; 214 cout << endl;215 cout << "结点i"<<"\t"<<"字符" << "\t" << "权值" << "\t" << "编码" << endl; 216for (int i = 1; i <= falg; i++)217 {218 cout << i << "\t"<<zf[i]<< "\t" << HT[i].weight << "\t" << HC[i] << endl; 219 }220 cout << endl;221break;222case3:223 cout << "<><请输⼊想要翻译的⼀串⼆进制编码><>：";224/*这样可以动态的直接输⼊⼀串⼆进制编码，225因为这样输⼊时最后系统会⾃动加⼀个结束符*/226 cin >> a;227 TranCode(HT, a, zf, b, falg);//调⽤译码的函数，228/*这样可以直接把数组b输出，因为最后有229在数组b添加输出时遇到结束符会结束输出*/230 cout << endl;231 cout << "<><译码成功！翻译结果为><>：" << b << endl;232 cout << endl;233break;234case4:235 cout << endl;236 cout << "<><退出成功！><>" << endl;237 exit(0);238default:239break;240 }241 }242243//-abcdefghijklmnopqrstuvwxyz244//186 64 13 22 32 103 21 15 47 57 1 5 32 20 57 63 15 1 48 51 80 23 8 18 1 16 1245//000101010111101111001111110001100100101011110110246247 }哈夫曼编码译码五．运⾏截图：。
实验：哈夫曼树编码及译码的实现一．实验题目给定字符集的HUFFMANN编码与解码，这里的字符集及其字符频数自己定义，要求输出个字符集的哈夫曼编码及给定的字符串的哈夫曼码及译码结果。
二．实验原理首先规定构建哈夫曼树，然后进行哈夫曼树的编码，接着设计函数进行字符串的编码过程，最后进行哈夫曼编码的译码。
首先定义一个结构体，这个结构体定义时尽可能的大，用来存放左右的变量，再定义一个地址空间，用于存放数组，数组中每个元素为之前定义的结构体。
输入n个字符及其权值。
构建哈夫曼树：在上述存储结构上实现的哈夫曼算法可大致描述为：1.首先将地址空间初始化，将ht[0…n-1]中所有的结点里的指针都设置为空，并且将权值设置为0.2.输入:读入n个叶子的权值存于向量的前n个分量中。
它们是初始森林中n个孤立的根结点上的权值。
3.合并:对森林中的树共进行n-1次合并，所产生的新结点依次放入向量ht的第i个分量中。
每次合并分两步：①在当前森林ht[0…i-1]的所有结点中，选取权最小和次小的两个根结点[s1]和 [s2]作为合并对象，这里0≤s1，s2≤i-1。
②将根为ht[s1]和ht[s2]的两棵树作为左右子树合并为一棵新的树，新树的根是新结点ht[i]。
具体操作：将ht[s1]和ht[s2]的parent置为i，将ht[i]的lchild和rchild分别置为s1和s2 .新结点ht[i]的权值置为ht[s1]和ht[s2]的权值之和。
4.哈夫曼的编码：约定左子为0，右子为1，则可以从根结点到叶子结点的路径上的字符组成的字符串作为该叶子结点的编码。
当用户输入字母时。
就在已经找好编码的编码结构体中去查找该字母。
查到该字母就打印所存的哈夫曼编码。
接着就是完成用户输入0、1代码时把代码转成字母的功能。
这是从树的头结点向下查找，如果当前用户输入的0、1串中是0则就走向该结点的左子。
如果是1这就走向该结点的右结点，重复上面步骤。
哈夫曼编码一、实验目的1、掌握哈夫曼编码的二叉树结构表示方法；2、编程实现哈夫曼编码译码器；3、掌握贪心算法的设计策略。
二、实验任务①从文件中读取数据，构建哈夫曼树；②利用哈夫曼树，对输入明文进行哈夫曼编码；③利用哈夫曼树，对输入编码译码为明文。
三、实验设计方案1、结构体设计Huffman树：包括字符，权，父亲下标，左孩子下标，右孩子下标2、自定义函数设计①函数原型声明void input(); //读取文件字符、权值数据void huffman(); //建立huffman树void getcode(int i, char *str); //得到单个字符的huffman编码void encode(char ch); //将明文进行huffman编码void decode(char *str); //将huffman编码译为明文3、主函数设计思路：主函数实现实验任务的基本流程。
void main(){char ch;int i;char str[100];huffman(); //建立huffman树printf("请输入明文："); //输入明文while((ch=getchar())!='\n')encode(ch); //得到huffman编码printf("\n");printf("\n请按字符编码对应表输入密文：\n");for(i=0;i<N;i++) //显示字符编码对应表{printf("%c:",ht[i].c);encode(ht[i].c);printf("\t");}scanf("%s",str); //输入编码串decode(str); //翻译成明文printf("\n");}程序代码：#include<stdio.h>struct shuju{char str;int data;};struct treenode{char c;int w;int f;int l;int r;};void sort(shuju a[],int num) {int i,j;shuju t;for(i=0;i<num;i++){int m=i;for(j=i+1;j<num;j++)if(a[j].data<a[m].data)m=j;t=a[m];a[m]=a[i];a[i]=t;}}void huffman(shuju a[],treenode htree[],int num) {int i,j,k,n;for(i=0; i<num; i++){htree[i].c=a[i].str;htree[i].w=a[i].data;htree[i].l=-1;htree[i].f=-1;htree[i].r=-1;}j=0;k=num;for(n=num;n<2*num-1;n++)htree[n].w=0;for(n=num;n<2*num-1;n++){int r=0,s=0;htree[n].l=-1;htree[n].f=-1;htree[n].r=-1;while(r<2){if((htree[k].w==0 || htree[k].w>htree[j].w) && j<num){ s=s+htree[j].w;if(r==0) htree[n].l = j;else htree[n].r=j;htree[j].f=n;j++;}else{s=s+htree[k].w;if(r==0) htree[n].l = k;else htree[n].r=k;htree[k].f=n;k++;}r++;}htree[n].w=s;}}int getcode(int i, int str[],treenode htree[]){int n,l=0;for(n=i;htree[n].f!=-1;n=htree[n].f){int m=htree[n].f;if(n==htree[m].l)str[l++]=0;elsestr[l++]=1;}return l;}void decode(treenode htree[],int c[],int n,int num){ int ch,m=0;ch=c[m];while(m<n){int i;for(i=2*num-2;htree[i].l!=-1;){if(ch==0)i=htree[i].l;elsei=htree[i].r;m++;ch=c[m];}printf("%c",htree[i].c);}}void main(){int str[1000],i,j,k,l,n,c[1000];FILE *fp;treenode htree[57];shuju a[29];char b[100];printf("请输入明文的长度n:");scanf("%d",&n);printf("请输入明文：");for(i=0;i<=n;i++)scanf("%c",&b[i]);fp=fopen("D:\\hanfuman\\shuju.txt","r"); for( i=0;i<29;i++){fscanf(fp,"%c%d\n",&a[i].str,&a[i].data);}fclose(fp);sort(a,29);huffman(a,htree,29);printf("输出译码是：");for(i=0;i<=n;i++){for(j=0;j<29;j++){if(b[i]==a[j].str){l=getcode(j,str,htree);for(k=l-1;k>=0;k--)printf("%d",str[k]);}}}printf("\n");printf("请输入译码的长度n："); scanf("%d",&n);printf("请输入译码：");for(i=0;i<n;i++)scanf("%d",&c[i]);printf("输出解码为：");decode(htree,c,n,29);printf("\n");}D:\\hanfuman\\shuju.txt中的内容为：j 217z 309q 343x 505k 1183w 1328v 1531f 1899. 2058y 2815b 2918g 3061, 3069h 3724d 4186m 4241p 4283u 49105005c 6028s 6859l 6882n 7948o 8259t 8929r 9337i 9364a 10050e 11991 运行结果为：。
华%%%%%%%%%%%%%%%%%%学院数据结构实验报告2011～2012学年第二学期2011级计算机专业班级：学号：姓名：实验三树的应用一、实验题目：树的应用——哈夫曼编/译码二、实验内容：利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。
根据哈夫曼编码的原理，编写一个程序，在用户输入字符及权值的基础上求哈夫曼编码。
要求：（1）从键盘输入字符集（字母a～z，空格）共27个字符，以及出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，并输出数组ht[]的初态和终态。
（2）对各个字符进行哈夫曼编码，打印输出字符及对应的哈夫曼编码。
（3）编码：从键盘输入字符串，利用已建好的哈夫曼编码，实现该字符串的编码。
（4）（选作）译码：从键盘输入二进制串，利用已建好的哈夫曼编码，将二进制串还原为字符串。
三、程序源代码：typedef struct{char data;int weight;int parent;int lchild;int rchild;}HTNode;typedef struct{char cd[100];int start;}HCode;//这里保存字母对应的编码，我本来想用指向字符数组的指针数组，可是后来想到利用结构体更简单。
struct Codes{char ch;char codes[27];};#include<iostream.h>#include<stdio.h>#include<string.h>const int maxsize=100;//特色，动态编码void tongji(char str[],int *pinlv);void createHT(HTNode *ht,int n,int pinlv[]);void showHT(HTNode ht[],int n);void createHcode(HTNode ht[],HCode* hcd,int n);void showHCode(HCode hcd[],int n,int pinlv[]);//使字符与编码对应void matchcodes(HCode hcd[],int pinlv[],int n,Codes* code);void charToCode(Codes codes[],char *str);void codeToChar(Codes codes[]);void main(){cout<<"本例实现动态编码：根据输入的字符串建立编码规则，然后按此规则对输入的字符串进行编码，对输入的编码进行译码操作"<<endl;//输入cout<<"input a string"<<endl;char str[maxsize];gets(str);//统计int pinlv[27];int len=0;for(int i=0;i<27;i++)pinlv[i]=0;tongji(str,pinlv);for(int k=0;k<27;k++)if(pinlv[k]!=0)len++;cout<<len<<endl;// cout<<pinlv[26]<<endl;//构造哈夫曼树HTNode ht[199];createHT(ht,len,pinlv);//哈夫曼编码HCode hcd[27];createHcode(ht,hcd,len);showHCode(hcd,len,pinlv);//字符与编码对应匹配Codes codes[27];matchcodes(hcd,pinlv,len,codes);//char to codecharToCode(codes,str);// code to charcodeToChar(codes);}//这个函数有错误，已经改正void codeToChar(Codes codes[]){cout<<"根据上面输出的编码规则，请输入要译码的01编码（相邻编码要以逗号分割，以“#”结束）"<<endl;char str[100];gets(str);cout<<str<<"的译码为："<<endl;char temp[27]; //保存每个字符的编码，每次要赋 0 啊int i,j;for(i=0,j=0;i<100;i++){if(str[i]!=','){temp[j]=str[i];j++;}else{temp[j]='\0';for(int k=0;k<27;k++){if(strcmp(codes[k].codes ,temp)==0){cout<<codes[k].ch <<" ";//cout.flush();break;}}j=0; //赋0 操作}if(str[i]=='#'){break;}}cout<<endl;}void charToCode(Codes codes[],char *str){char ch=*str;int k=0;cout<<str<<"的编码为："<<endl;while(ch!='\0'){for(int i=0;i<27;i++){if(codes[i].ch ==ch)cout<<codes[i].codes<<"，";}k++;ch=*(str+k);}cout<<endl;}//已经改进过的地方void matchcodes(HCode hcd[],int pinlv[],int n,Codes* codes) {int i,k,m;char ch='a';int p=0;char temp[27];for(int z=0;z<26;z++){temp[z]=' ';}temp[26]='\0';for(i=0;i<27;i++){if(pinlv[i]!=0){ch='a';ch=char(ch+i);if(ch>='a'&&ch<='z'){codes[p].ch =ch;//测试/* if(codes[p].ch==ch){cout<<"succss"<<endl;}*/}elsecodes[p].ch =' ';m=0;for(k=hcd[p].start;k<=n;k++){temp[m]=hcd[p].cd [k];m++;}//字符串必须给出结束符位置，否则会输出乱码啊temp[m]='\0';//codes[p]=temp;strcpy(codes[p].codes ,temp);// cout<<codes[p].ch;// cout<<codes[p].ch<<"-----"<<codes[p].codes<<endl;p++;}}}void showHCode(HCode hcd[],int n,int pinlv[]){int i,k;char ch='a';int p=0;cout<<"字符"<<" "<<"对应编码"<<endl;for(i=0;i<27;i++){//每次必须从字符'a'开始ch='a';////ch=char(ch+i);if(pinlv[i]!=0){if(ch>='a'&&ch<='z')cout<<ch<<" ";elsecout<<" "<<" ";for(k=hcd[p].start;k<=n;k++)cout<<hcd[p].cd [k];p++;cout<<endl;}}}void createHcode(HTNode ht[],HCode* hcd,int n) {int i,f,c;HCode hc;for(i=0;i<n;i++){//不是书上的hc.start =n;hc.start =n-1;c=i;f=ht[i].parent ;while(f!=-1){if(ht[f].lchild ==c)hc.cd [hc.start --]='0';elsehc.cd [hc.start --]='1';c=f;f=ht[f].parent ;}//最后一位必须赋值为结束符hc.cd[n]='\0';hc.start ++;hcd[i]=hc;}}void createHT(HTNode* ht,int n,int pinlv[]){for(int m=0;m<=2*n-1;m++)//初始化节点的所有与域值ht[m].parent =ht[m].lchild =ht[m].rchild =-1;char ch='a';int p=0;for(int z=0;z<27;z++)//循环27个字母（a-z和''），若频数大于0，就创建节点{if(pinlv[z]!=0){if(ch>='a'&&'z'>=ch){ht[p].data =ch;ht[p].weight =pinlv[ch-97];}else{ht[p].data =' ';ht[p].weight =pinlv[26];}p++;}ch=char (ch+1);}cout<<"ht[]初态输出 ";showHT(ht,n);int i,k,lnode,rnode;int min1,min2;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[i].data ='*';}cout<<"ht[]终态输出 ";showHT(ht,2*n-1);}void tongji(char str[],int *pinlv){char ch=*str;int k=1;while(ch!='\0'){ if(ch>='a'&&'z'>=ch)pinlv[ch-97]+=1;elsepinlv[26]+=1;ch=*(str+k);k++;}}void showHT(HTNode ht[],int n){ cout<<"节点信息如下："<<endl;cout<<"data"<<" "<<"weig"<<" "<<"pare"<<" "<<"lchd"<<" "<<"rchd"<<endl;for(int i=0;i<n;i++){cout<<ht[i].data <<" "<<ht[i].weight <<" "<<ht[i].parent <<" "<<ht[i].lchild <<" "<<ht[i].rchild <<endl;}}四、测试结果：五、小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等）注：内容一律使用宋体五号字，单倍行间距通过本次实验，我感觉到自己的程序编程细节问题必须注意：如使用gets（）函数可接收带有空格的输入字符串；在进行编码译码时，必须注意，数组的上下界问题。
#include<stdio.h>#include<string.h>#include<stdlib.h>#define N 100#define M 2*N-1typedef struct //定义哈夫曼树存储节点结构体类型{char data;int weight;int parent;int lchild;int rchild;}HuffmanTree[M];typedef struct //定义哈夫曼编码结构体类型{char data;char bits[N];}HuffmanCode[N];typedef struct str //定义字符串存储单元结构体类型{char data;char num;//int num;}str;int read(str s2[]){FILE *fp;char ch;int i,k;str s1[128];for(i=0;i<=128;i++){s1[i].num = 0; s1[i].data = 0;s2[i].num = 0; s2[i].data = 0;}if((fp=fopen("ywq1.txt","r"))==NULL){printf("\n库文件不存在!");exit(1);}printf("\n读取字符串为:\n");ch=fgetc(fp);while(!feof(fp)) //统计字符频率{printf("%c",ch);s1[ch].num++;s1[ch].data = ch;ch=fgetc(fp);}fclose(fp);for(i=1,k=1;i<=128;i++){if(s1[i].num!=0){s2[k].num = s1[i].num;s2[k].data = s1[i].data;k++;}}printf("\n\n统计结果为(字符频率):\n");for(i=1;i<k;i++){printf("<%c %d> ",s2[i].data,s2[i].num);}printf(" (共%d种字符)\n",k-1);return k;}void SelectMin(HuffmanTree ht, int i,int *p1,int *p2) //查找哈夫曼链表中两个权值最小的节点{int j,min1,min2;min1 = min2 = -1;for(j = 1;j<=i;j++){if(ht[j].parent == 0){if(ht[j].weight<min1||min1==-1){if(min1!=-1){min2 = min1;*p2=*p1;}min1 = ht[j].weight;*p1=j;}else if(ht[j].weight<min2||min2==-1){min2 = ht[j].weight;*p2=j;}}}}void CrtHuffmanTree(HuffmanTree ht,str s[],int n) //创建哈夫曼树{int i,m,p1,p2;for(i=1;i<n;i++) //初始化节点{ht[i].data = s[i].data;ht[i].weight = s[i].num;ht[i].parent = 0;ht[i].lchild = 0;ht[i].rchild = 0;}m=2*n-3;for(i=n;i<=m;i++){ht[i].data = 0;ht[i].weight = 0;ht[i].parent = 0;ht[i].lchild = 0;ht[i].rchild = 0;}for(i=n;i<=m;i++){SelectMin(ht,i-1,&p1,&p2); //调用SelectMin函数ht[i].weight=ht[p1].weight+ht[p2].weight;ht[p1].parent=i;ht[p2].parent=i;ht[i].lchild=p1;ht[i].rchild=p2;}}void CrtHuffmanCode(HuffmanTree ht,HuffmanCode hc,int k) //利用建立好的哈夫曼树对字符串进行编码{int c,p,i;char cd[N+1];int start;for(i=1;i<k;i++){hc[i].data = ht[i].data;start = k-1;cd[start] = '\0';c=i;while((p=ht[c].parent)!=NULL){cd[--start] = (ht[p].lchild==c)?'0':'1'; //左分支为0，右分支为1c=p;}strcpy(hc[i].bits,&cd[start]);}printf("\n\n每个字符对应的编码为:\n");for(i=1;i<k;i++)printf("<%d %c %s> \n",i,hc[i].data,hc[i].bits);}void WriteToFile(HuffmanCode hc,int n) //将编码结果存储在文件文件ywq2.txt中{FILE *fp1,*fp2;char ch;int i;if((fp1=fopen("ywq1.txt","r"))==NULL){printf("\n文件不存在!");exit(1);}if((fp2=fopen("ywq2.txt","w"))==NULL){printf("\n文件不存在!");exit(1);}ch = fgetc(fp1);printf("\n编码结果为：");while(ch != EOF){for(i=1;i<n;i++)if(ch == hc[i].data){fputs(hc[i].bits,fp2);printf("%s",hc[i].bits);}ch = fgetc(fp1);}fclose(fp1);fclose(fp2);printf("\n");}void DecodHuffmanCode(HuffmanTree ht,int n) //码结果进行译码，并将结果存储在文件ywq3中{FILE *fp1,*fp2;char ch;int p,k;if((fp1=fopen("ywq2.txt","r"))==NULL){printf("\n文件不存在!");exit(1);}if((fp2=fopen("ywq3.txt","w"))==NULL){printf("\n文件未能创建!");exit(1);}p=k=2*n-3;ch=fgetc(fp1);printf("译码为: ");while(ch!=EOF){if(ch=='0')p=ht[p].lchild;else if(ch=='1') p=ht[p].rchild;if(ht[p].data!=0){printf("%c",ht[p].data);fputc(ht[p].data,fp2);p=k;}ch = fgetc(fp1);}printf("\n");fclose(fp1); fclose(fp2);}void compare(int k){FILE *fp1,*fp2;char s1[N],s2[N];int i=1,j=1;printf("\n\n编译前后结果的比较:");if((fp1=fopen("ywq1.txt","rt"))==NULL){printf("\n打开文件失败！\n");exit(1);}printf("\n\n原文件ywq1中的字符为: ");for(i=1;(s1[i]=fgetc(fp1))!=EOF;i++)printf("%c",s1[i]);fclose(fp1);if((fp2=fopen("ywq3.txt","rt"))==NULL){printf("\n打开文件失败！\n");exit(1);}printf("\n文件ywq3中的字符为: ");for(i=1;(s2[i]=fgetc(fp2))!=EOF;i++)printf("%c",s2[i]);fclose(fp2);while(j<k){if(s1[j]==s2[j])j++;else{printf("\n编码失败！\n");break;}}if(j==k)printf("\n前后数据一致，编码成功！\n"); }void main(){int i,k;int j=1;HuffmanTree ht;HuffmanCode hc;str s2[128];printf("\n-------------------------------哈夫曼编码译码器---------------------------------");k=read(s2);getchar();CrtHuffmanTree(ht,s2,k);CrtHuffmanCode(ht,hc,k);WriteToFile(hc,k);getchar();printf("\n\n");printf("建立的哈夫曼树为:");printf("\nnumber\tdata\tweight\tlchild\trchild\tparent ");for(i=1;i<k;i++){printf("\n%d : %c %d %d %d %d",i,ht[i].data,ht[i].weig ht,ht[i].lchild,ht[i].rchild,ht[i].parent) ;}printf("\n\n");DecodHuffmanCode(ht,k);getchar();compare(k);//printf("\n\n按任意键退出...\n");}。
测试文件内容Dear Editor: There is something to tell to you. I'm a middle school student.My name is Li Ming.Final exams are coming.Everyone is preparing for this.But there is some important problem during the review. Most of students often stay up late for the review.As the result,they always take a nap in the class and they can't keep the studying normal. I think we should be a reasonable time.The more relaxing we get,the better we will be.Brothers do not misuse wood workers I hope all the students can access to ideal scores. I'm expecting your answer and suggestion. Li Ming.源代码#include <stdio.h>#include <string.h>#include <stdlib.h>/* 哈夫曼树*/struct huffmantree{char ch; /* 字符*/int weight; /* 权值*/int parent; /* 父亲*/int lchild; /* 左孩子*/int rchild; /* 右孩子*/char *code; /* 编码*/};/* 字符-权值*/struct char_weight{char ch;int weight;};/* 带大小的字符-权值*/struct size_cw{int size;struct char_weight *cw;};/* 创建带大小的字符-权值表*/struct size_cw *create_scw(){FILE *fp;int i;int c;int cnt;int tmp[256]; /* 临时记录字符频度，哈希法*/struct size_cw *scw= (struct size_cw *)malloc(sizeof(struct size_cw));fp = fopen("data", "r");if (fp == NULL)return NULL; //执行错误for (i = 0; i < 256; i++)tmp[i] = 0;/* 从文件中统计字符频度*/while ((c = fgetc(fp)) != EOF)tmp[c]++;/* 统计字符种类*/scw->size = 0;for (i = 0; i < 256; i++)if (tmp[i] != 0)(scw->size)++;/* 根据tmp创建字符-权值表*/scw->cw = (struct char_weight *)malloc(sizeof(struct char_weight) *scw->size);cnt = 0;for (i = 0; i < 256; i++)if (tmp[i] != 0){scw->cw[cnt].ch = i;scw->cw[cnt].weight = tmp[i];cnt++;}fclose(fp);return scw; //执行成功}/* 在不存在父亲节点的节点中，找出1个权值最小的节点*/ int min_weight(struct huffmantree *ht, int n){int i;int min;for (i = 1; ; i++)if (ht[i].parent == 0){min = i;break;}for (i++; i <= n; i++){if (ht[i].parent)continue;if (ht[min].weight > ht[i].weight)min = i;}return min;}/* 在不存在父亲节点的点中，找出2个权值最小的节点*/ void min2_wieght(struct huffmantree *ht, int n, int *s1, int *s2) {*s1 = min_weight(ht, n);ht[*s1].parent = 1;*s2 = min_weight(ht, n);ht[*s1].parent = 0;}/* 创建哈夫曼树*/struct huffmantree *create_huffmantree(struct size_cw *scw) {int i;int s1, s2;struct huffmantree *ht;struct char_weight *cw = scw->cw;int leave = scw->size;int node = 2 * leave - 1;if (leave <= 1)return NULL;/* 0号节点不用*/ht = (struct huffmantree *)malloc(sizeof(struct huffmantree) *(node + 1));for (i = 1; i <= leave; i++, cw++){memset(ht+i, 0, sizeof(struct huffmantree));ht[i].ch = cw->ch;ht[i].weight = cw->weight;}for ( ; i <= node; i++)memset(ht+i, 0, sizeof(struct huffmantree));for (i = leave + 1; i <= node; i++){min2_wieght(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;}return ht;}/* 对哈夫曼树编码*/void code_huffmantree(struct huffmantree *ht, struct size_cw *scw) {int c, f;int i, start;int leave = scw->size;char *code = (char *)malloc(sizeof(char) * scw->size);code[leave-1] = '\0';for (i = 1; i <= leave; i++){start = leave - 1;for (c = i, f = ht[i].parent; f != 0; c = f, f = ht[f].parent)if (ht[f].lchild == c){code[--start] = '0';}else{code[--start] = '1';}ht[i].code = (char *)malloc(sizeof(char) * (leave - start));strcpy(ht[i].code, code + start);}free(code);}/* 打印字符频度表*/void print_cw(struct size_cw *scw){int i;for (i = 0; i < scw->size; i++)printf("%c\t %d\n", scw->cw[i].ch, scw->cw[i].weight);}/* 打印哈夫曼树*/void print_ht(struct huffmantree *ht, struct size_cw *scw){int i;for (i = 1; i <= 2*scw->size-1; i++)printf("%-5d%-5d%-5d\n", ht[i].parent, ht[i].lchild, ht[i].rchild); }/* 打印编码表*/void print_hc(struct huffmantree *ht, struct size_cw *scw){int i;for (i = 1; i <= scw->size; i++)printf("%c\t%s\n", ht[i].ch, ht[i].code);}/* 将编码保存到文件中*/int code_to_file(struct huffmantree *ht, struct size_cw *scw){FILE *fpr;FILE *fpw;char s[500];int c;int i;printf("请输入保存编码的文件名\n");gets(s);fpw = fopen(s, "w");if (fpw == NULL)return -1;fpr = fopen("data", "r");if (fpw == NULL)return -1;while ((c = fgetc(fpr)) != EOF)for (i = 1; i <= scw->size; i++)if (ht[i].ch == c){fprintf(fpw, "%s", ht[i].code);break;}fclose(fpw);fclose(fpr);return 0;}/* 从文件中读取编码，并绎码*/void from_file_decode(struct huffmantree *ht, struct size_cw *scw) {FILE *fp, *fpout;char s[1000], filename[500];int i, c;int leave = scw->size;printf("请输入要进行译码的文件名\n");gets(s);printf("请输入你要保存译码的文件名\n");gets(filename);printf("\n");printf("-------------------------------------------\n");printf("---------------译码结果如下----------------\n");printf(" \n");fp = fopen(s, "r");fpout = fopen(filename, "wt");while (1){i = 2 * leave - 1;while (ht[i].lchild){if ((c = fgetc(fp)) == EOF)return;if (c == '0'){i = ht[i].lchild;}else{i = ht[i].rchild;}}printf("%c", ht[i].ch);fputc(ht[i].ch, fpout);}printf("\n");fclose(fp);fclose(fpout);}//主函数int main(){struct size_cw *scw;;struct huffmantree *ht;scw = create_scw(); //统计字符频度及字符类型if (scw == NULL)return 1;printf("\n");printf("-----------------字符频度表-----------------\n");print_cw(scw); //打印字符频度表printf("\n");ht = create_huffmantree(scw); //哈夫曼树printf("------------------哈夫曼树------------------\n");print_ht(ht, scw);printf("\n");printf("--------------------编码表-------------------\n");code_huffmantree(ht, scw); //将编码存进文件print_hc(ht, scw); //打印编码表printf("\n");code_to_file(ht, scw);char s[1000];while (1){printf("输入'q'退出，输入其他进行解码\n");gets(s);if (s[0] == 'q')break;from_file_decode(ht, scw);printf(" \n");printf("-------------------------------------------\n");printf("\n");}printf("\n");return 0;}。
数据结构哈夫曼树编码译码实验报告.【详细设计】具体代码实现如下：//HaffmanTree.h#include#include#includestruct HuffmanNode //哈夫曼树的一个结点{ int weight; int parent; int lchild,rchild; };class HuffmanTree //哈夫曼树{private: HuffmanNode *Node; //Node[]存放哈夫曼树char *Info; //Info[]存放源文用到的字符——源码，如'a','b','c','d','e'，此内容可以放入结点中，不单独设数组存放int LeafNum; //哈夫曼树的叶子个数，也是源码个数public: HuffmanTree(); ~HuffmanTree(); void CreateHuffmanTree(); /*在内存中建立哈夫曼树，存放在Node[]中。
让用户从两种建立哈夫曼树的方法中选择：1.从键盘读入源码字符集个数，每个字符，和每个字符的权重，建立哈夫曼树，并将哈夫曼树写入文件hfmTree中。
2.从文件hfmTree中读入哈夫曼树信息，建立哈夫曼树*/ void CreateHuffmanTreeFromKeyboard(); void CreateHuffmanTreeFromFile(); void Encoder(); /*使用建立好的哈夫曼树（如果不在内存，则从文件hfmTree中读入并建立内存里的哈夫曼树），对文件ToBeTran中的正文进行编码，并将码文写入文件CodeFile中。
ToBeTran的内容可以用记事本等程序编辑产生。
*/ void Decoder(); /*待译码的码文存放在文件CodeFile中，使用建立好的哈夫曼树（如果不在内存，则从文件hfmTree中读入并建立内存里的哈夫曼树）将码文译码，得到的源文写入文件TextFile中，并同时输出到屏幕上。
哈夫曼编译码程序简介哈夫曼编码是一种用于数据压缩的算法，通过根据字符出现的频率来构建一个最优的二叉树，将出现频率高的字符用较短的编码表示，从而实现对数据的高效压缩和解压。
本文将介绍如何使用Java编写一个简单的哈夫曼编译码程序。
我们将分为以下几个部分来讲解：1.哈夫曼编码原理及算法2.构建哈夫曼树3.生成哈夫曼编码表4.编码和解码哈夫曼编码原理及算法在介绍具体实现之前，我们先来了解一下哈夫曼编码的原理和算法。
原理哈夫曼编码是一种变长编码方式，即不同字符可以用不等长的二进制串表示。
它基于出现频率较高的字符使用较短的二进制串进行表示，而出现频率较低的字符使用较长的二进制串进行表示。
这样做可以大大减小数据在传输和存储过程中所占用的空间。
算法步骤1.统计字符频率：遍历待压缩的文本，统计每个字符出现的频率。
2.构建哈夫曼树：根据字符频率构建一个最小堆，每个节点包含字符和频率信息。
通过不断合并两个频率最小的节点，构建一棵哈夫曼树。
3.生成哈夫曼编码表：从根节点开始遍历哈夫曼树，左子树路径为0，右子树路径为1，将每个叶子节点对应的路径作为其编码。
4.编码和解码：使用生成的哈夫曼编码表对待压缩的文本进行编码，将每个字符替换为其对应的二进制串；使用哈夫曼树对编码后的二进制串进行解码。
构建哈夫曼树首先我们需要定义一个节点类来表示哈夫曼树中的节点：class Node implements Comparable<Node> {char character;int frequency;Node left;Node right;// 构造函数public Node(char character, int frequency, Node left, Node right) { this.character = character;this.frequency = frequency;this.left = left;this.right = right;}// 实现Comparable接口public int compareTo(Node other) {return this.frequency - other.frequency;}}然后我们可以利用优先队列（PriorityQueue）来构建最小堆，并通过合并两个频率最小的节点来构建哈夫曼树：import java.util.*;public class HuffmanTreeBuilder {public Node buildHuffmanTree(Map<Character, Integer> frequencyMap) {PriorityQueue<Node> minHeap = new PriorityQueue<>();// 将每个字符的频率作为节点的权重，构建最小堆for (Map.Entry<Character, Integer> entry : frequencyMap.entrySet()) { char character = entry.getKey();int frequency = entry.getValue();minHeap.offer(new Node(character, frequency, null, null));}// 合并两个频率最小的节点，直到堆中只剩下一个节点while (minHeap.size() > 1) {Node left = minHeap.poll();Node right = minHeap.poll();int combinedFrequency = left.frequency + right.frequency;minHeap.offer(new Node('\0', combinedFrequency, left, right));}return minHeap.poll();}}生成哈夫曼编码表生成哈夫曼编码表是通过遍历哈夫曼树来实现的。
实验二哈夫曼树及哈夫曼编码译码的实现实验二:哈夫曼树及哈夫曼编码译码的实现(验证性、4学时) 一、实验目的和要求构建哈夫曼树及哈夫曼编码，输出哈夫曼树及哈夫曼编码，完成编码与译码的算法。
(1)掌握树的有关操作算法2)熟悉树的基本存储方法 ((3)学习利用树求解实际问题二、实验内容和原理定义哈夫曼树的存储结构;输入要编码的字符权重，根据权重建立哈夫曼树，并进行编码，最后输出哈夫曼编码。
三、实验环境硬件:(1)学生用微机(2)多媒体教室或远程教学(3)局域网环境软件:(1)Windows XP中文操作系统 (2)Turbo C 3.0 四、算法描述及实验步骤1( 算法描述(1) 建立叶子结点——由于每个叶子结点都有一个权重值，构造哈夫曼树的过程中每个分枝节点的权重值等于两个孩子结点权重值的和，所以应该有一个权重域和指向左右孩子的两个指针域;(2) 另外在建成哈夫曼树之后，为了求得每个叶子结点的哈夫曼编码，需要走一条从叶子结点到根结点的路径，而译码的过程是从根结点出发到叶子的不断匹配的过程，所以既需要知道孩子结点的信息，也需要知道双亲结点的信息，应该再有一个指向双亲结点的指针域。
(3) 构建哈夫曼编码——在已建好的哈夫曼树中从每个叶子结点开始沿双亲链域回退到根结点，每回退一步走过哈夫曼树的一个分枝得到一个哈夫曼编码值;由于每个叶子结点的哈夫曼编码是从根就诶点到相应叶子结点的路径上各分枝代码所组成的0、1序列，所以先得到的分枝代码为说求编码的低位码而后得到的为高位码。
2( 算法流程图构建哈夫曼树算法流程哈夫曼编码算法流程3( 代码#include<stdio.h>#define maxvalue 10000//定义最大权值常量#define maxnodenumber 100//定义结点最大数目常量 typedef struct{int weight;int parent,lchild,rchild; }htnode;typedef htnode *huffmantree;//定义哈夫曼树类型 htnodeht[maxnodenumber]; //定义静态三叉链表存储区数组#define maxbit 10//定义哈夫曼编码的最大长度 typedef struct//定义保存一个叶子结点哈夫曼编码的结构 {int bit[maxbit];//哈夫曼编码域为一维数组int start;//开始位置域为整型}hcodetype;//定义哈夫曼编码类型hcodetype cd[maxnodenumber];//定义存放哈夫曼编码的数组cd void crthuffmantree(int n);//建立哈夫曼树void gethuffmancode(int n);//哈夫曼编码void main (){int nodenum;printf("inputnodenum:"); scanf("%d",&nodenum);crthuffmantree(nodenum); gethuffmancode(nodenum); }void crthuffmantree(int n)//该算法对n个叶子结点建立哈夫曼树，权重值由键盘逐个输入{int i,j,m1,m2,k1,k2;//定义局部变量for(i=0;i<2*n-1;i++)//数组ht初始化{ht[i].weight=0;//权重初始化为0ht[i].parent=-1;//3个指针域初始化为-1，即NULL ht[i].lchild=-1;ht[i].rchild=-1;}for (i=0;i<n;i++)//读入n个叶子结点的权重值scanf("%d",&ht[i].weight); for(i=0;i<n-1;i++)//控制n-1趟生成新结点构造哈夫曼树 {m1=maxvalue;//预置最小权值变量为最大权值 m2=maxvalue;//预置次小权值变量为最大权值 k1=0;k2=0;//预置最小和次小权值结点位置为下标0处for (j=0;j<n+i;j++)//控制一趟中找处最小权值的结点if(ht[j].parent==-1&&ht[j].weight<m1){m2=m1;k2=k1;//若第j个结点权小于当前最小的m1改为次小的m1=ht[j].weight;k1=j;//并记下新的当前最小权值及位置}elseif(ht[j].parent==-1&&ht[j].weight<m2){m2=ht[j].weight;k2=j;}//否则若小于当前次小的m2则更新m2及其位置ht[k1].parent=n+i;//修改最小权值结点的双亲为刚生成的新结点ht[k2].parent=n+i;//修改次小权值结点的双亲刚好生成的新结点ht[n+i].weight=ht[k1].weight+ht[k2].weight;//填新生成结点的权重值ht[n+i].lchild=k1;//新生成结点的左孩子指针指向k1ht[n+i].rchild=k2;//新生成结点的右孩子指针指向k2}}void gethuffmancode(int n) /*对具有n个叶子结点的哈夫曼树ht,求所有叶子结点的哈夫曼编码并输出*/{int i,j,c,p; /*定义局部变量*/for(i=0;i<n;i++) /*定义存放哈夫曼编码的数组cd*/ {c=i;j=maxbit; /*为求一个结点的哈夫曼编码初始化c和j*/ do{j--; /*j指向bit中存放编码位的正确位置*/ p=ht[c].parent; /*p指向c 的双亲结点*/if(ht[p].lchild==c) /*如果c是p的左孩子*/cd[i].bit[j]=0; /*编码位上赋0*/elsecd[i].bit[j]=1; /*否则c是p的右孩子，编码位上赋1*/ c=p; /*更新c为p,为求下一个编码位做准备*/ }while(ht[p].parent!=-1); /*当未到达根结点继续做do循环*/ cd[i].start=j; /*求完一个叶子结点的哈夫曼编码时，记下编码开始位置*/}for(i=0;i<n;i++) /*输出n个叶子结点的哈夫曼编码*/{for(j=cd[i].start;j<maxbit;j++) /*逐位输出一个编码*/printf("%d",cd[i].bit[j]);printf("\n"); /*输出完一个哈夫曼编码后换行*/ }}五、调试过程一次编译二次编译三次编译六、实验结果七、总结(1) 深刻体会构建哈夫曼树的整个过程，对整体有个总的理解; (2) 复习以前所学C语言的一些语法，例如:for循环，if循环，while循环 (3) 理解哈夫曼的编码过程，编码思想(4) 此程序的不足之处在于在进行哈夫曼编码时未能对字符进行编制，有待改进。
