数据结构实验报告八—哈夫曼编译码

数据结构 实验报告 哈夫曼编/译码

问题描述：

利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工通信（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统，试设计一个哈夫曼编码系统。 基本要求：

(1) 从文件中读入字符集大小n，以及n个字符和n个权值。

(2) 构建哈夫曼树，对每个字符生成哈夫曼编码。

(3) 从文件中读入需编码的字符串，利用哈夫曼编码，对字符串进行编码，编

码结果保存在文件。

一、 需求分析：

（1）、根据输入的字符和字符的权值建立哈夫曼树。

（2）、字符的数目和字符的权值由用户自己设定。

（3）、根据建立的哈夫曼树进行，编码和译码操作。

二、概要设计 ：

1. 哈夫曼树的定义

typedef struct{

char letter; //存储字符

int weight; //存储字符的权值

int parent; //父亲

int lchild; //左孩子

int rchild; //右孩子

}HTNode,*HuffmanTree;

2. 算定义的存储结构

//本结构存储哈夫曼树、编码等，便于后面的操作进行

typedef struct

{

HuffmanTree HT;

//动态分配数组存储哈夫曼编码表

HuffmanCode HC;

//记录输入字符的长度，编码和译码用到

int len;

char *c;//存储输入的字符

}Huf;

数据结构 实验报告 哈夫曼编/译码

3. 一些操作函数

void setHuffmanTree(HuffmanTree &HT,char *str,int *w,int n) 建立哈夫曼树，str是存储输入字符的数组，w 是存储字符权值的数组，n为输入字符的数目

Huf setHuffmanCode(HuffmanTree &HT,HuffmanCode &HC,int n,char *s)

为哈夫曼树编码，HT是已经建立的哈夫曼树，HC用于存储编码，民为字符的数目，s是存储字符的数组

Huf Initialization()

初始化函数

void Encoding(Huf huf)

编码函数

void Decoding(Huf huf)

译码函数

void Print()

打印代码文件的函数

void Treeprinting(Huf huf)

打印哈夫曼树的函数

4. 主函数

void main(){

根据不同的选择，执行特定的函数，完成操作

}

三、详细设计

核心程序为哈夫曼树的构建，实现该功能时，通过不断调用selecte（在已有的结点中选择双亲结点值为0，且权值最小的两个结点）函数查找构造哈夫曼树中的各个子树的结点，直到所有这种结点全部用完，即一颗哈夫曼树即构造完成。

1、 建立哈夫曼树及求哈夫曼编码

//初始化操作，接受输入，调用函数setHuffmanTree，

//setHuffmanCode创建树并编码

Huf Initialization(){

HuffmanTree HT;

HuffmanCode HC;

char c[100];//存放输入的字符

int w[100];//存放字符的权值

int n;

cout<<"请输入字符的个数："<<endl;

cin>>n;

cout<<"请输入所有字符："<<endl;

gets(c);

数据结构 实验报告 哈夫曼编/译码

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

cout<<"请输入第"<<i<<"个字符的权值："<<endl;

cin>>w[i];

}

//将数组c中的元素向右移动一位

for(int j=n-1;j>=0;j--)

{

c[j+1]=c[j];

}

// 调用setHuffmanTree函数

setHuffmanTree(HT,c,w,n);

//调用setHuffmanCode函数

Huf huf=setHuffmanCode(HT,HC,n,c);

return huf;

}

//选择权值最小的两个结点

void Select(HuffmanTree &HT,int s,int &s1,int &s2){

int j, k, i;

j=k=10000;

s1=s2=0;

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

if(HT[i].parent==0){

if(HT[i].weight<j){

k=j;s2=s1;

j=HT[i].weight;

s1=i;

}

else if(HT[i].weight<k){

k=HT[i].weight;

s2=i;

}

}

}

}

//创建哈夫曼树函数的具体实现

void setHuffmanTree(HuffmanTree &HT,char *str,int *w,int n)

{

HuffmanTree p;

int m,i,s1,s2; //s1,s2是权值最小的两个结点的序号

m = 2*n-1; //一棵有N个叶子节点的哈夫曼树共有2*N-1个结点 //动态定义长度，0号单元未使用

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

数据结构 实验报告 哈夫曼编/译码

//初始化

for(p=HT+1,i=1;i<=n;++i,++p){

p->letter = str[i]; p->weight = w[i];

(*p).parent = 0; p->lchild = 0; p->rchild = 0;

}

for(;i<=m;++i,++p){

p->weight=0; p->parent=0; p->lchild=0; p->rchild=0; }

//建立哈夫曼树

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

Select(HT,i-1,s1,s2); //此函数为自己定义用于选择出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;

}

// 将哈夫曼树写入到文件hufTree.dat中

FILE *huftree;

huftree=fopen("hufTree.dat","rt");

if(huftree==NULL)

{ huftree=fopen("hufTree.dat","wt");

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

fprintf(huftree,"%d %d %d %d\n",HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);//向文件中写入

rewind(huftree);

}

}

//从叶子到根结点逆向求每个字符的赫夫曼编码

Huf setHuffmanCode(HuffmanTree &HT,HuffmanCode &HC,int n,char *s){

Huf huf;

// 分配n个字符编码的头指针向量

huf.c=(char *)malloc((n+1)*sizeof(char));

//将以输入的字符存储在huf的c中

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

huf.c[j]=s[j];}

int start = 1; char *cd; int f,c,i;

//分配n个字符编码的头指针向量

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

//临时的编码存储，作用是分配求编码的工作空间

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

cd[n-1]='\0'; //编码结束符

//按已生成的哈夫曼树，逐个求哈夫曼编码并获得各个字符的哈夫曼编码 for(i=1;i<=n;++i){

start = n - 1; //编码结束符的位置

数据结构 实验报告 哈夫曼编/译码

//从叶子到根逆向求编码

for(c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent) if(HT[f].lchild == c) cd[--start] = '0';

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

//为第i个字符编码分配空间

HC[i] = (char *)malloc((n - start) * sizeof(char)); //从cd复制编码（串）到HC

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

}

//将HC,HT,n分别存储到结构体Huf中

huf.HC=HC;

huf.HT=HT;

huf.len=n;

free(cd); //释放工作空间

return huf;//返回值，供后面的操作使用}

2、 编码

//利用已建好的哈夫曼树对文件中的正文进行编码，然后将结果存入文//件codefile.dat中,如果正文中没有要编码的字符，则键盘读入 void Encoding(Huf huf)

{

int i=0,j=0,n;

char ch[10000];

//code为指向文件CodeFile.dat的指针，tbt为指向文件

//ToBeTran的指针

FILE *code,*tbt;

n=huf.len;

tbt=fopen("ToBeTran.dat","rt");

//如果ToBeTran中没有要编码的字符，则键盘读入

//如果ToBeTran中有要编码的字符，则从文件读取

if(tbt==NULL)

{

printf("不存在文件ToBeTran.dat");

printf("\n请输入要进行编码的报文: ");

gets(ch);

printf("\n");

code=fopen("CodeFile.dat","wt+");

}

else

{

fscanf(tbt,"%s",&ch);

fclose(tbt);

code=fopen("CodeFile.dat","wt+");

}

数据结构 实验报告 哈夫曼编/译码

// 将ch中的元素与哈夫曼树中的进行匹配，为字符串编码

while(ch[j])

{

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

if(ch[j]==huf.HT[i].letter)

{ //将编码写入到文件中

fprintf(code,"%s",huf.HC[i]);

break;

}

j++;

}

rewind(code);

fclose(code);

printf("已进行编码，结果保存到文件CodeFile.dat中"); }

3、 译码

//利用已建好的哈夫曼树将文件对CodeFile.dat中的代码进行译码，//结果存入文件TextFile.dat 中

void Decoding(Huf huf)

{

HuffmanTree p;

int i,n,j=0;

char d[10000];

FILE *code;//指向CodeFile.dat的指针

n=huf.len;

code=fopen("CodeFile.dat","rt");

if(code==NULL)

{

printf("没有找到CodeFile.dat文件，先编码\n");

printf("输入哈夫曼码进行译码:");

scanf("%s",&d);

}

else

{

fscanf(code,"%s",d);

fclose(code);

}

code=fopen("TextFile.dat","wt+");

while(d[j])

{

p=&huf.HT[2*n-1];

//从根开始 找叶子节点进行译码

//简而言之就是遇到0向左，遇到一向右，直到找到叶子

数据结构 实验报告 哈夫曼编/译码

while(p->lchild||p->rchild)

{

if(d[j]=='0')

{

i=p->lchild;

p=&huf.HT[i];

}

else

{ i=p->rchild;

p=&huf.HT[i]; }

j++;

}

printf("%c",huf.c[i]);

//将找到叶子节点的字符写入TextFile.dat

fprintf(code,"%c",huf.c[i]); }

fclose(code);

printf("译码成功，结果保存到文件TextFile.dat中");

}

4、 打印代码文件

//将文件CodeFile每行50个代码显示到终端

//将此字符形式的编码写入CodePrin中

void Print()

{

char ch;

//code是指向CodeFile的指针，codeprin是指向

//CodePrin的指针

FILE *code,*codeprin;

code=fopen("CodeFile.dat","r");

codeprin=fopen("CodePrin.dat","w");

//每行输出50个字符，将编码写进文件CodePrin中

for(int i=1;(ch=fgetc(code))!=EOF;i++)

{

if(i>=50){

printf("\n");

fputc('\n',codeprin);

i=1;

}

putchar(ch);

fputc(ch,codeprin);

}

fclose(codeprin);

fclose(code);

数据结构 实验报告 哈夫曼编/译码

printf("\n已经写入到文件CodePrin.dat中\n");

}

5、 打印哈夫曼树

//输出哈夫曼树节点，权值，双亲，左孩子，右孩子

//前n个结点打出对应的字符

void Treeprinting(Huf huf)

{

int j,n;

FILE *tree;

tree=fopen("TreePrint.dat","w");

n=huf.len;

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

printf("\n%4d(%c)%5d%8d%8d%8d",j,huf.c[j],huf.HT[j].weight,huf.HT[j].parent,huf.HT[j].lchild, huf.HT[j].rchild);

fprintf(tree,"\n%4d(%c)%5d%8d%8d%8d",j,huf.c[j],huf.HT[j].weight,huf.HT[j].parent,huf.HT[j].lchild, huf.HT[j].rchild);

}

for (int h=n+1; h<=2*n-1; h++){

printf("\n%4d%8d%8d%8d%8d",h,huf.HT[h].weight,huf.HT[h].parent,huf.HT[h].lchild, huf.HT[h].rchild);

fprintf(tree,"\n%4d%8d%8d%8d%8d",h,huf.HT[h].weight,huf.HT[h].parent,huf.HT[h].lchild, huf.HT[h].rchild);

}

fclose(tree);

}

6、 主函数

//通过不接收不同的输入，调用相应的函数

void main()

{Huf huf;

int num;

char input;

while(1){

cout<<"I:初始化"<<endl;

cout<<"E:编码"<<endl;

cout<<"D:译码"<<endl;

cout<<"P:印代码文件"<<endl;

cout<<"T:打印哈夫曼树"<<endl;

数据结构 实验报告 哈夫曼编/译码

cout<<"Q:退出"<<endl<<endl;

cout<<"请输入你的选择：";

cin>>input;

if(input=='I'||input=='i'){

num=1;

}else if(input=='E'||input=='e'){

num=2;

}else if(input=='D'||input=='d'){

num=3;

}else if(input=='P'||input=='p'){

num=4;

}else if(input=='T'||input=='t'){

num=5;

}else if(input=='Q'||'q'){

num=6;

}else{

num=7;

}

switch(num){

case 1:

huf=Initialization();

getch(); break;

case 2:

Encoding(huf);

getch(); break;

case 3:

Decoding(huf);

getch(); break;

case 4:

Print();

getch(); break;

case 5:

Treeprinting(huf);

getch(); break;

case 6:

return;

default:

printf("选择有错，请重新选择\n");

getch(); break;

}}

}

数据结构 实验报告 哈夫曼编/译码

四、调试分析

1. 开始时并未设计Huf这个结构体，但后来发现进行操作的时候很费力，在编写的过程中，就将后面要用到东西都放到这个结构体中了。可以说这个结构体是在编程过中不断完善的。

2. 在调试过程中发现有一些常犯的错误，如字母的拼写、结尾的分号等，在以后的编程过程中要避免这些错误。在写报告的同时还发现一些细节上的错误，如格式化输出的地方。

3. 由于缺乏MFC的知识，只是将哈夫曼树打印出来，没有将哈夫曼树以树的形式画出来。

4. Select算法的时间复杂度为O(n), setHuffmanTree的时间复杂度为O(n*n), setHuffmanCode的时间复杂度为O(n)。

五、测试结果

本实验的测试结果截图如下：

六、用户使用说明（可选）

1 、本程序的运行环境为windows 操作系统，执行文件为111.exe 2 、运行程序时

提示输入数据 并且输入数据然后回车就可以得到输出结果哈夫曼编码

3.此程序还具有译码功能。

数据结构 实验报告 哈夫曼编/译码

七、实验心得（可选）

通过编写哈夫曼编码器算法及程序的调试，清楚的掌握了二叉树这种存储结构在解决一些问题时的应用和优点，但是在对二叉树进行操作时，尤其对树的编历具体用程序实现时还是不能完全掌握。

附录（实验代码）：

#include<iostream.h>

#include<windows.h>

#include<string.h>

#define MAX 99

char cha[MAX],str[MAX];

char hc[MAX-1][MAX];

int s1,s2; //设置全局变量，以便在select(函数)中返回两个变量

typedef struct //huffman树存储结构

{unsigned int weight;//权值字符出现的频率

int lchild,rchild,parent;

}huftree;

void select(huftree tree[],int k) //找寻parent为0,权最小的两个节点

{int i;

for (i=1;i<=k && tree[i].parent!=0 ;i++); s1=i;

for (i=1;i<=k;i++)

if (tree[i].parent==0 && tree[i].weight<tree[s1].weight) s1=i;

for (i=1; i<=k ; i++)

if (tree[i].parent==0 && i!=s1) break; s2=i;

for (i=1;i<=k;i++)

if ( tree[i].parent==0 && i!=s1 && tree[i].weight<tree[s2].weight) s2=i;

}

void huffman(huftree tree[],int *w,int n) //生成huffman树

{ int m,i;

if (n<=1) return;

m=2*n-1;

for (i=1;i<=n;i++)//将各个字符的频率权值作为森林中的每一棵子树

{ tree[i].weight=w[i]; tree[i].parent=0;

tree[i].lchild=0; tree[i].rchild=0; }

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

{ tree[i].weight=0; tree[i].parent=0;

tree[i].lchild=0; tree[i].rchild=0; }

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

{select(tree, i-1);

tree[s1].parent=i;

数据结构 实验报告 哈夫曼编/译码

tree[s2].parent=i;

tree[i].lchild=s1;

tree[i].rchild=s2;

tree[i].weight =tree[s1]. weight+ tree[s2].weight;}

}

void huffmancode(huftree tree[],char code[],int n)//标记哈夫曼编码

{

int start,c,i,f;

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

cout<<"各字符的哈夫曼编码为:"<<endl;

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

{start=n-1;

for(c=i,f=tree[i].parent;f!=0;c=f,f=tree[f].parent)

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

else code[--start]='1';}

strcpy(hc[i],&code[start]);

cout<<cha[i]<<"的哈夫曼编码为："<<hc[i]<<" "<<endl;

}

}

void tohuffmancode(int n)//将您从键盘上输入的字符转变为对应的哈夫曼编码

{int i=0,j;

cout<<endl<<"输入的字符串转化为哈夫曼编码为:"<<endl;

for (;str[i]!='\0';i++)

{j=0;

for(;str[i]!=cha[j]&&j<=n;) j++;

if (j<=n) cout<<hc[j];}

cout<<endl;

}

void decode(char ch[],huftree tree[],int n)//根据输入的01代码按所得的哈夫曼编码箅到对应的字符

{

int i,j,m;char b;

m=2*n-1;

i=m;

cout<<"请输入二进值数:"<<endl;

cin>>b;

cout<<"解码后的字符串为: "<<endl;

while(b!='\n') //遇到回车时，结束

{ if(b=='0')i=tree[i].lchild;//按输入的二进制码填入对应的哈夫曼树中，从而得到对应的编码 else if(b=='1') i=tree[i].rchild;

数据结构 实验报告 哈夫曼编/译码

else if(b=='e') return;

else

{cout<<"输入的值非法，请重新输入："<<endl;goto L;}

if(tree[i].lchild==0)

{cout<<ch[i]<<" ";

j=i,i=m;

}

L:cin>>b;

}

if(tree[j].lchild!=0)

cout<<endl<<"ERROR"<<endl;

cout<<endl<<endl;

}

void main()

{ system("color ec");

int i=0,j=1,n;

int *w,weight[MAX],st[199]={0};

char code[MAX];

huftree tree[MAX];

w=weight;

cout<<"请输入一段字符串,按回车键结束"<<endl;

cin>>str;

system("pause");

for(;str[i]!='\0';i++) st[str[i]]++;

for(i=0;i<=199;i++) if (st[i]!=0) { cha[j]=i,weight[j]=st[i];j++;}

i=1;

for (n=j-2;i<j-1;i++)

cout<<cha[i]<<" 的权值为："<<weight[i]<<endl;

cout<<endl;

huffman(tree,w,n); //生成huffman树函数，w是存入各字符权值的数组首地址，n是输入字符的种类个数

huffmancode(tree,code,n); //标记哈夫曼编码函数

tohuffmancode(n); //将您从键盘上输入的字符转变为对应的哈夫曼编码函数

decode(cha,tree,n); //根据输入的01代码按所得的哈夫曼编码箅到对应的字符

}