[已解决]怎么单纯的建立一个赫夫曼树

请给我气球

比方说5，3，2，1，9
简单的把这些数存进赫夫曼树里

最佳答案

月排行榜 / 总排行榜

我是0和1

2015-7-19 14:18:27

#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[x].parent==0&&p[x].weight<tag1)
                          {   tag1=p[x].weight;s1=x;}
           }
   for(int y=1;y<=j-1;y++)
           {   if(p[y].parent==0&&y!=s1&&p[y].weight<tag2)
                   {  tag2=p[y].weight;s2=y;}
           }
           if(s1>s2)  //将选出的两个节点中的序号较小的始终赋给s1
           {  tmp=s1; s1=s2; s2=tmp;}
    p[s1].parent=j;
        p[s2].parent=j;
        p[j].lchild=s1;
        p[j].rchild=s2;
        p[j].weight=p[s1].weight+p[s2].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[i].data=w1[i-1];
           p[i].weight=w2[i];
   p[i].parent=p[i].lchild=p[i].rchild=0;
   }
  for(int i=1;i<=m;i++)
   {  p[i].weight=p[i].parent=p[i].lchild=p[i].rchild=0;  }
Select(HT,n,m);
ofstream outfile;        //生成hfmTree文件
outfile.open("hfmTree.txt",ios::out);
   for (int i=1;i<=m;i++)
{outfile<<HT[i].weight<<"\t"<<HT[i].parent<<"\t"<<HT[i].lchild
<<"\t"<<HT[i].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[n-1]='\0';
  for(int k=1;k<=n;k++)
  { int start=n-1;
           for(int c=k,f=HT[k].parent;f!=0;c=f,f=HT[f].parent)
          {  if(HT[f].lchild==c) cd[--start]='0';
                  else cd[--start]='1';
          }
          HC[k]=(char *)malloc((n-start)*sizeof(char));
          strcpy(HC[k],&cd[start]);
  }
  cout<<"输出哈夫曼编码:"<<endl;  
  for(int h=1;h<=n;h++)           //输出编码
  {   cout<<HT[h].data<<":";
      cout<<HC[h];
      cout<<"  ";
     if (h%8==0)  cout<<endl;
  }
cout<<endl<<"输出正文编码:"<<endl;
ToBeTree();
  //读取TOBETREE文件里的正文，并进行编码
  fstream infile;
  infile.open("ToBeTree.txt",ios::in);
   char s[80];
   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[h]!='\0';h++)
{ for(int k=1;k<=n;k++)
   if (s[h]==HT[k].data)
           {  cout<<HC[k];
      cout<<" ";
                   count++;
                   outfile<<HC[k];
    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[1000];
   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[i]!='\0')
{ f=2*n-1;
while(HT[f].lchild!=0)//以f对应的节点的左孩子的值==0作为结束
           {if (s[j]=='0')   f=HT[f].lchild;
                else          f=HT[f].rchild;
                j++;
           }  
          i=j;
          cout<<HT[f].data;
          outfile<<HT[f].data;         
  }
outfile.close();
cout<<"\n译码结果已保存在文件TextFile中.";
cout<<endl;
}
void Print()          //印代码文件
{ int count=0;
         fstream infile;
infile.open("CodeFile.txt",ios::in);
         char s[1000];
         while(!infile.eof())
           {infile.getline(s,sizeof(s));
            for(int i=0;s[i]!='\0';i++)
          { cout<<s[i];
                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[100];
   char cArray[100];
   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[i];
   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);
}
}

跳转到最佳答案楼层

我是0和1

#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[x].parent==0&&p[x].weight<tag1)
                          {   tag1=p[x].weight;s1=x;}
           }
   for(int y=1;y<=j-1;y++)
           {   if(p[y].parent==0&&y!=s1&&p[y].weight<tag2)
                   {  tag2=p[y].weight;s2=y;}
           }
           if(s1>s2)  //将选出的两个节点中的序号较小的始终赋给s1
           {  tmp=s1; s1=s2; s2=tmp;}
    p[s1].parent=j;
        p[s2].parent=j;
        p[j].lchild=s1;
        p[j].rchild=s2;
        p[j].weight=p[s1].weight+p[s2].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[i].data=w1[i-1];
           p[i].weight=w2[i];
   p[i].parent=p[i].lchild=p[i].rchild=0;
   }
  for(int i=1;i<=m;i++)
   {  p[i].weight=p[i].parent=p[i].lchild=p[i].rchild=0;  }
Select(HT,n,m);
ofstream outfile;        //生成hfmTree文件
outfile.open("hfmTree.txt",ios::out);
   for (int i=1;i<=m;i++)
{outfile<<HT[i].weight<<"\t"<<HT[i].parent<<"\t"<<HT[i].lchild
<<"\t"<<HT[i].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[n-1]='\0';
  for(int k=1;k<=n;k++)
  { int start=n-1;
           for(int c=k,f=HT[k].parent;f!=0;c=f,f=HT[f].parent)
          {  if(HT[f].lchild==c) cd[--start]='0';
                  else cd[--start]='1';
          }
          HC[k]=(char *)malloc((n-start)*sizeof(char));
          strcpy(HC[k],&cd[start]);
  }
  cout<<"输出哈夫曼编码:"<<endl;  
  for(int h=1;h<=n;h++)           //输出编码
  {   cout<<HT[h].data<<":";
      cout<<HC[h];
      cout<<"  ";
     if (h%8==0)  cout<<endl;
  }
cout<<endl<<"输出正文编码:"<<endl;
ToBeTree();
  //读取TOBETREE文件里的正文，并进行编码
  fstream infile;
  infile.open("ToBeTree.txt",ios::in);
   char s[80];
   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[h]!='\0';h++)
{ for(int k=1;k<=n;k++)
   if (s[h]==HT[k].data)
           {  cout<<HC[k];
      cout<<" ";
                   count++;
                   outfile<<HC[k];
    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[1000];
   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[i]!='\0')
{ f=2*n-1;
while(HT[f].lchild!=0)//以f对应的节点的左孩子的值==0作为结束
           {if (s[j]=='0')   f=HT[f].lchild;
                else          f=HT[f].rchild;
                j++;
           }  
          i=j;
          cout<<HT[f].data;
          outfile<<HT[f].data;         
  }
outfile.close();
cout<<"\n译码结果已保存在文件TextFile中.";
cout<<endl;
}
void Print()          //印代码文件
{ int count=0;
         fstream infile;
infile.open("CodeFile.txt",ios::in);
         char s[1000];
         while(!infile.eof())
           {infile.getline(s,sizeof(s));
            for(int i=0;s[i]!='\0';i++)
          { cout<<s[i];
                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[100];
   char cArray[100];
   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[i];
   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

weisuo

顶啊~.~

cqj9006

从小到大排成队列，小的在队头。
1、取出队头两个元素，相加得到一个新元素。新元素就是树的根节点，取出的两个元素就是子节点。
2、把第一步得到的新元素插入队列合适位置，保证有序
重复以上两步

千亩计者

取出队头两个元素，相加得到一个新元素。新元素就是树的根节点，取出的两个元素就是子节点