常用算法之哈夫曼算法

会计考友 · 发表于 2012-7-31 21:48:08

　　#include
　　#include
　　#include
　　#include
　　#include
　　/*声明两种链表结构----start*/
　　struct node_a{ /*链表1-----作用：用来统计文件中字符的个数和种类（通过count）*/
　　char data;
　　int count;
　　struct node_a *next;
　　};
　　typedef struct node_a node,*list;
　　list head=NULL;
　　struct nodeb{ /*链表2-----作用：用来建立用相应的编码代替字符的新文件*/
　　char data;
　　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;
　　int root;
　　};
　　struct alphabet{
　　char symbol;
　　float probability;
　　int leaf;
　　char *bianma;
　　};
　　struct tree{
　　int lchild;
　　int rchild;
　　int parent;
　　};
　　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 difination start****************/
　　struct stacknode{
　　char *bian_ma;
　　struct stacknode *next;
　　};
　　typedef struct stacknode stack_node;
　　typedef stack_node *link;
　　link top=NULL;
　　void push(char *item){
　　link p;
　　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){ /*显示栈重的内容*/
　　link ptr;
　　ptr=s;
　　while(ptr!=NULL){
　　printf("%s",ptr->bian_ma);
　　ptr=ptr->next;
　　}
　　}
　　/***************************stack__difination is end************************/
　　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*/
　　list temp,ptr;
　　int flag;
　　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;
　　list ptr;
　　char ch;
　　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*/

会计考友 · 发表于 2012-7-31 21:48:09

　　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;inext;
　　while(ptr!=NULL){
　　count=ptr->count+count;
　　n++;
　　ptr=ptr->next;
　　}</p>　　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;
, O, P1 Q) s' S0 t" z) Y　　forest1.root=alphabet1.leaf=i;
5 Y* h0 Q+ v& ]% a　　alphabet1.symbol=ptr->data;1 t* K  A" j7 \; }2 E
　　i++;/ m3 U! k+ Y! Y3 y- B  K1 ?
　　ptr=ptr->next;2 p- Y( l. i; `7 h* M$ f$ l
　　}
" g& C; ?4 d3 x5 ]5 Y! S　　for(i=0;inext;
2 d, s4 ~% K8 C& {　　if((fp=fopen("bianma.txt","w"))==NULL)
' w+ {1 d1 v2 o* ~- I5 K+ n. b　　printf("Write in a new file error!");
- b9 @2 s  e3 j: w, w% _　　else{3 U; R9 a- j+ e. `1 J9 c
　　while(ptr!=NULL){- r6 K% j9 \- N8 [
　　for(i=1;idata==alphabet1.symbol){
6 u6 s1 v) [( N# ?& {" t　　strcpy(ch,alphabet1.bianma);. ]) z8 B' o0 p7 s7 ~
　　fputs(ch,fp);
" k, [' Y  N- }: |　　}
3 J' ?; J% z* r3 Z　　}. ?- s: o$ }7 c9 k0 u) L: t: v- E0 m$ ^
　　ptr=ptr->next;  {0 Z: Q3 m6 O$ d
　　}! p3 n* z3 c. O
　　}- p0 v5 o7 I  Z( e
　　fclose(fp);' H  D0 P8 `* ~5 z" Y) |
　　}/ Z9 u8 ~3 n* h2 _* e7 c3 J
　　void main(void){! h! f% E* S# E+ ?9 R( a& b+ Y
　　int i,num;
5 m, q1 p6 M& Q: O: c- x　　char ch;
/ ]$ H! K- y* S8 G4 d# d5 z　　void huffman(void);+ t% G% \6 \, U2 [0 \
　　void lightones();+ F/ ~( @4 z( Y( x5 z; A% u/ D
　　head=(list)malloc(sizeof(node));
2 v. R, ]' Z; l　　head->next=NULL;9 i6 y* {( Q: {% r8 [/ @+ F1 E
　　head->data='\0';3 ^7 r3 a4 ~9 n  B3 q/ d$ q  \
　　head->count=0;
1 L8 S" n" U/ I3 g9 i　　head_b=(list_b)malloc(sizeof(node_b));7 g: f' ?6 T! {5 ^
　　head_b->data='\0';& m9 @/ h* K2 o4 ~+ \
　　head_b->next=NULL;
2 u" J* P: P9 P$ H( i( ?; F: X) K　　do{. L( D; w- O7 w, @
　　system("cls");4 v. f$ g& {) P) d7 _. V( I
　　creat();
( d4 h0 e" J* |& Y- f/ S- S+ L' L　　search();
4 ]( n) t, J2 b  j/ k　　printf("\nlianbiao1:\n");( `3 @5 @7 H& @% P% X, }) a4 D+ n# \
　　display(head);/*显示链表1*/; _6 c1 ?  v; \: [
　　getch();
& R# }2 a( U7 X8 y% k& f　　printf("\nlianbiao2:\n");
. G  J) U# J$ F3 W: Z6 f: U　　display_b(head_b);
& o- P! t2 H+ @$ z3 m　　getch();
' C, w% v0 y& e) Q6 P# X　　num=init_struct();
$ p  }3 B, D* m6 q　　printf("\n");
3 C) h: B! Q! D& @; V! |) Z　　printf("The 3 init_struct of huffman?\n");
+ ~' G8 f. X8 P- G3 K$ r% F' p; l　　display_struct(num);/*显示初始化的哈夫曼书的相关3个结构数组*/
) C% h5 T" c" E( K2 ^7 a8 i) R　　lastnode=num;4 Y* Q' J, I9 L
　　lasttree=num;
7 q/ W( r! o$ i7 A　　huffman();7 R5 A& Y8 v. z0 A; o7 s& L7 B& F
　　printf("Now the 3 struct through huffman shuanfa\n");
+ z" B- U( \" _' E9 Y$ c9 n　　display_struct(num);/*显示哈夫曼树中相关的3种结构（经过哈夫曼算法处理）*/: w4 i5 d* N! }
　　printf("\nThe bian_ma is:\n");6 c5 t9 A9 }& i% q% J$ S
　　creat_bianma(num);
; ?1 x0 U5 c+ F+ O/ q3 t5 J- X: Z　　write_new_file(num);6 ~' s6 y8 x3 p- i# e* X
　　printf("\nDo you want to re_try(y/n)?");
7 z5 x  Q3 I! C5 B' n4 p) ^/ K. c　　ch=getchar();& ?6 `4 c; b5 f- z( [
　　}while(ch=='y');6 T& {& c1 Z, Y+ e3 y- q1 p
　　}
; j, G: j0 _7 \9 j1 O( c" [　　/*哈夫曼算法-----defination_start*/1 z8 k! ?5 `+ b, f! P% ?- f
　　void lightones(void){8 p2 r& V% @% p6 u( Y+ a
　　int i;0 p  c2 d( X% V& b4 m$ m, d
　　if(forest1[1].weight1){
4 w1 J! h- l0 k　　lightones();. ]0 r- a( r/ i  _6 O
　　i=least;0 t  H& h3 j$ P. h, a$ a/ d
　　j=second;
  w# f) B; h4 h2 P　　newroot=creat_tree(i,j);
4 `# i6 n0 F( G　　forest1.weight=forest1.weight+forest1[j].weight;
, r0 F8 ~6 P8 l( S1 v　　forest1.root=newroot;& U+ L; C1 f2 d2 ]7 _- h
　　forest1[j]=forest1[lasttree];. Q' v/ |6 G9 j" r% G
　　lasttree=lasttree-1;5 H/ D4 _  N! |* R/ y2 P
　　}# {; {- m% c" S8 t$ R
　　}

		自动登录	找回密码
密码			立即注册

[C语言] 常用算法之哈夫曼算法

常用算法之哈夫曼算法