?? huffmancode.cpp
字號:
/*哈夫曼編/譯碼器
完成Huffman 編碼的譯碼過程。
即輸入一個碼串，請翻譯成相應的字符串。
要求有編碼過程和解碼過程。*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define WordNUM 28//字符集中字符個數
#define MessageNUM 100000//最大信息量
typedef struct {
int N;
int SumWeight;
char word[WordNUM+1];
int weight[WordNUM+1];
}Word,*Wordset;//字符集及其權重.0號單元未用
typedef int Boolean;
typedef char* Message;//動態分配字符串數組存儲信息
typedef struct {
int n;//n序號
char data;
int weight;//權重值
int parent,lchild,rchild;
}HTNode,*HuffmanTree;//動態分配數組存儲哈夫曼樹;
typedef struct{
char data;
char* Code;//動態分配字符串數組存儲哈夫曼編碼表
}HCode,*HuffmanCode;//動態分配字符串數組存儲哈夫曼編碼表
void printstar(){
printf("************************************************************\n");
}//printstar
Boolean UserSaysYes(){//與用戶對話函數
int c,t;
printf("(y,n)?");
do{
while((c=getchar())=='\n');//Ignore new line character.
if(c=='y'||c=='Y'||c=='n'||c=='N')
{
while((t=getchar())!='\n');//讀去'\n'
return(c=='y'||c=='Y');
}
printf("Please respond by typing one of the letters y or n\n");
}while(1);
}
//字符集Wordset操作
void CreatWordset(Wordset w){//建立自定義字符集和權重
int i;
char word[WordNUM+1]={
'#',' ','\n',
'a','b','c','d','e','f','g',
'h','i','j','k','l','m','n',
'o','p','q','r','s','t',
'u','v','w','x','y','z'};
int weight[WordNUM+1]={
0,186,4,
60,13,22,32,103,21,15,
47,57,1,5,32,20,57,
63,15,1,48,51,80,
23,8,18,1,16,1};
w->N =WordNUM;//記錄字符個數
w->SumWeight=0;//記錄總的權重值
for(i=1;i<=w->N;i++)
{
w->word [i]=word[i];
w->weight [i]=weight[i];
w->SumWeight+=weight[i];
}
}
void SaveWordsetFile(Wordset w){//保存到文件
FILE*fp;
if(!(fp=fopen("wordset","wb")))puts("cann't open file.");
if(fwrite(w,sizeof(Word),1,fp)!=1)puts("SaveWordsetFile write error!");
fclose(fp);
}
void OpenWordsetFile(Wordset w){//讀文件
FILE*fp;
w=(Wordset)malloc(sizeof(Word));//字符集及其權重所占空間分配
if(!(fp=fopen("wordset","rb")))puts("cann't open file.");
fread(w,sizeof(Word),1,fp);
}
void OutputWordset(Wordset w){//輸出
int i;
for(i=1;i<=w->N;i++){
printf("%c %d\t",w->word [i],w->weight [i]);
}
printf("SumWeight=%d\n",w->SumWeight);
}
//Huffman操作
void Select(HuffmanTree HT,int t,int*s1,int*s2){//在HT[1...i-1]選擇parent為0且weight最小的兩個結點，其序號為s1,s2.
int i;
HuffmanTree p;
int weight=99999 ;
*s1=*s2=0;
for(i=1,p=HT+1;i<=t;++i,++p)
{
if(p->parent==0 )
if(weight>p->weight)
{
*s1=i;
weight=p->weight ;
}
}
weight=99999 ;
for(i=1,p=HT+1;i<=t;++i,++p)
{
if(p->parent==0 && i!=*s1)
if(weight>p->weight)
{
*s2=i;
weight=p->weight ;
}
}
}
void CreatHuffmanTree(HuffmanTree HT,Wordset w){//建立HuffmanTree
//w存放n個字符的權值（均>0），構造哈夫曼樹HT,并求出n個字符的哈夫曼編碼HC。
int i,n,m,s1,s2;
HuffmanTree p;
if(w->N<=1)return;
n=w->N;
m=2*n-1;//一棵有n個葉子結點的赫夫曼樹共有2n-1個結點
for(p=HT,i=0;i<=n;++i,++p)//HuffmanTree initing
{
p->n =i;
p->data =w->word [i];
p->weight =w->weight [i];
p->lchild =0; p->parent =0; p->rchild =0;
}
for(;i<=m;++i,++p){
p->n =i;p->lchild =0;p->data ='#';p->parent =0;p->rchild =0;p->weight =0;
}
printf("初始Huffman樹:\n");
for(p=&HT[1],i=1;i<=n;++i,++p)
{
printf("%d %c %d %d %d %d\t",p->n,p->data,p->weight,p->lchild,p->parent,p->rchild);
}
printf("\nCreat HTTree:\n");
for(i=n+1;i<=m;++i){//建哈夫曼樹
//在HT[1...i-1]選擇parent為0且weight最小的兩個結點，其序號為s1,s2.
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;
printf("%d %d %d %d %d\t",HT[i].n,HT[i].weight,HT[i].lchild,HT[i].parent,HT[i].rchild);
}
printf("\n");
}
void CreatHuffmanCode(HuffmanTree HT,HuffmanCode HC,Wordset w){//建立HuffmanCode
//---從葉子結點到根逆向求每個字符的哈夫曼編碼---
char* cd;
int i,n,start,c,f;
n=w->N ;
for(i=1;i<=n;i++)HC[i].data=w->word[i];
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';//左0右1
else cd[--start]='1';
}
HC[i].Code=(char*)malloc((n-start)*sizeof(char));//為第i個字符編碼分配空間
strcpy(HC[i].Code,&cd[start]);
}
free(cd);
for(i=1;i<=n;i++)
printf("%c %s\n",HC[i].data,HC[i].Code);
printf("\n");
}//HuffmanCoding
void SaveHuffmanFile(HuffmanTree HT,HuffmanCode HC,int m,int n){//保存HuffmanTree和HuffmanCode
FILE*fp1,*fp2;
int i;
//寫出到文件
if((fp1=fopen("HT","wb"))==NULL)
{puts("can't open file \"HT.dat\" .");exit(0); }
if((fp2=fopen("HC","wb"))==NULL)
{puts("can't open file \"HC.dat\" .");exit(0); }
for(i=0;i<=m;i++)
if(fwrite(&HT[i],sizeof(HTNode),1,fp1)!=1)puts("write error!\n");
for(i=0;i<=n;i++)
if(fwrite(&HC[i],sizeof(HC[i]),1,fp2)!=1)puts("write error!\n");
fclose(fp1);fclose(fp2);
}
void OpenHuffmanFile(HuffmanTree HT,HuffmanCode HC){ //從文件讀入
FILE*fp1,*fp2;
HT=(HuffmanTree)malloc((WordNUM+1)*sizeof(HTNode));//0號單元未用
HC=(HuffmanCode)malloc((WordNUM+1)*sizeof(char*));//分配n個字符編碼的頭指針向量
if((fp1=fopen("HT","rb"))==NULL)
{puts("can't open file \"HT.dat\" .");exit(0); }
if((fp2=fopen("HC","rb"))==NULL)
{puts("can't open file \"HC.dat\" .");exit(0); }
fread(&HT,sizeof(HT),1,fp1);
fread(&HC,sizeof(HC),1,fp2);
fclose(fp1);fclose(fp2);
}
void OutputHuffmanTree(HuffmanTree HT,int n,int m){//輸出HuffmanTree
int i;
puts("Huffman Tree:");
printf("%d leaves %d HTNode :\n",n,m);
puts("非葉節點的data域不是有效字符，不予輸出!");
for(i=1;i<=m;i++)//非葉節點的data域不是有效字符，不予輸出
{
if(i<=n)printf("%d %c %d %d %d %d\t",HT[i].n,HT[i].data,HT[i].weight,HT[i].lchild,HT[i].parent,HT[i].rchild);
else printf("%d %d %d %d %d\t",HT[i].n,HT[i].weight,HT[i].lchild,HT[i].parent,HT[i].rchild);
}
printf("\n");
}
void OutputHuffmanCode(HuffmanCode HC,int n){//輸出HuffmanCode
int i;
puts("Huffman Code:");
for(i=1;i<=n;i++)
printf("%c %s\n",HC[i].data,HC[i].Code);
printf("\n");
}
void MessageInput(Message M){//信息輸入
char s[1000]={'\0'};//輸入緩沖
M[0]='\0';
while(strlen(gets(s))>0)//提供多行信息輸入
{
strcat(M,s);
strcat(M,"\n");
}
}
void SaveMessageFile(Message M){//信息保存
FILE *fp;
if((fp=fopen("Message.txt","w"))==NULL)
{ printf("cann't open file");exit(0); }
fputs(M,fp);
fclose(fp);
}
void MessageFileOutput(Message M){//打開信息文件并輸出
FILE*fp;
char s[1000];
M[0]='\0';
puts("The message in the Message File is :");
if((fp=fopen("Message.txt","r"))==NULL){printf("cann't open file");exit(0); }
while(fgets(s,1000,fp)!=NULL){
fputs(s,stdout);
strcat(M,s);
}
fclose(fp);
printstar();
puts("MessageSource we code is:");
puts(M);
}
void MessageCoding(Message M,Message MD,HuffmanCode HC,int n){//信息編碼函數
int i,k;
MD[0]='\0';
for(i=0;M[i]!='\0';i++)
for(k=1;k<=n;k++)
if(M[i]==HC[k].data)strcat(MD,HC[k].Code);
}
void SaveMessageCode(Message MD){//信息編碼保存到文件
FILE *fp;
if((fp=fopen("MessageCode.txt","w"))==NULL)
{ printf("cann't open file");exit(0); }
fputs(MD,fp);
fclose(fp);
}
void OutputMessageCode(Message MD){//信息編碼輸出
puts("MessageCode is:");
puts(MD);
printstar();
strcat(MD,"#");//作為結束標志
}
void MessageDecoding(Message MD,HuffmanTree HT){//信息解碼函數
int i,root,r;
for(i=1;HT[i].parent!=0;i++);//找根
r=root=i;
for(i=0;MD[i]!='#';){
while(HT[r].lchild&&HT[r].rchild){//0左走1右走，直到葉節點
if(MD[i]=='1')r=HT[r].rchild;
else r=HT[r].lchild;
i++;
}
putchar(HT[r].data);//輸出葉節點
r=root;
}
putchar('\n');
}
void welcome(){
puts("-----------------HuffmanCoding---------------");
puts("\t\t\t\tJS000603-060059-李建平");
}
void main(){//主函數，安排流程。
HuffmanTree HT;
HuffmanCode HC;
Wordset w;
Message M,MD;
int n=WordNUM,m,i;
m=2*n-1;//一棵有n個葉子結點的赫夫曼樹共有2n-1個結點
printstar();
welcome();
printstar();
//初始化
for(i=0;i<5E8;i++);
printstar();
puts("初始化....");
printstar();
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0號單元未用
HC=(HuffmanCode)malloc((n+1)*sizeof(HCode));//分配n個字符編碼的頭指針向量
w=(Wordset)malloc(sizeof(Word));//字符集及其權重所占空間分配
MD=(Message)malloc(MessageNUM*sizeof(char));
M=(Message)malloc(MessageNUM*sizeof(char));
for(i=0;i<5E8;i++);
puts("Init OK!");
printstar();
//字符集操作與保存
puts("創建字符集和權重....");
printstar();
for(i=0;i<5E8;i++);
CreatWordset(w);//創建字符集和權重
puts("CreatWordset ok!");
printstar();
for(i=0;i<5E8;i++);
puts("Saving to file....");
printstar();
for(i=0;i<5E8;i++);
SaveWordsetFile(w);//保存到文件
puts("save OK!");
printstar();
puts("reading from the wordset file...");
printstar();
for(i=0;i<5E8;i++);
OpenWordsetFile(w);//讀文件
puts("The wordset and each word's weight are:");
printstar();
OutputWordset(w);//輸出
printstar();
//HuffmanTree和HuffmanCode的建立與保存
puts("建立HuffmanTree....");
printstar();
for(i=0;i<5E8;i++);
CreatHuffmanTree(HT, w);//建立HuffmanTree
printstar();
puts("建立HuffmanCode....");
printstar();
for(i=0;i<5E8;i++);
CreatHuffmanCode(HT,HC,w);//建立HuffmanCode
printstar();
puts("寫入文件前輸出HuffmanTree和HuffmanCode....");//寫入文件前輸出
printstar();
for(i=0;i<5E8;i++);
OutputHuffmanTree(HT,n,m);//輸出HuffmanTree
printstar();
for(i=0;i<5E8;i++);
OutputHuffmanCode(HC,n);//輸出HuffmanCode
printstar();
puts("Saving to file....");
printstar();
for(i=0;i<5E8;i++);
SaveHuffmanFile(HT,HC,n,m);//保存HuffmanTree和HuffmanCode到文件
puts("save OK!");
printstar();
puts("從文件讀入后輸出HuffmanTree和HuffmanCode....");//讀入文件后輸出
printstar();
for(i=0;i<5E8;i++);
OpenHuffmanFile(HT,HC);//打開HuffmanTree和HuffmanCode文件
OutputHuffmanTree(HT,n,m);//輸出HuffmanTree
printstar();
for(i=0;i<5E8;i++);
OutputHuffmanCode(HC,n);//輸出HuffmanCode
printstar();
do{//信息輸入及其編碼與解碼
puts("please input the message you want to code....");
printstar();
MessageInput(M);//信息輸入
printstar();
puts("saving to file....");//保存信息至文件
printstar();
for(i=0;i<5E8;i++);
SaveMessageFile(M);
puts("MessageSave OK!");
printstar();
puts("信息從文件讀出并輸出....");
printstar();
for(i=0;i<5E8;i++);
MessageFileOutput(M);//信息從文件讀出并輸出
printstar();
puts("信息編碼....");
for(i=0;i<5E8;i++);
MessageCoding(M,MD,HC,n);//信息編碼
printstar();
puts("saving to file....");
printstar();
for(i=0;i<5E8;i++);
SaveMessageCode(MD);
puts("save OK!");
printstar();
puts("編碼輸出");
printstar();
OutputMessageCode(MD);//編碼輸出
printstar();
puts("信息解碼....");
for(i=0;i<5E8;i++);
printf("The message after decoding is:\n");
MessageDecoding(MD,HT);//解碼輸出
printstar();
puts("源碼輸出對比....");
for(i=0;i<5E8;i++);
puts("The MessageSource is:");
puts(M);//源碼輸出對比
printstar();
printf("Try again?");
}while(UserSaysYes());//提供重復進行信息輸入
}//main?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -