(完整word版)哈夫曼编码和译码的设计与实现

《数据结构》哈夫曼编码与译码实验报告题目：哈夫曼编码与译码班级：xxxx学号：xxxxxxxxxxx姓名：xxx完成时间：2012年12月19日一、程序总体结构主程序main显示系统时间showtime() 给用户提供选择方式chioce1()显示界面告诉用户程序名称show()打开文件进行加密openfile()退出程序输入电文进行加密input()将输入(文件中)的电文进行哈夫曼编码CrtHuffmanCode(ht,hc,n)统计输入(文件中)字母的出现频率CrW(data,w,count)【fcount(alldata,data,count)】输出每一个字母所对应的哈夫曼编码Printf(hc,n,data,alldata,count)将输入(文件中)的电文创建成哈夫曼树CrtHuffmantree(ht,w,n)对输入(文件中)的文字进行哈夫曼加密showall(hc,alldata,count,data,n)下面有几个不同的程序供选着参考：程序源代码:#include <iostream.h>#include <fstream.h>#include <string.h>#include <stdlib.h>typedef struct{char data;int weight;int parent,lchild,rchild;}HTNode,*HuffmanTree;typedef char * * HuffmanCode;void Select(HuffmanTree &HT,int n,int m){HuffmanTree p=HT;int tmp;for(int j=n+1;j<=m;j++){int tag1,tag2,s1,s2;tag1=tag2=32767;for(int x=1;x<=j-1;x++){ if(p[x].parent==0&&p[x].weight<tag1){ tag1=p[x].weight;s1=x;}}for(int y=1;y<=j-1;y++){ if(p[y].parent==0&&y!=s1&&p[y].weight<tag2){ tag2=p[y].weight;s2=y;}}if(s1>s2) //将选出的两个节点中的序号较小的始终赋给s1 { tmp=s1; s1=s2; s2=tmp;}p[s1].parent=j;p[s2].parent=j;p[j].lchild=s1;p[j].rchild=s2;p[j].weight=p[s1].weight+p[s2].weight;}}void HuffmanCoding(HuffmanTree &HT,int n,char *w1,int*w2) {int m=2*n-1;if(n<=1) return;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); HuffmanTree p=HT;for(int i=1;i<=n;i++){ p[i].data=w1[i-1];p[i].weight=w2[i];p[i].parent=p[i].lchild=p[i].rchild=0;}for(;i<=m;i++){ p[i].weight=p[i].parent=p[i].lchild=p[i].rchild=0; }Select(HT,n,m);ofstream outfile; //生成hfmTree文件outfile.open("hfmTree.txt",ios::out);for (i=1;i<=m;i++){outfile<<HT[i].weight<<"\t"<<HT[i].parent<<"\t"<<HT[i].lchild<<"\t"<<HT[i].rchil d<<"\t"<<endl;}outfile.close();cout<<"初始化结果已保存在hfmTree文件中\n";}void ToBeTree() //将正文写入文件ToBeTree中{ofstream outfile;outfile.open("ToBeTree.txt",ios::out);outfile<<"THIS PROGRAM IS MYFAVORITE";outfile.close();}void Encoding(HuffmanTree &HT,int n) //编码{HuffmanCode HC;HC=(HuffmanCode)malloc((n+1)*sizeof(char *));char *cd;cd=(char *)malloc(n*sizeof(char));cd[n-1]='\0';for(int k=1;k<=n;k++){ int start=n-1;for(int c=k,f=HT[k].parent;f!=0;c=f,f=HT[f].parent){ if(HT[f].lchild==c) cd[--start]='0';else cd[--start]='1';}HC[k]=(char *)malloc((n-start)*sizeof(char));strcpy(HC[k],&cd[start]);}cout<<"输出哈夫曼编码:"<<endl;for(int h=1;h<=n;h++) //输出编码{ cout<<HT[h].data<<":";cout<<HC[h];cout<<" ";if (h%8==0) cout<<endl;}cout<<endl<<"输出正文编码:"<<endl;ToBeTree();//读取TOBETREE文件里的正文，并进行编码fstream infile;infile.open("ToBeTree.txt",ios::in);char s[80];while(!infile.eof()){infile.getline(s,sizeof(s));}infile.close();fstream outfile;outfile.open("CodeFile.txt",ios::out);int count=0;for (h=0;s[h]!='\0';h++){ for(k=1;k<=n;k++)if (s[h]==HT[k].data){ cout<<HC[k];cout<<" ";count++;outfile<<HC[k];break;}if (count%9==0) cout<<endl; //每输出7个换行}outfile.close();cout<<"\n编码结果已保存在文件CodeFile中."; cout<<endl;}void Decoding(HuffmanTree &HT,int n) //译码{int f=2*n-1;fstream infile;infile.open("CodeFile.txt",ios::in);char s[1000];while(!infile.eof()){infile.getline(s,sizeof(s));}infile.close();int i=0;int j=0;fstream outfile;outfile.open("TextFile.txt",ios::out);while(s[i]!='\0')while(HT[f].lchild!=0)//以f对应的节点的左孩子的值==0作为结束{if (s[j]=='0') f=HT[f].lchild;else f=HT[f].rchild;j++;}i=j;cout<<HT[f].data;outfile<<HT[f].data;}outfile.close();cout<<"\n译码结果已保存在文件TextFile中.";cout<<endl;}void Print() //印代码文件{ int count=0;fstream infile;infile.open("CodeFile.txt",ios::in);char s[1000];while(!infile.eof()){infile.getline(s,sizeof(s));for(int i=0;s[i]!='\0';i++){ cout<<s[i];count++;if (count%50==0) cout<<endl; //在终端上每行显示50个代码}}infile.close();cout<<endl;}char menu() //菜单函数{ cout<<"功能菜单如下:"<<endl;cout<<"* * * * * * * * * * * * * * * * * * * * *"<<endl;cout<<" I:初始化(Initialization) "<<endl;cout<<" E:编码(Encoding) "<<endl;cout<<" D:译码(Decoding) "<<endl;cout<<" P:印代码文件(Print) "<<endl;cout<<" Q:退出(Exit) "<<endl;cout<<"* * * * * * * * * * * * * * * * * * * * *"<<endl;cout<<"请输入功能字符:";char ch;cin>>ch;return ch;}{ int n;int Array[100];char cArray[100];HuffmanTree HT;cout<<"输入n个字符:";cin.getline(cArray,100);n=strlen(cArray);cout<<"一共"<<n<<"个字符.\n";cout<<"依次输入各个字符的权值:"<<endl;for (int i=1;i<=n;i++) cin>>Array[i];int tag;char x=menu();while(1){ switch (x){case 'I':HuffmanCoding(HT,n,cArray,Array);break; case 'E':Encoding(HT,n);break;case 'D':Decoding(HT,n);break;case 'P':Print();break;case 'Q':tag=0;cout<<"结束"<<endl;break; default:cout<<"你输入错误!"<<endl;}if(tag==0) break;cout<<"y(继续) or n(退出)"<<endl;char ch;cin>>ch;if (ch=='y'){ cout<<"请输入功能字符:";char c;cin>>c;x=c;}else exit(1);}}源程序：#include<iostream>#include<fstream>#include<iomanip>#include<vector>using namespace std;typedef struct //节点结构{char data; //记录字符值long int weight; //记录字符权重unsigned int parent,lchild,rchild;}HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树typedef char * *HuffmanCode; //动态分配数组存储哈夫曼编码表void Select(HuffmanTree &HT,int i,int &s1,int &s2) //在HT[1...t]中选择parent不为0且权值最小的两个结点，其序号分别为s1和s2{s1=0;s2=0;int n1=30000,n2=30000;for(int k=1;k<=i;k++){if(HT[k].parent==0){if(HT[k].weight<n1){n2=n1; n1=HT[k].weight;s2=s1; s1=k;}elseif(HT[k].weight<n2){n2=HT[k].weight;s2=k;}}}}void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int n)//将要编码的字符串存入空树中{ifstream fin1("zifu.txt");ifstream fin2("weight.txt");if(n<=1)return;int m=2*n-1;int i;HT=new HTNode[m+1];char *zifu;int *weight;zifu= new char[n+1];weight=new int[n+1];for(i=1;i<=n;i++)//将待编码的字符放在zifu数组中{char ch;ch=fin1.get();zifu[i]=ch;}for(i=1;i<=n;i++)//将带编码字符对应的权值放在weight数组中{fin2>>weight[i];}for( i=1;i<=n;i++){HT[i].data=zifu[i];HT[i].weight=weight[i];}for(i=n+1;i<=m;i++){HT[i].data='@';}for(i=1;i<=m;i++){HT[i].parent=HT[i].lchild=HT[i].rchild=0;}for(i=n+1;i<=m;++i){int s1,s2;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=(HuffmanCode)malloc((n+1)*sizeof(char*));开辟一个求编码的工作空间char *cd;cd=(char *)malloc(n*sizeof(char));//开辟空间存放权值cd[n-1]='\0';for(i=1;i<=n;i++){int start=n-1;int c,f;for( c=i, f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到根逆向求编码{if(HT[f].lchild==c)cd[--start]='0';//若是左孩子编为'0'elsecd[--start]='1';//若是右孩子编为'1'}HC[i]=(char *)malloc((n-start)*sizeof(char)); //为第i个编码分配空间strcpy(HC[i],&cd[start]);}delete []cd; //释放工作空间}void printHuffmanTree(HuffmanTree HT,int n) //显示有n个叶子结点的哈夫曼树的编码表{ ofstream fout("hfmtree.txt"); //将对应字符的的哈弗曼树存入cout<<"NUM"<<" "<<"data"<<" "<<"weight"<<" "<<"parent"<<" "<<"lchild"<<" "<<"rchlid"<<endl;for(int i=1;i<=2*n-1;i++){fout<<HT[i].weight<<setw(3)<<HT[i].parent<<setw(3)<<HT[i].lchild<<setw(3) <<HT[i].rchild<<endl;cout<<i<<setw(5)<<HT[i].data<<setw(3)<<HT[i].weight<<setw(3)<<HT[i].pare nt<<setw(3)<<HT[i].lchild<<setw(3)<<HT[i].rchild<<endl;}}void printHuffmanCoding(HuffmanTree HT,HuffmanCode HC,int n)//输出字符的对应哈弗曼编码并存入code.txt文件{cout<<"Huffman code is:"<<endl;ofstream fout("code.txt");for(int i=1;i<=n;i++){cout<<HT[i].data<<" --> ";cout<<(HC[i])<<endl;fout<<(HC[i])<<endl;}}void code_file(HuffmanTree HT,HuffmanCode HC,int n)//对文件tobetran.txt进行编码，并将编码存入codefile文件中{ifstream fin("tobetran.txt");ofstream fout("codefile.txt");vector<char> a;char ch;while((ch=fin.get())!='*')a.push_back(ch);cout<<"待编码的字符串为：";for(int k=0;k<a.size();k++)cout<<a[k];cout<<endl;cout<<"\n编码结果:"<<endl;for(int i=0;i<a.size();i++){for(int j=1;j<=n;j++){if(a[i]==HT[j].data){fout<<HC[j];break;}}}fin.close();fout.close();}void Decoding(HuffmanTree HT,HuffmanCode HC,int n)//打开codefile文件并对文件内容进行译码{int const m=2*n-1;ifstream fin("codefile.txt");ofstream fout("textfile.txt");vector<char> a;for(char c;fin>>c;)a.push_back(c);int count=0;for(int k=0;k<a.size();k++){cout<<a[k];count++;if(count%50==0)cout<<endl;}int i=0;int p; //用p来记住m的值cout<<endl;cout<<"\n译码结果："<<endl;while(i<a.size()){p=m; //从哈弗曼数的根开始遍历while(HT[p].lchild){if(a[i]=='1')p=HT[p].rchild;elsep=HT[p].lchild;i++;}fout<<HT[p].data;cout<<HT[p].data;}}void main(){int n;cout<<"输入权值个数："; //设置权值数值cin>>n;printf("\n");HuffmanTree HT; //哈夫曼树HTHuffmanCode HC; //哈夫曼编码表HCHuffmanCoding(HT,HC,n); //进行哈夫曼编码printHuffmanCoding(HT,HC,n); //显示编码的字符printf("\n");code_file(HT,HC,n); //显示要编码的字符串，并把编码值显示出来Decoding(HT,HC,n); //译码并显示译码后的字符串printf("\n\n\n");system("pause");}主要程序代码://HuffmanCode1.h#ifndef HUFFMAMCODE_H#define HUFFMAMCODE_H#include<iostream>#include<fstream>using namespace std;struct HuffmanNode //定义哈夫曼树各结点{int weight;int parent;int lchild,rchild;int flag;};class HuffmanCode1 //哈夫曼编码类{public:char Info[100];int Start;char Leaf;};class HuffmanTree1 //建立哈夫曼树类{private:HuffmanNode *Node;public:int f;HuffmanCode1 *hf;HuffmanTree1();~HuffmanTree1();void TranslatedCode();void CodeHuf(HuffmanNode a[],HuffmanCode1 b[],int n);void CreateHfmTree(char Str[],int m[],int n);void TransCode(HuffmanCode1 b[],int n) ;void TranslateArtcle(HuffmanCode1 b[],int n) ;};#endif //HUFFMAMCODE_HHuffmanCode.cpp#include "iostream"#include<stdio.h>#include "math.h"#include "stdlib.h"#include"HuffmanCode1.h"#include<string>using namespace std;#define MAXDA TA 10000 //最长字符串#define MAXSIZE 150 //最多子叶数//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// ////////////////第一部分功能（W）实现的代码$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ HuffmanTree1::HuffmanTree1(){ Node=NULL; } //将树结点初始化为空HuffmanTree1::~HuffmanTree1(){ delete[] Node; } //释放结点空间void HuffmanTree1::CreateHfmTree(char Str[],int m[],int n)//建立哈夫曼树{int i,j,m1,m2,x1,x2;HuffmanNode *HfmNode=new HuffmanNode[2*n-1];HuffmanCode1 *HfmCode=new HuffmanCode1[n];for(i=0;i<2*n-1;i++){HfmNode[i].weight=0;HfmNode[i].parent=0;HfmNode[i].flag=0;HfmNode[i].lchild=-1;HfmNode[i].rchild=-1;}for(i=0;i<n;i++){HfmNode[i].weight=m[i];HfmCode[i].Leaf=Str[i];}for(i=0;i<n-1;i++){m1=m2=32767;x1=x2=0;for(j=0;j<n+i;j++){if(HfmNode[j].weight<=m1&&HfmNode[j].flag==0){m2=m1;x2=x1;m1=HfmNode[j].weight;x1=j;}else if(HfmNode[j].weight<=m2&&HfmNode[j].flag==0){m2=HfmNode[j].weight;x2=j;}}HfmNode[x1].parent=n+i;HfmNode[x2].parent=n+i;HfmNode[x1].flag=1;HfmNode[x2].flag=1;HfmNode[n+i].weight=HfmNode[x1].weight+HfmNode[x2].weight;HfmNode[n+i].lchild=x1;HfmNode[n+i].rchild=x2;}CodeHuf(HfmNode,HfmCode,n);TransCode(HfmCode,n);//TranslateArtcle(HfmCode,n);hf=HfmCode; f=n;}void HuffmanTree1::CodeHuf(HuffmanNode a[],HuffmanCode1 b[],int n) //对哈夫曼树进行编码{HuffmanCode1 Hfd;int c,p;for(int i=0;i<n;i++){Hfd.Start=n-1;c=i;p=a[c].parent;while(p!=0){if(a[p].lchild==c)[Hfd.Start]='0';else[Hfd.Start]='1';Hfd.Start--;c=p;p=a[c].parent;}printf("%c :",b[i].Leaf);for(int j=Hfd.Start+1;j<n;j++){b[i].Info[j]=[j];printf("%c",[j]);}printf("\n");b[i].Start=Hfd.Start;}}void HuffmanTree1::TransCode(HuffmanCode1 b[],int n) //对文章进行翻译并保存{ifstream ifs("WData.txt");ofstream ofs("WCode.txt");char s[1000];int t=0;char ch;cout<<"************************************************************** *****************"<<endl;printf("报文的编码为：\n");while(ifs.get(ch)){if(ch!='\n')s[t]=ch;for(int i=0;i<n;i++){if(s[t]==b[i].Leaf)for(int j=b[i].Start+1;j<n;j++){printf("%c",b[i].Info[j]);ofs<<b[i].Info[j];}}t++;}printf("\n");printf("报文的编码已经保存在WCode.txt中\n");cout<<"*********************************************************** ********************"<<endl;}void HuffmanTree1::TranslateArtcle(HuffmanCode1 b[],int n) //将所译的码翻译成文章并保存{int t=0;ifstream ifs("WCode.txt");ofstream ofs("TransWData.txt");string s;getline(ifs,s);for(t=0;s[t]!='\0';t++);int l=0;int j=0;printf("报文的译码结果为：\n");while(l<t){while(j<n){int hu=b[j].Start+1;int k=0;while(hu<n){if(s[l]==b[j].Info[hu]){l++;hu++;k++;}else{break;}}if(hu==n){printf("%c",b[j].Leaf);ofs<<b[j].Leaf;j=0;break;}else{l=l-k;j++; continue;}}}printf("\n");printf("译码的结果已经保存到TransWData.txt中\n");cout<<"*********************************************************** ********************"<<endl;}void HuffmanTree1::TranslatedCode(){ifstream ifs("WData.txt");char str[1000];char Str[100];int i=0,j,m[100],h,k=0;int n=0;cout<<"*********************************************************** ********************"<<endl;printf("文件中提取的文章字符串是：\n");char ch;while(ifs.get(ch)){printf("%c",ch);if(ch!='\n'){str[n++]=ch;}}printf("\n");printf("字符串中共含有字符%d个\n",n);for(i=0;i<n;i++){j=0;h=0;while(str[i]!=str[j])j++;if(j==i){Str[k]=str[i];printf("字符%c出现",Str[k]);}elsecontinue;for(j=i;j<n;j++){if(str[i]==str[j])h++;}printf("%d次\n",h);m[k]=h;k++;}cout<<"*********************************************************** ********************"<<endl;printf("字符串中字符种类有%d种\n",k);cout<<"*********************************************************** ********************"<<endl;printf("每个字符对应的哈夫曼编码是：\n");CreateHfmTree(Str,m,k);cin.get();// printf("\n");}//main.cpp//#include"HuffmanCode1.h"//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /////////////////第二部分功能实现的代码$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ typedef struct //哈弗曼树节点的结构体{char info; //关联字符信息unsigned int weight; //每个节点的权职unsigned int parent, lchild, rchild;}HTNode,*HuffmanTree;typedef char **HuffmanCode; //存储哈弗曼编码void Select(HuffmanTree HT, int j,int &s1,int &s2){ //选择双亲节点为0，并且最小的两个子叶节点int i=1,m;while(HT[i].parent!=0)i++; //找第一个双亲节点为0的子叶结点for(s2=s1=i;i<j;i++){ /保证s1中的权值最小，s2次小if(HT[i].parent==0 && HT[i].weight<HT[s1].weight){s2=s1;s1=i;}else if(HT[i].parent==0 && HT[i].weight>=HT[s1].weight &&HT[i].weight<=HT[s2].weight)s2=i;while(HT[i].parent==0 && s1==s2){m=i;m++;while(HT[m].parent!=0)m++;s2=m;}}}void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n, char *info){ //哈弗曼编码int i,m;HuffmanTree p;if(n<1) return;m = 2*n-1;HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode));for(p=HT+1,i=1;i<=n;++i,++p,++w,++info){ //初始化所有已存在的子叶信息p->info = *info;p->weight = *w;p->parent = 0;p->lchild = 0;p->rchild = 0;}//forfor(; i<=m;++i,++p){ //构造所需要的过度根节点p->weight = 0;p->parent = 0;p->lchild = 0;p->rchild = 0;}//forfor(i=n+1;i<=m;++i){ //建立哈弗曼树int s1,s2;Select(HT,i-1,s1,s2);HT[s1].parent =i;HT[s2].parent =i;HT[i].lchild = s2;HT[i].rchild = s1;HT[i].weight = HT[s1].weight+HT[s2].weight;}//for//哈弗曼编码HC = (HuffmanCode)malloc((n+1)*sizeof(char *));char* cd = (char*)malloc(n*sizeof(char));cd[n-1] = '\0';for(i=1;i<=n;++i){int f;unsigned int c;int 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';}HC[i]=(char*)malloc((n-start)*sizeof(char));strcpy(HC[i], &cd[start]);}//forfree(cd);}//HuffmanCoding//Y功能实现输出并保存字符串的二进制编码void CheckCoding(HuffmanTree HT, HuffmanCode HC, char *strcheck, int m,int k) { ofstream ofs("BCode.txt"); //查询哈弗曼编码信息int p;for(int i=0; i<m; i++){for(int j=1; HT[j].info != strcheck[i]; j++);cout<<HC[j]; //输出并保存字符串的二进制编码ofs<<HC[j];}cout<<endl;cout<<"字符串的二进制编码已经保存在“BCode.txt”中"<<endl;//cout<<"译码翻译得到的文章已保存在“Data.txt”中"<<endl;cout<<"************************************************************** *****************"<<endl;cout<<"各字符对应的编码为:"<<endl; //输出各字符对应的哈夫曼编码for( p=1;p<=k;p++){cout<<HT[p].info <<": "<<HC[p]<<endl;}}//CheckCoding//对键盘输入的二进制代码进行译码void HuffmanTranslateCoding(HuffmanTree HT, int n,char*c){ ofstream ofs("TransBData.txt"); //译码过程int m=2*n-1;int i,j=0;cout<<"译码翻译得到的文章已保存在“TransBData.txt”中"<<endl;cout<<"译码翻译得到的文章为:";while(c[j]!='\0'){i=m;while(HT[i].lchild && HT[i].rchild){if(c[j]=='0')i=HT[i].lchild;else if(c[j]=='1')i=HT[i].rchild;j++;}cout<<HT[i].info; //翻译成字符串并输出和保存ofs<<HT[i].info;}}//译码过程、、对"BCode.txt"的编码进行译码void HuffmanTranslateCoding2(HuffmanTree HT, int n){ ifstream ifs("BCode.txt");ofstream ofs("TransBData2.txt");string c;int m=2*n-1;int i,j=0;getline(ifs,c);cout<<"译码翻译得到的文章已保存在“TransBData2.txt”中"<<endl;cout<<"译码翻译得到的文章为:";while(c[j]!='\0'){i=m;while(HT[i].lchild && HT[i].rchild){if(c[j]=='0')i=HT[i].lchild;else if(c[j]=='1')i=HT[i].rchild;j++;}cout<<HT[i].info; //翻译成字符串并输出和保存ofs<<HT[i].info;}}void Menushow(){cout<<"||******************************************************************** ****||"<<endl;cout<<" || HuffmanCode and HUffmanTranslate System ||"<<endl;cout<<" || ***********哈夫曼编码/译码系统************* ||"<<endl;cout<<" || *************欢迎使用本系统**************** ||"<<endl;cout<<" || 东北电力大学信息工程学院计机093班兴趣小组||"<<endl;cout<<" || 制作人：范辉强（组长）李哲周兴宇||"<<endl;cout<<"||******************************************************************** ****||"<<endl;cout<<" ||在本系统中您可以进行如下操作：||"<<endl;cout<<" ||第一部分功能：||"<<endl;cout<<" || A :从文件提取字符串，然后对提取的字符串进行编码||"<<endl;cout<<" || B :根据W操作对“WCode.txt”里的二进制编码进行译码||"<<endl;cout<<" ||第二部分功能：||"<<endl;cout<<" || C :对您输入的字符串进行编码||"<<endl;cout<<" || D:对BCode.txt里的编码进行译码||"<<endl;cout<<" || E :对您输入的二进制编码进行译码||"<<endl;cout<<" ||第三部分功能：||"<<endl;cout<<" || F :退出本系统||"<<endl;cout<<"||******************************************************************** ****||"<<endl;cout<<" ||温馨提示：||"<<endl;cout<<" || 执行A，请将您的数据存储在同目录下名为“WData”文本文档里||"<<endl;cout<<" || 在执行C操作时务必在您输入的字符串后加上“#”||"<<endl;cout<<" || B与A是对应的B在A后运行||"<<endl;cout<<" || D/E与C是对应的，即B/C是根据C来进行译码的||"<<endl;cout<<" || 译码D/E应在编码C后才能进行||"<<endl;cout<<" ||*********************** Copyright by FanFan ********************||"<<endl;}//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// ///main().cppint main(){int n=0,i=0,k=0,j,h,*w;FILE *fp;char ch2,str[MAXDA TA],choose,name[]="BData.txt";w=new int[MAXSIZE];char *info;char *strcheck=str;info=new char[MAXSIZE];char *ch=new char[MAXSIZE];HuffmanTree HT=new HTNode[MAXSIZE];HuffmanCode HC=NULL;HuffmanTree1 HuffmanNode;Menushow();while(1){cout<<endl;cout<<"************************************************************** *****************"<<endl;cout<<"*********************************************************** ********************"<<endl;cout<<"请输入您要进行的操作（W/F/B/C/Y/T)(不区分大小写)："<<endl;cin>>choose;cout<<"************************************************************** *****************"<<endl;switch(choose){case 'A':case 'a':HuffmanNode.TranslatedCode();break;case 'B':case 'b':HuffmanNode.TranslateArtcle(HuffmanNode.hf,HuffmanNode.f);case 'D':case 'd':HuffmanTranslateCoding2( HT,n);break;case 'E':case 'e'://进行译码操作cout<<"请您输入您要编译的二进制编码: "<<endl;cin>>ch;HuffmanTranslateCoding(HT,n,ch);break;case 'T':case 't'://退出系统return 0;case 'C':case 'c'://进行编码操作cout<<"请输入您要编码的字符串："<<endl;//从键盘输入字符串存放在字符数组str[1000]中/*if ((fp=fopen(name,"w"))==NULL){cout<<"cannot open file"<<endl;exit(0);}*/fp=fopen(name,"w");ch2=getchar();//接收上一次键盘输入的换行符ch2=getchar();while(ch2!='#'){fputc(ch2,fp);str[n++]=ch2;putchar(str[n-1]);ch2=getchar();}putchar(10);fclose(fp);cout<<endl;cout<<"输入的数据已经保存在“BData.txt”中"<<endl;cout<<"*******************************************************************************"<<endl;cout<<"字符串中共含有字符"<<n<<"个"<<endl;cout<<"*********************************************************** ********************"<<endl;for(i=0;i<n;i++) // 统计从键盘输入的字符串的信息{j=0;h=0;while(str[i]!=str[j])j++;if(j==i){info[k]=str[i];cout<<"字符"<<info[k]<<"出现";}elsecontinue;for(j=i;j<n;j++){if(str[i]==str[j])h++;}cout<<h<<"次"<<endl;w[k]=h;k++;}cout<<"************************************************************** *****************"<<endl;cout<<"字符串中字符种类有"<<k<<"种"<<endl;cout<<"************************************************************** *****************"<<endl;HuffmanCoding( HT, HC, w, n,info);//对输入的字符串进行编码*strcheck=str[0];cout<<"您输入的字符串编码为："<<endl;CheckCoding(HT,HC,strcheck,n,k);break;default:cout<<"对不起，您的输入不正确！请重新输入"<<endl;}//switch}//while}//main程序清单.cpp#include<iostream>#include<stdio.h>#include<stdlib.h>#include<string>#include"Hh1.h"using namespace std;FILE * f1=fopen("d:\\pra1.txt","r");FILE * f2=fopen("d:\\pra2.txt","w");FILE * f3=fopen("d:\\pra4.huf","w");int main(){init(SN); //初始化字符数据库// input(f1); //读入初始文件的字符//for(int i=0;forest[i]!=NULL;i++)cout<<forest[i]->c<<":"<<forest[i]->weight<<endl; //输出字符及出现次数// cout<<"出现字符种类"<<count<<endl; //输出字符种类//HFM huffman(count); //创建哈夫曼树实例// huffman.creat(); //创建哈夫曼树// count=0;huffman.hufcode(); //哈夫曼编码，此时为逆向//exchange(); //调整首尾对调哈夫曼编码// huffman.savewithhufcode(f1,f2); //用哈夫曼编码存储原文件//cout<<endl;cout<<"1.查看哈夫曼编码"<<endl;cout<<"2.哈夫曼解码"<<endl;cout<<"3.查看压缩率"<<endl;int choice;cin>>choice;while(choice>=1&&choice<=3){switch(choice){case 1:{for(i=0;hufNode[i].sig!=NULL;i++){cout<<"字符"<<hufNode[i].sig->c<<"的哈夫曼编码:"; //输出哈夫曼编码//for(int j=0;j<hufNode[i].size;j++)cout<<hufNode[i].code[j];cout<<endl;}cout<<"最大列数:"<<huffman.maxc()<<endl;break;}case 2:{fclose(f2);f2=fopen("d:\\pra2.txt","r");huffman.hufdecode(f2,f3); //哈夫曼解码//cout<<endl;break;}case 3:{compress(); //查看压缩情况//cout<<endl;}}cout<<"1.查看哈夫曼编码"<<endl;cout<<"2.哈夫曼解码"<<endl;cout<<"3.查看压缩率"<<endl;cin>>choice;}cout<<"*谢谢使用*"<<endl; //退出操作//return 0;}.h#include<iostream>using namespace std;struct signode{ //signode节点，哈夫曼树节点//char c; //字符//int weight; //权重//bool b; //文章中是否出现//。

《数据结构》课程设计说明书题目哈夫曼编码与译码学号1267159206姓名张燕斌指导教师康懿日期2014.01。

02任务书目录第一章需求分析 (5)第二章总体设计 (6)第三章抽象数据类型定义 (7)3。

1 LinkList抽象数据类型的设计 (7)3.2 HuffmanTree抽象数据的设计 (7)第四章详细设计..。

...。

..。

....。

.....。

.。

.。

..。

.。

....。

.。

..。

..。

.。

.。

.。

.。

..。

....。

....。

.。

..。

...。

...。

7第五章测试 (10)第六章总结 (11)附录：程序代码 (12)第一章需求分析哈夫曼编码是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。

哈弗曼编码使用一张特殊的编码表将源字符（例如某文件中的一个符号)进行编码。

这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码,这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的)。

赫夫曼编码的应用很广泛,利用赫夫曼树求得的用于通信的二进制编码称为赫夫曼编码。

树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码,指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是赫夫曼编码。

哈弗曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串。

第二章总体设计（1）输入一个字符串用结构体链表存储字符串中出现的不同字符及其出现的次数。

（2）定义赫夫曼数的结点结构体，把不同的字符及其在字符串中出现的次数作为叶子结点的元素及其权值，统计叶子结点的个数n，开辟可以存储2*n个结点的顺序表，来赫夫曼树的各个结点,然后按照一定的规则构造赫夫曼树。

（3）开辟一个可以存储叶子结点元素及指向存储其赫夫曼编码链表的指针的顺序表，然后从叶子结点开始向上访问，是左孩子的把“0”接进链表是右孩子的把“1”接进链表,直到根结点，然后把叶子结点的元素及存储其赫夫曼链表的头指针读入顺序表,直到把所有的叶子结点的元素及指向存储其赫夫曼编码链表的头指针读入顺序表，这样得到的赫夫曼编码是倒序的。

目录目录 (1)1 课程设计的目的和意义 (3)2 需求分析 (5)3 系统设计 (6)（1)设计思路及方案 (6)（2)模块的设计及介绍 (6)(3)主要模块程序流程图 (9)4 系统实现 (14)（1）主调函数 (14)(2)建立HuffmanTree (14)(3）生成Huffman编码并写入文件 (18)（4)电文译码 (19)5 系统调试 (22)小结 (25)参考文献 (26)附录源程序 (27)1 课程设计的目的和意义在当今信息爆炸时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。

哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。

哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。

树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0"码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1"的序列作为和各个对应的字符的编码，这就是哈夫曼编码。

通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。

电报通信是传递文字的二进制码形式的字符串。

但在信息传递时,总希望总长度尽可能最短，即采用最短码。

作为软件工程专业的学生，我们应该很好的掌握这门技术。

在课堂上，我们能过学到许多的理论知识，但我们很少有过自己动手实践的机会！课程设计就是为解决这个问题提供了一个平台。

在课程设计过程中,我们每个人选择一个课题，认真研究，根据课堂讲授内容，借助书本，自己动手实践。

这样不但有助于我们消化课堂所讲解的内容，还可以增强我们的独立思考能力和动手能力；通过编写实验代码和调试运行，我们可以逐步积累调试C程序的经验并逐渐培养我们的编程能力、用计算机解决实际问题的能力。

在课程设计过程中,我们不但有自己的独立思考，还借助各种参考文献来帮助我们完成系统。

更为重要的是，我们同学之间加强了交流，在对问题的认识方面可以交换不同的意见.同时,师生之间的互动也随之改善，我们可以通过具体的实例来从老师那学到更多的实用的知识。

XXX学院本科数据结构课程设计总结报告设计题目：实验一、哈夫曼编/译码器学生姓名：XXX系别：XXX专业：XXX班级：XXX学号：XXX指导教师：XXX XXX2012年6 月21日xxx学院课程设计任务书题目一、赫夫曼编译码器专业、班级xxx学号xxx 姓名xxx主要内容、基本要求、主要参考资料等：1. 主要内容利用哈夫曼编码进行信息通信可大大提高信道利用率，缩短信息传输时间，降低传输成本。

要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码（复原）。

对于双工信道（既可以双向传输信息的信道），每端都需要一个完整的编/译码系统。

试为这样的信息收发站写一个哈夫曼的编/译码系统。

2. 基本要求系统应具有以下功能：（1）C：编码（Coding）。

对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中，将以此建好的哈夫曼树存入文件HuffmanTree中（2）D：解码（Decoding）。

利用已建好的哈夫曼树将文件codefile中的代码进行译码，结果存入textfile中。

（3）P：打印代码文件（Print）。

将文件codefile以紧凑格式显示在终端上，每行50个代码。

同时将此字符形式的编码文件写入文件codeprint中。

（4）T：打印哈夫曼树（Tree Printing）。

将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint中。

3. 参考资料：数据结构（C语言版）严蔚敏、吴伟民编著；数据结构标准教程胡超、闫宝玉编著完成期限：2012年6月21 日指导教师签名：课程负责人签名：2012年 6月 21 日一、设计题目（任选其一）实验一、哈夫曼编/译码器二、实验目的1巩固和加深对数据结构的理解，提高综合运用本课程所学知识的能力；2 深化对算法课程中基本概念、理论和方法的理解；3 巩固构造赫夫曼树的算法；4 设计试验用程序实验赫夫曼树的构造。

哈夫曼编\译码的设计与实现一、简介1．设计目的：通过对简单哈夫曼编/译码系统的设计与实现来熟练掌握树型结构在实际问题中的应用。

2．问题的描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。

但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码。

系统应该具有如下的几个功能：接收原始数据、编码、译码、打印编码规则。

二、数据结构的设计：1.哈夫曼结点结构体：typedef struct HtNode{int weight;int parent, lchild, rchild;}HtNode;2.哈夫曼树结构体：typedef struct HtTree{struct HtNode ht[MAXNODE+1];int root;}HtTree, *PHtTree;三、功能（函数）设计：总体上划分为四个模块，具体功能描述如下：1．初始化功能模块：接收输入信息，并正确输出2．建立哈夫曼树的功能模块：按照构造哈夫曼树的算法构造哈夫曼树，将HuffNode数组中的各个位置的各个域都添上相关的值3．哈夫曼编码的功能模块：根据输入的相关字符信息进行哈夫曼编码，然后将结果存入，同时将字符与0、1代码串的一一对应关系打印到屏幕上。

4．译码的功能模块：接收需要译码的0、1代码串，按照哈夫曼编码规则将其翻译成字符集中的字符所组成的字符串形式，将翻译的结果在屏幕上输出四、界面设计：该界面操做简单，内容详细，便于程序使用者根据提示轻松上手。

简洁明朗是该界面最大的特点。

哈夫曼编/译码请逐个输入结点和结点的权值>>>按Enter键开始根据此提示界面进入程序使用阶段。

请输入结点个数：根据用户输入结点个数，动态输入并存储字符及权值然后输出字符与0、1代码串的对应关系。

进入以下界面，进行后续操作1----------------------------编码2----------------------------译码3----------------------------重新输入权值;0----------------------------退出用户键入“0”，即可出编码译码操作五、程序设计：1．函数功能说明及其程序流程图的描述：1>:main函数：控制整个程序的整个流程。

哈夫曼编码和译码的算法设计与实现实验名称哈夫曼编码和译码的算法设计与实现实验方案实验成绩实验日期实验室信息系统设计与仿真室I 实验操作实验台号班级姓名实验结果一、实验目的1、掌握哈夫曼编码的二叉树结构表示方法；2、编程实现哈夫曼编码译码器；3、掌握贪心算法的设计策略。

二、实验任务①从文件中读取数据，构建哈夫曼树；②利用哈夫曼树，对输入明文进行哈夫曼编码；③利用哈夫曼树，对输入编码译码为明文。

三、实验设计方案1、结构体设计Huffman树：包括字符，权，父亲下标，左孩子下标，右孩子下标#define N 29 //26个小写字母，逗号，句号和空格字符.struct treenode{ //静态链表char c; //charint w; //weightint f; //fatherint l; //left child indexint r; //right child index};struct treenode htree[2*N-1];2、自定义函数设计①函数原型声明void input(); //读取文件字符、权值数据void huffman(); //建立huffman树void getcode(int i, char *str); //得到单个字符的huffman编码void encode(char ch); //将明文进行huffman编码void decode(char *str); //将huffman编码译为明文②读取文件字符、权值数据void input(){int i;char c;int f;freopen("in.txt","r",stdin);for(i=0;i<n;i++)< p="">{c=getchar(); //接收字符scanf("%d",&f); //接收权值getchar(); //接收回车ht[i].c=c;ht[i].w=f;ht[i].l=ht[i].f=ht[i].r=-1; //初始化父亲、左右孩子下标} freopen( "CON", "r", stdin);}③建立huffman树//使用贪心法建立huffman树,每次选择权值最小的根结点void huffman(){void huffman(){int j,k,n;input();j=0;k=N;for(n=N;n<2*N-1;n++){ //建立huffman树，共合并N-1次int r=0,s=0;ht[n].l=ht[n].f=ht[n].r=-1;while(r<2){ //选择两个最小的权值结点if((ht[k].w==0 || ht[k].w>ht[j].w) && j<n){< p="">s+=ht[j].w;if(r==0) ht[n].l = j; //修改父亲、孩子下标else ht[n].r=j;ht[j].f=n;j++;}else{s+=ht[k].w;if(r==0) ht[n].l = k; //修改父亲、孩子下标else ht[n].r=k;ht[k].f=n;k++;}r++;}ht[n].w=s; //修改权值}}④根据字符下标找到字符的huffman编码//根据字符所在的下标，从叶子结点往上搜索到根节点，然后逆置得到该字符的huffman编码void getcode(int i, char *str){ int n,j,l=0;for(n=i;ht[n].f!=-1;n=ht[n].f){ //沿着父亲往上搜索int m=ht[n].f;if(n==ht[m].l)str[l++]='0'; //左孩子记为0elsestr[l++]='1'; //右孩子记为1}for(j=0;j<=(l-1)/2;j++){ //将编码逆置char t;t=str[j];str[j]=str[l-1-j];str[l-1-j]=t;}str[l]=0; // str存放huffman编码，字符串结束标记}⑤读入明文生成huffman编码void encode(char ch){int i;char str[N];for(i=0;ht[i].c!=0;i++)if(ht[i].c==ch) //找字符下标break;if (ht[i].c!=0){getcode(i,str); //得到字符的huffman编码printf("%s",str);}}⑥将huffman编码串译码为明文void decode(char *str){while(*str!='\0'){int i;for(i=2*N-2;ht[i].l!=-1;){if(*str=='0')i=ht[i].l;elsei=ht[i].r;str++;}printf("%c",ht[i].c);}}3、主函数设计思路：主函数实现实验任务的基本流程。

哈夫曼编码算法实现完整版.doc
哈夫曼编码（Huffman Coding）是一种编码方式，它通过对最常出现频率最高的字符
串编码最短的字节，以节省带宽和存储空间。

它可以将字符信息编码为变长的序列，最短
的字符占用的位数就更少，而最长的字符占用的位数则更多。

实现哈夫曼编码步骤：
（1）统计字符串中字符出现的次数，并生成频率表
（2）将每个字符对应的频率以及编码长度（未分配）加入一个哈夫曼树（Huffman Tree）的叶节点集合中
（3）将集合中的叶节点按照哈夫曼编码的原则进行排序，并重新构造哈夫曼树
（4）从根节点开始计算叶节点的哈夫曼编码，并以二进制形式记录：找到从根节点
到叶节点的路径，从根节点出发，左子节点编码为0，右子节点编码为1
（5）最终给出每个字符对应的哈夫曼编码
哈夫曼编码有如下特点：
（1）使用有穷自动机原理：利用“最优子结构”和“贪心算法”的原理，构造符合
条件的哈夫曼树，从而获得哈夫曼编码；
（2）信源编码理论：哈夫曼编码是考虑到信源编码理论的一种应用，它能把信源各
字符的分布概率考虑在内，根据信源各字符分布给出较合理的字符编码，使得信源编码长
度最短；
（3）使用哈夫曼编码能更加有效地利用存储空间；
（4）哈夫曼编码能减少网络传输数据量，加快网络传输速度；
（5）哈夫曼编码的解码有较高的效率，可以采用类似BinarySearch的方式进行搜索，时间复杂度可以以O（log n）的速度进行解码
通过使用哈夫曼编码，能使编码的效率更高，节省大量存储空间和带宽。

此外，它的
实现原理相对较为简单，因此，现有大多数编码解码系统都会支持哈夫曼编码。

一、需求分析目前，进行快速远距离通信的主要手段是电报，即将需传送的文字转化成由二级制的字符组成的字符串。

例如，假设需传送的电文为“ABACCDA”，它只有4种字符，只需两个字符的串，便可以分辨。

假设A、B、C、D、的编码分别为00,01,10和11，则上述7个字符的电文便为“00010010101100”，总长14位，对方接受时，可按二位一分进行译码。

当然，在传送电文时，希望总长尽可能地短。

如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用尽可能短的编码，则传送电文的总长便可减少。

如果设计A、B、C、D的编码分别为0,00,1,01，则上述7个字符的电文可转换成总长为9的字符串“000011010”。

但是，这样的电文无法翻译，例如传送过去的字符串中前4个字符的字串“0000”就可以有很多种译法，或是“AAAA”或者“BB”，或者“ABA”等。

因此，若要设计长短不等的编码，则必须是任一字符的编码都不是另一个字符的编码的前缀，这种编码称作前缀编码。

然而，如何进行前缀编码就是利用哈夫曼树来做，也就有了现在的哈夫曼编码和译码。

二、概要设计利用哈夫曼树编/译码（一）、建立哈夫曼树（二）、对哈夫曼树进行编码（三）、输出对应字符的编码（四）、译码过程主要代码实现：struct code //结构体的定义{char a;int w; int parent; int lchild; int rchild;};void creation(code *p,int n,int m); //建立哈夫曼树 void coding(code *p,int n);//编码void display(code *p,int n,int m);//输出函数void translate(char **hc,code *p,int n);//译码三、 详细设计（一）、建立哈夫曼树（二）、对哈夫曼树进行编码主要代码实现：for(c=i,f=p[i].parent;f!=0;c=f,f=p[f].parent) { if(p[f].lchild==c)//左孩子编码为'0'{ cd[--start]='0';}1 2 3 4 5 * * * 6 7序号： 权值： 1 23 4 3 6 10 106 图3-1 图从叶子到根逆向求编码else //右孩子编码为'1'{ cd[--start]='1';}}（三）、输出对应字符的码（四）、译码过程主要代码实现：if(strcmp(a,hc[i])==0) //比较两个字符串是否相等，相等则输出0 { for(c=2*n-1,j=0;a[j]!='\0';j++) //从根出发，按字符'0'或'1'确定找左孩子或右孩子 {if(a[j]=='0') //左孩子{ c=p[c].lchild;}else图3-4表3-1从跟到叶子顺向求字符{ c=p[c].rchild; //右孩子}}四、 调试分析（一）、数字的输入判断（二）、字母的输入判断（三）、程序是否继续进行的判断五、 用户手册（一）、首先根据提示输入初始化数据，提示输入一个数字，请输入一个数a ，0<a<9999；提示输入一个1图3-5图4-1图4-2图4-3字母，则请输入一个字母（a~z)或者(A~Z)中的一个字符；请勿在输入一个数字后再输入一个字符，或者在输入一个字符后再输入一个数字。

哈夫曼编码与译码孙宇E010141081.题目内容：利用Huffman编码进行通信可以大大提高信道的利用率，缩短信息传输时间，降低传输成本。

但是，这要求在发送端通过一个编码系统对待传数据进行预先编码，在接收端进行解码。

对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/解码系统。

2.基本要求：输入一段英文，系统自动计算出每个字符的权值，以及哈夫曼编码，显示哈夫曼树。

最终把字符串的编码的显示出来。

然后进行译码，把编码信息转换成相应的文字信息。

3.程序模块结构图4.详细程序设计#include "stdafx.h" #include<stdio.h> #include<malloc.h> 主函数模块编码模块解码模块打印代码模块打印树模块输入初始化模块#include<string.h>#define MAXSIZE 100#define N 100#define M 2*N-1typedef struct //建立哈夫曼树结点{char ch;int weight;int parent;int LChild;int RChild;}HTNode,HuffmanTree[MAXSIZE];typedef struct //定义结构体{char ch;int number;}NUM[MAXSIZE];typedef char * HuffmanCode[N+1];void menu(void);void getchars(char *str,int *len); //输入字符串void Init(int A[MAXSIZE],int *n); //输入结点的权值（备用）void CrtHuffmanTree(HuffmanT ree ht,NUM w,int n);//创建哈夫曼树void select(HuffmanT ree ht,int pos,int *s1,int *s2);void CrtHuffmanCode(HuffmanTree ht,HuffmanCode hc,int n);//创建哈夫曼编码void showHuffmanCode(HuffmanCode hc,int n,NUM w,char *str,char *code,int len);//显示哈夫曼编码及各结点详细信息void total(char str[MAXSIZE],NUM w,int *n,int len);void CrtHuffmanDecode(HuffmanTree ht,char *code,int n);//进行译码工作void CrtHuffmanDecode(HuffmanTree ht,char *code,int n) {char result[MAXSIZE]={0};int rootIndex=n*2-1;int i,j,root=rootIndex;printf("\n传过来的信息是:\n");puts(&code[1]);for(i=j=1;i<=(int)strlen(&code[1])+1;i++){if(ht[root].RChild==0){result[j++]=ht[root].ch;root=rootIndex;}if(code[i]=='1')root=ht[root].RChild;elseroot=ht[root].LChild;}result[j]=0;printf("\n译码的结果是:\n%s\n\n",&result[1]);puts(&result[1]);}void total(char str[MAXSIZE],NUM w,int *n,int len) {int i,j=1,k=1;for(i=1;i<=len;i++)w[i].number=0;w[k].ch=str[j];w[k].number++;k++;for(j=2;j<len;j++){for(i=1;i<k;i++)if(str[j]==w[i].ch){w[i].number++;break;}if(i==k){w[k].ch=str[j];w[k].number++;k++;}}*n=k-1;}void showHuffmanCode(HuffmanCode hc,int n,NUM w,char *str,char *code,int len){int i,j;printf("字符\t权值\t编码\n");for(i=1;i<=n;i++)printf("%c\t%d\t%s\n",w[i].ch,w[i].number,hc[i]);printf("\n字符编码是:\n");for(i=1;i<len;i++)for(j=1;j<=n;j++)if(str[i]==w[j].ch){// printf("%s",hc[j]);strcat(&code[1],hc[j]);// break;}puts(&code[1]);}void CrtHuffmanCode(HuffmanTree ht,HuffmanCode hc,int n) {int i,c,start,p;char *cd;cd=(char *)malloc((n+1)*sizeof(char));cd[n-1]='\0';for(i=1;i<=n;i++){start=n-1;c=i;p=ht[i].parent;while(p!=0){--start;if(ht[p].LChild==c)cd[start]='0';elsecd[start]='1';c=p;p=ht[p].parent;}hc[i]=(char *)malloc((n-start)*sizeof(char));strcpy(hc[i],&cd[start]);}free(cd);}void select(HuffmanT ree ht,int pos,int *s1,int *s2){int i,m1,m2;for(i=1;i<=pos;i++)if(ht[i].parent==0){m1=i;break;}for(i=1;i<=pos;i++)if(ht[i].weight<=ht[m1].weight && ht[i].parent==0) m1=i;*s1=m1;m2=m1;for(i=1;i<=pos;i++)if(ht[i].parent==0 && i!=m2){m1=i;break;}for(i=1;i<=pos;i++)if(ht[i].weight<=ht[m1].weight && ht[i].parent==0 && i!=m2)m1=i;*s2=m1;}void CrtHuffmanTree(HuffmanTree ht,NUM w,int n){//构造哈夫曼树ht[M+1],w[]存放n个权值int i,m,s1,s2;for(i=1;i<=n;i++){ht[i].ch=w[i].ch;ht[i].weight=w[i].number;ht[i].parent=0;ht[i].LChild=0;ht[i].RChild=0;}m=2*n-1;for(i=n+1;i<=m;i++){ht[i].ch=' ';ht[i].weight=0;ht[i].parent=0;ht[i].LChild=0;ht[i].RChild=0;}for(i=n+1;i<=m;i++){select(ht,i-1,&s1,&s2);ht[i].weight=ht[s1].weight+ht[s2].weight;ht[s1].parent=i;ht[s2].parent=i;ht[i].LChild=s1;ht[i].RChild=s2;}}void getchars(char *str,int *len){printf("请输入一行字符串:\n");gets(&str[1]);*len=strlen(str);}/*void Init(int w[MAXSIZE],int *n) {int num,i=1;printf("请输入一组权值(以0结束):");scanf("%d",&num);while(num){w[i]=num;i++;scanf("%d",&num);}*n=i-1;}*/void main(void){HuffmanTree ht;HuffmanCode hc;char code[MAXSIZE]="";NUM w;int n,len;char str[MAXSIZE];getchars(str,&len);total(str,w,&n,len);// Init(w,&n);CrtHuffmanTree(ht,w,n);CrtHuffmanCode(ht,hc,n);showHuffmanCode(hc,n,w,str,code,len);CrtHuffmanDecode(ht,code,n);}5.测试程序：输入一段英文I am sunyu，i am a student. 显示结果如下：运行成功！。

实验五哈夫曼编码与译码的设计与实现一、问题描述利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。

但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。

对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。

试为这样的信息收发编写一个哈夫曼码的编/译码系统。

基本要求：（1）接收原始数据：从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件nodedata.dat中。

（2）编码：利用已建好的哈夫曼树（如不在内存，则从文件nodedata.dat 中读入），对文件中的正文进行编码，然后将结果存入文件code.dat中。

（3）译码：利用已建好的哈夫曼树将文件code.dat中的代码进行译码，结果存入文件text中。

（4）打印编码规则：即字符与编码的一一对应关系。

（5）打印哈夫曼树：将已在内存中的哈夫曼树以直观的方式显示在终端上。

二、数据结构设计1、构造哈夫曼树时，使用静态链表作为哈夫曼树的存储。

在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1，描述结点的数据类型为：typedef struct{int weight;int parent;int lchild;int rchild;char inf;}HNodeType;2.求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。

求哈夫曼编码实际上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，每回退一步，就走过了哈夫曼的一个分支，从而得到一位哈夫曼编码值。

由于一个字符的哈夫曼编码就是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码为所求的高位码。

XXX学院本科数据结构课程设计总结报告设计题目：实验一、哈夫曼编/译码器学生：XXX系别：XXX专业：XXX班级：XXX学号：XXX指导教师：XXX XXX2012年6 月21日xxx学院课程设计任务书题目一、赫夫曼编译码器专业、班级xxx学号xxx xxx主要容、基本要求、主要参考资料等：1. 主要容利用哈夫曼编码进行信息通信可大大提高信道利用率，缩短信息传输时间，降低传输成本。

要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码（复原）。

对于双工信道（既可以双向传输信息的信道），每端都需要一个完整的编/译码系统。

试为这样的信息收发站写一个哈夫曼的编/译码系统。

2. 基本要求系统应具有以下功能：（1）C：编码（Coding）。

对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中，将以此建好的哈夫曼树存入文件HuffmanTree中（2）D：解码（Decoding）。

利用已建好的哈夫曼树将文件codefile中的代码进行译码，结果存入textfile中。

（3）P：打印代码文件（Print）。

将文件codefile以紧凑格式显示在终端上，每行50个代码。

同时将此字符形式的编码文件写入文件codeprint中。

（4）T：打印哈夫曼树（Tree Printing）。

将已在存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint中。

3. 参考资料：数据结构（C语言版）严蔚敏、吴伟民编著；数据结构标准教程胡超、闫宝玉编著完成期限：2012年6月21 日指导教师签名：课程负责人签名：2012年 6月 21 日一、设计题目（任选其一）实验一、哈夫曼编/译码器二、实验目的1巩固和加深对数据结构的理解，提高综合运用本课程所学知识的能力；2 深化对算法课程中基本概念、理论和方法的理解；3 巩固构造赫夫曼树的算法；4 设计试验用程序实验赫夫曼树的构造。

#include <iostream.h>#include <iomanip.h>#include <string.h>#include <malloc.h>#include <stdio.h>//typedef int TElemType;const int UINT_MAX = 1000;typedef struct{int weight;int parent, lchild, rchild;} HTNode, *HuffmanTree;typedef char **HuffmanCode;//-----------全局变量-----------------------HuffmanTree HT;HuffmanCode HC;int *w, i, j, n;char *z;int flag = 0;int numb = 0;// -----------------求赫夫曼编码-----------------------int min(HuffmanTree t, int i){// 函数void select()调用int j, flag;int k = UINT_MAX; // 取k为不小于可能的值for (j = 1; j <= i; j++)if (t[j].weight < k && t[j].parent == 0)k = t[j].weight, flag = j;t[flag].parent = 1;return flag;}//--------------------slect函数----------------------void select(HuffmanTree t, int i, int &s1, int &s2){// s1为最小的两个值中序号小的那个int j;s1 = min(t, i);s2 = min(t, i);if (s1 > s2){j = s1;s1 = s2;s2 = j;}}// --------------算法6.12--------------------------void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n){// w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC int m, i, s1, s2, start;//unsigned c,f;int c, f;HuffmanTree p;char *cd;if (n <= 1)return ;//检测结点数是否可以构成树m = 2 * n - 1;HT = (HuffmanTree)malloc((m + 1) *sizeof(HTNode)); // 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->parent = 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 = HT[s2].parent = i;HT[i].lchild = s1;HT[i].rchild = s2;HT[i].weight = HT[s1].weight + HT[s2].weight;}// 从叶子到根逆向求每个字符的赫夫曼编码HC = (HuffmanCode)malloc((n + 1) *sizeof(char*));// 分配n个字符编码的头指针向量([0]不用)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';elsecd[--start] = '1';HC[i] = (char*)malloc((n - start) *sizeof(char));// 为第i个字符编码分配空间strcpy(HC[i], &cd[start]); // 从cd复制编码(串)到HC}free(cd); // 释放工作空间}//--------------初始化赫夫曼链表---------------------------------void Initialization(){flag = 1;int num;int num2;cout << "下面初始化赫夫曼链表" << endl << "数请输入结点的个n：";cin >> num;n = num;w = (int*)malloc(n *sizeof(int));z = (char*)malloc(n *sizeof(char));cout << "\n请依次输入" << n << "个字符(字符型)\n注意:必须以回车结束：" << endl;char base[2];for (i = 0; i < n; i++){cout << "第" << i + 1 << "个字符:" << endl;gets(base);*(z + i) = *base;for (i = 0; i <= n - 1; i++){cout << setw(6) << *(z + i);}cout << "\n请依次输入" << n << "个权值(\n注意:必须以回车结束)：" << endl; for (i = 0; i <= n - 1; i++){cout << endl << "第" << i + 1 << "个字符的权值:";cin >> num2;*(w + i) = num2;}HuffmanCoding(HT, HC, w, n);//------------------------打印编码-------------------------------------------cout << "字符对应的编码为:" << endl;for (i = 1; i <= n; i++){//cout<<"字符"<<*(z+i-1)<<"的编码";puts(HC[i]);}//--------------------------将赫夫曼编码写入文件------------------------cout << "下面将赫夫曼编码写入文件" << endl << "...................." << endl; FILE *htmTree;char r[] =' ', '\0'};if ((htmTree = fopen("htmTree.txt", "w")) == NULL){cout << "can not open file" << endl;return ;}fputs(z, htmTree);for (i = 0; i < n + 1; i++){fprintf(htmTree, "%6d", *(w + i));fputs(r, htmTree);}for (i = 1; i <= n; i++){fputs(HC[i], htmTree);fputs(r, htmTree);}fclose(htmTree);cout << "已将字符与对应编码写入根目录下文件htmTree.txt中" << endl << endl; }//---------------------获取报文并写入文件---------------------------------void InputCode()//cout<<"请输入你想要编码的字符"<<endl;FILE *tobetran;char str[100];if ((tobetran = fopen("tobetran.txt", "w")) == NULL){cout << "不能打开文件" << endl;return ;}cout << "请输入你想要编码的字符" << endl;gets(str);fputs(str, tobetran);cout << "获取报文成功" << endl;fclose(tobetran);}//---------------------编码函数---------------------------------void Encoding(){cout << "下面对目录下文件tobetran.txt中的字符进行编码" << endl; FILE *tobetran, *codefile;if ((tobetran = fopen("tobetran.txt", "rb")) == NULL){cout << "不能打开文件" << endl;}if ((codefile = fopen("codefile.txt", "wb")) == NULL) {cout << "不能打开文件" << endl;}char *tran;i = 99;tran = (char*)malloc(100 *sizeof(char));while (i == 99){if (fgets(tran, 100, tobetran) == NULL){cout << "不能打开文件" << endl;break;}for (i = 0; *(tran + i) != '\0'; i++){for (j = 0; j <= n; j++){if (*(z + j - 1) == *(tran + i)){fputs(HC[j], codefile);if (j > n){cout << "字符错误，无法编码!" << endl;break;}}}}}cout << "编码工作完成" << endl << "编码写入目录下的codefile.txt中" << endl << endl;fclose(tobetran);fclose(codefile);free(tran);}//-----------------译码函数---------------------------------void Decoding(){cout << "下面对根目录下文件codefile.txt中的字符进行译码" << endl;FILE *codef, *txtfile;if ((txtfile = fopen("Textfile.txt", "w")) == NULL){cout << "不能打开文件" << endl;}//txtfile=fopen("Textfile.txt","w");if ((codef = fopen("codefile.txt", "r")) == NULL){cout << "不能打开文件" << endl;}//codef=fopen("codefile.txt","r");char *work, *work2, i2;int i4 = 0, i, i3;unsigned long length = 10000;work = (char*)malloc(length *sizeof(char)); fgets(work, length, codef);work2 = (char*)malloc(length *sizeof(char)); i3 = 2 * n - 1;for (i = 0; *(work + i - 1) != '\0'; i++){i2 = *(work + i);if (HT[i3].lchild == 0){*(work2 + i4) = *(z + i3 - 1);i4++;i3 = 2 * n - 1;i--;}else if (i2 == '0')i3 = HT[i3].lchild;i3 = HT[i3].rchild;}*(work2 + i4) = '\0';fputs(work2, txtfile);cout << "译码完成" << endl << "内容写入根目录下的文件txtfile.txt中" << endl << endl;cout << work2;free(work);free(work2);fclose(txtfile);fclose(codef);}//------------------------打印赫夫曼树的函数-----------------------void coprint(HuffmanTree start, HuffmanTree HT){if (start != HT){FILE *TreePrint;if ((TreePrint = fopen("TreePrint.txt", "a")) == NULL){cout << "创建文件失败" << endl;return ;numb++; //该变量为已被声明为全局变量coprint(HT + start->rchild, HT);cout << setw(5 *numb) << start->weight << endl;fprintf(TreePrint, "%d\n", start->weight);coprint(HT + start->lchild, HT);numb--;fclose(TreePrint);}}void Tree_printing(HuffmanTree HT, int w){HuffmanTree p;p = HT + w;cout << "下面打印赫夫曼树" << endl;coprint(p, HT);cout << "打印工作结束" << endl;}//------------------------主函数------------------------------------void main(){char choice;cout << " 赫夫曼编码解码系统" << endl;cout << "1.要初始化赫夫曼链表请输入'i'" << endl;cout << "2.要编码请输入'e'" << endl;cout << "3.要译码请输入'd'" << endl;cout << "4.要打印编码请输入'p'" << endl;cout << "5.要打印赫夫曼树请输入't'" << endl;cout << "6.要离开请输入'q'" << endl;// if(flag==0)cout<<"\n请先初始化赫夫曼链表,输入'i'"<<endl; cin >> choice;switch (choice){case 'i':Initialization();break;case 'w':InputCode();break;case 'e':Encoding();break;Decoding();break;case 't':Tree_printing(HT, 2 *n - 1);break;case 'q':default:cout << "input error" << endl;}}free(z);free(w);free(HT);}运行结果：赫夫曼编码解码系统1.要初始化赫夫曼链表请输入'i'2.要编码请输入'e'3.要译码请输入'd'4.要打印编码请输入'p'5.要打印赫夫曼树请输入't'6.要离开请输入'q'下面初始化赫夫曼链表数请输入结点的个n：8请依次输入8个字符(字符型)注意:必须以回车结束：第1个字符:a第2个字符:b第3个字符:c第4个字符:d第5个字符:e第6个字符:f第7个字符:g第8个字符:ha b c d e f g h 请依次输入8个权值(注意:必须以回车结束)：第1个字符的权值:5第2个字符的权值:29第3个字符的权值:7第4个字符的权值:8第5个字符的权值:14第6个字符的权值:23第7个字符的权值:3第8个字符的权值:11字符对应的编码为:01101011101111110000111010下面将赫夫曼编码写入文件....................已将字符与对应编码写入根目录下文件htmTree.txt中赫夫曼编码解码系统1.要初始化赫夫曼链表请输入'i'2.要编码请输入'e'3.要译码请输入'd'4.要打印编码请输入'p'5.要打印赫夫曼树请输入't'6.要离开请输入'q'i下面初始化赫夫曼链表数请输入结点的个n：27请依次输入27个字符(字符型)注意:必须以回车结束：第1个字符:第2个字符:a第3个字符:b第4个字符:c第5个字符:d第6个字符:第7个字符: f第8个字符: g第9个字符: h第10个字符: i第11个字符: j第12个字符: k第13个字符: l第14个字符: m第15个字符: n第16个字符: o第17个字符: p第19个字符:r第20个字符:s第21个字符:t第22个字符:u第23个字符:v第24个字符:w第25个字符:x第26个字符:y第27个字符:za b c d e f gm n o p q r s t z请依次输入27个权值(第1个字符的权值:186第2个字符的权值:64第3个字符的权值:13第4个字符的权值:22第5个字符的权值:32第6个字符的权值:103第7个字符的权值:21第8个字符的权值:15第9个字符的权值:47第10个字符的权值:57第11个字符的权值:1第12个字符的权值:5第13个字符的权值:32第14个字符的权值:20第15个字符的权值:57第16个字符的权值:63第17个字符的权值:15第18个字符的权值:1第19个字符的权值:48第20个字符的权值:51第21个字符的权值:80第22个字符的权值:23第23个字符的权值:8第24个字符的权值:18第25个字符的权值:1第26个字符的权值:16第27个字符的权值:1字符对应的编码为: 11010101001000001010110010111110100101000001101111011100111101101011111111101111000100110111101110100100011111000011111101011110011110111101001111111011111下面将赫夫曼编码写入文件....................已将字符与对应编码写入根目录下文件htmTree.txt中。

实验六-哈夫曼编码和译码的算法设计与实现一、实验目的1、根据算法设计需要,掌握哈夫曼编码的二叉树结构表示方法；2、编程实现哈夫曼编译码器；3、掌握贪心算法的一般设计方法。

二、预习与参考1、认真阅读数据结构教材和算法设计教材内容, 熟悉哈夫曼编码的原理;2、设计和编制哈夫曼编译码器。

[参考数据类型或变量]typedef ElemType char；typedef struct node{int w;int flag;ElemType c;struct node *plink,*llink,*rlink;char code[m];}Node;Node *num[n], *root;[参考子程序接口与功能描述]void SetTree( NODE *root )功能: 从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树void EnCode( Node *p )功能: 利用已建好的哈夫曼树，对输入的正文进行编码void DeCode( void )功能: 利用已建好的哈夫曼树，将输入的代码进行译码三、实验要求上机实验时，一人一组，独立上机，熟练运用二叉树与贪心思想对数据进行压缩。

四、实验步骤1、设计SetTree的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止;2、设计EnCode的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止;3、设计DeCode的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止;4、将你的程序整理成功能模块存盘备用。

5、将写的程序如下：#include <stdio.h>#include <string.h>#include <math.h>#include <string>#define maxn 20 //最大结点数目#define inf 0xfffffff //无穷大typedef struct node{double w;int flag;int c;struct node *plink,*llink,*rlink; char code[maxn];int codelen;node() //初始化节点{flag=0;llink=NULL;plink=NULL;rlink=NULL;codelen=0;}}node;node *num[2*maxn-1];//指针数组int n;void SetTree(node *&root)//从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树{int i,m,j;scanf("%d",&n);//输入结点个数nfor(i=0;i<n;i++){num[i]=new node();num[i]->c=i;scanf("%lf",&num[i]->w);//输入结点的权值}m=n;double min1,min2;int pos1=0,pos2=0;for(i=0;i<m-1;i++){min1=inf;min2=inf;for(j=0;j<n;j++) //寻找权值最小的两个结点，保存在pos1和pos2中{if(num[j]->flag==0){if(num[j]->w<min1){min1=num[j]->w;pos2=pos1;pos1=j;}else if(num[j]->w<min2) {min2=num[j]->w;pos2=j;}}}num[pos1]->flag=1; //将pos1和pos2合并在新结点中，作为新节点的子节点num[pos2]->flag=1;num[n]=new node(); //新节点编号从n开始num[n]->c=-1;////添加代码，建立新结点n//// //建立新结点nnum[n]->w=num[pos1]->w+num[pos2]->w;num[n]->llink=num[pos1];num[n]->rlink=num[pos2];num[pos1]->plink=num[n];num[pos2]->plink=num[n];n++;}root=num[n-1];n=m;}void EnCode(node *root,int deep,char code[]) //利用已建好的哈夫曼树，对输入的文本进行编码{int i;if(root->c!=-1){for(i=0;i<deep;i++){root->code[i]=code[i];}root->codelen=deep;return;}code[deep]='0'; //左节点编码为0 EnCode(root->llink,deep+1,code);code[deep]='1'; //右节点编码为1 EnCode(root->rlink,deep+1,code);}void DeCode(node *root,char code[]) //利用已建好的哈夫曼树，对输入的代码进行译码int i;node *temproot=root;int len=strlen(code);int ans[maxn],anslen=0;for(i=0;i<len;i++){////添加代码，根据code[i]的值确定temproot的指向//// //根据code[i]的值确定temproot的指向if(code[i]=='0')temproot=temproot->llink;elsetemproot=temproot->rlink;if(temproot->c!=-1){ans[anslen++]=temproot->c; temproot=root;}if(temproot->llink==NULL && temproot->rlink==NULL){printf("你输入的数据不存在于该哈弗曼树中!\n");return;}}printf("输入数据的译码为：\n");for(i=0;i<anslen;i++){printf("%d",ans[i]);}printf("\n");}void print(){int i,j;for(i=0;i<n;i++){printf("%.2f:",num[i]->w);for(j=0;j<num[i]->codelen;j++) printf("%c",num[i]->code[j]);printf("\n");}}int main(){freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);node *root=NULL;root=new node();SetTree(root);char code[maxn*maxn];EnCode(root,0,code);print();printf("按上面的编码规则输入代码:\n");scanf("%s",code);DeCode(root,code);return 0;}五、测试输入80.6 0.2 0.05 0.05 0.03 0.03 0.030.01输出0.6：00.2：100.05：11000.05：11110.03：110100.03：110110.03：111010.01：11100六、实验报告要求1、阐述实验目的和实验内容;2、提交实验程序的功能模块;3、记录最终测试数据和测试结果。

算法与数据结构课程设计哈夫曼编码和译码的设计与实现1.问题描述利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输时间，降低传输成本。

但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。

对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。

试为这样的信息收发站设计一个哈夫曼码的编/译码系统。

2.基本要求a.编/译码系统应具有以下功能：（1）I：初始化（Initialization）。

从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。

（2）E：编码（Encoding）。

利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。

（3）D：译码（Decoding）。

利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。

（4）P：印代码文件（Print）。

将文件CodeFile以紧凑格式显示在终端上，每行50个代码。

同时将此字符形式的编码文件写入文件CodePrin中。

（5）T：印哈夫曼树（Tree printing）。

将已在内存中的哈夫曼树以直观的方式（树或凹入表形式或广义表）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。

b.测试数据（1）利用下面这道题中的数据调试程序。

某系统在通信联络中只可能出现八种字符，其概率分别为0.25，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计哈夫曼编码。

（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。

字符空格 A B C D E F G H I J K L M频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20字符 N O P Q R S T U V W X Y Z频度57 63 15 1 48 51 80 23 8 18 1 16 13．需求分析3.1程序的基本功能本程序可以对任何大小的字符型文件进行Huffman编码，生成一个编码文件。

《数据结构与算法》课程设计（2009/2010学年第二学期第20周）指导教师：班级：计算机科学与技术学号：姓名：《数据结构与算法》课程设计目录一、前言1．摘要2．《数据结构与算法》课程设计任务书二、实验目的三、题目--赫夫曼编码/译码器1．问题描述2．基本要求3．测试要求4．实现提示四、需求分析--具体要求五、概要设计六、程序说明七、详细设计八、实验心得与体会前言1．摘要随着计算机的普遍应用与日益发展，其应用早已不局限于简单的数值运算，而涉及到问题的分析、数据结构框架的设计以及设计最短路线等复杂的非数值处理和操作。

算法与数据结构的学习就是为以后利用计算机资源高效地开发非数值处理的计算机程序打下坚实的理论、方法和技术基础。

算法与数据结构旨在分析研究计算机加工的数据对象的特性，以便选择适当的数据结构和存储结构，从而使建立在其上的解决问题的算法达到最优。

数据结构是在整个计算机科学与技术领域上广泛被使用的术语。

它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。

数据结构有逻辑上的数据结构和物理上的数据结构之分。

逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。

数据结构是数据存在的形式。

《数据结构》主要介绍一些最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。

数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。

学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。

通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。

2．《数据结构与算法》课程设计任务书《数据结构与算法》是计算机专业重要的核心课程之一，在计算机专业的学习过程中占有非常重要的地位。

哈夫曼编码/译码一、实验内容利用哈夫曼编码进行住处通讯可以大大提高信道利用率,缩短住处传输时间,降低成本,但是,这要求在发送端通过一个编码系统将传输的数据预先编码,在接收端通过一个译码系统对传来的数据进行译码(复原),对于双向传输信息的信道,每端都一个完整的编码译码系统,试为这样的住处收发站写一个哈夫曼友的编码译码系统.测试数据：用下表给出的字符集和频度的计数据建立哈曼树,并实现以下报文的编码和译码：“THIS PROGRAM IS MY FA VORITE”.。

字符 A B C D E F G H I J K L M频数186 64 13 22 32 103 21 15 47 57 1 5 32 20字符N O P Q R S T U V W X Y Z频数57 63 15 1 48 51 80 23 8 18 1 16 1二、实验目的树型结构是一种应用极为广泛的非线性数据结构,也是本课程的重点内容,哈夫曼树(最优二叉树)是树型结构的典型应用,本次实验突出了数据结构加操作的程序设计观点,希望能根据树型结构的非线性特点,熟悉各种存储结构的特性,达到如何应用树型结构的非线性特点,熟悉各种存储结构的特性,达到如何应用树型结构解决具体问题的目的.三、实验步骤：1、需求分析1）、利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。

但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。

对于双工信道（既可以双向传输信息的信道），每端都需要一个完整的编/译码系统。

本次设计就是为这样的信息收发站写的一个哈夫曼的编/译码器。

本实验要求：2）、本演示程序中，用户可以输入键盘中的任意字符，长度为任意长，字符输入顺序不限，且允许出现重码3）、演示程序以用户与计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，相应的输入数据（可虑去输入中的非法字符）和运算结果显示在其后。