huffmancode.cpp

实验3：二叉树的应用--构造赫夫曼树 1、实验目的：掌握二叉树的性质及赫夫曼树的构造。 2、实验要求：根据任意给定若干结点的权值

// HuffmanCode.cpp : Defines the entry point for the console application.
// 
#include<malloc.h>
#include<string> 
#include<iostream>
#include<iomanip> 
using namespace std; 
int *w;//声明全局变量
typedef struct 
{unsigned int weight; 
 unsigned int parent,lchild,rchild; 
}HTNode,*HuffmanTree; 
typedef char **HuffmanCode; 

void select(HuffmanTree HT,int n,int& s1, int& s2)//选择权值最大的两个
{int min1,min2,t,i=1;
 for(i=1;i<=n;i++)//将min1和min2初始化为权值最大，也可以这样                      //写:min1=min2=32767;
 if(HT[i].weight>min1) 
 min2=min1=HT[i].weight;

 for(i=1;i<=n;i++) 
 if(HT[i].parent==0)
 if(HT[i].weight<min1) 
 {min1=HT[i].weight;
  s1=i;
 }
 
 for(i=1;i<=n;i++) 
 if(HT[i].parent==0)
 if((HT[i].weight<min2)&&(i!=s1))
 {min2=HT[i].weight;
  s2=i; 
 }
 if(s1>s2)
 {t=s2;s2=s1;s1=t;}
}


void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int n)//赫夫曼二叉树编码 
{
    int m,i,s1,s2,start,k,j; //实验3：二叉树的应用--构造赫夫曼树
 unsigned c,f; 
 HuffmanTree p; 
 char *cd; 
if(n<=1) 
return; 
m=2*n-1; 
*HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); 
for(p=*HT+1,i=1;i<=n;++i,++p)//前n个结点初始化 
{p->weight=w[i];
p->parent=0; 
p->lchild=0; 
 p->rchild=0; 
} 
for(;i<=m;++i,++p)//对从第n+1个顶点到第2n-1个顶点初始化 
{p->weight=0; 
 p->parent=0; 
 p->lchild=0; 
 p->rchild=0;
}
for(i=n+1;i<=m;++i) //构建赫夫曼树
{select(*HT,i-1,s1,s2);
 (*HT)[s1].parent=i;
 (*HT)[s2].parent=i; 
 (*HT)[i].lchild=s1; 
 (*HT)[i].rchild=s2; 
 (*HT)[i].weight=(*HT)[s1].weight+(*HT)[s2].weight; 
} 
cout<<"1.赫夫曼树的存储结构如下:"<<endl;
cout<<"==============================="<<endl;
cout<<"num weight parent lchild rchild"<<endl;
for(i=1;i<=m;i++)
{cout<<setiosflags(ios::left);
 cout<<setw(6)<<i<<" ";
 cout<<setw(6)<<(*HT)[i].weight<<" ";
 cout<<setw(6)<<(*HT)[i].parent<<" ";
 cout<<setw(6)<<(*HT)[i].lchild<<" ";
 cout<<setw(6)<<(*HT)[i].rchild<<endl;
}
cout<<"==============================="<<endl;

*HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//赫夫曼编码,*HC为二维动态数组
cd=(char*)malloc(n*sizeof(char)); 
cd[n-1]='\0'; 
for(i=1;i<=n;i++) 
{start=n-1; 
 for(c=i,f=(*HT)[i].parent;f!=0;c=f,f=(*HT)[f].parent) 
 if((*HT)[f].lchild==c) 
 cd[--start]='0'; 
 else 
 cd[--start]='1'; 
//(*HC)[i]数组开辟了n-start个空间
 (*HC)[i]=(char*)malloc((n-start)*sizeof(char));
//从cd复制编码串到HC,也可这样表示:strcpy((*HC)[i],&cd[start]);
 for(k=start,j=0;k<=n-1;j++,k++)
 (*HC)[i][j]=cd[k]; 
} 
free(cd); 
} 

int main()//主函数
{HuffmanTree HT; 
 HuffmanCode HC; 
 cout<<"========赫夫曼树编码=========="<<endl;
 cout<<"======1.构建赫夫曼树=========="<<endl;
 cout<<"======2.进行赫夫曼编码========"<<endl;
 cout<<"======3.退出=================="<<endl;
 cout<<"=============================="<<endl;
 cout<<"请输入操作:"<<endl;
 int n,i,a;
l1:
 {cin>>a;
 }
 switch(a)
 {case 1:
      cout<<"请确定输入权值个数:"<<endl; 
      cin>>n; 
      w=(int*)malloc((n+1)*sizeof(int)); 
      cout<<"请依次输入这几个权值"<<endl; 
      for(i=1;i<=n;i++) 
      cin>>w[i]; 
      cout<<"权值输入完毕!"<<endl;
      cout<<"请输入操作:"<<endl;
      goto l1;
      break;
 case 2:
     cout<<"赫夫曼树编码动态过程如下:"<<endl;
     cout<<"==============================="<<endl;
     HuffmanCoding(&HT,&HC,n);
     cout<<"2.赫夫曼树各字符的编码如下:"<<endl;
     cout<<"==============================="<<endl;
     for(i=1;i<=n;i++) 
     cout<<w[i]<<"-"<<HC[i]<<endl;
     cout<<"==============================="<<endl;
     cout<<"动态过程演示完毕!"<<endl;
     cout<<"==============================="<<endl;
     cout<<"请输入操作:"<<endl;
     goto l1;
     break;
 case 3:
     return 0;
 }
 return 0;
}