c++ - 指针对象的指针和内存分配

Question

一段时间以来，我一直在努力解决 c 中的指针和内存分配问题。

这是我对最大子数组问题的实现。它似乎工作正常(可能有错误)。但是我对元组结构对象的内存存储有疑问。如您所见，元组是在全局存储中声明的。随后在 findMaxSubArray() 函数中，声明了三个指向 Tuple 结构的指针。我的问题是我们没有声明指针(左、右、交叉)正在解决指针解引用(即左->和等)如何工作的 Tuple 结构对象实例。 GNU c 编译器会自动为它们分配存储空间吗？ (我不明白 x86 汇编代码)有人可以解释一下这里发生了什么吗？非常感谢。

#include <iostream>
using namespace std;

#define NEGINFINITY -2 << 31

typedef struct {
  int lowPosition;
  int highPosition;
  int sum;
} Tuple;

Tuple tuple;

Tuple* findMaxCrossingSubArray(int a[], int low, int mid, int high) {
  int leftSum, rightSum;
  int leftMax, rightMax;
  int sum;

  leftSum = rightSum = NEGINFINITY; 
  sum = 0; 
  for (int i = mid; i >= low; --i) {
    sum += a[i]; 
    if (sum > leftSum) {
      leftSum = sum;
      leftMax = i;
    } 
  }

  sum = 0;
  for (int j = mid + 1; j <= high; ++j) {
    sum += a[j];
    if (sum > rightSum) {
      rightSum = sum;
      rightMax = j;
    }
  }

  tuple.lowPosition = leftMax;
  tuple.highPosition = rightMax;
  tuple.sum = leftSum + rightSum;
  return &tuple;
}

Tuple* findMaxSubArray(int* array, int low, int high) {
  Tuple *left, *right, *cross;
  if (high == low) {
    // base case
    tuple.lowPosition = low;
    tuple.highPosition = high;
    tuple.sum = array[low];
    return &tuple;
  } 
  else {
    int mid = (low + high) / 2; 
    left = findMaxSubArray(array, low, mid);
    right = findMaxSubArray(array, mid + 1, high);
    cross = findMaxCrossingSubArray(array, low, mid, high);

    if (left->sum > right->sum && left->sum > cross->sum)
      return left;
    else if (right->sum > left->sum && right->sum > cross->sum)
      return right;
    else
      return cross;
  }
}

int main() {
  Tuple *result;
  int data[] = {1, -2, 3, 10, -4, 7, 2, -5};
  result = findMaxSubArray(data, 0, 7);
  for (int i = 0; i < 8; ++i)
    cout << data[i] << " ";
  cout << endl;
  cout << "The sum of max subarray is " << result->sum 
       << " Starting at index " << result->lowPosition 
       << " ending at index " << result->highPosition << endl;

}

Answer 1

全局变量 tuple 是这个程序中唯一实际的 Tuple。全局变量的内存由编译器管理。

在 main 中，Tuple *result 只是一个指针，当您声明它时，它包含一个随机数(无论以前发生在它现在占据的空间中是什么) )，因此 result 指向垃圾(不是有效的 Tuple 对象)。

然后将 findMaxSubArray 的结果分配给 tuple。由于 findMaxSubArray 返回作为全局变量的 &tuple(以某种方式)，result 指向全局变量 tuple。因此，当您执行 result->sum 时，它与执行 tuple.sum 相同。

在 findMaxSubArray 中，行 Tuple *left, *right, *cross; 声明了三个指向包含垃圾值的 Tuple 的指针.在 if 的一个分支中，您不使用它们，只是返回 &tuple，即全局变量 tuple 的地址。在另一个分支中，将 left、right 和 cross 设置为 findMaxCrossingSubArray 或 findMaxSubArray，它们都以一种或另一种方式返回 &tuple。

我确实建议阅读一本关于 C++ 的书，并在使用 C++ 时忘记所有关于 C 的知识(但是当你再次编写 C 时再次记住它)。他们不是同一种语言。此代码充满了您从 C 培训中学到的东西(例如 #define 和 typedef struct ... Tuple)，C++ 对此提供了更好的工具。