0

私はこの質問をデバッグしようとしました：バイナリ検索ツリーを各レベルのすべてのノードのリンクリストに変換します。しかし、実行時エラーが発生しました。コードでは、基本的にバイナリ検索ツリーのBFSを実行し、各レベルを追跡します。新しいレベルがヒットした場合は、新しいリンクリストを作成して新しいレベルのノードを格納します。STLのリンクリストを使用してノードを保存しました。その前に、関数min_heightを使用してバイナリ検索ツリーを作成します。これらのメソッドをinputvector= {1、2、3、4、5、6}でテストします。ツリーは次の図のようになります。一部のノードでは正常に動作しますが、ノード2で停止します。理由がわかりません。誰かが助けてくれますか？ありがとうございました ！ここに画像の説明を入力してください

#include <iostream>
#include<string>
#include<vector>
#include<queue>
#include<list>
using namespace std;

template<typename Key, typename Value>
struct BSTNode{
 Key key;
 Value value;
 BSTNode * left;
 BSTNode * right;
 BSTNode(Key k, Value v, BSTNode *l=NULL, BSTNode *r=NULL): key(k), value(v), left(l), right(r) {}
 };


template<typename Key, typename Value>
vector< list<BSTNode<Key, Value>*> > creat_lists(BSTNode<Key, Value>* root){
 vector< list<BSTNode<Key, Value>*> > v;
 if(root==NULL) return v; 
 queue<BSTNode<Key, Value>*> q;   queue<int> level;  int prev;
 q.push(root);   level.push(0);   prev=-1;
 while(!q.empty()){
  BSTNode<Key, Value>* cur=q.front();    int cur_level=level.front();
  cout<<"cur->key: "<<cur->key<<" cur_level: "<<cur_level<<endl;

  if(prev!=cur_level){
    list<BSTNode<Key, Value>*> l;
    l.push_back(cur);
    v.push_back(l);
  }
  else  {cout<<"got in"<<endl;  v.back().push_back(cur);}

  if(cur->left )cout<<"cur->left: "<<cur->left->key<<endl;
  if(cur->right )cout<<"cur->right: "<<cur->right->key<<endl;

  prev=cur_level;
  if(cur->left) {q.push(cur->left);  level.push(cur_level+1); }
  if(cur->right) {q.push(cur->right);  level.push(cur_level+1);}



  q.pop();    level.pop();


 }
return v;
}


template<typename Key, typename Value>
BSTNode<Key, Value>* min_height(vector<int> &v, int left, int right ){// here is different from my paper code
  if(left<=right){
    int mid=left+ (right-left)/2;
    BSTNode<Key, Value>* node=new BSTNode<Key, Value>(v[mid], v[mid]);
    node->left=min_height<Key, Value>(v, left, mid-1 );
    node->right=min_height<Key, Value>(v, mid+1, right );
    return node;
    }
}


int main(){
  vector<int> v;
  v.push_back(1);
  v.push_back(2);
  v.push_back(3);
  v.push_back(4);
  v.push_back(5);
  v.push_back(6);  
  BSTNode<int, int>* root=min_height<int, int>(v, 0, 5);
 vector<list<BSTNode<int, int>*> > newv=creat_lists(root);
 //for(int i=0; i<newv.size(); i++)  cout<<(v[i].front())->key<<endl;
}



complier result:
Run Status: Runtime Error

cur->key: 3 cur_level: 0
cur->left: 1
cur->right: 5
cur->key: 1 cur_level: 1
cur->right: 2
cur->key: 5 cur_level: 1
got in
cur->left: 4
cur->right: 6
cur->key: 2 cur_level: 2
4

1 に答える 1

0

これは暗闇の中での刺し傷です。

ダングリングポインタは、期待されるタイプの正当なオブジェクトのアドレスではないメモリ内の場所を指すポインタです。これは、メモリマネージャの保護下にない、機能しなくなったオブジェクトのアドレス、無関係なオブジェクトの中央にある場所、割り当てられていないメモリ内の場所、または実際のメモリの境界外にある可能性があります。実際には、古いランダムジャンクを含めることができ、それを逆参照しようとすると（つまり、正当なオブジェクトであるかのように使用すると）、未定義の動作が発生します（つまり、何かが発生する可能性があり、特殊な方法で失敗する可能性があります）。

関数は、そのシグネチャによって示されるタイプの値を返す必要があります。関数BSTNode<Key, Value>* min_height(...)はへのポインタを返す必要がありますBSTNode。しかし、書かれているように、それはそうするだけif(left<=right)です、さもなければ、それは単に終了します。この場合に何が起こるかは正確にはわかりませんが、少なくとも一部のコンパイラでは、未定義のポインタがランダムに返され、適切な方法ではない可能性があると思います。優れたコンパイラはこれについて警告します。（私の意見では、良いポインターはそれをコンパイルすることを拒否するべきですが、それは別の暴言です。）

したがって、関数を修正します。min_height(...)条件が満たされない場合は、正しい特定の値を返します。それでもバグが修正されない場合は、お知らせください。別の方法を試します。（ネタバレ： ןןnusıǝnןɐʌɔıɟıɔǝdsʇɔǝɹɹoɔǝɥʇ。）

于 2013-03-13T13:59:32.060 に答える