USTC机试——根据浮点数序列输出数列的huffuman编码

思想：1：huffuman并不唯一(完整代码在最低端)

2：利用<queue>头文件中的priority_queue队列实现结点的存储,优先队列是实现自动调整结点顺序的一种数据结构，由于我在结构体中重载的小于符号是根据其数值排序，故可以实现从小到大的自动排序。

3：每个树的结点的结构体如下：

struct Node{
   struct Node *lchild;
   struct Node *rchild;
   double d;//存储这个结点对应的数值
   bool operator <(const Node &A)const{//重载小于符号方便优先队列调用
      return d<A.d;
   }
   char tab[N];//每个结点附加一个huffuman编码
}Tree[N];

4：利用小顶堆形式的优先队列存储上述结点:

priority_queue <Node*, vector<Node*>,  greater<Node*> > q;

5:求解思想：先根据文件中的数字序列建立一棵完整的树，建立完整的树后利用遍厉到叶节点输出huffuman编码（huffuman编码的构建在遍历的过程确定）

根据两个节点建立一棵树的方法：

Node *setTree(Node *a,Node *b){//根据两个结点构建一颗树
     Node *temp1=create();//静态获取一个结点的方法，完整代码中此方法的定义
     temp1->d=a->d+b->d;
	 temp1->lchild=a;
	 temp1->rchild=b;
	 return temp1;
}

根据优先队列建立一棵完整的树：思想：反复的从队列中取出两个最小节点，利用上面setTree方法建立一棵树并且再把树的根节点压入优先队列中，如此往复，当优先队列中只有一个元素时就是建立好树的根节点

 Node *t1,*t2,*T;
   while(q.size()>1){//在优先队列中创建一课完整的树
       t1=q.top();
	   q.pop();
	   t2=q.top();
	   q.pop();
	   T=setTree(t1,t2);
	   q.push(T);
   }
   T=q.top();//最后队列中剩下的是根节点

在建立完一棵huffuman树后，遍历该树时建立每个结点的huffuman编码，思想：T结点的左孩子huffuman编码等于T结点的编码链接上'0',T结点的右孩子huffuman编码等于T结点的编码链接上'1';

void Huffuman(Node *T){//注解，huffuman树并不唯一所以此处多思考一下
	if(T->lchild!=NULL){strcpy(T->lchild->tab,T->tab);strcat(T->lchild->tab,"0");Huffuman(T->lchild);}
	if(T->rchild!=NULL){strcpy(T->rchild->tab,T->tab);strcat(T->rchild->tab,"1");Huffuman(T->rchild);}
	if(T->lchild==NULL&&T->rchild==NULL){
		fprintf(fp2,"%lf %s\n",T->d,T->tab);//输出Huffuman编码
	}
}

完整代码如下：

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
#define N 100 

struct Node{
   struct Node *lchild;
   struct Node *rchild;
   double d;
   bool operator <(const Node &A)const{//重载小于符号方便优先队列调用
      return d<A.d;
   }
   char tab[N];//每个结点附加一个huffuman编码
}Tree[N];

priority_queue <Node*, vector<Node*>,  greater<Node*> > q;//优先队列,此处有一注意事项即把最后一个>前的空格不可省略
int loc=0;
Node *create(){//静态分配一个结点
     Tree[loc].lchild=Tree[loc].rchild=NULL;
	 memset(Tree[loc].tab,0,sizeof(Tree[loc].tab));
	 return &Tree[loc++];
}

Node *setTree(Node *a,Node *b){//根据两个结点构建一颗树
     Node *temp1=create();
     temp1->d=a->d+b->d;
	 temp1->lchild=a;
	 temp1->rchild=b;
	 return temp1;
}


FILE *fp1,*fp2;
void Huffuman(Node *T){//注解，huffuman树并不唯一所以此处多思考一下
	if(T->lchild!=NULL){strcpy(T->lchild->tab,T->tab);strcat(T->lchild->tab,"0");Huffuman(T->lchild);}
	if(T->rchild!=NULL){strcpy(T->rchild->tab,T->tab);strcat(T->rchild->tab,"1");Huffuman(T->rchild);}
	if(T->lchild==NULL&&T->rchild==NULL){
		fprintf(fp2,"%lf %s\n",T->d,T->tab);//输出Huffuman编码
	}
}
int main(){//利用优先队列取两个节点创建树节点再放回去，往复循环创建一颗完整的树
   fp1=fopen("7.in","r");
   fp2=fopen("7.out","w");
   while(!feof(fp1)){//将结点压入栈中
      Node *T=create();
	  fscanf(fp1,"%lf",&T->d);//双精度数字格式
      q.push(T);
   }

   Node *t1,*t2,*T;
   while(q.size()>1){//在优先队列中创建一课完整的树
       t1=q.top();
	   q.pop();
	   t2=q.top();
	   q.pop();
	   T=setTree(t1,t2);
	   q.push(T);
   }
   T=q.top();//最后队列中剩下的是根节点
   Huffuman(T);
   return 0;
}

全部评论

推荐最新楼层

07-25 11:26

清华大学 Java

终章

打开电脑，思绪又回到了7月份刚开始的时候，感觉这个月过的如梦如幻，发生了太多事，也算是丰富了我本就是平淡的人生吧太早独立的我习惯了一切都是自己做决定，拥有绝对的决定权，而且永远不会听取别人的建议。我就是那个恋爱四年出轨的男主啦，感觉既然在牛客开了这个头，那我就要做个有始有终的人。从我出轨到结束再到和女朋友和好如初真的太像一场梦了，短短的一个月我经历了太多，也成长了很多，放下了那些本就不属于我的，找回了那些我不该放弃的。我的人生丰富且多彩，但人不能一直顺，上天总会让你的生活中出点乱子，有好有坏，让你学会一些东西，让你有成长。我和女朋友的恋爱四年太过于平淡，日常除了会制造一些小浪漫之外，我们的生活...

段哥亡命职场：不得不说，我是理解你的，你能发出来足见你是个坦诚的人，至少敢于直面自己的内心和过往的过错。这个世界没有想象中那样非黑即白，无论是农村还是城市，在看不见的阴影里，多的是这样的事。更多的人选择站在制高点去谩骂，一方面是社会的道德是需要制高点的，另一方面，很多人不经他人苦，却劝他人善。大部分的我们，连自己生命的意义尚且不能明晰，道德、法律、困境，众多因果交织，人会迷失在其中，只有真的走出来之后才能看明白，可是没走出来的时候呢？谁又能保证自己能走的好，走的对呢？可是这种问题有些人是遇不到的，不去追寻，不去探寻，也就没了这些烦恼，我总说人生的意义在过程里，没了目标也就没了过程。限于篇幅，没法完全言明，总之，这世界是个巨大的草台班子，没什么过不去了，勇敢面对，革故鼎新才是正确，祝你早日走出来。