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

树和二叉树

实验七 哈夫曼编码
哈夫曼编码
1. 问题描述
设某编码系统共有n个字符，使用频率分别为{w1, w2, …, wn}，设计一个不等长的编码方案，使得该编码系统的空间效率最好。
2. 基本要求
⑴ 设计数据结构；
⑵ 设计编码算法；
⑶ 分析时间复杂度和空间复杂度。
3. 编码
#include
#include
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')
{
forint 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].weight4].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;ict(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
}
}
k=2*n-2;g=0;
}
}
cout<bits<