数据结构实验哈夫曼树编码

实验四 哈夫曼树编码

一、实验目的

1、掌握哈夫曼树的一般算法；

2、掌握用哈夫曼树对字符串进行编码；

3、掌握通过哈夫曼树对字符编码进行译码得过程。 二、实验基本要求 1、设计数据结构； 2、设计编码算法；

3、分析时间复杂度和空间复杂度 三、程序实现

此程序中包含六个函数：Select（）、HuffmanTree（）、BianMa（）、BianMa2（）、YiMa（）、 Sum（），其功能及实现过程如下： #include

struct element//哈夫曼树结点类型 { int weight; int lchild,rchild,parent; };

struct Char//字符编码表信息 { char node; int weight; char code[20]; };

void Select(element hT[],int &i1,int &i2,int k)//在hT[]中查找最小值及次小值 { int min1=9999,min2=9999; i1=i2=0; for(int i=0;i

void HuffmanTree(element huffTree[],Char zifuma[],int n) //构建哈夫曼树 { int i,k,i1,i2; for(i=0;i<2*n-1;i++) //初始化 { huffTree[i].parent=-1; huffTree[i].lchild=-1; huffTree[i].rchild=-1; } for(i=0;i

void BianMa(element huffTree[],Char zifuma[],int n)//根据哈夫曼树编码 { int i,m,k,j,l; char temp[20]; if(n==1){ zifuma[0].code[0]='0';zifuma[0].code[1]=0;} else { for(i=0;i

} } }

void BianMa2(Char zifuma[],char zifu[],char bianma[],int n)//根据编码表对字符串编码 { int i,j,k,m; i=k=0; while(zifu[i]) { for(j=0;j

void YiMa(element huffTree[],Char zifuma[],char bianma[],char yima[],int n)//根据编号的码元译成字符串 { int i,j,k; i=j=0; if(n==1) while(bianma[i++]) yima[j++]=zifuma[0].node; else{ while(bianma[i]) { k=2*(n-1); while(!(huffTree[k].lchild==-1&&huffTree[k].rchild==-1)) if(bianma[i++]=='0') k=huffTree[k].lchild; else k=huffTree[k].rchild; yima[j++]=zifuma[k].node; } }

yima[j]=0; }

void Sum(char zifu[],Char bianma[],int &n)//计算字符串中字符种类的个数及其出现次数 {

int i,j; i=j=0; while(zifu[i]) { for(int k=0;k

void main() { int n,i; char a[50],b[200],c[50]; element huffTree[100]; Char w[50]; cout<<\请输入需要编码的字符串:\\n\ cin.getline(a,49); Sum(a,w,n); cout<<\该字符串中共有\类字符。其表示及出现频率分别为：\\n\ cout<<\字符\\t频率\\n\ for(i=0;i

{ cout<

四、运行结果

假设输入的一串字符串为：abcbcaddabbacda

则编译后它的编码为：111000100011010111101011000111 根据它的编码译码结果为：abcbcaddabbacda

五、实验心得体会

通过本次实验过程，熟悉了对哈夫曼树的使用方法，体会到哈弗曼树构造的编码是一种能够使字符串的编码总长度最短的不等长编码。掌握了哈夫曼树的一般算法；了解到用哈夫曼树对字符串进行编码；掌握通过哈夫曼树对字符编码进行译码得过程。

本文来源：https://www.bwwdw.com/article/0t1a.html