云南大学软件学院数据结构实验报告五

1、云南大学软件学院 数据结构实验报告 （本实验项目方案受“教育部人才培养模式创新实验区（X）”项目资助） 实验难度： A B C 序号学号姓名成绩123指导教师 （签名）学期：2012秋季学期 任课教师: 实验题目: 树及其应用 小 组 长: 联系电话: 完成提交时间：2012年12月10日云南大学软件学院2012学年 秋季 学期数据结构实验成绩考核表学号： 姓名： 本人承担角色： 小组长 评分项目评分指标分值得分实验构思（10%）1. 实验目的明确52. 实验内容理解透彻、对实验所涉及到的知识点分析到位5实验设计（15%）1. 有对基本数据结构的抽象数据类型定义52. 实验方案设计完整，数据结

2、构、算法选择合理 53.算法结构和程序功能模块之间逻辑清晰、有相应的流程图5实验实现（25%）1. 代码编写规范、风格统一、注释清楚易读 52. 程序运行正常，测试结果正确153. 界面友好、易于操作、有较强的容错性5实验报告撰写（10%）1. 内容详实无缺漏，文字流畅、图表清楚52. 实验结果分析客观、详细，实验体会真实可信，对原实验方案的改进和对实验内容的发散性思考5个人工作量（30%）1. 个人完成工作量152. 个人技术水平103. 团队合作精神5实验运作（10%）1. 有一定用户群52. 应用前景分析5综合得分： （满分100分）指导教师： 年 月 日（注：此表在难度为C时使用，每个

3、成员一份。）云南大学软件学院2012学年 秋季 学期数据结构实验成绩考核表学号： 姓名： 人承担角色： 组员 评分项目评分指标分值得分实验构思（10%）1. 实验目的明确52. 实验内容理解透彻、对实验所涉及到的知识点分析到位5实验设计（15%）1. 有对基本数据结构的抽象数据类型定义52. 实验方案设计完整，数据结构、算法选择合理 53.算法结构和程序功能模块之间逻辑清晰、有相应的流程图5实验实现（25%）1. 代码编写规范、风格统一、注释清楚易读 52. 程序运行正常，测试结果正确153. 界面友好、易于操作、有较强的容错性5实验报告撰写（10%）1. 内容详实无缺漏，文字流畅、图表清楚5

4、2. 实验结果分析客观、详细，实验体会真实可信，对原实验方案的改进和对实验内容的发散性思考5个人工作量（30%）1. 个人完成工作量152. 个人技术水平103. 团队合作精神5实验运作（10%）1. 有一定用户群52. 应用前景分析5综合得分： （满分100分）指导教师： 年 月 日（注：此表在难度为C时使用，每个成员一份。）一、【实验构思（Conceive）】(10%)（本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计、算法等相关知识）本实验要求设计一个哈夫曼编码译码器，要求通过统计一段电文中的各字符频率编写哈夫曼码并进行翻译。首先要解决如何进行哈夫曼编码，然

5、后设计对电文进行编码，最后还有有译码过程。本程序使用二叉树进行哈夫曼编码，使用文本文档保存电文处理。 利用程序设计的相关知识：贯彻设计程序所必需的五大步骤，目标分析-设计算法-程序编写-后期调试-售后服务 的流程完成这个项目。 利用算法设计相关知识：该算法具有有穷性、确定性、可行性、有0个或多个输入、有一个或多个输出、正确性、可读性、健壮性的特性。离散数学相关知识：正确合理使用与或非之间的关系，进行程序分支判断，保证程序正常进行，以及二叉树的使用。二、【实验设计(Design)】(20%)本次实验使用C进行编写，自定义函数7个：void SortHufmtree(hufmtree *tree)

6、/将哈夫曼树n个叶子结点由大到小排序Codetype* HuffmanCode(hufmtree *tree)/哈弗曼编码的生成hufmtree* BuildHuffmanTree(hufmtree *tree)/构建叶子结点已初始化的哈夫曼树hufmtree* CreateHuffmanTreeFromSourceFile()/通过解析源文件建立哈夫曼树hufmtree* Encoding(hufmtree *tree)/对源文件进行编码并保存hufmtree* Decoding(hufmtree *tree)/对存有编码的源文件进行译码并保存主函数为功能选择界面三、【实现描述（Implem

7、ent）】(30%) 主函数显示开始界面，选择相应的功能进行哈夫曼编码译码。本程序提供两种编码规则：统计源文件进行编码和给定权值文件编码。 人性化设计：1. 在输入出现错误时例如功能选择错误时，程序会给出友好的提示；2. 界面友好，容易上手。四、【测试结果（Testing）】(10%)程序开始运行后进行初始化，完成后的界面： 程序正确性测试1：通过源文件求哈夫曼码程序正确性测试2：通过指定权值文件求哈夫曼码程序正确性测试3：编码程序正确性测试4：译码程序健壮性测试1：输入错误的数据时报错程序健壮性测试2：输入错误的数据时报错四、【代码】(10%) #include #include #incl

8、ude #define MAXVAL 10000int flag=0;/哈弗曼树结点数据类型struct hufmtreenodechar data;int weight;/结点权值int parent,lchild,rchild;/父结点，左、右孩子结点;/哈弗曼树数据类型struct hufmtreehufmtreenode *node;/结点数组（根据n的值动态分配）int n;/叶子结点数;/哈弗曼编码数据类型struct Codetypechar *bits;/编码流数组，n为为哈夫曼树中叶子结点的数目，编码的长度不可能超过nint start;/编码实际在编码流数组里的开始位置;/

9、将哈夫曼树n个叶子结点由大到小排序void SortHufmtree(hufmtree *tree)int i,j,k;hufmtreenode temp;if (tree=NULL)return;for (i=0;in;i+)k=i;for(j=i+1;jn;j+)if (tree-nodej.weighttree-nodek.weight)k=j;if (k!=i)temp=tree-nodei;tree-nodei=tree-nodek;tree-nodek=temp;/哈弗曼编码的生成Codetype* HuffmanCode(hufmtree *tree)int i,j,p,k;Co

10、detype *code;if (tree=NULL)return NULL;code=(Codetype*)malloc(tree-n*sizeof(Codetype);for (i=0;in;i+)if(flag=1)printf(%c ,tree-nodei.data);/打印字符信息codei.bits=(char*)malloc(tree-n*sizeof(char);codei.start=tree-n-1;j=i;p=tree-nodei.parent;while(p!=-1)if (tree-nodep.lchild=j)codei.bitscodei.start=0;else

11、codei.bitscodei.start=1;codei.start-;j=p;p=tree-nodep.parent;if (flag=1)for (k=codei.start+1;kn;k+)/打印字符编码printf(%c,codei.bitsk);printf(n);return code;/构建叶子结点已初始化的哈夫曼树hufmtree* BuildHuffmanTree(hufmtree *tree)/tree中所有叶子结点已初始化int i,j,p1,p2,m;int small1,small2;m=2*(tree-n)-1;for (i=tree-n;inodei.paren

12、t=-1;tree-nodei.lchild=-1;tree-nodei.rchild=-1;tree-nodei.weight=0;for (i=tree-n;im;i+)/构建哈夫曼树small1=small2=MAXVAL;for (j=0;jnodej.parent=-1 & tree-nodej.weightnodej.weight;p1=j;for (j=0;jnodej.parent=-1 & tree-nodej.weightnodej.weight;p2=j;tree-nodep1.parent=tree-nodep2.parent=i;tree-nodei.weight=t

13、ree-nodep1.weight+tree-nodep2.weight;tree-nodei.lchild=p1;tree-nodei.rchild=p2;return tree;/通过解析源文件建立哈夫曼树hufmtree* CreateHuffmanTreeFromSourceFile()FILE *textfile,*datafile;char ch,sourcefilename100;int i,j=0,n=0;int count128; /用于统计字符在源文件中出现的次数，27表示26个英文字母和1个空格字符hufmtree *tree;/打开一个源文件printf(n请输入源文件

14、所在路径:n);scanf(%s,sourcefilename);if (textfile=fopen(sourcefilename,r)=NULL)printf(n找不到文件%sn,sourcefilename);return NULL;for(i=0;i128;i+)counti=0;/对源文件中各字符的个数统计ch=fgetc(textfile);while(!feof(textfile)for(i=0;i128;i+)if (ch=char(i)counti+;break;ch=fgetc(textfile);/将统计结果写入新建的权值文件data.txt中,方便以后使用，并构建哈夫曼

15、树datafile=fopen(data.txt,w);for (i=0;inode=(hufmtreenode*)malloc(2*n-1)*sizeof(hufmtreenode);tree-n=n;printf(n源文件权值信息已保存到data.txt文件中。n); for(i=0;inodej.data=char(i);tree-nodej.weight=counti;tree-nodej.parent=-1;tree-nodej.lchild=-1;tree-nodej.rchild=-1;j+;SortHufmtree(tree);BuildHuffmanTree(tree);fc

16、lose(textfile);fclose(datafile);printf(n哈夫曼树建立完毕n);return tree;/通过读取权值文件建立哈夫曼树hufmtree* CreateHuffmanTreeFromDataFile()FILE *datafile;int i,n,ch;hufmtree *tree;char datafilename100;printf(请输入权值文件路径：n); scanf(%s,datafilename);if (datafile=fopen(datafilename,r)=NULL)printf(n找不到文件%sn,datafilename);retu

17、rn NULL;/哈夫曼树初始化fscanf(datafile,%d,&n);tree=(hufmtree*)malloc(sizeof(hufmtree);tree-node=(hufmtreenode*)malloc(2*n-1)*sizeof(hufmtreenode);tree-n=n;for (i=0;i48&chnodei.data= ; tree-nodei.weight=ch-48;fgetc(datafile);/接收换行符 else if(ch=n) tree-nodei.data=n; fscanf(datafile,%dn,&tree-nodei.weight); fg

18、etc(datafile);/接收换行符 else tree-nodei.data=char(ch); fscanf(datafile,%dn,&tree-nodei.weight); tree-nodei.parent=-1;tree-nodei.lchild=-1;tree-nodei.rchild=-1;fclose(datafile);/哈夫曼树构建SortHufmtree(tree);BuildHuffmanTree(tree);printf(哈夫曼树成功建立！n);return tree;/对源文件进行编码并保存hufmtree* Encoding(hufmtree *tree)F

19、ILE *textfile,*codefile;char ch,sourcefilename50;int i,j;Codetype *code;if (tree=NULL)/如果内存中尚未建立哈夫曼树 printf(尚未建立哈夫曼编码树，请先建立！n); return NULL;/读取源文件printf(n请输入源文件所在路径:n);scanf(%s,sourcefilename);if (textfile=fopen(sourcefilename,r)=NULL)printf(n找不到文件%sn,sourcefilename);return NULL;/编码code=HuffmanCode(

20、tree);/将源文件中各字符编码并写入CodeFile临时文件 codefile=fopen(CodeFile.txt,w);fseek(textfile,0,SEEK_SET);ch=fgetc(textfile);while (!feof(textfile)for(i=0;in;i+)if (ch=tree-nodei.data)for(j=codei.start+1;jn;j+)fputc(codei.bitsj,codefile);break; if (i=tree-n)/在哈夫曼树树中找不到与文本内容里对应的字符printf(n字符%c不在哈夫曼树中，不能正确编码。n,ch);ch

21、=fgetc(textfile);fclose(codefile);/提示成功信息printf(n编码成功!n);fclose(textfile);textfile=fopen(sourcefilename,w);/拷贝临时文件内容到源文件 codefile=fopen(CodeFile.txt,r);ch = fgetc(codefile);while(!feof(codefile)fputc(ch,textfile);ch = fgetc(codefile);fclose(textfile);fclose(codefile);remove(codeFile.txt);/移除临时文件Code

22、File return tree;/对存有编码的源文件进行译码并保存hufmtree* Decoding(hufmtree *tree)FILE *codefile,*decodefile;char ch,codefilename100;int i;if (tree=NULL)/如果尚未建立哈夫曼树printf(尚未建立哈夫曼编码树，请先建立！n); return NULL;/打开编码文件printf(n请输入代码文件所在路径:n);scanf(%s,codefilename);if (codefile=fopen(codefilename,r)=NULL)printf(n找不到文件%sn,c

23、odefilename);return NULL;/进行译码并将译文写入DecodeFile临时文件 decodefile=fopen(DecodeFile.txt,w);fseek(codefile,0,SEEK_SET);ch=fgetc(codefile); while(!feof(codefile)for(i=2*tree-n-2;tree-nodei.lchild=0 & tree-nodei.rchild=0 & ch!=EOF;)if(ch=0)i = tree-nodei.lchild;else if(ch=1)i = tree-nodei.rchild;elseprintf(

24、n存在异常字符%c，不能正确译码。n,ch);return 0;if (i=-1)/在哈夫曼树中找不到对应叶子结点printf(n编码与当前哈夫曼树结构不相符，不能正确译码。n,ch);fclose(decodefile);remove(DecodeFile.txt);/移除临时文件DecodeFilereturn 0;ch=fgetc(codefile);if (tree-nodei.lchild=0 & tree-nodei.rchild=0)/寻找叶子结点的过程中突然读到了文件尾printf(n代码文件编码内容不完整，不能完整译码。n,ch);fclose(decodefile); re

25、move(DecodeFile.txt);/移除临时文件DecodeFilereturn 0;fputc(tree-nodei.data,decodefile);fclose(decodefile);/提示成功信息printf(nn译码成功!n);fclose(codefile);codefile=fopen(codefilename,w);/拷贝临时文件内容到源文件 decodefile=fopen(DecodeFile.txt,r);ch = fgetc(decodefile);while(!feof(decodefile)fputc(ch,codefile);ch = fgetc(decodefile);fclose(codefile);fclose(dec