C++博客-arthurs

严蔚敏《数据结构》（c版）HuffmanTree算法中Select函数算法

arthurs — Thu, 22 Apr 2010 14:00:00 GMT

在严蔚敏《数据结构》（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）；
代码未认真推敲；

arthurs 2010-04-22 22:00 发表评论

Trail one

arthurs — Fri, 02 Apr 2010 06:57:00 GMT

Hello C++ blog!

arthurs 2010-04-02 14:57 发表评论