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 }

我的实现想法是将数组复制到一个临时数组中，擦除原始数组上的所有内容，然后复制到其中，但从位置 [1] 而不是位置 [0] 开始。但这似乎不是很有效。

还有其他想法吗？

4

7 回答 7

9

假设数组有 n 个元素：

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

另一种方法是不移动数组的元素，而是移动用于访问它的索引。基本上，你想要做的是加 1 模 n。

于 2012-10-03T07:30:25.330 回答
4

从右到左迭代数组，将 element 分配n-1给 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_front, 而不是insert. 对于这么小的数组，简单的复制对象。的简单性std::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

如果您要经常这样做（并且数组不小），请考虑使用std::deque，因为它允许在两端进行有效的插入和删除。N然后可以用N从后面弹出空N值并在前面推空值来替换位置的右移。你也可以使用std::rotate它。

于 2012-10-03T07:32:35.053 回答
2

对于 POD 和非 POD 类型的任何容器（包括原始数组），请使用以下内容：

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 和 nonPOD 类型，因为copy_backward它负责值类别，如果它是 POD，则它使用memmove（至少在 gcc 使用的 std 库中）。

std::advance随机访问迭代器使用简单的加法/减法。

std::fill还像 . 一样照顾 PODness 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 回答
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 回答
0

在 C++11 中，我们有std::rotate.

int [] values = {1, 2, 3, 4, 5};
std::rotate(
    std::begin(values),
    std::next(std::begin(values)), // the new 'top'
    std::end(values));
*std::rbegin(values) = 0;

assert(values[0] == 2);
assert(values[1] == 3);
assert(values[2] == 4);
assert(values[3] == 5);
assert(values[4] == 0);
于 2015-09-28T08:43:46.850 回答