数据结构实验报告

1、福建农林大学计算机与信息学院计算机类课程设计报告课程名称：算法与数据结构课程设计题目：哈夫曼编/译码器姓 名：系：专 业：年 级：学 号：指导教师：职 称：年 月 日福建农林大学计算机与信息学院计算机类课程设计结果评定评语：成绩：指导教师签字：任务下达日期：评定日期：目录1、课程设计目的12、课程设计要求13、课程设计方案14、课程设计内容24.1模块的设计及介绍24.2系统运行环境74.3主要模块程序流程图74.4源程序114.5程序调试与测试结果164.6调试分析175、总结17参考文献18哈夫曼编/译码器1、课程设计目的Ø 通过实验，有助于消化课本中的内容，更好的掌握知识，可以

2、逐步积累调试C程序的经验并逐渐培养我们的编程能力，用计算机解决实际问题的能力。2、课程设计要求（1） 从硬盘的一个文件里读出一段英语文章；（2） 统计这篇文章中的每个字符出现的次数；（3）以字符出现字数作为权值，构建哈夫曼树，并将哈夫曼树的存储结构的初态和终态进行输出；（4） 对每个字符进行编码并将所编码写入文件然后对所编码进行破译。3、课程设计方案设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作权，构造一棵哈夫曼树，此构造过程称为哈夫曼编码。本程序包含四个功能：Ø 从硬盘读取字符串Ø 建立哈夫曼树Ø 输出哈夫曼树的存储结构的初态和终态Ø 输

3、出各种字符出现的次数以及哈夫曼编码的译码等。4、课程设计内容4.1模块的设计及介绍从硬盘读取字符串fileopen(参数) 实现命令； 打印输出；建立HuffmanTree通过三个函数来实现：void select(参数) 初始化； for 接受命令； 处理命令；说明：在ht1.k中选择parent为0且权值最小的两个根结点的算法int jsq(参数) 初始化； for 接受命令； 处理命令； 说明：统计字符串中各种字母的个数以及字符的种类void ChuffmanTree() 初始化； for 接受命令； 处理命令； 输出字符统计情况；说明：构造哈夫曼树输出哈夫曼树的存储结构的初态和终态分别

4、调用print1()和print2()来实现void print1(参数) 初始化； 输出初态；说明：输出哈夫曼树的初态void print2(参数) for 输出终态；说明：输出哈夫曼树的终态哈夫曼编码和译码void HuffmanEncoding(参数) 定义变量； 处理命令；说明：哈夫曼编码char*decode(参数) 定义变量；while接受命令；处理命令；说明：哈夫曼译码4.2系统运行环境Ø 操作系统：Windows XP Ø 运行软件：VC+ 6.04.3主要模块程序流程图主函数流程图：结束统计字符种类及频率字符总数num建立哈夫曼树哈夫曼编码哈夫曼译码打开文

5、件？开始否是流程图注释：该图比较简单，主要是调用各个函数模块，首先代开已经存在的文件，然后统计总的字符数以及出现的各个字符和频率。然后才开始建立哈夫曼树，接着在哈夫曼树的基础上对其进行编码，编码之后才是译码。最后输出结束。构造哈夫曼树：开始结束第i个结点权值i=num?创建哈夫曼树输出字符统计情况第i个根结点i=2*num-1?i=num?否是否是否是流程图注释：该图是表示构造哈夫曼树的过程。首先输入num个叶结点的权值，当i=num是循环结束。然后进行哈夫曼树的构建，当i=2*num-1是循环结束。最后输出所得到的字符统计情况。哈夫曼编码：结束开始Tp.lchlid=c?i<=num?

6、Cd-start=0,start=numCd-start=0Cd-start=1否否是是流程图解释：该流程图表四哈夫曼编码情况。首先初始化，Cd-start=0,start=num。然后进行编码，使用了一个三目运算符。cd-start=(Tp.lchild=c) ? '0' : '1'，即当cd-start=Tp.lchild= =c时，cd-start=0；当cd-start=Tp.lchild！= =c时，cd-start=1。这个编码循环一直到i=num时结束。4.4源程序#include <stdio.h>#include <strin

7、g.h>#include <stdlib.h>#include<fstream.h>/*类型相关变量的定义*#define n 100 /叶子结点数#define m 2*n-1 /哈夫曼树中的结点树typedef structchar ch;char bits9; /存放编码位串int len; CodeNode;typedef CodeNode HuffmanCoden+1;typedef struct int weight; /权值int lchild,rchild,parent; /左右孩子几双亲指针 HTNode;typedef HTNode Huffm

8、anTreem+1; /0号单元不用int num;/*建立HuffmanTree*void select(HuffmanTree T,int k,int &s1,int &s2) /在ht1.k中选择parent为0且权值最小的两个根结点的算法/其序号为s1和s2int i,j;int min1=101; for(i=1;i<=k;i+)if(Ti.weight<min1 &&Ti.parent=0) j=i;min1=Ti.weight;s1=j;min1=32767;for (i=1;i<=k;i+)if(Ti.weight<min

9、1 && Ti.parent=0 && i!=s1)j=i;min1=Ti.weight;s2=j;int jsq(char *s,int cnt,char str) /统计字符串中各种字母的个数以及字符的种类int i,j,k; char *p;int temp27; for(i=1;i<=26;i+)tempi=0; for(p=s; *p!='0'p+) /统计各种字符的个数 if(*p>='A'&&*p<='Z')k=*p-64;tempk+;for(i=1,j=0;i&l

10、t;=26;+i)if(tempi!=0 ) j+;strj=i+64; /送对应的字母到数组中cntj=tempi; /存入对应字母的权值return j; /j是输入字母总数void ChuffmanTree(HuffmanTree HT,HuffmanCode HC,int cnt,char str) /构造哈夫曼树HTint i,s1,s2;for(i=1;i<=2*num-1;i+)/初始化HT，2*num-1是指哈夫曼树所有的结点数目HTi.lchild=0;HTi.rchild=0;HTi.parent=0;HTi.weight=0;for(i=1;i<=num;i+

11、) /输入num个叶结点的权值HTi.weight=cnti;for(i=num+1;i<=2*num-1;i+) /在ht1.k中选择parent为0且权值最小的两个根结点/其序号为s1和s2/i为双亲select(HT,i-1,s1,s2);HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1; HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;for(i=0;i<=num;i+) /输入字符集的中字符HCi.ch=stri; /字符的种类i=1;while(i<=num)printf(&quo

12、t;字符%c次数:%dn",HCi.ch,cnti+);/*生成Huffman编码并写入文件*void HuffmanEncoding(HuffmanTree T,HuffmanCode H) /根据哈夫曼树T求哈夫曼编码Hint c,p,i; /c和p分别指示t中孩子和双亲char cdn; /临时存放编码串int start; /指示码在cd中的起始位置cdnum='0' /最后一位（第num个）放上串结束符for(i=1;i<=num;+i)start=num; /初始位置c=i; /从叶子结点ti开始上溯while(p=Tc.parent)>0)

13、/直至上溯到tc是树根为止 /若tc是tp的左孩子,则生成0;否则生成底码cd-start=(Tp.lchild=c) ? '0' : '1'c=p;strcpy(Hi.bits,&cdstart);Hi.len=num-start;void coding(HuffmanCode HC ,char *str) /对str所代表的字符串进行编码 并写入文件int i,j;FILE *fp;fp=fopen("codefile.txt","w");while(*str)for(i=1;i<=num;i+)if(H

14、Ci. ch=*str)for(j=0;j<=HCi.len;j+)fputc(HCi.bitsj,fp);break;str+;fclose(fp);/*电文译码*char*decode(HuffmanCode HC) /代码文件codefile.txt的译码FILE *fp;char str254; /假设远文本文件不超过254个字符char *p;static char cdn+1;int i,j,k=0,cjs;fp=fopen("codefile.txt","r");/一只读的方式打开文本文档codefile.txtwhile(!feof

15、(fp)/feof(fp)判断文件是否真正结束，feof(fp)=1时文件结束cjs=0;for(i=0;i<num && cjs=0 && !feof(fp);i+)cdi=' 'cdi+1='0'cdi=fgetc(fp);/数组接受从fp指针所指向文件中读入的一个字符 for(j=1;j<=num;j+)if(strcmp(HCj.bits,cd)=0)/haffman编码和密码译码相比较strk=HCj.ch;k+;cjs=1;break; strk='0'p=str;return p;/*输出

16、HuffmanTree存储结构*void print1(HuffmanTree HT)int x; for(x=1;x<=2*num-1;x+) HTx.parent=0;HTx.lchild=0;HTx.rchild=0;printf("%11d %dt %dt %dn",HTx.weight,HTx.parent,HTx.lchild,HTx.rchild);printf("-n"); void print2(HuffmanTree HT)int k;for(k=1;k<=2*num-1;k+) printf(" %dt %dt

17、 %dt %dn",HTk.weight,HTk.parent,HTk.lchild,HTk.rchild);printf("-n"); void DhuffmanTree(HuffmanTree HT,int cnt,char str) /构造哈夫曼树dhtint i;char x;for(i=1;i<=num;i+) /输入num个叶结点的权值HTi.weight=cnti;if (i>=stri)HTi.weight=(char)'*' ;/*打开文本*int fileopen(char string)FILE *fp; if(f

18、p=fopen("E:数据结构课程设计file1.txt","r")=NULL)printf("不能打开文件!n");exit(1);while(fgets(string,100,fp)!=NULL) printf("%sn",string);fclose(fp);return 0;/*主调函数*void main() char string100;char *s,str27;int cnt27; HuffmanTree HT;HuffmanCode HC; printf("读出文本为：n");

19、 fileopen(string);num=jsq(string,cnt,str); /统计字符的种类及各类字符出现的频率DhuffmanTree(HT,cnt,str);printf("-n");printf("HuffmanTree的初态:n");print1(HT);ChuffmanTree(HT,HC,cnt,str); /建立哈夫曼树 HuffmanEncoding(HT,HC); /生成哈夫曼编码coding(HC,string); /建立电文哈夫曼编码文件printf("-n");printf("HuffmanTree的终态:n");print2(HT);s=decode(HC); /读编码文件译码printf("译码后的字符串:n");printf("%sn",s); /输出译码后的字符串printf("*n");4.5程序调试与测试