huffman.cpp

本人所写的huffman编码程序

// huffman.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

typedef struct BitreeNode
{
	int weight;
	struct BitreeNode  *lchild,*rchild;
}BitreeNode,*Bitree;

typedef struct LNode
{
	BitreeNode data;
	LNode *next;
}LNode,*LinkList;

void preorder(Bitree t)
{
	if(t)
	{
		
		printf("%d\n",t->weight);
		preorder(t->lchild);
		preorder(t->rchild);

	}
}
void CreateLinkList(LinkList &L,int n)
{
	LinkList P,Q;
	
	L = new LNode();


	L->data.lchild = NULL;
	L->data.rchild = NULL;
	L->data.weight = 100000;

	L->next = NULL;

	P = L;
	int i=0;
	while(i++<n)
	{
       Q=new LNode();
	 
	   Q->data.lchild = NULL;
	   Q->data.rchild = NULL;
	   printf("输入第%d个节点权重\n",i);
	   scanf("%d",&Q->data.weight);
	   Q->next = NULL;
	   P->next = Q;
	   P=Q;
	}
}

void Display(LinkList L)
{
      LinkList P=L->next;
	  printf("************\n");
	  while(P)
	  {
		  printf("weight:%d\n",P->data.weight);
		  P=P->next;
	  }

}
void AppendTNode(LinkList &L,LinkList p,LinkList q)
{
	LinkList s=L;
	
	while(s->next)
	{
		s = s->next;
	}

	LinkList t=new LNode();
	t->data.lchild = &p->data;
	t->data.rchild = &q->data;
	t->data.weight = p->data.weight+q->data.weight;
	t->next = NULL;
	s->next = t;
	
}
void DeleteTNode(LinkList &L,LinkList p)
{
	LinkList q=L;

	while(q->next != p)
	{
		q = q->next;
	}
	q->next = p->next;
}
void SelectTNode(LinkList &L)
{
	LinkList P =L->next;
    LinkList P1,P2;

	if(P->data.weight <= P->next->data.weight)
	{
		P1 = P;
		P2 = P->next;
	}
	else
	{
		P2 = P;
		P1 = P->next;
	}
	P = P->next->next;
	while(P)
	{
		if(P->data.weight < P1->data.weight)
		{
			LinkList S=P1;
			P1=P;
			P2=S;
		}
		else if(P->data.weight < P2->data.weight)
		{
			P2=P;
		}
        P = P->next;
	}
    
	
	AppendTNode(L,P1,P2);

	DeleteTNode(L,P1);
	
	DeleteTNode(L,P2);
	Display(L);
}

int main(int argc, char* argv[])
{
	LinkList L = NULL;
	int n;
	printf("输入叶子接点个数:");
    scanf("%d",&n);

    CreateLinkList(L,n);  //建立一个叶子接点的链表

	while(n-->=2)         //每两个结点生成一个双亲结点，构建huffman树
	{
		SelectTNode(L);
	}

	preorder(&L->next->data);//先序遍历huffman树
	return 0;
}