我的C++合并排序程序有什么问题？

Question

我被这个实现困住了。在合并子阵列期间，我的n2变量被覆盖，这是什么原因造成的？我尝试过硬编码的值，但似乎并不奏效。

#include <iostream> 
#include <cstdlib> 
#include <ctime> // For time(), time(0) returns the integer number of seconds from the  system clock 
#include <iomanip> 
#include <algorithm> 
#include <cmath>//added last nite 3/18/12 1:14am 

using namespace std; 

int size = 0; 

void Merge(int A[], int p, int q, int r) 
{ 
    int i, 
     j, 
     k, 
     n1 = q - p + 1, 
     n2 = r - q; 

    int L[5], R[5]; 

    for(i = 0; i < n1; i++) 
     L[i] = A[i]; 

    for(j = 0; j < n2; j++) 
     R[j] = A[q + j + 1]; 

    for(k = 0, i = 0, j = 0; i < n1 && j < n2; k++)//for(k = p,i = j = 1; k <= r; k++) 
    { 
     if(L[i] <= R[j])//if(L[i] <= R[j]) 
     { 
      A[k] = L[i++]; 
     } else { 
      A[k] = R[j++]; 
     } 
    } 
} 

void Merge_Sort(int A[], int p, int r) 
{ 
    if(p < r) 
    { 
     int q = 0; 
     q = (p + r)/2; 
     Merge_Sort(A, p, q); 
     Merge_Sort(A, q+1, r); 
     Merge(A, p, q, r); 
    } 
} 

void main() 
{ 
    int p = 1, 
     A[8]; 

    for (int i = 0;i < 8;i++) { 
     A[i] = rand(); 
    } 
    for(int l = 0;l < 8;l++) 
    { 
     cout<<A[l]<<" \n"; 
    } 
    cout<<"Enter the amount you wish to absorb from host array\n\n"; 
    cin>>size; 
    cout<<"\n"; 
    int r = size; //new addition 
    Merge_Sort(A, p, size - 1); 

    for(int kl = 0;kl < size;kl++) 
    { 
     cout<<A[kl]<<" \n"; 
    } 

} 

Answer 1

void Merge(int A[], int p, int q, int r) 
{ 
    int i, 
     j, 
     k, 
     n1 = q - p + 1, 
     n2 = r - q; 

    int L[5], R[5]; 

    for(i = 0; i < n1; i++) 
     L[i] = A[i]; 

你只分配L[5]，但n1束缚你是基于输入q和p使用 - 主叫方被允许调用该函数，使写作q和p值在L[]的范围之外。这可以表现为覆盖任何其他自动变量，但由于它是未定义的行为，几乎任何事情都可能发生。 （包括security vulnerabilities）

我不知道最好的方法来解决这个问题 - 我不明白你为什么在Merge()有固定长度的缓冲区，但我没有仔细阅读，发现为什么 - 但当i大于或等于5时，您不应访问L[i]。

整个对话也适用于R[]。而且，由于*A传递给Merge()，因此确保您的数组访问它始终处于绑定状态是有意义的。 （我没有发现它们超出范围，但因为这些代码需要重新工作，所以我不确定这值得我仔细寻找它们。）

Answer 2

你用什么工具编译程序？有一些标志会打开e，.g中这类东西的检查。 gcc（例如-fmudflap，我没有使用它，但看起来很有用）。

如果您可以使用调试器（例如gdb），您应该能够为变量n2添加一个'数据监视'，并且只要检测到写入n2的任何内容，调试器就会停止该程序。这应该有助于你追踪错误。或者尝试valgrind。

一个简单的技术暂时停止这种类型的错误是把周围越来越捣毁了一个有些虚拟变量，所以：被丢弃

int dummy1[100]; 
int n2 = r - q; 
int dummy2[100]; 

int L[5], R[5]; 

变量通常通过代码编写超出数组的界限造成的。 罪魁祸首可能是R[5]，因为这可能是最接近的。您可以查看虚拟变量以查看正在写入的内容，并且可以从中推断出正在发生的事情。

另一种选择是在追踪问题的同时使所有阵列变得巨大。再次将值设置为超出正确范围的值，并检查应保持不变的值。

你可以做一个小宏来做这些检查，并将它放在任何方便的地方。

Answer 3

我以前使用过类似的合并函数，它似乎没有正常工作。然后我重新设计，现在它工作得很好。以下是C++中重新设计的合并函数的函数定义。

void merge(int a[], int p, int q, int r){ 
    int n1 = q-p+1;    //no of elements in first half 
    int n2 = r-q;    //no of elements in second half 
    int i, j, k; 

    int * b = new int[n1+n2]; //temporary array to store merged elements 

    i = p; 
    j = q+1; 
    k = 0; 
    while(i<(p+n1) && j < (q+1+n2)){  //merging the two sorted arrays into one 
     if(a[i] <= a[j]){ 
      b[k++] = a[i++]; 
     } 
     else 
      b[k++] = a[j++]; 
    } 

    if(i >= (p+n1))   //checking first which sorted array is finished 
     while(k < (n1+n2))  //and then store the remaining element of other 
      b[k++] = a[j++]; //array at the end of merged array. 
    else 
     while(k < (n1+n2)) 
      b[k++] = a[i++]; 

    for(i = p,j=0;i<= r;){  //store the temporary merged array at appropriate 
     a[i++] = b[j++];  //location in main array. 
    } 

    delete [] b; 
} 

我希望它有帮助。