Pointer and memory allocation for the pointee
<p>I have been struggling with pointer and memory allocation in c for a while.</p>

<p>Here's my implementation for the max subarray problem. It seems to work fine (maybe have bugs). But I have a question about the memory storage for tuple struct object. As you can see, tuple is declared in the global storage. Later in the findMaxSubArray() function, three pointers to Tuple struct are declared. My question is we didn't declare Tuple struct object instances that the pointers (left, right, cross) are addressing how come the pointer dereferences (i.e., left->sum, etc) work. Does the GNU c compiler automatically allocate storage for them? (I don't understand x86 assembly code) Can someone please explain what's going on here? Much appreciated.</p>

<pre><code>#include &lt;iostream&gt;
using namespace std;

#define NEGINFINITY -2 &lt;&lt; 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 &gt;= low; --i) {
    sum += a[i]; 
    if (sum &gt; leftSum) {
      leftSum = sum;
      leftMax = i;
    } 
  }

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

  tuple.lowPosition = leftMax;
  tuple.highPosition = rightMax;
  tuple.sum = leftSum + rightSum;
  return &amp;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 &amp;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-&gt;sum &gt; right-&gt;sum &amp;&amp; left-&gt;sum &gt; cross-&gt;sum)
      return left;
    else if (right-&gt;sum &gt; left-&gt;sum &amp;&amp; right-&gt;sum &gt; cross-&gt;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 &lt; 8; ++i)
    cout &lt;&lt; data[i] &lt;&lt; " ";
  cout &lt;&lt; endl;
  cout &lt;&lt; "The sum of max subarray is " &lt;&lt; result-&gt;sum 
       &lt;&lt; " Starting at index " &lt;&lt; result-&gt;lowPosition 
       &lt;&lt; " ending at index " &lt;&lt; result-&gt;highPosition &lt;&lt; endl;

}
</code></pre>
