函数在传递动态分配的指针时表现不佳

Question

我有这个功能

void shuffle_array(int* array, const int size){
  /* given an array of size size, this is going to randomly
   * attribute a number from 0 to size-1 to each of the
   * array's elements; the numbers don't repeat */
  int i, j, r;
  bool in_list;
  for(i = 0; i < size; i++){
    in_list = 0;
    r = mt_lrand() % size; // my RNG function
    for(j = 0; j < size; j++)
      if(array[j] == r){
    in_list = 1;
    break;
      }
    if(!in_list)
      array[i] = r;
    else
      i--;
  }
}

当我从

调用这个函数时

int array[FIXED_SIZE];
shuffle_array(array, FIXED_SIZE);

一切顺利，我可以在合理的时间内检查改组是否按预期进行 - 毕竟，它不是那么大的数组（< 1000 个元素）。

但是，当我从

调用函数时

int *array = new int[dynamic_size];
shuffle_array(array, dynamic_size);
[...]
delete array;

该函数无缘无故地永远循环。我已经用调试工具检查过了，但我不能说出哪里会出错（部分原因是我的算法依赖于随机数）。

问题是，它不起作用...我试过将数组作为 int*& array 传递，我试过使用 std::vector<int>&，我试过使用 random_shuffle （但大项目的结果并不令我满意）。

为什么会出现这种情况，我该如何解决？

Answer 1

您将 C 代码与 new 和 delete 的 C++ 内存分配例程混合在一起。而是坚持使用纯 C 并直接使用 malloc/free。

   int *array = malloc(dynamic_size * sizeof(int));
   shuffle_array(array, dynamic_size);
   [...]
   free(array);

附带说明一下，如果您在 C++ 中使用 new[] 运算符分配数组，请使用等效的 delete[] 运算符来正确释放内存。在这里阅读更多 - http://www.cplusplus.com/reference/new/operator%20new[]/

Answer 2

您的问题是 array 在您的第一个示例中未初始化。如果您使用 Visual Studio 调试模式，array 中的每个条目将全部设置为 0xCC（对于 "created"）。这掩盖了您的实际问题（见下文）。

当您使用 new int[dynamic_size] 时，数组被初始化为零。然后这会导致您的实际错误。

您的实际错误是，仅当您的数组尚未包含该项目并且您每次都在查看 整个数组 时，您才尝试添加一个新项目，然而，如果你的数组的最后一个元素已经是一个有效值（比如 0），你的循环将永远不会终止，因为它总是在数组中找到 0 并且已经用完所有其他数字。

要解决此问题，请更改您的算法以仅查看您放入数组的值（即最多 i）。

改变

for(j = 0; j < size; j++)

到

for(j = 0; j < i; j++)

Answer 3

我猜测问题在于数组初始化的方式和行：

r = mt_lrand() % size; // my RNG function

如果动态分配的数组由于某种原因被初始化为0，您的代码将总是在填充数组的最后一个数字时进入堆栈。

我可以想到以下两种方法来克服它：

您确保使用大于或等于 size 的数字初始化 array。

int *array = new int[dynamic_size];
for ( int i = 0; i < dynnamic_size; ++i )
   array[i] = size;
shuffle_array(array, dynamic_size);

您可以允许随机数在1和size之间，而不是在循环中在0和size-1之间。作为第二步，您可以从数组的每个元素中减去 1。

void shuffle_array(int* array, const int size){
   int i, j, r;
   bool in_list;
   for(i = 0; i < size; i++){
      in_list = 0;

      // Make r to be betwen 1 and size
      r = rand() % size + 1;
      for(j = 0; j < size; j++)
         if(array[j] == r){
            in_list = 1;
            break;
         }
      if(!in_list)
      {
         array[i] = r;
      }

      else
         i--;
   }

   // Now decrement the elements of array by 1.
   for(i = 0; i < size; i++){
      --array[i];

      // Debugging output
      std::cout << "array[" << i << "] = " << array[i] << std::endl;
   }
}

函数在传递动态分配的指针时表现不佳

Function behaves badly when passing dynamically allocated pointer

c++

shuffle

dynamic