文章作者：heroooooo
信息来源：邪恶八进制信息安全团队（
www.eviloctal.com）
以下程序是利用哈夫曼编码的原理对字符进行处理,最后输出的是对输入的字符的0和1的编码.程序有写得不好的地方,望多多指教.谢谢了..将这个程序稍微做些修改就可以从一个文件中判断字符出现的频率,还是照样能输出编码后的结果.这个功能我就没有加上了,各位有兴趣的可以试下.
复制内容到剪贴板
代码:
#include "iostream.h"
#include "malloc.h"
#define OK 1
#define ERROR 0
#define NULL 0
typedef int status;
typedef char Elemtype;
/*这个程序是想实现最优二叉树的寻找功能*/
typedef struct TREE{
/*data中放的是数据,father中放的是他的父节点的位置,lchild中放的是他的左孩子节点的位置
rchild中放的是他的右孩子的位置,整个数据结构用得是改进的邻接表的结构*/
//Elemtype data;
int weight;/*这个是权重的大小*/
int father;
int lchild;
int rchild;
}tree,*maptree;
/*今天是星期二，先把这个程序的一个小功能先实现下,其余的程序等吃完饭在来说.先完成的是输入数据并且
统计的一个小函数,这个时候先不考虑算法的优化，只是要程序能够跑起来就可以了..*/
status number(Elemtype *&input,Elemtype *&output,int *&count,int length)
{ /*这个函数的功能是统计一个输入的数据中的字符出现的频率，通过一个返回值确定出现了几个不同
的字符，output中放的是不同的字符的名称,count中存放的是与output相对应的字符出现的次数*/
int xunhuan=0;/*这个数放得让我也有些无奈了*/
output=(Elemtype *)malloc(length*sizeof(Elemtype));
count=(int *)malloc(length*sizeof(int));
Elemtype *p1=output;int *array=count;Elemtype *q1=NULL;
int countlength=0;
for(int i=0;i<length;i++)
{
*(p1++)='0';
}
for(i=0;i<length;i++)
{
*(array++)=0;
}
p1=output;array=count;q1=input;
for(i=0;i<length;i++)
{
for(int j=0;j<countlength;j++)
{
if((*(q1+i))==(*(p1+j)))
{
(*(array+j))++;
xunhuan=1;
j=countlength+1;/*这个时候退出循环*/
}
}
if(xunhuan==0)
{
*(p1+countlength)=*(q1+i);
(*(array+countlength))++;
countlength++;
}
xunhuan=0;/*重新设置下，防止出现了错误*/
}
return countlength;
}
status pailie(maptree &T,int length)
{/*这个函数的功能是将一个长度为length的数组按照升序排列*/
maptree linshi=(maptree)malloc(sizeof(tree));
for(int i=0;i<length;i++)
{
for(int j=(i+1);j<length;j++)
{
if(((T+i)->weight)>((T+j)->weight))
{/*这个地方的代码有点垃圾，需要好好的修改下..*/
(linshi->father)=(T+i)->father;
(linshi->lchild)=(T+i)->lchild;
(linshi->rchild)=(T+i)->rchild;
(linshi->weight)=(T+i)->weight;
(T+i)->father=(T+j)->father;
(T+i)->lchild=(T+j)->lchild;
(T+i)->rchild=(T+j)->rchild;
(T+i)->weight=(T+j)->weight;
(T+j)->father=linshi->father;
(T+j)->lchild=linshi->lchild;
(T+j)->rchild=linshi->rchild;
(T+j)->weight=linshi->weight;
}
}
}
free(linshi);
return OK;
}
status pailieout(Elemtype *&output,int *&count,int length)
{/*这个函数的功能是将output和count这两个数组中的内容按照从小到大的
顺序依次排列出来。好了废话不多说，开始写程序了..*/
int i,j;
i=0;j=0;
int warp=0;
Elemtype change;
/*以下用的这个是用选择法实现排序的..*/
for(i=0;i<(length-1);i++)
for(j=(i+1);j<length;j++)
{
if(*(count+i)>*(count+j))
{
warp=*(count+i);
*(count+i)=*(count+j);
*(count+j)=warp;
change=*(output+i);
*(output+i)=*(output+j);
*(output+j)=change;
}
}
return OK;
}
status erchashu(maptree &T,int *count,int length)
{/*这个函数的功能是将一个数组中的内容排列成一棵最优二叉树，希望能成功了..*/
/*一个有n个节点的最终形成的是(2*n-1)个，所以分配的空间也应该是这么大了.可以确定的是
这个函数有问题了..*/
T=(maptree)malloc((2*length-1)*sizeof(tree));
maptree linshi=T;
int *q=count;
int j=0;
for(int i=0;i<length;i++)
{
(linshi+i)->weight=(*(q++));
(linshi+i)->father=0;
(linshi+i)->lchild=0;
(linshi+i)->rchild=0;
}
for(i=length;i<(2*length-1);i++)
{
(linshi+i)->weight=0;
(linshi+i)->father=0;
(linshi+i)->lchild=0;
(linshi+i)->rchild=0;
}
linshi=T;
q=count;
pailie(T,length);
for(i=0;i<(length-1);i++)
{/*要进行(n-1)次操作，整个二叉数的操作才会结束.之后的才会变成最优二叉树*/
(linshi+i+length)->weight=((linshi+j)->weight)+((linshi+j+1)->weight);
(linshi+i+length)->lchild=j;
(linshi+i+length)->rchild=j+1;
(linshi+i+length)->father=0;
(linshi+j)->father=(i+length);
(linshi+j+1)->father=(i+length);
j++;
j++;
pailie(T,(length+i+1));/*这个地方的参数其实是可以缩小的*/
}
return OK;
}
status printtree(maptree T,Elemtype *output,int length)
{/*这个函数的功能是 将一个已经存在的最优二叉树按照一定的顺序输出出来..*/
/*length是1的时候想单独处理下*/
if(length==1)
{
cout<<0<<endl;
return OK;
}
maptree linshi=NULL;
int p=0;int j=length-1;int k=0;
int *array=(int *)malloc(length*sizeof(int));
int *q=array;
for(int i=0;i<length;i++)
{
(*(q+i))=2;
}
linshi=T;
for(i=0;i<length;i++)
{/*从树中读取(length-1)次，将所有的节点信息都输出出来*/
//cout<<"T+"<<i<<"->father="<<(T+i)->father<<endl;
p=(linshi+i)->father;k=i;
while(p!=0)
{
if(((linshi+p)->lchild)==k) *(array+j)=0;
if((linshi+p)->rchild==k) *(array+j)=1;
j--;
k=p;
p=(linshi+p)->father;
}
cout<<*(output+i)<<" ";
for(j=0;j<length;j++)
{
if((*(array+j))!=2)
cout<<(*(array+j));
}
cout<<endl;
/*再次复位下*/
for(j=0;j<length;j++)
(*(q+j))=2;/*数组也复位下看看有什么结果了..*/
j=length-1;/*搞了好几次错误的原因居然是这个地方的复位工作没有做好，小结问题，以后要注意了..*/
}
return OK;
}
int main()
{
int length;
int i=0;
int countlength=0;
maptree T=NULL;
Elemtype * M=NULL;Elemtype * linshi=NULL;
cout<<"please input a number:"<<endl;
cin>>length;
cout<<endl;
M=(Elemtype *)malloc(length*sizeof(Elemtype));
linshi=M;
for(i=0;i<length;i++)
{
cin>>(*(linshi+i));
}
Elemtype *output=NULL;
int *count=NULL;
cout<<"please wait for a few minute"<<endl;
countlength=number(linshi,output,count,length);
pailieout(output,count,countlength);/*调用函数将两个数组按照count数组中的数值进行修改排序..*/
for(i=0;i<countlength;i++)/*输出下看下有没有什么错误..*/
cout<<*(output+i)<<" "<<*(count+i)<<endl;
erchashu(T,count,countlength);
printtree(T,output,countlength);
free(M);
free(T);
return 0;
}
