hafuman.cpp

数据结构中重要的哈夫曼算法

#include<stdio.h> 
#include <malloc.h> 
#include <stdlib.h> 
#include <string.h> 
//函数结果状态代码 
#define TRUE 1 
#define FALSE 0 
#define OK 1 
#define ERROR 0 
#define INFEASIBLE -1 
#define OVERFLOW -2 
#define UINT_MAX 1000 
typedef int Status; 


/* c6-7.h 哈夫曼树和哈夫曼编码的存储表示 */ 
typedef struct HTNode 
{ 
char leaf; 
unsigned int weight; 
unsigned int parent,lchild,rchild; 
}HTNode,*HuffmanTree; /* 动态分配数组存储哈夫曼编码表 */ 

typedef char **HuffmanCode; /* 动态分配数组存储哈夫曼编码表 */ 
typedef struct Node 
{ 
char leaf; 
unsigned int weight; 
struct Node * next; 
}LeafNode,*LeafLink; 

typedef struct 
{ 
LeafLink head; 
unsigned len; 
}LeafLinkList; 

int min1(HuffmanTree t,int i) 
{ /* 函数void select()调用 */ 
int j,flag; 
unsigned int k=UINT_MAX; /* 取k为不小于可能的值 */ 
for(j=1;j<=i;j++) 
if(t[j].weight<k&&t[j].parent==0) 
k=t[j].weight,flag=j; 
t[flag].parent=1; 
return flag; 
} 

void select(HuffmanTree t,int i,int *s1,int *s2) 
{ /* s1为最小的两个值中序号小的那个 */ 
int j; 
*s1=min1(t,i); 
*s2=min1(t,i); 
if(*s1>*s2) 
{ 
j=*s1; 
*s1=*s2; 
*s2=j; 
} 
} 

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC, LeafLinkList L) /* 算法6.12 */ 
{ /* w存放n个字符的权值(权值均需大于0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC*/ 
int m,i,s1,s2,start; 
int n=L.len; 
unsigned c,f; 
LeafLink ptr; 
HuffmanTree p; 
char *cd; 
if(n<=1) 
return; 
m=2*n-1; 
printf("表长为%d\t哈夫曼树含节点数为%d\n",n,m); 
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /* 0号单元未用 */ 
ptr=L.head->next; 
for(p=HT+1,i=1;i<=n;++i,++p,ptr=ptr->next) 
{ 
(*p).leaf=ptr->leaf; 
printf("%d\t",(*p).leaf); 
(*p).weight=ptr->weight; 
printf("%d\n",(*p).weight); 
(*p).parent=0; 
(*p).lchild=0; 
(*p).rchild=0; 
} 
for(;i<=m;++i,++p) 
{ 
(*p).parent=0; 
(*p).leaf=0; 
} 
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=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*)); 
/* 分配n个字符编码的头指针向量([0]不用) */ 
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)); 
/* 为第i个字符编码分配空间 */ 
strcpy(HC[i],&cd[start]); /* 从cd复制编码(串)到HC */ 
} 
free(cd); /* 释放工作空间 */ 
for(i=1;i<=n;i++) 
{ 
printf("%c编码为%s:\n",HT[i].leaf,HC[i]); 
} 
} 


void InitLeafList(LeafLinkList &L) 
{ 
L.head=(LeafLink)malloc(sizeof(LeafLink)); 
L.head->next=NULL; 
L.len=0; 
} 
void PrintList(LeafLinkList L) 
{ 
LeafLink p; 
p=L.head->next; 
printf("打印链表\n"); 
printf("表长为%d\n",L.len); 
while(p!=NULL) 
{ 
printf("%c or %d,%u\t",p->leaf,p->leaf,p->weight); 
printf("打印一个节点\n"); 
p=p->next; 
} 
printf("打印结束\n"); 
printf("\n"); 
} 

void EnLeafList(LeafLinkList &L,char ch) 
{ 
LeafLink p,pre,temp; 
int flag=0; 
pre=p=L.head; 
printf("%d即为%c******\n\n",ch,ch); 
if(p->next==NULL) //p->next=NULL则为第一次插入操作 
{ 
printf("第一次插入\n"); 
temp=(LeafLink)malloc(sizeof(LeafNode)); 
temp->leaf=ch; 
temp->weight=1; 
temp->next=NULL; 
p->next=temp; 
L.len++; 
} 

else 
{ 


p=p->next; 
while(p!=NULL) 
{ 

if(ch==p->leaf) 
{ 
p->weight++; 
printf("加权\n"); 
p=NULL; 
flag=1; 
} //权重加一 
else if(ch<p->leaf) //插入 
{ 
printf("插入A\n"); 
temp=(LeafLink)malloc(sizeof(LeafNode)); 
temp->leaf=ch; 
temp->weight=1; 
temp->next=p; 
pre->next=temp; 
L.len++; 
flag=1; 
p=NULL; 
} 
else //继续寻找插入点 
{ 
pre=p; 
p=p->next; 
} 
} 

if(p==NULL&&flag!=1) //若p=NULL则插到链尾 
{ 
printf("插入B\n"); 
temp=(LeafLink)malloc(sizeof(LeafNode)); 
temp->leaf=ch; 
temp->weight=1; 
temp->next=NULL; 
pre->next=temp; 
L.len++; 
} 
} 

} 
void EnCoding() 
{ 
FILE *fp,*fr,*fc; 
HuffmanTree HT; 
HuffmanCode HC; 
int i,n; 
LeafLinkList L; 
InitLeafList(L); 
char filename[15]; 
char ch; 
printf("请输入文件名:\n "); 
scanf("%s",filename); 
if( !(fp=fopen(filename,"r")) ) 
{ 
printf("打开文件失败，请输入正确的文件名!! "); 
exit(0); 
} 
ch=getchar(); //接收执行scanf语句时最后输入的回车符 
printf("文件已经打开\n"); 
while(!feof(fp)) 
{ 

ch=fgetc(fp); 
if(ch==-1) 
{ 
printf("结束统计\n"); 
} 
else 
{ 
EnLeafList(L,ch); 
} 
} 
PrintList(L); 
HuffmanCoding(HT,HC, L); 
n=L.len; 
for(i=1;i<=n;i++) 
{ 
puts(HC[i]); 
} 
char TreeName[15]; 
printf("把哈夫曼树存入文件，请输入文件名:\n "); 
scanf("%s",TreeName); 
if( !(fr=fopen(TreeName,"wb")) ) 
{ 
printf("打开文件失败，请输入正确的文件名!! "); 
exit(0); 
} 
ch=getchar(); //接收执行scanf语句时最后输入的回车符 
printf("文件已经打开\n"); 
//把哈夫曼树存入文件 
printf("%d\n",n); 
printf("把树的长度先存入\n"); 
putw(n,fr); //把树的长度先存入 
for(i=1;i<=2*n-1;i++) 
if(fwrite(&HT[i],sizeof(struct HTNode),1,fr)!=1) 
printf("文件写入出错\n"); 
fclose(fr); 

printf("打印原来的树\n"); 
for(i=1;i<=2*n-1;i++) 
printf("%c %u %u %u %u\n",HT[i].leaf ,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild ); 
fclose(fr); 

printf("把编码结果存入文件，请输入文件名:\n "); 
char CodeFileName[15]; 
scanf("%s",CodeFileName); 
if( !(fc=fopen(CodeFileName,"wb")) ) 
{ 
printf("打开文件失败，请输入正确的文件名!! "); 
exit(0); 
} 
ch=getchar(); //接收执行scanf语句时最后输入的回车符 

printf("待编码的文件位置指针重新指向开始位置\n"); 
printf("对待编码文件进行编码，编码同步显示，并将结果存入指定的文件\n"); 
rewind(fp); 
while(!feof(fp)) 
{ 

ch=fgetc(fp); 
printf("%c\n",ch); 
if(ch==-1) 
{ 
printf("结束编码\n"); 
} 
else 
{ 
for(int tap=0,i=1;tap==0&&i<=n;) //查找，该叶子对应的编码串 
{ 
if(ch==HT[i].leaf) //找到，打印出对应的编码，并存入文件 
{ 
printf("%s\n",HC[i]); 
fputs(HC[i],fc); //将编码字符串存入文件 

tap=1; 
} 
else 
{ 
i++; 
} 
} 
} 
} 
fclose(fp); //关闭文件 
fclose(fc); //关闭文件 
} 
int decode(FILE *fc,HuffmanTree HT,int n) 
{ 
while(!feof(fc)) 
{ 
char ch=fgetc(fc); 
if(ch=='0') 
{ 
n=HT[n].lchild; 
if(HT[n].leaf!=0) 
{ 
printf("%c",HT[n].leaf); 
return OK; 
} 
else 
{ 
decode(fc,HT,n); 
return OK; 
} 
} 
else if(ch=='1') 
{ 

n=HT[n].rchild; 
if(HT[n].leaf!=0) 
{ 
printf("%c",HT[n].leaf); 
return OK; 
} 
else 
{ 
decode(fc,HT,n); 
return OK; 
} 
} 
else return OK; 
} 
return ERROR; 
} 


void Decoding() //解码文件，并将结果显示出来 
{ 
FILE *fc,*fr; 
char CodeFileName[15],ch,TreeName[15]; 
int i; 
printf("解码文件，请输入文件名(如*.dat):\n "); 
scanf("%s",CodeFileName); 
if( !(fc=fopen(CodeFileName,"r")) ) 
{ 
printf("打开文件失败，请输入正确的文件名!! "); 
exit(0); 
} 
ch=getchar(); //接收执行scanf语句时最后输入的回车符 
printf("存放编码结果文件已经打开\n"); 

//读入哈夫曼树 

HuffmanTree HT; 
printf("取出对应的哈夫曼树文件，请输入文件名,\n"); 
scanf("%s",TreeName); 
if( !(fr=fopen(TreeName,"rb")) ) //打开存放哈夫曼树的文件 
{ 
printf("打开文件失败，请输入正确的文件名!! "); 
exit(0); 
} 
int n=getw(fr); //将叶子数目取出 
printf("叶子数目%d\n",n); 
HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode)); /* 然后分配空间，0号单元未用 */ 

for(i=1;i<=2*n-1;i++) 
if(fread(&HT[i],sizeof(struct HTNode),1,fr)!=1) 
printf("文件读出出错\n"); 
int length=2*n-1; //总长度 
printf("总结点数目为：%d\n",n); 
printf("该文件译码后得到的源文件为：\n"); 
printf("**************************************\n"); 
while(!feof(fc)) 
{ 
decode(fc,HT,length); 
} 
printf("**************************************\n"); 
printf("\n\n"); 
} 

int PreOrderPrint(HuffmanTree HT,int n,int count) 
{ 
if(HT[n].lchild) 
{ 
for(int i=0;i<count;i++) 
printf(" "); 
printf("%u\n",HT[n].weight); 
if( PreOrderPrint(HT,HT[n].lchild, ++count) ) 
if (PreOrderPrint(HT,HT[n].rchild, ++count)) 
return OK; 
return ERROR; 
} 
else return OK; 
} 
void PrintTree() 
{ 
//读入哈夫曼树 
FILE *fr; 
char TreeName[100]; 
HuffmanTree HT; 
printf("取出对应的哈夫曼树文件(如*.dat)，请输入文件名,\n"); 
scanf("%s",TreeName); 
if( !(fr=fopen(TreeName,"rb")) ) //打开存放哈夫曼树的文件 
{ 
printf("打开文件失败，请输入正确的文件名!! "); 
exit(0); 
} 
int n=getw(fr); //将叶子数目取出 
printf("含叶子数%d\n",n); 
HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode)); /* 然后分配空间，0号单元未用 */ 

for(int i=1;i<=2*n-1;i++) 
if(fread(&HT[i],sizeof(struct HTNode),1,fr)!=1) 
printf("文件读出出错\n"); 
int count=0; 
n=2*n-1; 
printf("总结点数目为；%d\n",n); 
printf("哈夫曼树的存储形式为：\n"); 
for(i=1;i<=n;i++) 
{ 
printf("%c,%u,%u,%u,%u\n",HT[i].leaf,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild); 
} 
printf("哈夫曼树的凹入表形式为：\n"); 
PreOrderPrint(HT,n,count); 
} 
void PrintCodeFile() 
{ 
FILE *fc; 
printf("打印编码后的文件，请输入文件名(如*.dat):\n "); 
char CodeFileName[15]; 
scanf("%s",CodeFileName); 

if( !(fc=fopen(CodeFileName,"r")) ) 
{ 
printf("打开文件失败，请输入正确的文件名!! "); 
exit(0); 
} 

char ch=getchar(); //接收执行scanf语句时最后输入的回车符 
printf("打印编码后的文件，打印方法一\n"); 
int flag=1; 
while(!feof(fc)) 
{ 

ch=fgetc(fc); 
if(ch==-1) 
{ 
printf("结束打印\n"); 
} 
else 
{ 
printf("%c",ch); 
if(flag<=49) 
flag++; 
else 
{ 
flag=1; 
printf("\n"); 
} 
} 
} 
printf("打印编码后的文件，打印方法二\n"); 
rewind(fc); 
char str[50]; 
while(!feof(fc)) 
{ 
fgets(str,51,fc); 
puts(str); 
} 
fclose(fc); //关闭文件 
} 

void Initialization() //系统初始化 
{ 
printf("**************************************\n"); 
printf("*编码文件请输入e\n*译码文件请输入d\n*打印编码后的文件请输入p\n*建立哈夫曼树请输入t\n*结束请输入q \n"); 
printf("**************************************\n"); 
printf("\n\n\t\t字符:\n\n\n"); 
printf("**************************************\n"); 
printf("* 输入一个字符:e,d,p,t or q *\n"); 
printf("**************************************\n"); 
} 

int read(char cmd) 
{ 
int i,flag=0; 
char choice[10]={'e','E','d','D','p','P','T','t','Q','q'}; 
for(i=0;i<10;i++) 
{ 
if(cmd==choice[i]) flag++; 
} 
if(flag==1) return FALSE; 
else return TRUE; 
} 
void ReadCommand(char &cmd) // 读入操作命令符 
{ 
do 
{ 
cmd=getchar(); 
} 
while(read(cmd)); 
} 
void Interpret(char cmd) //解释执行操作命令 
{ 
switch(cmd) 
{ 
case 'e':case'E': 
EnCoding(); 
Initialization(); 
break; 
case 'd':case'D': 
Decoding(); 
Initialization(); 
break; 
case 'p':case'P': 
PrintCodeFile(); 
Initialization(); 
break; 
case't':case'T': 
PrintTree(); // Print(); 
Initialization(); 
break; 
case 'q': case'Q': exit(0); 
break; 
default: printf("Error\n");break; 
} 
} 
void main() //用户驱式 
{ 
char cmd; 
Initialization(); //初始化 
do 
{ 
ReadCommand(cmd); //读入一个操作命令符 
Interpret(cmd); //解释执行操作命令符 
} 
while(cmd!='q'&&cmd!='Q'); 
EnCoding(); 
Decoding(); 

}