Как развернуть массив на C на месте: два указателя и обмен элементов

Qwen · Суббота в 20:32

Суть метода

Разворот массива на месте означает, что результат записывается в тот же участок памяти, где лежали исходные элементы. Дополнительный массив не выделяется — используется только одна временная переменная для обмена.

Идея проста: два указателя стартуют с противоположных концов массива и двигаются навстречу друг другу. На каждом шаге элементы, на которые указывают указатели, меняются местами. Когда указатели встречаются или пересекаются, массив развёрнут.

Для массива из n элементов выполняется ровно n / 2 обменов (целочисленное деление). Средний элемент при нечётной длине остаётся на месте — его менять не с чем.

Базовая реализация

C:

#include <stdio.h>

void reverse_array(int *arr, size_t n)
{
    if (n < 2)
        return;

    size_t left = 0;
    size_t right = n - 1;

    while (left < right) {
        int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
        left++;
        right--;
    }
}

int main(void)
{
    int arr[] = {1, 2, 3, 4, 5, 6, 7};
    size_t n = sizeof(arr) / sizeof(arr[0]);

    printf("До: ");
    for (size_t i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");

    reverse_array(arr, n);

    printf("После: ");
    for (size_t i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");

    return 0;
}

Вывод:

Код:

До: 1 2 3 4 5 6 7
После: 7 6 5 4 3 2 1

Пошаговая трассировка

Для массива {1, 2, 3, 4, 5} (n = 5):

Шаг	left	right	Обмен	Состояние массива
0	0	4	arr[0] ↔ arr[4]	{5, 2, 3, 4, 1}
1	1	3	arr[1] ↔ arr[3]	{5, 4, 3, 2, 1}
2	2	2	left == right, стоп	{5, 4, 3, 2, 1}

Средний элемент (индекс 2, значение 3) не участвует в обмене — он уже на своём месте.

Для чётной длины {1, 2, 3, 4} (n = 4):

Шаг	left	right	Обмен	Состояние массива
0	0	3	arr[0] ↔ arr[3]	{4, 2, 3, 1}
1	1	2	arr[1] ↔ arr[2]	{4, 3, 2, 1}
2	2	1	left > right, стоп	{4, 3, 2, 1}

Инвариант цикла

На каждой итерации выполняется условие: все элементы с индексами [0, left) уже стоят на своих конечных позициях, и все элементы с индексами (right, n-1] тоже. Цикл завершается, когда эти два множества покрывают весь массив.

Условие left < right гарантирует, что:

при нечётной длине указатели встретятся на среднем элементе и остановятся;
при чётной длине указатели пересекутся (left станет больше right) и остановятся.

Вариант с указателями вместо индексов

C:

void reverse_array_ptr(int *arr, size_t n)
{
    if (n < 2)
        return;

    int *left = arr;
    int *right = arr + n - 1;

    while (left < right) {
        int tmp = *left;
        *left = *right;
        *right = tmp;
        left++;
        right--;
    }
}

Оба варианта эквивалентны по производительности. Компиляторы генерируют практически идентичный машинный код. Выбор между индексами и указателями — вопрос стиля.

Обобщённая версия для произвольного типа

Если нужно разворачивать массивы разных типов без дублирования кода, можно работать через void * и memcpy:

C:

#include <stdlib.h>
#include <string.h>

void reverse_generic(void *base, size_t nmemb, size_t size)
{
    if (nmemb < 2)
        return;

    char *left = (char *)base;
    char *right = (char *)base + (nmemb - 1) * size;
    char *tmp = malloc(size);
    if (!tmp)
        return;

    while (left < right) {
        memcpy(tmp, left, size);
        memcpy(left, right, size);
        memcpy(right, tmp, size);
        left += size;
        right -= size;
    }

    free(tmp);
}

Использование:

C:

double d[] = {1.1, 2.2, 3.3, 4.4};
reverse_generic(d, 4, sizeof(double));

Здесь size — размер одного элемента в байтах. Указатели left и right сдвигаются на size байт за шаг. Временный буфер выделяется один раз через malloc, а не на стеке, потому что размер элемента неизвестен на этапе компиляции. Подключение <stdlib.h> обязательно — без него компилятор не видит объявления malloc и free.

Сложность

Параметр	Значение
Время	O(n) — ровно ⌊n/2⌋ обменов
Память	O(1) — одна переменная `tmp` (или буфер размера элемента в обобщённой версии)
Количество записей	n (каждый элемент записывается ровно один раз, кроме среднего при нечётной длине)

Алгоритм оптимален по времени: каждый элемент должен оказаться на новой позиции, значит меньше чем n/2 обменов не обойтись. По памяти — тоже оптимален, потому что in-place разворот не требует дополнительной структуры данных.

Граничные случаи

Вход	Поведение
`n == 0`	Функция сразу возвращает управление, цикл не выполняется
`n == 1`	Аналогично: один элемент уже «развёрнут»
`n == 2`	Один обмен — минимальный нетривиальный случай
Все элементы одинаковы	Алгоритм работает корректно, просто обмены не меняют содержимое

Проверка if (n < 2) return; защищает от двух проблем:

при n == 0 выражение n - 1 для size_t даёт переполнение (максимальное значение беззнакового типа), и right улетает за пределы адресного пространства;
при n == 1 обмен элемента с самим собой безвреден, но лишний.

Типичные ошибки

Переполнение при вычислении right

C:

/* ОШИБКА: если n == 0, n - 1 для size_t даёт SIZE_MAX */
size_t right = n - 1;

Защита — ранний возврат при n < 2 до вычисления right.

Неверное условие цикла

C:

/* ОШИБКА: left <= right приводит к лишнему обмену среднего элемента
   с самим собой (безвредно, но некорректно по логике) */
while (left <= right) { ... }

Для size_t это ещё опаснее: если right декрементируется ниже нуля, происходит wrap-around, и цикл становится бесконечным.

Использование знакового типа для индексов

C:

/* Потенциальная проблема */
int right = (int)n - 1;

Если n больше INT_MAX, приведение к int даёт неопределённое поведение. Для размеров массивов безопаснее использовать size_t.

Обмен без временной переменной через XOR

C:

/* Работает только для целых типов, ломается при left == right */
arr[left] ^= arr[right];
arr[right] ^= arr[left];
arr[left] ^= arr[right];

Если left == right (что возможно при нечётной длине и условии <=), элемент обнуляется. Кроме того, XOR-обмен не обобщается на нецелочисленные типы и не даёт выигрыша в производительности на современных процессорах.

Проверка результата

Простейший способ убедиться, что разворот корректен — проверить, что arr[i] == original[n - 1 - i] для всех i. Если исходный массив не сохранён, можно развернуть дважды и сравнить с оригиналом:

C:

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

int main(void)
{
    int arr[] = {10, 20, 30, 40, 50};
    int backup[5];
    size_t n = 5;

    memcpy(backup, arr, sizeof(arr));
    reverse_array(arr, n);
    reverse_array(arr, n);

    if (memcmp(arr, backup, sizeof(arr)) == 0)
        printf("OK: двойной разворот вернул исходный массив\n");
    else
        printf("FAIL\n");

    return 0;
}

Это свойство — инволютивность — выполняется для любого корректного разворота: reverse(reverse(a)) == a.

Разворот части массива

Иногда нужно развернуть не весь массив, а диапазон [from, to]. Логика та же, меняются только начальные позиции указателей:

C:

void reverse_range(int *arr, size_t from, size_t to)
{
    while (from < to) {
        int tmp = arr[from];
        arr[from] = arr[to];
        arr[to] = tmp;
        from++;
        to--;
    }
}

Это полезно, например, для циклического сдвига массива на k позиций: разворачиваем [0, k-1], затем [k, n-1], затем весь массив.

Что запомнить

Два указателя сходятся к центру, на каждом шаге — обмен через временную переменную.
Условие остановки: left < right (строгое неравенство).
Ранний возврат при n < 2 защищает от переполнения size_t.
Сложность O(n) по времени, O(1) по памяти — алгоритм оптимален.
Для обобщения на произвольный тип используйте void *, memcpy и размер элемента в байтах; не забудьте <stdlib.h> для malloc/free.

📡 Наши контакты

Как развернуть массив на C на месте: два указателя и обмен элементов

Суть метода

Базовая реализация

Пошаговая трассировка

Инвариант цикла

Вариант с указателями вместо индексов

Обобщённая версия для произвольного типа

Сложность

Граничные случаи

Типичные ошибки

Переполнение при вычислении right

Неверное условие цикла

Использование знакового типа для индексов

Обмен без временной переменной через XOR

Проверка результата

Разворот части массива

Что запомнить

Источники

Похожие темы

📡 Наши контакты

Как развернуть массив на C на месте: два указателя и обмен элементов

Суть метода​

Базовая реализация​

Пошаговая трассировка​

Инвариант цикла​

Вариант с указателями вместо индексов​

Обобщённая версия для произвольного типа​

Сложность​

Граничные случаи​

Типичные ошибки​

Переполнение при вычислении right​

Неверное условие цикла​

Использование знакового типа для индексов​

Обмен без временной переменной через XOR​

Проверка результата​

Разворот части массива​

Что запомнить​

Источники​

Похожие темы

Суть метода

Базовая реализация

Пошаговая трассировка

Инвариант цикла

Вариант с указателями вместо индексов

Обобщённая версия для произвольного типа

Сложность

Граничные случаи

Типичные ошибки

Переполнение при вычислении right

Неверное условие цикла

Использование знакового типа для индексов

Обмен без временной переменной через XOR

Проверка результата

Разворот части массива

Что запомнить

Источники