基于Huffman编码的数据压缩算法的研究与实现

这是我们上学期做的一个上机题：

上机题：设电文字符集D及各字符出现的概率F如下：
D={a，b，c，d，e，f，g，h}（字符数n=8）
F={5，29，7，8，14，23，3，11}(%)
编写完成下列功能的程序：
①构造关于F的Huffman树；
②求出并打印D总各字符的Huffman编码。
程序结构： 类型说明；
构造Huffman树的函数：Huffman_tree(H[m+1])；
求Huffman编码的函数：Huffman_code(code[n+1])；
main()
{ 变量说明；
输入字符集D及频率F；
调用Huffman_tree(H)；
调用Huffman_code(code)；
打印编码；Y继续，N退出}

运行后，输入8个字符（中间不能有空格，否则将空格视为字符处理），然后输入概率（整数，空格或回车分隔。如果要支持浮点数，要改程序）然后Enter，出现构造的霍夫曼节点和编码，程序如下：（因为这只是一个上机题目，所以程序不复杂，也没有论文，希望对你有帮助）
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define N 8
#define M 2*N-1
#define MAX 32767
typedef char datatype;
typedef struct
{
int wi;
char data;
int Parent,Lchild,Rchild;
}huffm;
typedef struct
{
char bits[N+1];
int start;
char ch;
}ctype;

void Huffman_tree(huffm H[M+1])
{
int i,j,p1,p2;
int w,s1,s2;
for(i=1;i<=M;i++)
{
H[i].wi=MAX;
H[i].Parent=0;
H[i].Lchild=H[i].Rchild=0;
}
printf("please enter the weight:\n");
for(i=1;i<=N;i++)
{
scanf("%d",&H[i].wi);
}

for(i=N+1;i<=M;i++)
{
p1=p2=0;
s1=s2=MAX;
for(j=1;j<=M;j++)
if(H[j].Parent==0)
if(H[j].wi {
s2=s1;
s1=H[j].wi;
p2=p1; p1=j;
}
else if(H[j].wi H[p1].Parent=H[p2].Parent=i;
H[i].Lchild=p1;
H[i].Rchild=p2;
H[i].wi=H[p1].wi+H[p2].wi;
}
printf("Number\tParent\tLchild\tRchild\n");
for(i=1;i<=M;i++)
printf("%d\t%d\t%d\t%d\n",i,H[i].Parent,H[i].Lchild,H[i].Rchild);

}
void Huffman_code(ctype code[N+1])
{
int i,j,p,s;
char c[N];
huffm H[M+1];
ctype md;
printf("please enter char:\n");
/* for(i=1;i<=N;i++)
{
scanf("%c",&c);
H[i].data=code[i].ch=c;
}
*/
scanf("%s",c);
for(i=1;i<=N;i++)H[i].data=code[i].ch=c[i-1];
Huffman_tree(H);

for(i=1;i<=N;i++)
{
md.ch=code[i].ch;
md.start=N+1;
s=i;
p=H[i].Parent;
while(p!=0)
{
md.start--;
if(H[p].Lchild==s)
md.bits[md.start]='1';
else
md.bits[md.start]='0';
s=p;
p=H[p].Parent;
}
code[i]=md;
}
printf("print the code:\n");
for(i=1;i<=N;i++)
printf("%c\t",code[i].ch);
printf("\n");
for(i=1;i<=N;i++)
{
for(j=code[i].start;j<=N;j++)
printf("%c",code[i].bits[j]);
printf("\t");
}
printf("\n");
}
int Continue()
{ char c;
getchar();
printf("continue? y/n\n");
c=getchar();
if(c=='y') return 1;
else return 0;
}
main()
{
do{
/* huffm H[M+1]; */
ctype code[N+1];
Huffman_code(code);

}while(Continue());

}