常用算法之哈夫曼算法

会计考友 · 发表于 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;3 j# Y+ V' k( ^& L
　　forest1.root=alphabet1.leaf=i;
( c: `) b" V3 l$ l　　alphabet1.symbol=ptr->data;
( C. }. ]" r$ c3 U# b! B7 N　　i++;1 s9 o( E% L" C# J7 l. o( a, |
　　ptr=ptr->next;+ A  e% e" e  k3 X+ C
　　}. r9 X4 s* u  I
　　for(i=0;inext;
/ M* S( l3 T3 ]( c　　if((fp=fopen("bianma.txt","w"))==NULL)9 U# ?) _: m! h
　　printf("Write in a new file error!");
8 o7 \8 ^* H9 x2 @) a3 v　　else{8 c" \3 T) [. R5 t* y( g
　　while(ptr!=NULL){
" b4 r9 p/ K  S1 X: Y0 C3 I# m　　for(i=1;idata==alphabet1.symbol){9 l! Q% o- d  O# i
　　strcpy(ch,alphabet1.bianma);# D# b, {  p" p+ |& `2 l' w
　　fputs(ch,fp);
3 B1 O0 W, m0 j4 d0 Q& l' W5 ?" P　　}
5 z/ Y$ i* L( m* a3 s/ W; H　　}
2 I( e5 ?8 Y: k6 A　　ptr=ptr->next;
; ?0 }1 ?7 z5 Y　　}5 Z" f9 L; k; m: o( t% t% ^) @
　　}- l+ D' Y/ {2 g. x' p
　　fclose(fp);( j) q( f% T- n% l3 K6 C* Q3 x
　　}
+ _" W- R0 e4 u0 Q7 x* W4 f　　void main(void){
7 V6 R0 i! D9 Q1 x/ ^% U　　int i,num;. q7 T  v) p+ d# h8 v, J3 Z
　　char ch;. g8 H9 q6 r& Q5 F1 n0 z
　　void huffman(void);
2 O# \) V- n# v- B- O; _4 l& M1 v2 ~. L　　void lightones();. X. }$ h( T/ O2 T. x! T9 a+ I+ t0 i
　　head=(list)malloc(sizeof(node));. R2 c/ Y1 S/ s+ S! u2 z
　　head->next=NULL;! F6 h, @4 L& d
　　head->data='\0';
7 f: s6 m7 v7 P2 i- u, w9 s6 s　　head->count=0;
% C7 w* `% f* X6 j　　head_b=(list_b)malloc(sizeof(node_b));. P2 t! ^% |' A/ |3 i9 @' T3 A
　　head_b->data='\0';
( `8 A; T8 t3 |　　head_b->next=NULL;+ {# Y3 A2 I' G. P* i- d
　　do{  ]# k: u% z' F$ ?/ X& E5 ]+ o
　　system("cls");$ o8 G) h' ?: x! R5 I- R8 t
　　creat();2 [9 q6 A5 d+ T, A# ?4 X
　　search();
- E" Z2 m$ y! a" f; |/ K6 L8 t0 P　　printf("\nlianbiao1:\n");
. L$ b) F4 t9 R　　display(head);/*显示链表1*/& u" h2 ]/ j* x8 ?$ O! c  [
　　getch();
6 e1 S8 n4 k* q# L% Z8 L　　printf("\nlianbiao2:\n");9 c2 ~6 Y; h4 u  ]2 X- `
　　display_b(head_b);7 ~5 ]3 E0 S, ?
　　getch();
) ~& {* _/ R& o7 m9 l3 j2 n; I　　num=init_struct();
5 f* t4 E* {5 o( e　　printf("\n");: C8 y2 H$ s. @' k% g% D* m
　　printf("The 3 init_struct of huffman?\n");  X( d& d* F# M9 Q
　　display_struct(num);/*显示初始化的哈夫曼书的相关3个结构数组*/& x) d' d- p4 r- Z. R/ T; e
　　lastnode=num;
　　lasttree=num;  F( u4 K  a1 F+ Y
　　huffman();
: L, U; d% }  Y# \　　printf("Now the 3 struct through huffman shuanfa\n");
2 w6 Y: S" B$ [# |4 p8 J　　display_struct(num);/*显示哈夫曼树中相关的3种结构（经过哈夫曼算法处理）*/
0 \2 \. d  q5 a9 k* Z0 W, y1 v5 c' s　　printf("\nThe bian_ma is:\n");
7 e9 Z( P, [4 g0 n( X; v4 C# a　　creat_bianma(num);$ V: P+ F# C( f2 H& S+ Q3 N
　　write_new_file(num);
$ J: R( W2 j5 ^$ n　　printf("\nDo you want to re_try(y/n)?");
) B3 A7 _) @' C2 h+ |　　ch=getchar();; N# Z  `. E3 Q
　　}while(ch=='y');4 S9 d3 z$ y; D1 Z3 E6 N( b
　　}! t$ Q- a! ^( A/ }$ N3 F. X) g/ Y# s
　　/*哈夫曼算法-----defination_start*/
$ q. C0 t( c( K* q4 ]　　void lightones(void){6 }  h- v9 v0 Z5 l
　　int i;
7 ?3 V0 o( e5 x　　if(forest1[1].weight1){8 `& D9 v) X3 \5 Z  {* S
　　lightones();( z1 S6 {; w# D% g' z
　　i=least;
* o& P6 p) W" J" e. q& {/ ]+ P- y0 F& t　　j=second;
  H3 X  y! @. r　　newroot=creat_tree(i,j);# j$ V# E# |7 Y4 C
　　forest1.weight=forest1.weight+forest1[j].weight;4 I& c4 q4 G+ f
　　forest1.root=newroot;
  G1 ^1 E8 l6 t" w* i0 v: |　　forest1[j]=forest1[lasttree];
( a6 k2 g* ?6 m0 ~' a( H- }　　lasttree=lasttree-1;
1 G9 ^/ r2 z! e/ m* }　　}
5 J: G, v) O2 i: r　　}

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

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

常用算法之哈夫曼算法

浏览过的版块