STL算法我实现之rotate

STL在rotate上的优化是极尽其所能的。分别对前向访问，双向访问，随机访问的数据结构实现了三个版本的rotate。下面是自己按照对三种算法的理解，自己进行的实现。实现中我尽力避免使用C++的特性，从而以后可以在纯C的代码中使用。

下面是我使用到的数据结构，单向链表与双向链表，用于实现算法和验证算法的正确性：

//单链表节点
typedef struct Node* Link;
struct Node{
    int value;
    Link next;
    Link forward(Link& i)
    {
        i=i->next;
        return i;
    }
    void swap(Link& i)
    {
        int temp=i->value;
        i->value=this->value;
        this->value=temp;
    }
};
 
typedef struct BiNode* BiLink;
struct BiNode{
    int value;
    BiLink next;
    BiLink prev;
    BiLink forward(BiLink& i)
    {
        i=i->next;
        return i;
    }
    BiLink backward(BiLink& i)
    {
        i=i->prev;
        return i;
    }
    void swap(BiLink& i)
    {
        int temp=i->value;
        i->value=this->value;
        this->value=temp;
    }
};

版本一：forward iterator,即类单向链表上的rotate

//forward iterator,即类单向链表
void forwardRotate(Link head,Link middle)
{
    Link i=middle;
    while(true)
    {
        head->swap(i);
        head->forward(head);
        i->forward(i);
        if(head==middle)
        {
            if(i==NULL) return ;            //如果前后两指针同时到达末尾，则结束
            middle=i;                       //如果前者先到达末尾，则将i作为middle，继续rotate
        }
        else if(i==NULL)
            i=middle;                       //如果后者先到达末尾，则将middle作为i，继续rotate
    }
}

另附上注释的图像版以帮助理解：

版本二：bidirection iterator,即类双向链表上的rotate

这个版本的算法很容易理解，即是分段进行反转，之后对左右数据进行反转，代码如下：

void reverse(BiLink first,BiLink last)
{
    while(first!=last &&first!=last->backward(last))
    {
        last->swap(first);
        first->forward(first);
    }
}
 
void bidirectionRotate(BiLink first,BiLink middle,BiLink last)
{
    reverse(first,middle);
    reverse(middle,last);
    reverse(first,last);
}

版本三：random access iterator,即类数组上的rotate

该版本的效率无疑是最高的，当然算法因为涉及到有关群论的知识所以有点难以理解。其理论支持详见：数组循环移位问题

自己实现版本的代码如下：

//求最大公约数
int gcd(int m,int n)
{
    int t;
    while(n!=0)
    {
        t=m%n;
        m=n;
        n=t;
    }
    return m;
}
//循环移位
void rotate_cycle(int array[],int len,int initial,int shift)
{
    int value=array[initial];
    int first=initial;
    int next=initial+shift;
    while(next!=initial)
    {
        array[first]=array[next];
        first=next;
        next=(next+shift)%len;
    }
    array[first]=value;
}
 
void randomRotate(int array[],int middle,int len)
{
    int n=gcd(len,middle);
    while(n--)
        rotate_cycle(array,len,n,middle);
}

最后附上我自己的测试代码：

int main()
{
    int len=20;
    srand(time(0));
    //单向访问链表的rotate
    Link head=new Node;
    head->value=25;
    cout<<head->value<<"\t";
    Link p=head;
    Link middle;
    for(int i=0;i<len;i++)
    {
        Link next=new Node;
        p->next=next;
        next->value=rand()%200;
        cout<<next->value<<"\t";
        if(i==len/4*3)
            middle=p;
        p=p->next;
    }
    cout<<endl;
    p->next=NULL;
    forwardRotate(head,middle);	
    p=head;
    while(p!=NULL)
    {
        cout<<p->value<<"\t";
        p=p->next;
    }
    cout<<endl;

    //双向链表的rotate
    BiLink bihead=new BiNode;
    bihead->value=25;
    cout<<bihead->value<<"\t";
    BiLink bip=bihead;
    BiLink bimiddle;
    for(int i=0;i<len;i++)
    {
        BiLink binext=new BiNode;
        bip->next=binext;
        binext->prev=bip;
        binext->value=rand()%200;
        cout<<binext->value<<"\t";
        if(i==len/4)
            bimiddle=bip;
        bip=bip->next;
    }
    cout<<endl;
    BiNode end;
    bip->next=&end;
    end.prev=bip;
    bidirectionRotate(bihead,bimiddle,&end);	
    bip=bihead;
    while(bip!=&end)
    {
        cout<<bip->value<<"\t";
        bip=bip->next;
    }
    cout<<endl;

    int array[len];
    for(int i=0;i<len;i++)
    {
        array[i]=rand()%200;
        cout<<array[i]<<"\t";
    }	
    cout<<endl;
    randomRotate(array,len/3,len);
    for(int i=0;i<len;i++)
        cout<<array[i]<<"\t";
    cout<<endl;
    return 0;
}

OK，大致如此了。三个版本的rotate，极至的优化手段，这也许就是STL的魅力所在吧。

本文作者 ： cyningsun
本文地址 ： https://www.cyningsun.com/04-25-2011/stl-rotate.html
版权声明 ：本博客所有文章除特别声明外，均采用 CC BY-NC-ND 3.0 CN 许可协议。转载请注明出处！