На месте вращение Практика C++

There is an old trick for rotating elements in an array (I first saw it in Programming Pearls)

Say you want to rotate an array to the left by three elements.

First reverse the first three elements, next reverse the remaining elements, and then reverse the entire array.

Starting Array:
1 2 3 4 5 6 7

After reversing the first three elements
3 2 1 4 5 6 7

After reversing the remaining elements
3 2 1 7 6 5 4

Finally reverse the entire array to get the final rotated array
4 5 6 7 1 2 3

Reversing portions of the array can be done in place so you don't need any extra memory.

You can leave the data in place, and have a "base index" member to indicate where the array should start. You then need to use this to adjust the index when accessing the array. The array itself should be private, and only accessed through accessor functions that do the adjustment. Something like this:

class quack
{
public:
    explicit quack(int size) : items(new Item[size]), size(size), base(0) {}
    ~quack() {delete [] items;}

    void rotate(int n)      {base = (base + n) % size;}
    Item &operator[](int i) {return items[(base + i) % size];}

private:
    quack(quack const&) = delete;          // or implement these if you want
    void operator=(quack const&) = delete; // the container to be copyable

    Item *items;
    int   size;
    int   base;
};

although I'd call it something like RotatableArray, rather than quack.

делать вращения один за другим - не лучший способ. Если вы делаете что-то более двух или трех оборотов, это очень быстро становится очень медленным.

edit: в качестве последней мысли ... размещение элементов в (двойном) связанном «зацикленном» списке (так, чтобы последний элемент указывал на первый), потребовалось бы для поворота, чтобы переместить указатель головы только на несколько элементов. (Указатель заголовка является указателем, указывающим, какой элемент в зацикленном списке является началом.)

на сегодняшний день это самый быстрый (и самый простой) способ выполнить поворот списка элементов

Really the way to do it is to use indexes instead of pointers.

int to = 0;
int from = (to + nRotations) % count;
if (to == from)
    return;

for (int i=0; i < count; i++) {
   swap(from, to);
   from = advance(from);
   to = advance(to);
}

// ...
static inline int advance(int n, int count) { return (n + 1) % count; }

Как обычно, если вам действительно нужно физически повернуть элементы, правильным ответом для C ++ будет использование std :: rotate , который делает именно то, что вы хотите делать.

Если вам необходимо реализовать это вручную (в качестве практического задания), посмотрите на эти слайды алгоритмы из книги Джона Бентли «Жемчужины программирования».

У меня может быть альтернативное решение для вращения массива в линию. Вместо старого трюка с реверсированием множеств элементов, как предлагалось ранее, этот подход работает следующим образом:

Инициализация:

(Примечание q = величина сдвига влево, n = длина массива)

1. Определим первый исходный элемент, который находится на x1=q%n
2. Целевой элемент находится на x2=0
3. char, ch1, это ar[x1] элемент
4. char, ch2, это ar[x2] элемент

Loop on i=0 to n-1, где n = длина массива

1. Перезапишите элемент назначения, ar[x2] с помощью ch1
2. Set ch1 = ch2
3. Set x1 = x2
4. Set x2 = x2 - q
5. Если x2 является отрицательным из-за вышеуказанного вычитания, добавьте к нему n
6. ch2 = ar[x2]

Ниже можно объяснить, как это работает.

Пример, повернуть влево на 2 символа:

a b c d e f g

c d e g g

x1    ch1    x2    ch2
2     c      0     a
0     a      5     f
5     f      3     d
3     d      1     b
1     b      6     g
6     g      4     e
4     e      2     c

Как видите, для этого требуется не более n итераций, поэтому именно линейный алгоритм времени также вращается в строке (не требует дополнительного хранения, кроме нескольких временных переменных).

Вот функция, реализующая вышеприведенный алгоритм, чтобы вы могли попробовать:

void rotate(char *ar, int q)
{
    if (strlen(ar) < 2)
    {
        return;
    }

    if (q <= 0)
    {
        return;
    }

    char ch1;
    char ch2;
    int x1;
    int x2;
    int i;
    int n;

    n = strlen(ar);

    q %= n;

    if (q == 0)
    {
        return;
    }

    x1 = q;
    ch1 = ar[x1];
    x2 = 0;
    ch2 = ar[x2];

    for (i=0;i<n;i++)
    {
        ar[x2] = ch1;
        ch1 = ch2;

        x1 = x2;

        x2 -= q;

        if (x2 < 0)
        {
            x2 += n;
        }

        ch2 = ar[x2];
    }
}