编程论坛 → 数据结构与算法

赫夫曼编码中的select函数的更简单的思想是什么

miaorunhua 发布于 2008-06-22 13:00， 2598 次点击

void select(huffmantree ht, int n,int&s1,int&s2)
{

    int j;
    for(j=1;j<=n;j++)
      if(ht[j].parent==0)
     {
         s1=j;
         break;
     }
    for(j=j+1;j<=n;j++)
      if(ht[j].parent==0)
     {
         s2=j;
         break;
     }
    for(j=s1;j<=n;j++)
        if(ht[j].parent==0)
            if(ht[j].weight<ht[s1].weight) s1=j;
    if(s1==s2)
        for(j=s2+1;j<=n;j++)
             if(ht[j].parent==0)
             {
                  s2=j;
                  break;
             }


    for(j=1;j<=n;j++)

        if(ht[j].parent==0&&j!=s1)
            if(ht[j].weight<ht[s2].weight) s2=j;
    printf("s1=%d,s2=%d\n",s1,s2);

}
这个是我写的，但是我觉得太麻烦了，有没有更简单的写法？希望各位高手指点一下。我觉得主要是找几个数中最小的两个先找一个再找一个太麻烦了，但暂时又想不出其他的好的方法。

[[it] 本帖最后由 miaorunhua 于 2008-6-22 13:04 编辑 [/it]]

6 回复

#2

missiyou2008-06-22 20:56

最简单的思想，就是找一个线性表的，最小，和次最小，然后想加，最小通过查找，次最小，比最小的大一点，这样在比较就可以得到，别的就是对结构赋值。
无人指点，完全是自己乱想的。呵呵，或许有点用

#3

miaorunhua2008-07-03 23:42

回复 2# missiyou 的帖子

呵呵，谢谢你啊，我想的是先找到最小的，再在剩下的里面找最小的，这两个就是整个里面最小的两个啊，不过我觉得这样有点麻烦啊，有没有可以一下子把两个都找出来的算法啊。

#4

missiyou2008-07-04 08:34

可以写个排序函数，直接对它进行排序，然后就是两个指针一前一后。相加了，在后移了哦。不知道行不行，

#5

zeroandone2008-07-05 10:40

哈哈,我这有一个最好的

void select(int t,int *m1,int *m2)
{ int i;
  int s1,s2;
  s1=s2=infi;
  for(i=1;i<=t;i++)
   if(ht[i].parent==0)
    if(ht[i].w<s1)
     {  s2=s1;
    *m2=*m1;
    s1=ht[i].w;
    *m1=i;
     }
    else if(ht[i].w<s2)
     {  s2=ht[i].w;
    *m2=i;
     }
}
是我们老师写的,本人觉得非常好,简单易懂

#6

寻找梦想12013-05-23 21:51

void select(HuffmanTree t,int i,int &s1,int &s2)
{ // s1为最小的两个值中序号小的那个
   int j;
   s1=min(t,i);

   s2=min(t,i);
   if(s1>s2)
   {
     j=s1;
     s1=s2;
     s2=j;//实现s1为编号最小的；
   }
}

#7

巧若拙2014-09-28 12:33

做个优先队列，效率最高

1