STL经典算法集锦<四>之rotate
最后更新于：2022-04-01 07:30:39
## 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
该版本的效率无疑是最高的，当然算法因为涉及到有关群论的知识所以有点难以理解。其理论支持详见：[数组循环移位问题](http://blog.csdn.net/xinhanggebuguake/article/details/7498471)
自己实现版本的代码如下：
~~~
//求最大公约数
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的魅力所在吧。