哈夫曼编译码器制作

① 哈夫曼编码译码器 java

建议： 用类似的方法，可以将某一学科的总分统计出来，并填入第48行相应的单元格中。

② 哈夫曼编码/译码器

生成哈夫曼树的代码如下：

#define INT_MAX 10000
#define ENCODING_LENGTH 1000
#include "stdio.h"
#include "string.h"
#include "malloc.h"
typedef enum{none,left_child,right_child} Which;//标记是左孩子还是右孩子
typedef char Elemtype;
typedef struct TNode{
Elemtype letter;
int weight;
int parent;
Which sigh;
char *code;
}HTNode,*HuffmanTree;
int n;
char coding[50];//储存代码
char str[ENCODING_LENGTH];//保存要翻译的句子
void InitTreeNode(HuffmanTree &HT){//初始前N个结点,后M-N个结点置空
int i;int w;char c;
int m=2*n-1;
HuffmanTree p;
HT=(HuffmanTree)malloc((m)*sizeof(HTNode));
printf("input %d database letter and weight",n);
p=HT;
getchar();
for (i=1;i<=n;i++){
scanf("%c%d",&c,&w);
p->code='\0';
p->letter=c;
p->parent=0;
p->sigh=none;
p->weight=w;
p++;
getchar();
}
for (;i<=m;i++,p++){
p->code='\0';
p->letter=' ';
p->parent=0;
p->sigh=none;
p->weight=0;
}
}//INITTREENODE
void Select(HuffmanTree HT,int end,int *s1,int *s2){//在0~END之间,找出最小和次小的两个结点序号,返回S1,S2
int i;
int min1=INT_MAX;
int min2;
for (i=0;i<=end;i++){//找最小的结点序号
if (HT[i].parent==0&&HT[i].weight<min1){
*s1=i;
min1=HT[i].weight;
}
}
min2=INT_MAX;
for(i=0;i<=end;i++){//找次小结点的序号
if (HT[i].parent==0&&(*s1!=i)&&min2>HT[i].weight){
*s2=i;
min2=HT[i].weight;
}
}
}
void HuffmanTreeCreat(HuffmanTree &HT){//建立HUFFMAN树
int i;int m=2*n-1;
int s1,s2;
for(i=n;i<m;i++){
Select(HT,i-1,&s1,&s2);
HT[s1].parent=i;
HT[s2].parent=i;
HT[s1].sigh=left_child;
HT[s2].sigh=right_child;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
}

void HuffmanTreeCode(HuffmanTree HT){//HUFFMAN译码
int i;
char *temp;
temp=(char *)malloc(n*sizeof(char));
temp[n-1]='\0';
int p;int s;
for (i=0;i<n;i++){
p=i;
s=n-1;
while (HT[p].parent!=0){//从结点回溯,左孩子为0,右孩子为1
if (HT[p].sigh==left_child)
temp[--s]='0';
else if (HT[p].sigh==right_child)
temp[--s]='1';
p=HT[p].parent;
}
HT[i].code=(char *)malloc((n-s)*sizeof(char));//分配结点码长度的内存空间
strcpy(HT[i].code,temp+s);
printf("%s\n",HT[i].code);
}
}
void GetCodingSen(char *sencence){//输入要编码的句子
int l;
gets(sencence);
l=strlen(sencence);
sencence[l]='\0';
}
void HuffmanTreeEncoding(char sen[],HuffmanTree HT){//将句子进行编码
int i=0;int j;
while(sen[i]!='\0'){
for(j=0;j<n;j++){
if (HT[j].letter==sen[i]) //字母吻合则用代码取代
{strcat(coding,HT[j].code);
break;
}
}
i++;
if (sen[i]==32) i++;
}
printf("\n%s",coding);
}
void HuffmanTreeDecoding(HuffmanTree HT,char code[]){//HUFFMAN译码过程,将代码翻译为句子
char sen[100];
char temp[50];
char voidstr[]=" ";
int i;int j;
int t=0;int s=0;
for(i=0;i<strlen(code);i++){
temp[t++]=code[i];
for(j=0;j<n;j++){
if (strcmp(HT[j].code,temp)==0){//代码段吻合
sen[s]=HT[j].letter;s++;
strcpy(temp,voidstr);//将TEMP置空
t=0;
break;
}
}
}
printf("\n%s",sen);
}

void main(){
HTNode hnode;
HuffmanTree huff;
huff=&hnode;
printf("input the letter for coding number\n");
scanf("%d",&n);
InitTreeNode(huff);
HuffmanTreeCreat(huff);
HuffmanTreeCode(huff);
GetCodingSen(str);
HuffmanTreeEncoding(str,huff);
HuffmanTreeDecoding(huff,coding);
}

③ 哈夫曼编、译码器

这个是我课程设计弄的，也是哈弗曼编码译码器
#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(); //解码

//主函数
int 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)

}

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

}

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)
}

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;
}

④ 哈夫曼编码/译码器的实现用C++面向对象，用CLASS封装(不要C语言，用顺序表存储)

参考这个：
http://..com/link?url=qfz0NyWy_cNy2__AMhFOxD9_mslghqVqd-uVzp53fpjdD2yCgpQRl9a

大约这些功能：
void prin(){ //终端输出选择菜单
cout<<"----------------------------------------------------\n\n"
<<" ∣ I---创建哈夫曼树 ∣\n"
<<" ∣ ∣\n"
<<" ∣ E---文件编码 ∣\n"
<<" ∣ ∣\n"
<<" ∣ D---文件译码 ∣\n"
<<" ∣ ∣\n"
<<" ∣ P---打印代码文件 ∣\n"
<<" ∣ ∣\n"
<<" ∣ T---印哈夫曼树 ∣\n"
<<" ∣ ∣\n"
<<" ∣ O---哈夫曼树的存储结构 ∣\n"
<<" ∣ ∣\n"
<<" ∣ Q---退出 ∣\n"
<<"\n-----------------------------------------------------\n\n";
printf("选择菜单功能选项：");

⑤ 哈夫曼编码/译码器的设计与实现

我们老师最近也留了一个这样的作业,这是我做的,你看看吧