1

クローズド ソース プログラム用のツールを作成しています。デバッグ後、アクセスしたい構造のベースアドレスを取得しました。よく調べてみると、最初の 3 つの整数がポインターであり、他のすべての値がデータであるマルチリンク リストであることがわかります。

私は自分の分析からこの構造を再構築することに成功しました:

struct UnitsInfo
{
    //pointers to UnitsInfo structures, null when no structure available at that location
    DWORD * a;//0x00
    DWORD * b;//0x04
    DWORD * c;//0x08

    //data
    int unkown_1;       //0x0C
    unsigned int Type;  //0x10
    unsigned int Amount;//ox14
};
UnitsInfo * Base_Node = ((UnitsInfo*)( (*(DWORD*)( (*(DWORD*)(0x00400000+0x008E98EC)) + 0x38)) + 0x0C);

さて、私は連結構造、ましてや多重連結構造についてはまったくの初心者です。

私が考えていたのは、マップを作成して、すべてのアドレスを取得するまでブルートフォースを行うことです。(無限ループ可能)?

しかし、これがこのリンクされたリストをトラバースする方法ではないことはわかっています。どのように接続されているかを知らずに、この複数のリンクされたリスト内のすべてのノードを効率的にトラバースするにはどうすればよいでしょうか (そして、既に持っていたノードを回避します)。

編集：答えのおかげで、私はついにそれを作りました!

これが私のコードです。他の人にとっては便利かもしれません。

#define MAX_PLAYERS (6)
#define POINTER(type,addr) (*(type*)(addr))

struct UnitsInfo
{
    //pointers to UnitsInfo structures, null when no structure available at that location
    DWORD * nodes[3];//0x00

    //data
    int unkown_1;       //0x0C
    unsigned int Type;  //0x10
    unsigned int Amount;//ox14
};

struct pinfo
{
    bool            in;
    enum Controller {Ctrl_UNKNOWN,  Ctrl_HUMAN, Ctrl_AI             };
    enum Nation     {N_UNKNOWN,     N_ALLIES,   N_SOVIET,   N_JAPAN };
    std::string     Name;
    Nation          Side;
    short           Team;
    Controller      Who;
    int             *Money;
    int             *Power;
    int             *Usage;
    unsigned int    *Color;

    bool            GotUnits;
    DWORD           *unit_start_node;
};

std::map<DWORD*,UnitsInfo*> UnitList[MAX_PLAYERS];
void GenerateUnitList(unsigned short slot)
{
    std::set<DWORD*> todo;
    unsigned int inserted = 1;
    while(inserted)
    {
        inserted = 0;
        for(auto it = UnitList[slot].begin(); it != UnitList[slot].end(); ++it)
        {
            for(short i = 0; i < 3; ++i)
            {
                if(it->second->nodes[i] != NULL)
                {
                    if(UnitList[slot].find(it->second->nodes[i]) == UnitList[slot].end())
                    {
                        todo.insert(it->second->nodes[i]);
                        ++inserted;
                    }
                }
            }
        }
        while(!todo.empty())
        {
            UnitList[slot][*todo.begin()] = &POINTER(UnitsInfo,*todo.begin());
            todo.erase(todo.begin());
        }
    }
}

pinfo Player[MAX_PLAYERS];

//adding the first node
unsigned int CurrentSlot = (0xD8+(0x4*slot));
if(POINTER(DWORD,POINTER(DWORD,0x00400000+0x008E98EC)+CurrentSlot) != NULL)
{
    Player[slot].unit_start_node = &POINTER(DWORD,POINTER(DWORD,POINTER(DWORD,POINTER(DWORD,0x00400000+0x008E98EC)+CurrentSlot) + 0x38) + 0x0C);
}

//adding first unit if available, if yes continue generating list
if(!Player[i].GotUnits)
{
    if(POINTER(DWORD,*Player[i].unit_start_node+0x10) != NULL)
    {
        Player[i].GotUnits = true;
        UnitList[i][(Player[i].unit_start_node)] = &POINTER(UnitsInfo,*Player[i].unit_start_node);
    }
}
else
{
    GenerateUnitList(i);
}

そして何よりも、それは魅力のように機能し、遅れることはありません:)

4

2 に答える 2

2

BFS と DFS が最初に頭に浮かぶものです。

どちらも一般的にグラフをトラバースするために使用されます。リンク構造のループは両方のケースで検出されるため、正しく実装されていれば無限ループのリスクはありません。

基本的に言えば、どちらの方法も (少なくとも概念レベルでは) 検査済みのノードをマークし、これまでに確認されていないノードをある種のリストに保持することによって機能します。

幅優先トラバーサルはノードをキューに保持し、ある種の FIFO 方式でノードを処理しますが、深さ優先トラバーサルは新しいノードをスタックにプッシュし、新しく発見されたノードを最初に訪問します。

深さ優先トラバーサルを実装する最も簡単な方法の 1 つは、スタックを実装しなくても機能します。スタックを再帰的に呼び出すことで、プログラムのコール スタックを (ミス) 使用してまだ訪問する場所を追跡するだけだからです。

例

トラバースするグラフのノードが次のような構造を持っているとします。

struct Node {
  int visited;
  struct Node **edges;

  void *some_data;
}

エッジは、別のノードにつながるリンクの NULL 終端配列です。選択した任意のノードから開始します。基本的に、visit と呼ばれる単一の関数を呼び出すだけで完了です。

void visit (struct Node *node) {
  struct Node *n;

  node->visited = 1;    

  for (n=node->edges; *n!=NULL; ++n)
    if (!(*n)->visited)
      visit (*n, depth+1);
}

もちろん、訪問した各ノードで何か役立つことを行う必要があります。しかし、円を描くことなく開始ノードから到達可能なすべてのノードにアクセスするには、これですべての作業が完了します。

完全な例

ここでは、完全に機能する例を提供しようとしています。いくつかの努力を試みた後、選択されたさまざまなパスを示す比較的優れたグラフを思いついたと思います。

以下のコメント行にそれを書き留めようとしました：

#include <stdio.h>

struct Node {
  int visited;
  int id;
  struct Node **edges;
};

/* recursively visit this node and all unvisited nodes
   reachable from here */

void visit (struct Node *node, int depth) {
  struct Node **n;
  node->visited = 1;

  /* show the node id surrounded with '[' ']' characters
     to indicate this node has been visited in the output */

  printf ("[%d]\n", node->id);

  for (n=node->edges; *n!=NULL; ++n) {

    /* indent this line according the depth that has
       been reached in recursion and show the id
       of the reachable node currently inspected */
    printf ("%*s %d ", 5*depth, "", (*n)->id);
    if (!(*n)->visited) {
      /* indicate the search goes down one recursion level
         by drawing a '=>' next to the node id */
      printf ("=>");
      visit (*n, depth+1);
    }
    else
      printf ("\n");
  }
}
int main (int argc, char *argv[]) {

  /*  This is the graph that will be modeled and traversed

             +----+
            v      \
       + -- 0 -+    \
      /    ^    \    |
      |   /      v  /
      v  /       2 - 
       1-        ^ \
       \       /    v
        +---> 3     4
   */


  struct Node v[5]; /* These will form the vertices of the graph */

  / * These will be the edges */
  struct Node *e[][5] = {
    {v+1, v+2, NULL},
    {v+0, v+3, NULL},
    {v+0, v+4, NULL},
    {v+2, NULL},
    { NULL}
  };

  /* initialize graph */
  int i;
  for (i=0; i<5; ++i) {
    v[i].id = i;
    v[i].visited = 0;
    v[i].edges=e[i];
  }


  /* starting with each vertex in turn traverse the graph */
  int j;
  for (j=0; j<5; ++j) {
    visit (v+j, 0);
    printf ("---\n");

    /* reset the visited flags before the 
       next round starts */ 
    for (i=0; i<5; ++i)
      v[i].visited = 0;
  }

  return 0;
}

出力は、多かれ少なかれ不可解な方法で、再帰中にアルゴリズムが前後にジャンプすることを示します。

出力

開始ノードに応じて、異なる結果が得られます。たとえば、ノードから開始する4と、そこから続くパスがないため、他のノードは見つかりません。

ここでは、開始ノードが から までの出力0です4。[ ]訪問されたノードは、すでに検査されているために訪問されていない文字で囲まれ、代わりに境界線なしで描画されます。

この例が、アルゴリズムがどのように、そしてなぜ機能するかを理解するのに役立つことを願っています。

[0]
 1 =>[1]
      0 
      3 =>[3]
           2 =>[2]
                0 
                4 =>[4]
 2 
---
[1]
 0 =>[0]
      1 
      2 =>[2]
           0 
           4 =>[4]
 3 =>[3]
      2 
---
[2]
 0 =>[0]
      1 =>[1]
           0 
           3 =>[3]
                2 
      2 
 4 =>[4]
---
[3]
 2 =>[2]
      0 =>[0]
           1 =>[1]
                0 
                3 
           2 
      4 =>[4]
---
[4]
---
于 2013-03-29T13:19:43.097 に答える
1

私が考えていたのは、マップを作成して、すべてのアドレスを取得するまでブルートフォースを行うことです。(無限ループ可能)?

全体として、これは実行可能だと思います。必要なのは、処理済みの住所のセットと、処理する住所のセットだけです。どちらのセットにもないアドレスに遭遇したときはいつでも、それを「todo」セットに追加します。前者が空になるまで、「todo」セットのアドレスを処理し続けます (そして、それらを「done」セットに移動します)。

于 2013-03-29T13:19:09.477 に答える