随笔-2  评论-0  文章-0  trackbacks-0
  2010年4月22日
在严蔚敏《数据结构》(c版)HuffmanTree算法中;select函数用于求权值两个最小两个节点;为方便讨论,不失其本质,在此转换成“求任一序列中,求最小的两个数 ”的问题。非排序算法


void Make_Big_First(int &s1, int &s2)//将大的存储在S1中
{
    int temp = 0;

    if(s1 < s2)
    {
        temp = s1;
        s1 = s2;
        s2 = temp;
    }
}
/*****************************************************************************************/
                算法分析                                                                
     序列:{a1,a2,a3,a4,a5,...an}                                                       
    首先以序列的前两个值初始化,s1 = a1,s2 = a2;                                        
    调整  使得较大值存放于 中;即s1 > s2                                                
    循环变量从第三位开始,分以下几种情况讨论:                                           
        用数轴, 讨论a3,a4 。。的落点  _______|_______|_________->                  
                                              s2      s1
不失一般性,讨论a3,a4的落点:
注意:S1>S2;
    1:                                                                           
        s1 < a3,s2 < a4 :                                                                
        answer : s1 = s1;s2 = s2;下一次循环从a4开始,因为存在 s1 > a4 的可能性           
    2:                                                                          
        s1 < a3, s2 >a4                                                                    
        answer: s1 = s2 ,s2 = a4;下一次循环从a5开始,此时可保证s1,s2最小                
    3:                                                                           
        s1 > a3,s2 < a4                                                                    
        answer:    s1 = a3,s2 = s2;    下一次循环从a4开始,因为存在 a3(s1) > a4 的可能     
    4:                                                                            
            s1 > a3,s2 >a4                                                              
        answer:    {                                                                      
                 若 a3 > s2 则s1 = s2;s2 = a4  :因为a4无关,不能采取上面的策略        
                   否则 s1 = a3,s2 = a4;                                               
                } 下一次循环从a5开始,此时可保证s1,s2最小;
                                          
/*****************************************************************************************/

// arithmetic code
//寻找一个序列中,值最小的的两个数是s1 ,s2;其中s1放较大的数
void Get_Little(int a[], int a_length, int &s1, int &s2)
{
    //初始化s1 and s2;并将较大的数放在s1中
    s1 = a[0], s2 = a[1];
    Make_Big_First(s1,s2);
   
    for(int i = 2; i != a_length; ++i)
    { 
        if(s1 < a[i])
        {
            if(i != a_length - 1 && s2 > a[i+1])
            {
                s1 = s2,s2 = a[i+1];
                ++i;    //若s2 > a[i+1],则下一次比较只需要从i+2处开始;+2 : 在此+1,for循环+1           
            }
               
        }
        else if(s1 > a[i])
        {
            s1 = a[i];

            if(i != a_length - 1 && s2 > a[i+1])
            {       
                if(a[i] > s2)//若成立,则在此更新s1的值
                    s1 = s2;
                s2 = a[i+1];
                ++i;//若s2 > a[i+1],则下一次比较只需要从i+2处开始;+2 : 在此+1,for循环+1
            }
        }
        //将较大的数存储在s1中
        Make_Big_First(s1,s2);   
    }
}
显然,算法的时间复杂度为O(n);
代码未认真推敲;


posted @ 2010-04-22 22:00 arthurs 阅读(730) | 评论 (0)编辑 收藏
  2010年4月2日
Hello C++ blog!
posted @ 2010-04-02 14:57 arthurs 阅读(203) | 评论 (0)编辑 收藏
仅列出标题