我正在创建一个闭源程序的工具。调试后，我有了我想要访问的结构的基址。仔细检查后，我发现它是一个多链表，其中前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);
}
最好的是，它像一个魅力，不延迟:)
我首先想到的是BFS和DFS:
-
深度优先搜索(参见:http://en.wikipedia.org/wiki/Depth-firstrongearch)
-
广度优先搜索(参见:http://en.wikipedia.org/wiki/Breadth-firstrongearch)
它们通常用于遍历图。在宿主情况下，链接结构中的循环将被检测到，所以如果正确实现，就不会有无限循环的风险。
基本上，这两种方法的工作原理是(至少在概念层面上)标记任何已检查的节点，同时将迄今为止看到的任何未访问的节点保留在某种列表中。
宽度优先遍历将节点保持在队列中，以某种先进先出的方式处理节点，深度优先遍历将把新节点推到堆栈中，从而首先访问新发现的节点。
实现深度优先遍历的最简单的方法之一甚至不需要实现堆栈，因为通过递归调用自身，它只是(错过)使用程序的调用堆栈来跟踪仍然要访问的位置。
假设您要遍历的图的节点具有如下结构:
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]
---
总的来说，我认为这是可行的。您所需要的只是一组已经处理过的地址和一组要处理的地址。当您遇到一个不在这两个集合中的地址时，您将其添加到"todo"集合中。继续处理"todo"集中的地址(并将它们移动到"done"集中)，直到前者变为空。我想的是做一个地图和暴力，直到我有所有的地址。(可能无限循环)?