Циклический сдвиг элементов массива

Под циклическим сдвигом понимается перестановка значений всех элементов массива на одну или несколько позиций влево или вправо. При этом значение первого (последнего) элемента массива заносится в последний (первый) элемент массива в зависимости от направления сдвига.

Схематичное изображение циклического сдвига элементов массива вправо на одну позицию, выполняемого в три этапа, показано на рис. 5.4.1. Блок-схема алгоритма, выполняющего такой сдвиг, показана на рис. 5.4.2.

На 1-м этапе значение последнего элемента массива X_N заносится в дополнительную переменную А (блок 1). На 2-м этапе организовывается цикл «Для» на основе блока модификации (блок 2), который перебирает элементы массива Х в обратном порядке, т.е. с правого края (шаг -1), начиная с N -го и заканчивая 2-м элементом. На каждом шаге цикла текущему элементу X_i присваивается значение предыдущего элемента X_{i -1} (блок 3). В результате выполнения 2-го этапа значение предварительно сохраненного последнего элемента массива будет удалено. Значения остальных элементов массива будут смещены на одну позицию вправо. Значение первого элемента массива будет продублировано во втором элементе. На 3-м этапе алгоритма значение дополнительной переменной А, в которой хранится последний элемент исходного массива, будет занесено в первый элемент массива X ₁. В итоге будет выполнен циклический сдвиг элементов массива Х на одну позицию вправо.

Следует обратить внимание на граничные значения параметра цикла i, который изменяется от N до 2. При подстановке этих значений в формулу сдвига не должно происходить обращение к несуществующим элементам массива. При i =N формула сдвига принимает вид X_N = X_{N - 1}, при i =2 – X ₂ = X ₁. В случае если бы правая граница параметра i была равна 1, то в формуле сдвига происходило бы обращение к несуществующему элементу массива с индексом 0: X ₁ = X ₀, что недопустимо.

Схематичное изображение циклического сдвига элементов массива влево на одну позицию, также выполняемого в три этапа, показано на рис. 5.4.3. Блок-схема алгоритма, выполняющего такой сдвиг, показана на рис. 5.4.4.

На 1-м этапе значение первого элемента массива X ₁ заносится в дополнительную переменную А (блок 1). На 2-м этапе организовывается цикл «Для» (блок 2), который перебирает элементы массива Х в прямом порядке, т.е. с левого края (шаг +1), начиная с 1-го и заканчивая N -1-м элементом. На каждом шаге цикла текущему элементу X_i присваивается значение последующего элемента массива X_{i +1} (блок 3). В результате выполнения 2-го этапа значение предварительно сохраненного первого элемента массива будет удалено. Значения остальных элементов массива будут смещены на одну позицию влево. Значение последнего элемента массива будет продублировано в предпоследнем элементе. На 3-м этапе алгоритма значение дополнительной переменной А, в которой хранится первый элемент исходного массива, будет занесено в последний элемент массива X_N. В итоге будет выполнен циклический сдвиг элементов массива Х на одну позицию влево.

Для выполнения циклического сдвига элементов массива на k позиций достаточно k раз выполнить алгоритм сдвига на одну позицию, т.е. добавить внешний цикл, который будет требуемое количество раз повторять сдвиг на одну позицию. Пример блок-схемы алгоритма, выполняющего циклический сдвиг элементов массива на k позиций влево, представлен на рис. 5.4.5.

Сдвиг элементов массива находит применение при удалении или добавлении элементов в массив, а также в других задачах.