数据结构哈夫曼编码加密文件

学号《数据结构》课程设计报告题目：哈夫曼编码加密文件专业：班级：姓名：学号：指导教师：成绩：计算机与信息工程系2014年10月30日2014-2015学年第一学期计算机与信息工程系《数据结构》课程设计报告目录1问题描述.................................................................................12需求分析..................................................................................12.1数据结构.............................................12.2主要函数.............................................13概要设计............................................................................13.1可满足输入输出的形式及限制............................23.2所用数据类型的定义及含义..............................23.3各函数之间的调用关系..................................23.4各个模块之间的主要关系...............................24详细设计........................................24.1流程图................................................34.2源代码................................................45测试情况.......................................106测试结果.......................................117总结与提高.....................................15参考文献.........................................16计算机与信息工程系《数据结构》课程设计报告11问题描述用哈夫曼编码，将输入的文字，或者文件中的文字进行编码，并输出加密后的文字。2需求分析2.1数据结构此函数中运用到的数据结构知识就是哈夫曼树的建立以及遍历，建立主要就是每一次选择权值最小的两个数并将其求和，然后用他们的和代替这两个数，再进行求两个最小值，最后构成一个哈夫曼数；遍历是采用从叶子结点开始向根节点确定唯一的路径。掌握现实复杂问题的分析建模和解决方法（包括问题描述、系统分析、设计建模、代码实现、结果分析等）；提高利用计算机分析解决综合性实际问题的基本能力。2.2主要函数（1）voidCrtHuffmantree(HuffmanTree&ht,intw[],intn)，功能是建立一个哈夫曼树；（2）voidCrtHuffmanCode(HuffmanTreeht,HuffmanCodehc,intn)，功能是计算哈夫曼编码；（3）voiddianwen(intcount[],charalldata[])，功能是统计输入电文的字母种类以及频率；（4）intfcount(charalldata[],chardata[],intcount[])，功能是统计打开文件中出现的字母的种类以及频率；（5）voidshowtime()，功能是查看系统当前的时间；（6）intsearch(charch,chardata[],intn)，查询电文中的每一个字母所对应得哈夫曼编码的下标；（7）voidPrintf(HuffmanCode&hc,intn,chardata[],charalldata[],intcount[])，功能是输出每一个字母所对应的哈夫曼编码；（8）voidshowall(HuffmanCodehc,charalldata[],intcount[],chardata[],intn)，功能是输出经过加密后的密文。（9）voidshowMenu();功能是输出菜单列表3概要设计计算机与信息工程系《数据结构》课程设计报告23.1可满足输入输出的形式及限制本程序支持字符编码解码，程序运行中有一个文件，用于存储加密字符。支持用户在屏幕查看文件内容。程序在用户输入数据前，会输出相应的提示，在用户输入超出范围或者输入错误时，会提示重新输入或者提示错误并退出。使用菜单操作，提示用户相应的操作，用户指定文件对其进行加密或解密，在屏幕上可以看到文件内容。3.2所用数据类型的定义及含义此程序运用了整形、实型、字符型、指针、数组、结构体。下面是全局（举例）：typedefstruct{intweight;intparent,Lchild,Rchild;}HTNode,HuffmanTree[M+1];//构造赫夫曼树结点的结构体#defineN27//定义最大叶子结点个数#defineM2*N-1typedefchar*HuffmanCode[N+1];//存储哈夫曼编码串的头指针intcount[27];//用于存储所有字母出现的频率，count[0]用于存储字母的总个数chardata[N];//用于存储所出现过的字母3.3各函数之间的调用关系主函数中是菜单打印（show()）和showtime()，各模块套用和调用关系如下：主函数中调用chiocel(),openfile(),input(),子函数中调用CrW(data,w,count)【fcount(alldata,data,count)】,CrtHuffmantree(ht,w,n),CrtHuffmanCode(ht,hc,n),Printf(hc,n,data,alldata,count),showall(hc,alldata,count,data,n).3.4各个模块之间的主要关系该程序的功能主要是实现哈夫曼编码加密文件，各个模块之间的关系是相互联系的。首先，主函数包含了所有的子函数。主函数是整个程序的核心。子函数之间也是有联系的，对文件加密，先创建一个文件。因此文件建立是非常重要的，然后就可以进行编码，查看加密结果并退出。计算机与信息工程系《数据结构》课程设计报告34详细设计4.1流程图主程序main显示系统时间shoutime（）给用户提供选择方式choice1（）显示界面告诉用户程序名称show（）输入电文进行加密input()退出程序打开文件进行加密openfile()统计输入文件中字母的出现频率CrW(datd,w,count)将输入文件中的电文进行哈夫曼编码CrtHuffmanCode(ht,hc,n)将输入文件中的电文创建成哈夫曼树CrtHuffmantree(ht,w,n)对输入文件中的文字进行哈夫曼加密showall(hc,alldata,count,data,n)输出每一个字母所对应的哈夫曼编码printf(hc,n,data,alldata,count)计算机与信息工程系《数据结构》课程设计报告44.2源代码#includestdio.h#includestdlib.h#includetime.h#includestring.h#defineN27//定义最大叶子结点个数#defineM2*N-1typedefstruct{intweight;//定义哈夫曼结构体intparent;intLChild;intRChild;}HTNode,HuffmanTree[M+1];//0号单元不用typedefchar*HuffmanCode[N+1];//存储哈夫曼编码串的头指针//调用系统的时间voidshowtime(){time_tt;tm*tp;t=time(NULL);tp=localtime(&t);printf(\n\n\t\t\t%d/%d/%d\n,tp-tm_mon+1,tp-tm_mday,tp-tm_year+1900);printf(\n\t\t\t%d:%d:%d\n,tp-tm_hour,tp-tm_min,tp-tm_sec);}//**************计算电文中各个英文字母出现的次数*******************voiddianwen(intcount[],charalldata[]){intn,i;printf(〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒);printf(\n\n\n\t\t\t\t请输入电文：\n);fflush(stdin);for(i=0;i27;i++)//将数组计数器初始化count[i]=0;printf(%c,7);alldata[0]=getchar();while(alldata[count[0]]!='\n'){n=(alldata[count[0]]-'a')+1;count[n]++;count[0]++;//所有字母的总个数alldata[count[0]]=getchar();}}voidCrW(chardata[],intw[],intcount[])//存储数据以及权值信息计算机与信息工程系《数据结构》课程设计报告5{inti,j;j=0;for(i=1;i=26;i++){if(count[i]!=0){j++;data[j]=char(i-1+'a');w[j]=count[i];}}w[0]=j;//用于存储字母出现的种类个数}voidselect(HuffmanTree&ht,intn,int&s1,int&s2)//查找一串数字中的两个最小值{inti,t;s1=0;s2=0;ht[0].weight=65535;for(i=1;i=n;i++){if(ht[i].weightht[s1].weight&&ht[i].parent==0){t=s1;s1=i;if(ht[t].weightht[s2].weight){s2=t;}}elseif(ht[i].weightht[s2].weight&&ht[i].parent==0)s2=i;else;}}voidCrtHuffmantree(HuffmanTree&ht,intw[],intn)//创建哈夫曼树{inti,m;ints1,s2;for(i=1;i=n;i++)//初始化叶子结点{ht[i].weight=w[i];ht[i].parent=0;ht[i].LChild=0;ht[i].RChild=0;}m=2*n-1;for(i=n+1;i=m;i++)//初始化其他结点{ht[i].weight=0;ht[i].parent=0;ht[i].LChild=0;ht[i].RChild=0;}for(i=n+1;i=m;i++){select(ht,i-1,s1,s2);ht[i].weight=ht[s1].weight+ht[s2].weight;ht[s1].parent=i;计算机与信息工程系《数据结构》课程设计报告6ht[s2].parent=i;ht[i].LChild=s1;ht[i].RChild=s2;}}//计算哈夫曼编码voidCrtHuffmanCode(HuffmanTreeht,HuffmanCodehc,intn){inti,start,c,p;char*cd;cd=(char*)malloc((n+1)*sizeof(char));cd[n-1]='\0';for(i=1;i=n;i++){start=n-1;c=i;p=ht[i].parent;while(p!=0){--start;if(ht[p].LChild==c)cd[start]='0';else