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<<"	";
		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<<"	";
				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<<"	";
				p=p->next;
		}
		cout<<endl;

		//双向链表的rotate
		BiLink bihead=new BiNode;
		bihead->value=25;
		cout<<bihead->value<<"	";
		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<<"	";
				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<<"	";
				bip=bip->next;
		}
		cout<<endl;

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

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