c - 在合并排序中释放分配给已排序子数组的内存时出错

Question

我有以下实现归并排序的 merge_Sort() 函数。

它确实排序正确(当我注释掉 free() 调用时)，但是当我尝试释放已排序子数组占用的内存时出现问题。

/* merge_Sort() to merge array by didive and conquer*/
/* calls merge_v_1() to merge two sorted subarrays*/
/* merge_v_1() takes two sorted subarrays and copies them to new sorted array, and returns the pointer to this new sorted array*/
int *merge_Sort(int *array, int a, int b)
{
    if (a==b)
    return array;
   else
    {
         int middle = ((a+b)/2);
         int *left_Sub_Array, *right_Sub_Array;
         int *left_Sub_Array_1, *right_Sub_Array_1;

          left_Sub_Array = merge_Sort(array, a, middle);
          right_Sub_Array = merge_Sort((array + (middle - a + 1) ), middle + 1 ,b);

           left_Sub_Array_1 = left_Sub_Array;
           right_Sub_Array_1 = right_Sub_Array;

            int *newArray = malloc((b - a + 1) * (sizeof(int)));
            if (newArray == NULL)
             {
                  exit (1);
              }
             merge_v_1(left_Sub_Array_1, (middle - a + 1), right_Sub_Array_1, (b - middle), newArray);
         // PROBLEM IS HERE IN BELOW TWO FREE()
         free(left_Sub_Array);
         free(right_Sub_Array);
         return (newArray);
     }
}

最初，我认为这是因为函数 merge_v_1() 正在更改指针 left_Sub_Array 和 right_Sub_Array。所以我想将 left_Sub_Array 和 right_Sub_Array 的值复制到 left_Sub_Array_1 和 right_Sub_Array_1，然后将它们传递给 merge_v_1( ), 这样 left_Sub_Array 和 right_Sub_Array 的值就不会改变。但是，我在释放内存时仍然遇到问题。

下面是一个示例输出。

user $ ./a.out
*** Error in `./a.out': free(): invalid pointer: 0x0000000002272014 ***
Aborted (core dumped)
user $ 

看起来我正在尝试释放我不应该释放的内存，但我无法找出根本原因。感谢您的帮助。

Answer 1

您有 1 个 malloc 和 2 个 free。这总是一个问题。来自维基百科: http://en.wikipedia.org/wiki/C_dynamic_memory_allocation

The improper use of dynamic memory allocation can frequently be a source of bugs. These can include security bugs or program crashes, most often due to segmentation faults.

Most common errors are as follows:

Not checking for allocation failures. Memory allocation is not guaranteed to succeed, and may instead return a null pointer. If there's no check for successful allocation implemented, this usually leads to a crash of the program, due to the resulting segmentation fault on the null pointer dereference. Memory leaks. Failure to deallocate memory using free leads to buildup of non-reusable memory, which is no longer used by the program. This wastes memory resources and can lead to allocation failures when these resources are exhausted. Logical errors. All allocations must follow the same pattern: allocation using malloc, usage to store data, deallocation using free. Failures to adhere to this pattern, such as memory usage after a call to free (dangling pointer) or before a call to malloc (wild pointer), calling free twice ("double free"), etc., usually causes a segmentation fault and results in a crash of the program. These errors can be transient and hard to debug – for example, freed memory is usually not immediately reclaimed by the OS, and thus dangling pointers may persist for a while and appear to work.

我会检查您围绕 newArray 的逻辑并摆脱第二个免费的。