我正在寻找特定的搜索算法

Question

目前我正在尝试用 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，这也应该是可能的。出于各种原因，我需要一种搜索算法来遍历房间以找到特定的房间。我不知道如何实现这样的东西。有什么想法吗？

Answer 1

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

数组

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

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

但是，我们必须在结构 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
}

Answer 2

我认为您可以使用深度优先搜索技术来找到所需的 value.As 可能会找到四个边，因此此算法将帮助您找到。

学习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/

Answer 3

使用递归算法会很容易，将您的四元组列表视为 graph，其中包含 left、right、top 和 bottom connection.Following 是您搜索算法的伪代码：-

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

}

我正在寻找特定的搜索算法

I'm looking for a specific search algorithm

c

text-based