鱼C论坛

 找回密码
 立即注册
查看: 3462|回复: 9

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

[复制链接]
发表于 2015-7-19 14:18:26 | 显示全部楼层 |阅读模式
10鱼币
比方说5,3,2,1,9
简单的把这些数存进赫夫曼树里
最佳答案
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);
}
}

最佳答案

查看完整内容

#include #include #include #include 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
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 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);
}
}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-7-19 16:02:26 | 显示全部楼层
单纯这两个字该怎么理解
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2015-7-19 19:30:41 | 显示全部楼层
川本姨夫 发表于 2015-7-19 16:02
单纯这两个字该怎么理解

我不是举例了吗:curse:
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-7-19 22:01:20 | 显示全部楼层
从小到大排成队列,小的在队头。
1、取出队头两个元素,相加得到一个新元素。新元素就是树的根节点,取出的两个元素就是子节点。
2、把第一步得到的新元素插入队列合适位置,保证有序
重复以上两步
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-7-22 22:01:25 | 显示全部楼层
:handshake
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-7-26 11:58:55 | 显示全部楼层
顶啊~.~
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-7-26 21:28:34 | 显示全部楼层
从小到大排成队列,小的在队头。
1、取出队头两个元素,相加得到一个新元素。新元素就是树的根节点,取出的两个元素就是子节点。
2、把第一步得到的新元素插入队列合适位置,保证有序
重复以上两步
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

头像被屏蔽
发表于 2015-12-23 20:47:32 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2016-8-16 23:23:52 | 显示全部楼层
取出队头两个元素,相加得到一个新元素。新元素就是树的根节点,取出的两个元素就是子节点
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 05:04

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表