最大子阵列代码的分割错误

Question

我正在编码C上的最大子数组问题，并面临segFault错误。我单独测试了find_max_crossing_subarray功能，它工作得很好。但是，当我添加find_maximum_subarray功能时，出现了错误。你知道我的代码有什么问题吗?

Thx

#include <stdio.h>
#include <limits.h>
typedef struct Tuple{
    int max_left;
    int max_right;
    int left_plus_right;
}Tuple;

struct Tuple find_max_crossing_subarray(int A[], int low, int mid, int high){
    int left_sum = INT_MIN;
    int sum = 0;
    int i;  
    int max_left;
    int max_right;
    for (i = mid; i >= low; i--){
        sum += A[i];
        if (sum > left_sum){
            left_sum = sum;
            max_left = i;
        }
    }
    int right_sum = INT_MIN;
    sum = 0;
    for (i = mid + 1; i <= high; i++){
        sum += A[i];
        if (sum > right_sum){
            right_sum = sum;
            max_right = i;
        }
    }
    Tuple r = {max_left, max_right, left_sum+right_sum};
    return r;
}
struct Tuple find_maximum_subarray(int A[], int low, int high){
    int mid;        
    Tuple r;
    int left_sum;
    int right_sum;
    int cross_sum;
    if (low == high){
        r.max_left = low;
        r.max_right = high;
        r.left_plus_right = A[low];
        return r;
    }
    else{
        mid = (low+mid)/2;
        Tuple r_left = find_maximum_subarray(A, low, mid);
        Tuple r_right = find_maximum_subarray(A, mid+1, high);
        Tuple r_cross = find_max_crossing_subarray(A,low, mid, high);
        if (left_sum >= cross_sum && left_sum >= right_sum){
            return r_left;
        }
        else if (right_sum >= cross_sum && right_sum >= left_sum){  
            return r_right;
        }
        else{
            return r_cross;
        }
    }
}

int main(){
    int A[10] = {-1,2,4,5,-6,2,-1,4,-5,-1};
    int low = 0;
    int high = 9;
    struct Tuple avg;
    avg = find_maximum_subarray(A, low, high);
    printf("max_left: %dn",avg.max_left);
    printf("max_right: %dn",avg.max_right);
    printf("left_plus_right: %dn",avg.left_plus_right);
}

编辑:

gdb executable先输出run

Starting program: path_to_executable/maxSubArray 
Program received signal SIGSEGV, Segmentation fault.
0x0804854d in find_maximum_subarray ()

Answer 1

我复制了你的代码并在GDB下运行它。你被困在一个无限循环中了:

mid = (low+mid)/2;
Tuple r_left = find_maximum_subarray(A, low, mid);
Tuple r_right = find_maximum_subarray(A, mid+1, high);

莫名其妙，low = 3和high = 1。然后是mid = 4/2，再调用r_right = find_maximum_subarray(A, 1, 3)，再遍历一次。段错误是由堆栈溢出错误引起的。

调用栈的前几层看起来像这样:

#65496 0x00000000004006aa in find_maximum_subarray (A=0x7fffffffde50, low=1, high=-67111995) at so-help.c:59
#65497 0x0000000000400687 in find_maximum_subarray (A=0x7fffffffde50, low=1, high=0) at so-help.c:58
#65498 0x0000000000400687 in find_maximum_subarray (A=0x7fffffffde50, low=1, high=0) at so-help.c:58
#65499 0x0000000000400687 in find_maximum_subarray (A=0x7fffffffde50, low=1, high=9) at so-help.c:58
#65500 0x00000000004006aa in find_maximum_subarray (A=0x7fffffffde50, low=0, high=9) at so-help.c:59

指向未初始化的high。

问题是:

mid = (low+mid)/2;

你可能指的是low+high。

修复这个可以让它在没有分段故障的情况下运行，尽管你仍然需要修复left_sum, right_sum和cross_sum——它们也在未初始化的情况下使用，并且不清楚它们应该是什么。

在将来，考虑使用-Wuninitialized或-Wall选项进行编译——当我打开它们时，gcc会为我发现错误。