/** * author:gubojun * time:2012-12-11 * name:~ * version:0.1 */#includestdio.h#includestdlib.h#includestring.h/** * Huffman树的结构体 */typedef struct node{ char byte;//记录字符 int weight;//权值 char bit[10];//编码值 struct
/**
* author:gubojun
* time:2012-12-11
* name:~
* version:0.1
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
/**
* Huffman树的结构体
*/
typedef struct node{
char byte;//记录字符
int weight;//权值
char bit[10];//编码值
struct node *lchild,*rchild,*next;
}hufnode,*huflink;
huflink codetree;
//--------------------编码对照表
char codelist[256][10];int nn;
//---------------------------------------------------------------------------------
/**
* name:comp
* author:gubojun
* time:2012-12-11
* in:两个节点的地址
* out:int 大小
* function:qsort比较函数，降序排列结构体数组
*/
int comp(const void *a,const void *b){
return (*(huflink)b).weight-(*(huflink)a).weight;
}
//---------------------------------------------------------------------------------
/**
* 函数功能：将新结点s插入到有序链表root中，并保持链表的有序性
* 函数参数：链表头结点指针root；结点指针s
*/
huflink insert(huflink root,huflink s){
huflink p1,p2;
if(root==NULL)root=s;
else{
p1=NULL;
p2=root;
while(p2 && p2->weight < s->weight){/*查找插入位置*/
p1=p2;
p2=p2->next;
}
s->next=p2;
if(p1==NULL) root=s;
else p1->next=s;
}
return root;
}
//---------------------------------------------------------------------------------
/**
* 函数功能：根据有序链表root建立huffman树
* 函数参数：链表头结点二级指针变量root
*/
void creathuffman(huflink *root){//二阶指针(地址的指针)
huflink s,rl,rr;
while(*root && (*root)->next){//*root表示一个地址
rl=*root;
rr=(*root)->next;
*root=rr->next;
s=(huflink)malloc(sizeof(hufnode));/*生成新结点*/
s->next=NULL;
s->weight=rl->weight+rr->weight;
s->lchild=rl;
s->rchild=rr;
rl->next=rr->next=NULL;
s->bit[0]='\0';
*root=insert(*root,s);/*将新结点插入到有序表root中*/
}
}
void inorder(huflink t){ /*中序遍历二叉树*/
if(t){
inorder(t->lchild);
printf("%4d",t->weight);
inorder(t->rchild);
}
}
void preorder(huflink t){ /*前序遍历二叉树*/
if(t){
printf("%4d",t->weight);
preorder(t->lchild);
preorder(t->rchild);
}
}
void levelorder(huflink t){ //层次遍历二叉树
huflink queue[256]; //存放等待访问的节点队列
int f,r,i=0; //f,r分别为对头、队尾指针
int length;
huflink p;
f=0;r=1;queue[0]=t;
while(f<r){ //队列不为空
p=queue[f];f++;
if(p->lchild==NULL && p->rchild==NULL){
printf("%c",p->byte);
strcpy(codelist[p->byte],p->bit);
printf("(%5s) ",codelist[p->byte]);
}
if(p->lchild){
queue[r]=p->lchild;
strcpy((p->lchild)->bit,p->bit);
strcat((p->lchild)->bit,"0");
r++;
}
if(p->rchild){
queue[r]=p->rchild;
strcpy((p->rchild)->bit,p->bit);
strcat((p->rchild)->bit,"1");
r++;
}
}
}
//---------------------------------------------------------------------------------
/**
* name:compress
* author:gubojun
* time:2012-12-11
* in:char[],char[],输入的文件名，输出的文件名
* out:none
*/
void compress(char infilename[],char outfilename[]){
long flength=0; //记录压缩前文件长度
char ch,bin[10]; //存储读入的字符
huflink s,p;
hufnode list[256];
int i,j,word,count;
FILE *f_in,*f_out;
//----------------------判断文件是否打开成功
if((f_in=fopen(infilename,"r"))==NULL){
printf("Failure to open %s\n",infilename);
return;
}
//----------------------初始化数组
for(i=0;i<256;i++){
list[i].byte=i; //初始化字符
list[i].weight=0; //初始化权重
}
//----------------------统计权值大小
while((ch=fgetc(f_in))!=EOF){
list[ch].weight++; //权值加1
putchar(ch); //输出字符
flength++; //长度加1
}
nn=flength;
//----------------------关闭文件
fclose(f_in);
//----------------------结构体数组快排
qsort(list,256,sizeof(hufnode),comp);
printf("\nlength:%d\n\n",flength); //输入后换行
//----------------------建立Huffman编码树
codetree=(huflink)malloc(sizeof(hufnode));
codetree->byte=list[0].byte;//初始化字符
codetree->weight=list[0].weight;//初始化权重
codetree->lchild=codetree->rchild=codetree->next=NULL;
codetree->bit[0]='\0';
i=0;
while(list[++i].weight){//当权重不为0时
s=(huflink)malloc(sizeof(hufnode));
s->byte=list[i].byte;
s->weight=list[i].weight;
s->lchild=s->rchild=NULL;//左右孩子节点赋值为0
s->bit[0]='\0';
s->next=codetree;
codetree=s;
}
//----------------------打印权值和字符
p=codetree;
while(p){
printf("%d (%c) ",p->weight,p->byte);
p=p->next;
}
printf("\n");
//----------------------建立编码树
creathuffman(&codetree);
//----------------------根据编码树编码
//----------------------层次遍历编码树填写编码对照表
levelorder(codetree);
//----------------------判断文件是否打开成功
if((f_in=fopen(infilename,"r"))==NULL){
printf("Failure to open %s\n",infilename);
return;
}
//----------------------判断文件是否打开成功
if((f_out=fopen(outfilename,"w"))==NULL){
printf("Failure to open %s\n",outfilename);
return;
}
/*//---------------------写入编码1
while((ch=fgetc(f_in))!=EOF){
fprintf(f_out,"%s",codelist[ch]);
}
fclose(f_in);fclose(f_out);*/
printf("\n");
//----------------------写入编码
count=i=word=bin[0]=0;
while((ch=fgetc(f_in))!=EOF){
count+=strlen(codelist[ch]);
j=i;
while(i<count&&i<8){
word=word+((codelist[ch][i-j]-48)<<(7-i));
i++;
}
if(i==8){
if(count==8){
count-=8;i=0;
fprintf(f_out,"%c",word);
printf("%d\n",word);
word=0;
}
else{
count-=8;i=0;
fprintf(f_out,"%c",word);
printf("%d\n",word);
while(i<count&&i<8){
word=(codelist[ch][i]-48)<<(7-i);
i++;
}
}
}
//fprintf(f_out,"%s",codelist[ch]);
}
if(i!=8){
fprintf(f_out,"%c",word);
printf("%d\n",word);
}
fclose(f_in);fclose(f_out);
}
//---------------------------------------------------------------------------------
/**
* name:uncompress
* author:gubojun
* time:2012-12-11
* in:char[],char[],输入的文件名，输出的文件名
* out:none
*/
void uncompress(char infilename[],char outfilename[]){
FILE *f_in,*f_out;
char ch;//存储读入的字符
huflink s,p;
int i;
//-----------------------判断文件是否打开成功
if((f_in=fopen(infilename,"r"))==NULL){
printf("Failure to open %s\n",infilename);
return;
}
//-----------------------判断文件是否打开成功
if((f_out=fopen(outfilename,"w"))==NULL){
printf("Failure to open %s\n",outfilename);
return;
}
/*//------------------------读入编码1
p=codetree;
while((ch=fgetc(f_in))!=EOF){
if(ch=='0'){
p=p->lchild;
}
else{
p=p->rchild;
}
if(p->lchild==NULL && p->rchild==NULL){
fprintf(f_out,"%c",p->byte);
p=codetree;
}
}*/
//------------------------读入编码
printf("\n");
p=codetree;
while(fscanf(f_in,"%c",&ch)!=EOF){
for(i=7;i>=0&&nn;i--){
if(((ch>>i)&1)==0){
p=p->lchild;
}
else{
p=p->rchild;
}
if(p->lchild==NULL && p->rchild==NULL){
printf("%c",p->byte);
fprintf(f_out,"%c",p->byte);
p=codetree;
//nn--;
}
}
}
fclose(f_in);fclose(f_out);
}
/************************************************************************
* name:main
* author:gubojun
* time:2012-12-11
* in:none
* out:none
* function:程序的主函数
************************************************************************/
int main(){
char infilename[256]="in.txt",outfilename[256]="out.txt";
int choice=1;
//printf("please input filename:");
//scanf("%d",infilename);
//printf("please input filename:");
//scanf("%d",outfilename);
printf("1.compress 2uncompress:\n");
//scanf("%d",&choice);
switch(choice){
case 1:compress(infilename,outfilename);
//break;
case 2:uncompress(outfilename,"解压后.txt");
break;
}
}