标题: C语言经典算法之哈夫曼算法 [打印本页]

---

作者: 苹果也疯狂    时间: 2014-5-22 09:47     标题: C语言经典算法之哈夫曼算法

#include<stdio.h>
#include<malloc.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
/*声明两种链表结构----start*/
struct node_a{  /*链表1-----作用：用来统计文件中字符的个数和种类（通过count）*/
chardata;
intcount;
struct node_a *next;
};
typedef struct node_a node,*list;
list head=NULL;
struct nodeb{  /*链表2-----作用：用来建立用相应的编码代替字符的新文件*/
chardata;
struct nodeb *next;
};
typedef struct nodeb node_b,*list_b;  /*jiang bianma xieru wenjian*/
list_b head_b=NULL;
/*声明两种链表结构----end*/
/*哈夫曼算法种相关的3种结构的声明-----start*/
struct forest{   
float weight;
introot;
};
struct alphabet{
charsymbol;
float probability;
intleaf;
char*bianma;      
};
struct tree{
intlchild;
intrchild;
intparent;
};
typedef struct tree *tree_ptr,tree_node;
typedef struct forest*forest_ptr,forest_node;
typedef struct alphabet*alphabet_ptr,alphabet_node;
tree_ptr tree1;
forest_ptr forest1;
alphabet_ptr alphabet1;
int lasttree,lastnode;
int least,second;
/*哈夫曼算法种相关的3种结构的声明-----end*/
/**************stack difinationstart****************/
struct stacknode{
char *bian_ma;
struct stacknode *next;
  };
typedef struct stacknode stack_node;
typedef stack_node *link;
link top=NULL;
void push(char *item){
linkp;
if(top!=NULL){
  p=(link)malloc(sizeof(stack_node));
  if(p==NULL){
   printf("Memory allocation error!");
   return;
    }
  p->bian_ma=item;
  p->next=top;
  top=p;
  }
else{
   top=(link)malloc(sizeof(stack_node));
   if(!top){
    printf("Memory allocation error!");
    return;
    }
   top->bian_ma=item;
   top->next=NULL;
  }
}
void pop(void){
link p;
p=top;
top=top->next;
free(p);
}
void makenull(void){
while(top!=NULL)
  pop();
}


int empty(){
if(top==NULL)
return 1;
else
return 0;
  }
char* tops(void){
  return (top->bian_ma);
}
void display_stack(link s){ /*显示栈重的内容*/
linkptr;
ptr=s;
while(ptr!=NULL){
printf("%s",ptr->bian_ma);
ptr=ptr->next;
  }
}
/***************************stack__difination isend************************/
void display(list h){ /*显示链表1*/
list ptr;
int i=1;
ptr=h->next;
while(ptr!=NULL){
printf("%d,%c,%d\n",i,ptr->data,ptr->count);
i++;
ptr=ptr->next;
}
}
void display_b(list_b h){  /*显示链表2*/
list_b ptr;
int i=1;
ptr=h->next;
while(ptr!=NULL){
printf("%d,%c\n",i,ptr->data);
i++;
ptr=ptr->next;
}
}
void insert(char item){  /*用于插入元素以建立链表1*/
listtemp,ptr;
intflag;
ptr=head->next;
if(ptr==NULL){
head->next=(list)malloc(sizeof(node));
  head->next->data=item;
  head->next->count=1;
  head->next->next=NULL;
   }
else{
   while(ptr!=NULL){
    if(ptr->data==item){
    ptr->count=ptr->count+1;
    flag=1;
    }
   ptr=ptr->next;
       }
  ptr=head;
  if(flag==1)
    return;
  else{
    temp=ptr->next;
    ptr->next=(list)malloc(sizeof(node));
    ptr->next->data=item;
    ptr->next->count=1;
    ptr->next->next=temp;
   }
}
}
void insert_b(char item){  /*插入元素以建立链表2*/
list_b ptr_b, temp_b;
ptr_b=head_b;
if(ptr_b->next==NULL){
   head_b->next=(list_b)malloc(sizeof(node_b));
   head_b->next->data=item;
   head_b->next->next=NULL;
    }
else{
   while(ptr_b->next!=NULL){
ptr_b=ptr_b->next;
  }
   ptr_b->next=(list_b)malloc(sizeof(node_b));
   ptr_b->next->data=item;
   ptr_b->next->next=NULL;
    }
}
void search(void){ /*搜索文件并将文件中的数据分别存入作用不同的链表中*/
FILE*fp;
listptr;
charch;
if((fp=fopen("test.txt","r"))==NULL)
  printf("Reading error!\n");
while(!feof(fp)){
  ch=getc(fp);
  if(ferror(fp)){
    printf("error!\n");
    break;
    }
  if(ch==EOF)
   break;
  insert(ch);   /*插入元素进链表1*/
  insert_b(ch); /*插入元素进链表2*/
   }
printf("\n");
fclose(fp);
}
void display_struct(int n){ /*显示哈夫曼算法中的3个结构树组 */
int i=0;
printf("\n\n=======================================\n\n");
printf("FOREST_STRUCT_ARRY:\n\n\n");
for(i=0;i<=n;i++){
printf("%f,%d\n",forest1.weight,forest1.root);
}
getch();
printf("\n\nALPHABET_STRUCT_ARRY:\n\n\n");
for(i=0;i<=n;i++){
printf("%f,%d,%c\n",alphabet1.probability,alphabet1.leaf,alphabet1.symbol);
}
getch();
printf("\n\nTREE_STRUCT_ARRY:\n\n\n");
for(i=0;i<=2*n-1;i++)
printf("%d,%d,%d\n",tree1.lchild,tree1.rchild,tree1.parent);
printf("\n\n======================================\n\n");
getch();
}
int init_struct(void){  /*初始化哈夫曼算法中3种结构数组*/
list ptr;
float count=.0;
int i=1,n=0;
ptr=head->next;
while(ptr!=NULL){
count=ptr->count+count;
n++;
ptr=ptr->next;
}
ptr=head->next;
forest1=(forest_ptr)malloc(sizeof(forest_node)*n+sizeof(forest_node));
alphabet1=(alphabet_ptr)malloc(sizeof(alphabet_node)*n+sizeof(alphabet_node));
tree1=(tree_ptr)malloc(sizeof(tree_node)*n*2-sizeof(tree_node));
forest1[0].weight=alphabet1[0].probability=0.0;
forest1[0].root=alphabet1[0].leaf=0;
alphabet1[0].symbol='0';
while(ptr!=NULL){
forest1.weight=alphabet1.probability=ptr->count/count;
forest1.root=alphabet1.leaf=i;
alphabet1.symbol=ptr->data;
i++;
ptr=ptr->next;
}
for(i=0;i<=2*n-1;i++){
tree1.lchild=0;
tree1.rchild=0;
tree1.parent=0;
}
return n;
}
void creat(void){      /*创建正文文件test.txt*/
FILE*fp,*out;
charch;
if((fp=fopen("test.txt","r++"))==NULL)
  printf("Creat error!\n");
printf("Input the data:\n");
ch=getch();
putch(ch);
while(ch!='#'){
  putc(ch,fp);
  ch=getch();
  putch(ch);
   }
  fclose(fp);
}
void creat_bianma(int number){  /*根据哈夫曼算法建立文件中各种字符对应的编码*/
inti,j,n;
intp;
char*bm=malloc(sizeof(char)*number);
for(n=1;n<=number;n++){
   j=i=n;
   makenull();
   p=tree1.parent;
   while(tree1[p].parent!=0){
if(tree1[p].lchild==i)
    push("0");
else
    push("1");
i=p;
p=tree1[p].parent;
     }
   if(tree1[p].lchild==i)
push("0");
   else
push("1");
   strcpy(bm," "); /*目的：使创建编码文件中的各编码中间存在间隔*/
   while(!empty()){
strcat(bm,tops());
pop();
}
    alphabet1[j].bianma=malloc(sizeof(char)*number);
    strcpy(alphabet1[j].bianma,bm);
    printf("\n%c:%s",alphabet1[j].symbol,alphabet1[j].bianma); /*打印出相应的编码*/
    getch();
    }
}
void write_new_file(int number){ /*根据相应的编码重新建立编码文件*/
FILE *fp;
list_b ptr;
  inti;
char *ch=malloc(sizeof(char)*number);
ptr=head_b->next;
if((fp=fopen("bianma.txt","w"))==NULL)
   printf("Write in a new file error!");
else{
   while(ptr!=NULL){
     for(i=1;i<=number;i++){
if(ptr->data==alphabet1.symbol){
  strcpy(ch,alphabet1.bianma);
  fputs(ch,fp);
   }
}
     ptr=ptr->next;
    }
  }
fclose(fp);
}
void main(void){
int i,num;
char ch;
void huffman(void);
void lightones();
head=(list)malloc(sizeof(node));
head->next=NULL;
head->data='\0';
head->count=0;
head_b=(list_b)malloc(sizeof(node_b));
head_b->data='\0';
head_b->next=NULL;
do{
system("cls");
creat();
search();
printf("\nlianbiao1:\n");
display(head);/*显示链表1*/
getch();
printf("\nlianbiao2:\n");
display_b(head_b);
getch();
num=init_struct();
printf("\n");
printf("The 3 init_struct of huffman?\n");
display_struct(num);/*显示初始化的哈夫曼书的相关3个结构数组*/
lastnode=num;
lasttree=num;
huffman();
printf("Now the 3 struct through huffman shuanfa\n");
display_struct(num);/*显示哈夫曼树中相关的3种结构（经过哈夫曼算法处理）*/
printf("\nThe bian_ma is:\n");
creat_bianma(num);
write_new_file(num);
printf("\nDo you want to re_try(y/n)?");
ch=getchar();
}while(ch=='y');
  }
/*哈夫曼算法-----defination_start*/
void lightones(void){
inti;
if(forest1[1].weight<=forest1[2].weight){
   least=1;
   second=2;
    }
else{
   least=2;
   second=1;
    }
for(i=3;i<=lasttree;i++)
  if(forest1.weight<forest1[least].weight){
second=least;
least=i;
}
  else
if(forest1.weight<forest1[second].weight)
second=i;
}


int creat_tree(int lefttree,int righttree){
lastnode=lastnode+1;
  tree1[lastnode].lchild=forest1[lefttree].root;
tree1[lastnode].rchild=forest1[righttree].root;
tree1[lastnode].parent=0;
tree1[forest1[lefttree].root].parent=lastnode;
tree1[forest1[righttree].root].parent=lastnode;
return(lastnode);
}
void huffman(void){
  inti,j;
  intnewroot;
while(lasttree>1){
   lightones();
   i=least;
   j=second;
   newroot=creat_tree(i,j);
   forest1.weight=forest1.weight+forest1[j].weight;
   forest1.root=newroot;
   forest1[j]=forest1[lasttree];
   lasttree=lasttree-1;
    }
}

---

欢迎光临 电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/)

Powered by Discuz! 7.0.0