C中的A*实现，分段错误

Question

对于C语言的学校项目，我想创建一个路径查找算法，我决定使用A*。 经过长时间的反思和重写，我找不到问题所在。这一定是因为内存管理，但我无法弄清楚哪里出了问题。即使在论坛上查找了几个小时后，我也没有发现任何有趣的东西。

当 gdb 向我展示段错误发生在哪个函数中时，他会帮助我更多。

(gdb) bt
#0  0x0000000008000917 in list_prepend ()
#1  0x0000000008000b38 in findPath ()
#2  0x0000000008001473 in main ()

我使用结构来表示我的节点和指向节点的指针列表。

typedef struct Coord Coord;
struct Coord{
  int x;
  int y;
};
typedef struct Node{
    bool walkable;
    bool wayToGo;
    Coord pos;
    int gCost;
    int hCost;
    int fCost; // fCost = gCost + hCost
    struct Node *parent;
} Node;
typedef struct NodeList{
    Node * pNode;
    struct NodeList * next;
    struct NodeList * previous;
} NodeList;

以及提高SIGSEGV的功能：

NodeList * list_prepend(NodeList *old, Node *pNode)
{
    NodeList *list = list_create(pNode); 
    if (list){                     
       list->next = old;             
       old->previous = list;
    }
    return list;                    
}

哪里：

NodeList * list_create (Node *pNode)
{
    NodeList *list = malloc(sizeof(NodeList));
    if (list)
    {
        list->pNode = pNode;
        list->next = NULL;
        list->previous = NULL;
    }
    return list;
}

我认为问题来自old->previous = list，因为它看起来old->previous给出了 NULL，我试图将某些内容影响为 NULL。我不知道，这就是我问的原因。

如果您有任何想法，或者可以分享一个好的调试技术，那就太好了。

如果需要，这里是我为测试路径查找器而编写的完整代码： pathFinding.c

Answer 1

NodeList * list_prepend(NodeList *old, Node *pNode)
{
    NodeList *list = list_create(pNode);
    if (list){
       list->next = old;
       (*old).previous = list; // Since this accesses *old, old cannot be NULL
    }
    return list;
}

请参阅上面的评论。打电话给list_prepend的先决条件是old不NULL。

NodeList * getNeighbours(Node grid[row][column], Node * pNode)
{
        int x, y;
        NodeList * list = NULL;
        for(x = -1; x <= 1; x++){
                for(y = -1; y <= 1; y++){
                        if(x == y || x == -y)
                                continue;
                        int checkX = pNode->pos.x + x;
                        int checkY = pNode->pos.y + y;
                        if (checkX >= 0 && checkX < column && checkY >= 0 && checkY < row){
                                list = list_prepend(list, &(grid[checkY][checkX])); // Uh oh, list is NULL on first invocation
                        }
                }           
        }
        return list;
}

请参阅评论。第一次调用list_prepend违反了前提条件。清楚地记录(在注释中(函数的先决条件非常重要。测试所有前提条件是否为真并报告任何不符合条件的条件也非常有帮助。它使调试变得更加容易。

我也对你在几个地方的想法感到困惑。例如：

NodeList * list_append(NodeList *list, Node *pNode)
{/*Rajouter le previous*/
    NodeList **plist = &list;
    while (*plist)
       plist = &(*plist)->next;
    *plist = list_create(pNode);
    if (*plist)
       return list;
    else
       return NULL;
}

为什么在plist中出现双重间接的混乱？为什么不设置新创建的节点prev？为什么不只是：

NodeList * list_append(NodeList *list, Node *pNode)
{
    if (list == NULL)
        return list_create(pNode);
    NodeList *plist = list;
    while (plist->next != NULL)
       plist = plist->next;
    plist->next = list_create(pNode);
    if (plist->next == NULL)
        return NULL;
    plist->next->prev = plist;
    return list;
}