huffmantree代码.txt

huffman树的应用程序 源码以及功能说明

//1类型及相关定义(type6.h)
#define n 100 //叶子结点数
#define m 2*n-1//赫夫曼树中结点总数
typedef struct
{
	char ch;//存放编码的字符
	char bits[9];//存放编码位串
	int len;//编码长度
}CodeNode;
typedef CodeNode HuffmanCode[n+1];
typedef struct 
{
	int weight;//权值
	int lchild,rchild,parent;//左右孩子及双亲指针
}HTNode;//树中结点类型
typedef HTNode HuffmanTree[m+1];//0号单元不用
int num;
//2建立赫夫曼树的三个函数(jlhfms.c)
void select(HuffmanTree T,int k,int &s1,int &s2)
{//在HT[1...k]中选择parent为0且权值最小的两个根结点，其序号为s1和s2
	int i,j;int minl=101;
	for(i=1;i<=k;i++)
		if (T[i].weight<minl && T[i].parent==0)
		{
			j=i;minl=T[i].weight;
		}
		s1=j;minl=32767;
		for(i=1;i<=k;i++)
			if(T[i].weight<minl && T[i].parent==0 && i!=s1)
			{
				j=i;minl=T[i].weight;
			}
			s2=j;
}
int jsq(char*s,int cnt[],char str[])
{//统计字符串中各种字母的个数以及字符的种类
	char *p;
	int i,j,k;
	int temp[27];
    for(i=1;i<=26;i++)
		temp[i]=0;
	for(p=s;*p!='\0';p++)//\0是最后一位放上串结束符
	{//统计各种字符的个数
		if(*p>='A' && *p<='Z')
		{
			k=*p-64;
		    temp[k]++;
		}
	}
	j=0;
	for(i=1,j=0;i<=26;i++)//统计有多少种字符
		if(temp[i]!=0)
		{
			j++;
			str[j]=i+64;//送对应的字母到数组中
			cnt[j]=temp[i];//存入对应字母的权值
		}
		return j;
}
void ChuffmanTree(HuffmanTree HT,HuffmanCode HC,int cnt[],char str[])
{//构造赫夫曼HT
	int i,s1,s2;
	for(i=1;i<=2*num-1;i++)//初始化HT
	{
		HT[i].lchild=0;HT[i].rchild=0;
        HT[i].parent=0;HT[i].weight=0;
	}
	for(i=1;i<=num;i++)//输入num个叶子结点的权值
	  HT[i].weight=cnt[i];
	for(i=num+1;i<=2*num-1;i++)
	{//从HT[1..i-1]中选择parent为0且权值最小的两个根结点
		//其序号分别为s1和s2
		select(HT,i-1,s1,s2);
		HT[s1].parent=i;HT[s2].parent=i;
		HT[i].lchild=s1;HT[i].rchild=s2;
		HT[i].weight=HT[s1].weight+HT[s2].weight;
	}
	for(i=0;i<=num;i++)//输入字符集中的字符
		HC[i].ch=str[i];
	i=1;while(i<=num)
		printf("字符 %c,次数为：%d\n",HC[i].ch,cnt[i++]);
}
//3生成赫夫曼编码文件的两个函数(scbmwj.c)
void HuffmanEncoding(HuffmanTree HT,HuffmanTree HC)
{//根据赫夫曼树HT求赫夫曼编码表HC
	int c,p,i;//c和p分别指示T中孩子和双亲的位置
	char cd[n];//临时存放编码串
	int start;//指示编码在cd中的起始位置
	cd[num]='\0';//最后一位放上串结束符
	for (i=1;i<=num;i++)
	{
		start=num;//初始位置
		c=i;//从叶子结点T[i]开始上溯
		while((p=T[i].parent)>0)//直到上溯到t[c]是树根为止
		{//若T[c]是T[p]的左孩子，则生成0；否则生成代码1；
			cd[--start]=(T[p].lchild==c) ? '0':'1';
			c=p;
		}//end of while
		strcpy(H[i].bits,&cd[start]);
		H[i].len=num-start;
	}//end of for
}
void coding(HuffmanCode HC,char *str)
{//对str所代表的字符串进行编码，并写入文件
	int i,j;
	FILE*fp;
	fp=fopen("codefile.txt","w");
	while(*str)
	{
		for(i=1;i<=num;i++)
			if(HC[i].ch==*str)
			{
				for(j=0;j<HC[i].len;j++)
					fputc(HC[i].bits,fp)
					break;
			}
			str++;
	}
	fclose(fp);
}
//4电文的译码(dwym.c)
char *decode(HuffmanCode HC)
{
	FILE *fp;
    char str[254];//假设原文本文件不超过254个字符
    char *p;
    static char cd[n+1];
    int i,j,k=0,cjs;
    fp=fopen("codefile.txt","r");
    while(!feof(fp))
	{
	    cjs=0;//一个字符的编码是否读结束
	    for(i=0;i<num && cjs==0 && !feof(fp);i++)
		{
		    cd[i]=' ';cd[i+1]='\0';//初始化cd串
		    cd[i]=fgetc(fp);
		    for(j=1;j<=num;j++)
					if(strcmp(HC[j].bits,cd)==0)
					{
						str[k]=HC[j].ch;k++;
				        cjs=1;break;
				
					}
		}
	}
	str[k]='\0';p=str;
    return p;
}
#include<iostream>
#include<stdio.h>
#include<string.h>
#include"type6.h"//类的定义
#include"jlhfms.c"//建立赫夫曼树
#include"scbmwj.c"//生成编码文件
#include"dwym.c"//电文编码
using namespace std;
void main()
{
	char st[254],*s,str[27];
	int cn[27];
	HuffmanTree HT;
	HuffmanTree HC;
	printf("输入需要编码的字符串(假设均为大写字母)：\n");
	gets(st);
	num=jsq(st,cn,str);//统计字符的种类及各类字符出现的频率
    ChuffmanTree(HT,HC,cn,str);//建立赫夫曼树
	HuffmanEncoding(HT,HC);//生成赫夫曼编码
	coding(HC,st);//建立电文赫夫曼编码文件
	s=decode(HC);//读编码文件译码
	printf("译码后的字符串：\n");
	printf("%s\n",s);//输出译码后字符串
}