哈夫曼樹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;
}