huffman.c

《数据结构》教材源程序,可以让你轻松的根据教材学习数据结构

/***********************************************/
/*                Huffman算法                  */
/*   文件名：huffman.c  函数名：creathuffman() */
/***********************************************/
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
    int data;     /*权值*/
    struct node* lchild,*rchild,*next;
} hufnode;
typedef hufnode* linkhuf;

linkhuf insert(linkhuf root,linkhuf s)
   { linkhuf p1,p2;   /* 将结点s插入到有序链表root中,并保持链表的有序性*/
     if (root==NULL) root=s;
     else
      {       p1=NULL;
              p2=root;
	while(p2 && p2->data<s->data)  /*查找插入位置*/
               {   p1=p2;
                   p2=p2->next;
               }
        s->next=p2;
	if (p1==NULL) root=s; else p1->next=s;
      }
    return root;
  }
  
/*-------根据有序链表root建立huffman树-------*/
void creathuffman(linkhuf * root)
{ linkhuf s,rl,rr;       
  while (*root && (*root)->next)
   { rl=*root;
     rr=(*root)->next;
     *root=rr->next;
     s=(linkhuf)malloc(sizeof(hufnode));    /*生成新结点*/
     s->next=NULL;
     s->data=rl->data+rr->data;
     s->lchild=rl;
     s->rchild=rr;
     rl->next=rr->next=NULL;
     *root=insert(*root,s);                 /*将新结点插入到有序表root中*/
    }
}

void inorder(linkhuf t)  /*中序遍历二叉树*/
  { if (t) {inorder(t->lchild);
	      printf("%4d",t->data);
              inorder(t->rchild);
             }
   }
void preorder(linkhuf t) /*前序遍历二叉树*/
  { if (t) {  printf("%4d",t->data);
              preorder(t->lchild);
	      preorder(t->rchild);
             }

   }
main()
{ linkhuf root=NULL,s;
  int x;
  printf("请输入外部结点的概率值（以0结束）：\n");
  scanf("%d",&x);
  while (x!=0)              /* 建立外部结点概率值组成的有序链表*/
   {  s=(linkhuf)malloc(sizeof(hufnode));
      s->data=x;
      s->next=NULL;
      s->lchild=s->rchild=NULL;
      root=insert(root,s);
      scanf("%d",&x);
   }
  printf("The linkhuf of root is:\n");
  creathuffman(&root);
  printf("\nHuffman的前序序列是：");
  preorder(root);
  printf("\nHuffman的中序序列是：");
  inorder(root);
}