# 旋转数组

#1. 问题描述

#2. 经典解法

``````reverse(0, i-1) /* cba defgh */
reverse(i, n-1) /* cba hgfed */
reverse(0, n-1) /* defghabc */
``````

``````#include <stdio.h>
#include <string.h>

void reverse(char *base, int left, int right)
{
char *p = base + left;
char *q = base + right;

while ( p < q )
{
char temp = *p;
*p++ = *q;
*q-- = temp;
}
}

int main(int argc, char* argv[])
{

char str[] = "abcdefgh";
int n = strlen(str);
int i = 3;

reverse(str, 0, i-1); printf("%s\n", str);
reverse(str, i, n-1); printf("%s\n", str);
reverse(str, 0, n-1); printf("%s\n", str);
return 0;
}
``````

#3. 创新解法

``````template <class ForwardIterator>
void rotate ( ForwardIterator first, ForwardIterator 	middle,
ForwardIterator last )
{
ForwardIterator next = middle;
w	hile (first!=next)
{
swap (*first++,*next++);
if (next==last) next=middle;
else if (first == middle) middle=next;
}
}
``````

``````#include <stdio.h>
#include <string.h>

void swap(char *p, char *q)
{
if ( p == NULL || q == NULL) return;

char temp = *p;
*p = *q;
*q = temp;
}

void rotate(char* first, char* middle, char* last)
{
char *next = middle;
while( first != next)
{
swap( first++, next++);
if (next == last){ next = middle;}
else if ( first == middle ) { middle = next;}
}
return;
}

int main(int argc, char* argv[])
{

char str[] = "abcdefgh";
int n = strlen(str);
int i = 3;
rotate( str, str + i, str + n);
printf("%s\n", str);
return 0;
}
``````
/
Published under (CC) BY-NC-SA in categories 算法  tagged with C语言  算法