赫夫曼编码代码,C代码库,德仔网

代码语言

代码分类

【C】赫夫曼编码

作者:麦田里的守护者 / 发布于2013/5/28/ 638

该项目是一款基于安卓的图片处理软件，该程序集图片剪裁，锐化，调节暗亮，加边框，加文字，加特效，加图标，自由画板等功能于一身，功能虽说不算强大，但贵在开源，其中还有程序的说明文档，包括图像处理的基础知识，各个算法的描述，以及整个程序的搭建过程，是学习图像处理的很好的资源，有兴趣的朋友们还可以在我们的基础上进行修改，为自己定制一款独特的图像处理程序。


	//作者：石金南
	//功能：赫夫曼编码
	//日期：2013.5.19
	#include<stdio.h>
	#include<malloc.h>
	#include<string.h>
	#include<math.h>
	#include<conio.h>
	#define Len 1000//输入字符的长度
	#define kind 256//字符至多的的种类数目
	#include <stdlib.h>

	struct hfmNum
	{
	char hc;//赫夫曼编码的字符
	char h[10];//字符对应的赫夫曼01编码
	};
	typedef struct hfmTree//赫夫曼树节点
	{
	bool b;//判定是否已有parent节点
	 int weight;
	int rchild,lchild,parent;
	}hfm;//动态分配数组存贮赫夫曼树

	void setInchar(char a[Len]);//从键盘获取字符
	void printchar(char a[]);//输出字符串
	void classifyChar(char c[],char cTyde[],int n[]);//对输入字符串分类，并求出每一类的数目
	int numClass(char a[]);//求出字符串C中有多少个字符
	hfm *CreatHfmTree(char cTyde[],int num[],int numKind);
	struct hfmNum *SureHfm(char cTyde[],hfm *p,int numKind);
	void print(struct hfmNum *q,int numKind);//输出每个字符及它相对应的赫夫曼编码
	void printl();
	char* wordExchange(char c[],struct hfmNum a[],int numKind);

	int main()
	{
	char c[Len]={'\0'};
	int numKind;
	char cTyde[kind]={'\0'},*hfmNumber;//字符的种类
	int num[kind]={0};//每一类字符的数目
	struct hfmNum *q;
	hfm *p;
	setInchar(c);//从键盘获取组成赫夫曼树的字符
	classifyChar(c,cTyde,num);
	numKind=numClass(cTyde);//求出有cTyde字符串中有多少种字符类
	p=CreatHfmTree(cTyde,num,numKind);
	q=SureHfm(cTyde,p,numKind);
	print(q,numKind);
	
	hfmNumber=wordExchange(c,q,numKind);
	{//输出输入字符对应的赫夫曼编码
	 int i=0;
	 while(hfmNumber[i]!='\0')
	 {
	 printf("%c",hfmNumber[i]);
	 i++;
	 }
	}getch();
	return 0;

	}

	
	void setInchar(char a[Len])//
	{
	gets(a);//得到字符串
	
	}

	void printchar(char a[])//输出字符串
	{
	puts(a);
	}

	void classifyChar(char c[],char cTyde[],int n[])//对输入字符串分类，并求出每一类的数目
	{
	int t,i;
	for( i=0;c[i]!='\0';i++)//判定是否到字符串是否到尽头
	{
	 for(t=0;cTyde[t]!='\0';t++)//判定cTyde分类字符中是否有c[t]
	 {
	 if(cTyde[t]==c[i])//判定c[i]字符是否在cTyde分类字符中
	 {
	 n[t]++;break;//如果在对应的类数目加一，跳出循环
	 }
	 }
	 if(cTyde[t]=='\0')//如果不在，则在cTyde分类字符后添加一个c[i]的类
	 {
	 cTyde[t]=c[i];
	 n[t]++;
	 }
	}
	}

	int numClass(char a[])
	{
	int i=0;
	while(a[i]!='\0')//求出字符串c中有多少个字符
	{
	 i++;
	}
	return i;//返回字符数目
	}
	
	hfm *CreatHfmTree(char cTyde[],int num[],int numKind)//建立赫夫曼树
	{
	int m=2*numKind-1,i=0,n1,n2,m1,m2;//确定树有多少个节点
	hfm *p;
	p=(hfm*)calloc(m,sizeof(hfm));//开辟连续的存贮空间
	while(i<numKind)//对前numkind个单位进行初始化
	{
	 p[i].b=0;//
	 p[i].weight=num[i];//前numKind个单位与字符串cTyde中的字符相对应
	 p[i].rchild=-1;
	 p[i].lchild=-1;
	 p[i].parent=-1;
	 i++;
	}
	while(i<m)//对后numKind-1个单位进行初始化
	{
	 p[i].b=0;
	 p[i].weight=0;
	 p[i].rchild=-1;
	 p[i].lchild=-1;
	 p[i].parent=-1;
	 i++;
	}
	for(;numKind<m;numKind++)//
	{
	m2=m1=0;
	n1=n2=Len;//将n1,n2取最大
	for(i=0;i<numKind;i++)//求出节点数组中没parent节点的权值最小的两个数
	{
	
	 if(p[i].b==0&&p[i].weight<n1)
	 {
	 n2=n1;
	 m2=m1;
	 m1=i;
	 n1=p[i].weight;
	 }
	 else if(p[i].b==0&&p[i].weight<n2)
	 {
	 n2=p[i].weight;
	 m2=i;
	 }
	}
	p[numKind].weight=n1+n2;//将两个最小的权值相加赋给numKind
	p[m1].b=p[m2].b=1;//确定m1m2它们有父亲了
	p[m1].parent=p[m2].parent=numKind;//m1,m2的父母是numKind
	p[numKind].rchild=m1;//numKind+1的儿子是m1,m2
	p[numKind].lchild=m2;//最后numKind+1
	}
	return p;
	}
	struct hfmNum *SureHfm(char cTyde[],hfm *p,int numKind)
	{
	struct hfmNum *q=(struct hfmNum*)malloc(numKind*sizeof(struct hfmNum));//建立numKind个地址连续的hfmNum节点
	int a=0;

	char s[10]={'\0'};//
	int l,m1,m2,m3,i;
	for(i=0;i<numKind;i++)
	{
	 l=10;
	 m1=i;
	 while(p[m1].parent!=-1)
	 {
	 l--;
	 m2=p[m1].parent;
	 if(p[m2].lchild==m1)
	 s[l]='0';
	 else if(p[m2].rchild==m1) s[l]='1';
	 m1=m2;
	 }
	 q[i].hc=cTyde[i];//将cTyde的字符种类赋给q[i].hc
	 m3=0;
	 while(l<10)//确定q[i].hc字符相应的赫夫曼编码
	 {
	 q[i].h[m3]=s[l];
	 l++;
	 m3++;
	 }
	 q[i].h[m3]='\0';
	}
	return q;
	}

	void print(struct hfmNum *q,int numKind)
	{
	//int a=0;
	for(int i=0;i<numKind;i++)
	{
	 putchar(q[i].hc);
	 printl();
	 puts(q[i].h);
	 //while(q[i].h[a]!='\0'){printf("%c",q[i].h[a]);a++;}a=0;
	}
	}

	void printl()//为了简便输出:的赫夫曼编码：
	{
	printf("的赫夫曼编码：");
	}


	char* wordExchange(char c[],struct hfmNum a[],int numKind)//将输入的字符转换为对应的赫夫曼编码
	{
	int i=0,m,l=0;
	char *s=(char*)malloc(l*sizeof(char));
	//SqStack *s;//
	//if(!InitStack(s))exit(0);//
	while(c[i]!='\0')//
	{
	 for(m=0;m<numKind;m++)//
	 {
	 if(c[i]==a[m].hc)
	 {
	 for(int b=0;a[m].h[b]!='\0';b++)
	 {
	 l++;
	 s=(char*)realloc(s,l*sizeof(char));
	 s[l-1]=a[m].h[b];
	 }
	 }
	 }
	 i++;
	}
	s[l]='\0';
	return s;
	}

试试其它关键字

　赫夫曼编码　

同语言下

可能有用的

麦田里的守护者贡献的其它代码(2)