3

オブジェクトの配列を配列の右側にシフトする関数を実装しようとしています。インターネットで見つけたのは循環シフトの実装だけですが、それは私が探しているものではありません。右側に実際に空きスペースがある場合は、要素を右にシフトしたいと思います。オブジェクト Packet の配列を作成し、そのサイズが 10 であるとします。

Packet* a[] = { p4 , p3 , p2 , p1, null, null, null, null, null, null }

シフト機能は、すべてを右にシフトするだけです

{ null ,p4 , p3 , p2 , p1, null, null, null, null, null }

配列の末尾に要素がある場合

{ p10, p9, p8, p7 ,p6 ,p5 ,p4 , p3 , p2 , p1}

関数は何もシフトしません。

 { p4 , p3 , p2 , p1, null, null, null, null, null, null }

私の実装のアイデアは、配列を一時配列にコピーし、元の配列のすべてを消去してから、位置 [0] ではなく位置 [1] からコピーすることです。しかし、これはあまり効率的ではないようです。

他のアイデアはありますか？

4

7 に答える 7

9

配列に n 個の要素があると仮定します。

if(a[n-1]==null){
   memmove(a+1, a, (n-1)*sizeof(Packet*));
   a[0]=null;
}

別の方法は、配列の要素をシフトするのではなく、アクセスに使用するインデックスをシフトすることです。基本的に、あなたがしたいことは、モジュロ n を 1 追加することです。

于 2012-10-03T07:30:25.330 に答える
4

n-1elementに element を代入して、配列を右から左に繰り返しますn。最初の要素に到達したら、それに割り当てnullます。（それがどのような意味でも）

于 2012-10-03T07:23:33.323 に答える
3

C ++での明白な答えは、を使用することstd::vectorです。この場合、次のように単純になります。

if ( a.back() == NULL ) {
    a.insert( a.begin(), NULL );
    a.pop_back();
}

の代わりに、std::dequeを許可することも検討してください。コピーが簡単なオブジェクトのこのような小さな配列の場合。一般的にの単純さが勝ちます。push_frontinsertstd::vector

Cスタイルの配列を使用する必要がある場合は、次のようになります。

if ( *(end( a ) - 1) == NULL ) {
    std::copy_backwards( begin( a ), end( a ) - 1, end( a ) );
    a[0] = NULL;
}

トリックを行う必要があります。

于 2012-10-03T08:17:00.770 に答える
2

POD および非 POD タイプのコンテナー (raw 配列を含む) には、次を使用します。

template <class Iterator, class Distance>
void shiftRight(Iterator begin, Iterator end, Distance dist)
{
    typedef typename std::iterator_traits<Iterator>::value_type value_type;
    Iterator newBegin = begin, oldEnd = end;
    std::advance(newBegin, dist);
    std::advance(oldEnd, -dist);
    std::copy_backward(begin, oldEnd, end);
    std::fill(begin, newBegin, value_type());
}

値カテゴリを処理するため、POD および非POD タイプ用であり、PODcopy_backwardの場合はmemmove(少なくとも gcc で使用される std ライブラリで) 使用します。

std::advanceランダムアクセス反復子の場合、単純な加算/減算を使用しています。

std::fillPODっぽさにも気を配っていstd::copy*ます。

value_type()ポインター型の場合は NULL のみ、bool false の場合、整数型の場合は 0 などです。

配列の使用法:

  int* a[] = { 0, new int(1), new int(2), 0, 0, new int(3) };

  std::for_each(a, a + sizeof(a) / sizeof(*a), [](int* a) { !a ? (std::cout << "null\n") : (std::cout << *a << "\n"); });

  shiftRight(a, a + sizeof(a) / sizeof(*a), 3);
  std::cout << "-----------------------------------------------------\n";

  std::for_each(a, a + sizeof(a) / sizeof(*a), [](int* a) { !a ? (std::cout << "null\n") : (std::cout << *a << "\n"); });

期待どおりの出力:

null
1
2
null
null
3
-----------------------------------------------------
null
null
null
null
1
2
于 2012-10-03T09:35:35.227 に答える
2

これを頻繁に行う場合 (および配列が小さくない場合) は、std::deque両端で効率的に挿入および削除できるため、 の使用を検討してください。場所の右へのシフトは、後ろからヌルをポップし、前にヌルをプッシュするNことで置き換えることができます。そのためにも使えます。NNstd::rotate

于 2012-10-03T07:32:35.053 に答える
0

要素のシフト/シフト解除またはプッシュ/ポップを可能にするリンク リストの実装を試すことができます (この場合、スペースは解放されます)。

それを行う円形の方法の何が問題になっていますか? その非常に効率的です。例えば。：

bool insert(Packet *queue[], int *rear, int front, Packet *value)
{
  int tmp = (*rear+1) % MAX;
  if (tmp == front) 
    return false;

  *rear = tmp;
  queue[*rear] = value;
  return true;
}

bool delete(Packet *queue[], int rear, int *front, Packet **value) 
{
  if (*front == rear) 
    return false;

  *front = (*front+1) % MAX;
  *value = queue[*front];
  return true;
}
于 2012-10-03T07:29:01.907 に答える