哈夫曼编码译码问题

《数据结构》课程设计报告题目——哈夫曼编码译码问题班级：学号：姓名：时间：一、设计目的与内容1．设计目的熟悉对哈夫曼编码的应用以及构造方法，熟悉对树的存储方式的应用。2．设计内容：任务：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本，但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一哈夫曼编/译码系统。要求：1）初始化：从终端输入字符集的大小n，以及n个字符和n个权值，建立哈夫曼树。2）输出哈夫曼树，及各字符对应的编码。3）编码：利用建好的哈夫曼树，对输入的待发送电文进行编码。同时输入原文及编码串。4）译码：利用建好的哈夫曼树，对输入的已接收电文进行译码。同时输入编码串及原文。二、算法的基本思想算法的主要思路是：（1）定义结构体存储赫夫曼树的结点类型（2）定义函数strcpy(char*S1,char*S2)将字符串S2复制到S1（3）定义函数Select(HuffmanTreeHT,intt,int&s1,int&s2)在HT[1]到HT[t-1]中找出权值最小的两个S1和S2（4）定义函数HuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn)根据各个字符的权值构造赫夫曼树HT，将对应的赫夫曼编码存储在HC中（5）定义函数InitHuff_T(HuffmanTree&HT,HuffmanCode&HC,charch[],int&n)初始化赫夫曼数，要求用户输入字符和相应权值（6）定义函数Encoding(HuffmanTree&HT,HuffmanCode&HC,charch[])根据赫夫曼编码将用户指定的文件中的字符编成相应的编码,并将所得编码存储到用户指定文件（7）定义函数Decoding(HuffmanTreeHT,charch[],intn)对指定的存储由赫夫曼编码表示的信息的文件进行译码，翻译成相应的字符表示，并存储到指定文件（8）定义函数ReadHuff_T(HuffmanTree&HT,HuffmanCode&HC,charch[],int&n)从文件读取赫夫曼树（9）定义主函数main()实现相应的功能三、测试数据首先运行程序：请输入你要选择的功能1.初始化2.编码3.译码4.退出1请输入编码字符集的大小n:4请输入第1个字符和该字符的权值w:a1请输入第2个字符和该字符的权值w:b3请输入第3个字符和该字符的权值w:c2请输入第4个字符和该字符的权值w:d64a110b10c111d0请输入你要选择的功能1.初始化2.编码3.译码4.退出这时在工程目录下建立文件a.txt，内容为：abcda继续执行程序2请输入所要进行编码的文件的文件名:a.txt请输入编码后编码表示的信息所存储到的文件的文件名:c.txt110101110110字符无法识别，程序将退出。Pressanykeytocontinue此时c.txt文件下的内容为：110101110110这时我们将c.txt重命名为CodeFile请输入你要选择的功能1.初始化2.编码3.译码4.退出3请输入所要译的文件名:CodeFile请输入译后的字符存储到的文件的文件名:1.txtabcda此时文件1.txt的内容为：abcda四、源程序及系统文件使用说明#includestdio.h#includestdlib.h#defineYes1//当程序已经调用过初始化赫夫曼树的InitHuff_T()函数，或已从htfTree文件读取过，则将Init_Mode置为Yes，否则为No#defineNo0typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//存储赫夫曼树的结点类型typedefchar**HuffmanCode;//用于存储字符集中各个字符相应的赫夫曼编码voidstrcpy(char*S1,char*S2){//将字符串S2复制到S1inti=0;while(S2[i]!='\0'){S1[i]=S2[i];i++;}S1[i]='\0';}voidSelect(HuffmanTreeHT,intt,int&s1,int&s2){//在HT[1]到HT[t-1]中找出权值最小的两个S1和S2inti=1;s1=s2=0;HT[0].weight=65535;while(i=t){//遍历查找权值最小的结点S1if(HT[i].parent==0&&HT[i].weightHT[s1].weight)s1=i;i++;}i=1;while(i=t){//遍历查找除S1外权值最小的结点S2if(i!=s1&&HT[i].parent==0&&HT[i].weightHT[s2].weight)s2=i;i++;}}intHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){//根据各个字符的权值构造赫夫曼树HT，将对应的赫夫曼编码存储在HC中ints1,s2,m,i,start;unsignedintc,f;HTNode*p;char*cd;if(n=1)return0;m=2*n-1;//赫夫曼树的总结点树为mHT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//申请存储赫夫曼树的空间for(p=HT+1,i=1;i=n;++i,++p,++w){//将各个叶子结点的weight赋以相应的权值，parent,lchild,rchild均赋为0p-weight=*(w+1);p-parent=p-lchild=p-rchild=0;}for(;i=m;++i,++p){//将各个非叶子结点的weight,parent,lchild,rchild均赋为0p-weight=p-parent=p-lchild=p-rchild=0;}for(i=n+1;i=m;++i){//构造赫夫曼树，给各个非叶子结点赋值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*));//申请空间，用于存储指向存储各个字符相应赫夫曼编码的字符数组的指针cd=(char*)malloc(n*sizeof(char));//申请用于求赫夫曼编码cd[n-1]='\0';//编码结束符for(i=1;i=n;++i){//逐个字符求赫夫曼编码start=n-1;//编码在数组cd[]中的最前位置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[]数组的start位置到n-1位置复制给HC[i]}free(cd);//释放空间return1;}voidInitHuff_T(HuffmanTree&HT,HuffmanCode&HC,charch[],int&n){//初始化赫夫曼数，要求用户输入字符和相应权值inti=1,w[100],tem,j;chara[20];FILE*save;printf(请输入编码字符集的大小n:);scanf(%d,&n);//获取用户输入的字符集个数while(i=n){//获取用户输入的字符和相应权值，分别存储在ch[]和w[]数组中printf(请输入第%d个字符和该字符的权值w:,i);fflush(stdin);scanf(%c%d,&ch[i],&w[i]);i++;}ch[i]='\0';HuffmanCoding(HT,HC,w,n);//根据用户的输入，生成赫夫曼数及各个字符相应的赫夫曼编码，分别存在HT树和HC中if((save=fopen(htfTree,w))==NULL){//打开用于存储赫夫曼树的文件printf(Openfilefail......\n);exit(0);}tem=n;//接下来的14行是将字符集大小转换成字符形式写入到文件中j=0;while(tem!=0){tem=tem/10;j++;}tem=n;a[j]='\0';while(tem!=0){a[j-1]=(char)(tem%10+48);tem=tem/10;j--;}fputs(a,save);printf(%d\n,n);//向屏幕输出字符集大小nfputc('\n',save);for(i=1;i=n;i++){//分别向文件和屏幕输出各个字符和相应的赫夫曼编码fputc(ch[i],save);printf(%c\t,ch[i]);fputc('\t',save);fputs(HC[i],save);printf(%s\n,HC[i]);fputc('\n',save);}for(i=1;i=2*n-1;i++){//将赫夫曼树各个结点的parent,lchild,rchild分别写入到文件中tem=HT[i].parent;//将i结点的parent转换成字符并写入到文件中if(tem==0){fputc(tem+48,save);fputc('',save);}else{j=0;while(tem!=0){tem=tem/10;j++;}tem=HT[i].parent;a[j]='\0';while(tem!=0){a[j-1]=(char)(tem%10+48);tem=tem/10;j--;}fputs(a,save);fputc('',save);}tem=HT[i].lchild;//将i结点的lchild转换成字符并写入到文件中if(tem==0){fputc(tem+48,save);fputc('',save);}else{j=0;while(tem!=0){tem=tem/10;j++;}tem=HT[i].lchild;a[j]='\0';while(tem!=0){a[j-1]=(char)(tem%10+48);tem=tem/10;j--;}fputs(a,save);fputc('',save);}tem=HT[i].rchild;//将i结点的rchild转换成字符并写入到文件中if(tem==0){fputc(tem+48,save);fputc('\n',save);}else{j=0;while(tem!=0){tem=tem/10;j++;}tem=HT[i].rchild;a[j]='\0';while(tem!=0){a[j-1]=(char)(tem%10+48);tem=tem/10;j--;}fputs(a,save);fputc('\n',save);}}fclose(save);}voidEncoding(HuffmanTree&HT,HuffmanCode&HC,charch[]){//根据赫夫曼编码将用户指定的文件中的字符编成相应的编码,并将所得编码存储到用户指定文件FILE*ToBeTran,*CodeFile;charToBeTran_Name[100],CodeFile_Name[100];//存储用户指定文件的文件名inti;charc;