哈夫曼編解碼器製作

① 哈夫曼編碼解碼器 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("選擇菜單功能選項：");

⑤ 哈夫曼編碼/解碼器的設計與實現

我們老師最近也留了一個這樣的作業,這是我做的,你看看吧