数据结构综合性实验报告格式

1、华北科技学院 用哈夫曼编码实现文件压缩实验报告用哈夫曼编码实现文件压缩实 验 报 告课程名称 数据结构A 实验学期 2015 至 2016 学年 第 二 学期学生所在系部 管理学院 年级 2014 专业班级 电商B142 学生姓名 梁祺 学号 201404064208 成绩评定：1、工作量： A（ ），B（ ），C（ ），D（ ）,F( )2、难易度： A（ ），B（ ），C（ ），D（ ）,F( )3、答辩情况：基本操作： A（ ），B（ ），C（ ），D（ ）,F( )代码理解： A（ ），B（ ），C（ ），D（ ）,F( )4、报告规范度： A（ ），B（ ），C（ ），D（ ）,F(

2、 )5、学习态度： A（ ），B（ ），C（ ），D（ ）,F( )总评成绩:_指导教师: 兰 芸 一、 实验题目：用哈夫曼编码实现文件压缩二、实验目的：1、 了解文件的概念。2、 掌握线性链表的插入、删除等算法。3、掌握Huffman树的概念及构造方法。4、掌握二叉树的存储结构及遍历算法。5、利用Huffman树及Huffman编码，掌握实现文件压缩的一般原理。三、实验设备与环境：微型计算机、Windows 7操作系统 、Visual C+6.0软件四、实验内容：根据Ascii码文件中各Ascii字符出现的频率情况创建Haffman树，再将各字符对应的哈夫曼编码写入文件中，实现文件压缩。五、

3、系统设计：树中从根到每个叶子都有一条路径，对路径上的个分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符编码，这就是赫夫曼编码。实验前，先统计数据出现的频率，得出权值；然后开始实验，先通过for循环结构获得所有结点中权值最小的根结点序号，再通过Select方法选择权值最小的树的根结点的序号构建赫夫曼树，之后调用HuffmanTreeCoding方法，先初始化节点，之后再利用for循环结构建赫夫曼树，待生成赫夫曼树之后，从叶子到根逆向求每个字符的赫夫曼编码，最后设计主函数，实现实验中的大概步骤。以下是实验流程图：开始定

4、义变量得出权值最小的根节点序号初始化节点输入需要编码的字符构建赫夫曼树输出赫夫曼树构建过程表生成赫夫曼树从叶子到根逆向求每个字符的赫夫曼编码输出结果结束六、系统实现及测试结果：实验源代码：#include <stdio.h>#include <stdlib.h>#include <limits.h>#include <string.h>typedef int ElementType;typedef struct huffmantree unsigned int weight; / 权值 unsigned int parent, lchild, r

5、child; HTNode, *HuffmanTree; / 动态分配数组存储赫夫曼树typedef char * *HuffmanCode; / 动态分配数组存储赫夫曼编码表int Min(HuffmanTree t, int totalNodes) / 获得totalNodes个结点中权值最小的根结点序号 int minIndex = 0; unsigned int unWeight = UINT_MAX; / 无符号整型最大值 for (int i=1; i <= totalNodes; i+) if (ti.weight < unWeight && ti.p

6、arent = 0) / ti为根结点 unWeight = ti.weight; minIndex = i; tminIndex.parent = 1; / 给选中的根节点双亲赋1，避免第2次查找改点 return minIndex;void Select(HuffmanTree t, int minIndex, int &minIndex1, int &minIndex2)/ 选择权值最小的树的根结点的序号 minIndex1 = Min(t, minIndex); minIndex2 = Min(t, minIndex); int tempIndex; if (minIn

7、dex1 > minIndex2) tempIndex = minIndex1; minIndex1 = minIndex2; minIndex2 = tempIndex; return;void HuffmanTreeCoding(HuffmanTree &HT, HuffmanCode &HC, int* w, int n) / 存放n个字符的权值, 构造赫夫曼树，求出n个字符的赫夫曼编码HC if (n <= 1) return; int m = 2 * n - 1; / 总结点和 int i; / 根结点序号int s1,s2,j; HT = (Huffma

8、nTree)malloc(m+1) * sizeof(HTNode); / 0号单元未用 for (i=1; i<=n; i+) /初始化 HTi.weight=wi-1; HTi.parent=0; HTi.lchild=0; HTi.rchild=0; for (i=n+1; i<=m; i+) /初始化 HTi.weight=0; HTi.parent=0; HTi.lchild=0; HTi.rchild=0; puts("n哈夫曼树的构造过程如下所示："); printf("HT初态:n 结点 weight parent lchild rch

9、ild"); for (i=1; i<=m; i+) printf("n%4d%8d%8d%8d%8d",i,HTi.weight,HTi.parent,HTi.lchild,HTi.rchild); printf(" 按任意键，继续 ."); getchar(); for (i=n+1; i<=m; i+) / 建赫夫曼树/ 在HT1.nodeIndexs-1中选择parent为0且weight最小的两个结点，其序号分别为是s1,s2 Select(HT, i-1, s1, s2); HTs1.parent = i; HTs2.p

10、arent = i; HTi.lchild = s1; HTi.rchild = s2; HTi.weight = HTs1.weight + HTs2.weight; printf("n select: s1=%d s2=%dn", s1, s2); printf(" 结点 weight parent lchild rchild"); for (j=1; j<=i; j+) printf("n%4d%8d%8d%8d%8d",j,HTj.weight,HTj.parent,HTj.lchild, HTj.rchild); pr

11、intf(" 按任意键，继续 ."); getchar(); /-从叶子到根逆向求每个字符的赫夫曼编码- HC = (HuffmanCode)malloc( (n+1)*sizeof(char*); / 分配n个字符编码的头指针向量(0不用) char* cd; cd = (char*)malloc(sizeof(char) * n); / 分配求编码的工作空间 cdn-1 = '0' / 编码结束符 for (i = 1; i <= n; i+) / 逐个字符求赫夫曼编码 int start; unsigned int c, f; start = n

12、 - 1; / 编码结束位置 for (c=i, f=HTi.parent; f != 0; c=f, f = HTf.parent) / 从叶子到根逆向求编码 if (HTf.lchild = c) cd-start = '0' else cd-start = '1' HCi = (char*)malloc(n - start) * sizeof(char); / 为第i个字符编码分配空间 strcpy(HCi, &cdstart); / 从cd复制编码串到HC free(cd); / 释放工作区间 return;int main(void) Huff

13、manTree HT; HuffmanCode HC; int n; printf("请输入权值的个数: "); scanf("%d", &n);getchar(); int* w; w = (int*)malloc(n * sizeof(int); printf("请输入%d个权值： n", n); for (int i=0; i <= n-1; i+) scanf("%d", w+i);getchar(); HuffmanTreeCoding(HT, HC, w, n); printf("各权值赫夫曼编码为:n"); for (i=1; i <=n; i+) puts(HCi); return 0;测试结果：七、实验结果分析： 实验过程中磕磕绊绊，总算是完成了，从一开始对程序以一知半解，到基本上掌握程序的核心，花了不少功夫。在网上参考过很多别人的作品，也许是知识层面不同，有些地方理