hafuma.cpp

关于数据结构的各章节的c原代码实现

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

#include "stdafx.h"
#include <stdio.h>
typedef struct 
{
 int weight;
 int flag;
 int parent;
 int lchild;
 int rchild;
}hnodetype;
typedef struct
{
	int bit[100];
	int start;
}hcodetype;
void haffman()
{
	hnodetype haffnode[100];
	hcodetype haffcode[100],cd;
	int i,j,m1,m2,x1,x2,n,c,p;
	scanf("%d",&n);
	for (i=0;i<2*n-1;i++)
	{
		haffnode[i].weight=0;
		haffnode[i].parent=0;
		haffnode[i].flag=0;
		haffnode[i].lchild=-1;
		haffnode[i].rchild=-1;
	}
	for(i=0;i<n;i++)scanf("%d",&haffnode[i].weight);
	for (i=0;i<n-1;i++)
	{
		m1=m2=100;
		x1=x2=0;
		for (j=0;j<n+i;j++)
		{
			if(haffnode[j].weight<m1&&haffnode[j].flag==0)
			{
				m2=m1;
				x2=x1;
				m1=haffnode[j].weight;
				x1=j;
			}
			else if (haffnode[j].weight<m2&&haffnode[j].flag==0)
			{
                m2=haffnode[j].weight;
				x2=j;
			}
				
		}
		haffnode[x1].parent=n+i;
		haffnode[x2].parent=n+i;
        haffnode[x1].flag=1;
		haffnode[x2].flag=1;
		haffnode[n+i].weight=haffnode[x1].weight+haffnode[x2].weight;
		haffnode[n+i].lchild=x1;
		haffnode[n+i].rchild=x2;
	}
	for (i=0;i<n;i++)
	{
		cd.start=n-1;
		c=i;
		p=haffnode[c].parent;
		while (p!=NULL)
		{
			if (haffnode[p].lchild==c)cd.bit[cd.start]=0;
			 else cd.bit[cd.start]=1;
			 cd.start--;
			 c=p;
             p=haffnode[c].parent;
		}
		for(j=cd.start+1;j<n;j++)haffcode[i].bit[j]=cd.bit[j];
		haffcode[i].start=cd.start;
	}
for (i=0;i<n;i++)
{
	for(j=haffcode[i].start+1;j<n;j++)
		printf("%d",haffcode[i].bit[j]);
	printf("\n");
}
}

int main(int argc, char* argv[])
{
	haffman();
	return 0;
}