哈夫曼数实验报告

数据结构实验报告

姓名： XX

专业： 计算机科学与技术 班级： 104304XXX 学号： 104304XXX 指导老师：孙界平

日期： 2010年XXXXXX

一、实验题目:

Huffman编码(二叉树应用)

二、实验的目的和要求

1.要求对文件进行Huffman编码的算法,以及对一编码文件进行解码的算法 2.熟练掌握二叉树的应用;具体要求如下

(1) 统计：

2) 构造Huffman树 (3) 在左分枝标0,右分枝标1: 4) 确定Huffman编码

三、实验的环境:

Microsoft Visual c++2010

四、算法描述:

1>首先给出路径和路径长度的定义:

从树的一个结点到另一个结点之间的分支构成这两点之间的路径,路径上的分支数目叫路径长度,树的路径长度为从根到每一个结点的路径长度之和。

带权路径长度:为该结点到跟的路径长度和结点上权的乘积。 树的带权路径:根到每一个结点的路径长度和结点上权的乘积之和。 其中带权路径长度WPL最小的二叉树称为最优二叉树或赫夫曼树.

2>先根据输入确定每一个字符的总数m和其出现的次数wi（即权值），然后根据这m个权值构成m棵二叉树集合F，其中每一棵二叉树Ti中只有一个带权为wi的根结点，且根结点的权值为wi； 3>在F中殉难区两棵权值最小的书作为左右子树根结点权值之和； 4>在F中删除这两棵树，同时将新得到的二叉树加入F中； 5>重复（2）和（3），直到F中只含一棵树为止

五、源程序清单:

包含三个文件

hfclass.h // 类的建立 hfclass.cpp // 类的方法实现 hf.cpp // 运行主函数

hf.cpp //主函数入口

#include\"hfclass.h\" #include using namespace std;

void dealSStr(vectorstr) {

}

char cc; char c;

CdealStr dealstr; while(1) {

cout<<\"编码B 译码Y 返回 F\"<cout<<\"输入字符串\"<if(c=='B'){ } else { }

dealstr.dealStrTraslate(str); dealstr.setStr(str); dealstr.dealStr();

cc=getchar(); if(cc=='\\n') break;

str.push_back(cc);

} void dealFFile() {

char c;

char infile[100]; char outfile[100]; char keyfile[100]; CdealFile pq;

cout<<\"编码Y 解码N 查看文件C 文件编码退出E\"<c=getchar(); if(c=='Y'){

cout<<\"操作对象地址 输出文件地址 钥匙文件地址\"<while(1){

}

cin>>infile>>outfile>>keyfile; }

else if(c=='N') { }

else if(c=='C') { } else

cout<<\"输入文件地址产看地址\"<>infile; pq.chakeFile(infile);

cout<<\"操作对象地址 输出文件地址 钥匙文件地址\"<>infile>>outfile>>keyfile;

pq.dealFileOut(infile,outfile,keyfile); //解码 pq.dealFileIn(infile,outfile,keyfile); //编码

break;

} int main() {

cout<<\"处理文件F..处理字符串S\"<while(c=='F'||c=='S') {

getchar(); vectorstr;

}

if(c=='S') {

dealSStr(str); else }

system(\"cls\"); getchar();

cout<<\"文件编码F..字符串编码S\"<dealFFile();

} {

}

hfclass.h //相关类的声明

#ifndef HFCLASS #define HFCLASS #include #include #include #include #include

int wt; int l; int r; int par; int flag; Hf_node() {

flag=wt=0; l=r=par=-1; } };

/*******************************************/ /* 哈夫曼树建立.操作 */ /*******************************************/ class CHf {

private:

Hf_node *hftree; vectornum; int head;

string *Str;

//构造函shu

public:

};

CHf(vector a);

void start(); void BuildHf(); //找编码 void serch(); //返回编码

string CHf::returnStr(int i); ~CHf();

//初始化树 //建立哈夫曼树

/*******************************************/ /* 文件编码 */ /*******************************************/ class CdealFile{ private:

mapJugeLetter; //判断字符是否第一次出现 };

/*******************************************/ /* 处理字符串编码.... */ /*******************************************/ class CdealStr{ private:

vectorstr;

mapJugeLetter; //判断字符是否第一次出现 mapIntLetter; //标号与字符对应 int LetterTypeNum; //记录字符种类总数 vectorEachLetterNum; //每类字符的个数 mapStrLetter; //字符串与字符的映射 CdealStr(){};

mapIntLetter; //标号与字符对应 int LetterTypeNum; //记录字符种类总数 vectorEachLetterNum; //每类字符的个数 mapStrLetter; //字符串与字符的映射 CdealFile(); //构造函数

void dealFileIn(char *,char *,char *); //压缩文件... void chakeFile(char*); //检查文件内容

public:

void dealFileOut(char *,char *,char *); //解压文件

public:

};

CdealStr(vectorstr); void setStr(vectorstr); //编码处理

void dealStr(); //对输入的一行字符串进行编码并输出

//反编译

void dealStrTraslate(vectorstr);

#endif

hfclass.cpp //相关类的实现

#include\"hfclass.h\" #include #include #include using namespace std;

#define Compare(x,y) (hftree[x].wt/*******************************************/ /* 哈弗建树 */ /*******************************************/ CHf::CHf(vector a){ num=a; }

//初始化树 void CHf::start() {

int i;

for(i=0;i<(int)num.size();i++) {

hftree[i].flag=1; hftree[i].wt=num[i]; } }

hftree=new Hf_node[num.size()*2]; Str=new string[num.size()]; start();

//建立哈夫曼树 void CHf::BuildHf(){ int i,j; int i_m1,i_m2;

for(j=num.size();;j++){

i_m1=i_m2=-1;//标记最小与次小

for(i=0;i<(int)(2*num.size());i++){//选择... if(hftree[i].flag==0) continue; if(i_m1==-1){

i_m1=i;

continue; }

if(i_m2==-1){ i_m2=i;

if(Compare(i_m2,i_m1)) swap(i_m1,i_m2); continue;

}

if(Compare(i,i_m2)){ if(Compare(i,i_m1)){

i_m2=i;

swap(i_m2,i_m1);

}

else i_m2=i;

} }

if(i_m2==-1){ //建树完成 } else {

hftree[j].wt=hftree[i_m1].wt+hftree[i_m2].wt; hftree[j].l=i_m1; hftree[j].r=i_m2; hftree[i_m1].par=j; hftree[i_m2].par=j; hftree[i_m1].flag=0; hftree[i_m2].flag=0; head=i_m1;break;

//处理最小..次小

}

}

}

hftree[j].flag=1;

//找编码 void CHf::serch()

//返回编码.

string CHf::returnStr(int i) { }

//析构函数 CHf::~CHf()

{ return Str[i];

} }

}

int mm=0; for(i--;i>=0;i--)

Str[k]+=str[i];

int per=hftree[tmp].par; if(hftree[per].l==tmp) else

str[i++]='1'; str[i++]='0';

{

for(int k=0;k<(int)num.size();k++) {

int i=0;

char *str=new char[num.size()*2]; for(;;) {

if(hftree[tmp].par==-1) {break;}

int tmp=k;

tmp=hftree[tmp].par;

delete [] Str; delete hftree;

}

/*******************************************/ /* 字符串处理 */ /*******************************************/

//构造函数

CdealStr::CdealStr(vectorstr){ } //传值

void CdealStr::setStr(vectorstr) { }

//编码处理 对输入的一行字符串进行编码并输出 void CdealStr::dealStr(){

int i;

for(i=0;i<(int)str.size()-1;i++) {

int mid=JugeLetter[str[i]]; if(mid==0) {

JugeLetter[str[i]]=EachLetterNum.size()+1; IntLetter[EachLetterNum.size()]=str[i];

this->str.clear(); this->str=str;

IntLetter.clear(); EachLetterNum.clear(); StrLetter.clear(); this->str.clear();

this->str=str;

JugeLetter.clear();

EachLetterNum.push_back(1);

} else {

EachLetterNum[mid-1]++;

}

}

CHf chf(EachLetterNum); chf.BuildHf(); chf.serch();

for(i=0;i<(int)IntLetter.size();i++) { }

int mid=JugeLetter[IntLetter[i]];

cout<for(i=0;i<(int)str.size();i++) { }

cout<int mid=JugeLetter[str[i]]; cout<StrLetter[chf.returnStr(mid-1)]=IntLetter[mid-1];

//解码

void CdealStr::dealStrTraslate(vectorsstr){ }

/*******************************************/ /* 文件编码 */ /*******************************************/

for(int i=0;i<(int)sstr.size();) { }

cout<string ss; while(1) { }

if(StrLetter[ss]==NULL) { ss+=sstr[i++];continue;} else { }

cout<//构造函数

CdealFile::CdealFile() { }

//压缩文件...

void CdealFile::dealFileIn(char *infile,char *outfile,char *keyfile) {

//读文件 ifstream file1; file1.open(infile);

//输出钥匙 ofstream file2;

for(int i=0;i<(int)IntLetter.size();i++) { //编码

CHf chf(EachLetterNum); chf.BuildHf(); chf.serch(); char c;

while(!file1.eof()) {

file1>>c;

int mid=JugeLetter[c]; if(mid==0) {

JugeLetter[c]=EachLetterNum.size()+1;

IntLetter[EachLetterNum.size()]=c; EachLetterNum.push_back(1);

} else { }

file1.close();

EachLetterNum[mid-1]++; }

file2.open(keyfile);

int mid=JugeLetter[IntLetter[i]];

}

string sss=chf.returnStr(mid-1); StrLetter[sss]=IntLetter[mid-1]; sss.push_back(IntLetter[mid-1]); file2<file2.close(); //输出编码 ofstream file3; file3.open(outfile); char cc;

file1.open(infile); { }

file1.close(); file3.close(); system(\"cls\"); getchar();

cout<<\" 编码成功！！回车返回..\"<while(!file1.eof()) { }

file1>>cc;

int mid=JugeLetter[cc]; string ss=chf.returnStr(mid-1); file3<//解压文件

void CdealFile::dealFileOut(char *infile,char *outfile,char *keyfile) {

mapmm; mm.clear(); //处理钥匙 ifstream file1; file1.open(keyfile); string ss; file1>>ss;

while(1) { }

file1.close(); //查编码 ifstream file2; file2.open(infile); ofstream file3; file3.open(outfile); ss.clear(); char c; file2>>c; while(1) { }

file3<cout<<\" 解码成功！！回车返回..!\"<if(mm[ss]==NULL) { } else { } file2>>c; if(file2.eof())

break;

file3<string sss(ss,0,(int)ss.length()-1); mm[sss]=ss[(int)ss.length()-1]; file1>>ss; if(file1.eof())

break;

}

getchar(); system(\"cls\");

//查看文件内容

void CdealFile::chakeFile(char *infile) { }

ifstream file1; char c;

while(!file1.eof()) { }

cout<file1>>c; cout<file1.open(infile);

六、运行结果 1>字符串编码与解码

:

2>文件编码

文件编码结果

文件解码

文件解码结果

七、实验运行情况分析

程序运行成功,且调试成功，此程序通过输入一行字符串或者针对一个txt的文件两种方式进行的编码，在主函数中设计了一个dealSStr和dealFFile函数来来分别代表两种不同对象的操作，通过分别设计操作类与其公共建树类，达到编码；通过huffman算法求出不同字符的相应代码并将编码合理处理，文件则建立新的编码文件以及钥匙文件（各个字符的编码），进行保存，方便以后解码