还剩12页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
设计一个哈夫曼的编/译码系统问题描述L利用哈夫曼编码进行通信可以提高信道利用率,缩短信息传输时间,降低传输成本这要求在发送端通过一个编码系统对待传输数据预先编码,在接收端将传来的数据进行译码复原写一个哈夫曼树编码译码系统基本要求
2.一个完整的系统应具有以下功能I初始化Initialization从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树,并将它存于文件hfmTree中E编码Encoding利用已建好的哈夫曼树如不在内存,则从文件hfmTree中读入,对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中D译码Decodingo利用已建好的哈夫曼树将文件CodeFile中的代码进行译码,结果存入文件TextFile中P打印代码文件Print将文件CodeFile以紧凑格式显示在终端上,每行50个代码同时将此字符形式的编码文件写入文件CodePrin中T打印哈夫曼树Tree printing将已在中的哈夫曼树以直观的方式树或凹入表o形式显示在终端上,同时将此字符形式的哈夫曼树写入文件TreePrint中测试要求
3.1利用下面这道题中的数据调试程序某系统在通信联络中只可能出现八种字符,其概率分别为
0.25,
0.29,
0.07,
0.08,
0.14,
0.23,
0.03,
0.11,试设计哈夫曼编码2用下表给出的字符集和频度的实际统计数据建立哈夫曼树,并实现以下报文的编码和译码“THIS PROGRAMIS MYFAVORITE”算法思想
7.输入字符个数28plase inputthe plain:THIS PROGAMIS MYFAVORATEThe plainisTHIS PROGAMIS MYFAVORATE*the plain already save in plaintext,txt编码字符及其权值THIS PROGAMYFVE编码表:T2的编码为:0110H1的编码为noooI2的编码为:0111S2的编码为10005的编码为00P1的编码为11001R2的编码为100102的编码为1010G1的编码为11010A3的编码为010M2的编码为1011Y1的编码为11011F1的编码为1H00V1的编码为11101E1的编码为111101的编码为1111112141218121412116242824228242141211624282422824273125he ciphercode is:he ciphercode alreadysave inciphertext,txtInt weight;Int parent,Ichild,rchild;}htnode,*hfmtree;HuffmanCoding编码功能对输入字符进行编码HuffmanDecode译码功能利用已建好的哈夫曼树将文件中的代码进行译码概念设计
5.哈夫曼编译码器的主要功能是先建立哈夫曼树,然后利用建好的哈夫曼树生成哈夫曼编码后进行译码在数据通信中,经常需要将传送的文字转换成由二进制字符
0、1组成的二进制串,称之为编码构造--棵哈夫曼树,规定哈夫曼树中的左分之代表0,右分支代表I,则从根节点到每个叶子节点所经过的路径分支组成的0和1的序列便为该节点对应字符的编码,称之为哈夫曼编码最简单的二进制编码方式是等长编码若采用不等长编码,让出现频率高的字符具有较短的编码,让出现频率低的字符具有较长的编码,这样可能缩短传送电文的总长度哈夫曼树课用于构造使电文的编码总长最短的编码方案源程序
6.#includestdio.h#includestdlib.h#includestring.h#includetime.h#include windows.h#define MAXSIZE10000#define greenSetConsoleTextAttributeGetStdHandleSTD_0UTPUT_HANDLE,F0REGR0UND_GREEN|F0REGR0UNDINTENSITY#define whiteSetConsoleTextAttributeGetStdHandleSTD_0UTPUT_HANDLE,F0REGR0UND_RED|FOREGROUND_BLUE|FOREGROUND_GREEN#define redSetConsoleTextAttributeGetStdHandle STDOUTPUT_HANDLE,FOREGROUND^RED|FOREGROUND.INTENSITY#define yellowSetConsoleTextAttributeGetStdHandleSTD_OUTPUT_HANDLE,F0REGR0UND_RED|FOREGROUND_GREEN|FOREGROUND_INTENSITY//类似green;red;white;的语句为颜色控制语句const intINF=0x3f3f3f3f;const intNINF=OxcOcOcOcO;//1061109567-1061109567最大最小值typedef structchar a;int weight;}Diet;//Diet以键值对得形式存储编码字符和对应的权值typedef structintweight;int parent,Ichild,rchild;char data;}IITNode,*HuffmanTree;typedef char**HuffmanCode;void RandomGeneratechar*a,int n//随机生成字符串charall口二〃ABCDEFGHIJKLMN0PQRSTUVIictXYZabcdefghijklmnopqrstuvwxyz0123456789〃;srandtime0;for int i=0;in;i++a[i]=all[rand%62];a[n]=,\0;green;printf/zThe plainis:%s\nz,,a;white;FILE*fp;fp=fopen plaintext.txt〃,〃w〃;fprintffp,〃%s〃,a;fclose fp;printf the plain alreadysave inplaintext.txt\nz/;void ManuallyInputchar a[],int n//手动输入n个字符printf^plase inputtheplain:\nz,;for int i=0;in;i++//输入控制字符数scanf〃%c〃,a[i];fflushstdin;a[n]=\0;green;printf z,The plainis:%s\n〃,a;//回显white;FILE*fp;fp=fopen plaintext.txt〃,〃w〃;//保存到文件fprintffp,〃%s〃,a;fclose fp;printf theplainalreadysave inplaintext.txt\n,z;}void Weightchar*a,Diet w[],int n{//a是待加密文本//Diet以键值对得形式存储编码字符和对应的权值//求得权值后n改为Huffman树中编码字符的个数即没有重复出现的字符for intj=0;j=n;j++//初始化w[j].weight、;char*p;P=a;int i=0,k;w[i].a=*p;w[i].weight++;p++;while*p!=\0{//每次循环都遍历w,对当前p所指的字符进行处理//若果在W中就权值加一,否则加入加入Wfor k=0;k=i;k++if w[k].a==*p//在w中出现{w[k].weight++;break;}if ki//不在w中i++;w[i].a=*p;w[i].weight++;p++;n=i+l;forint x=n;x0;x--//w
[0]空出来w[x]=w[x-l];printf〃编码字符及其权值\n〃;for i=l;i=n;i++//打印权值printf〃%c〃,w[i].a;printf〃\n〃;for i=l;i=n;i++printf〃%d〃,w[i].weight;printf〃\n〃;void SelectHuffmanTree HT,int n,int sl,int s2{〃在HuffmanTree中筛选权值最小的两个节点下标赋值给si、s2int i=l;int minl=INF,min2=INF;//INF=1061109567sl=s2=0;whilei=n//minlmin2othersif IlT[i].parent二二0if minlHT[i].weightmin2=mini;s2=sl;minl=HT[i].weight;sl=i;}else ifmin2HT[i].weights2二i;min2=HT[i].weight;}}//end ifi++;}//end whilevoid CreateHuffmanHuffmanTreeHT,Diet w[],int n//创建哈弗曼树并存储在HuffmanTree文件中,n为长度int i,si,s2;int m=2*n-l;if n=lreturn;HT=HuffmanTreemallocm+1*sizeofHTNode;fori=0;i=n;i++{IIT[i].weight=w[i]・weight;HT[i].data=w[i].a;HT[iL lchild=0;HT[i].parent=0;HT[i],rchild=0;}for;i=m;++i HT[i].weight=0;HT[i].lchild=0;HT[i].parent=0;HT[i].rchild-O;for i=n+l;i=m;i++〃建立哈夫曼树si=s2=0;Select HT,i-l,si,s2;HT[sl].parent=i;HT[s2].parent=i;HT[i],lchild=sl;HT[i].rchild=s2;HT[i].weight=HT[si].weight+HT[s2].weight;//写入文件FILE*fp=fopen〃HuffmanTree〃,〃wb〃;fwriteHuffmanTreeHT,sizeofHTNode,m+1,fp;fclose fp;void Huffman_CodeTableHuffmanTree HT,HuffmanCode HC,int n{〃得到并打印哈夫曼树的编码表〃求出n个字符的哈夫曼编码HCifn=lreturn;printf〃编码表\n〃;int i;HC=HuffmanCodemallocn+1*sizeofchar*;char*cd=char*mallocn*sizeofchar;cd[nT]=\0;fori=l;i=n;++i〃倒序求编码字符的哈夫曼编码int start=n-l;forint c=i,f=HT[i],parent;f!=0;c=f,f=HT[f].parent ifHT[f].lchild=ccd[--start]=,O;elsecd[--start]=,1;HC[i]=char*mallocn-start*sizeof char;strcpy HC[i],cd+start;}for i=l;i=n;i++{printf zz%c%d的编码为:%s\n,z,HT[i].data,HT[i].weight,HCEi];}free cd;void HuffmanCodingHuffmanTreeHT,HuffmanCode HC,int n,char a[]FILE*fp;fp二fopen ciphertext.txt〃,〃w〃;//向文件中写入编码后的字符串green;printf〃\nThe ciphercode is:\n〃;int len=strlena;forint i=0;ilen;i++for intj=l;j=n;j++if a[i]==HT[j].datafprintffp,%s”,HC[j];printf%s〃,HC[j];}white;printf〃\nthe ciphercode alreadysaveinciphertext.txt\n,/;fclosefp;void HuffmanDecodeHuffmanTree HT,int n//Decode函数从ciphertext,txt读取编码字符串char decode[50*MAXSIZE]://最大加密字符个数MAXSIZE deocde要接收已加密的01字符串,所以空间要大,否则容易溢出inti,len,p;FILE*fp,*fpl;fp二fopenciphertext.txt〃,〃r〃;fscanffp,〃%s〃,decode;fclose fp;len=strlendecode;p=2*n-l;green;printfDecode Resultsis:\n〃;fpl=fopen/zDecodingResults.txt〃,“w〃;fori=0;i=len;i++//解码过程ifHT[p].lchild==0HT[p].rchild==0{printf/z%cz\HT[p].data;//向屏幕输出fprintf fpl,HT[p].data;//向文件输出保存p=2*n-l;}if decode[i]二二Op=HT[p].Ichild;else ifdecode[i]==,T p=HT[p].rchild;fclosefpl;white;void ReadHuffman_FromFi1eHuffmanTreeHT,int n//读取HuffmanTree文件中的哈夫曼树,n被修改为其中编码的字符个数printf〃输入HuffmanTree文件中编码字符的个数〃;scanf〃%d〃,n;fflushstdin;FILE*fp=fopen IIuffmanTree”,〃rb〃;freadHuffmanTreeHT,sizeof HTNode,2*n,fp;//因为huffman树是以二进制的形式存入文件的,〃所以读取的时候需要指定读取步长和总长度fclose fp;int DEPTH=0;〃递归层次void PreOrderTraverseHuffmanTreeHT,int k〃中序遍历并打印树,结果存放于fp中,k为根结点的下标inti;ifHT[k].rchild!=ODEPTH++;PreOrderTraverseHT,HT[k],rchild;DEPTH:fori=0;i=DEPTH;i++printf C/〃;printf,,%d\n,z,HT[k].weight;if HT[k].lchild!=ODEPTH++;PreOrderTraverse IIT,HT[k].Ichi Id;DEPTH—;ifHT[k].lchild==OHT[k].rchild==0return;return;}//PreOrderTraversevoid TreePrintingHuffmanTreeHT,int n〃打印树HT,n为树的叶子结点数//可以修改PreOrderTraverse函数,打印的凹凸哈夫曼树输出到文件printf〃凹凸哈夫曼树:\n〃;PreOrderTraverseHT,2*n~l;return;}//TreePrintingvoid startint choiceintn;char ch;。
个人认证
优秀文档
获得点赞 0