哈夫曼编码实验报告

哈夫曼编码器实验报告

学院：计算机学院

班级：计科

姓名：王宇宏

学号： 0801班 04081027（27）

一．实验目的

练习树和哈夫曼树的有关操作，和各个算法程序，理解哈夫曼树的编码和译码

二．实验环境

Microsoft visual c++

三、问题描述

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

低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编码/译码系统。试为这样的信息收发站写一个哈夫曼编码的编码/译码器。

四、需求分析

（1）初始化;从终端输入字符集的大小n，以及n个字符和n个权值建立哈夫曼树。

（2）输出哈夫曼树，及各字符对应的编码。

（3）编码：利用建好的哈夫曼树，对输入的待发送电文进行编码。同时输入原文及编码串。

（4）译码：利用建好的哈夫曼树，对输入的已接收电文进行译码。同时输入编码串及原文。

五、概要设计

#include

#include

#include

#include

#include

//typedef int TElemType;

const int UINT_MAX=1000;

char str[50];

typedef struct

{

int weight,K;

int parent,lchild,rchild;

}HTNode,* HuffmanTree;

typedef char **HuffmanCode; //-----------全局变量-----------------------

HuffmanTree HT;

HuffmanCode HC;

int w[50],i,j,n;

char z[50]; int flag=0;

int numb=0

// -----------------求哈夫曼编码-----------------------

struct cou{

char data; int count;

}cou[50]; int min(HuffmanTree t,int i)

{ // 函数void select()调用

int j,flag;

int k=UINT_MAX; // 取k为不小于可能的值,即k为最大的权值1000 for(j=1;j

if(t[j].weight

k=t[j].weight,flag=j;

t[flag].parent=1;

return flag;

}

//--------------------slect函数----------------------

void select(HuffmanTree t,int i,int &s1,int &s2)

{ // s1为最小的两个值中序号小的那个

int j; s1=min(t,i);

s2=min(t,i);

if(s1>s2)

{

j=s1;

s1=s2;

s2=j;

}

}

// --------------算法6.12--------------------------

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)

{ // w存放n个字符的权值(均>0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC

int m,i,s1,s2,start;

//unsigned c,f;

int c,f;

HuffmanTree p;

char *cd;

if(n

return;//检测结点数是否可以构成树

m=2*n-1;

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0号单元未用 for(p=HT+1,i=1;i

{

p->weight=*w;

p->parent=0;

p->lchild=0;

p->rchild=0;

}

for(;i

p->parent=0;

for(i=n+1;i

{ // 在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2

select(HT,i-1,s1,s2);

HT[s1].parent=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*)); // 分配n个字符编码的头指针向量([0]不用)

cd=(char*)malloc(n*sizeof(char)); // 分配求编码的工作空间 cd[n-1]='\0'; // 编码结束符

for(i=1;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';

HC[i]=(char*)malloc((n-start)*sizeof(char)); // 为第i个字符编码分配空间

strcpy(HC[i],&cd[start]); // 从cd复制编码(串)到HC } free(cd); // 释放工作空间

}

//--------------------- 获取报文并写入文件---------------------------------

int InputCode()

{

//cout

FILE *tobetran;

if((tobetran=fopen("tobetran.txt","w"))==NULL)

{

cout

return 0;

}

cout

gets(str);

fputs(str,tobetran);

cout

fclose(tobetran);

return strlen(str);

}

//--------------初始化哈夫曼链表---------------------------------

void Initialization()

{ int a,k,flag,len;

a=0;

len=InputCode();

for(i=0;i

{k=0;flag=1;

cou[i-a].data=str[i];

cou[i-a].count=1;

while(i>k)

{

if(str[i]==str[k]) {

a++;

flag=0;

} k++;

if(flag==0)

break;

}

if(flag) {

for(j=i+1;j

++cou[i-a].count;}

}

}

n=len-a;

for(i=0;i

{ cout

cout

}

for(i=0;i

{*(z+i)=cou[i].data;

*(w+i)=cou[i].count;

}

HuffmanCoding(HT,HC,w,n);

//------------------------ 打印编码-------------------------------------------

cout

for(i=1;i

{

puts(HC[i]);

}

//-------------------------- 将哈夫曼编码写入文件------------------------

cout

FILE *htmTree;

char r[]={' ','\0'};

if((htmTree=fopen("htmTree.txt","w"))==NULL)

{

cout

return;

}

fputs(z,htmTree);

for(i=0;i

{

fprintf(htmTree,"%6d",*(w+i));

fputs(r,htmTree);

}

for(i=1;i

{

fputs(HC[i],htmTree);

fputs(r,htmTree);

}

fclose(htmTree);

cout

//---------------------编码函数---------------------------------

void Encoding()

{ cout

if((tobetran=fopen("tobetran.txt","rb"))==NULL)

{

cout

if((codefile=fopen("codefile.txt","wb"))==NULL) {

cout

}

char *tran;

i=99;

tran=(char*)malloc(100*sizeof(char));

while(i==99)

{

if(fgets(tran,100,tobetran)==NULL)

{

cout

break;

}

for(i=0;*(tran+i)!='\0';i++) {

for(j=0;j

{

if(*(z+j-1)==*(tran+i))

{

fputs(HC[j],codefile);

if(j>n)

{

cout

}

}

}

}

}

cout

fclose(tobetran);

fclose(codefile);

free(tran);

}

//-----------------译码函数---------------------------------

void Decoding()

{

cout

FILE *codef,*txtfile;

if((txtfile=fopen("txtfile.txt","w"))==NULL)

{

cout

}

if ((codef=fopen("codefile.txt","r"))==NULL)

{ cout

}

char *work,*work2,i2;

int i4=0,i,i3; unsigned long length=10000;

work=(char*)malloc(length*sizeof(char));

fgets(work,length,codef);

work2=(char*)malloc(length*sizeof(char));

i3=2*n-1; for(i=0;*(work+i-1)!='\0';i++)

{ i2=*(work+i);

if(HT[i3].lchild==0)

{

*(work2+i4)=*(z+i3-1);

i4++;

i3=2*n-1;

i--;

}

else if(i2=='0') i3=HT[i3].lchild;

else if(i2=='1') i3=HT[i3].rchild;

}

*(work2+i4)='\0';

fputs(work2,txtfile);

cout

free(work);

free(work2);

fclose(txtfile);

fclose(codef);

}

//-----------------------打印编码的函数----------------------

void Code_printing()

{

cout

if((CodePrin=fopen("CodePrin.txt","w"))==NULL)

{

cout

return;

}

if((codefile=fopen("codefile.txt","r"))==NULL)

{

cout

return;

}

char *work3;

work3=(char*)malloc(51*sizeof(char));

do

{

if(fgets(work3,51,codefile)==NULL)

{

cout

break;

}

fputs(work3,CodePrin);

puts(work3);

}while(strlen(work3)==50); free(work3);

cout

中

fclose(CodePrin);

fclose(codefile); }

//------------------------------- 打印译码函数---------------------------------------------

void Code_printing1()

{ cout

FILE * CodePrin1,* txtfile; if((CodePrin1=fopen("CodePrin1.txt","w"))==NULL)

{

cout

return;

}

if((txtfile=fopen("txtfile.txt","r"))==NULL)

{

cout

return;

}

char *work5;

work5=(char*)malloc(51*sizeof(char));

do

{ if(fgets(work5,51,txtfile)==NULL)

{

cout

break;

}

fputs(work5,CodePrin1);

puts(work5);

}while(strlen(work5)==50);

free(work5);

cout

fclose(CodePrin1);

fclose(txtfile);

}

//------------------------打印哈夫曼树的函数----------------------- void coprint(HuffmanTree start,HuffmanTree HT)

{

if(start!=HT)

{

FILE * TreePrint;

if((TreePrint=fopen("TreePrint.txt","a"))==NULL)

{cout

return;

}

numb++;//该变量为已被声明为全局变量

coprint(HT+start->rchild,HT);

coutweight

fprintf(TreePrint,"%d\n",start->weight);

coprint(HT+start->lchild,HT);

numb--;

fclose(TreePrint);

} }

void Tree_printing(HuffmanTree HT,int w)

{

HuffmanTree p; p=HT+w;

cout

coprint(p,HT);

cout

} //------------------------主函数------------------------------------ void main() {

char choice;

while(choice!='q')

{ cout

cout

cout

cout

cout

cout

cout

cout>choice;

switch(choice)

{

case 'i':

Initialization();

break;

case 'e':

Encoding();

break;

case 'd':

Decoding();

break;

case 'p':

Code_printing();

break;

case 't':

Tree_printing(HT,2*n-1);

break;

case 'y':

Code_printing1();

break;

default:

cout

}

}

free(z);

free(w);

free(HT);

}

运行结果：

六、所遇问题及心得体会

本次试验中所遇到的主要问题为哈弗曼编码的算法，以及整个变量的控制。通过学习课本上的基础编码方法，再加上老师所讲的内容，整理修改后得到这个编码系统。

通过本次试验，掌握了树和哈夫曼树的基本操作，以及各个程序的算法。也

复习了前面所学习的参数调用和控制变量范围。这次课程设计，在编辑中犯了不应有的错误，统计字符时忘记了应该怎样保存数据，对文件的操作也很生疏，在不断的分析后明确并改正了错误和疏漏，是程序有了更高的质量。

总的来说，不仅是实验的结果，更重要的是过程和思考，是我学到了很多的知识，真的是受益匪浅。

附主要算法流程图：

功能结构图：

构造哈夫曼树：

11

哈夫曼编码：

12

参考文献：

【1】 严蔚敏.数据结构（C语言版），清华大学出版社

【2】 谭浩强.C语言程序设计教程，高等教育出版社 13