-1

目前我正在尝试在 C 中创建一个基于文本的小地牢爬虫，其中应该随机生成地图。我尝试通过使用四链表来实现这一点，其中每个节点（房间）最多可以有四个连接到下一个房间。

typedef struct Room {
    int x; //each room got its own number to be identified.
    struct Room *north;
    struct Room *east;
    struct Room *south;
    struct Room *west; } room;

一些房间也应该有可能只有一个或两个或三个连接，而未使用的指向下一个节点的指针保持为 NULL。由于各种原因，我需要一种搜索​​算法来遍历房间以找到特定的房间。我不知道如何实现这样的东西。有任何想法吗？

4

3 回答 3

2

我认为您可以使用深度优先搜索技术来找到所需的值。因为可能有四个方面可以找到，所以这个算法将帮助您找到。

学习 DFS（深度优先搜索）你可以阅读这些 :)

http://en.wikipedia.org/wiki/Depth-first_search

http://www.ics.uci.edu/~eppstein/161/960215.html

http://www.geeksforgeeks.org/applications-of-depth-first-search/

于 2015-02-25T20:33:33.313 回答
1

一个简单的解决方案是创建一个数组Room，或者一个数组Room *

然后，您可以在数组中循环搜索，直到找到搜索值为 的房间x，或者到达数组的末尾。

如果您从初始房间开始，您可以尝试链表的递归搜索。

但是，我们必须在 struct Room 中添加一个 bool 以避免无限搜索，因为您的房间可能会像这样相互循环：

 O--O
 |  |
 O--O
  O : room, - and | : link between rooms

该checked值应false在开始搜索之前初始化，并且该参数true在房间被检查一次时获取。

原则 ：

Room* search_room (int x_search, Room* current_room)
{
//if current_room is NULL, return NULL
//if checked is true, return NULL
//checked becomes true
//if current_room->x equals x_search, return current_room

//store the result of search_room(x_search, current_room->north) somewhere
//if it's not null, return what it has returned
//if not, then proceed to the store and check of the 3 others calls :
//search_room(x_search, current_room->east)
//search_room(x_search, current_room->south)
//search_room(x_search, current_room->west)

//if all the 4 calls returned NULL, return NULL
}
于 2015-02-25T20:21:53.747 回答
1

使用递归算法将很容易，将您的四边形列表视为具有 、 和graph连接left。right以下是您的搜索算法的伪代码：-topbottom

typedef enum{
    VISITED,
    NOT_VISITED
}status;
typedef struct vertex{
    int x;
    struct vertex* up;
    struct vertex* down;
    struct vertex* left;
    struct vertex* right;
    status node_status;
}node;
typedef struct{
    node* g_nodes;
    int capacity, length, width,curr_filled;
    int row_index, col_index;
}graph;
g_node* search_graph (graph* gph, int key)
{
    static g_node = get_first_node ( gph ); //you can get any node.
    if ( g_node->x == key){
        return g_node;
    }
    if ( g_node->node_status == VISITED){
        return NULL;
    } 
    g_node->node_status = VISITED;
    if (g_node->left != NULL){
        return search_graph (gph, g_node->left);
    }
    if (g_node->right != NULL){
        return print_graph (gph, g_node->right);
    }
    if (g_node->up != NULL){
        return print_graph (gph, g_node->up);
    }
    if (g_node->down != NULL){
        return print_graph (gph, g_node->down);
    }

}  
于 2015-02-25T21:13:24.957 回答