c++ - 遍历多链表？

Question

我正在为闭源程序创建一个工具。调试后，我有了要访问的结构的基地址。经过仔细检查，我发现它是一个多链表，其中前 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);

现在，我对链接结构真的很陌生，更不用说多链接结构了。

我在想的是制作一张 map 并进行暴力破解，直到我获得所有地址。 (可能无限循环)？

但是我知道这不是遍历这个链表的方法。我如何在不知道它是如何连接的情况下有效地遍历这个多链表中的所有节点(并避免我已经拥有的节点)？

---

编辑:多亏了我终于成功的答案!

这是我的代码，可能对其他人有用？

#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);
}

最棒的是，它就像一个魅力，不会滞后 :)

Answer 1

首先想到的是 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 结尾的链接数组。从您选择的任何节点开始。您基本上只需调用一个可能称为 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]
---