Смещение кругового массива

Question

У меня есть домашнее задание, которое требует смещения кругового массива -n мест в памяти.

Я выполнил задачу со следующим ++ Синтаксис C:

while (r < 0) // rotate negatively. 
{ 
    if (i == top+1) 
    { 
     current->n = items[top+1].n; 
     items[top+1].n = items[back-1].n; 
    } 
    midPtr->n = items[++i].n; 
    items[i].n = current->n; 

    if (i == back-1) 
    { 
      items[back-1].n = current->n; 
      i = 0; 
      r++; continue; 
    } 
    else 
    { 
      current->n = items[++i].n; 
      items[i].n = midPtr->n; 
      if (i == back-1) 
      { 
        i = 0; 
        r++; continue; 
      } 
    } 
} 

было интересно, если кто-то лучше, более эффективный метод сдвига круговой массив с помощью -n единиц.

Потому что я, кажется, выполняю ненужные переводы между переменными ptr.

Answer 1

Без указания кода (это, в конце концов, домашнее задание) рассмотрим это ... Круговой массив - это просто распределение n единиц в памяти и указатель на «начало» массива. Первый элемент массива не должен быть младшим адресом в выделенной памяти, а просто указателем/индексом для элемента в массиве, который представляет логический первый элемент. Смещение массива просто сдвигает индекс первого элемента. Это можно сделать без циклов, просто рассчитать, как далеко должен двигаться индекс - с учетом кругового характера структуры данных.

Answer 2

Finnicky, но, я думаю, ОК (есть слишком много мест, которые МОГУТ иметь ошибки «один за другим», чтобы убедиться в их соблюдении - просто убедитесь, что у вас есть тонна модульных тестов ;-). Лично, всякий раз, когда сталкиваешься с такими проблемами (в контексте реальной работы - увы, время домашней работы далеко впереди для меня ;-) Я склонен сосредоточиться на том, что я узнал от Гриса давным-давно ...: любая задача «своп двух блоков» внутри массива может быть выполнена достаточно эффективно (линейное время, 0 дополнительная память) с одним примитивом - «инвертировать блок». Визуальный массив как обычный компактный кусок памяти, у вас есть ...:

start 
    . 
    . 
beg1 
    . 
    . 
end1 
    . 
    . 
beg2 
    . 
    . 
end2 
    . 
    . 
finis 

и ваша задача состоит в том, чтобы поменять блок (beg1..end1) с блоком (beg2..end2). Решение Грис является (в каждом случае блока с учетом (begin..end) с крайностями в комплекте):

1. invert (beg1..end2) 
2. invert (end2..beg2) 
3. invert (end2+1..end1-1) 
4. invert (end1..beg1) 

... это все -) С инвертный (X..Y) принимает (Y-X +1) элементарные движения, решение Гриса принимает 2 * (end2-beg1 + 1) такие движения - относительные накладные расходы по сравнению с решением «минимально возможные элементарные движения» могут быть высокими в некоторых особых случаях (beg2 намного больше, чем end1 AND два блока точно такой же длины, например), но общность и недостаток финишных забот о проблемах по отдельности делает его полезным для меня чаще, чем нет.

«Вращение» - частный случай «обменять два блока», конечно. Таким образом, мой инстинкт будет состоять в том, чтобы убедиться, что у меня есть «инвертированный» примитив (гораздо проще программировать в любом случае ;-), а затем использовать его.

Но тогда мне нужно беспокоиться только о том, что мой код чист, правилен и быстр, а не о том, как TA оценит его, по общему признанию ;-).