怎么单纯的建立一个赫夫曼树
比方说5，3，2，1，9简单的把这些数存进赫夫曼树里 #include <iostream>
#include <fstream>
#include <string.h>
#include <cstdlib>
using namespace std;
typedef struct{
char data;
int weight;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char * * HuffmanCode;
void Select(HuffmanTree &HT,int n,int m)
{
HuffmanTree p=HT;
int tmp;
for(int j=n+1;j<=m;j++)
{int tag1,tag2,s1,s2;
tag1=tag2=256;
for(int x=1;x<=j-1;x++)
{if(p.parent==0&&p.weight<tag1)
{ tag1=p.weight;s1=x;}
}
for(int y=1;y<=j-1;y++)
{ if(p.parent==0&&y!=s1&&p.weight<tag2)
{tag2=p.weight;s2=y;}
}
if(s1>s2)//将选出的两个节点中的序号较小的始终赋给s1
{tmp=s1; s1=s2; s2=tmp;}
p.parent=j;
p.parent=j;
p.lchild=s1;
p.rchild=s2;
p.weight=p.weight+p.weight;
}
}
void HuffmanCoding(HuffmanTree &HT,int n,char *w1,int*w2)
{
int m=2*n-1;
if(n<=1) return;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
HuffmanTree p=HT;
for(int i=1;i<=n;i++)
{ p.data=w1;
p.weight=w2;
p.parent=p.lchild=p.rchild=0;
}
for(int i=1;i<=m;i++)
{p.weight=p.parent=p.lchild=p.rchild=0;}
Select(HT,n,m);
ofstream outfile; //生成hfmTree文件
outfile.open("hfmTree.txt",ios::out);
for (int i=1;i<=m;i++)
{outfile<<HT.weight<<"\t"<<HT.parent<<"\t"<<HT.lchild
<<"\t"<<HT.rchild<<"\t"<<endl;
}
outfile.close();
cout<<"初始化结果已保存在hfmTree文件中\n";
}
void ToBeTree() //将正文写入文件ToBeTree中
{
ofstream outfile;
outfile.open("ToBeTree.txt",ios::out);
outfile<<"THIS PROGRAM IS MYFAVORITE";
outfile.close();
}
void Encoding(HuffmanTree &HT,int n) //编码
{
HuffmanCode HC;
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
char *cd;
cd=(char *)malloc(n*sizeof(char));
cd='\0';
for(int k=1;k<=n;k++)
{ int start=n-1;
for(int c=k,f=HT.parent;f!=0;c=f,f=HT.parent)
{if(HT.lchild==c) cd[--start]='0';
else cd[--start]='1';
}
HC=(char *)malloc((n-start)*sizeof(char));
strcpy(HC,&cd);
}
cout<<"输出哈夫曼编码:"<<endl;
for(int h=1;h<=n;h++) //输出编码
{ cout<<HT.data<<":";
cout<<HC;
cout<<"";
if (h%8==0)cout<<endl;
}
cout<<endl<<"输出正文编码:"<<endl;
ToBeTree();
//读取TOBETREE文件里的正文，并进行编码
fstream infile;
infile.open("ToBeTree.txt",ios::in);
char s;
while(!infile.eof())
{infile.getline(s,sizeof(s));}
infile.close();
fstream outfile;
outfile.open("CodeFile.txt",ios::out);
int count=0;
for (int h=0;s!='\0';h++)
{ for(int k=1;k<=n;k++)
if (s==HT.data)
{cout<<HC;
cout<<" ";
count++;
outfile<<HC;
break;
}
if (count%9==0)cout<<endl; //每输出7个换行
}
outfile.close();
cout<<"\n编码结果已保存在文件CodeFile中.";
cout<<endl;
}
void Decoding(HuffmanTree &HT,int n) //译码
{
int f=2*n-1;
fstream infile;
infile.open("CodeFile.txt",ios::in);
char s;
while(!infile.eof())
{infile.getline(s,sizeof(s));}
infile.close();
int i=0;
int j=0;
fstream outfile;
outfile.open("TextFile.txt",ios::out);
while(s!='\0')
{ f=2*n-1;
while(HT.lchild!=0)//以f对应的节点的左孩子的值==0作为结束
{if (s=='0') f=HT.lchild;
else f=HT.rchild;
j++;
}
i=j;
cout<<HT.data;
outfile<<HT.data;
}
outfile.close();
cout<<"\n译码结果已保存在文件TextFile中.";
cout<<endl;
}
void Print() //印代码文件
{ int count=0;
fstream infile;
infile.open("CodeFile.txt",ios::in);
char s;
while(!infile.eof())
{infile.getline(s,sizeof(s));
for(int i=0;s!='\0';i++)
{ cout<<s;
count++;
if (count%50==0)cout<<endl; //在终端上每行显示50个代码
}
}
infile.close();
cout<<endl;
}
char menu() //菜单函数
{ cout<<"功能菜单如下:"<<endl;
cout<<"* * * * * * * * * * * * * * * * * * * * *"<<endl;
cout<<" I:初始化(Initialization) "<<endl;
cout<<" E:编码(Encoding) "<<endl;
cout<<" D:译码(Decoding) "<<endl;
cout<<" P:印代码文件(Print) "<<endl;
cout<<" Q:退出(Exit) "<<endl;
cout<<"* * * * * * * * * * * * * * * * * * * * *"<<endl;
cout<<"请输入功能字符:";
char ch;
cin>>ch;
return ch;
}
int main()
{int n;
int Array;
char cArray;
HuffmanTree HT;
cout<<"输入n个字符:";
cin.getline(cArray,100);
n=strlen(cArray);
cout<<"一共"<<n<<"个字符.\n";
cout<<"依次输入各个字符的权值:"<<endl;
for (int i=1;i<=n;i++) cin>>Array;
int tag;
char x=menu();
while(1)
{switch (x)
{
case 'I':HuffmanCoding(HT,n,cArray,Array);break;
case 'E':Encoding(HT,n);break;
case 'D':Decoding(HT,n);break;
case 'P':Print();break;
case 'Q':tag=0;cout<<"结束"<<endl;break;
default:cout<<"你输入错误!"<<endl;
}
if(tag==0) break;
cout<<"y(继续) or n(退出)"<<endl;
char ch;
cin>>ch;
if (ch=='y')
{ cout<<"请输入功能字符:";
char c;
cin>>c;
x=c;
}
else exit(1);
}
}
单纯这两个字该怎么理解 川本姨夫 发表于 2015-7-19 16:02
单纯这两个字该怎么理解
我不是举例了吗:curse: 从小到大排成队列，小的在队头。
1、取出队头两个元素，相加得到一个新元素。新元素就是树的根节点，取出的两个元素就是子节点。
2、把第一步得到的新元素插入队列合适位置，保证有序
重复以上两步 :handshake 顶啊~.~ 从小到大排成队列，小的在队头。
1、取出队头两个元素，相加得到一个新元素。新元素就是树的根节点，取出的两个元素就是子节点。
2、把第一步得到的新元素插入队列合适位置，保证有序
重复以上两步 取出队头两个元素，相加得到一个新元素。新元素就是树的根节点，取出的两个元素就是子节点
页:
[1]