哈夫曼编/译码器

Question

基本功能
初始化：输入一串字符（正文），计算不同字符（包括空格）的数目以及每种字符出现的频率（以该种字符出现的次数作为其出现频率），根据权值建立哈夫曼树，输出每一种字符的哈夫曼编码。
编码：利用求出的哈夫曼编码，对该正文（字符串）进行编码，并输出。
译码：对于得到的一串编码，利用已求得的哈夫曼编码进行译码，将译出的正文输出。
要求是C语言 希望各位大侠帮帮小妹 不胜感激

Answer 1

c++版的 java版的也有 就是没有C语言版的

#include<iostream>
#include<stdlib.h>
#include<string.h>
using namespace std;

typedef struct{
int weight;
int parent,lchild,rchild;
int asc;
}HTNode,*HuffmanTree; //定义赫夫曼存储结构

struct node{
int ASCII;
int n;
};
struct node a[127];
struct node w[127];
//一些全局变量
int count;
HTNode H_T[250];
char ** HC;
char filename[20];

//函数声明
void menu1(); //菜单1
HuffmanTree HeapSort(HuffmanTree HT,int length); //堆排序
void MinHeapify(HuffmanTree HT, int k,int len); //调整成一个小顶堆
void buildMinHeap(HuffmanTree HT,int len); //建一个小顶堆
void swap(HTNode &t1,HTNode &t2); //交换两结构体
void savefile(); //把输入的英文文章保存到文件
void loadfile(); //从文件中读取文章
HuffmanTree CreateHuffman(HuffmanTree &HT,struct node *w,int n); //建立赫夫曼数并存入文件
void BianMa(HuffmanTree HT,int n ); //字符编码
void BianMa_all(HuffmanTree HT,char**HC,char *filename); //整篇文章编码
int loadfile2(); //从文件读入文章
void JieMa(); //解码

//主函数
void main()
{
char s;
while(s!='0')
{
system("cls");
cout<<"\n\n\n";
cout<<"\t\t\t\t赫夫曼编码/译码器"<<endl<<endl<<endl<<endl<<endl;
cout<<"\t\t\t\t 1.编码"<<endl<<endl<<endl<<endl;
cout<<"\t\t\t\t 2.译码"<<endl<<endl<<endl<<endl;
cout<<"\t\t\t\t 0.退出"<<endl<<endl<<endl<<endl;
cout<<"\t请输入0—2进行选择，按回车确认";
cin>>s;
switch(s)
{
case '1': menu1(); break;
case '2':
{
system("cls");
JieMa();
system("pause");
break;
}

}

}
}

//菜单1
void menu1(){
char s;
int i;
int a;
char c;
char fpname[20]="article.txt";
HuffmanTree HT;
while(s!='0'){

system("cls");
cout<<"\n\t\t\t\t编码界面";
cout<<"\n\n\n\t\t\t\t1.输入英文文章"<<endl;
cout<<"\n\n\t\t\t\t2.从文件中读入文章"<<endl;
cout<<"\n\n\t\t\t\t0.返回上一层"<<endl;
cout<<"\n\t请输入0—2进行选择，按回车确认";
cin>>s;
switch(s){
case'1':
system("cls");
savefile();
loadfile();
CreateHuffman(HT,w,count);
BianMa(HT,count);
BianMa_all(HT,HC,fpname);
system("cls");
cout<<"出现字符种类共计：";
cout<<count<<endl;
for(i=1;i<=count;i++)
{ a=HT[i].asc;
c=(char)a;

cout<<"________________________________________________________________________________"<<endl;
cout<<"\t\t\t字符：";
cout<<c<<endl;
cout<<"\t\t\tASCII码：";
cout<<a<<endl;
cout<<"\t\t\t频数：";
cout<<HT[i].weight<<endl;
cout<<"\t\t\t赫夫曼编码：";
cout<<HC[i]<<endl;

}
cout<<"________________________________________________________________________________";
cout<<"\n\t\t整篇文章的编码已存入文件“赫夫曼编码.txt”"<<endl;

system("pause");
break;

case'2':
system("cls");
if(loadfile2())
{ system("pause");
return;}
CreateHuffman(HT,w,count);
BianMa(HT,count);
BianMa_all(HT,HC,filename);
system("cls");
cout<<"出现字符种类共计：";
cout<<count<<endl;
for(i=1;i<=count;i++)
{ a=HT[i].asc;
c=(char)a;

cout<<"________________________________________________________________________________"<<endl;
cout<<"\t\t\t字符：";
cout<<c<<endl;
cout<<"\t\t\tASCII码：";
cout<<a<<endl;
cout<<"\t\t\t频数：";
cout<<HT[i].weight<<endl;
cout<<"\t\t\t赫夫曼编码：";
cout<<HC[i]<<endl;

}
cout<<"________________________________________________________________________________";
cout<<"\n\t\t整篇文章的编码已存入文件“赫夫曼编码.txt”"<<endl;
system("pause");
break;
}

}

}

//交换结构体
void swap(HTNode &t1,HTNode &t2)
{
HTNode m;

m = t1;
t1 = t2;
t2 = m;
}

//从键盘输入文章并保存
void savefile(){

FILE *fp;
char article;
if((fp=fopen("article.txt","w"))==NULL){

printf("打开文件不成功！");
exit(0);
}
cout<<"请输入英文文章,以#结束:";
getchar();
article=getchar();
while(article!='#'){

fputc(article,fp);

article=getchar();
}
fclose(fp);
}

//从文件读取文章，并统计字符出现频数
void loadfile(){

FILE *fp;
char ch;
int i,k,j=0;
count=0;
for(i=0;i<=127;i++) //把所有字符的ascii码存在数组
{ a[i].ASCII=i;
a[i].n=0;

}
if((fp=fopen("article.txt","r"))==NULL){

printf("打开文件不成功！");
exit(0);
}
ch=fgetc(fp);
k=(int)ch;
a[k].n++;
while(!feof(fp)){
ch=fgetc(fp);
k=(int)ch;
a[k].n++;
}
fclose(fp);

for(i=0;i<=127;i++) //统计字符种类总数
{
ch=(char)i;
if(a[i].n){
count++;
}
}
for(i=0;i<=127;i++)
{
for(;j<count;)
{
if(a[i].n)
{
w[j].n=a[i].n;
w[j].ASCII=a[i].ASCII;
j++;
break;
}
else break;
}
}

}

//调整为小顶堆
void MinHeapify(HuffmanTree HT, int k,int len)
{
int left=k*2;
int right=k*2+1;
int large;
int l=len;

large = k;
if (left<=l&&HT[left].weight<HT[large].weight)
large = left;

if (right<=l&& HT[right].weight<HT[large].weight)
large=right;

if (large!=k)
{
swap(HT[k],HT[large]);
MinHeapify(HT,large,l);
}
}

//建立小顶堆
void buildMinHeap(HuffmanTree HT,int len)
{
int i;
for (i=len/2;i>=1;i--)
{
MinHeapify(HT,i,len);
}
}

//堆排序
HuffmanTree HeapSort(HuffmanTree HT,int length)
{
int i;
int l=length;
buildMinHeap(HT,length);
for (i=length;i>= 2;i--)
{
swap(HT[1],HT[i]);
length--;
MinHeapify(HT,1,length);
}

return HT;
}

//建立赫夫曼数
HuffmanTree CreateHuffman(HuffmanTree &HT,struct node *w,int n)
{
int i,m,s1,s2,k1,k2,j,x,a;
FILE *fp,*fp2;

if(n<=1) return HT;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0不用

for(i=1,j=0;i<=n;i++,j++)
{ HT[i].asc=w[j].ASCII;
HT[i].weight=w[j].n;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(;i<=m;i++)
{ a=250+i;
HT[i].asc=a;//父亲节点的asc可以是大于127的任意值
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(i=1;i<=n;i++){

H_T[i].asc=HT[i].asc;
H_T[i].parent=HT[i].parent;
H_T[i].lchild=HT[i].lchild;
H_T[i].rchild=HT[i].rchild;
H_T[i].weight=HT[i].weight;
}

for(i=n+1,x=n;i<=m;i++,x--)
{

HeapSort(H_T,x);
k1=H_T[x].asc;
k2=H_T[x-1].asc;
for(j=1;j<=127;j++)
{
if(HT[j].asc==k1)
{ s1=j;break;}

}

for(j=1;j<=127;j++)
{
if(HT[j].asc==k2)
{ s2=j;break;}

}

HT[s2].parent=i;
HT[s1].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;

H_T[x-1].asc=HT[i].asc;
H_T[x-1].lchild=HT[i].lchild;
H_T[x-1].parent=HT[i].parent;
H_T[x-1].rchild=HT[i].rchild;
H_T[x-1].weight=HT[i].weight;

}
if((fp2=fopen("count.txt","w"))==NULL) //保存赫夫曼树
{
cout<<"文件打开不成功！"<<endl;
exit(0);
}
fputc(count,fp2);
if((fp=fopen("HuffmanTree.dat","wb"))==NULL)
{ cout<<"文件打开不成功！"<<endl;
exit(0);

}

for(i=1;i<=(2*count-1);i++){
fwrite(&HT[i],sizeof(HTNode),1,fp);
}
fclose(fp);
fclose(fp2);
return HT;

}

//逆向编码
void BianMa(HuffmanTree HT,int n){
char *cd,temp;

int c,f,i,j,len,p,q;

cd=(char *)malloc(n*sizeof(char));
HC=(char * *)malloc(n*sizeof(char*));
for(i=1;i<=n;i++){
for(c=i,f=HT[i].parent,j=0;f!=0;c=f,f=HT[f].parent,j++)
{ if(HT[f].lchild==c) cd[j]='0';
else cd[j]='1';
if(HT[f].parent==0)
cd[j+1]='\0';

}

len=strlen(cd);
for(p=0,q=len-1;p<=q;p++,q--)
{
temp=cd[q];
cd[q]=cd[p];
cd[p]=temp;
}
cd[len]='\0';
HC[i]=(char*)malloc((len+10)*sizeof(char));
strcpy(HC[i],cd);

}

}

//整篇文章编码，并存入文件
void BianMa_all(HuffmanTree HT,char**HC,char *filename){
char ch;
int k,i;
FILE *fp,*fp2;

char code[100];
if((fp=fopen(filename,"r"))==NULL){

printf("打开文件不成功！");
exit(0);
}
if((fp2=fopen("赫夫曼编码.txt","w"))==NULL){

printf("打开文件不成功！");
exit(0);
}
ch=fgetc(fp);
k=(int)ch;
while(!feof(fp))
{

for(i=1;i<=count;i++)
{
if(k==HT[i].asc)
strcpy(code,HC[i]);

}
fputs(code,fp2);
ch=fgetc(fp);
k=(int)ch;

}
fclose(fp);
fclose(fp2);

}

void JieMa(){
int i,k,a,t,n=0;
FILE *fp1,*fp2,*fp3;
char ch,c;
HuffmanTree ht;
if((fp3=fopen("count.txt","r"))==NULL) //从文件读出字符总数
{
printf("打开文件不成功！");
exit(0);
}
n=fgetc(fp3);
ht=(HuffmanTree)malloc(2*n*sizeof(HTNode));
if((fp1=fopen("赫夫曼编码.txt","r"))==NULL)
{

printf("打开文件不成功！");
exit(0);
}

if((fp2=fopen("HuffmanTree.dat","rb"))==NULL)
{ cout<<"文件打开不成功！"<<endl;
exit(0);

}
for(i=1;i<=2*n-1;i++)

fread(&ht[i],sizeof(HTNode),1,fp2);

for(i=1;i<=2*n-1;i++)
{
if(ht[i].parent==0){t=k=i;break;}
}

ch=fgetc(fp1);
while(!feof(fp1)){
if(ch=='0')
{
k=ht[k].lchild;
if(ht[k].lchild==0)
{a=ht[k].asc;
c=(char)a;
printf("%c",c);;

k=t;
}
}
if(ch=='1')
{
k=ht[k].rchild;
if(ht[k].lchild==0)
{ a=ht[k].asc;
c=(char)a;
printf("%c",c);

k=t;
}

}

ch=fgetc(fp1);
}
fclose(fp1);
fclose(fp2);

}

//读取文件中的文章，可自己选择文件
int loadfile2(){

FILE *fp;
char ch;
int i,k,j=0;
count=0;
for(i=0;i<=127;i++)
{ a[i].ASCII=i;
a[i].n=0;

}
cout<<"\n\n\n\t\t\t请输入你要打开的文件名：";
cin>>filename;
if((fp=fopen(filename,"r"))==NULL){

printf("打开文件不成功！");
return 1;
}
ch=fgetc(fp);
k=(int)ch;
a[k].n++;
while(!feof(fp)){
ch=fgetc(fp);
k=(int)ch;
a[k].n++;
}
fclose(fp);

for(i=0;i<=127;i++){
ch=(char)i;
if(a[i].n){
count++;
}
}
for(i=0;i<=127;i++)
{
for(;j<count;)
{
if(a[i].n)
{
w[j].n=a[i].n;
w[j].ASCII=a[i].ASCII;
j++;
break;
}
else break;
}
}
return 0;
}

Answer 2

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 27 /*字符代码集包括26个字母+1个空格字符*/
typedef struct{
char data;
int weight;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;/*定义哈夫曼树抽象数据类型,用双亲孩子链表*/
typedef char ** HuffmanCode;/*定义哈夫曼编码序列*/
typedef struct {
int s1;
int s2;
}MinCode;
HuffmanTree HT;/*定义全局变量HT,HC*/
HuffmanCode HC;
/*下面是Select(HT,i-1,s1,s2)"函数"，实现在HT[i..i-1]选择parent=0且权值最小的两个结点，序号为s1,s2*/
MinCode Select(HuffmanTree HT,int n){
int min,secmin;
int temp;
int i,s1,s2,tempi;
MinCode code;
s1=1;s2=1;
for(i=1;i<=n;i++)
if(HT[i].parent==0) {
min=HT[i].weight;
s1=i;
break;
}
tempi=i++;
for(;i<=n;i++)
if(HT[i].weight<min && HT[i].parent==0){
min=HT[i].weight;
s1=i;
}
for(i=tempi;i<=n;i++)
if(HT[i].parent==0 && i!=s1){
secmin=HT[i].weight;
s2=i;
break;
}
for(i=1;i<=n;i++)
if(HT[i].weight<secmin&&i!=s1&&HT[i].parent==0){
secmin=HT[i].weight;
s2=i;
}
if(s1>s2){
temp=s1;
s1=s2;
s2=temp;
}
code.s1=s1;
code.s2=s2;
return code;
}
/*******下面HuffmanCoding函数建立哈夫曼树***************/
void HuffmanCoding(char c[],int num[],int n){
int m=2*n-1;/*n个叶子结点的哈夫曼树共有(2*n-1)个结点*/
int i,k,f,s1=0,s2=0,start;
MinCode min;
char * cd;/*指向动态数组的指针,用来分配编码的工作空间*/
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(i=1;i<=n;++i)/*先对n个叶子结点赋data值和权值*/
{
HT[i].data=c[i-1];
HT[i].weight=num[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(;i<=m;++i)/*对除叶子结点外的其余结点初始化*/
{
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(i=n+1;i<=m;++i){
min=Select(HT,i-1);
s1=min.s1;
s2=min.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;
}
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';/*编码结束符*/
for(i=1;i<=n;++i){
start=n-1;/*逐个字符求哈夫曼编码*/
for(k=i,f=HT[i].parent;f!=0;k=f,f=HT[f].parent)/*从叶子到根逆向求编码*/
if(HT[f].lchild==k)
cd[--start]='0';
else
cd[--start]='1';
HC[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(HC[i],&cd[start]);
}
free(cd);
printf("data weight parent lchild rchild HuffCode\n");
for(i=1;i<=n;++i){
printf("%c\t%d\t%d\t%d\t%d",HT[i].data,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
printf("%s\n",HC[i]);
}
for(i=n+1;i<=m;++i){
printf(" \t%d\t%d\t%d\t%d",HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
printf("\n");
}
}//HumanCoding
/*****下面translate_to_huffmancode实现编码/译码,若读入字符串则输出译码,反之输出字符串*****/
void translate_to_huffmancode(char *str,int n){
int i,j;
char ctemp,result[100]="\0";/*存放编/译码结果*/
for(i=0;i<n;i++){
ctemp=str[i];
for(j=1;j<=n;j++)
if(str[i]==HT[j].data)
strcat(result,HC[j]);
}
printf("所求哈夫曼编码为:\n");
puts(result);
}//translate_to_huffmancode
void main(){
char ch[N+1];/*读入字符集*/
char string[60];/*存放待转换的序列*/
int i,len,w[N+1];/*w[N+1]读入相应权值集*/
printf("输入字符：\n");
for(i=0;i<N;i++)
scanf("%c",&ch[i]);
printf("输入对应权值：\n");
for(i=0;i<N;i++){
printf("%c=",ch[i]);
scanf("%d",&w[i]);
}
HuffmanCoding(ch,w,N);
while(1){
printf("输入输入字符或哈夫曼编码序列(按'.'退出):\n");
fflush(stdin);
gets(string);
if(string[0]=='.')
break;
len=strlen(string);
translate_to_huffmancode(string,len);
}
}//main
不知对不对？

/***************************************************************/本回答被提问者采纳