5

C++ でツリー構造を書こうとしています。どの木にも枝と葉があるように。枝には、葉だけでなく他の枝も含めることができます。現在、私の実装では、各ブランチとリーフに異なる機能を持たせる必要があります。たとえば。ツリー構造を取る

                                          Root                                             
                                |                          |                             
                             Branch1                     Branch2                     Branch3
      |                |                |
    Leaf1            Leaf2           Branch4

各リーフとブランチには実行する関数が異なるため、Leaf1 には leaf1_func という関数があり、Leaf2 には leaf2_func があり、Branch4 には Branch4_func があります。

私は当初、複合設計パターンを実装しようとしていました。しかし、それはリーフと同じ数のクラスを持つことを意味します。しかし、葉や枝がたくさんあるので、避けたいのは、より多くのクラスを作成することです。これは異常な状況だと認識していますが、誰かがこの点で私を助けてくれることを望んでいました. あまりにも多くのクラスを作成せずにこのツリーを実装する最良の方法は何でしょうか.

私はマップ STL コンテナーを使用してデータを保存しています。このツリー実装を使用して、TSP 問題でこれを解決したいと考えています。

#include <cstdlib>
#include <iostream>
#include <map>

using namespace std;

int n=4;
int min=1, max=10;




struct graph
{
int nodes;//total no. of nodes or vertices namely cities
std::map<std::pair<int,int>, int> graphMap;//an object that links a pair of vertices   
};


void directed_Graph(graph);

void directed_Graph(graph G)
{
//int n = G->nodes; //city count
int i, j;
for(i = 0; i <= n-1; i++)
{
    for(j = 0; j <= n-1; j++)
    {
        if(i!=j)
        {
            G.graphMap[std::make_pair(i,j)] = (rand()%10)+1;
            //cout<<G.graphMap[std::make_pair(i,j)]<<"\n";
        }

        else
        {
            G.graphMap[std::make_pair(i,j)] = 0;
        }

    }
}
}


int main(int argc, char** argv) 
{
graph g;
g.nodes = 4;

directed_Graph(g);

return 0;
}
4

3 に答える 3

1

同じシグネチャを持つさまざまな関数は、同じ型を持ちます。関数が完全に無関係であっても、void *(型消去) を使用してランダム データを格納するツリーを作成し、リーフ ノードに到達した後に既知の実際の型に型キャストすることができます。

struct node {
    void (*fptr)(); // pointer to any function taking no args, no return
    void *data; // pointer to anything, need to cast before using
};

void f() { std::cout << "hello"; }
void g() { std::cout << "world"; }

node a = { f, f };
node b = { g, g };

a.fptr();
static_cast< void (*)() >( b.data )();

継承を伴う仮想メソッドを使用して、基本クラスの型へのポインターをツリーに格納することもできます。ノードが実際に何であるかによって異なります。

これはどれも、グラフに入るという事実とは実際には関係ありません。

于 2012-05-20T11:30:57.400 に答える
0

ダイアグラムの外観から、ノードが 3 つ以上の子を持つことができるツリーが必要なようです。その場合、STL コンテナーは機能しません。それらは自己均衡二分木です。

二分木に問題がない場合は、これを行う方法がいくつかあります。1 つ目は、関数を記述してから、関数ポインターまたはファンクターをツリーに格納することです。

#include <set>

int foo( ) {
  return 5;
}

std::set< int (*)( ) > my_set;
my_set.insert( &foo );

このアプローチの問題点は、すべての関数が同じ型でなければならないことです。つまり、同じ引数を取り、同じ戻り値の型を持つ必要があります。さらに、さまざまな動作を定義できますが、状態を保持することはできません。つまり、関数ポインターにデータを格納することはできません。

2 番目のオプションは、おっしゃったように、クラスを作成することです。ノードの動作を変更する必要がある場合、最適な方法はインターフェイスを定義してポリモーフィズムを使用することです。

#include <set>
#include <iostream>

struct base {
  virtual void print( ) const = 0;
};

struct derived1 : public base {
  void print( ) const { std::cout << "derived1" << std::endl; }
};

struct derived2 : public base {
  void print( ) const { std::cout << "derived2" << std::endl; }
};

std::set< base* > my_set;

my_set.insert( new derived1( ));
my_set.insert( new derived2( ));

特定の動作を強制的にリーフにし、他の動作を内部ノードにする必要があるかどうか、またはノードを特定の方法で順序付けする必要があるかどうかについては言及しませんでしたが、そうする場合は、カスタムを作成することでこれを達成できる可能性がありますより小さい関数:

bool operator < ( base const * const b1, base const * const b2 ) {
  // Figure out which is less here.
}

繰り返しますが、二分木ではないものが必要な場合は、運が悪いです。これをどのようにスライスしても、関数であれクラスであれ、各ノードに格納されている動作を実装するコードを記述する必要があります。

于 2012-05-20T11:15:19.680 に答える