0

26 個の英語のアルファベット文字の配列があります。言う：

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

配列内の要素を循環的に移動する必要があります (時計回りまたは反時計回り)。

Circular Array と呼ばれるデータ構造が存在することは理解していますが、それは単方向です。

たとえば、配列内の各要素を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 に答える