转换数组C ++中的元素

一尘不染

转换数组C ++中的元素

algorithm

我已经为我的堆栈对象类开发了一种称为“旋转”的方法。我要做的是，如果堆栈包含元素：{0,2,3,4,5,6,7}我将需要向前和向后旋转元素。

如果我需要向前旋转2个元素，那么数组中将有{3,4,5,6,7,0,2}。而且如果我需要向后旋转或-3个元素，那么，看一下原始数组，它就是{5,6,7,0,2,3,4}

因此，我开发的方法效果很好。IMO效率极低。我想知道是否可以使用mod运算符将数组包装起来？或者，如果它们是我尚未意识到的无用的代码所困扰，等等。

我想我的问题是，如何简化这种方法？例如使用更少的代码。:-)

void stack::rotate(int r)
{
    int i = 0;
    while ( r > 0 ) // rotate postively.
    {
        front.n = items[top+1].n;
        for ( int j = 0; j < bottom; j++ )
        {
            items[j] = items[j+1];                                  
        }
        items[count-1].n = front.n;
        r--;
    }

    while ( r < 0 )  // rotate negatively.
    {
        if ( i == top+1 )
        {
            front.n = items[top+1].n;  
            items[top+1].n = items[count-1].n; // switch last with first
        }

        back.n = items[++i].n; // second element is the new back
        items[i].n = front.n; 
        if ( i == bottom )
        {
            items[count-1].n = front.n; // last is first
            i = 0;  
            r++;   
            continue;
        }
        else
        {
            front.n = items[++i].n;
            items[i].n  = back.n;
            if ( i == bottom )
            {
                i = 0;
                r++; 
                continue;
            }
        }
    }
}

阅读 263

2020-07-28

共1个答案

一尘不染

以下功能rotate基于提醒（您是在“ mod”操作下表示此意思吗？）

这也是相当有效的。

// Helper function.
// Finds GCD. 
// See http://en.wikipedia.org/wiki/Euclidean_algorithm#Implementations
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}

// Number of assignments of elements in algo is
// equal to (items.size() + gcd(items.size(),r)).
void rotate(std::vector<int>& items, int r) {
  int size = (int)items.size();
  if (size <= 1) return; // nothing to do
  r = (r % size + size) % size; // fits r into [0..size)
  int num_cycles = gcd(size, r);
  for (int first_index = 0; first_index < num_cycles; ++first_index) {
    int mem = items[first_index]; // assignment of items elements
    int index = (first_index + r) % size, index_prev = first_index;
    while (index != first_index) {
      items[index_prev] = items[index]; // assignment of items elements
      index_prev = index;
      index = (index + r) % size;
    };
    items[index_prev] = mem; // assignment of items elements
  }
}

当然，如果如其他答案中所述适合更改数据结构，则可以获得更有效的解决方案。

2020-07-28