具有靜態結構返回類型的最大子數組

Question

我做了最大的子數組算法，這似乎是錯誤的。由於C不能返回多個值，函數「maxarr」或「maxcarr」應該返回三個值 - （起始索引，結束索引和它的總和）在一個靜態結構「rettype」中。但是，那些返回值似乎是一樣的（我已經檢查過它的內存地址，它們都是一樣的）。我想這個錯誤發生的原因是靜態類型變量只聲明一次，不會被初始化多次，但我不知道如何糾正它。

#include <stdio.h> 
#include <stdlib.h> 

struct rettype 
{ 
    int a; 
    int b; 
    int c; 
}; 

struct rettype* maxarr(int i, int j, int* array); 
struct rettype* maxcarr(int i, int j, int* array); 
int main(void) 
{ 
    int array[20]; 
    int temp = 0; 
    int num = 0; 
    int len = 0; 
    struct rettype* ret; 
    printf("Type length in.\n"); 
    scanf("%d", &len); 
    while (num<len) 
    { 
     printf("%dth element: ", num); 
     scanf("%d", &array[num]); 
     num++; 
    } 
    ret = maxarr(1, len, array); 
    printf("Maximum Subarray:\nfrom element %d to element %d with sum of %d\n", ret->a, ret->b, ret->c); 
    return 0; 
} 

struct rettype* maxarr(int i, int j, int* array) 
{ 
    static struct rettype retb; 
    static struct rettype ret; 
    struct rettype* fretr; 
    struct rettype* fretc; 
    struct rettype* fretl; 
    int hi=j; 
    int mid; 
    int low=i; 
    mid = ((hi + low)/2); 
    if (i == j) {//base case 
     retb.a = i; 
     retb.b = j; 
     retb.c = *(array + i); 
     return &retb; 
    } 
    fretl = maxarr(i, mid, array); 
    fretr = maxarr(mid+1, j, array); 
    fretc = maxcarr(i, j, array); 
    if (fretl->c>fretr->c && fretl->c>fretc->c) 
    { 
     ret.a = fretl->a; 
     ret.b = fretl->b; 
     ret.c = fretl->c; 
     return &ret; 
    } 
    else if (fretr->c>fretl->c && fretr->c>fretc->c) 
    { 
     ret.a = fretr->a; 
     ret.b = fretr->b; 
     ret.c = fretr->c; 
     return &ret; 
    } 
    else 
    { 
     ret.a = fretc->a; 
     ret.b = fretc->b; 
     ret.c = fretc->c; 
     return &ret; 
    } 
} 
struct rettype* maxcarr(int i, int j, int* array) 
{ 
    int mid = (i + j)/2; 
    static struct rettype ret; 
    int a = mid; 
    int b = mid+1; 
    int risum = -9999; 
    int lesum = -9999; 
    int sum = 0; 
    while (a-->i) 
    { 
     sum += *(array + a); 
     if (sum>lesum) 
     { 
      lesum = sum; 
     } 
    } 
    sum = 0; 
    while (b++<j) 
    { 
     sum += *(array + b); 
     if (sum>risum) 
     { 
      risum = sum; 
     } 
    } 
    sum = 0; 
    ret.a = a; 
    ret.b = b; 
    ret.c = risum + lesum; 
    return &ret; 
} 

Answer 1

你正在使用一個static變量，你正在從地址返回給調用者。

在這種情況下，您將爲您的返回值共享相同的內存區域，而不是創建單獨的內存區域。

爲什麼不返回結構代替值（C不能返回數組，但是可以返回結構，幸運）：

struct rettype maxcarr(int i, int j, int* array) 
{ 
    int mid = (i + j)/2; 
    struct rettype ret; 
    ... 
    return ret; 
} 

（拖放static用於返回時被複制的自動變量）

請注意，您必須將此模式應用於所有例程。

Answer 2

Maximum subarray problem
Kadane's algorithm

#include <stdio.h> 

struct rettype { 
    int start; 
    int end; 
    int sum; 
}; 

struct rettype max_subarray(int array[], int length); 

int main(void){ 
    int array[20]; 
    int len = 0, num; 
    struct rettype ret; 

    printf("Type length in.\n"); 
    if(scanf("%d", &len) != 1){ 
     printf("invalid input.\n"); 
     return 1; 
    } 
    if(len > 20){ 
     printf("too long.\n"); 
     return 2; 
    } 
    for(num = 0; num < len; num++){ 
     printf("%dth element: ", num); 
     if(scanf("%d", &array[num]) != 1){ 
      printf("invalid input.\n"); 
      len = num; 
      break; 
     } 
    } 
    if(len > 0){ 
     ret = max_subarray(array, len); 
     printf("Maximum Subarray:\nfrom element %d to element %d with sum of %d\n", ret.start, ret.end, ret.sum); 
    } 
    return 0; 
} 

struct rettype max_subarray(int array[], int length){ 
    struct rettype ret = { .sum = array[0] }; 
    struct rettype curr = { .sum = array[0] }; 

    for(int i = 1; i < length; ++i){ 
     if(array[i] < array[i] + curr.sum){ 
      curr.sum += array[i]; 
      curr.end = i; 
     } else { 
      curr.sum = array[i]; 
      curr.start = curr.end = i; 
     } 
     if(ret.sum < curr.sum){ 
      ret = curr; 
     } 
    } 
    return ret; 
}