实验七哈夫曼编码实验
- 格式：doc
- 大小：44.00 KB
- 文档页数：5
实验七哈夫曼编码
哈夫曼编码
1. 问题描述
设某编码系统共有n个字符，使用频率分别为{w1, w2,…, w n}，设计一个不等长的编码方案，使得该编码系统的空间效率最好。
2. 基本要求
⑴设计数据结构；
⑵设计编码算法；
⑶分析时间复杂度和空间复杂度。
3. 编码
#include<iostream>
#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[]) arent==-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)arent=-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)child==-1 && h[m].rchild==-1)arent;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函数中通过对树的遍历寻找叶子结点，进行编码。
