| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
Reworld,下班在家制作游戏,1500万奖金等你拿千里之行 始于足下
共有 861 人关注过本帖
标题:霍夫曼树问题,求解答
只看楼主 加入收藏
Insistanttea
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2013-10-22
结帖率:0
  已结贴   问题点数:20  回复次数:3   
霍夫曼树问题,求解答
#include "stdio.h"
#include "stdlib.h"



typedef struct Node
{   char data;
    int w;
    struct Node *lchild,*rchild,*parent;
}Node;

int n;
Node *p,*q;

int a[1000],top,base=0;

void init()
{top=base=0;
}

int empty( )
{if (top==base)
  return 1;
 else
  return 0;
}

int full()
{ if(top==1000)
    return 1;
  else
   return 0;
 }

 void push(int x)
 { if(!full())
     {a[top]=x;
      top++;
     }
 }

 void pop()
 { if(!empty())
        top--;
 }

 int get()
 { if(!empty())
    return a[top-1];
   else
    return -1;
 }


void input()  //输入N个结点
{int i;
 
 printf("请输入需要编码的结点的个数:");
 scanf("%d",&n);
 fflush(stdin);
 p=(Node*)malloc((2*n)*sizeof(Node)); //p+0不要


for(i=1;i<=n;i++)//构建待编码的N个零散结点
{ printf("请输入第%d个需要编码的结点的字符和权重,以逗号隔开:",i);
    scanf("%c,%d",&(p+i)->data,&(p+i)->w);
    fflush(stdin);
  (p+i)->rchild=(p+i)->lchild=(p+i)->parent=NULL;
  
}           

 for(i=n+1;i<=n*2-1;i++)//构建树需要补充的N-1个结点
 {   
      (p+i)->data=' ';
      (p+i)->w=1000;
      (p+i)->rchild=(p+i)->lchild=(p+i)->parent=NULL;
 }   

}

int minw()//求最小的权的结点
{
    int i,f=0;
    int m=10000;
 
    for(i=1;i<=n*2-1;i++)
 {
     if((p+i)->parent==NULL && (p+i)->w<m)
         
     { m=(p+i)->w;
       f=i;   
     }
 }
 
return f;
}

void createtree()  //创建赫夫曼树
{int k,f1=0,f2=0,j;
 k=1;
 while(k<=n-1)
 {  j=n+k;
    f1=minw();
   (p+f1)->parent=(p+j);
  f2=minw();
  (p+f2)->parent=(p+j);
 
  (p+j)->w=(p+f1)->w+(p+f2)->w;
  (p+j)->lchild=(p+f1);
  (p+j)->rchild=(p+f2);
  
    k++;
  }
}



void output()  //输出编码
{
    int i;
   
   
    for(i=1;i<=n;i++)
    {  
        printf("%c %d:",(p+i)->data,(p+i)->w);
        q=(p+i);

        while(q->parent!=NULL)
        {
            if (q->parent->lchild==q)
                push(0);
            else
                push(1);
            q=q->parent;
        }


        while(!empty())
        {
            printf("%d",get());
            pop();
        }
        printf("\n");
    }
}

main()
{init();
 input();
createtree();
output();

请问这段代码是什么意思:
int a[1000],top,base=0;

void init()
{top=base=0;
}

int empty( )
{if (top==base)
  return 1;
 else
  return 0;
}
还有这句: (p+i)->data=' '中的空格什么意思?;


int minw()//求最小的权的结点
{
    int i,f=0;
    int m=10000;
 
    for(i=1;i<=n*2-1;i++)
 {
     if((p+i)->parent==NULL && (p+i)->w<m)
         
     { m=(p+i)->w;
       f=i;   
     }这没看懂,m为什么要设为10000?拜托大神帮我解答下吧,谢谢
搜索更多相关主题的帖子: include return parent 霍夫曼 
2014-04-22 22:12
鸥翔鱼游
Rank: 5Rank: 5
等 级:职业侠客
帖 子:182
专家分:323
注 册:2014-4-19
  得分:20 
看帖是学习,回帖更是礼貌!!!
2014-04-26 16:00
Insistanttea
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2013-10-22
  得分:0 
回复 2 楼 鸥翔鱼游
帮帮我吧,大师
2014-05-19 22:09
wu2782641803
Rank: 2
等 级:论坛游民
帖 子:65
专家分:46
注 册:2013-10-28
  得分:0 
#include<stdio.h>
#include<malloc.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>

/*声明两种链表结构----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*/
   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[i].weight,forest1[i].root);
}
getch();
printf("\n\nALPHABET_STRUCT_ARRY :\n\n\n");
for(i=0;i<=n;i++){
 printf("%f,%d,%c\n",alphabet1[i].probability,alphabet1[i].leaf,alphabet1[i].symbol);
}
getch();
printf("\n\nTREE_STRUCT_ARRY :\n\n\n");
for(i=0;i<=2*n-1;i++)
printf("%d,%d,%d\n",tree1[i].lchild,tree1[i].rchild,tree1[i].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[i].weight=alphabet1[i].probability=ptr->count/count;
 forest1[i].root=alphabet1[i].leaf=i;
 alphabet1[i].symbol=ptr->data;
 i++;
 ptr=ptr->next;
}
for(i=0;i<=2*n-1;i++){
 tree1[i].lchild=0;
 tree1[i].rchild=0;
 tree1[i].parent=0;
 }
return n;
}

void creat(void){      /*创建正文文件test.txt*/
 FILE *fp,*out;
 char ch;
 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){  /*根据哈夫曼算法建立文件中各种字符对应的编码*/
 int i,j,n;
 int p;
 char *bm=malloc(sizeof(char)*number);
 for(n=1;n<=number;n++){
    j=i=n;
    makenull();
    p=tree1[i].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;
  int i;
  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[i].symbol){
   strcpy(ch,alphabet1[i].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){
 int i;
 if(forest1[1].weight<=forest1[2].weight){
    least=1;
    second=2;
    }
 else{
    least=2;
    second=1;
    }
 for(i=3;i<=lasttree;i++)
   if(forest1[i].weight<forest1[least].weight){
second=least;
least=i;
}
   else
if(forest1[i].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){
  int i,j;
  int newroot;
  while(lasttree>1){
    lightones();
    i=least;
    j=second;
    newroot=creat_tree(i,j);
    forest1[i].weight=forest1[i].weight+forest1[j].weight;
    forest1[i].root=newroot;
    forest1[j]=forest1[lasttree];
    lasttree=lasttree-1;
    }
} 希望对你有帮助!!
2014-05-21 15:21
快速回复:霍夫曼树问题,求解答
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.066316 second(s), 7 queries.
Copyright©2004-2019, BCCN.NET, All Rights Reserved