//数据结构课程设计、//设计程序以实现构造哈夫曼树的哈夫曼算法。//要求：使用实验工具的有关功能；要能有演示过程；求解出所构造的哈夫曼//树的带权路径长度。 #include"btreint.h" int count=0;//数据的个数；bitre data[50];//存储数组 void delete_min()//获得最小元素、{ for(int i=1;i<=count-2;i++) data[i]=data[i+2];} int tree_insert(bitre t)//插入新的节点; {   if(t->data>=data[count]->data){data[++count]=t;return 0;} else{int m; for(int j=1;j<=count;j++) if(data[j]->data>=t->data){m=j;break;} for(int k=count;k>=m;k--) data[k+1]=data[k]; data[m]=t; count++;} } int num=0;get_long(bitre t)//求解huffman树的带权路径长度; { if(t!=NULL){ if(t->rchild!=NULL&&t->lchild!=NULL) { visite_bnode(t,1); num=num+t->data; get_long(t->lchild); get_long(t->rchild); }}}void main(){       cout<<endl<<endl<<endl<<endl;    cout<<"          ***************************************"<<endl;    cout<<"          *       Construct Huffman Tree        *"<<endl;    cout<<"          *       Name:     XuHua               *"<<endl;    cout<<"          *       Number:   20042297            *"<<endl;    cout<<"          ***************************************"<<endl<<endl<<endl<<endl;             bitre a,b,t;    //定义变量;  cout<<"please put in the data and in increased way and -9999 over "<<endl; for(int i=1;i<=50;i++)//输入数据;   { int adj; data[i]=(bitre)malloc(sizeof(struct bnode));//数据存储;   if(i==1){data[0]->data=0;} cin>>adj; if(adj==-9999){cout<<"put in over "<<endl;break;}//结束标志;  data[i]->data=adj;count++;    }  //数据元素，   //数据的存储;   for(int y=1;y<=count;y++)//整理存储的数据;   for(int x=count;x>y;x--)  if(data[x]->data<data[x-1]->data)  {      int shu=data[x]->data;      data[x]->data=data[x-1]->data;      data[x-1]->data=shu;  }     for(int j=1;j<=count;j++) {data[j]->lchild=NULL;data[j]->rchild=NULL;}//huffman树构造过程;  while(count>1) {  a=data[1];b=data[2];//得到最小的两个节点;  t=(bitre)malloc(sizeof(struct bnode)); t->lchild=a; t->rchild=b; t->data=a->data+b->data; delete_min(); count=count-2; tree_insert(t); display_bitre("tree",t);//显示此时的huffman树;  Wait();  } get_long(t); cout<<"WL="<<num<<endl;//输出带权路径长度;  Wait();}      

评论