数据结构实验报告记录文件压缩

数据结构实验报告实验名称：文件压缩实验类型：综合性试验班级：20112111学号：2011211107姓名：冯若航实验日期：2003.6.19 下午4:001.问题描述文件压缩①基本要求哈夫曼编码是一种常用的数据压缩技术，对数据文件进行哈夫曼编码可大大缩短文件的传输长度，提高信道利用率及传输效率。

要求采用哈夫曼编码原理，统计文本文件中字符出现的词频，以词频作为权值，对文件进行哈夫曼编码以达到压缩文件的目的，再用哈夫曼编码进行译码解压缩。

●统计待压缩的文本文件中各字符的词频，以词频为权值建立哈夫曼树，并将该哈夫曼树保存到文件HufTree.dat中。

●根据哈夫曼树（保存在HufTree.dat中）对每个字符进行哈夫曼编码，并将字符编码保存到HufCode.txt文件中。

●压缩：根据哈夫曼编码，将源文件进行编码得到压缩文件CodeFile.dat。

●解压：将CodeFile.dat文件利用哈夫曼树译码解压，恢复为源文件。

2.数据结构设计此类问题，应设计文件的数据结构。

* 4 压缩头标记* 1 文件名长度* ns 文件名* 4 源文件长度* 1020 huffman树* 1021~EOF 文件内容赫夫曼树节点的数据结构typedef struct node{long w; //权short p,l,r; //父亲，左孩子，右孩子}HTNODE,*HTNP; //霍夫曼树的结点赫夫曼编码数组元素的数据结构设计typedef struct huffman_code{BYTE len; //长度BYTE *codestr; //字符串}HFCODE; //霍夫曼编码数组元素3.算法设计源代码#define_CRT_SECURE_NO_DEPRECATE#include<stdio.h>#include<string.h>#include<stdlib.h>typedef unsigned int UINT;typedef unsigned char BYTE;typedef struct node{long w; //权short p,l,r; //父亲，左孩子，右孩子}HTNODE,*HTNP; //霍夫曼树的结点typedef struct huffman_code{BYTE len; //长度BYTE *codestr; //字符串}HFCODE; //霍夫曼编码数组元素#define OK 1#define ERROR -1#define UNUSE -1 //未链接节点标志#define CHAR_BITS 8 //一个字符中的位数#define INT_BITS 32 //一个整型中的位数#define HUFCODE_SIZE 256 //霍夫曼编码个数#define BUFFERSIZE 256 //缓冲区大小大小#define UINTSIZE sizeof(UINT)#define BYTESIZE sizeof(BYTE)#define TAG_ZIGHEAD 0xFFFFFFFF //压缩文件头标#define MAX_FILENAME512//函数声明//压缩模块int Compress(char *SourceFilename,char *DestinationFilename);//压缩调用int Initializing(char *SourceFilename,FILE **inp,char *DestinationFilename,FILE **outp); //初始化文件工作环境long AnalysisFiles(FILE *in,long frequency[]);//计算每个不同字节的频率以及所有的字节数int CreateHuffmanTree(long w[],int n,HTNODE ht[]);//生成霍夫曼树int HuffmanTreeCoding(HTNP htp,int n,HFCODE hc[]);//霍夫曼编码int Search(HTNP ht,int n);//查找当前最小权值的霍夫曼树节点并置为占用BYTE Char2Bit(const BYTE chars[CHAR_BITS]);//将一个字符数组转换成二进制数字int Search(HTNP ht,int n);//查找当前最小权值的霍夫曼树节点并置为占用int WriteZipFiles(FILE *in,FILE *out,HTNP ht,HFCODE hc[],char* SourceFilename,long source_filesize);//写压缩文件//解压缩模块int DeCompress(char *SourceFilename,char *DestinationFilename);//解压缩调用int Initializing_Dezip(char *SourceFilename,FILE **inp,char*DestinationFilename,FILE **outp); //为处理解压缩流程初始化文件void ReadHuffmanTree(FILE* in,short mini_ht[][2]);//从待解压缩文件中读取huffman树int WriteDeZipFiles(FILE *in,FILE* out,short mini_ht[][2],long bits_pos,longDst_Filesize); //写解压缩文件void ErrorReport(int error_code);//报错//函数定义//函数实现//压缩int Compress(char *SourceFilename,char *DestinationFilename){FILE *in,*out; //输入输出流int i; //计数变量float Compress_rate; //存放压缩率HFCODE hc[HUFCODE_SIZE]; //存放256个字符的huffman编码HTNODE ht[HUFCODE_SIZE*2-1]; //256个字符的huffman树需要2*256-1=511个节点。

东北大学信息科学与工程学院数据结构课程设计报告题目哈夫曼压缩软件设计课题组长王健课题组成员张颖刘琪张晓雨专业名称计算机科学与技术班级计1307指导教师杨雷2015 年1月课程设计任务书目录1 课题概述 (4)1.1 课题任务 (4)1.2 课题原理 (4)1.3 相关知识 (4)2 需求分析 (5)2.1 课题调研 (5)2.2 用户需求分析 (5)3 方案设计 (5)3.1 总体功能设计 (5)3.2 数据结构设计 (6)3.3 函数原型设计 (6)3.4 主算法设计 (7)3.5 用户界面设计 (9)4 方案实现 (12)4.1 开发环境与工具 (12)4.2 程序设计关键技术 (12)4.3 个人设计实现（按组员分工）4.3.1 王健设计实现 (12)4.3.2 张颖设计实现 (17)4.3.3 刘琪设计实现 (20)4.3.4 张晓雨设计实现 (22)5 测试与调试 (25)5.1 个人测试（按组员分工） (25)5.1.1 王健测试 (25)5.1.2 张颖测试 (26)5.1.3 刘琪测试 (27)5.1.4 张晓雨测试 (31)5.2 组装与系统测试 (32)5.3 系统运行 (32)6 课题总结 (33)6.1 课题评价 (33)6.2 团队协作 (33)6.3 下一步工作 (33)6.4 个人设计小结（按组员分工） (33)6.4.1 王健设计小结 (33)6.4.2 张颖设计小结 (34)6.4.3 刘琪设计小结 (34)6.4.4 张晓雨设计小结 (34)7 附录A 课题任务分工 (35)A-1 课题程序设计分工 (35)A-2 课题报告分工 (36)附录B 课题设计文档（光盘） (37)B-1源程序代码（*.H，*.CPP） (37)B-2工程与可执行文件） (37)附录C 用户操作手册（可选） (37)C.1 运行环境说明 (37)C.2 操作说明 (37)1 课题概述1.1课题任务采用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。

《数据结构》课程设计数学与应用数学一班胡耕岩 2012214147一、问题分析和任务定义1.1设计任务采用哈夫曼编码思想实现文件的压缩和恢复功能，并提供压缩前后的占用空间之比。

要求（1）运行时的压缩原文件的规模应不小于5K。

（2）提供恢复文件与原文件的相同性对比功能。

1.2问题分析本课题是利用哈夫曼编码思想，设计对一个文本文件（.txt）中的字符进行哈夫曼编码，生成编码压缩文件，并且还可将一个压缩后的文件进行解码还原为原始文本文件（.txt）。

在了解哈夫曼压缩解压缩原理之前，首先让我们来认识哈夫曼树。

哈夫曼树又称最优二叉树，是带权路径长度最小的二叉树。

在文本文件中多采用二进制编码。

为了使文件尽可能的缩短，可以对文件中每个字符出现的次数进行统计。

设法让出现次数多的字符二进制码短些，而让那些很少出现的字符二进制码长一些。

若对字符集进行不等长编码，则要求字符集中任一字符的编码都不是其它字符编码的前缀。

为了确保哈夫曼编码的唯一性，我们可以对它的左右子树的大小给予比较限定，如：左子树的权值小于右子树的权值。

哈夫曼树中的左右分支各代表‘0’和‘1’,则从根节点到叶子节点所经历的路径分支的‘0’和‘1’组成的字符串，为该节点对应字符的哈夫曼编码。

统计字符中每个字符在文件中出现的平均概率（概率越大，要求编码越短）。

利用哈夫曼树的特点：权越大的叶子离根越近，将每个字符的概率值作为权值，构造哈夫曼树。

则概率越大的节点，路径越短。

哈夫曼译码是从二进制序列的头部开始，顺序匹配成共的部分替换成相应的字符，直至二进制转换为字符序列。

哈夫曼用于文件解压缩的基础是在压缩二进制代码的同时还必须存储相应的编码，这样就可以根据存储的哈夫曼编码对压缩代码进行压缩。

总之，该课题的任务应该是首先要打开要压缩的文本文件并读出其字符出现的频率，以其为权值构建哈夫曼树。

其次要找到构建压缩功能的方法，在构建哈夫曼树的基础上进行编码，改变字符原先的存储结构，以达到压缩文件的目的，以外还有存储相应的哈夫曼编码，为解压缩做准备。

南京工程学院实验报告<班级>_<学号>_<实验X>.RAR文件形式交付指导老师。

一、实验目的1.熟悉上机环境，进一步掌握语言的结构特点。

2.掌握线性表的顺序存储结构的定义及实现。

3.掌握线性表的链式存储结构——单链表的定义及实现。

4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。

5.掌握线性表在链式存储结构——单链表中的各种基本操作。

二、实验内容1.顺序线性表的建立、插入及删除。

2.链式线性表的建立、插入及删除。

三、实验步骤1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。

2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。

3.建立一个带头结点的单链表，结点的值域为整型数据。

要求将用户输入的数据按尾插入法来建立相应单链表。

四、程序主要语句及作用程序1的主要代码(附简要注释)public struct sequenlist{public const int MAXSIZE=1024; /*最大值为1024*/public elemtype[] vec;public int len; /* 顺序表的长度 */public sequenlist( int n){vec=new elemtype[MAXSIZE ];len = n;}};class Program{static void Main(string[] args){sequenlist list1 = new sequenlist(5);for (int i = 0; i < 5; i++){list1.vec[i] = i;}for (int i = 0; i < 5; i++){Console.Write("{0}---", list1.vec[i]) ;}Console.WriteLine("\n");Console.WriteLine("表长：{0}\n",list1.len );Console.ReadKey();}}程序2的主要代码(附简要注释)public void insertlist(int i, int x){if (len >= MAXSIZE)throw new Exception("上溢"); /*长度大于最大值则抛出异常*/if (i < 1 || i > len + 1)throw new Exception("位置");/插入位置小于1或大于len+1则抛出插入位置错误的异常for (int j = len; j >= i; j--)vec[j] = vec[j - 1]; //注意第j个元素存在数组下标为j-1处vec[i - 1] = x;len++;}};class Program{static void Main(string[] args){sequenlist list2 = new sequenlist(7);list2.vec[0] = 21;list2.vec[1] = 23;list2.vec[2] = 14;list2.vec[3] = 5;list2.vec[4] = 56;list2.vec[5] = 17;list2.vec[6] = 31;Console.Write("请输入第i个位置插入元素：");int loc =Convert.ToInt32( Console.ReadLine());Console.Write("请输入第{0}个位置插入的元素：", loc);int ele = Convert.ToInt32(Console.ReadLine());Console.WriteLine("插入前的线性表：");for (int i = 0; i < list2.len ; i++){Console.Write("{0}---", list2.vec[i]);}Console.WriteLine("\n");list2.insertlist(loc, ele);Console.WriteLine("插入后的线性表：");for (int i = 0; i < list2.len ; i++){Console.Write("{0}---", list2.vec[i]);}Console.WriteLine("\n");Console.ReadKey();}}程序3的主要代码(附简要注释)class Node{private int num;public int Num{set { num = value; }/输入值get { return num; }/获得值}private Node next;public Node Next{set { next = value; }get { return next; }}}class Pp{static void Main(string[] args){Node head;Node tempNode, tempNode1;int i;head = new Node();Console.WriteLine("输入六项数据：\n");Console.Write("输入第1项数据:");head.Num = Convert.ToInt32(Console.ReadLine());head.Next = null;tempNode = head;for (i = 1; i < 6; i++){tempNode1 = new Node();Console.Write("输入第{0}项数据:",i+1);tempNode1.Num = Convert.ToInt32(Console.ReadLine());/插入项转换为整形数值 tempNode1.Next = null;tempNode.Next = tempNode1;tempNode = tempNode.Next;}Console.WriteLine("线性表:");tempNode = head;for (i = 0; i < 6; i++){Console.Write("{0}", tempNode.Num);if (i < 5){Console.Write("--");}tempNode = tempNode.Next;}Console.ReadKey();}}五、程序运行结果截图程序1程序2程序3六、收获，体会及问题(写得越详细、越个性化、越真实越好，否则我不知道你做这个实验的心路历程，也就无法充分地判断你是否是独立完成的这个实验、你是否在做这个实验时进行了认真仔细地思考、通过这个实验你是否在实践能力上得到了提高)这次试验刚开始做时完全不知道从哪下手，才刚上了几节课，对于线性表、链式表都不是理解的很透彻，不知道用哪个软件编写程序。

数据结构与程序设计实验实验报告哈尔滨工程大学实验报告四一、问题描述哈夫曼编码是一种常用的数据压缩技术，对数据文件进行哈夫曼编码可大大缩短文件的传输长度，提高信道利用率及传输效率。

要求采用哈夫曼编码原理，统计文本文件中字符出现的词频，以词频作为权值，对文件进行哈夫曼编码以达到压缩文件的目的，再用哈夫曼编码进行译码解压缩。

统计待压缩的文本文件中各字符的词频，以词频为权值建立哈夫曼树，并将该哈夫曼树保存到文件HufTree.dat 中。

根据哈夫曼树（保存在HufTree.dat 中）对每个字符进行哈夫曼编码，并将字符编码保存到HufCode.txt 文件中。

压缩：根据哈夫曼编码，将源文件进行编码得到压缩文件CodeFile.dat。

解压：将CodeFile.dat 文件利用哈夫曼树译码解压，恢复为源文件。

二、数据结构设计由于哈夫曼树中没有度为1的结点，则一棵树有n个叶子结点的哈夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中，而且对每个结点而言，即需知双亲结点的信息，又需知孩子结点的信息，由此可采用如下数据结构。

1.使用结构体数组统计词频，并存储:typedef struct Node{int weight; //叶子结点的权值char c; //叶子结点int num; //叶子结点的二进制码的长度}LeafNode[N];2.使用结构体数组存储哈夫曼树:typedef struct{unsigned int weight;//权值unsigned int parent, LChild, RChild;}HTNode,Huffman[M+1]; //huffman树3.使用字符指针数组存储哈夫曼编码表：typedef char *HuffmanCode[2*M]; //haffman编码表三、算法设计1.读取文件，获得字符串void read_file(char const *file_name, char *ch){FILE *in_file = Fopen(file_name, "r");unsigned int flag = fread(ch, sizeof(char), N, in_file);if(flag == 0){printf("%s读取失败\n", file_name);fflush(stdout);}printf("读入的字符串是: %s\n\n", ch);Fclose(in_file);int len = strlen(ch);。

实验一常见压缩软件的使用一、实验目的使用一些常见的压缩软件，对数据压缩的概念、分类、技术和标准形成初步的认识和理解。

二、实验要求1．认真阅读实验指导书，按实验步骤完成实验内容。

2．实验过程中注意思考实验提出的问题，并通过实验解释这些问题。

3．通过实验达到实验目的。

三、实验环境计算机硬件：CPU处理速度1GHz以上，内存258M以上，硬盘10G以上软件：Windows操作系统2000或XP。

四、实验内容1．使用WinZip或WinRAR两种压缩软件分别对文本文件(.txt,.doc)、程序源代码文件(.c)、数据文件(.dat)、二进制目标代码文件(.obj)、图像文件(.bmp)、音频文件(.wav)和视频文件(.avi,.wmv)进行压缩，分别计算出压缩率，判断这两种压缩软件采用的是可逆压缩还是不可以压缩，猜测其可能用到了那些压缩（编码）技术？2．使用jpegimager、TAK和BADAK分别进行图像、音频和视频的压缩，体验其压缩效果。

3．使用bcl程序对文本文件、程序源代码文件、数据文件、二进制目标代码文件、图像文件等进行多种统计编码技术的压缩，包括香农-费诺(shannon-fano)编码、霍夫曼(huffman)编码、游程编码rle、字典编码lz等，记录每种压缩方法对不同类型文件的压缩效果并进行比较，结合所学知识，解释其中的原因。

五、实验步骤1、下载并打开WinZip和WinRAR两种压缩软件2、分别新建两个文档：qqjj.winzip 和winrar。

添加所要压缩的文件：文本文件(.txt,.doc)、程序源代码文件(.c)、数据文件(.dat)、二进制目标代码文件(.obj)、图像文件(.bmp)、音频文件(.wav)和视频文件(.avi,.wmv)进行压缩，如图所示：3、WinZip压缩软件可以直接看出各文件的压缩率，而winrar压缩软件不能直接看出各文件的压缩率，要在winrar压缩软件的屏幕上只显示一个压缩文件时，右健该压缩文件，点击显示信息方可看到该压缩文件的压缩率。

数据结构课程设计报告实验二：文本文件压缩一、设计要求1、问题描述：根据huffman编码以及二叉树的相关知识实现文本文件的压缩（即将输入的字符串转换为二进制编码）和解压（即将二进制编码转换为字符串）2、输入：文本文件（压缩文件）。

3、输出：压缩文件（文本文件）。

知识点：堆、霍夫曼树、二叉树遍历实际输入输出情况：源文件为文本文件，内容如下：输出的文件是以.zl0010为扩展名的二进制文件，将其用记事本以文本方式打开得到如下文件：解压过程如下：解压获得的文件doc.txt.zl0010.txt比较发现源文件与解压缩后文件内容相同。

一、数据结构与算法描述1.对输入文件的处理创建文件输入流，将源文本文件以二进制方式打开，建立保存每个Byte频率的数组count[256]，并通过对文件的第一次遍历，完成对Byte频率的统计。

其中bytecount变量记录输入的字节数，关键代码如下：string filename;//文件名int count[256];//每个字符的频率for(int i=0;i<256;i++)count[i]=0;std::ifstream ifs;//输入流std::cout<<"请输入需要压缩的文件路径"<<std::endl;std::cin>>filename;ifs.open(filename,std::ifstream::binary);if(!ifs){std::cout<<"文件打开错误"<<std::endl;system("pause");exit(0);}char buf;int bytecount=0;//计算总共输入了多少字节std::cout<<"正在计算频率……"<<std::endl;while(!ifs.eof()){ifs.read((char*)&buf,1);/*buf+=128;count[buf]++;*/if(ifs.eof())break;count[(int)buf+128]++;bytecount++;/*std::cout<<(int)buf<<std::endl;*/}2.哈夫曼树的建立及编码过程以第一步中统计的Byte出现频率为每个树节点的权值，进行哈夫曼树的构建，并通过构建的哈夫曼树，获取std::string类型的哈夫曼编码。

数据结构实验报告三——哈夫曼文件压缩实验题目：哈夫曼文件压缩实验目标：输入一个有10k单词的英文文档。

输出压缩后的二进制文件，并计算压缩比。

数据结构：栈和哈夫曼树。

1.定义栈（）typedef struct{char *elem;int stacksize;int top;}STACK;2.定义哈夫曼树（）typedef struct{int weight;int left,right;int parent;}HTNode;需要的操作有：1.初始化栈（Initstack）void Initstack(STACK *s){s->elem=(char *)malloc(sizeof(int)*1000);s->stacksize=1000;s->top=-1;}2.压栈（push）void push(STACK *s,int e){s->elem[++s->top]=e;}3.弹栈（pop）void pop(STACK *s,int *e){if(s->top!=-1)*e=s->elem[s->top--];}4.构造哈夫曼树（Inithuffman）void Inithuffman(int wset[n],int k,HuffTree HT[]){ //构造哈夫曼树int i,m;int s1,s2;m=k*2-1;for(i=0;i<m;i++){ //初始化HT数组HT[i]=(HuffTree)malloc(sizeof(HTNode));HT[i]->weight=(i<k?wset[i]:0);HT[i]->parent=-1;HT[i]->left=HT[i]->right=-1;}for(i=k;i<m;i++){ //主循环，完成n-1次合并select(HT,k,i,&s1,&s2); //在HT[1...i-1]中选择parent为0且weight为最小的两个结点，其下标分别为s1和s2HT[i]->left=s1;HT[i]->right=s2;HT[i]->weight=HT[s1]->weight+HT[s2]->weight;HT[s1]->parent=HT[s2]->parent=i;}}其中用到另一个基本操作：找到哈夫曼树中最小和次小的结点（select）5.找到哈夫曼树中最小和次小的结点（select）void select(HuffTree HT[255],int a,int i,int *p,int *q){int j=0,k=0,*HT1,temp;HT1=(int *)malloc(sizeof(int)*(i-1)); //存放权值for(j=0;j<i;j++){if(HT[j]->parent==-1){HT1[k]=HT[j]->weight; //把没有parent的结点的权值放在HT1中k++;}//printf("%4d%4d%4d%4d%4d\n",HT[j]->parent,HT[j]->left,HT[j]->right,HT[j]->we ight,HT1[k-1]);}j=0;while(j<2) { //找到权值最小和第二小的结点for(k=j;k<(i-(i-a)*2);k++){if(HT1[j]>HT1[k]){temp=HT1[k];HT1[k]=HT1[j];HT1[j]=temp;}}j++;}k=0;for(j=0;j<i;){if(HT[j]->parent==-1)if(HT[j]->weight==HT1[0]&&k<1){ //将最小的权值赋到*p中*p=j;k++;}j++;}for(j=0;j<i;){if(HT[j]->parent==-1)if(j!=*p)if(HT[j]->weight==HT1[1]&&k<2){ //将第二小的权值赋到*q 中*q=j;k++;}j++;//printf("%4d%4d%4d%4d\n",HT[i]->parent,HT[i]->left,HT[i]->right,HT[i]->weigh t);}}6.根据哈夫曼树得到各字符对应的哈夫曼编码（Huffman）void Huffman(HuffTree HT[2*n-1],int k,char str[][20]){int i,j,e,t1=0,t2=0;char c;STACK st;for(i=0;i<k;i++){if(HT[i]->right==-1&&HT[i]->left==-1){ //找一个叶子结点Initstack(&st);HT[i]->right=HT[i]->left==-2;j=i; //记录其下标while(HT[j]->parent!=-1){if(HT[HT[j]->parent]->right==j) //找到一个叶子结点，如果他是其parent结点的右结点，就将此边记为1push(&st,'1');elsepush(&st,'0'); //在左边记为0j=HT[j]->parent; //循环操作直到到达根结点}c=i;printf("\t%c ",c); //打印此字符for(;st.top!=-1;){pop(&st,&e);printf("%c",e); //打印其二进制编码str[t1][t2]=e; //将二进制编码存放在str中t2++;}putchar('\n');str[t1][t2]='\0';t2=0;t1++;}}}算法设计：1.从文件中逐个读取字符，记录其出现次数以及文件总字符数，由此确定其频率高低。

《数据结构》实验报告利用Huffman编码对文件进行压缩解压学生:XXX学号:XXXXXXXX联系:XXXXXX@(一)基本信息1.实验题目利用Huffman编码对文件进行压缩解压2.完成人（姓名、学号）姓名：XXX 学号：XXXXXXXX3.报告日期2007年12月12日星期二(二)实习内容简要描述1.实习目标学会对树的基本操作学会对文件进行操作利用Huffman编码对文件压缩解压2.实习要求实现最小堆模板类利用最小堆构建Huffman树实现Huffman编码和解码根据用户从键盘输入的报文文本,输出各字符的Huffman编码以及报文的编码根据用户从键盘输入一串报文文本，输出各字符的Huffman编码输出报文的Huffman编码及长度根据输入的Huffman编码，解码输出利用Huffman编码和解码对二进制文件的压缩和解压(三)报告主要内容1.设计思路开发环境：Microsoft Visual C++ 2005设计思路：1.设计Pack类储存字符的权值2.设计MinHeap模板类构建最小堆3.设计ExtBinTree模板类为带权二叉树4.设计Compress模板类以实现文件的压缩解压2.主要数据结构1.MinHeap.h: 头文件,包含MinHeap模板类的类界面以及定义;2.HuffmanTree.h:头文件,包含ExtBinTree模板类以及Compress模板类的类的的类界面以及定义3.main.cpp:调用上述头文件实现相关操作3.主要代码结构主要代码结构为见附件中各文件的代码注释4.主要代码段分析主要代码段分析，见附件中的代码注释(四)实习结果1.基本数据源程序代码行数：约800行完成该实习投入的时间：二十四小时(不包括写实验报告的时间)与其他同学讨论交流情况:感谢刘畅同学对程序的测试2.测试数据设计1.对屏幕输入字符进行Huffman编码2.根据Huffman树非唯一性,虽然和课件上有些许不同,但是还是正确的3.输入字符串:CASTCASTSATATATASA4.输出编码:A:0 C:110 S:111 T:105.输入霍夫曼编码:01110101101106.输出译码:ASATCC7.8.对”实验05.PPT”的压缩操作9.使用0秒(不足一秒按0秒计算),压缩率为56.1755%10.对”实验05.ppt.hfm”(即刚才生成的压缩文件)的解压操作11.使用0秒(不足一秒按0秒计算),解压后文件无异常12.对一个18M的EXE安装包前后进行压缩和解压操作,分别用时10秒和9秒3.测试结果分析A)程序运行的系统资源配置操作系统：Microsoft Windows XP Professional SP2CPU: AMD Athlon 3600+ 2.0GRAM: 1024M DDRII开发环境：Microsoft Visual C++ 2005B)对TXT文档进行压缩和解压后,通过WinMerge检验和原文件无差异C)对MP3和EXE文件压缩和解压后仍能正常使用D)对于中文名字和带有空格的路径均能正确无误识别E)文件名只能小于16个字符(包括后缀名),否则解压会出错(只预留了16个字节用于储存文件名)F)相对于不用文件块读写的程序,效率提高了三倍以上G)具有动态进度条,可以显示当前压缩和解压的进度百分比(当然消耗了一些系统资源)H)出错处理不够充分,特别是cin部分,如果误输入可能会造成死循环(五)实习体会1.实习过程中遇到问题及解决过程A)一开始时候的程序运行很慢,,压缩一个4M左右的文件需要七八秒,后来改用文件块缓存字节来读写后,压缩一个4M的文件只需要两秒左右的时间.本来是只想写一个进度条而已的,后来发现如果只读一个字节就判断一次进度条的话会很消耗系统资源,后来干脆麻烦点用文件块来缓存.不过至于一次缓存多少字节才能达到最好的效果还未知,现在设置的是一次缓存40KB 的数据B)本来一个一个字节读的时候对最后一个字节的操作基本没费什么劲,但是在文件块读写的时候就不是那么清晰明了了,后来经过仔细Debug,才找到错误的所在.许多问题都是这样C)对于中文名和带空格路径,用C++的fstream就不支持,但是C中的FILE*就支持,不知道为什么.还有C++中的fstream的成员函数read返回值很奇怪,不知道如何获取成功读入的项数.改用C中的FILE*文件指针后就解决掉了D)由于这次实验的各个步骤是一环套一环的,在哪里出错很难找得出来,所以这次实验调试消耗的时间特别多.最郁闷的一次错误是发现在取得字符C的第N位函数中,居然把0x40写成了0x30.有时候文件解压出来不对,但是又不清楚是压缩时候错了,还是解压时候错了,然后就要两个函数都要检查一遍.2. 实习体会和收获这次实验最大的特点在于难找错,很锻炼自己的Debug能力(六)自评成绩分数：90 //功能做得较齐全,程序的效率也不错(七)参考文献MSDN还有某网站上树的遍历算法(八)源程序见同一文件夹内.。

实验报告班级0901101 学号PB09210173 姓名饶亚民日期2010-11-10 一、题目要求:利用Huffman树及其编码原理写一个压缩和解压缩程序二、概要设计根据对用户输入的内容判断用户是要求压缩还是解压缩,若是压缩,则读入需压缩的文件（以二进制形式打开）,求文件中字符的权重,构建Huffman树,求每个字符的Huffman编码,然后依次读入需压缩文件的内容,把其每个字符用其Huffman编码代换存入一数组中,输出到输出文件中。

输出文件格式为--.zap（也是二进制形式输出）。

若是解压缩，则根据读入文件的内容（以二进制形式打开），先判断是否为本压缩程序所压缩，若非，则报错。

若是，则依次读入存入该文件中的原来压缩文件的后缀名，原来文件中每个字符的权重，然后依据已存的每个字符的权重构建Huffman树,接着求每个字符的Huffman编码。

然后依次读入文件中的已存的以Huffman编码结果储存的0和1字符，按照Huffman编码结果，左子树为0，右子树为1，直至叶子节点，然后就可得到该Huffman编码所存储的字符值，然后依次输出到输出文件中，其中有一个count，用来记录已输出的字符个数，当它等于被压缩的文件长度时就停止。

三、详细设计详细数据结构定义：#include<stdio.h>#include<stdlib.h>#include<malloc.h>#include<string.h>#include"head.cpp"#include"BitWriting-Reading.cpp"#include"Directions.cpp"#include"Compress.cpp"#include"FindName.cpp"#include"filecompress.cpp"#include"Huffman Code.cpp"#include"DeCompress.cpp"#include"Match.cpp"#define TRUE 1#define FALSE 0#define ERROR 0#define OK 1typedef int Status;typedef struct{unsigned int weight;unsigned int parent,lchild,rchild;}HTNode,*HuffmanTree;typedef char **HuffmanCode;具体实现过程：main(int argc,char *argv[])//若argc=1则按报错处理然后调用Match函数Match(argv[1],flag)，其作用是用来判断用户输入的内容Status Match(char *argv,int &flag){char *parameters[]={"compress","decompress","help"};int i;for(i=0;i<3;++i){if(!strcmp(parameters[i],argv)){flag=i+1;return OK;}}flag=0;return OK;}若flag=0，则按报错处理，并提示用户可以参考’help’；若flag=1，则说明是要压缩，接着判断argv[2]是否为空，若不为空，则将其视为输出文件的文件名，若为空，则默认为输入文件名为输出文件名，仅后缀不同而已。

《用哈夫曼编码实现文件压缩》实验报告课程名称《数据结构B》实验学期2014至2014 学年第 1 学期学生所在系部计算机系年级2010 专业班级网络B10-3学生姓名学号任课教师实验成绩用哈夫曼编码实现文件压缩1、了解文件的概念。

2、掌握线性链表的插入、删除等算法。

3、掌握Huffman树的概念及构造方法。

4、掌握二叉树的存储结构及遍历算法。

5、利用Huffman树及Huffman编码，掌握实现文件压缩的一般原理。

微型计算机、Windows 系列操作系统、Visual C++6.0软件根据ASCII码文件中各ASCII字符出现的频率情况创建Haffman树，再将各字符对应的哈夫曼编码写入文件中，实现文件压缩。

在文件存储时，一个整型的字符要占用一个字节的空间，对于某些不常用的字符这样会造成空间的浪费，但如果用位来存储数据，可以将字符重新编码，使那些常用的字符存储空间相对短的，不常用的字符相对长些，可以节约空间。

哈夫曼编码即是这样一个过程。

用哈夫曼编码进行文件压缩，首先应对所用的字符进行哈夫曼变编码，在这之前应先对所用字符进行权值统计。

在编码哈夫曼树的时候，选取两个权值最小的依次构造哈夫曼树，进行哈夫曼编码时，使哈夫曼树的左孩子上的分支编码为0，右孩子上的分支编码为1。

然后对文件进行压缩。

压缩过程用到了文件的读写。

头文件的构造：头文件首先应用宏定义，对文件要用到的数据进行定义，然后定义了结构体类型，将所要到字符的权值，数据，双亲编号与孩子编号放在结构体中，使程序间的关系变得紧密。

定义第二个结构体，其中包含结构体数组和树根的编号。

定义指针，使其指向第二个结构体。

接着类型定义，定义了结构体，其中包含字符原码值，哈夫曼编码值和哈夫曼编码值的长度，并将其取名为HaffCode。

将程序所用到的函数包含在头文件里。

哈夫曼树的构造：在程序开头先对程序所用到的变量进行定义，包括指向结构体的指针，整型变量，权值最小的结点的编号，第二小的结点的编号，权值最小的结点的权值，第二小的结点的权值。

《用哈夫曼编码实现文件压缩》实验报告班级：计算B111学号：201109014129姓名：张小梅指导教师：丁智斌实验日期：2013.6.12成绩：一、实验题目：用哈夫曼编码实现文件压缩二、实验目的：1.了解文件的概念。

2.掌握线性链表的插入、删除等算法。

3.掌握Huffman树的概念及构造方法。

4.掌握二叉树的存储结构及遍历算法。

5.利用Huffman树及Huffman编码，掌握实现文件压缩的一般原理。

三、实验设备与环境：微型计算机、Windows 系列操作系统、Visual C++6.0软件四、实验内容：根据ascii码文件中各ascii字符出现的频率情况创建Haffman树，再将各字符对应的哈夫曼编码写入文件中，实现文件压缩。

五、概要设计：本次实验采用将字符用长度尽可能短的二进制数位表示的方法，即对于文件中出现的字符，无须全部都用8位的ASCII码进行存储，根据他们在文件中出现的频率不同，我们利用Haffman算法使每个字符能以最短的二进制字符进行存储，以达到节省存储空间，压缩文件的目的。

解决了压缩需采用的算法，程序的思路已然清晰：1．统计需压缩文件中每个字符出现的频率。

2．将每个字符的出现频率作为叶子结点构建Haffman树，然后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列，这样便完成了Haffman编码，将每个字符用最短的二进制字符表示。

3．打开需压缩文件，再将需压缩文件中的每个ASCII码对应的Haffman编码按bit单位输出。

4．文件压缩结束。

六、详细设计：1. 构造Hufffman树的方法—Hafffman算法构造Huffman树步骤：I. 根据给定的n个权值{w1,w2,⋯⋯wn}，构造n棵只有根结点的二叉树，令起权值为wj。

II. 在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和。

2008级数据结构实验报告实验名称：实验三——实现哈夫曼树学生姓名：***班级：**********班内序号：**学号：********日期：2009年11月14日1．实验要求利用二叉树结构实现赫夫曼编/解码器。

基本要求：1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立赫夫曼树2、建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符的编码输出。

3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。

4、译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。

5、打印(Print)：以直观的方式打印赫夫曼树（选作）6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。

测试数据：I love data Structure, I love Computer。

I will try my best to study data Structure.提示：1、用户界面可以设计为“菜单”方式：能够进行交互。

2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。

2. 程序分析2.1 存储结构在哈夫曼树编码这个程序中，所有数据用的存储结构都是顺序存储结构，其中包括顺序表和树（三叉树）。

树的存储结构如下：（输入的字符串为assddddffffffffgggggggggggggggg）上结构图中，填充为黄色的部分为写入内存中的部分。

每一行的部分为数组的下标，左边部分为所定义的结构的成员。

其中有的结点的父节点的下标是一个负数，用来说明该节点是该节点的父节点的左孩子，正数说明的是该节点的父节点的右孩子。

父节点这零的节点说明该节点是该哈夫曼树的根节点。

画出树的结构如下画所示：（结点中第一个数表示这个字符的ASCⅡ编码，第二个数字表示权值）红色箭头表示父指针，黑色箭头表示孩子指针由上面的图可知，原字符串编码后的二进制编码为11101111111111011011011010101010101010100000000000000000字符串中出现的所有的字符的编码如下：a 1110 ；s 1111 ； d 110 ； f 10 ；g 02.2 关键算法分析算法1：哈夫曼树的构造这个算法分两个部分，每一个部分是对一个字符串中每个字符出现次数的统计，并为每一个出现的字符建立一个叶子节点；第二个部分是以上面的统计的数据为依据建立起一棵哈夫曼树。

实验报告学生所在系部 专业班级 学号 2017任课教师 实验成绩计算机学院制课程名称 数据结构B 实验学期2018 至 2019 学年 第学期年级 学生姓名《数据结构》课程综合性实验报告、实验目的5、利用Huffman 树及Huffman 编码，掌握实现文件压缩的一般原理。

—、设备与环境微型计算机、Windows 系列操作系统、Visual C++6.0软件三、实验内容1、实验内容根据ascii 码文件中各ascii 字符出现的频率情况创建Haffman 树，再将各字符对 应的哈夫曼编码写入文件中，实现文件压缩。

2、实验要求a 、用C 语言编程实现上述实验内容中的结构定义和算法。

b 要有main()函数，并且在main()函数中使用检测数据调用上述算法。

3、最后结果输出。

要求：输出格式要界面直观、清晰大方、格式规范。

四、实验方法或步骤1、实验的预备知识(1)构造Hufffman 树的方法一Hufffman 算法构造Huffman 树步骤:I.根据给定的n 个权值｛w1,w2, ............... wn ｝，构造n 棵只有根结点的二叉树， 令起权值为wj 。

II.在森林中选取两棵根结点权值最小的树作左右子树, 根结点权值为其左右子树根结点权值之和。

III.在森林中删除这两棵树，同时将新得到的二叉树加入森林中。

IV.重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树。

开课实验室: 软件工程实验室2018年11月23日实验题目用赫夫曼编码实现文件压缩1、 了解文件的概念。

2、 掌握线性链表的插入、删除等算法。

3、 掌握Hufman 树的概念及构造方法。

4、 掌握二叉树的存储结构及遍历算法。

构造一棵新的二叉树，置新二叉树(2) Huffman编码：数据通信用的二进制编码思想：根据字符出现频率编码，使电文总长最短编码：根据字符出现频率构造Huffman树，然后将树中结点引向其左孩子的分支标“0”, 引向其右孩子的分支标“ 1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列。