ポインターのポインタとメモリの割り当て

Question

私はしばらくの間、ポインタとメモリの割り当てに苦労しています。

これは、私が実装したmaxサブアレイの問題です。それは正常に動作するようです（おそらくバグがあります）。しかし、私はタプル構造体オブジェクトのメモリストレージに関する質問があります。ご覧のように、タプルはグローバルストレージに宣言されています。後でfindMaxSubArray（）関数では、Tuple構造体への3つのポインタが宣言されています。私の質問は、ポインタの逆参照（つまり、left-> sumなど）がどのように働くのかをポインター（左、右、十字）が扱っている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はあなたがそれを宣言し、ポインタだけで、ゴミ（無効Tupleオブジェクト）に乱数（以前にそれが今占有スペースにあるに起こった何でも）ので、resultポイントが含まれています。

次に、findMaxSubArrayの結果をtupleに割り当てます。 findMaxSubArrayはグローバル変数である&tuple（いずれかまたは別の方法で）を返しますので、resultはグローバル変数tupleを指します。したがって、result->sumを実行する場合は、tuple.sumと同じです。

findMaxSubArrayでは、Tuple *left, *right, *cross;は、ゴミ値を含むTupleへの3つのポインタを宣言しています。 ifの1つの支店では、それらを使用せず、グローバル変数tupleのアドレス&tupleを返すだけです。他の支店では、left、right、およびcrossをfindMaxCrossingSubArrayまたはfindMaxSubArrayのいずれかに設定します。両方とも&tupleを返します。

私はC++で本を読んで、C++を使っている間にCについて知っていることをすべて忘れてしまったことをお勧めします。彼らは同じ言語ではありません。このコードは、C++でより良い機能を提供するCトレーニング（たとえば#defineおよびtypedef struct ... Tupleなど）から学んだことで沢山です。

Answer 2

実際に割り当てられたTupleは、グローバルスコープのtupleです。 Tupleへのすべてのポインタ。 Tuple* leftは、そのグローバルストレージをポイントするだけです。だから、例えば：

left = findMaxSubArray(array, low, mid); 
right = findMaxSubArray(array, mid + 1, high); 

あなたはleftとright同じアドレスに両方のポイントとなり、値が指す同じを持っていることがわかります。

これはC言語ではなくC言語であることに注意して、Tuple*の戻り値の型をTupleの戻り値に変更し、自動（スタック）記憶域で動作させるだけです。常に&組の同じメモリ位置を指します

Tuple findMaxSubArray(int* array, int low, int high) 
{ 
    Tuple left, right, cross; 
    // blah blah 
    if (something) 
     return left; 
    else 
    return right; 
} 

Answer 3

あなたのポインタの

全て（右、左、およびクロス）：

コードは次のようになります。別のタプルが必要な場合は、mallocを使用してヒープ上に異なるタプルを作成する必要があります。