实验七--哈夫曼编码实验.doc

树和二叉树

实验七 哈夫曼编码
哈夫曼编码
1. 问题描述
设某编码系统共有n个字符，使用频率分别为{w1, w2, …, wn}，设计一个不等长的编码方案，使得该编码系统的空间效率最好。
2. 基本要求
⑴ 设计数据结构；
⑵ 设计编码算法；
⑶ 分析时间复杂度和空间复杂度。
3. 编码
#include<iostream>
#include<string.h>
using namespace std;
const int Size=10,Size1=50;
struct element
{
int weight;
int lchild,rchild,parent;
};
char s[Size];int w[Size],w1[Size];
int getW(char T1[]) //统计字母频率，获得权值
{
char T[Size1];
strcpy(T,T1);
char c;int count,k=0;
for(int i=0;T[i]!='\0';i++)
{
count=0;
if(T[i]>='a'&&T[1]<='z')
{
c=T[i];
s[k]=c;s[k+1]='\0';
}
if(c!='\0')
{
for(int j=0;T[j]!='\0';j++)
{
if(T[j]==c)
{
count++;
T[j]='$';
}
}
}
if(c!='\0')
{
w1[k]=count;
w[k++]=count;
}
c='\0';
}
return k;
}
void Select(element h[],int &i3,int &i4)//获得哈夫曼数组中权值最小的两个下标
{
int c;
i3=-1;i4=-1;
for(int i=0;i3==-1;i++)
if(h[i].parent==-1)
i3=i;
for(i;i4==-1;i++)
if(h[i].parent==-1)
i4=i;
if(h[i3].weight>h[i4].weight)
{
c=i3;
i3=i4;
i4=c;
}
for(i;h[i].weight>0;i++)
{
if(h[i].parent==-1)
if(h[i].weight<h[i3].weight)
i4=i3,i3=i;
else if(h[i].weight<h[i4].weight)
i4=i;
}
}

void HuffmanTree(element *huffTree,int n)//哈夫曼树
{
int i1,i2;
for(int i=0;i<2*n-1;i++)
{
huffTree[i].parent=-1;
huffTree[i].lchild=-1;
huffTree[i].rchild=-1;
}
for(i=0;i<n;i++)
huffTree[i].weight=w[i];
for(int k=n;k<2*n-1;k++)
{
Select(huffTree,i1,i2);
huffTree[i1].parent=k;
huffTree[i2].parent=k;
huffTree[k].weight=huffTree[i1].weight+huffTree[i2].weight;
huffTree[k].lchild=i1;
huffTree[k].rchild=i2;
}
}
struct codetype
{
char bits[Size];
char ch;
};
codetype code[Size];
void bm(element h[],int m)//记录路径编码
{
char b[Size];b[0]='\0';
int s1[Size],cd;
int top=-1,i=0,k;
while(m!=-1||top!=-1)
{
while(m!=-1)
{
if(h[m].lchild==-1 && h[m].rchild==-1)//记录路径编码'0'，'1'的算法，用到parent回溯。
{
cd=0;
for(int j=h[m].parent;j!=-1;j=h[j].parent)
cd++;
b[cd]='\0';
k=m;
for(j=h[k].parent;j!=-1;j=h[j].parent)
{
if(h[j].lchild==k) b[--cd]='0';
else b[--cd]='1';
k=j;
}
for(j=0;s[j]>='a'&&s[j]<='z';j++)
{
if(h[m].weight==w[j])
{
strcpy(code[i].bits,b);
code[i++].ch=s[j];
w[j]=-1;break;
}
}
}
s1[++top]=m;
m=h[m].lchild;
}
if(top!=-1)
{
m=s1[top--];
m=h[m].rchild;
}
}
}
void jm(element huffT[],int n,char t1[])
{
char b1[Size];b1[0]='\0';
int k=2*n-2,g=0;
for(int i=0;t1[i]!='\0';i++)
{
if(t1[i]=='0')
{
k=huffT[k].lchild;
b1[g++]='0';
b1[g]='\0';
}
else
{
k=huffT[k].rchild;
b1[g++]='1';
b1[g]='\0';
}
if(huffT[k].lchild==-1 && huffT[k].rchild==-1)
{
for(int j=0;j<n;j++)
{
if(strcmp(b1,code[j].bits)==0)
{
cout<<code[j].ch;
break;
}
}
k=2*n-2;g=0;
}
}
cout<<endl;
}
void main()
{
char T[Size1],t[Size1];int n;
cout<<"输入字符串：";
gets(T);
n=getW(T);
element huffTree[Size1];
HuffmanTree(huffTree,n);
cout<<"编码："<<endl;
bm(huffTree,2*n-2);
for(int i=0;i<n;i++) cout<<code[i].ch<<":"<<code[i].bits<<endl;
for(i=0;T[i]!='\0';i++)
for(int j=0;j<n;j++)
if(T[i]==code[j].ch)
cout<<code[j].bits;
cout<<endl;
cout<<"输入编码:";
gets(t);
cout<<"解码："<<endl;
jm(huffTree,n,t);
}

4.实验结果

5.实验小结
本次实验主要是通过实验过程掌握哈夫曼编码的逻辑结构，掌握哈夫曼编码和解码的基本算法，bm函数中通过对树的遍历寻找叶子结点，进行编码。