选择函数.txt

此函数的功能是依次选出两个小的数

void select(HuffmanTree HT, int k, int &s1, int &s2)
{         //在HT[1...k]中选择parent为0且权值最小的两个根结点，
          //其序号分别为s1和s2，并靠引用参数带回主调函数
	int i, j;
	int min1 = 32767;
	for(i = 1; i <= k; i++)    //找s1
	  if(HT[i].weight < min1 && HT[i].parent == 0){
		j = i;
		min1 = HT[i].weight;
	 }
	s1 = j;
	min1 = 32767;
	for(i = 1; i <= k; i++)    //找s2
		if(HT[i].weight < min1 && HT[i].parent == 0 && i != s1){
			j = i;
			min1 = HT[i].weight;
		}
	s2 = j;
}

void Select(HuffmanTree HT, int t, int *s1, int *s2)
{
     int m, n, i;
     
     m = n = 10000;/*感觉有点取巧可以自己修改*/ 
     for(i = 1; i <= t; i++)/*遍历找两个最小的结点*/ 
     {
         if(HT[i].parent == 0 /*m和n只是一个穿插的过程*/ 
            && (HT[i].weight < m || HT[i].weight < n))
         {
             if(m < n)         /*把大的除去,小的继续比较放那里*/ 
             {
                 n = HT[i].weight;
                 *s2 = i;
             }
             else
             {
                 m = HT[i].weight;
                 *s1 = i;
             }
         }
     }
     if(*s1 > *s2)            /*把小的放前面*/
     {
         i = *s1;
         *s1 = *s2;
         *s2 = i;
     }
}

for(i=0;i<n-1;i++){
  x1=0;x2=0;
  k=0;
  for(int j=0;j<n+i;j++){//查找两个权值最小的树叶
   if(HT[j].parent==0)
    if(k==0){      //当找到第一个数时
     x1=x2=j;k=1;
    }
    else if(HT[j].weight<HT[x1].weight){
     x2=x1; x1=j;k=2;  //当找到一个小于标记的最小数时
    }
    else if(HT[j].weight<HT[x2].weight) //当找到一个树在标记最小的两个数之间时
     x2=j;
    else if(k==1){//当只记录了一个数时，
     x2=j;k=2;
    }
  }//for