《数据结构课程设计报告哈夫曼编码译码器》由会员分享，可在线阅读，更多相关《数据结构课程设计报告哈夫曼编码译码器（9页珍藏版）》请在装配图网上搜索。
1、数据结构课程设计报告数据结构课程设计报告哈夫编码译码器班级：姓名：学号：完成时间:题目：哈夫曼编码译码器【问题描述】利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对传输数据预先编码，在接收端将传来的数据进行译码。对于双工信道，每端都需要一个完整的编码译码系统。试为这样的通信端编写一个哈夫曼编码译码系统。【基本功能】 一个完整的系统应具有以下功能： 初始化：输入一串字符（正文），计算不同字符（包括空格）的数目一级每种字符出现的频 率（以该种字符出现的次数作为其出现频率），根据权值建立哈夫曼树，输出每一种字符的哈夫曼编码。编码：利
2、用求出的哈夫曼编码，对该正文（字符串）进行编码，并输出。译码：对于得到的一串哈夫曼编码， 利用已求得的哈夫曼编码进行译码，将译出的正文输出。【运行流程】开始初始化：1、输入正文2、统计字符出现次数并输出3、求出哈夫曼编码并输出编码：发送方利用得到的哈夫曼编码对正文进行编码，输出密文译码：接收方利用哈夫曼编码对密文进行译码，输出译后的字符串结束源程序：/haffman.h#in cludevstri ngstruct HaffNode哈夫曼的结点结构int weight;char value;int flag;int pare nt;int leftchild;int rightchild;st
3、ruct Code/存放哈夫曼编码的数据元素结构char bitMAXN;char value;int start;int weight;void Haffma n(i nt weight,i nt n, HaffNode hafftree,char str2)构造哈夫曼树int j,m1,m2,x1,x2;/m1,m2 是左右孩子的 weight.x1,x2是左右孩子的仿真指针for(int i=0;i2*n-1;i+)/哈弗曼树的初始化，也就是将所有节点列出来，一边下面将他们一个一个构建入哈夫曼数中if(i n)hafftreei.weight=weighti;hafftreei.valu
4、e=str2i;else hafftreei.weight=0;hafftreei.flag=0;hafftreei.pare nt=O;hafftreei.leftchild=-1;hafftreei.rightchild=-1;for(i=0;in-1;i+)/构造n-1个非叶节点，循环一次构造一个非叶节点m仁 m2=MaxValue;x1=x2=0;for(j=0;jv n+i;j+)if(hafftreej.weightvm1 & hafftreej.flag=0)m2=m1;/使得ml得到的比m2小x2=x1;m1=hafftreej.weight;x1=j;else if(haff
5、treej.weightm2 & hafftreej.flag=0)m2=hafftreej.weight;x2=j;hafftreex1.pare nt=n+i;hafftreex2.pare nt=n+i;hafftreex1.flag=1;hafftreex2.flag=1;hafftree n+i.weight=hafftreex1.weight+hafftreex2.weight;hafftree n+i.leftchild=x1;hafftree n+i.rightchild=x2;void bianma(HaffNode hafftree,int n,Code haffCode,
6、char str1)/ 编码功能Code *cd=new Code;int child,pare nt;for(i nt r=0;r start=n-1;cd-weight=hafftreer.weight;cd-value=str1r;child=r;pare nt=hafftreechild.pare nt;while(pare nt!=0)/对所有叶节点编码if(hafftreepare nt.leftchild=child) cd-bitcd-start=0;elsecd-bitcd-start=1; cd-start-; child=pare nt;/左孩子结点为0/右孩子结点为1p
7、are nt=hafftreechild.pare nt;for(i nt j=cd-start+1;j bitj; haffCoder.start=cd-start; haffCoder.weight=cd-weight; haffCoder.value=cd-value;void yima(HaffNode hafftree,int n,string Enstr)/ 译码功能in t root=2* n-2;for(int i=0;iEnstr.length();i+)/ 当 Enstri为 0 时,oot 向左走,为1时向右走。当走到叶子结点时，输出叶子的 valueif(En stri
8、=0&hafftreeroot.leftchild!=-1)root=hafftreeroot .l eftchild;else if(En stri=1&hafftreeroot.rightchild!=-1)root=hafftreeroot.rightchild;if(hafftreeroot.leftchild=-1 &hafftreeroot.rightchild=-1)couthafftreeroot.value;root=2* n-2;coute ndl;/haf.cpp#in clude#i nclude#in cludeconst int MaxValue=100; cons
9、t int MAXN=100;const int maxbit=100; using n amespace std;#in cludehaffma n.h void mai n()int j=0;stri ng str,e nstr=;char temp26;/存放不同的字符int weight26;/存放不同字符的权值coutvv请输入要编译的字符串：；getli ne(ci n, str);cout这个字符串的长度为：vvstr.length()endlendl;int m=str.length();int *flag=new in tm;for(int t=O;tm;t+) flagt=
10、O; /初始化该字符串，每个字符标记为0for(t=0;tstr.le ngth();t+)if(flagt=0) 取出不同字符tempj=strt;weightj=1;for(i nt k=t+1;kstr.le ngth();k+)将与找出来的字符相同的字符标记，if(tempj=strk &flagk=0)flagk=1;weightj+;j+;coutvv在这串字符串中存在的字符种类是 vvjvv种endlvvendl;HaffNode *myhafftree=new HaffNode2*j-1;Code *myhaffcode=new Codej;Haffma n( weight,j
11、,myhafftree,temp);bia nm a(myhafftree,j,myhaffcode,temp);for(t=0;tstr.le ngth();t+)for(i nt k=0;kj;k+)if(myhaffcodek.value=strt)for(int s=myhaffcodek.start+1;sj;s+)en str=e nstr+myhaffcodek.bits;for(t=0;tj;t+)couttemptvv出现的次数为：weighttvv对应的编码为：for(int k=0;kj;k+)if(myhaffcodek.value=tempt)for(int s=my
12、haffcodek.start+1;sj;s+)coutmyhaffcodek.bits;coute ndl;coutn此字符串的编码为:endl;coute nstre ndl;coutn 译码结果为:endl;yima(myhafftree,j,e nstr);coute ndl;测试数据运行结果:：、F= I课程设才、竝膨5再VH天亜S3斜译吗器EebuEhfM.在这申字符串中存左的字舒网裘和日种+匸?十讥罕+十十 耳一TflH-S严皿-曲吊亠用一wj.丽亠闫亠用=睛 的肉的旳前的曲囱雷tI 圉应应应壷应应应府直118 1L1B 0L190 ldl RfWn 1111 VlAUi nnin sail:现羽次数为詁 忍免肖沖i现的次更为d网的次数知2 现対蓟敦为：!:圳的岌数为=!此字特爭慣編禍为：11 si 1160118301 iei 3O0di 0B8i 181 ii aid lateasieii ail ii liieaoaieeieBioaii 1161 in第8页数据结构课程设计报告第#页数据结构课程设计报告rBK 帚pi# krf Co CCilItjiviiiK译田结果为：t hereatuderita第9页
数据结构课程设计报告哈夫曼编码译码器
