2

私はコンピュータサイエンスの大学生です。昨日、C++を使用した二分探索木についてのクラスがあります。私たちはそのクラスのラボアシスタントによって教えられています。

ツリー内のノードを次のような構造体として定義します。

struct Data{
    char name[15];
    int age;
    Data *left,*right;
};

そして、次のようにBST内を検索するためのコードを提供します。

// temp is current node, name is the value of the node to be searched for.
Data* search(Data *temp,char name[]) {
    if(strcmp(temp->name,name)>0)
        search(temp->left,name);
    else if(strcmp(temp->name,name)<0)
        search(temp->right,name);
    else
        return temp;
}

コードが間違っていることに気づきました。関数が最初または2番目のifブロックに入ると、returnステートメントは実行されません。

ただし、ラボアシスタントがコードを実行すると、正常に機能します。

多分この振る舞いはコンパイラ特有だと思いました。しかし、gccでそのコードを試したところ、関数も正常に機能します。（私たちの大学はMicrosoft Visual C ++コンパイラを使用しています）

誰かが何が起こっているのか説明できますか？このコードが機能しているのはなぜですか？

PS：ノードが空の場合、値が見つからない場合など、他のエラーは無視してください。

4

2 に答える 2

8

これは未定義の動作です。

戻り値を保持するレジスタが1つあるため、機能しているように見えます。再帰ツリーの最も深いパスでは、tempはそのレジスタに移動され、後でクリアまたは変更されることはありません。そのため、最初の呼び出しが戻るまで、レジスタには正しいノードが含まれます。

最初の呼び出しが戻ると、呼び出しコンテキストはそのレジスタの戻り値をチェックしますが、これはたまたま正しいものです。しかし、これに頼るべきではありません。それが常に機能すると仮定するのは安全ではありません。

于 2012-05-11T09:29:55.440 に答える
1

通常、関数から値を返すために使用されるハードウェアレジスタが1つあります（たとえば、i686では％EAXになります）。関数で最後に行ったことが別の関数の呼び出しであり、意図した戻り値がその関数の結果である場合、％EAX値が破棄されておらず、呼び出し元によって適切に取得されている可能性があります。

ただし、これには多くの仮説がありますが、信頼性があると期待するべきではありません。まず、コンパイラは、の戻り値を使用していないことを検出できるため、副作用がないsearch()ことについてのヒントがある場合は、その呼び出しを最適化することを決定する場合があります。search()検索呼び出しをインライン化できる場合は、部分的に最適化することができます。

他のアーキテクチャ（iirc、IA64の場合）があり、呼び出し規約がより微妙で、1つの関数で値を返すために使用されるレジスタが呼び出し元の関数と同じではない場合があります。したがって、コードは、プラットフォームに依存する詳細に依存して機能しますが、高レベルの（そして移植可能な）言語であると想定されています。

于 2012-05-11T09:32:01.617 に答える