本文目录一览：
- 1、怎么样用c语言程序编码哈夫曼树？
- 2、哈夫曼树的建立
- 3、哈夫曼树应用（C语言）
- 4、哈夫曼树的c语言编程，急急急！
- 5、关于C语言建立赫夫曼树的问题，我不是很明白，下面是代码：
- 6、数据结构中哈夫曼树的应用（C语言）
怎么样用c语言程序编码哈夫曼树？
#includestdio.h
#includestdlib.h
#includestring.h
#include ctype.h
#includelimits.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].weightkt[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(s1s2)
{
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); // 从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; icount; 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; ij; i++)
*(m+i)=0;
for(t=0; tj; t++)
{
for(i=0; icount; i++)
{
if(*(s2+t)==*(s1+i))
*(m+t)+=1;
}
}
for(i=0;ij;i++)
while(flag)
{
flag = 0;
for (t=0; tj-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;
}
哈夫曼树的建立
。。作业吧，运行可用，自己再试试。
//huffman_h.h 哈夫曼树的头文件
#include"iostream.h"
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
typedef char ElemType;
typedef struct{
ElemType elem;
unsigned int weight;
unsigned int parent,lchild,rchild,tag;
}HTNode,*HuffmanTree;
typedef char** HuffmanCode;
typedef int Status;
typedef struct weight
{
char elem;
unsigned int m_weight;
}Weight; // 保存符号信息;
void Select(HuffmanTree HT,int n,int s1,int s2)
{
int i;
s1=s2=0;
for(i=1;i=n;i++){
if(HT[i].weightHT[s2].weightHT[i].parent==0s2!=0){
if(HT[i].weightHT[s1].weight) {
s2=s1; s1=i; }
else s2=i;
}
if((s1==0||s2==0)HT[i].parent==0){
if(s1==0) s1=i;
else if(s2==0) {
if(HT[i].weightHT[s1].weight) {
s2=s1; s1=i; }
else s2=i;
} // end of else if
if(s1s2) {i=s1; s1=s2; s2=i;}
// end of if
// end of for
}
void HuffmanCoding(HuffmanTree HT, HuffmanCode HC, Weight* w, int n) {
// w存放n个字符的权值(均0)，构造哈夫曼树HT，
// 并求出n个字符的哈夫曼编码HC
//本函数实现选择方式：从左往右选择两个小权值结点，结点信息在前面的为左子树，其后为右子树
//修改选择方式：依序选择两个小权值结点，权值小的为左子树。！！
int i, j, m, s1,s2;
char *cd;
int p;
int cdlen;
if (n=1) return;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0号单元未用
for (i=1; i=n; i++) { //初始化
HT[i].elem=w[i-1].elem;
HT[i].weight=w[i-1].m_weight;
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;
}
printf("\n哈夫曼树的构造过程如下所示：\n");
printf("HT初态:\n 结点 weight parent lchild rchild");
for (i=1; i=m; i++)
printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight,
HT[i].parent,HT[i].lchild, HT[i].rchild);
printf(" 按任意键，继续 ...");
getchar();
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 = i; HT[s2].parent = i;
HT[i].lchild = s1; HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
printf("\nselect: s1=%d s2=%d\n", s1, s2);
printf(" 结点 weight parent lchild rchild");
for (j=1; j=i; j++)
printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,
HT[j].parent,HT[j].lchild, HT[j].rchild);
printf(" 按任意键，继续 ...");
getchar();
}//for
//------无栈非递归遍历哈夫曼树，求哈夫曼编码
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
cd = (char *)malloc((n+1)*sizeof(char)); // 分配求编码的工作空间
p = m; cdlen = 0;
for (i=1; i=m; ++i) // 遍历哈夫曼树时用作结点状态标志
HT[i].tag = 0;
while (p) {
if (HT[p].tag==0) { // 向左
HT[p].tag = 1;
if (HT[p].lchild != 0) { p = HT[p].lchild; cd[cdlen++] ='0'; }
else if (HT[p].rchild == 0) { // 登记叶子结点的字符的编码
HC[p] = (char *)malloc((cdlen+1) * sizeof(char));
cd[cdlen] ='\0'; strcpy(HC[p], cd); // 复制编码(串)
}
} else if (HT[p].tag==1) { // 向右
HT[p].tag = 2;
if (HT[p].rchild != 0) { p = HT[p].rchild; cd[cdlen++] ='1'; }
} else { // HT[p].weight==2，退回退到父结点，编码长度减1
HT[p].tag = 0; p = HT[p].parent; --cdlen;
}//else
}//while
} // HuffmanCoding
/*
//--- 从叶子到根逆向求每个字符的哈夫曼编码 ---
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] = '0';
else cd[--start] = '1';
HC[i] = (char *)malloc((n-start)*sizeof(char));
// 为第i个字符编码分配空间
strcpy(HC[i], cd); // 从cd复制编码(串)到HC
}
free(cd); // 释放工作空间
*/
void OutputHuffmanCode(HuffmanTree HT,HuffmanCode HC,int n)
{
int i;
printf("\nnumber---element---weight---huffman code\n");
for(i=1;i=n;i++)
printf(" %d %c %d %s\n",i,HT[i].elem,HT[i].weight,HC[i]);
}
//主函数
//huffman.cpp
#include"huffman_h.h"
void main()
{
HuffmanTree HT;
HuffmanCode HC;
Weight *w;
char c; // the symbolizes;
int i,n; // the number of elements;
int wei; // the weight of a element;
printf("请输入构建哈夫曼树的结点数:" );
cinn; //coutendl;
w=(Weight *)malloc(n*sizeof(Weight));
for(i=0;in;i++)
{
//cout"请输入第"i+1"个结点编号及其权值（如a 100）:"endl;
printf("请输入结点编号及其权值（如a 100）:" );
scanf("%1s%d",c,wei);
w[i].elem=c;
w[i].m_weight=wei;
}
HuffmanCoding(HT,HC,w,n);
OutputHuffmanCode(HT,HC,n);
}
哈夫曼树应用（C语言）
Huffman(C)
Input: C一组节点，节点中储存了字符以及该字符在文件中出现的频率
Output: Huffman树的根节点
Algorithm:
n=length(C)
insert(Q,C) //注：把C中的每一个节点都插入minHeap中
for i 从0到n-2 do
创建一个新的空节点z
z.leftchild=x=extract-min(Q)
z.rightchild=y=extract-min(Q)
z.frequence=x.frequence+y.frequence
insert(Q,z)
end for
return extract-min(Q)
如图所示，因为每次都取出2个最小的节点，然后合并它们。所以第一次选择C和D合并为新的节点它的频率是2。然后把这个新节点插入Q。而B和R的频率都是2，和新的节点频率相同，根据不同的min-heap算法，在此处可能有所不同。本例选择的是先入先出，因此先合并B和R得到一个新节点4。之后再取出2个最小的节点，即新的2和新的4，合并它们得到新节点6。最后合并节点A和新节点6得到根节点11。
哈夫曼树的c语言编程，急急急！
我写的你看下！！有什么问题可以交流下！！！
#include stdio.h
#includestring.h
#define N 26
typedef struct
{
int W,P,R,L;
}HTNode;
typedef struct
{
char ch;
char code[10];
}HTCode;
HTCode HC[27];
void select(HTNode HT[],int *min1,int *min2,int *a,int *b)
{
int i;int mina=100,minb=100;
int m,n;
for(i=1;i=2*N-1;i++)
{
if(HT[i].WminaHT[i].P==0HT[i].W)
{
mina=HT[i].W;
m=i;
}
if(HT[i].WminbHT[i].P==0HT[i].Wi!=m)
{
minb=HT[i].W;
n=i;
}
}
*min1=mina;
*min2=minb;
*a=m;
*b=n;
}
void Ecode(HTNode HT[])
{
char temp[10];
int i,j,k;
int c,ff;
for(i=1;i=26;i++)
HC[i].ch=96+i;
for(i=1;i=N;i++)
{ j=0;
for(c=i,ff=HT[c].P;ff;c=ff,ff=HT[c].P)
{
if(HT[ff].L==c) {temp[j]='0';j++;}
else {temp[j]='1';j++;}
}
j--;
for(k=0;k=j;k++)
HC[i].code[k]=temp[j-k];
HC[i].code[k]='\0';
}
printf("以下为各字母的哈弗曼编码：\n");
for(i=1;i=26;i++)
printf("%c: %s\n",HC[i].ch,HC[i].code);
}
void Displaycode(HTCode HC[])
{
char ch;int i;
printf("请输入字符串：\n");
while((ch=getchar())!=EOFch!='\n')
{
for(i=1;i=26;i++)
if(ch==HC[i].ch)
{
printf("%s",HC[i].code);
break;
}
}
}
void main()
{
HTNode HT[2*N-1];
int min1=100,min2=100;
int i,j,a=0,b=0;
int w[27]={0,8,3,2,4,2,2,1,3,4,2,3,2,1,5,3,3,2,1,2,5,3,3,3,2,3,6};
//各节点初始化。
for(i=1;i=N;i++)
{
HT[i].W=w[i];
HT[i].P=0;
HT[i].L=0;
HT[i].R=0;
}
//剩余节点初始化。
for(i=N+1;i=2*N-1;i++)
{
HT[i].W=0;
HT[i].P=0;
HT[i].L=0;
HT[i].R=0;
}
for(j=N+1;j=2*N-1;j++)
{
select(HT,min1,min2,a,b);
HT[j].W=min1+min2;
HT[j].L=a;
HT[j].R=b;
HT[a].P=j;
HT[b].P=j;
}
Ecode(HT);
Displaycode(HC);
getchar();
}
关于C语言建立赫夫曼树的问题，我不是很明白，下面是代码：
下面是我写程序的时候的注释，两种方法都写上了。这个程序不能运行，主要是为了理解，注释写的很清楚的。
/*这只是讲解，程序并不能运行*/
#includestdio.h
#includestdlib.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(mina[i])
{
s2=s1;
s1=i;
}
for(i=s1;in;++i)
a[i]=a[i+1];
for(i=s2;in;++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语言）
#includestdio.h
#includestdlib.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;i2*n-1;i++)
{
if(in)
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;in-1;i++)
{
m1=m2=MaxValue;
x1=x2=0;
for(j=0;jn+i;j++)
{
if(haffTree[j].weightm1haffTree[j].flag==0)
{
m2=m1;
x2=x1;
m1=haffTree[j].weight;
x1=j;
}
else if(haffTree[j].weightm2haffTree[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;in;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;jn;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;in;i++)
printf(" ");
if(bt-data!=0bt-data100)
{
if(n0)
{
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]im)
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]im) /*查找失败返回数字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;p1word+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;jn;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;kn;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;p1word+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;p3weight+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(nMaxN)
{
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;in;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;p2weight+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!=1w!=2w!=3w!=4w!=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();
}
