奇怪的錯誤在C++涉及新的和刪除[]功能

Question

我正在對Coursera的算法：設計和分析課程（https://www.coursera.org/course/algo）的第一個編程作業。 它涉及使用合併排序來倒數計數（http://en.wikipedia.org/wiki/Inversion_(discrete_mathematics））。我認爲這將是一個相對簡單的因爲我在之前（在學校）遇到過合併排序。

#include <iostream> 
#include <fstream> 

using namespace std; 

int *half(int *array, int n, int start, int end) 
{ 
    /* 
    * Creates a new array which contains elements from ''array'' starting with ''start'' 
    * and ending with ''end - 1''. 
    */ 

    int *new_array = new int[end-start]; 

    for(int i = start; i < end; i++) 
    { 
     new_array[i-start] = array[i]; 
    } 

    return new_array; 
} 

int merge(int *array1, int n1, int *array2, int n2, int *new_array) 
{ 
    /* 
    * Merges arrays 1 and 2 (with lengths n1 and n2) into a new_array, counting 
    * ''split inversions'' by the way. 
    */ 
    int i = 0, j = 0, count = 0; 

    for(int k = 0; k < n1 + n2; k++) 
    { 

     if(i >= n1) 
     { 
      new_array[k] = array2[j]; 
      j++; 
      continue; 
     } 

     if(j >= n2) 
     { 

      new_array[k] = array1[i]; 
      i++; 
      continue; 
     } 

     if(array1[i] <= array2[j]) 
     { 
      new_array[k] = array1[i]; 
      i++; 
     } 
     else 
     { 
      new_array[k] = array2[j]; 
      j++; 
      count++; 
     } 
    } 

    return count; 
} 

int mergesort(int *array, int n) 
{ 

    if(n == 1) return 0; //base case 

    int x, y, z; 
    int odd; 

    if(n%2 == 0) odd = 0; 
    else odd = 1; 

    int *half1 = new int [n/2]; 
    int *half2 = new int [n/2 + odd]; 

    half1 = half(array, n, 0, n/2); 
    half2 = half(array, n, n/2, n); 

    x = mergesort(half1, n/2); 
    y = mergesort(half2, n/2 + odd); //if n is odd, we add one 
    z = merge(half1, n/2, half2, n/2 + odd, array); //we write a sorted array back in our starting array 

    delete [] half1; 
    delete [] half2; 

    return x + y + z; 
} 

int main() 
{ 
    int n; 
    int *array = new int[n]; 

    cin >> n; 

    for(int i = 0; i < n; i++) 
    { 
     int x; 
     cin >> x; 
     array[i] = x; 
    } 

    for(int i = 0; i < n; i++) 
     cout << array[i] << " "; 

    cout << endl; 
    cout << "Number of inversions: " << mergesort(array, n) << endl; 

    for(int i = 0; i < n; i++) 
    cout << array[i] << " "; 

    cout << endl; 
    delete[] array; 

    return 0; 
} 

那麼，這裏有什麼奇怪的東西呢？第一件事：對我來說，它適用於某些數組，但對於其他數組會崩潰（稍後的示例）。第二件事：我向我的朋友發送了代碼，他說一切正常，對他而言，即使是那些對我來說都很顯着的例子。

所以，例子：

對於陣列[1 2 3 4 5 6 7] G ++產生這樣的：

malloc.c:2451: sYSMALLOc: Assertion `(old_top == (((mbinptr) (((char *) &((av)->bins[((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk, fd)))) && old_size == 0) || ((unsigned long) (old_size) >= (unsigned long)((((__builtin_offsetof (struct malloc_chunk, fd_nextsize))+((2 * (sizeof(size_t))) - 1)) & ~((2 * (sizeof(size_t))) - 1))) && ((old_top)->size & 0x1) && ((unsigned long)old_end & pagemask) == 0)' failed. 
Aborted (core dumped) 

當我 '' 回溯 '用gdb它'：

#0 0x00007ffff7753445 in __GI_raise (sig=<optimized out>) at ../nptl/sysdeps/unix/sysv/linux/raise.c:64 
#1 0x00007ffff7756bab in __GI_abort() at abort.c:91 
#2 0x00007ffff779abed in __malloc_assert (assertion=<optimized out>, file=<optimized out>, line=<optimized out>, function=<optimized out>) at malloc.c:300 
#3 0x00007ffff779e0f4 in sYSMALLOc (av=0x7ffff7ad3720, nb=32) at malloc.c:2448 
#4 _int_malloc (av=0x7ffff7ad3720, bytes=12) at malloc.c:3892 
#5 0x00007ffff779fa45 in __GI___libc_malloc (bytes=12) at malloc.c:2924 
#6 0x00007ffff7b8fded in operator new(unsigned long)() from /usr/lib/x86_64-linux-gnu/libstdc++.so.6 
#7 0x00007ffff7b8ff09 in operator new[](unsigned long)() from /usr/lib/x86_64-linux-gnu/libstdc++.so.6 
#8 0x0000000000400b12 in mergesort (array=0x603010, n=7) at jedan.cpp:81 
#9 0x0000000000400cfe in main() at jedan.cpp:120 

它確實相似對於陣列[1 2 3 4 5 6 7 8 9 10]一些（但不是相同！），再次連接到新的和刪除[]功能。如果有人認爲這會有所幫助，我可以在稍後發佈，但我不想誇大這個帖子太多。 它適用於大多數我試過陣列（我曾與大小< = 6的排列沒有問題，而對於一個相當大的數目更大陣列）。

我使用Ubuntu 12.04，昨天裝...很乾淨清爽。 幫助？

P.S.如果你發現變量名有點奇怪，對不起......我將它們從我的母語中翻譯出來，這樣代碼可以更具可讀性。

Answer 1

int n; 
int *array = new int[n]; // Undefined behavior 

n在這裏使用未初始化，所以你會得到一個「隨機」長度分配。

如果你運氣不好和n持有「大」垃圾值，你的代碼可能出現的工作。如果它的值很小，那麼當你填充你的初始數組時，你可能會破壞你的堆 - 這會產生你所看到的錯誤類型。

的array分配之前移動cin >> n;線。

附註：我覺得你在做mergesort的兩個撥款被泄露（你只delete荷蘭國際集團在half分配的內存，你實際上並不需要在mergesort分配本身，如果我正確地讀出你的代碼）。

Answer 2

你不檢查

n==0 

在歸併（）例程

。

然後將新[]失敗。

BTW，在半（）函數同樣的東西：

int *new_array = new int[end-start]; 

你不檢查的

end == start 

Answer 3

你沒有指定爲陣列數量：

int main() 
{ 
    int n; 
    int *array = new int[n]; 

    cin >> n; 

程序啓動時，您沒有爲n指定值。所以分配的大小是未知的。

我建議在數組分配前移動cin >> n;。