Ⅰ 哈夫曼樹及哈夫曼編碼解碼的實現（根據程序畫流程圖及對每句程序注釋）
這是以前寫的，可是我不想加註釋了，Huffman編碼其實原理很簡單的，你自己好好學下吧，一句一句注釋也太誇張了啊。
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
int m,s1,s2;
typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char ** HuffmanCode;
void Select(HuffmanTree HT,int n)
{
int i,j;
for(i=1;i<=n;i++)
if(HT[i].parent==0)
{s1=i;
break;
}
for(j=i+1;j<=n;j++)
if(HT[j].parent==0)
{
s2=j;
break;
}
for(i=1;i<=n;i++)
{
if(HT[i].parent==0)
if(HT[s1].weight>HT[i].weight)
if(s2!=i)
s1=i;
}
for(j=1;j<=n;j++)
{
if(HT[j].parent==0)
if(HT[s2].weight>HT[j].weight)
if(s1!=j)
s2=j;
}
if(s1>s2)
{
int temp=s1;
s1=s2;
s2=temp;
}
}
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)
{
int i,j;
char *cd;
int p;
int cdlen;
if (n<=1) return;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode));
for (i=1; i<=n; i++)
{
HT[i].weight=w[i-1];
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("構造過程顯示：\n");
for(i=1;i<=m;i++)
printf("%4d%4d%4d%4d%4d\n",i,HT[i].weight, HT[i].parent,HT[i].lchild, HT[i].rchild);
system("pause");
for(i=n+1;i<=m;i++)
{
Select(HT,i-1);
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;
//添加查看，便於調試
/*printf("s1=%d,s2=%d\n",s1,s2);
for(j=1;j<=i;j++)
printf("%d%4d%4d%4d",j,HT[j].weight,HT[j].parent,HT[j].lchild, HT[j].rchild);
system("pause");
*/
}
cd = (char *)malloc(n*sizeof(char));
p=m;
cdlen=0;
for(i=1;i<=m;i++)
HT[i].weight=0;
while(p)
{
if(HT[p].weight==0)
{
HT[p].weight=1;
if(HT[p].lchild!=0)
{
p=HT[p].lchild;
cd[cdlen++]='0';
}
else if(HT[p].rchild==0)
{
HC[p]=(char *)malloc((cdlen+1)*sizeof(char));
cd[cdlen]='\0';
strcpy(HC[p],cd);
}
}
else if(HT[p].weight==1)
{
HT[p].weight=2;
if(HT[p].rchild!=0)
{
p=HT[p].rchild;
cd[cdlen++]='1';
}
}
else
{
HT[p].weight=0;
p=HT[p].parent;
--cdlen;
}
}
}
int main()
{
HuffmanTree HT;
HuffmanCode HC;
int *w,n,i;
printf("請輸入節點數：\n");
scanf("%d",&n);
HC = (HuffmanCode)malloc(n*sizeof(HuffmanCode));
w=(int *)malloc(n*sizeof(int));
printf("請輸入節點的權值：\n");
for(i=0;i<n;i++)
scanf("%d",&w[i]);
HuffmanCoding(HT,HC,w,n);
printf("輸出編碼：\n");
for(i=1;i<=n;i++)
printf("%2d(%4d):%s\n",i,w[i-1],HC[i]);
return 0;
system("pause");
}
Ⅱ 題目：哈夫曼編碼，解碼系統
/* 哈夫曼編碼*/
#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();
}
Ⅲ 哈夫曼編碼與解碼
#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;
}
Ⅳ 利用 數據結構 實現 哈夫曼編碼/解碼實現
//D:\2010 代碼\haffman\haffman\Node_statement.h
#define MAXVALUE 1000//定義最大權值
#define MAXBIT 100//定義哈夫曼樹中葉子結點個數
typedef struct
{
char data;//字元值
int num;//某個值的字元出現的次數
}TotalNode;
//統計結點，包括字元種類和出現次數
typedef struct
{
TotalNode tot[300];//統計結點數組
int num;//統計數組中含有的字元個數
}Total;
//統計結構體，包括統計數組和字元種類數
typedef struct
{
char mes[300];//字元數組
int num;//總字元數
}Message;
//信息結構體，包括字元數組和總字元數
typedef struct{
int locked[500];//密碼數組
int num;//密碼總數
}Locking;
//哈夫曼編碼後的密文信息
typedef struct
{
char data;//字元
int weight;//權值
int parent;//雙親結點在數組HuffNode[]中的序號
int lchild;//左孩子結點在數組HuffNode[]中的序號
int rchild;//右孩子結點在數組HuffNode[]中的序號
}HNodetype;
//哈夫曼樹結點類型，包括左右孩子，權值和信息
typedef struct
{
int bit[MAXBIT];
int start;
}HCodetype;
//哈夫曼編碼結構體，包括編碼數組和起始位
void reading_file(Message *message);//從文件中讀取信息
int writing_file(Message *message);//將信息寫進文件
void total_message(Message *message,Total *total);//統計信息中各字元的次數
void HaffmanTree(Total *total,HNodetype HuffNode[]);//構建哈夫曼樹
void HaffmanCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total);//建立哈夫曼編碼
void writing_HCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total);//將編碼規則寫進文件
void lock(Message *message,HNodetype HuffNode[],HCodetype HuffCode[],Total *total,Locking *locking);//給文件信息加密編碼
void writing_lock(Locking *locking);//將已編碼信息寫進文件
void first_function(HNodetype HuffNode[],HCodetype HuffCode[],Total *total,Message *message);
void display(Total *total,HNodetype HuffNode[]);
void writing_translate(Locking *locking,HCodetype HuffCode[],HNodetype HuffNode[],Total *total);//將已編碼信息翻譯過來並寫進文
//D:\2010 代碼\haffman\haffman\function_mian.cpp
#include"Node_statement.h"
#include<iostream>
#include<fstream>
#include "cstdlib"
using namespace std;
int main()
{
int i,j,choice,mark=0;//mark標記文件信息是否讀入到內存中
HNodetype HuffNode[500];//保存哈夫曼樹中各結點信息
HCodetype HuffCode[300];
Locking *locking;
Total *total;
Message *message;
locking=new Locking;
locking->num=0;
total=new Total;
total->num=0;
message=new Message;
message->num=0;
//初始化變數
printf("┏ ┓\n");
printf("┣ haffman_code system ┫ \n");
printf("┗ ┛\n");
printf("\n\n");
choice=0;
while(choice!=7 )
{
printf("＃〓§〓〓〓〓〓§〓〓〓〓§〓〓〓〓§〓＃ \n ");
printf(" 0:go \n");
printf("※********** 1：從文件讀取信息**********************※\n");
printf(" *********** 2：顯示編碼規則 ********************* \n");
printf(" ********** 3：將原文件信息寫進文件 ************ \n");
printf(" ********* 4：將編碼規則寫進文件 ************ \n");
printf(" ********** 5：將編碼後的信息寫進文件 ********** \n");
printf(" *********** 6：將解碼後的信息寫進文件 *********\n");
printf("※***********7：退出 *****************************※\n");
printf("＃〓§〓〓〓〓〓§〓〓〓〓§〓〓〓〓§〓＃ \n ");
printf(" please input the choice ");
cin>>choice;
switch(choice)
{
case 1:
reading_file(message);//從文件中讀取信息
mark=1;
break;
case 2://顯示編碼規則
if(mark==0)cout<<"請先從文件中讀取信息!"<<endl;
else
{
first_function(HuffNode,HuffCode,total,message);
cout<<"編碼規則為"<<endl;
for(i=0;i<total->num;i++)//顯示編碼規則
{
cout<<total->tot[i].data<<" ";
for(j=HuffCode[i].start+1;j<total->num;j++)
cout<<HuffCode[i].bit[j];
cout<<endl;
}
}
break;
case 3://將原文件信息寫進文件a_test1.txt
if(mark==0)cout<<"請先從文件中讀取信息!"<<endl;
else
writing_file(message);//將信息寫進文件
break;
case 4://將編碼規則寫進文件
if(mark==0)cout<<"請先從文件中讀取信息!"<<endl;
else
{
first_function(HuffNode,HuffCode,total,message);
writing_HCode(HuffNode,HuffCode,total);//將編碼規則寫進文件
}
break;
case 5://將編碼後的信息寫進文件
if(mark==0)cout<<"請先從文件中讀取信息!"<<endl;
else
{
first_function(HuffNode,HuffCode,total,message);
writing_lock(locking);//將已編碼信息寫進文件
}
break;
case 6://將解碼後的信息寫進文件
if(mark==0)cout<<"請先從文件中讀取信息!"<<endl;
else
{
first_function(HuffNode,HuffCode,total,message);
writing_translate(locking,HuffCode,HuffNode,total);//將已編碼信息翻譯過來並寫進文件
}
break;
}
}
/**
列印haffman樹
**/
display(total,HuffNode);
system("PAUSE");
return 0;
}
void display(Total *total,HNodetype HuffNode[])
{
int i,j;
for(i=0;i<2*total->num-1;i++)
{
printf("data weight lchild rchild parent \n");
printf(" %c %d %d %d %d\n",HuffNode[i].data,HuffNode[i].weight,HuffNode[i].lchild,HuffNode[i].rchild,HuffNode[i].parent);
}
}
void reading_file(Message *message)
/**
絕對路徑下讀取a_test.txt file
message 中的num記錄suoyou字元總數 ，放在nes【】中
equal to the buffer
**/
{
int i=0;
char ch;
ifstream infile("a_test.txt",ios::in | ios::out);
if(!infile)//打開失敗則結束
{
cout<<"打開a_test.txt文件失敗"<<endl;
exit(1);
}
else
cout<<"讀取文件成功"<<endl;
while(infile.get(ch) && ch!='#')//讀取字元直到遇到#
{
message->mes[i]=ch;
i++;
}
message->num=i;//記錄總字元數
infile.close();//關閉文件
}
int writing_file(Message *message)
/**
把從數組message 的信息write to disk，a_test1.txt to save
**/
{ /*
int i;
ifstream outfile("a_test1.txt",ios::in ); //打開文件
if( !outfile )//打開失敗則結束
{
cout<<"打開a_test1.txt文件失敗"<<endl;
return -1;
}
for(i=0;i<message->num;i++)//寫文件
outfile.put(message->mes[i]);
cout<<"信息寫進文件成功"<<endl;
outfile.close();//關閉文件
return 0;*/
int i;
FILE *fp1=NULL;
if((fp1 = fopen("a_test1.txt","at"))==NULL)
{
printf("can't open the file\n");
exit(0);
}
for(i=0;i<message->num;i++)
fprintf(fp1,"%d ",message->mes[i]);
printf("文件寫入成功!\n");
i=fclose(fp1);
if(i==0)
printf("文件關閉成功!\n");
else
printf("文件關閉失敗!\n");
}
void total_message(Message *message,Total *total)
/**
統計message中不同字元 的個數，和相同字元重復的次數，重復字元用mark標記，
total.tot[] 放不同字元，TotalNode 類型（char，num）
total.num 統計不同字元個數
使total這塊內存空間有數據，
**/
{
int i,j,mark;
for(i=0;i<message->num;i++)//遍歷message中的所有字元信息
{
if(message->mes[i]!=' ')//字元不為空格時
{
mark=0;
for(j=0;j<total->num;j++)//在total中搜索當前字元
if(total->tot[j].data==message->mes[i])//搜索到，則此字元次數加1，mark標志為1
{
total->tot[j].num++;
mark=1;
break;
}
if(mark==0)//未搜索到，新建字元種類，保存進total中，字元類加1
{
total->tot[total->num].data=message->mes[i];
total->tot[total->num].num=1;
total->num++;
}
}
}
}
void HaffmanTree(Total *total,HNodetype HuffNode[])
/**create the haffman tree
不同字元個數為葉子節點個數對應書上的n，
相同字元的個數為其權值weight；
get HuffNode to store the tree
**/
{
int i,j,min1,min2,x1,x2;
for(i=0;i<2*(total->num)-1;i++)//初始化哈夫曼樹並存入葉子結點權值和信息
{
if(i<=total->num-1)
HuffNode[i].data=total->tot[i].data;
HuffNode[i].weight=total->tot[i].num;
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
}
for(i=0;i<total->num-1;i++)
{
min1=min2=MAXVALUE;
x1=x2=0;
for(j=0;j<total->num+i;j++)//選取最小x1和次小x2的兩權值
{
if(HuffNode[j].parent==-1&&HuffNode[j].weight<min1)
{
min2=min1;
x2=x1;
min1=HuffNode[j].weight;
x1=j;
}
else
if(HuffNode[j].parent==-1&&HuffNode[j].weight<min2)
{
min2=HuffNode[j].weight;
x2=j;
}
}
HuffNode[x1].parent=total->num+i;//修改親人結點位置
HuffNode[x2].parent=total->num+i;
HuffNode[total->num+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;
HuffNode[total->num+i].lchild=x1;//左孩子比右孩子權值小
HuffNode[total->num+i].rchild=x2;
}
}
void HaffmanCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total)
/***
haffman to code (0,10,110,)
得到每個不同字元（葉子）的編碼，
存貯在數組HuffCode【】中,bit[] store the char,start store the loction
**/
{
int i,j,c,p;
HCodetype cd;
for(i=0;i<total->num;i++)//建立葉子結點個數的編碼
{
cd.start=total->num-1;//起始位初始化
p=HuffNode[i].parent;
c=i;
while(p!=-1)//從葉結點向上爬直到到達根結點
{
if(HuffNode[p].lchild==c)//左分支則為0
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;//右分支則為1
cd.start--;//起始位向前移動
c=p;
p=HuffNode[p].parent;
}
for(j=cd.start+1;j<total->num;j++)//保存求出的每個葉結點編碼和起始位
HuffCode[i].bit[j]=cd.bit[j];
HuffCode[i].start=cd.start;
}
}
void writing_HCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total)
/**
HuffNode[]to input the leaf
HuffCode[]to input the code
all is to the a_test2.txt ,save the code
**/
{
/*打開HCode文件，失敗則結束。將信息寫進文件*/
int i,j;
FILE *fp2=NULL;
if((fp2 = fopen("a_test2.txt","at"))==NULL)
{
printf("can't open the file\n");
exit(0);
}
for(i=0;i<total->num;i++)
{fprintf(fp2,"%d ",HuffNode[i].data);
printf(" ");
for(j=HuffCode[i].start+1;j<total->num;j++)
fprintf(fp2,"%d ",HuffCode[i].bit[j]);
}
printf("編碼規則寫進文件成功!\n");
i=fclose(fp2);
if(i==0)
printf("文件關閉成功!\n");
else
printf("文件關閉失敗!\n");
}
void lock(Message *message,HNodetype HuffNode[],HCodetype HuffCode[],Total *total,Locking *locking)
/***
對messag操作，對所有字元加密，
結果存貯在數組locked[]中，locking 記錄已經加密後的密文
**/
{
int i,j,m;
for(i=0;i<message->num;i++)//把相同的不同的字元全部 遍歷
{
if(message->mes[i]==' ')//碰到空格則以-1形式保存進locked數組中
{
locking->locked[locking->num]=-1;
locking->num++;
}
else
for(j=0;j<total->num;j++)//從total中找到對應的字元
{
if(HuffNode[j].data==message->mes[i])
//找到在HuffNode 中對應字元，找到下標j
// 在HuffCode
for(m=HuffCode[j].start+1;m<total->num;m++)///////// !
{
locking->locked[locking->num]=HuffCode[j].bit[m];//加密
locking->num++;
}
}
}
}
void writing_lock(Locking *locking)
/*
將密文寫到a_test3.txt
*/
{
int i;
FILE *fp3=NULL;
if((fp3= fopen("a_test3.txt","at"))==NULL)
{
printf("can't open the file\n");
exit(0);
}
for(i=0;i<locking->num;i++)
{
if(locking->locked[i]==-1)
printf(" ");
else
fprintf(fp3,"%d ",locking->locked[i]);
}
printf("已編碼信息寫進文件成功!\n");
i=fclose(fp3);
if(i==0)
printf("文件關閉成功!\n");
else
printf("文件關閉失敗!\n");
}
void writing_translate(Locking *locking,HCodetype HuffCode[],HNodetype HuffNode[],Total *total)
/**
密文翻譯成明文，然後存到文件 a_test4.txt
**/
{
int i,j,mark[100],start[100],min,max;
FILE *fp4=NULL;
if((fp4 = fopen("a_test4.txt","at"))==NULL)
{
printf("can't open the file\n");
exit(0);
}
for(i=0;i<total->num;i++)//start數組初始化
{
start[i]=HuffCode[i].start+1;//。。。。
}
for(i=0;i<total->num;i++)//mark數組初始化
{
mark[i]=1;
}
min=0;
for(max=0;max<locking->num;max++)//寫文件
{
if(locking->locked[max]==-1)//碰到空格信息則直接輸出空格
{
printf(" ");//把空格寫到文件
min++;
}
else
{
for(i=min;i<=max;i++)//查找從min開始到max的編碼對應的信息
{
for(j=0;j<total->num;j++)
{
if(start[j] == total->num+1)
mark[j]=0; //對應編碼比所給編碼短則不在比較
if(mark[j]==1&&locking->locked[i]==HuffCode[j].bit[start[j]])
start[j]++;
else
mark[j]=0;
}
}
for(i=0;i<total->num;i++)//找到對應信息，則寫進文件
{
if(mark[i]==1&&start[i]==total->num)
{
fprintf(fp4,"%d ",HuffNode[i].data);//寫到文件outfile
break;
}
}
if(i!=total->num)
min=max+1;
for(i=0;i<total->num;i++)//start數組初始化
{
start[i]=HuffCode[i].start+1;
}
for(i=0;i<total->num;i++)//mark數組初始化
{
mark[i]=1;
}
}
}
printf("文件寫入成功!\n");
i=fclose(fp4);
if(i==0)
printf("文件關閉成功!\n");
else
printf("文件關閉失敗!\n");
}
void first_function(HNodetype HuffNode[],HCodetype HuffCode[],Total *total,Message *message)
{
total_message(message,total);//統計信息中各字元的出現次數
HaffmanTree(total,HuffNode);//構建哈夫曼樹
HaffmanCode(HuffNode,HuffCode,total);//建立哈夫曼編碼
}
Ⅳ java實現哈夫曼演算法，運行出現問題，求幫助，在線等！！！
可以在Dog與Cat類中重寫Animal中的animalDo方法，通過調用animalDo方法，
然後會自動根據不同的實例調用不同類中的方法（多態知識）。
Ⅵ 哈夫曼編碼與解碼 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]);
}
}
Ⅶ 用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;
}
}
Ⅷ 哈夫曼解碼演算法
C++的
#include<stdlib.h>
#include<fstream.h>
#include<iomanip.h>
#include<windows.h>
ofstream outstuf;
#define MAXBIT 50 // 哈夫曼編碼的最大長度
#define MAXVALUE 50 // 最大權值
#define MAXLEAF 50 // 哈夫曼樹中葉子結點個數
#define MAXNODE MAXLEAF*2-1 //樹中結點總數
//哈夫曼樹結點結構
typedef struct
{
char data ; //結點值
int weight; //權值
int parent; //雙親結點
int lchild; //左孩子結點
int rchild; //右孩子結點
}HNodeType;
HNodeType HuffNode[MAXNODE];
//存放哈夫曼編碼的數據元素結構
typedef struct
{
int bit [MAXBIT]; //存放哈夫曼碼
int start; //編碼的起始下標
}HCodeType;
void Haffmanfile(int n); //保存文件
HNodeType *HaffmanTree(int n) ; //構造哈夫曼樹
void Haffmancode(int n); //構造哈夫曼編碼
HNodeType *HaffmanTree(int n) //構造哈夫曼樹
{
int i,j,m1,m2,x1,x2;
for(i=0;i<2*n-1;i++) //所有結點的初始化
{
HuffNode[i].weight=0;
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
}
cout<<"\t________________________________________"<<endl;
cout<<"\t輸入葉子結點的值和權值"<<endl;
cout<<"\t________________________________________"<<endl;
for(i=0;i<n;i++)
{
cout<<"\t______________________"<<endl;
cout<<"\t輸入第"<<i+1<<"個葉子節點的值: ";
cin>>HuffNode[i].data;
cout<<"\t輸入第"<<i+1<<"個葉子節點的權值: ";
cin>>HuffNode[i].weight;
}
for(i=0;i<n-1;i++) //構造哈夫曼樹
{ m1=m2=MAXVALUE; x1=x2=0;
for(j=0;j<n+i;j++)
{
if(HuffNode[j].parent==-1&&HuffNode[j].weight<m1) //只在尚未構造二叉樹的結點中查找
{
m2=m1;
x2=x1;
m1=HuffNode[j].weight;
x1=j;
}
else if(HuffNode[j].parent==-1&&HuffNode[j].weight<m2)
{
m2=HuffNode[j].weight;
x2=j;
}
}
//將找出的兩棵權值最小的子樹合並為一棵子樹
HuffNode[x1].parent=n+i;
HuffNode[x2].parent=n+i;
HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;
HuffNode[n+i].lchild=x1;
HuffNode[n+i].rchild=x2;
}
return HuffNode;
}
//構造哈夫曼編碼
void Haffmancode(int n)
{
int i,j,c,p;
HNodeType *HuffNode=new HNodeType[MAXNODE];
HCodeType *HuffCode=new HCodeType[MAXLEAF];
HCodeType *cd=new HCodeType;
HuffNode=HaffmanTree(n); //建立哈夫曼樹
for(i=0;i<n;i++)
{
cd->start=n-1;
c=i;
p=HuffNode[c].parent;
while(p!=-1) //循環直到樹根結點
{
if(HuffNode[p].lchild==c)
cd->bit[cd->start]=0; //處理左孩子結點
else
cd->bit[cd->start]=1; //處理右孩子結點
cd->start--;
c=p;
p=HuffNode[c].parent;
}
for(j=cd->start+1;j<n;j++)
HuffCode[i].bit[j]=cd->bit[j];
HuffCode[i].start=cd->start; //指向哈夫曼編碼最開始字元
}
cout<<"\n\t每個葉子結點的值及對應的哈夫曼編碼"<<endl;
for(i=0;i<n;i++)
{ cout<<"\t****************************************"<<endl;
cout<<"\t第"<<i+1<<"個葉子結點的值和哈夫曼編碼為:";
cout<<HuffNode[i].data<<" ";
for(j=HuffCode[i].start+1;j<n;j++)
cout<<HuffCode[i].bit[j];
cout<<endl;
}
outstuf.open("bianma.txt",ios::out);
outstuf<<"____________\n哈夫曼編碼:\n____________ "<<endl;
for(i=0;i<n;i++)
{
for(j=HuffCode[i].start+1;j<n;j++)
outstuf<<HuffCode[i].bit[j]<<" ";
outstuf<<endl;
}
cout<<"\t\t*******************"<<endl;
cout<<"\t\t哈夫曼編碼保存成功!"<<endl;
cout<<"\t\t*******************"<<endl;
outstuf.close();
Haffmanfile(n);
}
void Haffmanfile(int n)
{
char s[80];
int a[20],i=0,r;
ifstream instuf("bianma.txt",ios::in);
if(!instuf)
{
cout<<"文件不能打開!"<<endl;
abort();
}
instuf.getline(s,80);
while(instuf>>a[i])
i++;
for(r=0;r<i;r++) cout<<a[r]<<" ";
if(a[0]!=0&&a[0]!=1)
{
cout<<"此文件無內容!"<<endl;
abort();
}
instuf.close();
int p=0,j=0,k=0; char zu[10],ch;
system("pause");system("cls");
cout<<"\n\t\t*************************************"<<endl;
cout<<"\t\t是否要對原編碼進行解碼操作 (Y or N)?:\t";
cin>>ch;
if(ch=='N'||ch=='n') return;
for(r=0;r<n;r++)
{
p=2*n-2;
while(HuffNode[p].lchild!=-1&&HuffNode[p].rchild!=-1)
{
if(a[j]==0) p=HuffNode[p].lchild;
if(a[j]==1) p=HuffNode[p].rchild;
j++;
}
zu[k]=HuffNode[p].data;
k++;
}
outstuf.open("yima.txt",ios::out);
outstuf<<"解碼為: "<<endl;
for(j=0;j<n;j++) outstuf<<HuffNode[j].data<<" ";
outstuf<<endl;
cout<<"\t\t**************\n\t\t解碼保存成功!\n\t\t**************"<<endl;
outstuf.close();
instuf.open("yima.txt",ios::in);
if(!instuf)
{
cout<<"文件不能打開!"<<endl;
abort();
}
instuf.getline(s,80);
i=0;
cout<<"\n\t\t哈夫曼編碼的解碼為: ";
while(instuf>>zu[i])
{cout<<zu[i]<<" ";
i++;
}
cout<<endl;
instuf.close();
}
void main()
{
int n,i;char choice;system("cls");system("color 80");
cout<<"\t _______________________________________________________"<<endl;
cout<<"\t 本演示系統可以良好的演示哈夫曼編碼和解碼的產生,"<<endl;
cout<<"\t 但本程序有一定的不完善，用戶可以隨時到CSDN社區關注更新!"<<endl;
cout<<"\t _______________________________________________________"<<endl;
loop:
cout<<"\t\t _________________________________\n\n";
cout<<"\t\t 1.哈夫曼演示系統 0.退出演示系統\n";
cout<<"\t\t _________________________________\n\n\t請選擇\t";
cin>>choice;
switch(choice)
{case '1': system("cls");
cout<<"\t\t _____________________________\n\n";
cout<<"\t\t\t請輸入葉子結點個數:\t";
cin>>n;
Haffmancode(n);
cout<<"\n\t*********輸出哈夫曼樹!**********"<<endl;
cout<<"\t字元 "<<"權值 "<<"左孩子指針 "<<"右孩子指針"<<endl;
for( i=0;i<2*n-1;i++)
{cout<<"\t";
cout<<setw(5)<<HuffNode[i].data<<setw(5)<<HuffNode[i].weight<<setw(5)<<
HuffNode[i].lchild<<setw(5)<<HuffNode[i].rchild<<setw(5)<<
HuffNode[i].parent<<endl;
}
system("pause");system("cls");goto loop;break;
case '0':break;
}
}
Ⅸ 哈夫曼編碼與解碼
使用說明：首先建立哈夫曼樹，輸入你的信號源的個數，然後輸入每個信號的符號及其相應的頻率（最後乘以100不要出現小數的為好）我的輸入文件名為Myinput.txt即在C盤下建立文本文檔取名為Myinput.txt然後輸入你的信號的符號以空格結束，最後按提示選擇你需要實現的功能！
/********************************************************************
created: 2010/07/01
created: 1:7:2010 17:53
filename: D:\Program Files\Microsoft Visual Studio\MyProjects\課程設計\HuffmanTree.cpp
file path: D:\Program Files\Microsoft Visual Studio\MyProjects\課程設計
file base: HuffmanTree
file ext: cpp
author: xiezhong
purpose:
*********************************************************************/
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
typedef struct{
int weight;
int parent;
int lchild;
int rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;
int minl(HuffmanTree t,int i);
void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n);
void select(HuffmanTree t,int i,int *s1,int *s2);
void main(){
HuffmanTree HT;
HuffmanCode HC;
int *w,n,i;
cout<<"請輸入字元的個數："<<endl;
cin>>n;
char *ch;
ch=(char *)malloc((n+1)*sizeof(char));
w=(int *)malloc(n*sizeof(int));
for (i=0;i<n;i++)
{
cout<<"請輸入字元以及對應的權值（中間以空格隔開）："<<endl;
cin>>ch[i+1];
cin>>w[i];
}//給w賦值。
HuffmanCoding(&HT,&HC,w,n);
cout<<"*******哈夫曼樹已經建成啦！*********"<<endl;
cout<<"===================================="<<endl;
while (true)
{
cout<<" 1:將哈夫曼樹存入Huffmancode文件中"<<endl;
cout<<" 2:從Myinput文件中讀取字元然後編碼存入codemyinput文件中；"<<endl;
cout<<" 3:從codemyinput讀取編碼輸入到頻幕上。"<<endl;
cout<<" 4:將codemyinput讀取編碼解碼後存檔。"<<endl;
cout<<" 0:退出系統！！！！"<<endl;
cout<<" 請輸入你的選擇："<<endl;
int c;
cin>>c;
if (c==0)
{
cout<<"程序已經結束！謝謝使用！！！"<<endl;
break;
}
while(c>4||c<0)
{
cout<<"你輸入有誤請重新輸入："<<endl;
cin>>c;
}
fstream file;
ofstream outfile;
ifstream printfile;
ifstream codefile;
ofstream textfile;
if(c==1){
file.open("c:\\Huffmancode.txt", ios::out);
if(!file)
{
cout<<"can not open output file."<<endl;
exit(1);
}
for(i=1;i<=n;i++){
file<<ch[i]<<"的編碼是："<<HC[i]<<endl;
} //將哈夫曼樹存入Huffmancode文件中去、
file.close();
cout<<"哈夫曼樹已經存入Huffmancode文件中"<<endl;
cout<<"\n______________________"<<endl;
}
if(c==2){
file.open("c:\\Myinput.txt",ios::in);//從文件Myinput中讀取字元。
outfile.open("c:\\codemyinput.txt",ios::out);
//將讀取出的字元進行編碼存入codemyinput文件中去、
char read;
cout<<"從Myinput文件中讀取的數據為："<<endl;
while(!file.eof()){
file.get(read);
cout<<read;
for(i=1;i<=n;i++)
{
if(ch[i]==read)
{
// outfile<<read<<"的哈弗曼編碼為：";
outfile<<HC[i];//將對應字元的編碼輸出到文件中。
break;
}
}
if(i>n)
{
outfile<<read;
}
}//讀取文件完畢
outfile.close();
file.close();
cout<<"\n______________________"<<endl;
}
if(c==3){
printfile.open("c:\\codemyinput.txt",ios::in);
int count=0;
char c;
cout<<"\n這些字母對應的哈夫曼編碼是："<<endl;
while (!printfile.eof())
{
printfile.get(c);
cout<<c;
if (count%50==0&&count!=0)
{
cout<<endl;
}
count++;
}
cout<<endl;
printfile.close();
}
if(c==4){
codefile.open("c:\\codemyinput.txt",ios::in);
textfile.open("c:\\textfile.txt",ios::out);
int flag=2*n-1;
char read;
codefile.get(read);
while(!codefile.eof())
{
//cout<<read;
if(read=='0'||read=='1')
{
while(true)
{
if(flag>=1&&flag<=n) //判斷停止的條件
{
textfile<<ch[flag];
break;
}
else if(read=='0')
{
flag=HT[flag].lchild;
}
else
{
flag=HT[flag].rchild;
}
codefile.get(read);
}
}
else
{
textfile<<read;
codefile.get(read);
}
flag=2*n-1;
}
codefile.close();
textfile.close();
}
}//while循環結束的括弧。
}
int minl(HuffmanTree t,int i)
{
int a,j,flag;
int k=1000;
for(a=1;a<=i;a++)
{
if(!t[a].parent)
{
flag=a;
break;
}
}
for(j=a;j<=i;j++)
{
if(t[j].parent==0&&t[j].weight<k)
{
k=t[j].weight;
flag=j;
}
}
t[flag].parent=1; //這是必須的
return flag;
}
void Select(HuffmanTree t,int i,int *s1,int *s2)
{
int j;
*s1=minl(t,i);
*s2=minl(t,i);
if(*s1>*s2)
{
j=*s1;
*s1=*s2;
*s2=j;
}
}
void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n){
if(n<=1)
return;
int s1,s2,start;
char *cd=NULL;
int m=2*n-1;
*HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
HuffmanTree p;
int i,c,f;
for(p=(*HT)+1,i=1;i<=n;i++,p++,w++){
(*p).weight=*w;
(*p).parent=0;
(*p).rchild=0;
(*p).lchild=0;
}
for(;i<=m;i++,p++){
(*p).weight=0;
(*p).parent=0;
(*p).rchild=0;
(*p).lchild=0;
}
for(i=n+1;i<=m;i++){
Select(*HT,i-1,&s1,&s2);//找出兩個權值最小的節點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;
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]);
}
free(cd);
}
Ⅹ 哈夫曼樹編碼的應用（Java語言）
1）編寫函數實現選擇parent為0且權值最小的兩個根結點的演算法
2）編寫函數實現統計字元串中字元的種類以及各類字元的個數。
3）編寫函數構造赫夫曼樹。
4）編寫函數實現由赫夫曼樹求赫夫曼編碼表。
5）編寫函數實現將正文轉換為相應的編碼文件。
6）編寫函數實現將編碼文件進行解碼。
7）編寫主控函數，完成本實驗的功能。