云南大学软件学院数据结构实验报告五
- 格式：doc
- 大小：415.00 KB
- 文档页数：18
（本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）
实验难度： A □ B □ C
序号 学号 姓名 成绩
1 20111120
2 20111120
3
指导教师 （签名）
学 期： 2012秋季学期
任课教师:
实验题目: 树及其应用
小 组 长:
联系电话:
完成提交时间：2012年12月10日
云南大学软件学院 数据结构实验报告
云南大学软件学院2012学年 秋季 学期
《数据结构实验》成绩考核表
学号： 20111120 姓名： 本人承担角色： 小组长
评分项目 评分指标 分值 得分
实验构思（10%） 1. 实验目的明确 5
2. 实验内容理解透彻、对实验所涉及到的知识点分析到位 5
实验设计（15%） 1. 有对基本数据结构的抽象数据类型定义 5
2. 实验方案设计完整，数据结构、算法选择合理 5
3.算法结构和程序功能模块之间逻辑清晰、有相应的流程图 5
实验实现（25%） 1. 代码编写规范、风格统一、注释清楚易读 5
2. 程序运行正常，测试结果正确 15
3. 界面友好、易于操作、有较强的容错性 5
实验报告撰写（10%） 1. 内容详实无缺漏，文字流畅、图表清楚 5
2. 实验结果分析客观、详细，实验体会真实可信，对原实验方案的改进和对实验内容的发散性思考 5
个人工作量（30%） 1. 个人完成工作量 15
2. 个人技术水平 10
3. 团队合作精神 5
实验运作（10%） 1. 有一定用户群 5
2. 应用前景分析 5
综合得分： （满分100分）
指导教师： 年 月 日
（注：此表在难度为C时使用，每个成员一份。）
云南大学软件学院2012学年 秋季 学期
《数据结构实验》成绩考核表
学号： 20111120 姓名： 人承担角色： 组员
评分项目 评分指标 分值 得分
实验构思（10%） 1. 实验目的明确 5
2. 实验内容理解透彻、对实验所涉及到的知识点分析到位 5
实验设计（15%） 1. 有对基本数据结构的抽象数据类型定义 5
2. 实验方案设计完整，数据结构、算法选择合理 5
3.算法结构和程序功能模块之间逻辑清晰、有相应的流程图 5
实验实现（25%） 1. 代码编写规范、风格统一、注释清楚易读 5
2. 程序运行正常，测试结果正确 15
3. 界面友好、易于操作、有较强的容错性 5
实验报告撰写（10%） 1. 内容详实无缺漏，文字流畅、图表清楚 5
2. 实验结果分析客观、详细，实验体会真实可信，对原实验方案的改进和对实验内容的发散性思考 5
个人工作量（30%） 1. 个人完成工作量 15
2. 个人技术水平 10
3. 团队合作精神 5
实验运作（10%） 1. 有一定用户群 5
2. 应用前景分析 5
综合得分： （满分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 #include #include #define MAXVAL 10000 int flag=0; //哈弗曼树结点数据类型 struct hufmtreenode{ char data; int weight;//结点权值 int parent,lchild,rchild;//父结点，左、右孩子结点 }; //哈弗曼树数据类型
struct hufmtree{ hufmtreenode *node;//结点数组（根据n的值动态分配） int n;//叶子结点数 }; //哈弗曼编码数据类型 struct Codetype{ char *bits;//编码流数组，n为为哈夫曼树中叶子结点的数目，编码的长度不可能超过n
int start;//编码实际在编码流数组里的开始位置 }; //将哈夫曼树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->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;in;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'; else code[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;kn;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;inode[i].parent=-1; tree->node[i].lchild=-1; tree->node[i].rchild=-1; tree->node[i].weight=0; } for (i=tree->n;inode[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; }
