0

我有一个包含 26 个英文字母字符的数组。说：

char a[26] = ['a','b','c','d'.......so on till ....'z']

我需要以圆形方式（可以顺时针或逆时针）移动数组中的元素。

我知道存在一种称为循环数组的数据结构，但它是单向的。

说，我想将数组中的每个元素向前移动 3 个元素，然后新数组应该是：

char new[26] = ['x','y','z','a','b'... and so on till 'w']

但是，我可能还想将元素向后移动 2 个元素，那么我的新数组应该是：

char new[26]=['c','d','e'....and so on... 'y','z','a','b']

所有这些都应该在不使用指针的情况下完成（因为我还没有读过指针）。

有没有办法实现这个？

我已经搜索了很多关于圆形数组的信息，但我从未意识到简单的数组可以用作圆形数组并且可以向前和向后移动元素。有人可以告诉我是否有办法做到这一点？

数组大小是固定的。

我们用 C 编码

4

2 回答 2

0

您只需在数组上使用模数index：

size_t index;
size_t move_index(int pos_or_neg_steps) {
    return (index + pos_or_neg_steps) % 26;
}
于 2013-09-08T20:13:09.910 回答
0

天真地用O(1)额外的记忆和O(n^2)时间

C代码（天真）：

void shiftElements(int *array, int size, int shift) {
  int i,reverse;

  reverse = shift < 0;
  if(shift < 0)
    shift = -shift;
  if(shift > size) 
    shift %= size;

  for(i=0; i < shift; ++i) {
    if(reverse)
      shiftForward(array,size);
    else
      shiftBackwards(array,size);
  }
}

void shiftForward(int *array, int size) {
  int tmp = array[size-1];
  int i;
  for(i=size; i>0; --i)
    array[i] = array[i-1]; 
  array[0] = tmp;
}

void shiftBackward(int *array, int size) {
  int tmp = array[0];
  int i;
  for(i=0; i<size; ++i)
    array[i] = array[i+1]; 
  array[size-1] = tmp;
}

有效地使用O(N)额外的内存和O(N)时间

C代码（高效）：

void shiftElements(int *array, int size, int shift) {
  int i,reverse,absVal,*tmp;

  reverse = shift < 0;
  absVal  = shift < 0 ? -shift : shift;
  if(shift > size) 
    shift %= size;
  *tmp = malloc(shift * sizeof *array);

  for(i=0; i < absVal; ++i)
    tmp[i] = array[size-shift+i];

  for(i=0; i < size; ++i)
    array[(i+shift)%size] = array[i];

  for(i=0; i < absVal; ++i)
    array[size+shift+i] = tmp[i];
  free(tmp);
} // I still need to test some corner cases, but you should get the idea
于 2013-09-08T21:02:29.007 回答