## 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的魅力所在吧。