当前位置:文档之家› 数据结构(C语言版)实验报告(哈夫曼树)

数据结构(C语言版)实验报告(哈夫曼树)

数据结构(C语言版)实验报告(哈夫曼树)
数据结构(C语言版)实验报告(哈夫曼树)

《数据结构与算法》实验报告

一、需求分析

1.问题描述:

利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输

时间,降低传输成本。但是,这要求在发送端通过一个编码系统对

待传数据预先编码,在接收端将传来的数据进行译码(复原)。对于双

工通道(及可以双向传输信息的通道),每端都需要一个完整的编/

译码系统。试为这样的信息收发站写一个哈夫曼的编/译码系统。

2.基本要求

一个完整的系统应具有以下功能:

(1)I:初始化(Initialization)。从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树,并将它存于文件hfmTree中。

(2)E:编码(Encoding)。利用已建好的哈夫曼树(如不在内存,则从文件hfmTree中读入),对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中。

(3)D:译码(Decoding)。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码,结果存入文件TextFile中。

(4)P:印代码文件(Print)。将文件CodeFile以紧凑格式显示在终端上,

每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。

(5)T:印哈夫曼树(Tree printing)。将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示出,同时将此字符形式的哈夫曼树写入文件TreePrint中。

3.测试数据

(1)利用教科书例6-2中的数据调试程序。

(2)用下表给出的字符集和频度的实际统计数据建立哈夫曼树,并实现以下报文的编码和译码:“THIS PROGRAM IS MY FAVORITE”。

4,实现提示

(1)编码结果以文本方式存储在文件CodeFile中。

(2)用户界面可以设计为“菜单”方式:显示上述功能符号,再加上“Q”表示退出运行Quit。请用户键入一个选择功能符。此功能执行完

毕后再显示此菜单,直至某次用户选择了“Q”为止。

(3)在程序的一次执行过程中,第一次执行I、D或C命令之后,哈夫曼树已经在内存了,不必再读入。每次执行中不一定执行I命令,因为

文件hfmTree可能早已建好。

二、概要设计

本程序的数据类型定义为:

typedef struct{

unsigned int weight;

unsigned int parent,lchild,rchild;

}HTNode,*HuffmanTree;

typedef char** HuffmanCode;

所实现的功能函数为:

void initHuffmanTree();//选择初始化哈夫曼树的方式

int openfileInit();//通过打开的data.txt文件初始化哈夫曼树该文件是为了测试数据2 包涵26个字符

int inputInit();//通过手动输入字符初始化哈夫曼树

int HuffmanCoding(int *w); //初始化哈夫曼数,按照哈夫曼规则建立二叉树。此函数块调用了Select ()函数。

void Select(int j,int &s1,int &s2); //选择parent为0,且weight最小的两个节点序号为s1,s2 void encoding();//选择哈夫曼编码方式

void openfileEnco();//通过打开文件encode.txt的方式进行编码

void inputEnco();//通过手动输入的方式进行编码

void decode();//选择译码方式

void openfileDeco();//通过打开文件CodeFile.txt的方式进行译码

void inputDeco();//通过手动输入的方式进行译码

void dispHT( HuffmanTree nodeRoot, int level ); //以缩进方式输出哈夫曼树直观图

主函数:

主函数主要设计的是一个分支语句,让用户挑选所实现的功能。

如图所示:

三、详细设计

//程序的头文件

#include

#include

#include

using namespace std;

ofstream outstuf;

typedef struct{

unsigned int weight;

unsigned int parent,lchild,rchild;

}HTNode,*HuffmanTree;

typedef char** HuffmanCode;

HuffmanTree HT=NULL;

int n=0;

HuffmanCode HC=NULL;

char *ch=NULL;

void initHuffmanTree();

int openfileInit();

int inputInit();

int HuffmanCoding(int *w);

void Select(int j,int &s1,int &s2);

void encoding();

void openfileEnco();

void inputEnco();

void decode();

void openfileDeco();

void inputDeco();

void dispHT( HuffmanTree nodeRoot, int level );

void initHuffmanTree(){ //选择初始化哈夫曼树

int sel=0;

for(;;){

cout<<"\t*********************************************************"<

cout<<"\t* "<<"字符集及权值来源\t\t\t\t\t*"<

cout<<"\t*\t"<<"1.使用权值文件data.txt进行编码\t\t\t*"<

cout<<"\t*\t"<<"2.自行输入字符集及权值\t\t\t\t*"<

cout<<"\t*\t"<<"3.返回上层\t\t\t\t\t*"<

cout<<"\t*********************************************************"<

cout<<"请输入您的选择"<

cin>>sel;

if(sel==3) break;

switch(sel)

{case 1:openfileInit();break;

case 2:inputInit();break;

default:cout<<"对不起,您输入的数据有误!请重新输入。"<

}

};

}

int openfileInit(){ //通过打开的data.txt文件初始化哈夫曼树该文件是为了测试数据2 包涵26个字符int *w=(int*)malloc(28*sizeof(int));

ch=(char*)malloc(28*sizeof(char));

n=27;

ifstream infile("data.txt",ios::in);

if(!infile){

cerr<<"open error!"<

exit(1);

}

cout<<" 权值文件中的信息(#代表空格)"<

for(int i=1;infile.eof()==0;i++){

infile>>ch[i];

infile>>w[i];

}

cout<

infile.close();

cout<<" 字符:";

for(i=1;i<10;i++) cout<

cout<<" 权值:";

for(i=1;i<10;i++) cout<

cout<<" 字符:";

for(i=10;i<19;i++) cout<

cout<<" 权值:";

for(i=10;i<19;i++) cout<

cout<<" 字符:";

for(i=19;i<28;i++) cout<

cout<<" 权值:";

for(i=19;i<28;i++) cout<

cout<

n=27;

HuffmanCoding(w);

cout<<" 各字符编码如下:"<

for(i=1;i<=27;i++) {

cout<<" "<

cout<

};

outstuf.open("code.txt",ios::out);

for(i=1;i<=27;i++) {outstuf<

outstuf.close();

return 0;

}

int inputInit(){ //通过手动输入字符初始化哈夫曼树

cout<<" 请输入字符集n\t";

cin>>n;

int *w=(int *)malloc((n+1)*sizeof(int));

if(!w) {cout<<"ERROR";return 0;}

ch=(char *)malloc((n+1)*sizeof(char));

if(!ch) {cout<<"ERROR";return 0;}

cout<<" 请输入各字符\t";

for(int i=1;i<=n;i++) cin>>ch[i];

cout<<" 请输入各权值\t";

for(i=1;i<=n;i++) cin>>w[i];

//outstuf.close();

outstuf.open("hfmTree.txt",ios::out);

for(i=1;i<=n;i++){outstuf<

HuffmanCoding(w);

cout<<" 各字符编码如下:";

for(i=1;i<=n;i++) {

cout<<" "<

cout<

} ;

outstuf.close();

outstuf.open("code.txt",ios::out);

for(i=1;i<=n;i++){outstuf<

outstuf.close();

return 0;

}

int HuffmanCoding(int *w){ //哈夫曼编码

if(n<=1) return 1;

int m=2*n-1;

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));

if(!HT) {cout<<"ERROR";return 0;}

for(int i=1; i<=n; ++i)

{

HT[i].weight=w[i];

HT[i].parent=HT[i].lchild=HT[i].rchild=0;

}

for(;i<=m; ++i) HT[i].weight=HT[i].parent=HT[i].lchild=HT[i].rchild=0;

int s1=0;

int s2=0;

for(i=n+1;i<=m; ++i){

Select(i-1, s1, s2);

HT[s1].parent=i; HT[s2].parent=i;

HT[i].lchild=s1; HT[i].rchild=s2;

HT[i].weight=HT[s1].weight+ HT[s2].weight;

}

HC=(HuffmanCode)malloc((n+1)*sizeof(char*));

char *cd=(char*) malloc(n*sizeof(char));

if(!cd) {cout<<"ERROR";return 0;}

cd[n-1]='\0';

int start;

for(i=1;i<=n;++i){

start=n-1;

for(int c=i,unsigned int f=HT[i].parent;f!=0;c=f,f=HT[f].parent)

{if(HT[f].lchild==c) cd[--start]='0';

else cd[--start]='1';

}

HC[i]=(char*)malloc((n-start)*sizeof(char));

strcpy(HC[i],&cd[start]);

}

free(cd);

return 0;

}

void Select(int j,int &s1,int &s2){ //选择parent为0,且weight最小的两个节点序号为s1,s2 for(int h=1;h<=j;h++)

if(HT[h].parent==0) {s1=h;break;}

h++;

for(;h<=j;h++)

if(HT[h].parent==0) {s2=h;break;}

int m;

if(HT[s1].weight>HT[s2].weight) {m=s1;s1=s2;s2=m;}

h++;

for(;h<=j;h++)

if(HT[s1].weight>HT[h].weight&&HT[h].parent==0) s1=h;

for(m=1;m<=j;m++)

if(HT[s2].weight>HT[m].weight&&m!=s1&&HT[m].parent==0) s2=m; }

void encoding(){ //选择哈夫曼编码方式

int sel=0;

for(;;){

if(!HT) {cout<<"对不起,哈夫曼树不存在!请先建立哈夫曼树。"<

cout<<"\t*********************************************************"<

cout<<"\t*\t"<<"1.使用已有文件encode.txt进行编码\t\t*"<

cout<<"\t*\t"<<"2.自行输入文件进行编码\t\t\t\t*"<

cout<<"\t*\t"<<"3.返回上层\t\t\t\t\t*"<

cout<<"\t*********************************************************"<

cin>>sel;

if(sel==3) break;

switch(sel)

{case 1:openfileEnco();break;

case 2:inputEnco();break;

default:cout<<"对不起,您输入的数据有误!请重新输入。"<

}

}

void openfileEnco(){ //通过打开文件encode.txt的方式进行编码

cout<<" encode.txt文件内容如下(#代表空格):"<

ifstream infile("encode.txt",ios::in);

if(!infile){

cerr<<"open error!"<

exit(1);

}

char *file=(char *)malloc(200*sizeof(char));

for(int i=1;infile.eof()==0&&i!=200;i++){

infile>>file[i];

cout<

}

if(i==200) {

file=(char *)realloc(file,(200+80)*sizeof(char));

for(;infile.eof()==0&&i!=280;i++){

infile>>file[i];

cout<

}

}

infile.close();

cout<

int m=i;

cout<<" 编码结果是:"<

//outstuf.close();

outstuf.open("CodeFile.txt",ios::out);

for(i=1;i

for(int j=1;j<=n;j++)if(file[i]==ch[j]) {cout<

if(j==(n+1)) {cout<

}

cout<

outstuf.close();

}

void inputEnco(){ //通过手动输入的方式进行编码

cout<<" 请输入您要编码的文章(以$作为文章结尾)"<

char *file=(char *)malloc(200*sizeof(char));

for(int i=1;i<200;i++){

cin>>file[i];

if(file[i]=='$') break;

}

if(i==200) {

file=(char *)realloc(file,(200+80)*sizeof(char));

for(;i<280;i++){

cin>>file[i];

if(file[i]=='$') break;

}

}

int m=i;

cout<<" 编码结果是:"<

//outstuf.close();

outstuf.open("CodeFile.txt",ios::out);

for(i=1;i

for(int j=1;j<=n;j++)if(file[i]==ch[j]) {

cout<

outstuf<

}//将编码结果写入CodeFile.txt

if(j==(n+1)) {cout<

}

cout<

outstuf.close();

}

void decode(){ //选择译码方式

int sel=0;

for(;;){

if(!HT) {cout<<"对不起,哈夫曼树不存在!请先建立哈夫曼树。"<

cout<<"\t*********************************************************"<

cout<<"\t* "<<"要译码的文件来源\t\t\t\t\t*"<

cout<<"\t*\t"<<"1.使用已有文件CodeFile.txt进行译码\t\t*"<

cout<<"\t*\t"<<"2.自行输入文件进行译码\t\t\t\t*"<

cout<<"\t*\t"<<"3.返回上层\t\t\t\t\t*"<

cout<<"\t*********************************************************"<

cout<<"请输入您的选择"<

cin>>sel;

if(sel==3) break;

switch(sel)

{case 1:openfileDeco();break;

case 2:inputDeco();break;

default:cout<<"对不起,您输入的数据有误!请重新输入。"<

}

}

void inputDeco(){ //通过手动输入的方式进行译码

int m=2*n-1;

char *password=(char *)malloc(200*sizeof(char));

cout<<" 请输入要译码的文件(以$结束)"<

for(int i=1;i<200&&password[i-1]!='$';i++) cin>>password[i];

if(i==200) {

password=(char *)realloc(password,(200+80)*sizeof(char));

for(;i<280&&password[i]!='$';i++) cin>>password[i];

}

cout<<"译码结果为(#代表空格)"<

//outstuf.close();

outstuf.open("TextFile.txt",ios::out);

for(i=1;password[i]!='$';){

char record[20];

for(int j=0,q=i;password[q]!='$';j++,q++){

if(password[q]=='0') {record[j]='0';m=HT[m].lchild;}

else {record[j]='1';m=HT[m].rchild;}

if(HT[m].rchild==0) {record[j+1]='\0';break;}

}

if(HT[m].rchild!=0) {cout<

for(int p=1;p<=n;p++){

if(!strcmp(record,HC[p])) {outstuf<

}

i=i+strlen(record);

m=2*n-1;

}

cout<

outstuf.close();

}

void openfileDeco(){ //通过打开文件CodeFile.txt的方式进行译码

int m=2*n-1;

cout<<" CodeFile.txt文件内容如下:"<

ifstream infile("CodeFile.txt",ios::in);

if(!infile){

cerr<<"open error!"<

exit(1);

}

char *password=(char *)malloc(200*sizeof(char));

for(int i=1;infile.eof()==0&&i!=200;i++){

infile>>password[i];

cout<

}

if(i==200) {

password=(char *)realloc(password,(200+80)*sizeof(char));

for(;infile.eof()==0&&i!=280;i++){

infile>>password[i];

cout<

}

}

infile.close();

password[++i]='$';

cout<

cout<<"译码结果为(#代表空格)"<

//outstuf.close();

outstuf.open("TextFile.txt",ios::out);

for(i=1;password[i]!='$';){

char record[20];

for(int j=0,q=i;password[q]!='$';j++,q++){

if(password[q]=='0') {record[j]='0';m=HT[m].lchild;}

else {record[j]='1';m=HT[m].rchild;}

if(HT[m].rchild==0) {record[j+1]='\0';break;}

}

if(HT[m].rchild!=0) {cout<

for(int p=1;p<=n;p++){

if(!strcmp(record,HC[p])) { outstuf<

}

i=i+strlen(record);

m=2*n-1;

}

cout<

outstuf.close();

}

void dispHT( HuffmanTree nodeRoot, int level ) {//以缩进方式输出哈夫曼树

if(HT==NULL) return;

if(nodeRoot->rchild) {

dispHT(HT+nodeRoot->rchild,level+1);

}

for(int i=0;i

{cout<<" ";outstuf<<" ";}

else {cout<<"-------";outstuf<<"-------";} }

cout<weight<weight<

if(nodeRoot->lchild!=0 ) {

dispHT(HT+nodeRoot->lchild,level+1);

}

}

int main(){

int sel=0;

cout<<"\t\t\t->欢迎使用哈夫曼编码/译码器<-"<

for(;;){

cout<<"\t*********************************************************"<

cout<<"\t*\t"<<"1.构建哈夫曼树\t\t\t\t\t*"<

cout<<"\t*\t"<<"2.输出哈夫曼树\t\t\t\t\t*"<

cout<<"\t*\t"<<"3.编码\t\t\t\t\t\t*"<

cout<<"\t*\t"<<"4.译码\t\t\t\t\t\t*"<

cout<<"\t*\t"<<"5.退出\t\t\t\t\t\t*"<

cout<<"\t*********************************************************"<

cout<<"请输入您的选择(1-5)"<

cin>>sel;

if(sel==5) break;

switch(sel)

{case 1:initHuffmanTree();break;

case 3:encoding();break;

case 2:{if(HC==NULL) cout<<"对不起,哈夫曼树不存在!请先建立哈夫曼树。"<

else {outstuf.open("TreePrint.txt",ios::out); dispHT(HT+2*n-1,1);outstuf.close();}break;}

case 4:decode();break;

default:cout<<"对不起,您输入的数据有误!请重新输入。"<

}

}

outstuf.close();

cout<<"-------------------------------感谢使用本系统!--------------------------------"<

return 0;

}

四、调试分析

在调试过程中,出现了很多次明明建立了文件却发现未存入数据的情况,为此多次进行调试,发现是打开文件的操作放在了循环体内部导致数据无法写入。

整体而言,整个程序主要使用了HuffmanCoding()的方式进行哈夫曼编码,在encoding()里面用了字符串的匹配进行译码,在decode()里进行了重新遍历树的过程,在算法的效率以及如何更为节省空间的存储数据上都要进一步改进。

五、用户守则

1.本程序的运行环境为windows操作系统,可执行文件为:a.exe

2.为了界面更加友好特将背景颜色设计为黑色,字体为白色。

3.进入演示程序后即显示文本形式的用户界面:

六、测试结果

构建哈夫曼树

使用权值文件构建

各字符编码显示

自行输入建树

输入的字符与权值被保存在hfmTree.txt里面

使用data.txt建立的哈夫曼树输出直观图

同时存入了文件

自行输入文件进行编码

编码结果被存储在CodeFile.txt文件里

通过打开文件进行译码

译码结果被存储

通过打开encode.txt文件进行编码

编码结果同时被存储通过自行输入文件进行译码

译码同时被存储

退出

七、附录(源代码)

#include

#include

#include

using namespace std;

ofstream outstuf;

typedef struct{

unsigned int weight;

unsigned int parent,lchild,rchild;

}HTNode,*HuffmanTree;

typedef char** HuffmanCode;

HuffmanTree HT=NULL;

int n=0;

HuffmanCode HC=NULL;

char *ch=NULL;

void initHuffmanTree();

int openfileInit();

int inputInit();

int HuffmanCoding(int *w);

void Select(int j,int &s1,int &s2);

void encoding();

void openfileEnco();

void inputEnco();

void decode();

void openfileDeco();

void inputDeco();

void dispHT( HuffmanTree nodeRoot, int level );

void initHuffmanTree(){ //选择初始化哈夫曼树

int sel=0;

for(;;){

cout<<"\t*********************************************************"<

cout<<"\t* "<<"字符集及权值来源\t\t\t\t\t*"<

cout<<"\t*\t"<<"1.使用权值文件data.txt进行编码\t\t\t*"<

cout<<"\t*\t"<<"2.自行输入字符集及权值\t\t\t\t*"<

cout<<"\t*\t"<<"3.返回上层\t\t\t\t\t*"<

cout<<"\t*********************************************************"<

cout<<"请输入您的选择"<

cin>>sel;

if(sel==3) break;

switch(sel)

{case 1:openfileInit();break;

case 2:inputInit();break;

default:cout<<"对不起,您输入的数据有误!请重新输入。"<

}

};

}

int openfileInit(){ //通过打开的data.txt文件初始化哈夫曼树该文件是为了测试数据2 包涵26个字符int *w=(int*)malloc(28*sizeof(int));

ch=(char*)malloc(28*sizeof(char));

n=27;

ifstream infile("data.txt",ios::in);

if(!infile){

cerr<<"open error!"<

exit(1);

}

cout<<" 权值文件中的信息(#代表空格)"<

for(int i=1;infile.eof()==0;i++){

infile>>ch[i];

infile>>w[i];

}

cout<

infile.close();

cout<<" 字符:";

for(i=1;i<10;i++) cout<

cout<<" 权值:";

for(i=1;i<10;i++) cout<

cout<<" 字符:";

for(i=10;i<19;i++) cout<

cout<<" 权值:";

for(i=10;i<19;i++) cout<

cout<<" 字符:";

for(i=19;i<28;i++) cout<

cout<<" 权值:";

for(i=19;i<28;i++) cout<

cout<

n=27;

HuffmanCoding(w);

cout<<" 各字符编码如下:"<

for(i=1;i<=27;i++) {

哈夫曼树编码译码实验报告(DOC)

数据结构课程设计设计题目:哈夫曼树编码译码

目录 第一章需求分析 (1) 第二章设计要求 (1) 第三章概要设计 (2) (1)其主要流程图如图1-1所示。 (3) (2)设计包含的几个方面 (4) 第四章详细设计 (4) (1)①哈夫曼树的存储结构描述为: (4) (2)哈弗曼编码 (5) (3)哈弗曼译码 (7) (4)主函数 (8) (5)显示部分源程序: (8) 第五章调试结果 (10) 第六章心得体会 (12) 第七章参考文献 (12) 附录: (12)

在当今信息爆炸时代,如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视,哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。哈夫曼编码是一种编码方式,以哈夫曼树—即最优二叉树,带权路径长度最小的二叉树,经常应用于数据压缩。哈弗曼编码使用一张特殊的编码表将源字符(例如某文件中的一个符号)进行编码。这张编码表的特殊之处在于,它是根据每一个源字符出现的估算概率而建立起来的(出现概率高的字符使用较短的编码,反之出现概率低的则使用较长的编码,这便使编码之后的字符串的平均期望长度降低,从而达到无损压缩数据的目的)。哈夫曼编码的应用很广泛,利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径,对路径上的各分支约定:指向左子树的分支表示“0”码,指向右子树的分支表示“1”码,取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码,这就是哈夫曼编码。哈弗曼译码输入字符串可以把它编译成二进制代码,输入二进制代码时可以编译成字符串。 第二章设计要求 对输入的一串电文字符实现哈夫曼编码,再对哈夫曼编码生成的代码串进行译码,输出电文字符串。通常我们把数据压缩的过程称为编码,解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时,总希望总长度能尽可能短,即采用最短码。假设每种字符在电文中出现的次数为Wi,编码长度为Li,电文中有n种字符,则电文编码总长度为∑WiLi。若将此对应到二叉树上,Wi为叶结点的权,Li为根结点到叶结点的路径长度。那么,∑WiLi 恰好为二叉树上带权路径长度。因此,设计电文总长最短的二进制前缀编码,就是以n种字符出现的频率作权,构造一棵哈夫曼树,此构造过程称为哈夫曼编码。设计实现的功能: (1) 哈夫曼树的建立; (2) 哈夫曼编码的生成; (3) 编码文件的译码。

哈夫曼编码实验报告

中南大学数据结构课程 姓名:刘阳 班级:信息0703 学号:0903070312 实验时间: 08.11.14 指导老师:赵颖

一、实验内容 根据输入的n 个带权结点,构造出哈夫曼树,并且把构造结果输出到屏幕。 二、实验说明 哈夫曼数,也称最优二叉树,是指对于一组带有确定权值的叶结点,构造的具有最小带权路径长度的二叉树。 设二叉树具有n 个带权值的叶结点,那么从根结点到各个叶结点的路径长度与相应结点权值的乘积之和叫做二叉树的带权路径长度WPL ,记作: WPL=k n k k L W *∑=1。在给定一组具有确定权值的叶结点,可以构造出不同的带权二 叉树。根据哈夫曼树的定义,一棵二叉树要使其WPL 值最小,必须使权值越大的叶结点越靠近根结点,而权值越小的叶结点越远离根结点。 在数据通讯中,经常需要将传送的文字转换成由二进制字符0,1组成的二进制串,我们称之为编码。例如,假设要传送的电文为ABACCDA ,电文中只含有A ,B ,C ,D 四种字符,若这四种字符采用下表所示的编码,则电文的代码为000010000100100111 000,长度为21。 在传送电文时,我们总是希望传送时间尽可能短,这就要求电文代码尽可能短。如果在编码时考虑字符出现的频率,让出现频率高的字符采用尽可能短的编码,出现频率低的字符采用稍长的编码,构造一种不等长编码,则电文的代码就可能更短。并且在建立不等长编码时,必须使任何一个字符的编码都不是另一个字符编码的前缀,以避免反译成原文时,编码出现多义性。 在哈夫曼编码树中,树的带权路径长度的含义是各个字符的码长与其出现次数的乘积之和,也就是电文的代码总长,所以采用哈夫曼树构造的编码是一种能使电文代码总长最短的不等长编码。 采用哈夫曼树进行编码,也不会产生上述二义性问题。因为,在哈夫曼树中,每个字符结点都是叶结点,它们不可能在根结点到其它字符结点的路径上,所以一个字符的哈夫曼编码不可能是另一个字符的哈夫曼编码的前缀,从而保证了译码的非二义性。

哈夫曼树 实验报告

计算机科学与技术学院数据结构实验报告 班级2014级计算机1班学号20144138021 姓名张建华成绩 实验项目简单哈夫曼编/译码的设计与实现实验日期2016.1.5 一、实验目的 本实验的目的是进一步理解哈夫曼树的逻辑结构和存储结构,进一步提高使用理论知识指导解决实际问题的能力。 二、实验问题描述 利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码,此实验即设计这样的一个简单编/码系统。系统应该具有如下的几个功能: 1、接收原始数据。 从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树,并将它存于文件hfmtree.dat中。 2、编码。 利用已建好的哈夫曼树(如不在内存,则从文件hfmtree.dat中读入),对文件中的正文进行编码,然后将结果存入文件codefile.dat中。 3、译码。 利用已建好的哈夫曼树将文件codefile.dat中的代码进行译码,结果存入文件textfile.dat中。 4、打印编码规则。 即字符与编码的一一对应关系。 5、打印哈夫曼树, 将已在内存中的哈夫曼树以直观的方式显示在终端上。 三、实验步骤 1、实验问题分析 1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。 在构造哈夫曼树时,设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息,根据二叉树的性质可知,具有n个叶子结点的哈夫曼树共有2n-1个结点,所以数组HuffNode的大小设置为2n-1,描述结点的数据类型为: Typedef strcut { Int weight;/*结点权值*/ Int parent; Int lchild; Int rchild; }HNodeType; 2、求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。 求哈夫曼编码,实质上就是在已建立的哈夫曼树中,从叶子结点开始,沿结点的双亲链域回退到根结点,没回退一步,就走过了哈夫曼树的一个分支,从而得到一位哈夫曼码值,由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列,因此先得到的分支代码为所求编码的低位码,后得到的分支代码位所求编码的高位码,所以设计如下数据类型:

数据结构实验报告哈夫曼树

数据结构实验报告实验题目: Huffman编码与解码 姓名: 学号: 院系:

实验名称: Huffman编码与解码实验 问题描述: 本实验需要以菜单形式完成以下功能: 1、输入电文串 2、统计电文串中各个字符及其出现的次数 3、构造哈弗曼树 4、进行哈弗曼编码 5、将电文翻译成比特流并打印出来 6、将比特流还原成电文 数据结构的描述: 逻辑结构: 本实验可用二叉树实现,其逻辑结构为一对二的形式,即一个结点对应两个结点。在实验过程中我们也应用到了栈的概念。 存储结构: 使用结构体来对数据进行存储: typedef struct { int weight; int parent,lc,rc; }HTNode,*HuffmanTree; typedef struct LNode { char *elem; int stacksize; int top; }SqStack; 在main函数里面定义一个哈弗曼树并实现上述各种功能。 程序结构的描述: 本次实验一共构造了10个函数: 1.void HuffTree(HuffmanTree &HT,int n[],int mun); 此函数根据给定的mun个权值构建哈弗曼树,n[]用于存放num个权值。 2、void Select(HuffmanTree &HT,int n,int i,int &s1,int &s2);

此函数用于在HT[1,i-1]中选择parent为0且weight为最小的两个结点,其下标分别为s1,s2、 3.void HuffmanCoding(HuffmanTree HT,char **&HC,int n); 此函数从哈弗曼树HT上求得n 个叶子结点的哈弗曼编码并存入数组HC中。 4.void Coding(HuffmanTree HT,char **HC,int root,SqStack &S); 此函数用于哈弗曼编码,先序遍历哈弗曼树HT,求得每个叶子结点的编码字符串,存入数组HC,S为一个顺序栈,用来记录遍历路径,root就是哈弗曼数组HT中根结点的位置下标。 5.void InitStack(SqStack &S); 此函数用于初始化一个栈。 6.void Pop(SqStack &S,char e); 此函数为出栈操作。 7.void Push(SqStack &S,char e); 此函数为进栈操作。 8.int StackLength(SqStack S); 此函数用于求栈长,返回一个int型的值。 9.int Find(char a,char s[],int num); 此函数用于查找字符a在电文串中的位置。 10.int Recover(HuffmanTree HT,char **HC,char string[],char a[],char b[],int n); 此函数用于将比特流还原成电文。 调试分析: 输入任意一个字符串,如输入welcometoustc:运行结果如下:

霍夫曼树实验报告

实验二二叉树的遍历及霍夫曼编码 班级:计科1101班 学号:0909101605 姓名:杜茂鹏 2013年5月22日

一、实验目的 掌握二叉树的建立及遍历操作,霍夫曼编码基本操作及存储结构表示 二、实验内容 1. 系统要求包含以下功能 1)初始化:从终端读入字符集大小n,以及n个字符和n个权值(或者读入字符集和频度数据文件),建立哈夫曼树,并将哈夫曼树存入到文件HfmTree 中。 2)编码:利用已建好的哈夫曼树(如果不在内存中,则从文件中读入),从文件ToBeTran中读入原文,对原文进行编码,将编码后的结果存入文件CodeFile 中。 3)译码:利用已建好的哈夫曼树将文件CodeFile中的代码进行译码,结果存入文件TextFile中。 4)打印:打印输出哈夫曼树,显示ToBeTran, TextFile和CodeFile文件的内容。 三、实验要求 1.在上机前写出全部源程序; 2.能在机器上正确运行程序; 3.用户界面友好。 四、概要设计 1)首先动态分配数组存储霍夫曼树及存储霍夫曼编码表,然后从终端或文件读入霍夫曼树的字符变量及其频度,初始化建立霍夫曼树并将其写入文件HfmTree.txt中。 2)从指定的文件succe.txt中读入原文,利用已经编好的霍夫曼树对其编码,将编码结果写入文件Coding.txt保存。 3)利用已建好的哈夫曼树将文件Coding.txt中的代码进行译码,结果存入文件decoding.txt中。

五、测试数据: 2.原文内容“THIS IS MY PROGRAM” 六、详细设计 实验内容(原理、操作步骤、程序代码) //建立霍夫曼树,对原文进行编码、译码 #include #include #include #include typedef struct tree { char ch; int weight;//权值 int parent,lchild,rchild; }HTNode,*HuffmanTree;//动态分配数组存储霍夫曼树typedef char **HuffmanCode;//动态分配数组存储霍夫曼编码表void Select(HuffmanTree &HT,int* s1,int* s2,int n) { int j; int min1=10000; for(j=1;j<=n;j++) { if(HT[j].parent==0&&min1>HT[j].weight)

哈夫曼树实验报告

哈夫曼树实验报告 Company number:【0089WT-8898YT-W8CCB-BUUT-202108】

计算机科学与技术学院数据结构实验报告 班级 2014级计算机1班学号姓名张建华成绩 实验项目简单哈夫曼编/译码的设计与实现实验日期一、实验目的 本实验的目的是进一步理解哈夫曼树的逻辑结构和存储结构,进一步提高使用理论知识指导解决实际问题的能力。 二、实验问题描述 利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码,此实验即设计这样的一个简单编/码系统。系统应该具有如下的几个功能: 1、接收原始数据。 从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树,并将它存于文件中。 2、编码。 利用已建好的哈夫曼树(如不在内存,则从文件中读入),对文件中的正文进行编码,然后将结果存入文件中。 3、译码。 利用已建好的哈夫曼树将文件中的代码进行译码,结果存入文件中。 4、打印编码规则。 即字符与编码的一一对应关系。 5、打印哈夫曼树, 将已在内存中的哈夫曼树以直观的方式显示在终端上。 三、实验步骤 1、实验问题分析 1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。 在构造哈夫曼树时,设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息,根据二叉树的性质可知,具有n个叶子结点的哈夫曼树共有2n-1个结点,所以数组HuffNode的大小设置为2n-1,描述结点的数据类型为: Typedef strcut { Int weight;/*结点权值*/ Int parent; Int lchild; Int rchild; }HNodeType; 2、求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。 求哈夫曼编码,实质上就是在已建立的哈夫曼树中,从叶子结点开始,沿结点的双亲链域回退到根结点,没回退一步,就走过了哈夫曼树的一个分支,从而得到一位哈夫曼码值,由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路

哈夫曼树的实验报告1

一、需求分析 1、本演示程序实现Haffman编/译码器的作用,目的是为信息收发站提供一个编/译系统, 从而使信息收发站利用Haffman编码进行通讯,力求达到提高信道利用率,缩短时间,降低成本等目标。系统要实现的两个基本功能就是:①对需要传送的数据预先编码; ②对从接收端接收的数据进行译码; 2、本演示程序需要在终端上读入n个字符(字符型)及其权值(整形),用于建立Huffman 树,存储在文件hfmanTree.txt中;如果用户觉得不够清晰还可以打印以凹入表形式显示的Huffman树; 3、本演示程序根据建好的Huffman树,对文件的文本进行编码,结果存入文件CodeFile 中;然后利用建好的Huffman树将文件CodeFile中的代码进行译码,结果存入文件TextFile中;最后在屏幕上显示代码(每行50个),同时显示对CodeFile中代码翻译后的结果; 4、本演示程序将综合使用C++和C语言; 5、测试数据: (1)教材例6-2中数据:8个字符,概率分别是0.05,0.29,0.07,0.08,0.14,0.23,0.03, 0.11,可将其的权值看为5,29,7,8,14,23,3,11 (2)用下表给出的字符集和频度的实际统计数据建立Haffman树,并实现以下报文的编码和 一、概要设计 1、设定哈夫曼树的抽象数据类型定义 ADT Huffmantree{ 数据对象:D={a i| a i∈Charset,i=1,2,3,……n,n≥0} 数据关系:R1={< a i-1, a i >| a i-1, a i∈D, i=2,3,……n} 基本操作: Initialization(&HT,&HC,w,n,ch) 操作结果:根据n个字符及其它们的权值w[i],建立Huffman树HT,用字符数组ch[i]作为中间存储变量,最后字符编码存到HC中; Encodeing(n) 操作结果:根据建好的Huffman树,对文件进行编码,编码结果存入到文件CodeFile 中 Decodeing(HT,n) 操作结果:根据已经编译好的包含n个字符的Huffman树HT,将文件的代码进行翻译,结果存入文件TextFile中 } ADT Huffmantree

赫夫曼树实验报告

实验报告 实验原理: 霍夫曼编码(Huffman Coding)是一种编码方式,是一种用于无损数据压缩的熵编码(权编码)算法。1952年,David A. Huffman在麻省理工攻读博士时所发明的。 在计算机数据处理中,霍夫曼编码使用变长编码表对源符号(如文件中的一个字母)进行编码,其中变长编码表是通过一种评估来源符号出现机率的方法得到的,出现机率高的字母使用较短的编码,反之出现机率低的则使用较长的编码,这便使编码之后的字符串的平均长度、期望值降低,从而达到无损压缩数据的目的。 例如,在英文中,e的出现机率最高,而z的出现概率则最低。当利用霍夫曼编码对一篇英文进行压缩时,e极有可能用一个比特来表示,而z则可能花去25个比特(不是26)。用普通的表示方法时,每个英文字母均占用一个字节(byte),即8个比特。二者相比,e使用了一般编码的1/8的长度,z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算,就可以大幅度提高无损压缩的比例。 霍夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的路径长度是从树根到每一结点的路径长度之和,记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln),N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径长度为Li(i=1,2,...n)。 可以证明霍夫曼树的WPL是最小的。 实验目的: 本实验通过编程实现赫夫曼编码算法,使学生掌握赫夫曼树的构造方法,理解树这种数据结构的应用价值,并能熟练运用C语言的指针实现构建赫夫曼二叉树,培养理论联系实际和自主学习的能力,加强对数据结构的原理理解,提高编程水平。 实验内容: (1)实现输入的英文字符串输入,并设计算法分别统计不同字符在该字符串中出现的次数,字符要区分大小写;

哈夫曼树实验报告

数据结构实验报告 实验名称:实验三哈夫曼树 学生姓名: 班级: 班内序号: 学号: 日期: 程序分析: 存储结构:二叉树 程序流程: template class BiTree { public: ) 1.初始化链表的头结点

2.获得输入字符串的第一个字符,并将其插入到链表尾部,n=1(n记录的是链 表中字符的个数) 3.从字符串第2个字符开始,逐个取出字符串中的字符 将当前取出的字符与链表中已经存在的字符逐个比较,如果当前取出的 字符与链表中已经存在的某个字符相同,则链表中该字符的权值加1。 如果当前取出的字符与链表中已经存在的字符都不相同,则将其加入到 链表尾部,同时n++ =n(tSize记录链表中字符总数,即哈夫曼树中叶子节点总数) 5.创建哈夫曼树 6.销毁链表 源代码: void HuffmanTree::Init(string Input) { Node *front=new Node; 建哈夫曼树(void HuffmanTree::CreateCodeTable(Node *p)) 算法伪代码: 1.创建一个长度为2*tSize-1的三叉链表 2.将存储字符及其权值的链表中的字符逐个写入三叉链表的前tSize个结点 的data域,并将对应结点的孩子域和双亲域赋为空 3.从三叉链表的第tSize个结点开始,i=tSize 3.1从存储字符及其权值的链表中取出两个权值最小的结点x,y,记录其 下标x,y。 3.2将下标为x和y的哈夫曼树的结点的双亲设置为第i个结点 3.3将下标为x的结点设置为i结点的左孩子,将下标为y的结点设置为 i结点的右孩子,i结点的权值为x结点的权值加上y结点的权值,i 结点的双亲设置为空 4. 根据哈夫曼树创建编码表

哈夫曼树及其操作-数据结构实验报告(2)

电子科技大学 实验报告 课程名称:数据结构与算法 学生姓名:陈*浩 学号:************* 点名序号: *** 指导教师:钱** 实验地点:基础实验大楼 实验时间: 2014-2015-2学期 信息与软件工程学院

实验报告(二) 学生姓名:陈**浩学号:*************指导教师:钱** 实验地点:科研教学楼A508实验时间:一、实验室名称:软件实验室 二、实验项目名称:数据结构与算法—树 三、实验学时:4 四、实验原理: 霍夫曼编码(Huffman Coding)是一种编码方式,是一种用于无损数据压缩的熵编码(权编码)算法。1952年,David A. Huffman在麻省理工攻读博士时所发明的。 在计算机数据处理中,霍夫曼编码使用变长编码表对源符号(如文件中的一个字母)进行编码,其中变长编码表是通过一种评估来源符号出现机率的方法得到的,出现机率高的字母使用较短的编码,反之出现机率低的则使用较长的编码,这便使编码之后的字符串的平均长度、期望值降低,从而达到无损压缩数据的目的。 例如,在英文中,e的出现机率最高,而z的出现概率则最低。当利用霍夫曼编码对一篇英文进行压缩时,e极有可能用一个比特来表示,而z则可能花去25个比特(不是26)。用普通的表示方法时,每个英文字母均占用一个字节(byte),即8个比特。二者相比,e使用了一般编码的1/8的长度,z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算,就可以大幅度提高无损压缩的比例。 霍夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的路径长度是从树根到每一结点的路径长度之和,记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln),N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径长度为Li(i=1,2,...n)。 可以证明霍夫曼树的WPL是最小的。

数据结构实验三哈夫曼树实验报告

题目:哈夫曼编/译码器 一、题目要求: 写一个哈夫曼码的编/译码系统,要求能对要传输的报文进行编码和解码。构造哈夫曼树时,权值小的放左子树,权值大的放右子树,编码时右子树编码为1,左子树编码为0. 二、概要设计: 数据结构: typedef struct { int bit[MAXBIT]; int start; } HCodeType; /* 编码结构体 */ typedef struct { int weight; int parent; int lchild; int rchild; char value; } HNode; /* 结点结构体 */ 函数: void DEMONHuffmanTree (HNode HuffNode[MAXNODE], int n) 作用:构造一个哈夫曼树,并循环构建 int main () 作用:运用已经构建好的哈弗曼树,进行节点的处理,达到成功解码编译 三、详细设计: 哈夫曼树的建立: void DEMONHuffmanTree (HNode HuffNode[MAXNODE], int n) { int i = 0, j, m1, m2, x1, x2; char x; /* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */ while (i

HuffNode[i].rchild =-1; scanf("%c",&x); scanf("%c",&HuffNode[i].value); //实际值,可根据情况替换为字母 i++; } /* 输入 n 个叶子结点的权值 */ scanf("%c",&x); for(i=0;i

哈夫曼树实验报告(付原C语言程序)

哈夫曼树实验报告 需求分析: 从终端读入一串字符,利用建立好的哈夫曼树对其进行编码,储存到文件当中去,然后从文件读入哈夫曼编码,针对每个字母对其进行译码,翻译为原来的信息。 二、概要设计 程序分为以下几个模块: 1、从终端读入字符集大小,n个字符和n个权值,建立哈夫曼树,写入文件hfmTree中去。 2、对hfmTree进行编码,建立hfm编码表。 3、从文件ToTran读入信息,根据hfm编码表对其进行hfm编码,将编码后的信息写入文件Codefile 中去 4、对Codefile文件反向译码,结果储存在Textfile中去。 5、将建立的hfmTree打印在终端上,并储存于相应的Treeprint文件中去。 抽象的数据定义如下: 哈夫曼树结构 typedef struct //定义哈夫曼树的结构 { int weight; //权值 int parent; //双亲 int lchild; //左孩子 int rchild; //右孩子 }htnode,huffmantree[M+1]; 建立哈夫曼树 void crthuffmantree(huffmantree ht,int w[],int n) //初始化哈夫曼树 { int i,s1,s2,m; for(i=1;i<=n;i++) { ht[i].weight=w[i]; ht[i].parent=0; ht[i].lchild=0; ht[i].rchild=0; } m=2*n-1; for(i=n+1;i<=m;i++) { ht[i].weight=0; ht[i].parent=0; ht[i].lchild=0; ht[i].rchild=0; } for(i=n+1;i<=m;i++) { select(ht,i-1,&s1,&s2); ht[i].weight=ht[s1].weight+ht[s2].weight; ht[s1].parent=i;

哈夫曼编码实验报告

哈夫曼编码: 哈夫曼编码,又称霍夫曼编码,是一种编码方式,哈夫曼编码是可变字长编码的一种。Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就叫做Huffman编码。 发展历史: 1951年,哈夫曼和他在MIT信息论的同学需要选择是完成学期报告还是期末考试。导师Robert M. Fano给他们的学期报告的题目是,寻找最有效的二进制编码。由于无法证明哪个已有编码是最有效的,哈夫曼放弃对已有编码的研究,转向新的探索,最终发现了基于有序频率二叉树编码的想法,并很快证明了这个方法是最有效的。由于这个算法,学生终于青出于蓝,超过了他那曾经和信息论创立者香农共同研究过类似编码的导师。 1952年,David A. Huffman在麻省理工攻读博士时发表了《一种构建极小多余编码的方法》(A Method for the Construction of Minimum-Redundancy Codes)一文,它一般就叫做Huffman编码。 Huffman在1952年根据香农(Shannon)在1948年和范若(Fano)在1949年阐述的这种编码思想提出了一种不定长编码的方法,也称霍夫曼(Huffman)编码。霍夫曼编码的基本方法是先对图像数据扫描一遍,计算出各种像素出现的概率,按概率的大小指定不同长度的唯一码字,由此得到一张该图像的霍夫曼码表。编码后的

图像数据记录的是每个像素的码字,而码字与实际像素值的对应关系记录在码表中。 赫夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就称Huffman 编码。下面引证一个定理,该定理保证了按字符出现概率分配码长,可使平均码长最短。

数据结构实验报告(哈夫曼树)

数据结构实验报告实验题目:Huffman编码与解码 姓名: 学号: 院系:

实验名称: Huffman编码与解码实验 问题描述: 本实验需要以菜单形式完成以下功能: 1.输入电文串 2.统计电文串中各个字符及其出现的次数 3.构造哈弗曼树 4.进行哈弗曼编码 5.将电文翻译成比特流并打印出来 6.将比特流还原成电文 数据结构的描述: 逻辑结构: 本实验可用二叉树实现,其逻辑结构为一对二的形式,即一个结点对应两个结点。在实验过程中我们也应用到了栈的概念。 存储结构: 使用结构体来对数据进行存储: typedef struct { int weight; int parent,lc,rc; }HTNode,*HuffmanTree; typedef struct LNode { char *elem; int stacksize; int top; }SqStack; 在main函数里面定义一个哈弗曼树并实现上述各种功能。 程序结构的描述: 本次实验一共构造了10个函数: 1.void HuffTree(HuffmanTree &HT,int n[],int mun); 此函数根据给定的mun个权值构建哈弗曼树,n[]用于存放num个权值。 2.void Select(HuffmanTree &HT,int n,int i,int &s1,int &s2);

此函数用于在HT[1,i-1]中选择parent为0且weight为最小的两个结点,其下标分别为s1,s2. 3.void HuffmanCoding(HuffmanTree HT,char **&HC,int n); 此函数从哈弗曼树HT上求得n 个叶子结点的哈弗曼编码并存入数组HC中。 4.void Coding(HuffmanTree HT,char **HC,int root,SqStack &S); 此函数用于哈弗曼编码,先序遍历哈弗曼树HT,求得每个叶子结点的编码字符串,存入数组HC,S为一个顺序栈,用来记录遍历路径,root是哈弗曼数组HT中根结点的位置下标。 5.void InitStack(SqStack &S); 此函数用于初始化一个栈。 6.void Pop(SqStack &S,char e); 此函数为出栈操作。 7.void Push(SqStack &S,char e); 此函数为进栈操作。 8.int StackLength(SqStack S); 此函数用于求栈长,返回一个int型的值。 9.int Find(char a,char s[],int num); 此函数用于查找字符a在电文串中的位置。 10.int Recover(HuffmanTree HT,char **HC,char string[],char a[],char b[],int n); 此函数用于将比特流还原成电文。 调试分析: 输入任意一个字符串,如输入welcometoustc:运行结果如下:

树和哈夫曼树实验报告

树和哈夫曼树实验报告 一.实验目的 练习树和哈夫曼树的有关操作,和各个算法程序,理解哈夫曼树的编码和译码 二.实验环境 Microsoft visual c++ 三.实验问题描述 1. 问题描述:建立一棵用二叉链表方式存储的二叉树,并对其进行遍历(先序、中序和后序),打印输出遍历结果。 基本要求:从键盘接受输入先序序列,以二叉链表作为存储结构,建立二叉树(以先序来建立),并将此二叉树按照“树状形式”打印输出,然后对其进行遍历(先序、中序和后序),最后将遍历结果打印输出。在遍历算法中要求至少有一种遍历采用非递归方法。 测试数据: ABC??DE?G??F???(其中?表示空格字符) 输出结果为: 先序:ABCDEGF 先序:CBEGDFA 先序:CGEFDBA 2. 问题描述:利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接受端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。 基本要求:(至少完成功能1-2) 一个完整的系统应具有以下功能: I:初始化(Initialization)。从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树,并将它存于文件hfmTree中。 基本要求: E:编码(Encoding)。利用已建好的哈夫曼树(如不在内存,则从文件hfmTree中读入),对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中。 D:译码(Decoding )。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码,结果存入文件TextFile中。 P:印代码文件(Print)。将文件CodeFile以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。 T:印哈夫曼树(TreePrinting)。将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件TreePrint中。 测试数据: 设权值w=(5,29,7,8,14,23,3,11),n=8。 按照字符‘0’或‘1’确定找左孩子或右孩子,则权值对应的编码为: 5:0001,29:11,7:1110,8:1111 14:110,23:01,3:0000,11:001 用下表给出的字符集和频度的实际统计数据建立哈夫曼树,并实现以下报文的编码和译码:“THIS PROGRAM IS MY FAVORITE”。 四.实验主要程序流

数据结构实验三哈夫曼树实验报告

数据结构实验三哈夫曼树实验报告

题目:哈夫曼编/译码器 一、题目要求: 写一个哈夫曼码的编/译码系统,要求能对要传输的报文进行编码和解码。构造哈夫曼树时,权值小的放左子树,权值大的放右子树,编码时右子树编码为1,左子树编码为0. 二、概要设计: 数据结构: typedef struct { int bit[MAXBIT]; int start; } HCodeType; /* 编码结构体 */

typedef struct { int weight; int parent; int lchild; int rchild; char value; } HNode; /* 结点结构体 */ 函数: void DEMONHuffmanTree (HNode HuffNode[MAXNODE], int n) 作用:构造一个哈夫曼树,并循环构建 int main () 作用:运用已经构建好的哈弗曼树,进行节点的处理,达到成功解码编译 三、详细设计: 哈夫曼树的建立: void DEMONHuffmanTree (HNode HuffNode[MAXNODE], int n) { int i = 0, j, m1, m2, x1, x2; char x;

/* 初始化存放哈夫曼树数组HuffNode[] 中的结点*/ while (i

哈夫曼树及其操作-数据结构实验报告(2)

电子科技大学实验报告 课程名称:数据结构与算法学生姓名:陈*浩 学号:************* 点名序号:*** 指导教师:钱** 实验地点:基础实验大楼 实验时间:2015.5.7 2014-2015-2学期 信息与软件工程学院

实验报告(二) 学生姓名:陈**浩学号:*************指导教师:钱** 实验地点:科研教学楼A508实验时间:2015.5.7 一、实验室名称:软件实验室 二、实验项目名称:数据结构与算法—树 三、实验学时:4 四、实验原理: 霍夫曼编码(Huffman Coding)是一种编码方式,是一种用于无损数据压缩的熵编码(权编码)算法。1952年,David A. Huffman在麻省理工攻读博士时所发明的。 在计算机数据处理中,霍夫曼编码使用变长编码表对源符号(如文件中的一个字母)进行编码,其中变长编码表是通过一种评估来源符号出现机率的方法得到的,出现机率高的字母使用较短的编码,反之出现机率低的则使用较长的编码,这便使编码之后的字符串的平均长度、期望值降低,从而达到无损压缩数据的目的。 例如,在英文中,e的出现机率最高,而z的出现概率则最低。当利用霍夫曼编码对一篇英文进行压缩时,e极有可能用一个比特来表示,而z则可能花去25个比特(不是26)。用普通的表示方法时,每个英文字母均占用一个字节(byte),即8个比特。二者相比,e使用了一般编码的1/8的长度,z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算,就可以大幅度提高无损压缩的比例。 霍夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的路径长度是从树根到每一结点的路径长度之和,记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln),N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径长度为Li(i=1,2,...n)。 可以证明霍夫曼树的WPL是最小的。

哈夫曼实验报告材料(附代码)

哈弗曼编码/译码器 一、程序的功能分析 1.构造哈夫曼树及哈夫曼编码:从终端读入字符集大小n、n个字符以及n个对应的权值,建立哈夫曼树;利用已经建好的哈夫曼树求每个叶结点的哈夫曼编码,并保存。 2.编码:利用已构造的哈夫曼编码对“明文”文件中的正文进行编码,然后将结果存入“密文”文件中。 3.译码:将“密文”文件中的0、1代码序列进行译码。(读文件) 4.打印“密文”文件:将文件以紧凑格式显示在终端上,每行30个代码;同时,将此字符形式的编码文件保存。 5.打印哈夫曼树及哈夫曼编码:将已在存中的哈夫曼树以凹入表形式显示在终端上,同时将每个字符的哈夫曼编码显示出来;并保存到文件。 二、基本要求分析 1、输入输出的要求 按提示容从键盘输入命令,系统根据用户输入的需求在保证界面友好的前提下输出用户所需信息,并按要求保存文件,以便保存备份信息。 2、测试数据 (1).令叶子结点个数N为4,权值集合为{1,3,5,7},字符集合为{A,B,C,D},且字符集与权值集合一一对应。 (2).令叶子结点个数N为7,权值集合为{12,6,8,18,3,20,2},字符集合为{A,B,C,D,E,F,G},且字符集与权值集合一一对应。 (3).请自行选定一段英文文本,统计给出的字符集,实际统计字符的频度,建立哈夫曼树,构造哈夫曼编码,并实现其编码和译码。 三、概要设计 1.主模块的流程及各子模块的主要功能 主函数负责提供选项功能,循环调控整个系统。 创建模块实现接收字符、权值、构建哈夫曼树,并保存文件,此功能是后续功能的基础。 编码模块实现利用已编好的哈夫曼树对每个字符进行哈夫曼编码,即对每个字符译出其密文代码,并保存文件。 译码模块实现对用户输入的密文翻译成明文,即用户所需的字符串信息。 输出模块实现对已编好的哈夫曼树以凹入表的的形式输出。 2、模块之间的层次关系 1.采用c语言定义的相关数据类型

哈夫曼树上机实验报告

霍夫曼树 实验目的: 掌握结构体、指针及二叉树的生成、遍历等操作掌握霍夫曼编码/译码的原理。 基本要求: 熟练掌握树的操作。 程序实现: 程序第一遍统计原数据中各字符出现的频率,利用得到的频率值创建哈夫曼树,并把树的信息保存起来,以便解压时创建同样的哈夫曼树进行解压;第二遍,根据第一遍扫描得到的哈夫曼树进行编码,并把编码后的码字存储。 要点分析: 题目中涉及的主要知识点: 1、本程序参考霍夫曼算法(由给定的权值构造赫夫曼树): (1)由给定的n个权值{w0, w1, w2, …, wn-1},构造具有n棵二叉树的集合F ={T0, T1, T2, …, Tn-1},其中每一棵二叉树Ti只有一个带有权值wi的根结点,其左、右子树均为空。 (2)重复以下步骤, 直到F中仅剩下一棵树为止:①在F中选取两棵根结点的权值最小的二叉树, 做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。②在F中删去这两棵二叉树。③把新的二叉树加入F。 2、用构造赫夫曼树以完成赫夫曼编码:把d1,d2,…, dn 作为叶子

结点,把w1,w2,…,wn作为叶子结点的权,构造赫夫曼树。在赫夫曼树中结点的左分支赋0,右分支赋1,从根结点到叶子结点的路径上的数字拼接起来就是这个叶子结点字符的编码。 3、译码的过程是分解电文中的字符串,从根出发,按字符‘0’或‘1’确定找左孩子或右孩子,直至叶子节点,便求得该子串相应的字符。心得体会: 通过本次实验,我熟练掌握了结构体、指针及二叉树的生成、遍历等操作,掌握了霍夫曼编码和译码的原理,熟练掌握树的操作,尤其是对霍夫曼树有了更深刻的理解。同时,在编写代码的过程中方,对字符串的相关知识进行了回顾。

相关主题
相关文档 最新文档