哈夫曼树c语言代码

‘壹’ 编写一个程序，构造一棵哈夫曼树

#include<stdio.h>
#include<string.h>
#define N 50 //叶子结点数
#define M 2*N-1 //树中结点总数
typedef struct
{ char data[5]; //节点值
int weight; //权重
int parent; //双仔世亲结点
int lchild; //左孩子结点
int rchild; //右孩子结点
}htnode;
typedef struct
{ char cd[N]; //存放哈夫曼码
int start;
}hcode;
void createht(htnode ht[],int n) //构造哈夫曼树
{ int i,k,lnode,rnode;
int min1,min2;
for(i=0;i<2*n-1;i++) //所有结点的相关域置初值-1
ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
for(i=n;i<2*n-1;i++) //构造哈夫曼树
{ min1=min2=32767; //lchild和rchild为最小权重的两个结点位置
lnode=rnode=-1;
for(k=0;k<=i-1;k++)
if(ht[k].parent==-1) //只在尚未构造二叉树的结点中查找
{ if(ht[k].weight<min1)
{ min2=min1;
rnode=lnode;
min1=ht[k].weight;
lnode=k;
}
else if(ht[k].weight<min2)
{ min2=ht[k].weight;
rnode=k;
}
}
ht[lnode].parent=i;
ht[rnode].parent=i;
ht[i].weight=ht[lnode].weight+ht[rnode].weight;
ht[i].lchild=lnode;
ht[i].rchild=rnode;
}
}
void createhcode(htnode ht[],hcode hcd[],int n) //构造雀汪哈夫曼编码
{ int i,f,c;
hcode hc;
for(i=0;i<n;i++) //根据哈夫曼树求哈夫曼编码
{ hc.start=n;
c=i;
f=ht[i].parent;
while(f!=-1) //循序直到树根结点
{ if(ht[f].lchild==c) //处理左孩子结点
hc.cd[hc.start--]='0';
else
hc.cd[hc.start--]='1'; //处理右孩子结点
c=f;
f=ht[f].parent;
}
hc.start++; //start指向哈夫曼编码最开始字符
hcd[i]=hc;
}
}
void disphcode(htnode ht[],hcode hcd[],int n) // 输出哈夫曼编码
{ int i,k;
int sum=0,m=0,j;
printf("输出哈夫曼编码：\n");
for(i=0;i<n;i++)
{ j=0;
printf(" %s:\t"顷戚仔,ht[i].data);
for(k=hcd[i].start;k<=n;k++)
{ printf("%c",hcd[i].cd[k]);
j++;
}
m+=ht[i].weight;
sum+=ht[i].weight*j;
printf("\n");
}
printf("\n平均长度=%g\n",1.0*sum/m);
}
void main()
{ int n=15,i;
char *str[]={"The","of","a","to","and","in","that","he","is","at","on","for","His","are","be"};
int fnum[]={1192,677,541,518,462,450,242,195,190,181,174,157,138,124,123};
htnode ht[M];
hcode hcd[N];
for(i=0;i<n;i++)
{ strcpy(ht[i].data,str[i]);
ht[i].weight=fnum[i];
}
printf("\n");
createht(ht,n);
createhcode(ht,hcd,n);
disphcode(ht,hcd,n);
printf("\n");
}

‘贰’ 哈夫曼树编码译码，c语言做的，第17行就是错，搞不懂啊，求高手指点一下啊

首先一个错误是
HaffmanTree 这个打错了 应该是HuffmanTree 这个才是你定义的数据类型

除了这个以外 由于代码不全 所以无法确定是否还有其他问题

‘叁’ 创建一个哈夫曼树并且进行编码权重如下w={5，29，7 8，14，13 ，3 ，11}写出c语言代码

#include"stdafx.h"
#include"hfm.h"
#include<string.h>
#include<malloc.h>//malloc()等
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<limits.h>
#include<iostream>
#defineTRUE1
#defineFALSE1
#defineOK1
#defineERROR1
#defineINFEASIBLE-1

typedefintStatus;
typedefintBoolean；
/************************************************************************/
/*最优二叉树简称：哈夫曼树*/
/************************************************************************/
//哈夫曼树结构
;typedefstruct{
unsignedintweight;//权重
unsignedintparent,lchild,rchild;//树的双亲节点，和左右孩子

}HTNode,*HuffmanTree;

typedefchar**HuffmanCode;


//返回i个节点中权值最小的树的根节点的序号，供select()调用
intMin(HuffmanTreeT,inti){
intj,flag;
unsignedintk=UINT_MAX;//%d-->UINT_MAX=-1,%u--->非常大的数
for(j=1;j<=i;j++)
if(T[j].weight<k&&T[j].parent==0)
k=T[j].weight,flag=j;//
T[flag].parent=1;//将parent标志为1避免二次查找

returnflag;//返回
}

voidSelect(HuffmanTreeT,inti,int&s1,int&s2){
//在i个节点中选取2个权值最小的树的根节点序号，s1为序号较小的那个
intj;
s1=Min(T,i);
s2=Min(T,i);
if(s1>s2){
j=s1;
s1=s2;
s2=j;
}
}

//HuffmanCode代表的树解码二进制值
voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){
//w存放n个字符的权值(均>0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC
intm,i,s1,s2,start;
unsignedc,f;
char*cd;
//分配存储空间
HuffmanTreep;
if(n<=1)
return;
//n个字符(叶子节点)有2n-1个树节点，所以树节点m
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号元素未用
//这一步是给哈夫曼树的叶子节点初始化
for(p=HT+1,i=1;i<=n;++i,++p,++w)
{
(*p).weight=*w;
(*p).lchild=0;
(*p).rchild=0;
(*p).parent=0;
}
//这一步是给哈夫曼树的非叶子节点初始化
for(;i<=m;++i,++p){
(*p).parent=0;
}
/************************************************************************/
/*做完准备工作后，开始建立哈夫曼树
/************************************************************************/
for(i=n+1;i<=m;i++)
{
//在HT[1~i-1]中选择parent=0且weigh最小的节点，其序号分别为s1,s2
Select(HT,i-1,s1,s2);//传引用
HT[s1].parent=HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
/************************************************************************/
/*从叶子到根逆求每个叶子节点的哈夫曼编码*/
/************************************************************************/
//分配n个字符编码的头指针向量，（[0]不用）
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
cd=(char*)malloc(n*sizeof(char));//分配求编码的工作空间
cd[n-1]='';//结束符
for(i=1;i<=n;i++)//每个节点的遍历
{
start=n-1;
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent){//每个节点到根节点的遍历
//从叶子节点到根节点的逆序编码
if(HT[f].lchild==c)
cd[--start]='0';
else
cd[--start]='1';
}
HC[i]=(char*)malloc((n-start)*sizeof(char));//生成一个块内存存储字符
//为第i个字符编码分配空间
strcpy(HC[i],&cd[start]);//从cd赋值字符串到cd
}
free(cd);//释放资源
}

//函数声明
intMin(HuffmanTreeT,inti);//求i个节点中的最小权重的序列号，并返回
voidSelect(HuffmanTreeT,inti,int&s1,int&s2);//从两个最小权重中选取最小的(左边)给s1，右边的给s2
voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn);//哈夫曼编码与解码

intmain(){

HuffmanTreeHT;
HuffmanCodeHC;

int*w,n,i;
printf("请输入权值的个数(>1):");
scanf_s("%d",&n);

w=(int*)malloc(n*sizeof(int));
printf("请依次输入%d个权值(整形):
",n);

for(i=0;i<=n-1;i++)
{
scanf_s("%d",w+i);
}
HuffmanCoding(HT,HC,w,n);

for(i=1;i<=n;i++)
{
puts(HC[i]);
}
return0;
}

‘肆’ 怎么样用c语言程序编码哈夫曼树

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include <ctype.h>
#include<limits.h>
int function1(char ch,char *s)
{
int i;
for(i=0; s[i]!='\0'; i++)
{
if(ch==s[i])return 0;
}
return 1;
}
typedef struct
{
unsigned int weight;
unsigned int parent,lchild,rchild;
} HTNode,*HuffmanTree; // 动态分配数组存储赫夫曼树
typedef char **HuffmanCode; // 动态分配数组存储赫夫曼编码表
// algo6-1.cpp 求赫夫曼编码。实现算法6.12的程序

int min(HuffmanTree t,int i)
{
// 函数void select()调用
int j,flag;
unsigned int k=UINT_MAX; // 取k为不小于可能的值
for(j=1; j<=i; j++)
if(t[j].weight<k&&t[j].parent==0)
k=t[j].weight,flag=j;
t[flag].parent=1;
return flag;
}

void select(HuffmanTree t,int i,int &s1,int &s2)
{
// s1为最小的两个值中序号小的那个

s1=min(t,i);
s2=min(t,i);
/* if(s1>s2)
{
j=s1;
s1=s2;
s2=j;
}*/
}

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) // 算法6.12
{
// w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC
int m,i,s1,s2,start;
unsigned c,f;
HuffmanTree p;
char *cd;
if(n<=1)
return;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0号单元未用
for(p=HT+1,i=1; i<=n; ++i,++p,++w)
{
(*p).weight=*w;
(*p).parent=0;
(*p).lchild=0;
(*p).rchild=0;
}
for(; i<=m; ++i,++p)
(*p).parent=0;
for(i=n+1; i<=m; ++i) // 建赫夫曼树
{
// 在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2
select(HT,i-1,s1,s2);
HT[s1].parent=HT[s2].parent=i;
HT[i].rchild=s1;
HT[i].lchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
// printf("HT[%d].lchild:%d HT[%d].rchild:%d\n",i,s2,i,s1);
}
// 从叶子到根逆向求每个字符的赫夫曼编码
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
// 分配n个字符编码的头指针向量([0]不用)
cd=(char*)malloc(n*sizeof(char)); // 分配求编码的工作空间
cd[n-1]='\0'; // 编码结束符
for(i=1; i<=n; i++)
{
// 逐个字符求赫夫曼编码
start=n-1; // 编码结束符位置
for(c=i,f=HT[i].parent; f!=0; c=f,f=HT[f].parent)
// 从叶子到根逆向求编码
if(HT[f].lchild==c)
cd[--start]='1';
else
cd[--start]='0';
HC[i]=(char*)malloc((n-start)*sizeof(char));
// 为第i个字符编码分配空间
strcpy(HC[i],&cd[start]); // 从cd复制编码(串)到HC
}
free(cd); // 释放工作空间
}
void swap1(int *a ,int *b)
{
int t;
t=*a;
*a=*b;
*b=t;
}
void swap2(char *a,char *b)
{
char ch;
ch=*a;
*a=*b;
*b=ch;
}
int main(void)
{
HuffmanTree HT;
HuffmanCode HC;
char *s1,*s2;
int i,j=0,n,count,*m,t,flag=1;
scanf("%d",&n);
getchar();
s1=(char*)malloc((n+n)*sizeof(char));
s2=(char*)malloc(n*sizeof(char));
memset(s2,'\0',n*sizeof(char));
gets(s1);
count=strlen(s1);
for(i=0; i<count; i++)
{
if(!isspace(*(s1+i)))
{
if(function1(*(s1+i),s2))
{
*(s2+j)=*(s1+i);
j++;
}
}
else;
}
m=(int*)malloc(j*sizeof(int));
for(i=0; i<j; i++)
*(m+i)=0;
for(t=0; t<j; t++)
{
for(i=0; i<count; i++)
{
if(*(s2+t)==*(s1+i))
*(m+t)+=1;
}
}
for(i=0;i<j;i++)
while(flag)
{
flag = 0;
for (t=0; t<j-1; t++)
{
if(*(m+t)<*(m+t+1))
{
swap1(m+t,m+t+1);
swap2(s2+t,s2+t+1);
flag=1;
}
}
}
HuffmanCoding(HT,HC,m,j);
for(i=1,t=0; i<=j; i++,t++)
{
printf("%c %d %s\n",*(s2+t),*(m+t),HC[i]);

}
return 0;
}

‘伍’ 数据结构作业，用c语言编:根据给定的n个权值生成赫夫曼二叉树，输出赫夫曼编码。求大神解答，求代码！

#include"stdafx.h"
#include芹圆者"stdlib.h"
#include"string.h"
staticints1,s2;
typedefstruct
{
unsignedintweight;//结点的权值
unsignedintparent;//结点的双亲
	unsignedintlchild;//左孩子
	unsignedintrchild;//右孩子
	unsignedchardate;
}HTnode,*Huffmantree;
typedefchar**Huffmancode;
voidselect(HuffmantreeHT,intn)//寻找权值最小的S1,s2节点
{
	inti,j;
	for(i=1;i<=n;i++)
	{
		if(HT[i].parent==0)
		{
			s1=i;break;
		}
	}
	for(j=i+1;j<=n;j++)
	{
		if(HT[j].parent==0)
		{
			s2=j;break;
		}
	}
	for(i=1;i<=n;i++)
	{
		if(HT[i].parent==0)
		{
			if(HT[s1].weight>HT[i].weight)
			{
				if(s2!=i)
				{
					s1=i;
				}
			}
		}
	}
	for(j=1;j<=n;j++)
	{
		if(HT[j].parent==0)
		{
			if(HT[s2].weight>HT[j].weight)
			{
				if(s1!=j)
				{
					s2=j;
				}
			}
		}
	}
	if(s1>s2)
	{
		inttemp=s1;
		s1=s2;
		s2=temp;
	}
}
voidHuffmancoding(HuffmantreeHT,HuffmancodeHC,int*w,intn,char*d)
{
	inti,j,c,f,start;
	charcd[100];
	intm=2*n-1;//共有m个节点，n个叶子节点
	charstring[100];//输入字符串嫌薯进行编码
	char*out;//存放字符串编码
	HT=(Huffmantree)malloc((m+1)*sizeof(HTnode));
	for(i=1;i<=n;i++)
	{
		HT[i].weight=w[i-1];
		HT[i].date=d[i-1];
		HT[i].parent=0;
		HT[i].lchild=0;
		HT[i].rchild=0;
	}
	for(i=n+1;i<=m;i++)
	{
		HT[i].weight=0;
		HT[i].parent=0;
		HT[i].lchild=0;
		HT[i].rchild=0;
	}
	for(i=n+1;i<=m;i++)
	{
		select(HT,i-1);
		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;
	}
	printf("输出哈夫曼树的存储结构
");
	for(i=1;i<=m;i++)
	{	
		printf("%4d%4d%4d%4d%c
",HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild,HT[i].date);
	}
	HC=(Huffmancode)malloc((n+1)*sizeof(char*));
	cd[n-1]='';//编码结束符
	for(i=1;i<=n;i++)//逐个字符求霍夫曼编码
	{
		start=n-1;//编码结束符位置
		for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到根逆向求编码
		{
			if(HT[f].lchild==c)
			{
				cd[--start]='腔吵0';
			}
			else
			{
				cd[--start]='1';
			}
		}
		HC[i]=(char*)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间
		strcpy(HC[i],&cd[start]);//从cd复制编码到HC
	}
	printf("输出结点的编码
");
	for(i=1;i<=n;i++)
	{
		printf("%c的编码:",HT[i].date);
		puts(HC[i]);//用puts函数输出字符串
	}
printf("请输入字符串
");
	for(i=0;i<=3;i++)//输入字符串进行编码
	{
		if(string[i-1]==10)//目的是去除空格字符
		{
			i--;
		}
		scanf("%c",&string[i]);
	}
	printf("字符串的编码是:
");
	out=(char*)malloc(n*sizeof(char));
	for(i=0;string[i]!='';i++)
	{
		for(j=1;j<=n;j++)
		{
			if(HT[j].date==string[i])
			{
				strcpy(out,HC[j]);
				printf("%s",out);
				break;
			}
		}
	}
}
intmain()	
{
	HuffmantreeHT;
	HuffmancodeHC;
	int*w,n,i;
	char*d;
	printf("请输入节点数
");
	scanf("%d",&n);
	w=(int*)malloc(n*sizeof(int));
	d=(char*)malloc(n*sizeof(char));
	printf("请输入节点的权值
");
	for(i=0;i<n;i++)
	{
		scanf("%d%c",&w[i],&d[i]);
	}
	Huffmancoding(HT,HC,w,n,d);
	return0;
}

‘陆’ 数据结构中哈夫曼树的应用（C语言）

#include<stdio.h>
#include<stdlib.h>
typedef int DataType;
#define MaxValue 10000
#define MaxBit 10
#define MaxN 100
#define N 100;
int n1=0;
char c[100];
typedef struct Node
{
DataType data;
struct Node *leftChild;
struct Node *rightChild;
}BiTreeNode;
typedef struct
{
int weight;
int flag;
int parent;
int leftChild;
int rightChild;
}HaffNode;

typedef struct
{
int bit[MaxN];
int start;
int weight;
}Code;

struct worder
{
char words; /*字符*/
}word[100];
struct weighted
{
int weighter; /*转换权值有利于文件的存储*/
}weight[100] ;
void Initiate(BiTreeNode **root) /*初始化二叉树*/
{
*root=(BiTreeNode * )malloc(sizeof(BiTreeNode));
(*root)->leftChild=NULL;
(*root)->rightChild=NULL;
}
BiTreeNode *InsertLeftNode(BiTreeNode *curr,DataType x) /*插入左子树*/
{
BiTreeNode *s,*t;
if(curr==NULL) return NULL;
t=curr->leftChild;
s=(BiTreeNode *)malloc(sizeof(BiTreeNode));
s->data=x;
s->leftChild=t;
s->rightChild=NULL;
curr->leftChild=s;
return curr->leftChild;
}

BiTreeNode *InsertRightNode(BiTreeNode *curr ,DataType x) /*插入右子树*/
{
BiTreeNode *s,*t;
if(curr==NULL)
return NULL;
t=curr->rightChild;
s=(BiTreeNode *)malloc(sizeof(BiTreeNode));
s->data=x;
s->rightChild=t;
s->leftChild=NULL;
curr->rightChild=s;
return curr->rightChild;
}

void Haffman(int weigh[],int n,HaffNode haffTree[],int a[][3]) /*建立哈夫曼树*/
{
int i,j,m1,m2,x1,x2;

for(i=0;i<2*n-1;i++)
{

if(i<n)
haffTree[i].weight=weigh[i];
else haffTree[i].weight=0;
haffTree[i].parent=-1;
haffTree[i].flag=0;
haffTree[i].leftChild=-1;
haffTree[i].rightChild=-1;
}

for(i=0;i<n-1;i++)
{
m1=m2=MaxValue;
x1=x2=0;
for(j=0;j<n+i;j++)
{
if(haffTree[j].weight<m1&&haffTree[j].flag==0)
{
m2=m1;
x2=x1;
m1=haffTree[j].weight;
x1=j;
}
else if(haffTree[j].weight<m2&&haffTree[j].flag==0)
{
m2=haffTree[j].weight;
x2=j;
}
}
haffTree[x1].parent=n+i;
haffTree[x2].parent=n+i;
haffTree[x1].flag=1;
haffTree[x2].flag=1;
haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight;
haffTree[n+i].leftChild=x1;
haffTree[n+i].rightChild=x2;
a[i+1][0]=haffTree[x1].weight;
a[i+1][1]=haffTree[x2].weight; /*将每个权值赋值给二维数组a[][],利用这个二维数组可以进行建立二叉树*/
a[i+1][2]=haffTree[n+i].weight;
}
}

void HaffmanCode(HaffNode haffTree[],int n,Code haffCode[]) /*对已经建立好的哈夫曼树进行编码*/
{
Code *cd=(Code *)malloc(sizeof(Code));
int i,j,child,parent;

for(i=0;i<n;i++)
{
cd->start=n-1;
cd->weight=haffTree[i].weight;
child=i;
parent=haffTree[child].parent;
while(parent!=-1)
{
if(haffTree[parent].leftChild==child)
cd->bit[cd->start]=0;
else
cd->bit[cd->start]=1;
cd->start--;
child=parent;
parent=haffTree[child].parent;
}

for(j=cd->start+1;j<n;j++)
haffCode[i].bit[j]=cd->bit[j];
haffCode[i].start=cd->start+1;
haffCode[i].weight=cd->weight;
}
}

void PrintBiTree(BiTreeNode *bt ,int n) /*将哈夫曼树转换成的二叉树进行打印*/
{
int i;
if(bt==NULL)
return;
PrintBiTree(bt->rightChild,n+1);
for(i=0;i<n;i++)
printf(" ");
if(bt->data!=0&&bt->data<100)
{
if(n>0)
{
printf("---");
printf("%d\n\n",bt->data);
}
}
PrintBiTree(bt->leftChild,n+1);
}

int search(int a[][3],int m) /*查找和a[][2]相等的权值*/
{
int i=1;
if(m==1) return 0;
while(a[i][2]!=a[m][0]&&i<m)
i++;
if(i==m) return 0; /*查找失败返回数字0 查找成功返回和a[][2]相等的数的行数 i*/
else return i;
}

int searcher(int a[][3],int m) /*查找和a[][1]相等的权值*/
{
int i=1;
if(m==1) return 0;
while(a[i][2]!=a[m][1]&&i<m) /*查找失败返回数字0 查找成功返回和a[][1]相等的数的行数 i*/
i++;
if(i==m) return 0;
else return i;
}

void creat(BiTreeNode *p,int i,int a[][3]) /*建立哈夫曼树*/（利用递归）
{
int m,n;
BiTreeNode *p1,*p2,*p3;
if(i<=0) return;
p1=p;
if(a[i][0]!=a[i][1]) /*如果a[][0]和a[][1]不相等*/
{
p2=InsertLeftNode(p,a[i][0]); /*a[][0]为左子树*/
n=search(a,i);
if(n)
creat(p2,n,a);
p3=InsertRightNode(p1,a[i][1]); /*a[][1]为右子树*/
m=searcher(a,i);
if(m)
creat(p3,m,a);
} /*如果a[][0]和a[][1]相等则只要进行一个的查找*/
else
{
p2=InsertLeftNode(p,a[i][1]);
n=searcher(a,i);
if(n)
creat(p2,n,a);
p3=InsertRightNode(p1,a[i][1]);
}
}

void code(Code myHaffCode[],int n ) /*编码*/
{
FILE *fp,*fp1,*fp2;
int i=0,k,j;
int text_len = strlen(c);
int *p2;
struct worder *p1;
if((fp2=fopen("CodeFile","wb"))==NULL) /*建立存储编码的文件*/
{
printf("Error,cannot open file\n" );
exit(0);
}
if((fp1=fopen("hfmTree","rb"))==NULL) /*读取存储字符的文件*/
{
printf("\n\n Please,increase records first~!! \n" );
return;
}
for(p1=word;p1<word+n;p1++)
{
fread(p1,sizeof(struct worder),1,fp1) ;
printf("word=%c Weight=%d Code=",p1->words,myHaffCode[i].weight); /*输出每个权值的编码*/
for(j=myHaffCode[i].start;j<n;j++)
printf("%d",myHaffCode[i].bit[j]);
printf("\n");
printf("\n");
i++;
}
j=0;
printf("\n\nThe codes :") ;
for(i=0;i< text_len;i++)
{
while(c[i]!=word[j].words) /*查找字符找到对应的编码*/
{
j++;
}
for(k=myHaffCode[j].start;k<n;k++)
{
printf("%d",myHaffCode[j].bit[k]); /*输出相应的编码*/
fprintf(fp2,"%d",myHaffCode[j].bit[k]);
}
j=0;
}

fclose(fp2);
}

void sava(int n) /*建立文件*/
{
FILE *fp,*fp1,*fp2;
int *p2,i,j;
struct worder *p1;
struct weighted *p3;
if((fp2=fopen("NO.","wb"))==NULL) /*建立存储权值个数的文件*/
{
printf("Error,cannot open file\n" );
exit(0);
}
fprintf(fp2,"%d",n) ;
if((fp=fopen("hfmTree","wb"))==NULL) /*建立存储字符的文件*/
{
printf("Error,cannot open file\n" );
exit(0);
}
for(p1=word;p1<word+n;p1++)
{
if(fwrite(p1,sizeof(struct worder),1,fp)!=1)
printf("file write error\n");
}
fclose(fp);
if((fp1=fopen("hfmTree-1","wb"))==NULL) /*建立存储权值的文件*/
{
printf("Error,cannot open file\n" );
exit(0);
}
for(p3=weight;p3<weight+n;p3++)
{
if(fwrite(p3,sizeof(struct weighted),1,fp1)!=1)
printf("file write error\n");
}
fclose(fp1);
printf("Please input any key !\n") ;

printf("Please input any key !\n") ;
if(n>MaxN)
{
printf("error!\n\n");
exit(0);
}
}

void menu() /*界面*/
{

printf("\n\n\n\t\t*************************************\n\n");
printf("\t\t\t1. To Code:\n\n"); /*编码*/
printf("\t\t\t2. Decoding:\n\n"); /*译码*/
printf("\t\t\t3. Output the huffman Tree:\n\n"); /*打印哈夫曼树*/
printf("\t\t\t4. New data\n\n");
printf("\t\t\t5. Quit up...\n\n");
printf("\n\t\t************************************\n\n");
printf("Input you choice :\n");
}

void main()
{ FILE *fp,*fp1,*fp2,*fp3,*fp4;
int i,j;
int b[100][3],m=100,n,w,k=0,weigh[100];
struct worder *d;
struct weighted *p2;
char h;
BiTreeNode *root,*p;

HaffNode *myHaffTree=(HaffNode *)malloc(sizeof(HaffNode)*(2*m+1));
Code *myHaffCode=(Code *)malloc(sizeof(Code)*m);
Initiate(root);
if(((fp1=fopen("hfmTree","rb"))==NULL)&&((fp=fopen("hfmTree-1","rb"))==NULL))
{
loop:
printf("how many number do you want input?\n");
scanf("%d",&n);
if((fp=fopen("hfmTree-1","wb"))==NULL)
{
printf("Error,cannot open file\n" );
exit(0);
}
for(i=0;i<n;i++)
{
printf("\nword[%d]=",i) ;
scanf("%s",&word[i].words) ;
printf("\nweight[%d]=",i);
scanf("%d",&weight[i].weighter);
}
sava(n) ;
}
else
{
if((fp3=fopen("NO.","rb"))==NULL)
{
printf("\n\n Please,increase records first~!! \n" );
return;
}
fscanf(fp3,"%d",&n);
if((fp=fopen("hfmTree-1","rb"))==NULL)
{
printf("\n\n Please,increase records first~!! \n" );
return;
}
for(p2=weight;p2<weight+n;p2++)
{
fread(p2,sizeof(struct weighted),1,fp) ;
weigh[k]=p2->weighter ;
k++;
}
Haffman(weigh,n,myHaffTree,b);
HaffmanCode(myHaffTree,n,myHaffCode);
while(1)
{
do
{
clrscr();
menu();
scanf("%d",&w);
}while(w!=1&&w!=2&&w!=3&&w!=4&&w!=5);
switch(w)
{
case 1: clrscr();
printf("plesase input :\n");
scanf("%s",&c) ;
if((fp2=fopen("ToBeTran","wb"))==NULL)
{
printf("Error,cannot open file\n" );
exit(0);
}
fprintf(fp2,"%s",c) ;
fclose (fp2);
code(myHaffCode,n) ;
getch();
break;
case 2: if((fp2=fopen("ToBeTran","rb"))==NULL)
{
printf("\n\n Please,increase records first~!! \n" );
return;
}
fscanf(fp2,"%s",&c);
printf("The words:");
printf("%s",c);
if((fp4=fopen("TextFile.","wb"))==NULL)
{
printf("Error,cannot open file\n" );
exit(0);
}
fprintf(fp4,"%s",c) ;
fclose (fp4);
getch();
break;
case 3: clrscr();
printf("The huffman Tree:\n\n\n\n\n\n");
p=InsertLeftNode(root,b[n-1][2]);
creat(p,n-1,b);
PrintBiTree(root->leftChild,n);
printf("\n");
getch();
clrscr();
break;
case 4:goto loop;

case 5:exit(0);
}
}
}
getch();
}

‘柒’ 霍夫曼编码 用c语言实现

以前写的，证明最优子结构，随便一本算法书上就有.
#include<stdio.h>
#include<stdlib.h>
#define
NIL
-2
#define
Size_Max_bm
30
#define
left(i)
(2*(i)+1)
#define
right(i)
(2*(i)+2)
#define
swap(a,b)
{cjys
t;t=(a);(a)=(b);(b)=t;}
#define
parent(i)
((i)%2?((i)-1)/2:((i)-2)/2)typedef
struct
cjys
{
char
sj;
int
pl;
struct
cjys
*left;
struct
cjys
*right;
}cjys;typedef
struct
cjdl
{
int
size;
int
leapsize;
cjys
*p;
}cjdl;
cjys
*fpnn(void);
void
input(cjdl
*p);
cjys
*fpnn(void);
void
zxdwh(cjys
*p,
int
i,
int
leapsize);
void
rd(cjdl
*p,
cjys
tp);
cjys
cd(cjdl
*p);
void
hbs(cjdl
*p);
cjys
*cjs(cjdl
*p);
void
bls(cjys
*p,int
*jl,
int
i);
void
disp(char
*tp,
cjys
*p);int
main()
{
cjdl
p;
char
x[255];
cjys
*re=NULL;
int
jl[Size_Max_bm];
input(&p);
re=cjs(&p);
printf("对照编码图为:\n");
bls(re,jl,0);
freopen("CON","r",stdin);
printf("输入Huffman码(VLC):");
scanf("%s",x);
disp(x,re);
system("pause");
}
void
input(cjdl
*p)
{
int
i;
cjys
*tp;
tp=fpnn();
printf("输入字母个数:");
scanf("%d",
&p->size);
p->p=malloc(sizeof(cjys)*p->size);
p->leapsize=0;
for(i
=
0;
i
<
p->size;i++)
{
printf("输入第%d字母:",i+1),scanf("
%c",&tp->sj);
printf("输入出现次数(频率整数):"),scanf("%d",&tp->pl);
rd(p,*tp);
}
free(tp);
}
cjys
*fpnn(void)
{
cjys
*p=NULL;
p=malloc(sizeof(cjys));
p->left=NULL;
p->right=NULL;
return
p;
}
void
zxdwh(cjys
*p,
int
i,
int
leapsize)
{
int
l=left(i),
r=right(i),
mini=i;
if(l<leapsize
&&
p[l].pl<p[mini].pl)
mini=l;
if(r<leapsize
&&
p[r].pl<p[mini].pl)
mini=r;
if(mini
!=
i)
{
swap(p[i],p[mini]);
zxdwh(p,mini,leapsize);
}
}
void
rd(cjdl
*p,
cjys
tp)
{
if(p->leapsize
==
p->size)
{
printf("队列已满!");
exit(0);
}
p->p[p->基枣leapsize]=tp;
int
j=p->leapsize,k=parent(j);
while(k>=0
&&
p->p[j].pl
<
p->p[k].pl)
{
swap(p->p[j],p->p[k]);
j=k;
k=parent(j);
}
p->御裤leapsize++;
}
cjys
cd(cjdl
*p)
{
if(p->leapsize
==
0)
{
printf("队列搏拆拆已空!");
exit(0);
}
cjys
tp=p->p[0];
p->leapsize--;
p->p[0]=p->p[p->leapsize];
zxdwh(p->p,0,p->leapsize);
return
tp;
}
void
hbs(cjdl
*p)
{
cjys
*p1=NULL,
*p2=NULL;
cjys
tp;
p1=fpnn();
p2=fpnn();
*p1=cd(p);
*p2=cd(p);
tp.left=p1;
tp.right=p2;
tp.pl=p1->pl+p2->pl;
tp.sj=NIL;
rd(p,tp);
}cjys
*cjs(cjdl
*p)
{
int
i,
n=p->leapsize;
cjys
*tp=NULL;
tp=fpnn();
for(i
=
0;
i
<
n-1;
i++)
hbs(p);
*tp=p->p[0];
return
tp;
}
void
bls(cjys
*p,
int
*jl,
int
i)
{
if(p
==
NULL)
return;
if(p->sj!=NIL)
{
int
i2;
printf("%c:",p->sj);
for(i2
=
0;
i2
<
i;
i2++)
printf("%d",jl[i2]);
printf("\n");
}
jl[i]=0;
bls(p->left,jl,i+1);
jl[i]=1;
bls(p->right,jl,i+1);
}
void
disp(char
*tp,
cjys
*p)
{
cjys
*ttp=NULL;
int
pd=0;
while(1)
{
ttp=p;
while(1)
{
if(ttp->sj
!=
NIL)
{
printf("%c",ttp->sj);
break;
}
if(*tp
==
'\0')
{
pd=1;
break;
}
if(*tp++
==
'0'
)
ttp=ttp->left;
else
ttp=ttp->right;
}
if(pd)
break;
}
}

‘捌’ 哈夫曼树怎么运行.代码完全看不懂，运行的窗口都不知道该输入什么，请指教~

有6个字符,分别是A,B,C,D,E,F,对应的权值分别是6,5,4,3,2,1,
也就是说字符A的权值是6,字符B的权值是5,按此顺序,最后的字符F的权值是1.
求这6个字符的哈夫曼编码.

运行程序:
输入叶子结点的总个数(n):6
输入6个叶子结点的字符(Data)和权值(Weight):
No.1=>Data:A
Weight:6
No.2=>Data:B
Weight:5
No.3=>Data:C
Weight:4
No.4=>Data:D
Weight:3
No.5=>Data:E
Weight:2
No.6=>Data:F
Weight:1
输出哈夫曼编码:
A(6):10
B(5):01
C(4):00
D(3):110
E(2):1111
F(1):1110

对谈皮应的哈夫曼树(带权值):

N21
/
N9N12
//
456N6
/
3N3
/
12

对应的哈夫曼树(带字符):
(注:哈夫曼树的左分支代表0,右分支代表1)

N21
/
N9N12
//
CBAN6
/
DN3
/
陆侍则FE

例如:
从根结点N21到结点A,先经历右分支,后经历左分支,结点A的编码就是10
从根结点N21到结点F,先经历三次右分支,最后经历左分支,结点F的编码就是1110


#include<stdio.h>
#definemax21
structhuffnode
{
chardata;
intweight;
intparent;
intleft;
intright;
};

structhuffcode
{
charcd[max];
intstart;
};

intmain()//原代码main()
{
structhuffnodeht[2*max];
structhuffcodehcd[max],d;
inti,k,f,l,r,n,c,m1,m2;
//printf("pleaseinputn
");
printf("输入叶子结点的总个数(n):");
scanf("%d",&n);
printf("输入%d个叶子结点的字符(Data)和权值(Weight):
",n);
for(i=1;i<=n;i++)
{
getchar();//吸收掉回车符'
'
//原代码printf("NO.&d=>Data:",i);
printf("NO.%d=>Data:",i);
scanf("%c",&ht[i].data);
printf("	Weight:");
scanf("%d",&ht[i].weight);
}
for(i=1;i<=2*n-1;i++)//所有结点初始化
{
ht[i].parent=ht[i].left=ht[i].right=0;
}
//创建"哈夫曼树"
//原代码for(i=1;i<=2*n-1;i++)
for(i=1;i<n;i++)
{
//查找"最小值"和"次最小值"的下标
//l是最小值的下标,r是次最小值的下标
m1=32767;
l=r=0;
//原代码for(k=1;k<=i-1;k++)
for(k=1;k<=n+i-1;k++)
{
//原代码if(ht[k].weight==0)
早棚if(ht[k].parent==0)
{
if(ht[k].weight<m1)
{
m2=m1;
r=l;//原代码r=1;
m1=ht[k].weight;
l=k;
}
elseif(ht[k].weight<m2)
{
m2=ht[k].weight;
r=k;
}
}
}
//原代码ht[l].parent=i;
//原代码ht[r].parent=i;
//原代码ht[i].weight=ht[l].weight+ht[r].weight;
//原代码ht[i].left=l;
//原代码ht[i].right=r;
ht[l].parent=n+i;
ht[r].parent=n+i;
ht[n+i].weight=ht[l].weight+ht[r].weight;//新结点
ht[n+i].left=l;
ht[n+i].right=r;
}
//编码过程
for(i=1;i<=n;i++)
{
d.start=n;
c=i;
f=ht[i].parent;
while(f!=0)
{
if(ht[f].left==c)
{
d.cd[d.start]='0';
}
else
{
d.cd[d.start]='1';
}
d.start=d.start-1;
c=f;
f=ht[f].parent;
}
//原代码hcd[i]=d;
hcd[i].start=d.start;
for(k=d.start+1;k<=n;k++)
{
hcd[i].cd[k]=d.cd[k];
}
}
//输出每个叶子结点的哈夫曼编码
//printf("outputhuff_code:
");
printf("输出哈夫曼编码:
");
for(i=1;i<=n;i++)
{
printf("%c(%d):",ht[i].data,ht[i].weight);
//原代码for(k=hcd[i].start;k<=n;k++)
for(k=hcd[i].start+1;k<=n;k++)
{
printf("%c",hcd[i].cd[k]);
}
printf("
");
}

return0;//intmain()要有返回值
}

‘玖’ 关于C语言建立赫夫曼树的问题，我不是很明白，下面是代码：

下面是我写程序的时候的注释，两种方法都写上了。这个程序不能运行，主要是为了理解，注释写的很清楚的。
/*这只是讲解，程序并不能运行*/
#include<stdio.h>
#include<stdlib.h>

#define OK 1
#define ERROR 0

typedef struct
{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;

typedef char * * HuffmanCode;

int a[100];
int s1,s2;

int Select()
/*在Select函数中，选取了两个根节点权值最小的树构造了一棵新的数，需要将这两个最小的删掉，将新的加入，再找两个最小的，但如果这样，我们就修改了树了，最后得到
的树中，我们删除了一些结点，所以我想，将这些树的权值放在一个整型数组中，去寻找最小的两个*/
{
min=a[1];
s1=1;
for(i=2;i<=a[0];++i)
if(min>a[i])
{
s2=s1;
s1=i;
}
for(i=s1;i<n;++i)
a[i]=a[i+1];
for(i=s2;i<n;++i)
a[i]=a[i+1];
a[0]=a[0]-2;
return OK;
}

HuffmanTree HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int *w,int n)
/*HT是树，HC存放赫夫曼树的叶结点的编码，w存放叶结点的权值，n是叶结点的个数*/
{
int m,i,j,start,t;
if(n<=1)
return OK;
m=2*n-1; /*因为有n个叶结点，所以共有2*n-1个结点*/
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /*为m个节点分配空间，0结点不使用*/
if(!HT)
return ERROR;
for(p=HT,i=1;i<=n;++i,++p)
{
p->weight=w[i]; /*数组w中存放叶结点的权值，从下标1开始*/
p->parent=0;
p->lchild=0;
p->rchild=0;
} /*以上是为叶结点初始化*/
for(;i<=m;++i,++p)
{
p->weight=0;
p->parent=0;
p->lchild=0;
p->rchild=0;
} /*为非叶结点初始化，非叶结点的权值是待计算的*/
a[0]=n;
for(p=HT,i=1;i<=a[0];++i,++p)
a[i]=p->weight;
for(i=n+1;i<=m;++i)
{
Select(); /*找到a数组中两个最小的元素是s1,s2，并且删除它们,a[0]中存储a中元素个数，要及时修改a[0]的值*/
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; /*将求得的新的结点的权值加入a数组中*/
a[0]=a[0]+1;
a[a[0]]=HT[i].weight;
} /*该循环是建赫夫曼树*/
/*以下从叶子到根逆向求每个字符的赫夫曼编码*/
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
if(!HC)
return ERROR; /*为n个字符编码分配头指针向量，0号单元不使用*/
cd=(char *)malloc(n*sizeof(char));
if(!cd)
return ERROR; /*分配求编码的工作空间*/
cd[n-1]='\0'; /*编码结束符*/
for(i=1;i<=n;++i)
{
start=n-1; /*由于n-1位置已经存放了'/0'，所以下面用--start,从n-2的位置存放0,1编码*/
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
if(HT[f].lchild==c)
cd[--start]="0";
else
cd[--start]="1";
HC[i]=(char *)malloc((n-start)*sizeof(char)); /*各字符的编码长度不等，故为每一个头指针向量动态分配它所指向的空间大小，就是n-start*/
if(!H[i])
return ERROR;
t=1;
printf("\n%d:",i);
for(j=start;j<=n-2;j++)
{
HC[i][t++]=cd[j];
printf("%c",cd[j]);
}
}
free(cd);
return HT;
}
/*由此得到的赫夫曼树的前n个分量表示叶子结点，最后一个分量表示根结点*/
/*以上算法是从叶子到根逆向处理的*/

/*以下算法是从根出发，遍历整棵赫夫曼树，求得各个叶子结点所表示的字符的赫夫曼编码*/
/*译码的过程是分解电文中字符串，从根出发，按字符'0'或'1'确定找左孩子或右孩子，直至叶子结点，便求得该子串相应的字符。*/
HuffmanTree HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int *w,int n)
/*HT是树，HC存放赫夫曼树的叶结点的编码，w存放叶结点的权值，n是叶结点的个数*/
{
HuffmanTree p;
char *cd;
int m,i,j,start,t,c,f;
if(n<=1)
exit(OK);
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
if(!HT)
return ERROR;
for(p=HT+1,i=1;i<=n;++i,++p)
{
p->weight=w[i];
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(;i<=m;++i,++p)
{
p->weight=0;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
a[0]=n;
for(p=HT+1,i=1;i<=a[0];++i,++p)
a[i]=p->weight;
for(i=n+1;i<=m;++i)
{
Select();
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;
a[0]=a[0]+1;
a[a[0]]=HT[i].weight;
}

HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
if(!HC)
return ERROR; /*分配n个字符编码的头指针向量*/
p=m; /*m是结点总数*/
cdlen=0; /*应该是计数每一个编码的长度*/
for(i=1;i<=m;++i)
HT[i].weight=0; /*遍历赫夫曼树时用作结点的标志(是否是weight域为0，表示没有遍历过，weight域为1，表示遍历过)*/
while(p)
{
if(HT[p].weight==0)
{
HT[p].weight=1;
if(HT[p].lchild!=0)
{
p=HT[p].lchild;
cd[cdlen++]='0';
} /*左孩子不等于0，表示没有走到左边的尽头，0就是NULL，*/
/*我们将一直执行这个if语句，直到走到左边的尽头，将所有左边的边全部赋值为0*/
else
if(HT[p].rchild==0)
{
HC[p]=(char *)malloc((cdlen+1)*sizeof(char));
cd[cdlen]='\0';
strcpy(HC[p],cd); /*当走到最左边的时候，我们就得到了最左下那个结点的编码，存储在cd数组中，将它赋值到HC[p]中*/
}
}
else
if(HT[p].weight==1)
{
HT[p].weight=2;
if(HT[p].rchild!=0)
{
p=HT[p].rchild;
cd[cdlen++]='1';
}
}
else
{
HT[p].weight=0;
p=HT[p].parent;
--cdlen; /*因为这个编码和上一个编码只有最后一位是不一样的，所以cdlen-1*/
}
}
return HT;
}

‘拾’ 哈夫曼编码C语言实现

我写了一个注释较为完整且压缩、解压缩比较全面的：

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

#define MAX_FILE 5000/* 假设的文件最大长度 */
#define MAXLIST 256/* 最大MAP值 */
#define MAX_HOFFMAN_LENGTH 50/* 哈夫曼编码长度 */
char dictionary[MAXLIST][2]={0};/* Hash映射,[][0]为权值,[][1]为字符 */
char fileContent[MAX_FILE];/* 处理的字符串大小 */
int Hoffman[MAXLIST][MAX_HOFFMAN_LENGTH]={2};/* 哈夫曼编码序列 */
char HoffmanList[MAXLIST]={0};/* 哈夫曼编码对应的字符有序序列 */
char HoffFileCode[MAX_FILE]={0};/* 哈夫曼编码字符串序列 */
char HoffFile[MAX_FILE]={0};
/* 编码到假设的文件的哈夫曼压缩格式： 依次存储 原字符串长度(1字节存储:可扩展到2字节)、哈夫曼编码数(1字节)、每个哈夫曼编码的长度序列、每个哈夫曼编码对应的字符序列、编码过的哈夫曼字符串 */

char GetFile[MAX_FILE]={0};/* 解码序列 */

void ShellSort(char pData[MAXLIST][2],int Count)/* Shell排序，用于准备有序化要构造的编码权值构造哈夫曼树做准备 */
{
int step[4]={9,5,3,1};/* 增量序列 */

int iTemp,cTemp;
int k,s,w,i,j;
for(i=0;i<4;i++)
{
k=step[i];
s=-k;
for(j=k;j<Count;j++)
{iTemp=pData[j][0];
cTemp=pData[j][1];
w=j-k;
if(s==0)
{
s=-k;
s++;
pData[s][0]=iTemp;
pData[s][1]=cTemp;
}
while((iTemp<pData[w][0])&&(w>=0)&&(w<=Count))
{
pData[w+k][0]=pData[w][0];/* 权值交换 */
pData[w+k][1]=pData[w][1];/* 字符交换 */
w=w-k;
}
pData[w+k][0]=iTemp;
pData[w+k][1]=cTemp;
}
}
}

struct TNode/* 哈夫曼树结点 */
{
struct TNode* pNode;
struct TNode* lNode;
struct TNode* rNode;
char dictionary;
char weight;

};

void TNode_init(struct TNode*tn,char dic,char wei)
{
tn->pNode=0;
tn->lNode=0;
tn->rNode=0;
tn->dictionary=dic;
tn->weight=wei;
}
struct LNode/* 链表结点,用于存储哈夫曼树结点,进而构造哈夫曼树(保证每一步链表结点包含的哈夫曼结点都是有序的) */
{
struct LNode* prev;
struct LNode* next;
struct TNode* tnode;

};

void LNode_init(struct LNode* ln)
{
ln->prev=ln->next=0;
ln->tnode=0;
}

int len=0;/* 哈夫曼编码数 */
int deep=-1;/* 深度 */
void Preorder(struct TNode * p);/* 前序遍历 */
void byLeft(struct TNode*p)/* 经由左结点 */
{
deep++;
Hoffman[len][deep]=0;
Preorder(p);

Hoffman[len][deep]=2;
deep--;
}
void byRight(struct TNode*p)/* 经由右结点 */
{

deep++;
Hoffman[len][deep]=1;
Preorder(p);

Hoffman[len][deep]=2;
deep--;
}
void Preorder(struct TNode * p)
{

int i;
if(p->lNode!=0)/* 当左子结点非空则遍历 */
{

byLeft(p->lNode);
}
if(p->rNode!=0)/* 当右子结点非空则遍历 */
{
byRight(p->rNode);
}

if((p->lNode==0)&&(p->rNode==0))/* 当左右结点都为空，则增加哈夫曼编码数到另一个记录 */
{

Hoffman[len][deep+1]=2;
i=0;
for(;Hoffman[len][i]!=2;i++)
{
Hoffman[len+1][i]=Hoffman[len][i];
}
Hoffman[len+1][i]=2;

HoffmanList[len]=p->dictionary;

len++;
}

}

char generateOne(int k)/* 产生k个连续1的二进制串,比如111,1111,111111,用于编码进假设的文件 */
{
char c=0;
for(;k!=0;k--)
{
c|=(1<<(k-1));

}
return c;
}

int compareBits(char b1,char b2,char c,int l,int d)/* 判断由 [b1,b2] 组成的16位二进制数以d为起点,是否是长度为l的c二进制串（哈夫曼编码）的前缀 */
{
unsigned char t=(((((0x00ff&b1)<<8)|(0x00ff&b2))>>(8-d))&0x00ff);
return (((t)&((generateOne(l)<<(8-l))&0xff))==((c<<(8-l))&0xff));
}

int main()
{
struct LNode* t,*p;
struct LNode* head;
struct TNode *tempTNode,*k1;
int i=0,j,k;
unsigned short fileLen=0;
int len=0,l,b1,b2,d;
char c;
int code[500],h=0;
int codeLen=0,total=0;
/* 或许假定的文件字符串向量中的字符串 */

printf("please Enter string to be pressed:");
scanf("%s",&fileContent);

/* Hash进dictionary */

for(;fileContent[i]!='\0';i++,fileLen++)
{

++dictionary[fileContent[i]][0];
dictionary[fileContent[i]][1]=fileContent[i];
}

/* 把Hash了的dictionary向前靠拢 */

{

for(i=0;i!=MAXLIST;i++)
{

if(dictionary[i][0]!=0)
{
dictionary[len][0]=dictionary[i][0];
dictionary[len][1]=dictionary[i][1];
len++;
}
}
}
printf("the number of Huffman's codes:%d\n",len);
/* 对dictionary按权值进行排序 */

ShellSort(dictionary,len);

/* 构造链表,链表中放有序dictionary权值的树结点 */
head=(struct LNode*)malloc(sizeof(struct LNode)),p=head;
LNode_init(head);
head->next=(struct LNode*)malloc(sizeof(struct LNode));
LNode_init(head->next);

tempTNode=(struct TNode*)malloc(sizeof(struct LNode));
TNode_init(tempTNode,dictionary[0][1],dictionary[0][0]);
head->tnode=tempTNode;

{
for(i=0;i!=len-1;i++)
{
p->next->prev=p->next;
p=p->next;

p->next=(struct LNode*)malloc(sizeof(struct LNode));
LNode_init(p->next);

tempTNode=(struct TNode*)malloc(sizeof(struct TNode)) ;
TNode_init(tempTNode,dictionary[i+1][1],dictionary[i+1][0]);
p->tnode=tempTNode;
}
}
free(p->next);
p->next=0;

/* 每次最小权值的前面两个链表结点中的树结点组成一个子树,子树有合权值,子数的根按权值排序进链表*/

for(p=head;p->next!=0;)
{

p->tnode->pNode=(struct TNode*)malloc(sizeof(struct TNode)) ;
TNode_init(p->tnode->pNode,'\0',(p->tnode->weight)+(p->next->tnode->weight));

p->next->tnode->pNode=p->tnode->pNode;
p->tnode->pNode->lNode=p->tnode;
p->tnode->pNode->rNode=p->next->tnode;
head=p->next;
free(p);
p=head;
p->tnode=p->tnode->pNode;
for(t=head;t->next!=0;t=t->next)
{
if(t->tnode->weight>t->next->tnode->weight)
{
k1=t->tnode;
t->tnode=t->next->tnode;
t->next->tnode=k1;
}
}

}

/* 前序遍历构造哈夫曼编码 */
Preorder(p->tnode);

{
for(i=0;i!=len;i++)
dictionary[HoffmanList[i]][0]=i;
}
/* 存储字符串的哈夫曼压缩编码串,并且打包文件格式 */

{
for(i=0;i!=fileLen;i++)
{
int j=dictionary[fileContent[i]][0];
for(k=0;Hoffman[j][k]!=2;k++)
{

HoffFileCode[codeLen]|=(Hoffman[j][k]<<(7-total%8));
code[h++]=Hoffman[j][k];

if(((total+1)%8)==0)
{
HoffFile[1+len*3+1+codeLen]=HoffFileCode[codeLen];
codeLen++;
}
total++;
}

}
}
HoffFile[1+len*3+1+codeLen]=HoffFileCode[codeLen];
HoffFile[0]=(fileLen);

/* 解压缩假定的文件HoffFile成为原字符串序列 */
printf("Huffman's code list:\n");
HoffFile[1]=len;

{
for(i=0,j=0;i!=len;i++,j=0)
{

for(;Hoffman[i][j]!=2;j++);

HoffFile[i+2]=j;
HoffFile[i+2+2*len]=HoffmanList[i];

for( k=0;k!=j;k++)
{

printf("%d",Hoffman[i][k]);
HoffFile[i+2+len]|=(Hoffman[i][k]<<(j-1-k));

}
printf(":%d\n",HoffmanList[i]);

}
}

{
for(i=0,j=0;i!=(HoffFile[0]&0xff);i++)
{
for(k=0;k!=HoffFile[1];k++)
{

l=HoffFile[2+k],d=j%8,b1=HoffFile[j/8+2+HoffFile[1]*3],b2=HoffFile[j/8+1+2+HoffFile[1]*3];

c=HoffFile[HoffFile[1]+2+k];

if(compareBits(b1,b2,c,l,d))
{

j+=HoffFile[2+k];

GetFile[i]=HoffFile[2+HoffFile[1]*2+k];

break;

}
}

}
}
{
printf("Huffman code List Pressed :\n");
for(i=0;i!=h;i++)
{
printf("%c",code[i]);
if((i+1)%8==0)
printf(" ");
}
}
printf("\n");

{
printf("Huffman code packaged:\n");
for(i=0;i!=HoffFile[0]+HoffFile[1]*3;i++)
{
printf("%c",HoffFile[i]);
}
printf("\n");
}

printf("The initial len :%d\n",fileLen);
printf("The string len pressed:%d\n",(h)/8+1);
printf("The rate%.2f\%",((h/8.0+1)/fileLen)*100);

{

printf("The number of bytes:%d\n",(HoffFile[0]&0xff));
printf("The string decoded:");
for(i=0;i!=(HoffFile[0]&0xff);i++)
{
printf("%c",GetFile[i]);
}

printf("\n");

}
getch();
return 1;
}