实验报告 数据结构

1、华北科技学院 用哈夫曼编码实现文件压缩实验报告用哈夫曼编码实现文件压缩实 验 报 告课程名称 数据结构B 实验学期 2014 至 2015 学年 第 二 学期学生所在系部 管理学院 年级 2013 专业班级 电商B133 学生姓名 谷美霞 学号 201304064328 任课教师 兰芸 实验成绩 一、实验题目：用哈夫曼编码实现文件压缩二、实验目的：1、 了解文件的概念。2、 掌握线性链表的插入、删除等算法。3、掌握Huffman树的概念及构造方法。4、掌握二叉树的存储结构及遍历算法。5、利用Huffman树及Huffman编码，掌握实现文件压缩的一般原理三、实验设备与环境：微型计算机、Wind

2、ows 系列操作系统 、Visual C+6.0软件四、实验内容：根据ascii码文件中各ascii字符出现的频率情况创建Haffman树，再将各字符对应的哈夫曼编码写入文件中，实现文件压缩五、概要设计：1、构建赫夫曼树HT，并求出n个字符的赫夫曼编码HC。2、创建完毕后，放入hfmTree.txt文件中!3、进行编码，并将字符放入ToBeTran.txt。4、从CodeFile.txt中读入编码，输出在终端。5、读入CodeFile.txt中的编码进行译码，将译出来的字符放入Textfile.txt中。6、先用编码中的前几个和字符的编码相比较，然后往后移。7、最后译码结束后，字符已经存入Te

3、xtfile.txt文件中！8、如有其他情况请重新输入。六、详细设计：#include<iostream.h>#include<stdio.h>#include<stdlib.h>#include<string.h>#include<fstream.h>typedef struct /赫夫曼树的结构体char ch;int weight; /权值int parent,lchild,rchild;htnode,*hfmtree;typedef char *hfmcode;void Select(hfmtree &HT,int a

4、,int *p1,int *p2) /Select函数，选出HT树到a为止，权值最小且parent为0的2个节点int i,j,x,y;for(j=1;j<=a;+j)if(HTj.parent=0)x=j;break;for(i=j+1;i<=a;+i)if(HTi.weight<HTx.weight&&HTi.parent=0)x=i; /选出最小的节点for(j=1;j<=a;+j)if(HTj.parent=0&&x!=j)y=j;break;for(i=j+1;i<=a;+i)if(HTi.weight<HTy.we

5、ight&&HTi.parent=0&&x!=i)y=i; /选出次小的节点if(x>y)*p1=y;*p2=x;else*p1=x;*p2=y;void hfmcoding(hfmtree &HT,hfmcode &HC,int n) /构建赫夫曼树HT，并求出n个字符的赫夫曼编码HCint i,start,c,f,m,w;int p1,p2;char *cd,z;if(n<=1)return;m=2*n-1;HT=(hfmtree)malloc(m+1)*sizeof(htnode);for(i=1;i<=n;+i) /初始

6、化n个叶子结点printf("请输入第%d字符信息和权值：",i);scanf("%c%d",&z,&w);while(getchar()!='n')continue;HTi.ch=z;HTi.weight=w;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(;i<=m;+i) /初始化其余的结点HTi.ch='0'HTi.weight=0;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(i=n+1;i<=m;+i) /

7、建立赫夫曼树Select(HT,i-1,&p1,&p2);HTp1.parent=i;HTp2.parent=i;HTi.lchild=p1;HTi.rchild=p2;HTi.weight=HTp1.weight+HTp2.weight;HC=(hfmcode)malloc(n+1)*sizeof(char *);cd=(char *)malloc(n*sizeof(char);cdn-1='0'for(i=1;i<=n;+i) /给n个字符编码start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if

8、(HTf.lchild=c)cd-start='0'elsecd-start='1'HCi=(char*)malloc(n-start)*sizeof(char);strcpy(HCi,&cdstart);free(cd);int main()char code100,h100,hl100;int n,i,j,k,l;ifstream input_file; /文件输入输出流ofstream output_file;char choice,str100;hfmtree HT;hfmcode HC;cout<<"n"cout

9、<<" "<<"电商B133班"<<" "<<"201304064328"<<" "<<"谷美霞n"while(choice!='Q'&&choice!='q') /当choice的值不为q且不为Q时循环cout<<" "<<"*赫夫曼编码/译码器*n" cout<<" &

10、quot;<<"I.Init"<<" "<<"E.Encoding"<<" "<<"D.Decoding"<<" "<<"Q.Exitn" cout<<"请输入您要操作的步骤："cin>>choice; if(choice='I'|choice='i') /初始化赫夫曼树cout<<&q

11、uot;请输入字符个数："cin>>n;hfmcoding(HT,HC,n);for(i=1;i<=n;+i)cout<<HTi.ch<<":"<<HCi<<endl;output_file.open("hfmTree.txt");if(!output_file)cout<<"can't oen file!"<<endl;return 1;for(i=1;i<=n;i+)output_file<<"(

12、"<<HTi.ch<<HCi<<")"output_file.close();cout<<"赫夫曼树已经创建完毕，并且已经放入hfmTree.txt文件中!"<<endl; else if(choice='E'|choice='e') /进行编码，并将字符放入ToBeTran.txt，码值放入CodeFile.txt中printf("请输入字符：");gets(str);output_file.open("ToBeTran.

13、txt");if(!output_file)cout<<"can't oen file!"<<endl;return 1;output_file<<str<<endl;output_file.close();output_file.open("CodeFile.txt");if(!output_file)cout<<"can't oen file!"<<endl;return 1;for(i=0;i<strlen(str);i+)f

14、or(j=0;j<=n;+j)if(HTj.ch=stri)output_file<<HCj;break;output_file.close();cout<<"n"cout<<"编码完毕，并且已经存入CodeFile.txt文件！n"input_file.open("CodeFile.txt"); /从CodeFile.txt中读入编码，输出在终端if(!input_file)cout<<"can't oen file!"<<endl;ret

15、urn 1;input_file>>code;cout<<"编码码值为："<<code<<endl;input_file.close(); else if(choice='D'|choice='d') /读入CodeFile.txt中的编码进行译码，将译出来的字符放入Textfile.txt中input_file.open("CodeFile.txt");if(!input_file)cout<<"can't oen file!"<

16、;<endl;return 1;input_file>>h;input_file.close();output_file.open("Textfile.txt");if(!output_file)cout<<"can't oen file!"<<endl;return 1;k=0;while(hk!='0') /先用编码中的前几个和字符的编码相比较，然后往后移for(i=1;i<=n;i+)l=k;for(j=0;j<strlen(HCi);j+,l+)hlj=hl;hlj=&

17、#39;0'if(strcmp(HCi,hl)=0)output_file<<HTi.ch;k=k+strlen(HCi);break;output_file.close();input_file.open("Textfile.txt");if(!input_file)cout<<"can't oen file!"<<endl;return 1;input_file>>h; cout<<h<<endl;input_file.close();cout<<"译码结束，字符已经存入Textfile.txt文件中！"<<endl; e