综合实验报告格式模板汇编.docVIP

华北科技学院计算机学院综合性实验 实 验 报 告 课程名称 数据结构B 实验学期 2016 至 2017 学年 第 一 学期 学生所在系部 基础部 年级 2015级 专业班级 计算B152 学生姓名 潘予斌 学号 20150901419 任课教师 崔新伟 实验成绩 计算机学院制 《数据结构B》课程综合性实验报告 开课实验室： 基础实验室 2016年 12 月23日 实验题目 用哈夫曼编码实现文件压缩 一、实验目的 1、了解文件的概念。 2、掌握线性链表的插入、删除等算法。 3、掌握Huffman树的概念及构造方法。 4、掌握二叉树的存储结构及遍历算法。 5、利用Huffman树及Huffman编码，掌握实现文件压缩的一般原理。 二、设备与环境 微型计算机、Windows系列操作系统 、Visual C++6.0软件 三、实验内容 根据ASCII码文件中各ASCII字符出现的频率情况创建Huffman树，再将各字符对应的哈夫曼编码写入文件中，实现文 （1）．基本概念 赫夫曼树(Huffman树)是指具有n个叶子结点(每个结点的权值为wi) 的WPL值最小的树，也称为最优树。 WPL=w1?l1+w2?l2+?+wn?ln=∑wi?li (i=1,2,?,n) 其中：n为叶子结点的个数；wi为第i个结点的权值；li为第i个结点的路径长度，即从叶子结点i到根的路径上分支个数。 （2）赫夫曼树构造 根据n个权值{w1, w2, ?,wn}，构造成n棵二叉树的集合F={T1, T2, ?,Tn}，其中每棵二叉树只有一个权值为wi的根结点，没有左、右子树； 在F中选取两棵根结点权值最小的树作为左、右子树构造一棵新的二叉树，且这棵新的二叉树根结点权值为其左、右子树根结点的权值之和； 在F中删除这两棵树，同时将新得到的树加入F中； （3）3．赫夫曼树存储表示 typedef struct{ int weight; int parent, lchild, rchild; }HTNode, * HuffmanTree; \\动态分配数组存储赫夫曼树 typedef char ** HuffmanCode; \\动态分配数组存储赫夫曼编码表#includestdio.h #includestring.h #includestdlib.h #define MAX 17 typedef struct \\顺序列表结构 {int weight; int parent,lchild,rchild; }HTnode,*Huffmantree; \\ 动态分布数组储存赫夫曼树 typedef char * *Huffmancode; \\动态分配数组储存赫夫曼编码表 void select(Huffmantree HT,int n,int *s1,int *s2) {int i,t; \\定义i和t t=1000; \\权的最大值为1000 for(i=1;i=n;i++) \\输入i的值小于1000 if(HT[i].parent==0HT[i].weightt) \\如果传入的结构体里面的父母等于0，并且权值小于t，则执行程序 {t=HT[i].weight; \\当条件成立，t等于结构体里面的权值 *s1=i; \\得出结果最小值s1等于i } t=1000; for(i=1;i=n;i++) \\输入i值小于1000 if(HT[i].parent==0HT[i].weightti!=*s1) \\如果传入的结构体里面的父母等于0，并且全值小于t，且不等于最小值s1 {t=HT[i].weight; \\当条件成立，t等于结构体里面的权值 *s2=i; \\得出结果次小值s2等于i } } void Huffmancoding(Huffmantree HT,Huffmancode HC,int *w,int n) \\w存放n个字符的权值，构造HT，并求出n个字符的HT的编码HC { int p1,q2; int *s1,*s2; int m,i,f,start,c; char *cd; Huffmantree p; s1=p1; \\最小值s1的编码等于p1 s2=q2; \\次小值