主题:[原创]哈夫曼树极其代码(VC6.0)
/////////////stack.h//////////////////////////////
#ifndef HEAD01_FILE //避免头文件的重复包含
#define HEAD01_FILE
/////////////////////
#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
#define TEST printf("her is OK!!\n");
typedef struct N{
int data;
struct N *next;
struct N*per;
}stacknode,*PN;//栈的结点
typedef struct S{ //栈的属性
PN base;
PN top; //为栈顶元素//有数据
int lenth;
char *remark;//备注
}Stack,*PS;
void InitStack(Stack &st,char *str){
st.base=st.top=(PN)malloc(sizeof(stacknode));
st.lenth=0;
st.remark=(char*)malloc(sizeof(char)*32);
strcpy(st.remark,str);
}
int Pop(Stack &st) //弹出元素
{ int d;
if(st.lenth!=0){
st.top=st.top->per;
free(st.top->next);
d=st.top->data;
st.lenth-=1;
}
else d=-1; //表示空栈
return d;
}
void Push(Stack &st,int d) //
{
st.top->data=d;
st.top->next=(PN)malloc(sizeof(stacknode));
st.top->next->per=st.top;
st.top=st.top->next;
st.lenth+=1;
}
void outputstack(Stack st)
{
PN p;
p=st.base;
for(int i=0;i<st.lenth;i++,p=p->next)
printf("**%d** : [ %d ]\n",i+1,p->data);
}
#endif
///////////head01.h/////////////////
#ifndef HEAD_FILE01
#define HEAD_FILE01
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<stdlib.h>
#include<windows.h>
#include"stack.h"
////////////////
typedef struct T{ //树结点定义
char data; //数据
int cost; //权
int parent; //父母
int lchild; //左孩子
int rchild; //右孩子
}TreeNode,*Huftree;
typedef struct C{
char c; //字符
int cost; //权重
}charlist,*pcharlist;
//////////////////////////////////// 主要函数
pcharlist change(char *str,int &longth);//由字符串生成带权的字符集表//longth:字符集表长度
void madetree(Huftree &tree,pcharlist l,int longth);//由带权的字符集表生成树~~~什么时候开花结果~~
void Select(Huftree ,int longth,int &s1,int &s2);//在带权的森林中找出权最小的两个树(s1<=s2)
char* changetocode(char *str,Huftree tree);//由树生成编码~~~~~~~~什么时候能做好~~~~~~
//////////////////////////////////////辅助函数
int Findchar(char *str,char c);//从字符串中查找字符 返回字符数量
void Deletechar(pcharlist l,int &longth,int s1,int s2);//在带权的字符集表中最小的两个值合并权相加
void outputtree(Huftree); //输出树//
Stack loadtree(Huftree tree,int n,char *str);//遍历树//返回树的结点//递归调用//未定义
void treetext(Huftree tree);//将哈夫曼树生成文本文件并保存//用于解码用
int loadcode(Stack &st,Huftree tree,int n,char c);//在树中查找C并将对应的编码入栈
void outputstack(Stack st);//输出栈的信息
void begin();//程序运行函数;
#endif
////////////////FUNCTION.CPP///////
#include"head01.h"
///////////////////////////////
// //
///////////////////////////////
pcharlist change(char *str,int &longth)//由字符串生成带权的字符集表//longth:字符集表长度
{
int i=0,j=0;
char *s;
pcharlist list1;
s=(char*)malloc(sizeof(char)*strlen(str));
for(;i<strlen(str);i++) //遍历字符串//找出不相同的字符生成新串s
if(!Findchar(s,str[i]))
{
s[j]=str[i];
j++;
}
longth=j;
list1=(pcharlist)malloc(sizeof(charlist)*(j));//这句为什么曾经错误 很严重耶
for(i=0;i<j;i++){
(list1+i)->c=s[i];
(list1+i)->cost=Findchar(str,s[i]);
}
return list1;
}
/////////////////////////////
void madetree(Huftree &tree,pcharlist l,int longth)//由带权的字符集表生成树~~~什么时候开花结果~~
{
int i,j=0;
int s1,s2,len;
len=2*longth;
tree=(Huftree)malloc(sizeof(TreeNode)*(len));
for(i=longth;i<len;i++){//将字符生成只有一个根的树放在longth-1 ~~~2*longth-1中
//根的父母为[0] 孩子的父母是对tree的相对位移(整数)//刚好存放字符集表
(tree+i)->cost=(l+j)->cost;
(tree+i)->data=(l+j)->c;
(tree+i)->lchild=0;
(tree+i)->parent=0;
(tree+i)->rchild=0;
j++;
} //for
for(i=1;i<longth;i++){ //longth-1个空间//刚好存放树枝
Select(tree,len,s1,s2);
(tree+i)->lchild=s1;
(tree+i)->rchild=s2;
(tree+s1)->parent=i;
(tree+s2)->parent=i;
(tree+i)->parent=0;
(tree+i)->cost=(tree+s1)->cost+(tree+s2)->cost;
//printf("我是:[ %d ] \n",i);printf("左孩子:[%d] 右孩子:[%d]\n",(tree+i)->lchild,(tree+i)->rchild);
}//哈夫曼树的根放在 len/2-1 位置// for(i=9;i<5555;i++) Sleep(11111);
tree->lchild=longth-1;
tree->rchild=0;
tree->parent=0;
tree->cost=len;//////////////////////
printf("%d++++",len);
}
void Select(Huftree tree,int len,int &s1,int &s2)//在带权的森林中找出权最小的两个树(s1<s2)
{
int i,k=0;
s1=0;s2=0;
for(i=1;i<len;i++){
if(((tree+i)->parent==0)&&(tree+i)->cost>=k){
s1=i;//s1记录大的
k=(tree+s1)->cost;
}
}
s2=s1;
for(i=1;i<len;i++){
if(((tree+i)->parent==0)&&(tree+i)->cost<=(tree+s1)->cost)
s1=i;
}//for
for(i=1;i<len;i++){
if(((tree+i)->parent==0)&&(tree+i)->cost<=(tree+s2)->cost)
if(s1!=i) s2=i;
}//for
}
void Deletechar(pcharlist l,int &longth,int s1,int s2)//在带权的字符集表中最小的两个值合并权相加
{
(l+s1)->cost+=(l+s2)->cost;
(l+s1)->c=0; //表示为树枝交叉
(l+s2)->c=(l+longth)->c;
(l+s2)->cost=(l+longth)->cost;
longth--;
}
int Findchar(char *str,char c)//从字符串中查找字符 返回字符数量
{
int i,l,k=0;
l=strlen(str);
for(i=0;i<l;i++){
if(str[i]==c) k++;
}
return k;
}
void outputtree(Huftree tree) //输出树//返回树的结点//递归调用
{
int i,l;
l=tree[0].data;
for(i=0;i<l;i++)
{
if(tree[i].lchild!=0){//树
printf("**[%d]**:I'm a [tree] and",i+1);
printf("my name is [%c],my parents'no. is [%d]\n",tree[i].data,tree[i].parent);
printf("my first child's no. is [] the other one is [%d]",tree[i].lchild,tree[i].rchild);
}//if
else { //叶
//printf("**[%d]**:I'm a [leafage] and",i+1);
printf("my name is [%c],my parents'no. is [%d]\n",tree[i].data,tree[i].parent);
}//else
}//for
}
Stack loadtree(Huftree tree,int n,char *str)//由字符串生成编码//放在栈中并返回//
{
int i,len;
len=strlen(str);
Stack st;
InitStack(st,"Haffcode");
for(i=0;i<len;i++){
//printf("%d]]字符:%c\n",i+1,str[i]);
loadcode(st,tree,tree->lchild,str[i]);
}
return st;
}
int loadcode(Stack &st,Huftree tree,int n,char c)//在树中查找C并将对应的编码入栈//这个函数有点头大哦
{
if((tree+n)->data==c){
//printf("已经找到\n");
//outputstack(st);
return 2;
}
if((tree+n)->lchild!=0){
Push(st,0); //printf("我左孩子是:%d\n",(tree+n)->lchild);
if(loadcode(st,tree,(tree+n)->lchild,c)==2)
return 2;
else
Pop(st);
}
if((tree+n)->rchild!=0){
Push(st,1);// printf("我右孩子是:%d\n",(tree+n)->rchild);
if(loadcode(st,tree,(tree+n)->rchild,c)==2)
return 2;
else
Pop(st);
}
return 1;
}
void treetext(Huftree tree)//将哈夫曼树生成文本文件并保存//用于解码用
{
int i,l;
FILE* treefile;
treefile=fopen("treecode.txt","wt");
fputc(tree->cost,treefile);//整数不用转化直接储存
l=tree->cost;
//因为一般树的储存长度小于122
for(i=0;i<l;i++) //这里不关心权重
{
fputc((tree+i)->lchild,treefile);//顺序为左孩子
fputc((tree+i)->rchild,treefile);//右孩子
fputc((tree+i)->parent,treefile);//父母
fputc((tree+i)->data,treefile);//字符值
}
}
void begin()//程序运行函数
{
printf("********************************************************************************");
system("color 4a");
Stack st;
Huftree tree;
pcharlist charlist;
int listlong;
char *str;
char path[64],goodpath[64];
int lenth;
FILE *handle,*gfile;
printf(" 请输入原文件路径: ");
scanf("%s",path);
printf(" 输入目标文件路径: ");
scanf("%s",goodpath);
handle=fopen(path,"rt"); //打开文件
gfile=fopen(goodpath,"wt");
fseek(handle,0,SEEK_END); //
lenth=ftell(handle); //取文件长度
lenth+=1;
str=(char*)malloc(sizeof(char)*lenth);//多一个字节//存放'\0'
rewind(handle); //文件指针回打文件开始
fgets(str,lenth,handle); //将文件内容存入str
charlist=change(str,listlong);
madetree(tree,charlist,listlong);
st=loadtree(tree,0,str);
//outputstack(st);//输出栈的信息//将栈中的每8个二进制数据转化为一个字符存放
///////////////////////////////////////////////////
int l,i;
l=st.lenth;
PN p;
p=st.base;
for(i=0;i<l;i++){
fputc(p->data+48,gfile);
p=p->next;
}
printf("\n\n");
//outputstack(st);
printf(" 编码完成 编码文件存放在 %s \n\n\n",goodpath);
treetext(tree);
printf("********************************************************************************\n\n\n");
}
void main()
{
begin();
}
//附:将整数转化为字符串的函数:itoa(,,);
//字符转化为整数 : atoi( );
//共3个文件
//自己做的哈夫曼树
//大家交流交流
//由英语文本文件生成二进制编码存放在另一个文件中
//注意:原文件须在项目工程文件夹下
//生成的编码文件也在项目工程文件夹下
#ifndef HEAD01_FILE //避免头文件的重复包含
#define HEAD01_FILE
/////////////////////
#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
#define TEST printf("her is OK!!\n");
typedef struct N{
int data;
struct N *next;
struct N*per;
}stacknode,*PN;//栈的结点
typedef struct S{ //栈的属性
PN base;
PN top; //为栈顶元素//有数据
int lenth;
char *remark;//备注
}Stack,*PS;
void InitStack(Stack &st,char *str){
st.base=st.top=(PN)malloc(sizeof(stacknode));
st.lenth=0;
st.remark=(char*)malloc(sizeof(char)*32);
strcpy(st.remark,str);
}
int Pop(Stack &st) //弹出元素
{ int d;
if(st.lenth!=0){
st.top=st.top->per;
free(st.top->next);
d=st.top->data;
st.lenth-=1;
}
else d=-1; //表示空栈
return d;
}
void Push(Stack &st,int d) //
{
st.top->data=d;
st.top->next=(PN)malloc(sizeof(stacknode));
st.top->next->per=st.top;
st.top=st.top->next;
st.lenth+=1;
}
void outputstack(Stack st)
{
PN p;
p=st.base;
for(int i=0;i<st.lenth;i++,p=p->next)
printf("**%d** : [ %d ]\n",i+1,p->data);
}
#endif
///////////head01.h/////////////////
#ifndef HEAD_FILE01
#define HEAD_FILE01
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<stdlib.h>
#include<windows.h>
#include"stack.h"
////////////////
typedef struct T{ //树结点定义
char data; //数据
int cost; //权
int parent; //父母
int lchild; //左孩子
int rchild; //右孩子
}TreeNode,*Huftree;
typedef struct C{
char c; //字符
int cost; //权重
}charlist,*pcharlist;
//////////////////////////////////// 主要函数
pcharlist change(char *str,int &longth);//由字符串生成带权的字符集表//longth:字符集表长度
void madetree(Huftree &tree,pcharlist l,int longth);//由带权的字符集表生成树~~~什么时候开花结果~~
void Select(Huftree ,int longth,int &s1,int &s2);//在带权的森林中找出权最小的两个树(s1<=s2)
char* changetocode(char *str,Huftree tree);//由树生成编码~~~~~~~~什么时候能做好~~~~~~
//////////////////////////////////////辅助函数
int Findchar(char *str,char c);//从字符串中查找字符 返回字符数量
void Deletechar(pcharlist l,int &longth,int s1,int s2);//在带权的字符集表中最小的两个值合并权相加
void outputtree(Huftree); //输出树//
Stack loadtree(Huftree tree,int n,char *str);//遍历树//返回树的结点//递归调用//未定义
void treetext(Huftree tree);//将哈夫曼树生成文本文件并保存//用于解码用
int loadcode(Stack &st,Huftree tree,int n,char c);//在树中查找C并将对应的编码入栈
void outputstack(Stack st);//输出栈的信息
void begin();//程序运行函数;
#endif
////////////////FUNCTION.CPP///////
#include"head01.h"
///////////////////////////////
// //
///////////////////////////////
pcharlist change(char *str,int &longth)//由字符串生成带权的字符集表//longth:字符集表长度
{
int i=0,j=0;
char *s;
pcharlist list1;
s=(char*)malloc(sizeof(char)*strlen(str));
for(;i<strlen(str);i++) //遍历字符串//找出不相同的字符生成新串s
if(!Findchar(s,str[i]))
{
s[j]=str[i];
j++;
}
longth=j;
list1=(pcharlist)malloc(sizeof(charlist)*(j));//这句为什么曾经错误 很严重耶
for(i=0;i<j;i++){
(list1+i)->c=s[i];
(list1+i)->cost=Findchar(str,s[i]);
}
return list1;
}
/////////////////////////////
void madetree(Huftree &tree,pcharlist l,int longth)//由带权的字符集表生成树~~~什么时候开花结果~~
{
int i,j=0;
int s1,s2,len;
len=2*longth;
tree=(Huftree)malloc(sizeof(TreeNode)*(len));
for(i=longth;i<len;i++){//将字符生成只有一个根的树放在longth-1 ~~~2*longth-1中
//根的父母为[0] 孩子的父母是对tree的相对位移(整数)//刚好存放字符集表
(tree+i)->cost=(l+j)->cost;
(tree+i)->data=(l+j)->c;
(tree+i)->lchild=0;
(tree+i)->parent=0;
(tree+i)->rchild=0;
j++;
} //for
for(i=1;i<longth;i++){ //longth-1个空间//刚好存放树枝
Select(tree,len,s1,s2);
(tree+i)->lchild=s1;
(tree+i)->rchild=s2;
(tree+s1)->parent=i;
(tree+s2)->parent=i;
(tree+i)->parent=0;
(tree+i)->cost=(tree+s1)->cost+(tree+s2)->cost;
//printf("我是:[ %d ] \n",i);printf("左孩子:[%d] 右孩子:[%d]\n",(tree+i)->lchild,(tree+i)->rchild);
}//哈夫曼树的根放在 len/2-1 位置// for(i=9;i<5555;i++) Sleep(11111);
tree->lchild=longth-1;
tree->rchild=0;
tree->parent=0;
tree->cost=len;//////////////////////
printf("%d++++",len);
}
void Select(Huftree tree,int len,int &s1,int &s2)//在带权的森林中找出权最小的两个树(s1<s2)
{
int i,k=0;
s1=0;s2=0;
for(i=1;i<len;i++){
if(((tree+i)->parent==0)&&(tree+i)->cost>=k){
s1=i;//s1记录大的
k=(tree+s1)->cost;
}
}
s2=s1;
for(i=1;i<len;i++){
if(((tree+i)->parent==0)&&(tree+i)->cost<=(tree+s1)->cost)
s1=i;
}//for
for(i=1;i<len;i++){
if(((tree+i)->parent==0)&&(tree+i)->cost<=(tree+s2)->cost)
if(s1!=i) s2=i;
}//for
}
void Deletechar(pcharlist l,int &longth,int s1,int s2)//在带权的字符集表中最小的两个值合并权相加
{
(l+s1)->cost+=(l+s2)->cost;
(l+s1)->c=0; //表示为树枝交叉
(l+s2)->c=(l+longth)->c;
(l+s2)->cost=(l+longth)->cost;
longth--;
}
int Findchar(char *str,char c)//从字符串中查找字符 返回字符数量
{
int i,l,k=0;
l=strlen(str);
for(i=0;i<l;i++){
if(str[i]==c) k++;
}
return k;
}
void outputtree(Huftree tree) //输出树//返回树的结点//递归调用
{
int i,l;
l=tree[0].data;
for(i=0;i<l;i++)
{
if(tree[i].lchild!=0){//树
printf("**[%d]**:I'm a [tree] and",i+1);
printf("my name is [%c],my parents'no. is [%d]\n",tree[i].data,tree[i].parent);
printf("my first child's no. is [] the other one is [%d]",tree[i].lchild,tree[i].rchild);
}//if
else { //叶
//printf("**[%d]**:I'm a [leafage] and",i+1);
printf("my name is [%c],my parents'no. is [%d]\n",tree[i].data,tree[i].parent);
}//else
}//for
}
Stack loadtree(Huftree tree,int n,char *str)//由字符串生成编码//放在栈中并返回//
{
int i,len;
len=strlen(str);
Stack st;
InitStack(st,"Haffcode");
for(i=0;i<len;i++){
//printf("%d]]字符:%c\n",i+1,str[i]);
loadcode(st,tree,tree->lchild,str[i]);
}
return st;
}
int loadcode(Stack &st,Huftree tree,int n,char c)//在树中查找C并将对应的编码入栈//这个函数有点头大哦
{
if((tree+n)->data==c){
//printf("已经找到\n");
//outputstack(st);
return 2;
}
if((tree+n)->lchild!=0){
Push(st,0); //printf("我左孩子是:%d\n",(tree+n)->lchild);
if(loadcode(st,tree,(tree+n)->lchild,c)==2)
return 2;
else
Pop(st);
}
if((tree+n)->rchild!=0){
Push(st,1);// printf("我右孩子是:%d\n",(tree+n)->rchild);
if(loadcode(st,tree,(tree+n)->rchild,c)==2)
return 2;
else
Pop(st);
}
return 1;
}
void treetext(Huftree tree)//将哈夫曼树生成文本文件并保存//用于解码用
{
int i,l;
FILE* treefile;
treefile=fopen("treecode.txt","wt");
fputc(tree->cost,treefile);//整数不用转化直接储存
l=tree->cost;
//因为一般树的储存长度小于122
for(i=0;i<l;i++) //这里不关心权重
{
fputc((tree+i)->lchild,treefile);//顺序为左孩子
fputc((tree+i)->rchild,treefile);//右孩子
fputc((tree+i)->parent,treefile);//父母
fputc((tree+i)->data,treefile);//字符值
}
}
void begin()//程序运行函数
{
printf("********************************************************************************");
system("color 4a");
Stack st;
Huftree tree;
pcharlist charlist;
int listlong;
char *str;
char path[64],goodpath[64];
int lenth;
FILE *handle,*gfile;
printf(" 请输入原文件路径: ");
scanf("%s",path);
printf(" 输入目标文件路径: ");
scanf("%s",goodpath);
handle=fopen(path,"rt"); //打开文件
gfile=fopen(goodpath,"wt");
fseek(handle,0,SEEK_END); //
lenth=ftell(handle); //取文件长度
lenth+=1;
str=(char*)malloc(sizeof(char)*lenth);//多一个字节//存放'\0'
rewind(handle); //文件指针回打文件开始
fgets(str,lenth,handle); //将文件内容存入str
charlist=change(str,listlong);
madetree(tree,charlist,listlong);
st=loadtree(tree,0,str);
//outputstack(st);//输出栈的信息//将栈中的每8个二进制数据转化为一个字符存放
///////////////////////////////////////////////////
int l,i;
l=st.lenth;
PN p;
p=st.base;
for(i=0;i<l;i++){
fputc(p->data+48,gfile);
p=p->next;
}
printf("\n\n");
//outputstack(st);
printf(" 编码完成 编码文件存放在 %s \n\n\n",goodpath);
treetext(tree);
printf("********************************************************************************\n\n\n");
}
void main()
{
begin();
}
//附:将整数转化为字符串的函数:itoa(,,);
//字符转化为整数 : atoi( );
//共3个文件
//自己做的哈夫曼树
//大家交流交流
//由英语文本文件生成二进制编码存放在另一个文件中
//注意:原文件须在项目工程文件夹下
//生成的编码文件也在项目工程文件夹下