求一个<哈夫曼编码>数据结构课程设计（C语言版）

Question

设计一个利用哈夫曼算法的编码系统，重复地显示并处理以下项目，直到选择退出为止。
【基本要求】1) 将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目录中) 2) 初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；3) 编码：利用建好的哈夫曼树生成哈夫曼编码；4) 输出（1）各个字符的编码；（2）

Answer 1

#include<stdio.h>
#include<string.h>
#include<malloc.h>
#define M 50
#define MAX 1000;
typedef struct
{
int weight;//结点权值
int parent,lchild,rchild;
}HTNODE,*HUFFMANTREE;
typedef char** HUFFMANCODE;//动态分配数组存储哈夫曼编码表
HUFFMANTREE huffmantree(int n,int weight[])//构建哈夫曼树
{
int m1,m2,k;
int i,j,x1,x2;
HUFFMANTREE ht;
ht=(HUFFMANTREE)malloc((2*n)*sizeof(HTNODE));
for(i=1;i<(2*n);i++)//初始化哈夫曼树中各结点的数据，没初始值的赋值为0
{
ht[i].parent=ht[i].lchild=ht[i].rchild=0;
if(i<=n)
ht[i].weight=weight[i];
else
ht[i].weight=0;
}
for(i=1;i<n;i++)//每一重循环从森林中选择最小的两棵树组建成一颗新树
{
m1=m2=MAX;
x1=x2=0;
for(j=1;j<(n+i);j++)
{
if((ht[j].weight<m1)&&(ht[j].parent==0))
{
m2=m1;
x2=x1;
m1=ht[j].weight;
x1=j;
}
else if((ht[j].weight<m2)&&(ht[j].parent==0))
{
m2=ht[j].weight;
x2=j;
}
}
k=n+i;
ht[x1].parent=ht[x2].parent=k;
ht[k].weight=m1+m2;
ht[k].lchild=x1;
ht[k].rchild=x2;
}
return ht;
}
void huffmancoding(const int n,HUFFMANCODE hc,HUFFMANTREE ht,char str[])
{
int i,start,child,father;
char *cd;
hc=(HUFFMANCODE)malloc((n+1)*sizeof(char*));//分配n个字符编码的头指针
cd=(char*)malloc(n*sizeof(char));//分配求编码的工作空间
cd[n-1]='\0';//编码结束符
for(i=1;i<=n;++i)//逐个字符求哈夫曼编码
{
start=n-1;
for(child=i,father=ht[i].parent;father!=0;child=father,father=ht[father].parent)/*从叶子结点到根结点求逆向编码*/
if(ht[father].lchild==child)
cd[--start]='0';
else
cd[--start]='1';
hc[i]=(char*)malloc((n-start)*sizeof(char));//为i个字符编码分配空间
strcpy(hc[i],&cd[start]);//从cd复制哈夫曼编码串到hc
}
free(cd);//释放工作空间
for(i=1;i<=n;++i)
{
printf("%c的编码:",str[i]);
printf("%s\n",hc[i]);
}
}
void main()
{
int i,j,k;
char str[50];
int weight[50];
printf("请输入字符(一次性连续输入所求的字符):");/*如:abcjhjg不要输成ab cj hig,即字符间不加空格*/
gets(str);
for(j=0;j<50;j++)
{
if(str[j]=='\0')
break;
}
const int n=j;
for(j=n;j>0;j--)
str[j]=str[j-1];
str[n+1]='\0';
for(k=0;k<n;k++)
{
printf("请输入%c的权值:",str[k+1]);
scanf("%d",&weight[k]);
}
for(k=n;k>0;k--)
weight[k]=weight[k-1];
weight[0]=0;
HUFFMANCODE hc=NULL;
HUFFMANTREE ht;
ht=huffmantree(n,weight);
huffmancoding(n,hc,ht,str);
}

Answer 2

我帮你测试了，这个可以满足你的要求！#include<stdio.h>
#include<stdlib.h>
#define max 50
struct a
{
int weight;
int parent,lchild,rchild;
};
struct b
{
char cd[max];
int start;
};
void main()
{
struct a ht[2*max];
struct b hcd[max],d;
int i,k,n,c,s1,s2,m1,m2,f;
printf("输入n:");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
printf("输入权值:");
scanf("%d",&ht[i].weight);
ht[i].parent=0;
}
for(;i<=2*n-1;i++)
ht[i].parent=ht[i].lchild=ht[i].rchild=0;
for(i=n+1;i<=2*n-1;i++)
{
m1=m2=30000;
s1=s2=0;
for(k=1;k<=i-1;k++)
{
if(ht[k].parent==0 && ht[k].weight<m1)
{
m2=m1;
s2=s1;
m1=ht[k].weight;
s1=k;
}
else if(ht[k].parent==0 && ht[k].weight<m2)
{
m2=ht[k].weight;
s2=k;
}
}
ht[s1].parent=ht[s2].parent=i;
ht[i].lchild=s1;
ht[i].rchild=s2;
ht[i].weight=ht[s1].weight+ht[s2].weight;
}
for(i=1;i<=n;i++)
{
d.start=n-1;
c=i;
f=ht[i].parent;
while(f)
{
if(ht[f].lchild==c)d.cd[--d.start]='0';
else d.cd[--d.start]='1';
c=f;
f=ht[f].parent;
}
hcd[i]=d;
}
printf("输出哈夫编码:");
for(i=1;i<=n;i++)
{
printf("%d ",ht[i].weight);
for(k=hcd[i].start;k<n-1;k++)
printf("%c",hcd[i].cd[k]);
printf(" ");
}
printf("\n");
}本回答被网友采纳