赫夫曼编码译码器.doc

数据结构课程设计实验题目：赫夫曼编码/译码器 班级 网络一班 姓名 学号 指导老师 成绩 一、需求分析 利用赫夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个赫夫曼码的编/译码系统。二、基本要求 1.基本要求一个完整的系统应具有以下功能： (1) I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立赫夫曼树，并将它存于文件hfmTree中。 (2) E：编码（Encoding）。利用已建好的赫夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。 (3) D：译码（Decoding）。利用已建好的赫夫曼树将文件CodeFile中的代码进行译码，结果存入文件Textfile中。2.测试要求(1) 利用教科书例6-2的数据调试程序：已知某系统在通信联络中只可能出现八种字符，其频率分别0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，试设计赫夫曼编码。(2) 用下表给出的字符集和频度的实际统计数据建立赫夫曼树，并实现以下报文的编码和译码：“THIS PROGRAME IS MY FAVORITE”。字符ABCDEFGHIJKLM频度1866413223210321154757153220字符NOPQRSTUVWXYZ频度57631514851802381811613.实现提示(1) 编码结果以文本方式存储在文件Codefile中。(2) 用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“Q”为止。(3) 在程序的一次执行过程中，第一次执行I，D或C命令之后，赫夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。三、概要设计 程序主要分为五部分，哈夫曼节点的定义，哈夫曼编码的定义，Select函数选择出权值最小的节点，Initialization函数生成哈夫曼树，主函数。 四、详细设计1. 数据存储结构设计（1）哈夫曼节点 哈夫曼节点数据类型如下，包含字符，权值，父节点，左右孩子：typedef struct char ch; unsigned int weight; unsigned int parent,lchild,rchild; HTNode,*HfmTree;（2） 哈夫曼编码 哈夫曼编码用二级指针存储，动态分配空间:typedef char *HfmCode;2. 算法的设计思想 （1）Select函数void Select(HfmTree HT,int a,int &s1,int &s2) /选择出parent为0的两个权值最小的两个节点，s1节点权值小于s2节点 int i,temp; i=0; while(HT+i.parent!=0); s1=i; while(HT+i.parent!=0); s2=i+; if(HTs1.weightHTs2.weight) temp=s1; s1=s2; s2=temp; for(;i=a;i+) if(HTi.parent=0) if(HTi.weightHTs1.weight) s1=i; else if(HTi.weightHTs2.weight) s2=i; /选出权值最小且无父节点的节点，选择范围为i-a; （2）Initialization函数void Initialization(HfmTree &HT,HfmCode &HC,int n,string ch,int *w) int i,m,s1,s2,start,c,f;/i HTNode位置，m为哈夫曼树节点数，s1s2选择节点，start开始点，c当前节点，f父节点 char* cd; if(n=1) return; m=2*n-1; HT=(HfmTree)malloc(m+1)*sizeof(HTNode);/0号单元使用 for(i=1;i=n;i+) HTi.ch=chi-1; HTi.weight=wi-1; HTi.parent=0; HTi.lchild=0; HTi.rchild=0; /初始化叶子节点 for(;i=m;i+) HTi.ch=0; HTi.weight=0; HTi.parent=0; HTi.lchild=0; HTi.rchild=0; /-为什么不能批量赋值-！ for(i=n+1;i=m;i+)/建立 哈夫曼树 Select(HT,i-1,s1,s2); HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; HC=(HfmCode)malloc(n+1)*sizeof(char*); cd=(char*)malloc(n*sizeof(char); cdn-1=0; for(i=1;i=n;i+) start=n-1; for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) if(HTf.lchild=c) cd-start=0; else cd-start=1; HCi=(char*)malloc(n-start)*sizeof(char); strcpy(HCi,&cdstart); free(cd); cout生成成功！endlendl; coutIDtchartweighttparenttlchildtrchildtendl; for(i=1;i2*n;i+) coutitHTi.chtHTi.weighttHTi.parenttHTi.lchildtHTi.rchildtendl; coutchartCodetendl; for(i=1;i=n;i+) coutHTi.chtHCitendl; /生成，前半部分为生成哈夫曼树，调用Select得出权值最小的两项，计算权值 /后半部分为哈夫曼编码生成，从后到前生成，动态分配空间大小3.源程序#include#include#includeusing namespace std;typedef struct char ch; unsigned int weight; unsigned int parent,lchild,rchild; HTNode,*HfmTree;typedef char *HfmCode;void Select(HfmTree HT,int a,int &s1,int &s2) /选择出parent为0的两个权值最小的两个节点，s1节点权值小于s2节点 int i,temp; i=0; while(HT+i.parent!=0); s1=i; while(HT+i.parent!=0); s2=i+; if(HTs1.weightHTs2.weight) temp=s1; s1=s2; s2=temp; for(;i=a;i+) if(HTi.parent=0) if(HTi.weightHTs1.weight) s1=i; else if(HTi.weightHTs2.weight) s2=i; void Initialization(HfmTree &HT,HfmCode &HC,int n,string ch,int *w) int i,m,s1,s2,start,c,f; /i HTNode位置，m为哈夫曼树节点数，s1s2选择节点，start开始点，c当前节点，f父节点 char* cd; if(n=1) return; m=2*n-1; HT=(HfmTree)malloc(m+1)*sizeof(HTNode);/0号单元使用 for(i=1;i=n;i+) HTi.ch=chi-1; HTi.weight=wi-1; HTi.parent=0; HTi.lchild=0; HTi.rchild=0; /初始化叶子节点 for(;i=m;i+) HTi.ch=0; HTi.weight=0; HTi.parent=0; HTi.lchild=0; HTi.rchild=0; /-为什么不能批量赋值- for(i=n+1;i=m;i+)/建立 哈夫曼树 Select(HT,i-1,s1,s2); HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; HC=(HfmCode)malloc(n+1)*sizeof(char*); cd=(char*)malloc(n*sizeof(char); cdn-1=0; for(i=1;i=n;i+) start=n-1; for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) if(HTf.lchild=c) cd-start=0; else cd-start=1; HCi=(char*)malloc(n-start)*sizeof(char); strcpy(HCi,&cdstart); free(cd); cout生成成功！endlendl; coutIDtchartweighttparenttlchildtrchildtendl; for(i=1;i2*n;i+)coutitHTi.chtHTi.weighttHTi.parenttHTi.lchildtHTi.rchildtendl; coutchartCodetendl; for(i=1;i=n;i+) coutHTi.chtHCitendl; int main() ifstream input_file; ofstream output_file; char action; string toBeTranSource,textFileSource; string charsIn,code; int i,j,c,n,w100; HfmTree HT; HfmCode HC; while(action!=Q) coutendl*endl; cout* 哈夫曼编码/译码器 *endl; cout* *endl; cout* I.初始化 E.编码 D.译码 /P.印码 /T.印树 *endl; cout* C.清屏 *endl; cout* Code by whocaresu 16/12/2010 *endl; cout*endl; coutendlaction; action=toupper(action); switch(action) case I: / 输入信息 coutn; cout请输入字符组(紧密输入不用空格区分)：; getline(cin,charsIn); getline(cin,charsIn); cout输入各个权重(中间空格)：; for(i=1;iwi-1; Initialization(HT,HC,n,charsIn,w); /输出备份到文件 cout正在输出备份到hfmTree.txt.endl; output_file.open(hfmTree.txt); if(!output_file) system(cls); coutCant open file!endl;return 1; output_filen; output_filecharsInn; for(i=0;in;i+) output_filewi ; output_file-以下为具体编码信息-endl; output_fileChartCodetendl; for(i=1;i=n;i+) output_fileHTi.chtHCitendl; output_file.close(); cout备份到hfmTree.txt成功！endl; ;break; case E: /判断内存中是否有生成哈夫曼树，没有的话从文件读入 if(sizeof(HC)5) cout内存中不存在哈夫曼树，从hfmTree.txt读入！endl; input_file.open(hfmTree.txt); if(!input_file) system(cls); coutCant open file!n; getline(input_file,charsIn); for(i=1;iwi-1; input_file.close(); Initialization(HT,HC,n,charsIn,w); input_file.open(ToBeTran.txt); if(!input_file) system(cls); coutCant open file!endl;return 1; cout-从ToBetTran.txt读取数据为-endl; getline(input_file,toBeTranSource); couttoBeTranSourceendl; input_file.close(); cout-endl; output_file.open(CodeFile.txt); if(!output_file) system(cls); coutCant open file!endl;return 1; cout-编译的密文(输出到CodeFile.txt)-endl; for(i=0;i=toBeTranSource.length();i+) for(j=1;j=n;j+) if(toBeTranSourcei=HTj.ch) coutHCj; output_fileHCj; output_file.close(); coutendl-编译完成-endl; ;break; case D: /译码 input_file.open(CodeFile.txt); if(!output_file) system(cls); coutCant open file!endl; return 1; cout-读取的编码为-endl; getline(input_file,code); coutcodeendl; input_file.close(); cout-译码为-endl; c=2*n-1; output_file.open(TextFile.txt); for(i=0;i=code.length();i+) if(HTc.lchild=0) coutHTc.ch; c=2*n-1; if(codei=0) c=HTc.lchild; else c= HTc.rchild; coutendl; cout-endl; ;break; case C: system(cls); break; default: coutendl操作码错误，重新输入！endl; system(pause); return 0; 五、调试分析1. 测试数据列表：(1) 利用教科书例6-2的数据调试程序：0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11(2) 用下表给出的字符集和频度的实际统计数据建立赫夫曼树，并实现以下报文的编码和译码：“THIS PROGRAME IS MY FAVORITE”。 abcdefghijklmnopqrstuvwxyz186 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 12.测试数据运行结果以下是程序运行的界面截图，