JAVA哈夫曼編解碼系統
❶ 哈夫曼編碼與解碼 java
class
HaffmanNode
//哈夫曼樹的結點類
{
int
weight;
//
權值
int
parent,left,right;
//父母結點和左右孩子下標
public
HaffmanNode(int
weight)
{
this.weight
=
weight;
this.parent=-1;
this.left=-1;
this.right=-1;
}
public
HaffmanNode()
{
this(0);
}
public
String
toString()
{
return
this.weight+",
"+this.parent+",
"+this.left+",
"+this.right;
}
return
code;
}
public
static
void
main(String[]
args)
{
int[]
weight={5,29,7,8,14,23,3,11};
//指定權值集合
HaffmanTree
htree
=
new
HaffmanTree(weight);
System.out.println("哈夫曼樹的結點數組:\n"+htree.toString());
String[]
code
=
htree.haffmanCode();
System.out.println("哈夫曼編碼:");
for
(int
i=0;
i<code.length;
i++)
System.out.println(code[i]);
}
}
❷ 哈夫曼編碼和解碼系統有編碼和解碼菜單項
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define N 20
#define M 2*N-1
char * cd;
typedef char *Huffmancode[N+1];
typedef struct
{
int weight;
int parent;
int LChild;
int RChild;
char c;
}HTNNOde,HuffmanTree[M+1];
void select(HuffmanTree p,int k,int *i,int *j)
{
int m,n=1;
while((n<=k)&&p[n].parent!=0) //尋找雙親節點為空的起始節點
{
n++;
}
m=p[n].weight;
*i=n;
while(n<=k) //找最小的值
{
if(p[n].weight<m&&p[n].parent==0)
{
*i=n;
m=p[n].weight;
}
n++;
}
n=1;
while((n<=k&&p[n].parent!=0)||n==(*i))
{
n++;
}
m=p[n].weight;
*j=n;
while(n<=k) //找次小的值
{
if(p[n].weight<m&&n!=*i&&p[n].parent==0)
{
*j=n;
m=p[n].weight;
}
n++;
}
if(*i>*j)
{
n=*i;
*i=*j;
*j=n;
}
}
void creatHuffmanTree(HuffmanTree ht,int w[],int n)
{
int m=2*n-1,i,s1,s2;
for(i=1;i<=n;i++)
{
ht[i].weight=w[i];
ht[i].parent=0;
ht[i].LChild=0;
ht[i].RChild=0;
}
for(i=n+1;i<=m;i++)
{
ht[i].weight=0;
ht[i].parent=0;
ht[i].LChild=0;
ht[i].RChild=0;
// printf("%d\n",ht[i].weight);
}
for(i=n+1;i<=m;i++)
{
select(ht,i-1,&s1,&s2); /*ht前i-1項選雙親為零且權最小的兩結點*/
// printf("%d,%d\n",s1,s2);
ht[i].weight=ht[s1].weight+ht [s2].weight;
ht[s1].parent=i;
ht[s2].parent=i;
ht[i].LChild=s1;
ht[i].RChild=s2;
// printf("%d\n",ht[i].weight);
}
// i=1;
/* while(i<=9)
{printf("%d\n",ht[i].weight);
i++;}
*/
}
void CrtHuffmanCode(HuffmanTree ht,Huffmancode hc,int n,char w[N][20])
{
int i,p,c;
int start,j=1;
// char w[20][20];
cd=(char *)malloc(n*sizeof(char ));
cd[n-1]='\0';
for(i=1;i<=n;i++)
{ start=n-1;
c=i;
p=ht[i].parent;
while ( p!=0)
{
--start;
if(ht[p].LChild == c)
cd[start]='0';
else cd[start]='1';
c=p;
p=ht[p].parent;
}
hc[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(hc[i],&cd[start]);
strcpy(w[j],hc[i]);
j++;
printf("%s\n",hc[i]);//實驗性列印
}
}
void translationhuffman(char w[N][20],HuffmanTree ht,int n)
{
char litter[20];int i;char yes_no;
do
{
printf("輸入哈夫曼編碼編碼\n");
scanf("%s",litter);
for(i=1;i<=n;i++)
if(strcmp(litter,w[i])==0)
{
printf("該密碼對應的字母\n");
printf("%c",ht[i].c);
break;
}
if(i==n+1)
printf("無該密碼對應字母\n");
printf(" \n要繼續解碼嗎（Y/N）\n");
do
{
yes_no=getchar();
}while(yes_no!='Y'&&yes_no!='y'&&yes_no!='N'&&yes_no!='n');
}while(yes_no!='N'&&yes_no!='n');
}
main()
{
HuffmanTree ht;
Huffmancode hc;
int i,n;
int h[50];char w[N][20];
printf("請輸入節點總個數");
scanf("%d",&n);
printf("請輸入哈夫曼樹權值和對應字母\n");
for(i=1;i<=n;i++)
scanf("%d %c",&h[i],&ht[i].c);
creatHuffmanTree(ht,h,n);
/* i=1;
while(i<=9)
{printf("%d\n",ht[i].weight);
i++;}*/
CrtHuffmanCode(ht,hc,n,w);
translationhuffman(w,ht,n);
}
❸ 哈夫曼編碼/解碼器
注釋非常詳細，希望對你有所幫助！
#ifndef Huffman_Tree_h
#define Huffman_Tree_h
#endif
#include <stdio.h>
typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode, * HuffmanTree; //存儲赫夫曼樹的結點類型
typedef char * * HuffmanCode; //用於存儲字元集中各個字元相應的赫夫曼編碼
void strcpy(char *S1,char *S2){ //將字元串S2復制到S1
int i = 0;
while( S2[i] != '\0' ){
S1[i] = S2[i];
i++;
}
S1[i] = '\0';
}
void Select(HuffmanTree HT,int t,int &s1,int &s2){ //在HT[1]到HT[t-1]中找出權值最小的兩個S1和S2
int i = 1;
s1 = s2 = 0;
HT[0].weight = 65535;
while( i <= t ){ //遍歷查找權值最小的結點S1
if( HT[i].parent == 0 && HT[i].weight < HT[s1].weight )
s1 = i;
i++;
}
i = 1;
while( i <= t ){ //遍歷查找除S1外權值最小的結點S2
if( i != s1 && HT[i].parent == 0 && HT[i].weight < HT[s2].weight )
s2 = i;
i++;
}
}
int HuffmanCoding( HuffmanTree &HT,HuffmanCode &HC,int *w,int n){ //根據各個字元的權值構造赫夫曼樹HT，將對應的赫夫曼編碼存儲在HC中
int s1,s2,m,i,start;
unsigned int c,f;
HTNode * p;
char *cd;
if( n <= 1 ) return 0;
m = 2 * n - 1; //赫夫曼樹的總結點樹為m
HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode)); //申請存儲赫夫曼樹的空間
for(p = HT + 1, i = 1; i <= n; ++i, ++p, ++w){ //將各個葉子結點的weight賦以相應的權值，parent,lchild,rchild均賦為0
p->weight = *(w+1);
p->parent = p->lchild = p->rchild = 0;
}
for( ; i <= m; ++i, ++p ){ //將各個非葉子結點的weight,parent,lchild,rchild均賦為0
p->weight = p->parent = p->lchild = p->rchild = 0;
}
for( i = n + 1; i <= m; ++i ){ //構造赫夫曼樹，給各個非葉子結點賦值
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;
}
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; //編碼在數組cd[]中的最前位置
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)); //為第i個字元編碼分配空間
strcpy(HC[i], &cd[start]); //將cd[]數組的start位置到n-1位置復制給HC[i]
}
free(cd); //釋放空間
return 1;
}
以上為第一部分
#include <stdio.h>
#include <stdlib.h>
#include "Huffman_Tree.h"
#define Yes 1 //當程序已經調用過初始化赫夫曼樹的InitHuff_T()函數，或已從htfTree文件讀取過，則將Init_Mode置為Yes，否則為No
#define No 0
void InitHuff_T( HuffmanTree &HT, HuffmanCode &HC, char ch[],int &n ){ //初始化赫夫曼數，要求用戶輸入字元和相應權值
int i = 1,w[100],tem,j;
char a[20];
FILE *save;
printf("請輸入編碼字元集的大小n:");
scanf("%d",&n); //獲取用戶輸入的字元集個數
while( i <= n ){ //獲取用戶輸入的字元和相應權值，分別存儲在ch[]和w[]數組中
printf("請輸入第%d個字元和該字元的權值w:",i);
fflush(stdin);
scanf("%c%d",&ch[i],&w[i]);
i++;
}
ch[i] = '\0';
HuffmanCoding(HT,HC,w,n); //根據用戶的輸入，生成赫夫曼數及各個字元相應的赫夫曼編碼，分別存在HT樹和HC中
if(( save = fopen("htfTree","w")) == NULL ){ //打開用於存儲赫夫曼樹的文件
printf("Open file fail......\n");
exit(0);
}
tem = n; //接下來的14行是將字元集大小轉換成字元形式寫入到文件中
j = 0;
while( tem != 0 ){
tem = tem / 10;
j++;
}
tem = n;
a[j] = '\0';
while( tem != 0 ){
a[j - 1] = (char)(tem % 10 + 48);
tem = tem / 10;
j--;
}
fputs(a,save);
printf("%d\n",n); //向屏幕輸出字元集大小n
fputc('\n',save);
for( i = 1; i <= n; i++ ){ //分別向文件和屏幕輸出各個字元和相應的赫夫曼編碼
fputc(ch[i],save); printf("%c\t",ch[i]);
fputc('\t',save);
fputs(HC[i],save); printf("%s\n",HC[i]);
fputc('\n',save);
}
for(i = 1; i <= 2 * n - 1; i++ ){ //將赫夫曼樹各個結點的parent,lchild,rchild分別寫入到文件中
tem = HT[i].parent; //將i結點的parent轉換成字元並寫入到文件中
if(tem == 0){
fputc(tem + 48,save);
fputc(' ',save);
}
else{
j = 0;
while( tem != 0 ){
tem = tem / 10;
j++;
}
tem = HT[i].parent;
a[j] = '\0';
while( tem != 0 ){
a[j - 1] = (char)(tem % 10 + 48);
tem = tem / 10;
j--;
}
fputs(a,save);
fputc(' ',save);
}
tem = HT[i].lchild; //將i結點的lchild轉換成字元並寫入到文件中
if(tem == 0){
fputc(tem + 48,save);
fputc(' ',save);
}
else{
j = 0;
while( tem != 0 ){
tem = tem / 10;
j++;
}
tem = HT[i].lchild;
a[j] = '\0';
while( tem != 0 ){
a[j - 1] = (char)(tem % 10 + 48);
tem = tem / 10;
j--;
}
fputs(a,save);
fputc(' ',save);
}
tem = HT[i].rchild; //將i結點的rchild轉換成字元並寫入到文件中
if(tem == 0){
fputc(tem + 48,save);
fputc('\n',save);
}
else{
j = 0;
while( tem != 0 ){
tem = tem / 10;
j++;
}
tem = HT[i].rchild;
a[j] = '\0';
while( tem != 0 ){
a[j - 1] = (char)(tem % 10 + 48);
tem = tem / 10;
j--;
}
fputs(a,save);
fputc('\n',save);
}
}
fclose(save);
}
void Encoding(HuffmanTree &HT, HuffmanCode &HC, char ch[]){ //根據赫夫曼編碼將用戶指定的文件中的字元編成相應的編碼,並將所得編碼存儲到用戶指定文件
FILE *ToBeTran,*CodeFile;
char ToBeTran_Name[100],CodeFile_Name[100]; //存儲用戶指定文件的文件名
int i;
char c;
printf("請輸入所要進行編碼的文件的文件名:");
scanf("%s",ToBeTran_Name); //獲得所要進行編碼的文件的文件名
if(( ToBeTran = fopen(ToBeTran_Name,"r")) == NULL ){ //打開文件
printf("Open file fail......\n");
exit(0);
}
printf("請輸入編碼後編碼表示的信息所存儲到的文件的文件名:");
scanf("%s",CodeFile_Name); //獲得編碼後編碼表示的信息所存儲到的文件的文件名
if(( CodeFile = fopen(CodeFile_Name,"w")) == NULL ){ //打開文件
printf("Open file fail......\n");
exit(0);
}
c = fgetc(ToBeTran); //從文件讀取一個字元
while( c != EOF ){ //對文件中的各個字元進行編碼，直至文件結尾
i = 1;
while( c != ch[i] && ch[i] != '\0' ) //在ch[]數組中查找從文件讀取的字元
i++;
if(ch[i] == '\0'){ //未找到，c不在ch[]數組中，c無法被識別，程序出錯，退出
printf("字元%c無法識別，程序將退出。\n",c);
exit(0);
}
fputs(HC[i],CodeFile); //若找到，則將c相應的赫夫曼編碼寫入到文件中
printf("%s",HC[i]); //將c相應的赫夫曼編碼輸出到屏幕
c = fgetc(ToBeTran); //讀入文件中的下一個字元
}
printf("\n");
fclose(ToBeTran);
fclose(CodeFile);
}
void Decoding(HuffmanTree HT, char ch[] , int n){ //對指定的存儲由赫夫曼編碼表示的信息的文件進行解碼，翻譯成相應的字元表示，並存儲到指定文件
int p,i = 1;
char code[1000],c;
char CodeFile_Name[100],TextFile_Name[100]; //存儲用戶指定文件的文件名
p = 2 * n - 1;
FILE *CodeFile,*TextFile;
printf("請輸入所要譯的文件名:");
scanf("%s",CodeFile_Name); //獲得所要譯的文件的文件名
if(( CodeFile = fopen("CodeFile","r")) == NULL ){ //打開文件
printf("Open file fail......\n");
exit(0);
}
printf("請輸入譯後的字元存儲到的文件的文件名:");
scanf("%s",TextFile_Name); //獲得譯後的字元存儲到的文件的文件名
if(( TextFile = fopen(TextFile_Name,"w")) == NULL ){ //打開文件
printf("Open file fail......\n");
exit(0);
}
c = fgetc(CodeFile);
while( c != EOF ){
code[i] = c;
i++;
c = fgetc(CodeFile);
}
code[i] = '\0'; //從文件讀取字元，存儲在code[]數組中
i = 1;
while ( code[i] != '\0' && p != 0 ){ //對數組code[]中的赫夫曼編碼進行解碼
if ( code[i] == '0' )
p=HT[p].lchild; //進入左分支
else
p = HT[p].rchild; //進入右分支
if (!HT[p].lchild&& !HT[p].rchild){ //進入葉子結點
fputc(ch[p], TextFile); //將相應的字元寫入到文件中
printf("%c",ch[p]); //將相應的字元輸出到屏幕
p = 2 * n - 1; //重新從樹根出發進行解碼
}
i++;
}
printf("\n");
}
void ReadHuff_T( HuffmanTree &HT, HuffmanCode &HC, char ch[], int &n){ //從文件讀取赫夫曼樹
FILE *htfTree;
char c[100],ch1;
int i,j,t;
if(( htfTree = fopen("htfTree","r")) == NULL ){ //打開存有赫夫曼樹信息的文件
printf("Open file fail......\n");
exit(0);
}
fgets(c,10,htfTree); //獲取赫夫曼樹葉子結點個數的字元串表示形式
i = 0; //以下6行將字元串形式轉換成整數形式
while( c[i] != '\n' )
i++;
n = 0;
for( j = 0; j < i; j++ )
n = 10 * n + c[j] - '0'; //求出葉子結點數n
HC = (HuffmanCode)malloc((n + 1) * sizeof(char *)); //申請HC空間
HT = (HuffmanTree)malloc((2 * n) * sizeof(HTNode)); //申請赫夫曼樹存儲空間
i = 1;
while( i <= n ){
ch[i] = fgetc(htfTree); //讀取字元集中的一個字元
HC[i] = (char *)malloc((10)*sizeof(char)); //申請用於存儲讀取到的字元集中的字元的赫夫曼編碼的空間
fgetc(htfTree); //將『\t』輸出
ch1 = fgetc(htfTree); //讀取赫夫曼編碼，存儲在相應的HC[i][]數組里
int j = 0;
while( ch1 != '\n' ){
HC[i][j] = ch1;
j++;
ch1 = fgetc(htfTree);
}
HC[i][j] = '\0';
i++;
}
ch[i] = '\0';
i = 0;
while( i < 2 * n - 1 ){ //讀取赫夫曼樹的各個結點的parent,lchild,rchild.並賦值到赫夫曼樹HT中
ch1 = fgetc(htfTree); //讀取parent的字元串形式,存儲在c[]中，並將其轉換成整數形式，賦給HT[i].parent
j = 0;
while( ch1 != ' ' ){
c[j] = ch1;
j++;
ch1 = fgetc(htfTree);
}
HT[i+1].parent = 0;
for( t = 0; t < j; t++ )
HT[i+1].parent = 10 * HT[i+1].parent + c[t] - '0';
ch1 = fgetc(htfTree); //讀取lchild的字元串形式，並將其轉換成整數形式，賦給HT[i].lchild
j = 0;
while( ch1 != ' ' ){
c[j] = ch1;
j++;
ch1 = fgetc(htfTree);
}
HT[i+1].lchild = 0;
for( t = 0; t < j; t++ )
HT[i+1].lchild = 10 * HT[i+1].lchild + c[t] - '0';
ch1 = fgetc(htfTree); //讀取rchild的字元串形式，並將其轉換成整數形式，賦給HT[i].rchild
j = 0;
while( ch1 != '\n' ){
c[j] = ch1;
j++;
ch1 = fgetc(htfTree);
}
HT[i+1].rchild = 0;
for( t = 0; t < j; t++ )
HT[i+1].rchild = 10 * HT[i+1].rchild + c[t] - '0';
i++;
}
}
int main(){
HuffmanTree HT;
HuffmanCode HC;
char ch[100]; //用於存儲字元集
int n,Init_Mode = No; //n為字元集的大小，Init_Mode = No 表示內存中沒有赫夫曼樹的信息
char mode; //讓用戶選擇不同的操作
printf("請輸入你要選擇的功能\n");
printf("\t\tI -- 初始化\t\tE -- 編碼\n");
printf("\t\tD -- 解碼 \t\tQ -- 退出程序\n");
scanf("%c",&mode); //獲得用戶選擇的操作
while( mode != 'Q' && mode != 'q' ){ //當用戶輸入不為Q或q時，執行相應操作
switch(mode){
case 'I' :
InitHuff_T(HT,HC,ch,n);
Init_Mode = Yes;
break;
case 'i' :
InitHuff_T(HT,HC,ch,n);
Init_Mode = Yes;
break;
case 'E' :
if( No == Init_Mode )
ReadHuff_T(HT,HC,ch,n);
Encoding(HT,HC,ch);
Init_Mode = Yes;
break;
case 'e' :
if( No == Init_Mode )
ReadHuff_T(HT,HC,ch,n);
Encoding(HT,HC,ch);
Init_Mode = Yes;
break;
case 'D' :
if( No == Init_Mode )
ReadHuff_T(HT,HC,ch,n);
Decoding(HT,ch,n);
Init_Mode = Yes;
break;
case 'd' :
if( No == Init_Mode )
ReadHuff_T(HT,HC,ch,n);
Decoding(HT,ch,n);
Init_Mode = Yes;
default :
printf("您的輸入有錯，請重新選擇.\n");
}
printf("請輸入你要選擇的功能\n");
printf("\tI -- 初始化\tE -- 編碼\n");
printf("\tD -- 解碼 \tQ -- 退出程序\n");
fflush(stdin);
scanf("%c",&mode); //讓用戶繼續選擇相應的操作，直至用戶選擇退出
}
return 0;
}
❹ 我需要一個程序設計的代碼：設計一個利用哈夫曼演算法的編碼和解碼系統
我的這個能實現編碼與解碼；
//huffman.h
const int Lengh=1000;
char coding[100]; //存儲二進制字元串
int n; //定義全局變數
enum Child{none,lchild,rchild}; //採用枚舉標記事左孩子還是右孩子
struct element
{
char letter,*code;
int weight; //權值域
int parent;
Child a;
};
void Select(element h[],int k,int *a,int *b);
void InitHuffmanTree(element huffTree[],char t[],int w[]) //哈夫曼樹的初始化
{
int i,m=2*n-1,s1,s2;
for(i=0;i<n;i++) //初始前n個結點
{
huffTree[i].code='\0';
huffTree[i].parent=-1;
huffTree[i].a=none;
huffTree[i].letter=t[i];
huffTree[i].weight=w[i];
}
for(;i<=m;i++) //後m-n個結點置空
{
huffTree[i].code='\0';
huffTree[i].letter=' ';
huffTree[i].parent=-1;
huffTree[i].a=none;
huffTree[i].weight=0;
}
for(i=n;i<m;i++) //建立哈夫曼樹
{
Select(huffTree,i-1,&s1,&s2); //在huffTree中找權值最小的兩個結點s1,s2
huffTree[s1].parent=i; //將s1,s2合並，則s1,s2的雙親是k
huffTree[s2].parent=i;
huffTree[s1].a=lchild;
huffTree[s2].a=rchild;
huffTree[i].weight=huffTree[s1].weight+huffTree[s2].weight;
}
}
void Select(element h[],int k,int *a,int *b) //尋找最小和次小節點的序號
{
int i;
int min1=1000;
int min2=1000;
for (i=0;i<=k;i++)//找最小的結點序號
{
if (h[i].parent==-1&&h[i].weight<min1)
{
*a=i;
min1=h[i].weight;
}
}
for(i=0;i<=k;i++)//找次小結點的序號
{
if(h[i].parent==-1&&(*a!=i)&&h[i].weight<min2)
{
*b=i;
min2=h[i].weight;
}
}
}
void HuffmanTreeCode(element HT[]) //單個字元編碼
{
int i;
char *temp;
temp=(char *)malloc(n*sizeof(char)); //分配n個字元空間
temp[n-1]='\0';
int p;
int s;
for(i=0;i<n;i++)
{
p=i;
s=n-1;
while(HT[p].parent!=-1)//從結點回溯,左孩子為0,右孩子為1
{
if(HT[p].a==lchild)
temp[--s]='0';
else if(HT[p].a==rchild)
temp[--s]='1';
p=HT[p].parent;
}
HT[i].code=(char *)malloc((n-s)*sizeof(char));//分配結點碼長度的內存空間
strcpy(HT[i].code,temp+s);
printf("%c",HT[i].letter);
printf(":"); printf(" ");
printf("%s\n",HT[i].code);
}
}
void HuffmanTreeYima(element huff[],char cod[],int b) //解碼
{
char sen[100];
char temp[50];
char voidstr[]=" ";
int t=0; int s=0;
for(int i=0 ; i<b; i++)
{
temp[t++]=cod[i];
temp[t] = '\0';
for(int j=0;j<n;j++)
{
if (!strcmp(huff[j].code,temp)) //代碼段吻合
{
sen[s]=huff[j].letter;
s++;
strcpy(temp,voidstr); //將TEMP置空
t=0;
break;
}
}
}
sen[s]='\0';
cout<<"解碼為:"<<endl;
cout<<sen<<endl;
}
//h.cpp
#include <iostream.h>
#include <string.h>
#include <malloc.h>
#include <stdio.h>
#include "huffman.h"
void main()
{
element h[Lengh];
char c,a[Lengh],p;
int i,b[Lengh];
int symbol=1;
cout<<"!!!!歡迎來到哈夫曼編碼與解碼!!!!"<<endl;
cout<<"編碼："<<endl;
cout<<"請輸入要編碼字元的個數：";
cin>>n;
for(i=0;i<n;i++)
{
cin.get();//跳過輸入流中的一個字元(即獲取上次輸入的回車鍵)
cout<<"字元："; cin.get(c); a[i]=c;
cout<<"權值："; cin>>b[i];
}
InitHuffmanTree(h,a,b); //哈夫曼樹的初始化
HuffmanTreeCode(h); //編碼
cout<<"解碼："<<endl;
cout<<"請輸入要解碼的二進制字元串,輸入'#'結束：";
int k=0;
while(symbol)
{
cin>>p; coding[k]=p;
if(p=='#') symbol=0;
k++;
}
HuffmanTreeYima(h,coding,k-1); //進行解碼
}
❺ Java實現哈夫曼演算法，運行出現問題，求幫助，在線等！！！
可以在Dog與Cat類中重寫Animal中的animalDo方法，通過調用animalDo方法，
然後會自動根據不同的實例調用不同類中的方法（多態知識）。
❻ 題目：哈夫曼編碼，解碼系統
/* 哈夫曼編碼*/
#include "graphics.h"
#include "stdlib.h"
#include "Stdio.h"
#include "Conio.h"
#define MAX 53
char bmfile[10];
char a[100];
typedef struct
{char c,s[10];}MM;
MM mm[53];
typedef struct /*以數組存儲哈夫曼樹時的結點類型*/
{char ch;
int w,lcd,rcd,pt; /*權值、左孩子、右孩子、雙親*/
}HuffNode;
HuffNode Hm[MAX];
typedef struct CNode /*Auffman編碼的結點類型*/
{ char c;
struct CNode *prv;
}CODE;
CODE *cd;
wjbm1 (char a[])/*從文件中讀取要進行編碼的字元*/
{FILE *fp3;
char ch;
int i=0,n=0,k,t,m;
/*printf("\n輸入要編碼的文件名：");
scanf("%s",bmfile);*/
if((fp3=fopen("bmfile.txt","r"))==NULL)
{printf("\n文件不存在");
exit(0);}
while(!feof(fp3))
a[i++]=fgetc(fp3);
a[i]='\0';
for(i=0;a[i]!='\0';i++)
{if(a[i]>='A'&&a[i]<='Z') {Hm[a[i]-65].ch=a[i]; Hm[a[i]-65].w++;}
if(a[i]>='a'&&a[i]<='z') {Hm[a[i]-71].ch=a[i]; Hm[a[i]-71].w++;}
if(a[i]==' ') {Hm[52].ch=' ';Hm[52].w++;}
}
for(i=0;i<53;i++)
if(Hm[i].w!=0)
{ Hm[n].ch=Hm[i].ch;
Hm[n].w=Hm[i].w;
Hm[n].lcd=-1;
Hm[n].rcd=-1;
Hm[n].pt=-1;
n++;}
fclose(fp3);
return n;
}
zfbm1(char a[])
{
int n=0,i;
gets(a);
for(i=0;a[i]!='\0';i++)
{if(a[i]>='A'&&a[i]<='Z') {Hm[a[i]-65].ch=a[i]; Hm[a[i]-65].w++;}
if(a[i]>='a'&&a[i]<='z') {Hm[a[i]-71].ch=a[i]; Hm[a[i]-71].w++;}
if(a[i]==' ') {Hm[52].ch=' ';Hm[52].w++;}
}
printf("\n葉字信息(字元、權值):");
for(i=0;i<53;i++)
if(Hm[i].w!=0)
{printf("(%c,%d)",Hm[i].ch,Hm[i].w);
Hm[n].ch=Hm[i].ch;
Hm[n].w=Hm[i].w;
Hm[n].lcd=-1;
Hm[n].rcd=-1;
Hm[n].pt=-1;
n++;}
return n;
}
charTJ()
{char c;
int i;
printf("\n1-從文件中讀取字元生成樹;2-從鍵輸入字母生成樹;3-退出;\n");
while(1)
switch(c=getch())
{case '1':wjbm1(a);return;
case '2':puts("\n輸入字母");zfbm1(a);return;
case '3':return;
default:printf("\n輸入無效,重新輸入");scanf("%d",&c);}
}
void HuffmanCode(int n) /*哈夫曼編碼。n為哈夫曼樹的葉子數*/
{ int i,k,t;
CODE *p,*h;
cd=(CODE*)malloc(sizeof(CODE)*n);/*用於存儲每個葉子的編碼(鏈棧)*/
for(i=0;i<n;i++) /*搜索第i+1個葉子*/
{ k=i;h=0;
while((Hm+k)->pt>=0)
{ if((Hm+(Hm+k)->pt)->lcd==k)t=0;else t=1;
p=(CODE*)malloc(sizeof(CODE));
p->c=48+t;p->prv=h;h=p;
k=(Hm+k)->pt;
}
cd[i].prv=h;
}
}
void dispCodes(int n) /*顯示*/
{ int i,j=0;
CODE *p;
for(i=0;i<n;i++)
{ p=cd[i].prv;
/*printf("\n%c:",Hm[i].ch); */
mm[i].c=Hm[i].ch;
j=0;
while(p)
{{/*printf("%c",p->c);*/ mm[i].s[j++]=p->c;}
mm[i].s[j]='\0';
p=p->prv;
}
}
puts("\n顯示結果：");
for(i=0;i<n;i++)
printf("(%c,%s) ",mm[i].c,mm[i].s);
dispCode(n);
}
dispCode(int n) /*將各字元的編碼存入數組mm*/
{ int i,j;
CODE *p;
for(i=0;i<n;i++)
{ p=cd[i].prv;
/*printf("\n%c:",Hm[i].ch); */
mm[i].c=Hm[i].ch;
j=0;
while(p)
{{/*printf("%c",p->c);*/ mm[i].s[j++]=p->c;}
mm[i].s[j]='\0';
p=p->prv;
} }
}
Huffmanshu(int n) /*顯示哈夫曼樹的字元編碼*/
{int i;
HuffmanCode(n);
dispCodes(n);
}
wjbm(int n)
{FILE *fp4;
char ch;
int i=0,j;
wjbm1(a);
HuffmanCode(n);
dispCode(n);
fp4=fopen("stfile.txt","w");
for(i=0;a[i]!='\0';i++)
{for(j=0;j<n;j++)
if(a[i]==mm[j].c) fputs(mm[j].s,fp4);
}
puts("結果已寫入文件");
fclose(fp4);
}
zfbm(int n)
{int i,j;
puts(a);
HuffmanCode(n);
dispCode(n);
printf("解碼:");
for(i=0;a[i]!='\0';i++)
{for(j=0;j<n;j++)
if(a[i]==mm[j].c) printf("%s",mm[j].s);}
}
Huffmanbm(int n,HuffNode Hm[])/*哈夫曼編碼*/
{
int k;
char ch;
printf("\n1-結果輸出到文件；2-結果顯示在屏幕;3-退出;\n");
while(1)
switch(ch=getch())
{case '1':wjbm(n);return 0;
case '2':printf("\n源碼:");zfbm(n);return;
case '3':return 0;
default:printf("輸入無效,重新輸入");scanf("%d",&ch);}
}
wjjm(int n,char a[])
{FILE *fp1,*fp2;
char ch;
int i=0,k,t,m;
if((fp1=fopen("jmfile.txt","r"))==NULL)
{printf("\n文件不存在");
exit(0);}
fp2=fopen("st.txt","w");
while(!feof(fp1)) a[i++]=fgetc(fp1);
a[i]='\0'; k=i;
printf("\n1-結果輸出到文件；2-結果顯示在屏幕;3-退出;\n");
t=2*n-2;
while(1)
switch(ch=getch())
{case '1':
for(i=0;i<=k;)
{ if(a[i]=='0')
if(Hm[t].lcd==-1) { putc(Hm[t].c,fp2); t=2*n-2;}else {t=Hm[t].lcd;i++;}
else
if(Hm[t].rcd==-1) { fputc(Hm[t].c,fp2); t=2*n-2;}else {t=Hm[t].rcd;i++;}
} return;
case'2':
for(i=0;i<=k;)
{ if(a[i]=='0')
if(Hm[t].lcd==-1) { printf("%c",Hm[t].c); t=2*n-2;}else {t=Hm[t].lcd;i++;}
else
if(Hm[t].rcd==-1) { printf("%c",Hm[t].c); t=2*n-2;}else {t=Hm[t].rcd;i++;}
} return;
case'3':return 0;
}
fclose(fp1);
fclose(fp2);
}
zfjm(int n,char a[])/*對輸入的字元進行解碼*/
{int i,t,k;
printf("\n輸入要解碼的信息:");
scanf("%s",a);
k=strlen(a);
t=2*n-2;
printf("生成源代碼：");
for(i=0;i<=k;)
{ if(a[i]=='0')
if(Hm[t].lcd==-1) { printf("%c",Hm[t].c); t=2*n-2;}else {t=Hm[t].lcd;i++;}
else
if(Hm[t].rcd==-1) { printf("%c",Hm[t].c); t=2*n-2;}else {t=Hm[t].rcd;i++;}
}
}
void Huffmanjm(int n,HuffNode Hm[]) /*哈夫曼解碼。n為哈夫曼樹的葉子數*/
{ int m=n;
char *a,ch;
printf("\n1-對文件解碼；2-對字元解碼;3-退出;\n");
while(1)
switch(ch=getch())
{case '1':wjjm(m,a);return 0;
case '2':zfjm(m,a);return;
case '3':return 0;
}
}
void HuffmanTree() /*生成哈夫曼樹*/
{ int i,j,x,y,n;
char c;
n=charTJ();
for(i=0;i<n-1;i++)
{ x=0;
while((Hm+x)->pt>=0)x++; /*搜索第一個未處理的結點*/
y=x+1;
while((Hm+y)->pt>=0)y++; /*搜索第二個未處理的結點*/
j=y;
if((Hm+x)->w>(Hm+y)->w){j=y;y=x;x=j;}
for(j=j+1;j<n+i;j++) /*搜索兩個未處理且權值最小的結點*/
{ if((Hm+j)->pt<0&&(Hm+j)->w<(Hm+x)->w) {y=x;x=j;}
else
if((Hm+j)->pt<0&&(Hm+j)->w<(Hm+y)->w) y=j;
}
(Hm+x)->pt=n+i;(Hm+y)->pt=n+i;(Hm+n+i)->w=(Hm+x)->w+(Hm+y)->w;
(Hm+n+i)->lcd=x;(Hm+n+i)->rcd=y;(Hm+n+i)->pt=-1;
}
puts("\n1-顯示字元的編碼;2-編碼;3-解碼;4-退出;");
while(1)
switch(c=getch())
{case '1':Huffmanshu(n);break;
case '2':Huffmanbm(n,Hm);break;
case '3':Huffmanjm(n,Hm);break;
case '4':return;
}
}
int main()
{ char c;
gotoxy(29,1);
puts("文件編碼解碼系統");
window(1,3,80,25);
HuffmanTree();
getch();
clrscr();
}
❼ 課設題目：哈夫曼編碼與解碼的實現
妄末卉丫丫,yffrskngiw7112244622,轄回答.
❽ 哈夫曼編碼與解碼
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <stdlib.h>
#include <conio.h>
#define NN 10000
#define M 2*NN-1
#define IN 0
#define OUT 1
#define MAX_INT 32767
#define PRINTLN printf("\n\n\n\n\n\n\n\n");
typedef struct
{
int wi;
char c;
int tag;
int parent, lchild, rchild;
}huffmtype;
typedef char* encodetype[NN+1];
typedef struct
{
char c;
int times;
}codetype;
void PRINT()
{
PRINTLN;
printf("\t\t\t Huffman編/解碼器\n");
printf("\t\t\t ====================\n");
printf("\t\t\t 1.編碼 2.解碼 3.退出\n\n");
printf("\t\t\t >>選擇:");
}
FILE* OpenFile(char filename[20], char type[3])
{
FILE *fp = NULL;
if((fp = fopen(filename, type)) == NULL) exit(1);
return fp;
}
int ReadCode(codetype* code, FILE* fp)
{
char c;//保存某次從文件中讀入字元-
int n = 1;//記錄首次出現字元在數組中的下標-
int i;//循環變數-
int cnt = 1;
int tag;//標志某次讀入字元是否為首次出現字元，tag=1表示是首次出現;tag=0表示本次讀入字元為已有字元
while((c = fgetc(fp)) != EOF)//當文件沒有結束時讀入字元-
{
//從fp指向文件中讀取字元，存入字元變數c中-
tag = 1;//假設本次讀取字元為首次出現字元-
for(i = 1; i < n; i++)
{
if(c == code[i].c)//如果本次讀入字元為存儲在下標為i已有字元-
{
code[i].times++;//權值加1-
tag = 0;//標記本字元為已有字元-
break;//在已有數組元素中找到本次讀入字元，結束for(;;)循環-
}
}
if(tag)//當本字元為首次出現字元時-
{
code[n].c = c;//把改字元存入n指向的數組單元中-
code[n].times = 1;//記字元出現次數為1-
n++;//n指向下一個數組地址-
}
}
return n - 1;//返迴文件中字元集合的元素個數-
}
void InitHuffmanTree(huffmtype* huffmtree, int real_n, int real_m)//初始化-
{
int i;
for(i = real_n; i <= real_m; i++)
{
huffmtree[i].wi = 0;
huffmtree[i].c = 0;
huffmtree[i].tag = IN;
huffmtree[i].lchild = huffmtree[i].rchild = huffmtree[i].parent = 0;
}
}
void ReadDataWeight_Init(huffmtype* huffmtree, codetype* code, int real_n)//獲取權值及數值域值-
{
int i;
for(i = 1; i <= real_n; i++)//-
{
huffmtree[i].wi = code[i].times;
huffmtree[i].c = code[i].c;
huffmtree[i].tag = IN;
huffmtree[i].lchild = huffmtree[i].rchild = huffmtree[i].parent = 0;
}
}
int LeastNode(huffmtype *huffmtree, int max_i)//找到最小權值節點地址-
{
int i;
int least_i;
int max = MAX_INT;
for(i = 1; i <= max_i; i++)//遍歷1到max_i節點-
{
if(huffmtree[i].wi < max && huffmtree[i].tag == IN)//若節點權值比max小並且在森林中-
{
max = huffmtree[i].wi;//刷新max值-
least_i = i;//保存當前節點地址-
}
}
huffmtree[least_i].tag = OUT;//將最小權值節點從森林中移除-
return least_i;//返回最小節點地址
}
void Slect(huffmtype *huffmtree, int max_i, int *x1, int *x2)//找到權值最小的兩個節點，並將其下標值保存在x1，x2中-
{
*x1 = LeastNode(huffmtree, max_i);//計算合法最下權值下標-
*x2 = LeastNode(huffmtree, max_i);//
}
void CreatHuffmanTree(huffmtype* huffmtree, int real_n, int real_m)//創建哈弗曼樹-
{
int i;
int x1, x2;
for(i = real_n + 1; i <= real_m; i++)
{
Slect(huffmtree, i-1, &x1, &x2);//找到權值最小的兩個節點，並將其下標值保存在x1，x2中-
huffmtree[i].wi = huffmtree[x1].wi + huffmtree[x2].wi;//計算雙氣節點權值-
huffmtree[x1].parent = huffmtree[x2].parent = i;//計算雙親節點地址-
huffmtree[i].lchild = x1; huffmtree[i].rchild = x2;//計算雙親節點左右孩子地址-
}
}
void Encode(huffmtype *huffmtree, encodetype encode, int real_n)//依據已創建的HuffmanTree對字元進行編碼-
{
char *cd;
int i;
int start;
int c, p;
cd = (char*)malloc(real_n*sizeof(char));//cd用來存放某次運行時當前字元編碼-
cd[real_n - 1] = '\0';//作為字元結束符-
for(i = 1; i <= real_n; i++)//對real_n個節點進行遍歷-
{
start = real_n-1;
c = i;//c保存當前節點地址（下標）-
p = huffmtree[i].parent;//p保存當前節點雙親地址-
while(p)
{
start--;//計算編碼的起始地址-
if(huffmtree[p].lchild == c)//若當前節點為其雙親的左孩子-
{
cd[start] = '0';//編碼為0-
}
else//若為右孩子-
{
cd[start] = '1';//編碼為1-
}
c = p;//節點前進-
p = huffmtree[p].parent;//計算前進後節點雙親節點地址-
}
encode[i] =(char*)malloc((real_n - start)*sizeof(char));//申請空間用於存放編碼-
strcpy(encode[i], &cd[start]);//將本次編碼存入encode數組中-
}
free(cd);//釋放閑置存儲空間-
}
void WriteToFile(FILE *fp, encodetype encode, codetype *code, int real_n, char *readfile)//將編碼輸出到文件
{
int i;
char cod[NN];
FILE *fp2;
char c;
int cnt = 1, j;
fp2 = fopen(readfile, "rt");
while((c = fgetc(fp2)) != EOF)
{
cod[cnt++] = c;
}
fclose(fp2);
for(i = 1; i < cnt; i++)
{
for(j = 1; j <=real_n; j++)
{
if(cod[i] == code[j].c)
{
break;
}
}
fprintf(fp, "%s", encode[j]);
}
fclose(fp);
}
int IsError(FILE *fp)//對打開文件進行出錯判斷-
{
if(!fp)
{
printf("\t\t\t ×打開文件錯誤\n");
printf("\t\t\t 任意鍵返回主菜單");
getch();
return 1;//文件打開失敗-
}
return 0;//文件打開成功-
}
void GetFilename(char *filename, char type[13])//得到用戶輸入相關文件名
{
system("cls");
PRINTLN;
printf("\t\t\t %s:", type);
fflush(stdin);
gets(filename);
}
int PutIntoCode(codetype code[], huffmtype huffmtree[])//編碼函數
{
encodetype encode;
FILE* fp;//文件類型指針-
int real_n;//用來存放字元集長度-
char readfile[20];//從readfile文件中讀取字元，寫入到writefile文件中-
GetFilename(readfile, "讀取源文件");//從鍵盤讀取文件名-
fp=OpenFile(readfile, "rt");//打開待編碼文件-
if(IsError(fp))//判斷是否正確打開文件-
{
return 0;//打開文件失敗，返回主菜單-
}
real_n=ReadCode(code, fp);//從readfile文件讀取字元，將字元集合元素存入code數組，將集合元素個數存入real_n-
fclose(fp);//關閉文件-
ReadDataWeight_Init(huffmtree, code, real_n);//初始化HuffmanTree中從1到real_n的元素-
InitHuffmanTree(huffmtree, real_n, 2*real_n-1);//初始化HuffmanTree中real_n到2*real_n的元素-
CreatHuffmanTree(huffmtree, real_n, 2 * real_n - 1);//創建HuffmanTree-
Encode(huffmtree, encode, real_n);//根據HuffmanTree對字元進行編碼，編碼結果保存到encode數組中-
fp = OpenFile("CodeFile.txt", "wb");//打開待寫入文件-
WriteToFile(fp, encode, code, real_n, readfile);//將encode數組中元素寫入到文件中-
fclose(fp);//關閉文件-
printf("\t\t\t 完成編碼並保存至CodeFile.txt文件中");//列印完成編碼信息-
getch();//等待用戶輸入任意鍵返回主菜單-
return real_n;
}
void Translate(codetype code[], huffmtype huffmtree[], int real_n)//解碼函數
{
FILE *fp,*fp2;
int i, real_m;
char c;
char writefile[20];
GetFilename(writefile, "保存解碼文件到");
fp = OpenFile("CodeFile.txt", "rb");
fp2 = OpenFile(writefile, "wt");
if(IsError(fp))
{
return;
}
i = real_m = 2*real_n - 1;
while((c = fgetc(fp)) != EOF)
{
if(c == '0')
{
i = huffmtree[i].lchild;
}
else
{
i = huffmtree[i].rchild;
}
if(huffmtree[i].lchild == 0)
{
fputc(code[i].c, fp2);
i = real_m;
}
}
fclose(fp);
fclose(fp2);
printf("\t\t\t 完成解碼任務");
getch();
}
int main(void)
{
int choice;
int real_n = 0;
codetype code[NN];
huffmtype huffmtree[NN];
while(1)
{
system("cls");
PRINT();
scanf("%d",&choice);
switch(choice)
{
case 1 :
real_n = PutIntoCode(code, huffmtree);
break;//編碼函數
case 2 :
if(real_n) Translate(code, huffmtree, real_n);break;//解碼函數
case 3 :
exit(1);//退出程序
default :
printf("\t\t\t ★無效輸入");
getch();
break;
}
}
return 0;
}
❾ 哈夫曼樹編碼的應用（Java語言）
1）編寫函數實現選擇parent為0且權值最小的兩個根結點的演算法
2）編寫函數實現統計字元串中字元的種類以及各類字元的個數。
3）編寫函數構造赫夫曼樹。
4）編寫函數實現由赫夫曼樹求赫夫曼編碼表。
5）編寫函數實現將正文轉換為相應的編碼文件。
6）編寫函數實現將編碼文件進行解碼。
7）編寫主控函數，完成本實驗的功能。
❿ 用java實現哈夫曼編碼
只要自己再加個類Tree就可以了。
代碼如下：
public class Tree {
double lChild, rChild, parent;
public Tree (double lChild, double rChild, double parent) {
this.lChild = lChild;
this.rChild = rChild;
this.parent = parent;
}
public double getLchild() {
return lChild;
}
public void setLchild(double lChild) {
this.lChild = lChild;
}
public double getRchild() {
return rChild;
}
public void setRchild(double rChild) {
this.rChild = rChild;
}
public double getParents() {
return parent;
}
public void setParents(double root) {
this.parent = root;
}
}