?? huffman.cpp
字號(hào):
/*Huffman編碼與解碼器-----可以完成對(duì)ASCII碼表的所有字符的壓縮功能 時(shí)間：2008年12月11日21:22:23*/
#include<stdio.h>
#include<malloc.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
#define TABLE 128 //26個(gè)字母表，
#define MAX 64 // MAX最長(zhǎng)編碼長(zhǎng)度
int LENGHTH=0; // 全局變量_字符個(gè)數(shù)
typedef struct //Huffman樹(shù)節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)定義
{
char data; // 節(jié)點(diǎn)的字符值
int p; //字符出現(xiàn)的頻率
int lchild, rchild; //節(jié)點(diǎn)的左右孩子位置
int parent; //父節(jié)點(diǎn)的位置
}HNode;
HNode huffmannode[2*TABLE-1];
typedef struct //Huffman編碼的數(shù)據(jù)結(jié)構(gòu)
{
int bit[MAX]; //字符的編碼
int start; //編碼存放的其實(shí)位置
}Hcode;
Hcode huffmancode[TABLE];
void initial() //初始化Huffman樹(shù)節(jié)點(diǎn)
{
int i;
for (i=0;i<2*TABLE-1;i++)
{
huffmannode[i].data=0;
huffmannode[i].p=0;
huffmannode[i].lchild=-1;
huffmannode[i].parent=-1;
huffmannode[i].rchild=-1;
}
}
void hufftreeconstruct() //創(chuàng)建Huffman樹(shù)
{
int i,j,lnode,rnode,n;
int min1,min2;
n=LENGHTH;
lnode=rnode=0;
for(i=0;i<n-1;i++)
{
min1=min2=65536;
for(j=0;j<n+i;j++)
{
if(huffmannode[j].parent==-1)
{
if(huffmannode[j].p<min1)
{
min2=min1;
rnode=lnode;
min1=huffmannode[j].p;
lnode=j;
}
else if(huffmannode[j].p<min2)
{
min2=huffmannode[j].p;
rnode=j;
}
}
}
huffmannode[lnode].parent=n+i;
huffmannode[rnode].parent=n+i;
huffmannode[n+i].p=huffmannode[lnode].p+huffmannode[rnode].p;
huffmannode[n+i].lchild=lnode;
huffmannode[n+i].rchild=rnode;
}
printf(" \n生成的Huffman 樹(shù)如下:\n");
printf("位置： 頻率： 左孩子： 右孩子： 父節(jié)點(diǎn)位置：\n");
for(i=0;i<2*n-1;i++)
{
printf(" %3d %3d %3d %3d %3d\n",i,huffmannode[i].p,huffmannode[i].lchild,huffmannode[i].rchild,huffmannode[i].parent);
}
printf("\nHufman 樹(shù)創(chuàng)建完畢\n");
}
FILE *fileopen()
{
FILE *fp;
if((fp=fopen("test.txt","r"))==NULL)
{
printf("\ntest.txt文件打開(kāi)失敗,文件可能不存在\n");
exit(0);
}
else
{
printf("\ntest.txt文件打開(kāi)成功\n");
}
return fp;
}
void tongjipinlv(FILE *fp) //從test.txt文件中讀取字符 并統(tǒng)計(jì)各字符出現(xiàn)的頻率
{
int a[TABLE]={0};
int i,j,b=0;
char ch;
while(feof(fp)==0)
{
ch=fgetc(fp);
i=ch;
a[i]++;
}
fclose(fp);
j=0;
for(i=0;i<TABLE;i++)
{
if(a[i]!=0)
{
LENGHTH++;
huffmannode[j].data=i;
huffmannode[j].p=a[i];
j++;
}
}
printf("\n文件中出現(xiàn)的字符: 頻率：\n");
for(i=0;i<LENGHTH;i++)
{
printf("%c %d \n",huffmannode[i].data,huffmannode[i].p);
}
printf("\n");
}
void huffman_code() //對(duì)Huffman樹(shù)進(jìn)行編碼
{
Hcode code;
int i,j,k,m;
FILE *fp;
for(i=0;i<LENGHTH;i++)
{
code.start=MAX-1;
m=i;
k=huffmannode[m].parent;
while(k!=-1)
{
if(huffmannode[k].lchild==m)
code.bit[code.start]=0;
else code.bit[code.start]=1;
code.start--;
m=k;
k=huffmannode[m].parent;
}
for(j=code.start+1;j<MAX;j++)
huffmancode[i].bit[j]=code.bit[j];
huffmancode[i].start=code.start;
}
printf("\nHuffman編碼如下:\n");
for(i=0;i<LENGHTH;i++)
{ printf("%c: ",huffmannode[i].data);
for(j=huffmancode[i].start+1;j<MAX;j++)
printf(" %d",huffmancode[i].bit[j]);
printf("\n");
}
printf("\n編碼結(jié)束 \n");
if((fp=fopen("code.txt","w+"))!=NULL)
for(i=0;i<LENGHTH;i++)
{
fprintf(fp,"%c ",huffmannode[i].data);
for(j=huffmancode[i].start+1;j<MAX;j++)
fprintf(fp,"%d",huffmancode[i].bit[j]);
fprintf(fp,"\n");
}
else
{
printf("Can not open or create the file \"code.txt\".\n");
exit(0);
}
fclose(fp);
printf("\nHuffman編碼方案文件----code.txt創(chuàng)建成功!\n");
}
void code_ef() //計(jì)算編碼效率 用Huffman編碼的總長(zhǎng)度除以等長(zhǎng)編碼的總長(zhǎng)度
{
float m,n,t;
int i;
m=0;
for(i=0;i<LENGHTH;i++)
m=m+huffmannode[i].p*(MAX-huffmancode[i].start);
n=huffmannode[2*LENGHTH-2].p*MAX;
t=m/n*100;
printf("\nHuffman 編碼效率： %f%%\n",t);
}
void compression() //對(duì)test.txt文件進(jìn)行壓縮，所以內(nèi)容轉(zhuǎn)換成Huffman碼
{
int i,j,m=0;
char ch;
FILE *fp1,*fp2;
fp1=fileopen();
if((fp2=fopen("compression.txt","w+"))==NULL)
{
printf("\n文件創(chuàng)建不成功\n");
exit(0);
}
else
printf("\ncompression.txt文件創(chuàng)建成功。\n");
ch=fgetc(fp1);
while(feof(fp1)==0)
{
for(i=0;i<LENGHTH;i++)
if(ch==huffmannode[i].data)
break;
for(j=huffmancode[i].start+1;j<MAX;j++)
fprintf(fp2,"%d",huffmancode[i].bit[j]);
ch=fgetc(fp1);
}
fclose(fp1);
fclose(fp2);
}
void huffman_decode() //Huffman 解碼函數(shù)
{
FILE *fp1,*fp2;
char ch;
int m;
if((fp1=fopen("compression.txt","r"))==NULL)
{
printf("\n在解碼時(shí)compression.txt文件不成功!\n");
exit(0);
}
if((fp2=fopen("huffman_decode.txt","w+"))==NULL)
{
printf("\nhuffman_decode.txt文件創(chuàng)建不成功\n");
exit(0);
}
else
printf("\nhuffman_decode.txt文件創(chuàng)建成功!\n\n下面進(jìn)行解碼：\n");
ch=fgetc(fp1);
m=2*LENGHTH-2;
while(feof(fp1)==0)
{
if(ch=='0')
{
if(huffmannode[huffmannode[m].lchild].data==0)
m=huffmannode[m].lchild;
else
{
fprintf(fp2,"%c",huffmannode[huffmannode[m].lchild].data);
m=2*LENGHTH-2;
}
}
else
{
if(huffmannode[huffmannode[m].rchild].data==0)
m=huffmannode[m].rchild;
else
{
fprintf(fp2,"%c",huffmannode[huffmannode[m].rchild].data);
m=2*LENGHTH-2;
}
}
ch=fgetc(fp1);
}
fclose(fp1);
fclose(fp2);
printf("\nHuffman 解碼成功，解碼結(jié)果保存在huffman_decode.txt中。請(qǐng)注意檢查！\n\n");
}
void main()
{
FILE *fp;
printf("\nHuffman 編碼器-------<李海 2601307023>\n");
initial();
fp=fileopen();
tongjipinlv(fp);
hufftreeconstruct();
huffman_code();
code_ef();
compression();
huffman_decode();
}
?? 快捷鍵說(shuō)明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -