中南民族大学数据结构课程设计报告姓名:康宇年级:2010学号:10061014专业:计算机科学与技术指导老师:宋中山2013年4月15日实习报告:赫夫曼编/译码器题目:为信息收发站写一个赫夫曼码的编/译码系统班级:计科一班姓名:康宇学号:10061014完成日期:2013.4.5一、需求分析1、问题描述:利用赫夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端讲传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。2、基本要求:(1)I:初始化(Initialization)。从终端读入字符集大小n,以及n个字符和n个权值,建立赫夫曼树,并将它存于文件hfmTree中。(2)E:编码(Encoding)。利用已建好的赫夫曼树,对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中。(3)D:译码(Decoding)。利用已建好的赫夫曼树将文件CodeFile中的代码进行译码,结果存入文件TextFile中。(4)P:印代码文件(Print)。将文件CodeFile以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。(5)T:印赫夫曼树(TreePrinting)。将已在内存中的赫夫曼树以直观的方式(树或凹入表形式)显示在终端上,同时将此字符形式的赫夫曼树写入文件TreePrint中。3、实现提示:(1)编码结果以文本方式存储在文件CodeFile中。(2)用户界面可以设计为“菜单”方式:显示上述功能符号,再加上“Q”,表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单,直至某次用户选择了“Q”为止。二、概要设计1.元素类型:typedefstruct{intweigt;//权值intparent,lchild,rchild;//双亲,左孩子,右孩子}HTNode,*HuffmanTree;实习报告typedefchar**HuffmanCode;//存放各个字符的前缀编码2.本程序包括六个大板块:(1)主程序:intmain(){输出菜单;选择功能选项并调用对应的函数;}(2)初始化函数:voidInitialization(HuffmanTree&ht,FILE*fp){安全打开文件;输入字符数量以及各字符及其权值;对各节点进行初始化;创建赫夫曼列表;(需要调用Select()函数选择权职最小的两个节点)}voidSelect(HuffmanTree&ht,inti,int&s_1,int&s_2){找出第一个非零结点;找出第二个非零结点;遍历比较找出权值最小的两个节点;}(3)编码函数:voidEncoding(HuffmanTree&ht,HuffmanCode&hc,FILE*fp1,FILE*fp2){安全打开文件;for:1n,双亲不为空If(为左孩子)str[--start]='0';elsestr[--start]='1';储存各字符的编码;从文件中读取正文;依次遍历正文各字符,显示其编码;}(4)译码函数:voidDecoding(HuffmanTree&ht,HuffmanCode&hc,FILE*fp1,FILE*fp2){安全打开文件;While(成功读取字符){遍历目前的编码中是否有对应的字符;if(有)输出该字符;else跳到循环体首;(再次读入一个字符再判断)}}(5)印代码文件:voidPrint(FILE*fp1,FILE*fp2){安全打开文件;从文件中读取字符,50个一行输出;}(6)印赫夫曼树:voidTreeprinting(HuffmanTreeht){安全打开文件;调用print_tree(ht,root)函数;}voidprint_tree(HuffmanTreeht,intr){if(存在节点){深度+1;递归调用print_tree(ht,ht[r].rchild);//先输出右子树用深度控制格式;输出对应的字符;递归调用print_tree(ht,ht[r].lchild);//再输出左子树深度-1}}三、详细设计#includestdio.h#includestdlib.h#includestring.htypedefstruct{intweigt;intparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;//存放各个字符的前缀编码//此全局文件指针用于输出赫夫曼树到对应文件,便于调用递归FILE*TreePrint=NULL;char*s;//存放各字符int*w;//存放各字符的权值intn;intm;intdep=0;//存放各字符的深度voidSelect(HuffmanTree&ht,inti,int&s_1,int&s_2)//挑选出权值最小的两个结点{intj;for(j=1;j=i;j++)//找出第一个非零结点if(ht[j].parent==0){s_1=j;break;}for(j=s_1+1;j=i;j++)//找出第二个非零结点if(ht[j].parent==0){s_2=j;break;}for(j=1;j=i;j++)//遍历出权值最小的两个结点{if(ht[j].parent==0)//必须要判断双亲是否为空{if(ht[j].weigtht[s_1].weigt){s_2=s_1;s_1=j;}elseif(ht[j].weigtht[s_1].weigt&&ht[j].weigtht[s_2].weigt){s_2=j;}}}}voidInitialization(HuffmanTree&ht,FILE*fp){inti,s1,s2;if((fp=fopen(hfmTree.txt,w))==NULL)//安全打开文件{printf(FilehfmTree.txtcannotopened.\n);exit(1);}//输入各字符以及权值printf(请输入字符集大小n:);scanf(%d,&n);s=(char*)malloc(n*sizeof(char));w=(int*)malloc(n*sizeof(int));printf(请输入各字符:\n);getchar();//getchar();//处理换行符//scanf(%s,s);gets(s);printf(请输入各字符对应的权值:\n);for(i=0;in;i++)scanf(%d,&w[i]);if(n=1)return;m=2*n-1;//节、结点的个数ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode));for(i=1;i=n;i++)//分别对各结点赋值{ht[i].weigt=w[i-1];ht[i].parent=ht[i].lchild=ht[i].rchild=0;}for(i=n+1;i=m;i++){ht[i].weigt=ht[i].parent=ht[i].lchild=ht[i].rchild=0;}//构建赫夫曼树for(i=n+1;i=m;i++){Select(ht,i-1,s1,s2);//选出权值最小的叶子节点ht[s1].parent=ht[s2].parent=i;ht[i].lchild=s1;ht[i].rchild=s2;ht[i].weigt=ht[s1].weigt+ht[s2].weigt;//构建新结点的权值}//输出赫夫曼列表printf(赫夫曼列表为:\n);for(i=1;i=n;i++)//叶子节点{fprintf(fp,\t%c\t%d\t%d\t%d\t%d\n,s[i],ht[i].weigt,ht[i].parent,ht[i].lchild,ht[i].rchild);printf(\t%c\t%d\t%d\t%d\t%d\n,s[i-1],ht[i].weigt,ht[i].parent,ht[i].lchild,ht[i].rchild);}for(i=n+1;i=m;i++)//非叶子节点{fprintf(fp,\t\t%d\t%d\t%d\t%d\n,ht[i].weigt,ht[i].parent,ht[i].lchild,ht[i].rchild);printf(\t\t%d\t%d\t%d\t%d\n,ht[i].weigt,ht[i].parent,ht[i].lchild,ht[i].rchild);}fclose(fp);}voidEncoding(HuffmanTree&ht,HuffmanCode&hc,FILE*fp1,FILE*fp2)//编码{inti,j,c,f,start;char*str;//用于存放编码chardata[100];//用于存放文件正文字符if((fp1=fopen(ToBeTran.txt,r))==NULL){printf(FileToBeTran.txtcannotopened.\n);exit(1);}if((fp2=fopen(CodeFile.txt,w))==NULL){printf(FileCodeFile.txtcannotopened.\n);exit(1);}//根据赫夫曼树得到各字符对应的编码hc=(HuffmanCode)malloc((n+1)*sizeof(char*));str=(char*)malloc(n*sizeof(char));//n个字符中的最长的编码个数为n-1str[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)//为左子树str[--start]='0';else//为右子树str[--start]='1';}hc[i]=(char*)malloc((n-start)*sizeof(char));strcpy(hc[i],&str[start]);//赋值对应字符的编码}printf(各字符串的编码为:\n);for(i=1;i=n;i++){printf(%s\n,hc[i]);}//对文件正文进行编码//fscanf(fp1,%s,data);fgets(data,500,fp1);//读取正文printf(文件正文为:);printf(%s,data);printf(\n文件ToBeTran中的正文编码为:\n);for(i=0;istrlen(data);i++){for(j=0;jn;j++)if(data[i]==s[j])//依次遍历出正文各字符的编码,并存储到文件中{printf(%s,hc[j+1]);fprintf(fp2,%s,hc[j+1]);break;}}printf(\n);free(str);fclose(fp1);fclose(fp2);}voidDecoding(HuffmanTree&ht,HuffmanCode&hc,FILE*fp1,FILE*fp2){inti,j;boolflag;charch;char*data=(char*)malloc(n*sizeof(char));//临时存放赫夫曼码if((fp1=fopen(CodeFile.txt,r))==NULL){printf(FileCodeFile.txtcannotopened.\n);exit(1);}if((fp2=fopen(TextFile.txt,w))==NULL){printf(FileTextFile.txtcannotopened.\n);exit(1);}//进行