Question

哈夫曼编/译码器的问题：请求高手帮帮忙，课程设计用的，自己写的错误太多了，万分感谢，c描述。拜托了

1、问题描述：
利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。试写一个哈夫曼编/译码系统。
2、基本要求：
一个完整的系统应具有以下功能：
（1）初始化。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件中。
（2）编码。利用已建好的哈夫曼树对文件中的正文进行编码，然后将结果存入文件中。
（3）译码。利用已建好的哈夫曼树将文件中的代码进行译码，结果存入文件中。
（4）完成数据测试，要求编码字符不低于15个，编码文件的长度不低于50个字符。
(5) 计算平均编码长度。

Answer 1

以下程序在c-free下测试成功。
算法参考 数据结构（C语言版）——清华大学出版社
请根据题目具体要求进行修改！有问题找我……

#include"stdio.h"
#include"stdlib.h"
#include"string.h"
typedef char ElemType;
typedef char** HuffmanCode;
typedef int Status;
typedef struct
{
ElemType elem;
unsigned int m_weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef struct weight
{
char elem;
unsigned int m_weight;
}Weight;
void HuffmanCoding(HuffmanTree *,HuffmanCode *,Weight *,int);
void Select(HuffmanTree,int,int *,int *);
void OutputHuffmanCode(HuffmanTree,HuffmanCode,int);

void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,Weight *w,int n)
{
//w存放n个字符的权值（均>0），构造Huffman树HT，并求出n个字符的Huffman编码HC
int i,m,s1,s2,start,c,f;
char *cd;
HuffmanTree p;
if(n<=1) return;
m=2*n-1;
(*HT)=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0号单元未用
for(p=HT,i=1;i<=n;++i,++p,++w)
{
(*HT)[i].elem=w[i-1].elem;
(*HT)[i].m_weight=w[i-1].m_weight;
(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0;
}
for(;i<=m;++i,++p)
{
(*HT)[i].elem='0';
(*HT)[i].m_weight=(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0;
}
for(i=n+1;i<=m;++i)
{
//在HT[1...i-1]选择parent为0且weight最小的两个结点，其序号分别为s1和s2
Select(*HT,i-1,&s1,&s2);
(*HT)[s1].parent=i;(*HT)[s2].parent=i;
(*HT)[i].lchild=s1;(*HT)[i].rchild=s2;
(*HT)[i].m_weight=(*HT)[s1].m_weight+(*HT)[s2].m_weight;
}
//从叶子到根逆向求每个字符的Huffman编码
(*HC)=(HuffmanCode)malloc(n*sizeof(char*));
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=1;i<=n;++i) //逐个字符求编码
{
start=n-1;
for(c=i,f=(*HT)[i].parent;f!=0;c=f,f=(*HT)[f].parent)//从叶子到跟逆向求编码
if((*HT)[f].lchild==c) cd[--start]='0';
else cd[--start]='1';
(*HC)[i]=(char *)malloc((n-start)*sizeof(char));
strcpy((*HC)[i],&cd[start]); //从cd复制编码到HC
}
}
void Select(HuffmanTree HT,int n,int *s1,int *s2)
{
int i;
(*s1)=(*s2)=0;
for(i=1;i<=n;i++)
{
if(HT[i].m_weight<HT[(*s2)].m_weight&&HT[i].parent==0&&(*s2)!=0)
{
if(HT[i].m_weight<HT[(*s1)].m_weight)
{
(*s2)=(*s1);
(*s1)=i;
}
else
(*s2)=i;
}
if(((*s1)==0||(*s2)==0)&&HT[i].parent==0)
{
if((*s1)==0) (*s1)=i;
else
if((*s2)==0)
{
if(HT[i].m_weight<HT[(*s1)].m_weight)
{
(*s2)=(*s1);
(*s1)=i;
}
else (*s2)=i;
}
}
}
if((*s1)>(*s2))
{
i=(*s1);
(*s1)=(*s2);
(*s2)=i;
}
}
void OutputHuffmanCode(HuffmanTree HT,HuffmanCode HC,int n)
{
int i;
printf("\nnumber---element---weight---huffman code\n");
for(i=1;i<=n;i++)
printf(" %d %c %d %s\n",i,HT[i].elem,HT[i].m_weight,HC[i]);
}
Status main(void)
{
HuffmanTree HT;
HuffmanCode HC;
Weight *w;
char c;
int i,n;
int wei;
printf("input the tatol number of the Huffman Tree:" );
scanf("%d",&n);
w=(Weight *)malloc(n*sizeof(Weight));
for(i=0;i<n;i++)
{
printf("input the element & its weight:");
scanf("%1s%d",&c,&wei);
w[i].elem=c;
w[i].m_weight=wei;
}
HuffmanCoding(&HT,&HC,w,n);
OutputHuffmanCode(HT,HC,n);
return 1;
}

追问

不好意思哈，您能把题目做一下吗？感谢。。。。

Answer 2

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef char* HuffmanCode;/*动态分配数组，存储哈夫曼编码*/

typedef struct
{
unsigned int weight ; /* 用来存放各个结点的权值*/
unsigned int parent, LChild,RChild ; /*指向双亲、孩子结点的指针*/
}HTNode, * HuffmanTree; /*动态分配数组，存储哈夫曼树*/

void select(HuffmanTree *ht,int n, int *s1, int *s2)
{
int i;
int min;
for(i=1; i<=n; i++)
{
if((*ht)[i].parent == 0)
{
min = i;
i = n+1;
}
}
for(i=1; i<=n; i++)
{
if((*ht)[i].parent == 0)
{
if((*ht)[i].weight < (*ht)[min].weight)
min = i;
}
}
*s1 = min;
for(i=1; i<=n; i++)
{
if((*ht)[i].parent == 0 && i!=(*s1))
{
min = i;
i = n+1;
}
}
for(i=1; i<=n; i++)
{
if((*ht)[i].parent == 0 && i!=(*s1))
{
if((*ht)[i].weight < (*ht)[min].weight)
min = i;
}
}
*s2 = min;
}

void CrtHuffmanTree(HuffmanTree *ht , int *w, int n)
{ /* w存放已知的n个权值，构造哈夫曼树ht */
int m,i;
int s1,s2;
m=2*n-1;
*ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /*0号单元未使用*/
for(i=1;i<=n;i++)
{/*1-n号放叶子结点，初始化*/
(*ht)[i].weight = w[i];
(*ht)[i].LChild = 0;
(*ht)[i].parent = 0;
(*ht)[i].RChild = 0;
}
for(i=n+1;i<=m;i++)
{
(*ht)[i].weight = 0;
(*ht)[i].LChild = 0;
(*ht)[i].parent = 0;
(*ht)[i].RChild = 0;
} /*非叶子结点初始化*/
/* ------------初始化完毕！对应算法步骤1---------*/

for(i=n+1;i<=m;i++) /*创建非叶子结点,建哈夫曼树*/
{ /*在(*ht)[1]~(*ht)[i-1]的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给s1、s2返回*/
select(ht,i-1,&s1,&s2);
(*ht)[s1].parent=i;
(*ht)[s2].parent=i;
(*ht)[i].LChild=s1;
(*ht)[i].RChild=s2;
(*ht)[i].weight=(*ht)[s1].weight+(*ht)[s2].weight;
}
}/*哈夫曼树建立完毕*/
void outputHuffman(HuffmanTree HT, int m)
{
if(m!=0)
{
printf("%d ", HT[m].weight);
outputHuffman(HT,HT[m].LChild);
outputHuffman(HT,HT[m].RChild);
}
}

void CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n)
/*从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码*/
{
char *cd;
int i;
unsigned int c;
int start;
int p;
hc=(HuffmanCode *)malloc((n+1)*sizeof(char *)); /*分配n个编码的头指针*/
cd=(char * )malloc(n * sizeof(char )); /*分配求当前编码的工作空间*/
cd[n-1]='\0'; /*从右向左逐位存放编码，首先存放编码结束符*/
for(i=1;i<=n;i++) /*求n个叶子结点对应的哈夫曼编码*/
{
start=n-1; /*初始化编码起始指针*/
for(c=i,p=(*ht)[i].parent; p!=0; c=p,p=(*ht)[p].parent) /*从叶子到根结点求编码*/
if( (*ht)[p].LChild == c)
cd[--start]='0'; /*左分支标0*/
else
cd[--start]='1'; /*右分支标1*/
hc[i]=(char *)malloc((n-start)*sizeof(char)); /*为第i个编码分配空间*/
strcpy(hc[i],&cd[start]);
}
free(cd);
for(i=1;i<=n;i++)
printf("%d编码为%s\n",(*ht)[i].weight,hc[i]);
}

void main()
{
HuffmanTree HT;
HuffmanCode HC;
int *w;
int i,n; // the number of elements;
int wei; // the weight of a element;
int m;

printf("input the total number of the Huffman Tree:" );
scanf("%d",&n);
w=(int *)malloc((n+1)*sizeof(int));
for(i=1;i<=n;i++)
{
printf("input the %d element's weight:",i);
fflush(stdin);
scanf("%d",&wei);
w[i]=wei;
}

CrtHuffmanTree(&HT,w,n);
m = 2*n-1;
outputHuffman(HT,m);
printf("\n");
CrtHuffmanCode(&HT,&HC,n);

}

追问

在最后有一个错误啊