哈夫曼树编码c语言代码（求C语言C++高手赐教额~~~关于哈夫曼树的程序~~>.< 急求~~一定要可以运行的噢~）

本文目录

• 求C语言C++高手赐教额~~~关于哈夫曼树的程序~~>.< 急求~~一定要可以运行的噢~
• 赫夫曼OR哈弗曼编码 c语言 数据结构 简单的程序设计
• 哈夫曼编码C语言实现
• c语言哈夫曼树哈夫曼编码纠错
• 哈夫曼编码的C语言源代码

求C语言C++高手赐教额~~~关于哈夫曼树的程序~~>.< 急求~~一定要可以运行的噢~

/*说实话，哈夫曼树的编码有点难度，这个代码是我花了三四个小时写的，
不能完全满足你的要求，但是可以进行哈夫曼编码，你试着向你题目的要求改一下吧。*/
#include《iostream.h》
#include《iomanip.h》
#define N 5
#define M 2*N-1
typedef struct HF_Node
{
double weight;
int lchild;
int rchild;
int parent;
}HTNODE;
typedef struct Node
{
int x;
Node *lchild;
Node *rchild;
}*BTree;
typedef HTNODE HuffmanT;
bool Is_Empty(BTree root)
{
if(root)
return false;
return true;
}
void Visit(BTree root) //访问二叉树的结点
{
cout《《root-》x《《" ";
}
void Print(HuffmanT T) //以数组的形式输出哈夫曼树
{
for(int i=0;i《M;++i)
{
cout《《setw(4)《《T.rchild《《endl;
}
}
void InitHT(HuffmanT T)
{
for(int i=0;i《M;++i)
{
T.parent=-1;
T.weight=0;
}
T.weight=0.25; //书上例题，已经初始化好，
}
void SelectMin(HuffmanT T,int n,int &p,int &q)
{
int i,j;
for(i=0;i《=n;++i)
{
if(T.parent==-1)
{
p=1;
break;
}
}
for(j=i+1;j《=n;++j)
{
if(T.parent==-1)
{
q=j;
break;
}
}
for(i=0;i《=n;++i)
{
if((T.parent==-1)&&(q!=i))
p=i;
}
for(j=0;j《=n;++j)
{
if((T.parent==-1)&&(p!=j))
q=j;
}
}
void Create_HT(HuffmanT T) //创建哈夫曼树
{
int i,p,q;
InitHT(T);
for(i=N;i《M;++i)
{
SelectMin(T,i-1,p,q);
T.parent=i;
T.lchild=p;
T.rchild=q;
T.weight;
}
}
void Create_BTree(BTree &root) //以先序递归建立二叉树
{
int x;
root=0;
cout《《"请输入数据，以-1结束："《《endl;
cin》》x;
if(x==-1)
return;
root = new Node;
root-》x=x;
root-》lchild=0;
root-》rchild=0;
Create_BTree(root-》lchild);
Create_BTree(root-》rchild);
}
void InOrder(BTree root) //以中序遍历二叉树
{
if(!Is_Empty(root))
{
InOrder(root-》lchild);
Visit(root);
InOrder(root-》rchild);
}
}
void PostOrder(BTree root)
{
if(!Is_Empty(root))
{
PostOrder(root-》lchild);
PostOrder(root-》rchild);
Visit(root);
}
}
void Distroy_BTree(BTree &root) //以后序遍历删除二叉树
{
if(!Is_Empty(root))
{
Distroy_BTree(root-》lchild);
Distroy_BTree(root-》rchild);
delete root;
}
root=0; //为了防止指针出现错误，最好加上
}
void HF_PreOrder(HuffmanT T,int i) //哈夫曼树的所有内节点都有两个孩子，都经过扩充,先序遍历
{
if(T.rchild==-1)
{
cout《《T.weight《《endl;
return;
}
cout《《T.weight《《endl;
i=T.lchild;
HF_PreOrder(T,i);
i=T.parent; //访问完左子树之后通过其双亲结点访问其右兄弟，必须通过双亲结点才能找到右兄弟
i=T.lchild使i的值不断变化，且回溯后不能变为递归之前的状态
HF_PreOrder(T,i);
}
void HF_InOrder(HuffmanT T,int i) //中序遍历
{
if(T.rchild==-1)
{
cout《《T.weight《《endl;
return;
}
i=T.lchild;
HF_InOrder(T,i);
i=T.parent; //必须在此处找到双亲结点
cout《《T.weight《《endl; //访问双亲结点
i=T.rchild; //因为i已经为双亲结点，所以不必找双亲结点了
HF_InOrder(T,i);
}
void HF_PostOrder(HuffmanT T,int i) //后序遍历
{
if(T.rchild==-1)
{
cout《《T.weight《《endl;
return;
}
i=T.lchild;
HF_PostOrder(T,i);
i=T.parent; //必须在此处找到双亲结点

i=T.rchild; //通过双亲结点找到右兄弟
HF_PostOrder(T,i);

i=T.parent; //左右结点都访问结束后访问双亲结点，再找双亲结点
cout《《T.weight《《endl; //访问双亲结点
}
void HuffmanCode(HuffmanT T) //构造哈弗曼编码
{

int p; //找双亲结点
int i=0,j=0;
for(i=0;i《N;++i)
{
cout《《setw(4)《《T.weight《《": ";
j=i;
p=T.parent;
while(p!=-1)
{
if(T.lchild==j) //如果为双亲结点的左孩子，则输出0
cout《《"0";
if(T.rchild==j) //如果为双亲结点的右孩子，则输出1
cout《《"1";
j=p; //保存当前结点
p=T.parent; //找到当前结点的双亲结点
}
cout《《endl;
}
}
void main()
{
HuffmanT T;
Create_HT(T);
Print(T);
cout《《"先序遍历："《《endl;
HF_PreOrder(T,M-1);
cout《《endl;
cout《《"中序遍历："《《endl;
HF_InOrder(T,M-1);
cout《《endl;
cout《《"后序遍历："《《endl;
HF_PostOrder(T,M-1);
cout《《endl;
cout《《"哈夫曼编码："《《endl;
HuffmanCode(T);
BTree BT;
Create_BTree(BT);
InOrder(BT);
cout《《endl;
Distroy_BTree(BT);
}

赫夫曼OR哈弗曼编码 c语言 数据结构 简单的程序设计

#include 《stdio.h》
#include 《stdlib.h》
#include 《string.h》
#define N 100
#define M 2*N-1
typedef char * HuffmanCode;//haffman编码
typedef struct
{
int weight;//权值
int parent;//父节节点
int LChild;//左子节点
int RChild;//右子节点
}HTNode,Huffman;//huffman树
typedef struct Node
{
int weight; //叶子结点的权值
char c; //叶子结点
int num; //叶子结点的二进制码的长度
}WNode,WeightNode;

/***产生叶子结点的字符和权值***/
void CreateWeight(char ch,int *s,WeightNode CW,int *p)
{
int i,j,k;
int tag;
*p=0;//叶子节点个数
//统计字符出现个数,放入CW
for(i=0;ch!=’\0’;i++)
{
tag=1;
for(j=0;j《i;j++)
if(ch)
{
tag=0;
break;
}
if(tag)
{
CW;
CW.weight=1;
for(k=i+1;ch!=’\0’;k++)
if(ch)
CW.weight++;//权值累加
}
}
*s=i;//字符串长度
}
/********创建HuffmanTree********/
void CreateHuffmanTree(Huffman ht,WeightNode w,int n)
{
int i,j;
int s1,s2;
//初始化哈夫曼树
for(i=1;i《=n;i++)
{
ht.weight;
ht.parent=0;
ht.LChild=0;
ht.RChild=0;
}
for(i=n+1;i《=2*n-1;i++)
{
ht.weight=0;
ht.parent=0;
ht.LChild=0;
ht.RChild=0;
}
for(i=n+1;i《=2*n-1;i++)
{
for(j=1;j《=i-1;j++)
if(!ht.parent)
break;
s1=j; //找到第一个双亲不为零的结点
for(;j《=i-1;j++)
if(!ht.parent)
s1=ht.weight?j:s1;
ht.parent=i;
ht.LChild=s1;
for(j=1;j《=i-1;j++)
if(!ht.parent)
break;
s2=j; //找到第二个双亲不为零的结点
for(;j《=i-1;j++)
if(!ht.parent)
s2=ht.weight?j:s2;
ht.parent=i;
ht.RChild=s2;
ht.weight;//权值累加
}
}
/***********叶子结点的编码***********/
void CrtHuffmanNodeCode(Huffman ht,char ch,HuffmanCode h,WeightNode weight,int m,int n)
{
int i,c,p,start;
char *cd;
cd=(char *)malloc(n*sizeof(char));
cd=’\0’;//末尾置0
for(i=1;i《=n;i++)
{
start=n-1; //cd串每次从末尾开始
c=i;
p=ht.parent;//p在n+1至2n-1
while(p) //沿父亲方向遍历,直到为0
{
start--;//依次向前置值
if(ht.LChild==c)//与左子相同,置0
cd=’0’;
else //否则置1
cd=’1’;
c=p;
p=ht.parent;
}
weight.num=n-start; //二进制码的长度(包含末尾0)
h=(char *)malloc((n-start)*sizeof(char));
strcpy(h);//将二进制字符串拷贝到指针数组h中
}
free(cd);//释放cd内存
system("pause");
}
/*********所有字符的编码*********/
void CrtHuffmanCode(char ch,HuffmanCode h,HuffmanCode hc,WeightNode weight,int n,int m)
{
int i,k;
for(i=0;i《m;i++)
{
for(k=1;k《=n;k++) /*从weight相等的下标K*/
if(ch.c)
break;
hc.num)*sizeof(char));
strcpy(hc); //拷贝二进制编码
}
}
/*****解码*****/
void TrsHuffmanTree(Huffman ht,WeightNode w,HuffmanCode hc,int n,int m)
{
int i=0,j,p;
printf("***StringInformation***\n");
while(i《m)
{
p=2*n-1;//从父亲节点向下遍历直到叶子节点
for(j=0;hc!=’\0’;j++)
{
if(hc==’0’)
p=ht.LChild;
else
p=ht.RChild;

}
printf("%c",w.c); /*打印原信息*/
i++;
}
}
/*****释放huffman编码内存*****/
void FreeHuffmanCode(HuffmanCode h,HuffmanCode hc,int n,int m)
{
int i;
for(i=1;i《=n;i++)//释放叶子结点的编码
free(h);
for(i=0;i《m;i++) //释放所有结点的编码
free(hc);
}
void print(Huffman &ht,int i,int space)//打印哈弗曼树
{
int j;
if(i)
{
print(ht,ht.RChild,space+5);
for(j=0;j《=space;j++)
printf(" ");
printf("%d\n",ht.weight);
print(ht,ht.LChild,space+5);
}
return ;
}
void main()
{
int i,n=0;/*n为叶子结点的个数*/
int m=0; /*m为字符串ch的长度*/
char ch存放输入的字符串*/
Huffman ht;/*Huffman二叉数 */
HuffmanCode h,hc;/*h存放叶子结点的编码，hc 存放所有结点的编码*/
WeightNode weight; /*存放叶子结点的信息*/
printf("**********************************************\n");
printf(" 欢迎使用哈弗曼编码解码系统\n");
printf("**********************************************\n");
printf("\t***HuffmanCoding***\n");
printf("please input information :");
gets(ch);/*输入字符串*/
CreateWeight(ch,&m,weight,&n);/*产生叶子结点信息，m为字符串ch的长度*/
printf("***WeightInformation***\n Node ");
for(i=1;i《=n;i++)/*输出叶子结点的字符与权值*/
printf("%c ",weight.c);
printf("\nWeight ");
for(i=1;i《=n;i++)
printf("%d ",weight.weight);
CreateHuffmanTree(ht,weight,n); /*产生Huffman树*/
printf("\n***HuffamnTreeInformation***\n");
printf("\ti\tweight\tparent\tLChild\tRChild\n");
for(i=1;i《=2*n-1;i++) /*打印Huffman树的信息*/
printf("\t%d\t%d\t%d\t%d\t%d\n",i,ht.RChild);
CrtHuffmanNodeCode(ht,ch,h,weight,m,n); /*叶子结点的编码*/
printf(" ***NodeCode***\n"); /*打印叶子结点的编码*/
for(i=1;i《=n;i++)
{
printf("\t%c:",weight.c);
printf("%s\n",h);
}
CrtHuffmanCode(ch,h,hc,weight,n,m); /*所有字符的编码*/
printf("***StringCode***\n\n"); /*打印字符串的编码*/
for(i=0;i《m;i++)
printf("%s",hc);
system("pause");
TrsHuffmanTree(ht,weight,hc,n,m); /*解码*/

FreeHuffmanCode(h,hc,n,m);
printf("\n");
printf("\n哈弗曼树\n");
print(ht,2*n-1,0);
system("pause");

}

哈夫曼编码C语言实现

我写了一个注释较为完整且压缩、解压缩比较全面的：
#include 《stdio.h》
#include 《conio.h》
#define MAX_FILE 5000/* 假设的文件最大长度 */
#define MAXLIST 256/* 最大MAP值 */
#define MAX_HOFFMAN_LENGTH 50/* 哈夫曼编码长度 */
char dictionary为字符 */
char fileContent;/* 处理的字符串大小 */
int Hoffman={2};/* 哈夫曼编码序列 */
char HoffmanList={0};/* 哈夫曼编码对应的字符有序序列 */
char HoffFileCode={0};/* 哈夫曼编码字符串序列 */
char HoffFile={0};
/* 编码到假设的文件的哈夫曼压缩格式： 依次存储 原字符串长度(1字节存储:可扩展到2字节)、哈夫曼编码数(1字节)、每个哈夫曼编码的长度序列、每个哈夫曼编码对应的字符序列、编码过的哈夫曼字符串 */
char GetFile={0};/* 解码序列 */
void ShellSort(char pData,int Count)/* Shell排序，用于准备有序化要构造的编码权值构造哈夫曼树做准备 */
{
int step={9,5,3,1};/* 增量序列 */
int iTemp,cTemp;
int k,s,w,i,j;
for(i=0;i《4;i++)
{
k=step;
s=-k;
for(j=k;j《Count;j++)
{iTemp=pData;
cTemp=pData;
w=j-k;
if(s==0)
{
s=-k;
s++;
pData=iTemp;
pData=cTemp;
}
while((iTemp《pData)&&(w》=0)&&(w《=Count))
{
pData;/* 权值交换 */
pData;/* 字符交换 */
w=w-k;
}
pData=iTemp;
pData=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=0;
Preorder(p);
Hoffman=2;
deep--;
}
void byRight(struct TNode*p)/* 经由右结点 */
{
deep++;
Hoffman=1;
Preorder(p);
Hoffman=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=2;
i=0;
for(;Hoffman!=2;i++)
{
Hoffman;
}
Hoffman=2;
HoffmanList=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)/* 判断由 组成的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,h=0;
int codeLen=0,total=0;
/* 或许假定的文件字符串向量中的字符串 */
printf("please Enter string to be pressed:");
scanf("%s",&fileContent);
/* Hash进dictionary */
for(;fileContent!=’\0’;i++,fileLen++)
{
++dictionary;
dictionary;
}
/* 把Hash了的dictionary向前靠拢 */
{
for(i=0;i!=MAXLIST;i++)
{
if(dictionary!=0)
{
dictionary;
dictionary;
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);
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);
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=i;
}
/* 存储字符串的哈夫曼压缩编码串,并且打包文件格式 */
{
for(i=0;i!=fileLen;i++)
{
int j=dictionary;
for(k=0;Hoffman!=2;k++)
{
HoffFileCode《《(7-total%8));
code;
if(((total+1)%8)==0)
{
HoffFile;
codeLen++;
}
total++;
}
}
}
HoffFile;
HoffFile=(fileLen);
/* 解压缩假定的文件HoffFile成为原字符串序列 */
printf("Huffman’s code list:\n");
HoffFile=len;
{
for(i=0,j=0;i!=len;i++,j=0)
{
for(;Hoffman!=2;j++);
HoffFile=j;
HoffFile;
for( k=0;k!=j;k++)
{
printf("%d",Hoffman);
HoffFile《《(j-1-k));
}
printf(":%d\n",HoffmanList);
}
}
{
for(i=0,j=0;i!=(HoffFile&0xff);i++)
{
for(k=0;k!=HoffFile;k++)
{
l=HoffFile;
c=HoffFile;
if(compareBits(b1,b2,c,l,d))
{
j+=HoffFile;
GetFile;
break;
}
}
}
}
{
printf("Huffman code List Pressed :\n");
for(i=0;i!=h;i++)
{
printf("%c",code);
if((i+1)%8==0)
printf(" ");
}
}
printf("\n");
{
printf("Huffman code packaged:\n");
for(i=0;i!=HoffFile*3;i++)
{
printf("%c",HoffFile);
}
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&0xff));
printf("The string decoded:");
for(i=0;i!=(HoffFile&0xff);i++)
{
printf("%c",GetFile);
}
printf("\n");
}
getch();
return 1;
}

c语言哈夫曼树哈夫曼编码纠错

我电脑里保存了类似的这样的题目，可以直接运行的：#include#include#include#include#include#include#defineMAXSIZE50//定义huffnode及huffcode，分别用来存储节点信息及各节点编码typedefstruct{chardata;//节点值intweight;//权值intparent;intleft;intright;intflag;}huffnode;typedefstruct{charcode.weight

哈夫曼编码的C语言源代码

/*文件名:exp7-6.cpp*/
#include 《stdio.h》
#include 《string.h》
#define N 50 /*叶子结点数*/
#define M 2*N-1 /*树中结点总数*/
typedef struct
{
char data; /*结点值*/
int weight; /*权重*/
int parent; /*双亲结点*/
int lchild; /*左孩子结点*/
int rchild; /*右孩子结点*/
} HTNode;
typedef struct
{
char cd; /*存放哈夫曼码*/
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.rchild=-1;
for (i=n;i《2*n-1;i++) /*构造哈夫曼树*/
{
min1=min2=32767; /*lnode和rnode为最小权重的两个结点位置*/
lnode=rnode=-1;
for (k=0;k《=i-1;k++)
if (ht.parent==-1) /*只在尚未构造二叉树的结点中查找*/
{
if (ht.weight《min1)
{
min2=min1;rnode=lnode;
min1=ht.weight;lnode=k;
}
else if (ht.weight《min2)
{
min2=ht.weight;rnode=k;
}
}
ht.parent=i;
ht.weight;
ht.rchild=rnode;
}
}
void CreateHCode(HTNode ht,int n)
{
int i,f,c;
HCode hc;
for (i=0;i《n;i++) /*根据哈夫曼树求哈夫曼编码*/
{
hc.start=n;c=i;
f=ht.parent;
while (f!=-1) /*循序直到树根结点*/
{
if (ht.lchild==c) /*处理左孩子结点*/
hc.cd=’0’;
else /*处理右孩子结点*/
hc.cd=’1’;
c=f;f=ht.parent;
}
hc.start++; /*start指向哈夫曼编码最开始字符*/
hcd=hc;
}
}
void DispHCode(HTNode ht,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.data);
for (k=hcd.start;k《=n;k++)
{
printf("%c",hcd);
j++;
}
m+=ht.weight;
sum+=ht.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;
HCode hcd;
for (i=0;i《n;i++)
{
strcpy(ht);
ht;
}
printf("\n");
CreateHT(ht,n);
CreateHCode(ht,hcd,n);
DispHCode(ht,hcd,n);
printf("\n");
}

以前写的，你照着改下就行的.