c - 从 C 中的函数返回元组

Question

我需要一些提示来在 C 中实现这个算法。这是一个最大子数组问题。我已经制作了多项式时间程序和线性时间程序。我是 C 的新手，所以我不知道如何从一个函数返回多个值，因为这个算法需要它。例如算法中的这一行 (left-low,left-high,left-sum)=FIND-MAXIMUM-SUBARRAY(A,low,mid) 其中 FIND-MAX-SUBARRAY( A,low,mid) 是递归函数调用。

这是coremen的算法:

下面我设置了全局变量 cross-low,cross-high,cross-sum 。我怎样才能对 left-low,left-high,left-sum 和 right-low,right-high,right-sum 做同样的事情？

#include "max_subarray_common.h"
#define SENTINAL -3000

int left_low,left_high,left_sum;
int right_low,right_high,right_sum;
int cross_low,cross_high,cross_sum;


void max_crossing_subarray(int low,int mid,int high)
{
    int left_sum=SENTINAL;
    int sum=0;
    int max_left=low,max_right=high;
    for(int i=mid;i>=low;i--)
    {
        sum=sum+change[i];
        if(sum>left_sum)
        {
            left_sum=sum;
            max_left=i;
        }
    }
    int right_sum=0;
    sum=0;
    for(int j=mid+1;j<=high;j++)
    {
        sum=sum+change[j];
        if(sum>right_sum)
        {
            right_sum=sum;
            max_right=j;
        }
    }
    cross_low=max_left;
    cross_high=max_right;
    cross_sum=left_sum+right_sum;
}

这是我的头文件:

#ifndef max_subarray_h
#define max_subarray_h

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

extern int price[];
extern int n;
extern int change[];
extern int from;
extern int to;
extern int max;


void init_change();
void max_subarray_poly();
void max_subarray_crossing();
void max_subarray_rec();
void max_crossing_subarray();

#endif

change[] 是要为其找到子数组的数组。我的输出也应该是这样的:

from=8
to=11
maximum profit=43

Answer 1

您可以通过使用关键字“struct”定义一个结构来实现该目标，该结构将包含您打算返回的三个变量。为此，请在您的 c 程序的 header 部分添加结构定义。

typedef struct left {  
  int left_low;  
  int left_high;
  int left_sum;
}LEFT;

在你的 main 中定义一个 LEFT 类型的变量(或者你想使用它的地方) 笔记。您的 FIND-MAXIMUM-SUBARRAY 的返回类型将为 LEFT。您还需要将变量“STLeft”传递给 FIND-MAXIMUM-SUBARRAY 函数。

LEFT stleft;

分配内存给STLeft

stleft = malloc(sizeof(LEFT));

将要返回的值分配给变量“STLeft”

stleft.left_low = max_left;
stleft.left_high = max_left;
stleft.left_sum = left_sum + right_sum;

返回你的变量

return stleft;

在 STLeft 中访问 left_low

int newvar1;
newvar1 = stleft.left_low;

有关查找 C 结构的更多帮助