数据结构课程设计(赫夫曼编码)

1、精选优质文档-倾情为你奉上中南民族大学数据结构课程设计报告姓 名： 康宇 年 级： 2010 学 号： 专 业：计算机科学与技术 指导老师： 宋中山 2013年4月15日实习报告： 赫夫曼编/译码器实习报告题目：为信息收发站写一个赫夫曼码的编/译码系统班级：计科一班 姓名：康宇 学号： 完成日期：2013.4.5 一、 需求分析1、 问题描述：利用赫夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端讲传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。2、

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:印赫夫曼树

3、（Tree Printing）。将已在内存中的赫夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的赫夫曼树写入文件TreePrint中。3、 实现提示：（1） 编码结果以文本方式存储在文件CodeFile中。（2） 用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“Q”为止。二、 概要设计1. 元素类型：typedef structint weigt;/权值int parent,lchild,rchild;/双亲，左孩子，右孩子HTNode,*HuffmanTree

4、;typedef char* HuffmanCode;/存放各个字符的前缀编码2. 本程序包括六个大板块：（1）主程序： int main() 输出菜单；选择功能选项并调用对应的函数； （2）初始化函数： void Initialization(HuffmanTree &ht,FILE *fp) 安全打开文件；输入字符数量以及各字符及其权值；对各节点进行初始化；创建赫夫曼列表；（需要调用Select()函数选择权职最小的两个节点） void Select(HuffmanTree &ht,int i,int &s_1,int &s_2)找出第一个非零结点；找出第二

5、个非零结点；遍历比较找出权值最小的两个节点；（3）编码函数：void Encoding(HuffmanTree &ht,HuffmanCode &hc,FILE *fp1,FILE *fp2)安全打开文件；for:1àn,双亲不为空If(为左孩子)str-start='0'elsestr-start='1'储存各字符的编码；从文件中读取正文；依次遍历正文各字符，显示其编码；（4）译码函数：void Decoding(HuffmanTree &ht,HuffmanCode &hc,FILE *fp1,FILE *fp2)安

6、全打开文件；While（成功读取字符）遍历目前的编码中是否有对应的字符；if(有)输出该字符；else跳到循环体首；（再次读入一个字符再判断）（5）印代码文件：void Print(FILE *fp1,FILE *fp2)安全打开文件；从文件中读取字符，50个一行输出；（6）印赫夫曼树：void Treeprinting(HuffmanTree ht)安全打开文件；调用print_tree(ht,root)函数；void print_tree(HuffmanTree ht, int r)if(存在节点)深度+1；递归调用print_tree(ht,htr.rchild);/先输出右子树用深度控

7、制格式；输出对应的字符；递归调用print_tree(ht,htr.lchild);/再输出左子树深度-1三、 详细设计#include <stdio.h>#include <stdlib.h>#include <string.h>typedef structint weigt;int parent,lchild,rchild;HTNode,*HuffmanTree;typedef char* HuffmanCode;/存放各个字符的前缀编码/此全局文件指针用于输出赫夫曼树到对应文件，便于调用递归FILE *TreePrint=NULL;char *s;/存

8、放各字符int *w;/存放各字符的权值int n;int m;int dep=0;/存放各字符的深度void Select(HuffmanTree &ht,int i,int &s_1,int &s_2)/挑选出权值最小的两个结点int j;for(j=1;j<=i;j+)/找出第一个非零结点if(htj.parent=0)s_1=j;break;for(j=s_1+1;j<=i;j+)/找出第二个非零结点if(htj.parent=0)s_2=j;break;for(j=1;j<=i;j+)/遍历出权值最小的两个结点if(htj.parent=0)

9、/必须要判断双亲是否为空if(htj.weigt<hts_1.weigt)s_2=s_1;s_1=j;else if(htj.weigt>hts_1.weigt&&htj.weigt<hts_2.weigt)s_2=j;void Initialization(HuffmanTree &ht,FILE *fp)int i,s1,s2;if(fp=fopen("hfmTree.txt","w")=NULL)/安全打开文件printf("File hfmTree.txt cannot opened.n&quo

10、t;);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;i<n;i+)scanf("%d

11、",&wi);if(n<=1)return;m=2*n-1;/节、结点的个数ht=(HuffmanTree)malloc(m+1)*sizeof(HTNode);for(i=1;i<=n;i+)/分别对各结点赋值hti.weigt=wi-1;hti.parent=hti.lchild=hti.rchild=0;for(i=n+1;i<=m;i+)hti.weigt=hti.parent=hti.lchild=hti.rchild=0;/构建赫夫曼树for(i=n+1;i<=m;i+)Select(ht,i-1,s1,s2);/选出权值最小的叶子节点ht

12、s1.parent=hts2.parent=i;hti.lchild=s1;hti.rchild=s2;hti.weigt=hts1.weigt+hts2.weigt;/构建新结点的权值/输出赫夫曼列表printf("赫夫曼列表为：n");for(i=1;i<=n;i+)/叶子节点fprintf(fp,"t%ct%dt%dt%dt%dn",si,hti.weigt,hti.parent,hti.lchild,hti.rchild);printf("t%ct%dt%dt%dt%dn",si-1,hti.weigt,hti.pare

13、nt,hti.lchild,hti.rchild);for(i=n+1;i<=m;i+)/非叶子节点fprintf(fp,"t t%dt%dt%dt%dn",hti.weigt,hti.parent,hti.lchild,hti.rchild);printf("t t%dt%dt%dt%dn",hti.weigt,hti.parent,hti.lchild,hti.rchild);fclose(fp);void Encoding(HuffmanTree &ht,HuffmanCode &hc,FILE *fp1,FILE *fp2)

14、/编码int i,j,c,f,start;char *str;/用于存放编码char data100;/用于存放文件正文字符if(fp1=fopen("ToBeTran.txt","r")=NULL)printf("File ToBeTran.txt cannot opened.n");exit(1);if(fp2=fopen("CodeFile.txt","w")=NULL)printf("File CodeFile.txt cannot opened.n");exit(1

15、);/根据赫夫曼树得到各字符对应的编码hc=(HuffmanCode)malloc(n+1)*sizeof(char *);str=(char *)malloc(n*sizeof(char);/n个字符中的最长的编码个数为n-1strn-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)/为左子树str-start='0'else/为右子树str-start='1'

16、hci=(char *)malloc(n-start)*sizeof(char);strcpy(hci,&strstart);/赋值对应字符的编码printf("各字符串的编码为：n");for(i=1;i<=n;i+)printf("%sn",hci);/对文件正文进行编码/fscanf(fp1,"%s",data);fgets(data,500,fp1);/读取正文printf("文件正文为：");printf("%s",data);printf("n文件ToBeTr

17、an中的正文编码为：n");for(i=0;i<strlen(data);i+)for(j=0;j<n;j+)if(datai=sj)/依次遍历出正文各字符的编码，并存储到文件中printf("%s",hcj+1);fprintf(fp2,"%s",hcj+1);break;printf("n");free(str);fclose(fp1);fclose(fp2);void Decoding(HuffmanTree &ht,HuffmanCode &hc,FILE *fp1,FILE *fp2)i

18、nt i,j;bool flag;char ch;char *data=(char *)malloc(n*sizeof(char);/临时存放赫夫曼码if(fp1=fopen("CodeFile.txt","r")=NULL)printf("File CodeFile.txt cannot opened.n");exit(1);if(fp2=fopen("TextFile.txt","w")=NULL)printf("File TextFile.txt cannot opened.n&

19、quot;);exit(1);/进行译码printf("文件译码为：n");while(fscanf(fp1,"%c",&ch)!=EOF)/有编码可读取flag=true;/控制循环i=0;while(flag)if(i!=0)fscanf(fp1,"%c",&ch);datai+=ch;datai='0'for(j=1;j<=n;j+)if(!strcmp(data,hcj)/如果找到匹配的字符编码printf("%c",sj-1);fprintf(fp2,"%c

20、",sj-1);flag=false;break;fclose(fp1);fclose(fp2);void Print(FILE *fp1,FILE *fp2)char ch;int sum=0;if(fp1=fopen("CodeFile.txt","r")=NULL)printf("File CodeFile.txt cannot opened.n");exit(1);if(fp2=fopen("CodePrin.txt","w")=NULL)printf("File C

21、odePrin.txt cannot opened.n");exit(1);/从CodeFile中读取出来输出到CodePrin中printf("文件字符为：n");while(fscanf(fp1,"%c",&ch)!=EOF)sum+;printf("%c",ch);fprintf(fp2,"%c",ch);if(sum%50=0)/50个字符一行printf("n");fprintf(fp2,"n");fclose(fp1);fclose(fp2);v

22、oid print_tree(HuffmanTree ht, int r)/左倒置90度输出到文件和终端上if(r)dep+;/控制叶子节点的深度print_tree(ht,htr.rchild);/先输出右子树for(int i=1;i<dep;i+)/控制深度printf("t");fprintf(TreePrint,"t");if(r>n)printf("On");fprintf(TreePrint,"On");elseprintf("%cn",sr-1);fprintf(Tr

23、eePrint,"%cn",sr-1);print_tree(ht,htr.lchild);/再输出左子树dep-;void Treeprinting(HuffmanTree ht)int root;/根结点if(TreePrint=fopen("TreePrint.txt","a")=NULL)/进行数据追加printf("File TreePrint.txt cannot opened.n");exit(1); root=m;printf("赫夫曼树为：n");print_tree(ht,r

24、oot);fclose(TreePrint);/及时关闭文件int main()int choose;FILE *hfmTree=NULL,*ToBeTran=NULL,*CodeFile=NULL,*TextFile=NULL,*CodePrin=NULL;HuffmanTree huftree=NULL;/指针初始化HuffmanCode hufcode=NULL;while(1)printf("n-赫夫曼编/译码器菜单-n");printf("1-Initialization(初始化)n");printf("2-Encoding(编码)n");printf("3-Decoding(译码)n");printf("4-Print(印代码文件)n");printf("5-Treeprinting(印赫夫曼树)n");printf("