vc_哈夫曼树halftree.doc

包括编译程序词法分析器、操作系统进程状态切换演示、VC_哈夫曼树halftree、节点矩阵最短路径guildmap、串基本操作的演示

#include <stdio.h>
#include <conio.h>

struct NodWeight
{
	int data;
	int nod;
	unsigned long weight;
};

struct CodeNod
{
	int data;
	char* code;
};
struct HarfNod
{
	int left;
	int right;
	int parent;
	int data;
};
int GetMinNod(NodWeight* wt)
{
	int i,index;
	unsigned long t;
	for(i=0; i<=255 && wt[i].weight==0; i++);
	if(i==256)
		return -1;
	t=wt[i].weight;
	index = i;
	for(i+=1; i<=255; i++)
	{
		if(wt[i].weight<t && wt[i].weight!=0)
		{
			t=wt[i].weight;
			index = i;
		}
	}
	return index;
}


int RmNod(NodWeight* wt, int nod)
{
	if(nod<0 || nod>255 || wt==NULL)
		return 0;
	wt[nod].data = -1;
	wt[nod].nod = -1;
	wt[nod].weight = 0;
	return 1;
}

int AddNod(NodWeight* wt, const NodWeight nod)
{
	int i;
	for(i=0; i<=255 && wt[i].weight!=0; i++);
	if(i==256)
		return 0;
	wt[i].data = nod.data;
	wt[i].nod = nod.nod;
	wt[i].weight = nod.weight;
	return 1;
}


int StoreHarfTree(HarfNod* ht, unsigned long cl, char* filename)
{
	char* buf;
	FILE* fp;
	int i;
	fp=fopen(filename, "wb");
	if(fp == NULL || ht ==NULL)
		return 0;
	buf = (char*)&cl;
	for(i=0; i<=sizeof(unsigned long)-1; i++)
		fputc(buf[i], fp);
	buf = (char*)ht;
	for(i=0; i<=512*sizeof(HarfNod)-1; i++)
		fputc(buf[i], fp);
	fclose(fp);
	return 1;
}



int DecodeFile(HarfNod* ht, unsigned long cl, char* srcf, char* dstf)
{
	FILE* sfp;
	FILE* dfp;
	int b;
	int p;

	sfp = fopen(srcf, "rb");
	dfp = fopen(dstf, "wb");
	if(dfp==NULL || sfp == NULL)
		return 0;
	b=fgetc(sfp);
	cl--;
	p=0;
	while(!feof(sfp) && cl >=0)
	{
		if(b=='0')
		{
			if(ht[p].left ==-1)
			{
				fputc(ht[p].data, dfp);
				p=0;
			}
			else
			{
				p=ht[p].left;
				b=fgetc(sfp);
				cl--;
			}
		}
		else
		{
			if(ht[p].right == -1)
			{
				fputc(ht[p].data, dfp);
				p=0;
			}
			else
			{
				p=ht[p].right;
				b=fgetc(sfp);
				cl--;
			}
		}
	}
	fclose(sfp);
	fclose(dfp);
	return 1;
}



HarfNod* BuildHarfTree(NodWeight* wt)
{
	int i;
	int m,n;
	int last;
	NodWeight td1,td2,td3;
	HarfNod* tree;
	tree=new HarfNod[512];
	if(wt==NULL || tree==NULL)
		return NULL;
	for(i=0; i<=511; i++)
		tree[i].data = -1;
	last = 1;
	for(i=0; i<=255; i++)
	{
		if(wt[i].weight!=0)
		{
			wt[i].nod = last;
			tree[last].data = wt[i].data;
			tree[last].left = -1;
			tree[last].right = -1;
			tree[last].parent = -1;
			last++;
		}
	}
	td3.data = -1;
	m=GetMinNod(wt);
	while(m!=-1)
	{
		 td1.nod = wt[m].nod;
		 td1.weight = wt[m].weight;
		 RmNod(wt, m);
		 n = GetMinNod(wt);
		 if(n==-1)
		 {
			 tree[0].left = td1.nod;
			 tree[0].right = -1;
			 tree[0].parent = -1;
			 tree[td1.nod].parent = 0;
			 return tree;
		 }
		 td2.nod = wt[n].nod;
		 td2.weight = wt[n].weight;
		 RmNod(wt, n);
		 m = GetMinNod(wt);
		 td3.weight = td1.weight+td2.weight;
		 if(m==-1)
		 {
			 td3.nod = 0;
			 tree[0].left = td1.nod;
			 tree[0].right = td2.nod;
			 tree[0].parent = -1;
			 tree[0].data = -1;
			 tree[td1.nod].parent = 0;
			 tree[td2.nod].parent = 0;
			 return tree;
		 }
		 else
		 {
			 td3.nod = last;
			 tree[last].data = -1;
			 tree[last].left = td1.nod;
			 tree[last].right = td2.nod;
			 tree[last].parent = -1;
			 tree[td1.nod].parent = last;
			 tree[td2.nod].parent = last;
			 last++;
			 AddNod(wt, td3);
		 }
	}
	delete[] tree;
	return NULL;
}


NodWeight* BuildWeightTable(const char* filename)
{
	FILE* fp;
	NodWeight* t;
	int c;
	int i;
	fp=fopen(filename, "rb");
	if(fp==NULL)
		return NULL;
	t=new NodWeight[256];
	if(t==NULL)
		return NULL;
	
	for(i=0; i<=255; i++)
	{
		t[i].nod = -1;
		t[i].data = -1;
		t[i].weight = 0;
	}
	
	c=fgetc(fp);
	if(feof(fp))
		return NULL;
	while(!feof(fp))
	{
		t[c].data = c;
		t[c].weight++;		
		c=fgetc(fp);
	}
	fclose(fp);
	return t;
}




unsigned long EncodeFile(HarfNod* ht, char* srcf, char* codef)
{
	unsigned long count;
	int c;
	int i;
	int p;
	char code[256];
	int l;
	FILE *sfp, *cfp;
	sfp=fopen(srcf, "rb");
	cfp = fopen(codef, "wb");
	if(sfp==NULL || cfp == NULL)
		return 0;
	count = 0;
	c=fgetc(sfp);
	while(feof(sfp)==0)
	{
		l=0;
		for(i=1; i<=257 && ht[i].data!=c; i++);
		if(i==257)
			return 0;
		p=ht[i].parent;
		while(p!=-1)
		{
			if(ht[p].left ==i)
				code[l]='0';
			else
				code[l]='1';
			l++;
			i=p;
			p=ht[i].parent;
		}
		for(i=l-1; i>=0; i--)
		{
			count++;
			if(code[i]=='1')
			{
				fputc('1', cfp);
			}
			else
			{
				fputc('0', cfp);
			}
		}
		c=fgetc(sfp);
	}
	fclose(cfp);
	fclose(sfp);
	return count;
}


HarfNod* RestoreHarfTree(char* filename, unsigned long *cl)
{
	FILE* fp;
	char* buf;
	HarfNod* ht;
	int i;
	fp=fopen(filename, "rb");
	buf = (char*)cl;
	for(i=0; i<=sizeof(unsigned long)-1; i++)
		buf[i]=fgetc(fp);
	ht = new HarfNod[512];
	if(fp == NULL || ht == NULL)
		return NULL;
	buf = (char*)ht;
	for(i=0; i<=512*sizeof(HarfNod)-1; i++)
		buf[i]=fgetc(fp);
		fclose(fp);
	return ht;
}

void main()
{
	
	HarfNod *ht;
	NodWeight *wt;
	int ch;
	char filename[200];
	unsigned long cl;
	printf("\n1.edit\n2.decode\n3.exit\n");
	printf("please choose");
	an = getch();
	while(an!='3')
	{
		switch(ch)
		{
		case '1':
			printf("\ntype a file name");
			gets(filename);
			wt = BuildWeightTable(filename);
			ht = BuildHarfTree(wt);
			cl = EncodeFile(ht, filename, "code");
			StoreHarfTree( ht, cl, "tree");
			break;
		case '2':
			printf("\ntype a file name");
			gets(filename);
			RestoreHarfTree("tree", &cl);
			DecodeFile(ht, cl, filename, "result");
			break;
		}
		printf("\n1.edit\n2.decode\n3.exit\n");
		printf("please choose");
		an = getch();
	}
}