C - 具有静态结构返回类型的最大子数组

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 %dn", 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

最大子数组问题
卡达内算法

#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 %dn", 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;
}