未命名4.cpp

一个关于huffman编码树的简单小程序

#include<iostream> 
#include<iomanip>
using namespace std;
const int NUM=26; 
const int SIZE=51; 
const int LENTH=15; 
class Node 
{ 
public: 
        char data; 
        int weight; 
        int parent; 
        int lchild; 
        int rchild; 
}; 
int main() 
{ 
   char word[NUM]={'a','b','c','d','e','f','g','h','i','j','k','l', 
   'm','n','o','p','q','r','s','t','u','v','w','x','y','z'};
   cout<<"Pleas input the data you want to be coding!"<<endl;
   cout<<"Explaining：if there are upper letters in ,they will always be transformed to   ";
   cout<<"lower letters instead.Then just to count them !!!"<<endl<<endl;
   char store[100000]={0};
   int weit[NUM]={0};
   int ml=0;
   FILE *fp;fp=fopen("yan.txt","r");
while(ml<99999)
{
    store[ml]=fgetc(fp);
    ml++;
}
int nl;
for(nl=0;nl<ml;nl++)
    if(store[nl]>='A'&&store[nl]<='Z'||store[nl]<='z'&&store[nl]>='a')
    {
    if(store[nl]>'Z')weit[(int)(store[nl]-97)]++;
    else weit[(int)(store[nl]-65)]++;
}
ml=0;
for(nl=0;nl<NUM;nl++)
{  cout<<"   "<<weit[nl];
   if(weit[nl]!=0) ml++;
}cout<<endl;
Node nodes[SIZE];
int i,j,one,two,a,b; 
int hc[NUM][LENTH];
int m,n; 
for(i=0;i<NUM;i++) 
{  if(word[i]!=0){
    nodes[i].data=word[i]; 
    nodes[i].weight=weit[i]; 
    nodes[i].parent=-1; 
    nodes[i].lchild=-1; 
    nodes[i].rchild=-1; }
} 
for(i=NUM;i<SIZE;i++) 
{ 
   nodes[i].data='@'; 
   nodes[i].weight=-1; 
   nodes[i].parent=-1; 
   nodes[i].lchild=-1; 
   nodes[i].rchild=-1; 
} 
for(i=NUM;i<SIZE;i++) 
{ 
a=b=-1; 
one=two=10000;
for(j=0;j<i;j++) 
{ 
if(nodes[j].parent==-1) 
{ 
if(nodes[j].weight<=two) 
{ one=two; two=nodes[j].weight; a=b; b=j; 
} else if(nodes[j].weight>two&&nodes[j].weight<=one) 
{   one=nodes[j].weight; a=j; } } }
    nodes[a].parent=i; 
    nodes[b].parent=i; 
    nodes[i].lchild=a; 
    nodes[i].rchild=b; 
    nodes[i].weight=nodes[a].weight+nodes[b].weight; 
} 
for(i=0;i<LENTH;i++) 
{ 
   for(j=0;j<NUM;j++) 
   { hc[j][i]=2; } } 
for(i=0;i<NUM;i++) 
{   j=LENTH-1; 
    for(m=i,n=nodes[i].parent;m!=-1;m=n,n=nodes[n].parent) 
    {   if(nodes[n].lchild==m) { hc[i][j]=0; } 
        else { hc[i][j]=1; } 
        j--; } 
    } 
cout<<"HuffmanTree:"<<endl; 
cout<<setw(4)<<"NO."<<setw(6)<<"data"<<setw(8)<<"weight"<<setw(6) 
<<"parnt"<<setw(6)<<"lchd"<<setw(6)<<"rchd"<<endl; 
for(i=0;i<SIZE;i++) 
{ 
   cout<<setw(4)<<i<<setw(6)<<nodes[i].data<<setw(8)<<nodes[i].weight<<setw(6) 
   <<nodes[i].parent<<setw(6)<<nodes[i].lchild<<setw(6)<<nodes[i].rchild<<endl; 
} 
cout<<endl<<"Result:"<<endl; 
cout<<setw(6)<<"char"<<setw(10)<<"frequency"<<setw(16)<<"huffmancode\n"; 
for(i=0;i<NUM;i++) 
{ 
   cout<<setw(6)<<word[i]<<setw(8)<<weit[i]; 
   cout<<" "; 
   for(j=0;j<LENTH;j++) 
   {   if(hc[i][j]!=2) { cout<<hc[i][j]; } 
   } cout<<endl;
} 
cout<<"\nDone.\n"<<endl;
system("pause");
return 0;
}