云南大学软件学院大数据结构实验报告材料五
- 格式：doc
- 大小：416.50 KB
- 文档页数：18
云南大学软件学院数据结构实验报告（本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）实验难度： A □ B □ C序号学号成绩1 201111202 201111203指导教师（签名）学期：2012秋季学期任课教师:实验题目: 树及其应用小组长:联系:完成提交时间：2012年12月10日大学软件学院2012学年秋季学期《数据结构实验》成绩考核表学号： 20111120 ：本人承担角色：小组长综合得分：（满分100分）指导教师：年月日（注：此表在难度为C时使用，每个成员一份。
）大学软件学院2012学年秋季学期《数据结构实验》成绩考核表学号： 20111120 ：人承担角色：组员综合得分：（满分100分）指导教师：年月日（注：此表在难度为C时使用，每个成员一份。
）一、【实验构思（Conceive）】(10%)（本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计、算法等相关知识）本实验要求设计一个哈夫曼编码译码器，要求通过统计一段电文中的各字符频率编写哈夫曼码并进行翻译。
首先要解决如何进行哈夫曼编码，然后设计对电文进行编码，最后还有有译码过程。
本程序使用二叉树进行哈夫曼编码，使用文本文档保存电文处理。
利用程序设计的相关知识：贯彻设计程序所必需的五大步骤，目标分析->设计算法->程序编写->后期调试->售后服务的流程完成这个项目。
利用算法设计相关知识：该算法具有有穷性、确定性、可行性、有0个或多个输入、有一个或多个输出、正确性、可读性、健壮性的特性。
离散数学相关知识：正确合理使用与或非之间的关系，进行程序分支判断，保证程序正常进行，以及二叉树的使用。
二、【实验设计(Design)】(20%)本次实验使用C进行编写，自定义函数7个：void SortHufmtree(hufmtree *tree){//将哈夫曼树n个叶子结点由大到小排序Codetype* HuffmanCode(hufmtree *tree){//哈弗曼编码的生成hufmtree* BuildHuffmanTree(hufmtree *tree){//构建叶子结点已初始化的哈夫曼树hufmtree* CreateHuffmanTreeFromSourceFile(){//通过解析源文件建立哈夫曼树hufmtree* Encoding(hufmtree *tree){//对源文件进行编码并保存hufmtree* Decoding(hufmtree *tree)//对存有编码的源文件进行译码并保存主函数为功能选择界面三、【实现描述（Implement）】(30%)主函数显示开始界面，选择相应的功能进行哈夫曼编码译码。
本程序提供两种编码规则：统计源文件进行编码和给定权值文件编码。
人性化设计：1. 在输入出现错误时例如功能选择错误时，程序会给出友好的提示；2. 界面友好，容易上手。
四、【测试结果（Testing）】(10%)程序开始运行后进行初始化，完成后的界面：程序正确性测试1：通过源文件求哈夫曼码程序正确性测试2：通过指定权值文件求哈夫曼码程序正确性测试3：编码程序正确性测试4：译码程序健壮性测试1：输入错误的数据时报错程序健壮性测试2：输入错误的数据时报错四、【代码】(10%)#include <stdio.h>#include <conio.h>#include <stdlib.h>#define MAXVAL 10000int flag=0;//哈弗曼树结点数据类型struct hufmtreenode{char data;int weight;//结点权值int parent,lchild,rchild;//父结点，左、右孩子结点};//哈弗曼树数据类型struct hufmtree{hufmtreenode *node;//结点数组（根据n的值动态分配）int n;//叶子结点数};//哈弗曼编码数据类型struct Codetype{char *bits;//编码流数组，n为为哈夫曼树中叶子结点的数目，编码的长度不可能超过nint start;//编码实际在编码流数组里的开始位置};//将哈夫曼树n个叶子结点由大到小排序void SortHufmtree(hufmtree *tree){int i,j,k;hufmtreenode temp;if (tree==NULL)return;for (i=0;i<tree->n;i++){k=i;for(j=i+1;j<tree->n;j++)if (tree->node[j].weight>tree->node[k].weight)k=j;if (k!=i){temp=tree->node[i];tree->node[i]=tree->node[k];tree->node[k]=temp;}}}//哈弗曼编码的生成Codetype* HuffmanCode(hufmtree *tree){int i,j,p,k;Codetype *code;if (tree==NULL)return NULL;code=(Codetype*)malloc(tree->n*sizeof(Codetype));for (i=0;i<tree->n;i++){if(flag==1)printf("%c ",tree->node[i].data);//打印字符信息code[i].bits=(char*)malloc(tree->n*sizeof(char));code[i].start=tree->n-1;j=i;p=tree->node[i].parent;while(p!=-1){if (tree->node[p].lchild==j)code[i].bits[code[i].start]='0';elsecode[i].bits[code[i].start]='1';code[i].start--;j=p;p=tree->node[p].parent;}if (flag==1){for (k=code[i].start+1;k<tree->n;k++)//打印字符编码printf("%c",code[i].bits[k]);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;i<m;i++)//初始化所有非叶子结点{tree->node[i].parent=-1;tree->node[i].lchild=-1;tree->node[i].rchild=-1;tree->node[i].weight=0;}for (i=tree->n;i<m;i++)//构建哈夫曼树{small1=small2=MAXVAL;for (j=0;j<=i-1;j++){if (tree->node[j].parent==-1 &&tree->node[j].weight<=small1){small1=tree->node[j].weight;p1=j;}}for (j=0;j<=i-1;j++){if (tree->node[j].parent==-1 &&tree->node[j].weight<=small2 && (j!=p1)){small2=tree->node[j].weight;p2=j;}}tree->node[p1].parent=tree->node[p2].parent=i;tree->node[i].weight=tree->node[p1].weight+tree->node[p2]. weight;tree->node[i].lchild=p1;tree->node[i].rchild=p2;}return tree;}//通过解析源文件建立哈夫曼树hufmtree* CreateHuffmanTreeFromSourceFile(){FILE *textfile,*datafile;char ch,sourcefilename[100];int i,j=0,n=0;int count[128]; //用于统计字符在源文件中出现的次数，27表示26个英文字母和1个空格字符hufmtree *tree;//打开一个源文件printf("\n请输入源文件所在路径:\n");scanf("%s",sourcefilename);if ((textfile=fopen(sourcefilename,"r"))==NULL){printf("\n找不到文件%s\n",sourcefilename);return NULL;}for(i=0;i<128;i++)count[i]=0;//对源文件中各字符的个数统计ch=fgetc(textfile);while(!feof(textfile)){for(i=0;i<128;i++)if (ch==char(i)){count[i]++;break;}ch=fgetc(textfile);}//将统计结果写入新建的权值文件data.txt中,方便以后使用，并构建哈夫曼树datafile=fopen("data.txt","w");for (i=0;i<128;i++)if (count[i]!=0)n++;fprintf(datafile,"%d\n",n);tree=(hufmtree*)malloc(sizeof(hufmtree));tree->node=(hufmtreenode*)malloc((2*n-1)*sizeof(hufmtreeno de));tree->n=n;printf("\n源文件权值信息已保存到data.txt文件中。
