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 是首先想到的：

  • 深度优先搜索（参见：http ://en.wikipedia.org/wiki/Depth-first_search ）

  • 广度优先搜索（参见：http ://en.wikipedia.org/wiki/Breadth-first_search ）

它们都常用于遍历图。在大多数情况下都会检测到链接结构中的循环，因此如果实施得当，就不会有无限循环的风险。

基本上来说，这两种方法的工作原理是（至少在概念层面上）标记任何已检查的节点，同时将迄今为止看到的任何未访问的节点保留在某种列表中。

虽然广度优先遍历将使节点保持在队列中以某种 FIFO 方式处理节点，但深度优先遍历会将新节点推送到堆栈上，从而首先访问新发现的节点。

实现深度优先遍历的最简单方法之一即使不必实现堆栈，也可以通过递归调用自身，它只是（未命中）使用程序的调用堆栈来跟踪仍要访问的地方。

例子

假设您要遍历的图形的节点具有类似于以下结构的内容：

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

  void *some_data;
}

边是指向另一个节点的以 NULL 结尾的链接数组。从您选择的任何节点开始。您基本上只需调用一个可能称为访问的函数即可完成：

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

我在想的是制作地图并进行暴力破解，直到我拥有所有地址。（可能无限循环）？

总的来说，我认为这是可行的。您所需要的只是一组您已经处理过的地址，以及一组要处理的地址。每当您遇到不在这两个集合中的地址时，将其添加到“待办事项”集合中。您继续处理“待办事项”集中的地址（并将它们移动到“完成”集中），直到前者变为空。

于 2013-03-29T13:19:09.477 回答