2

我正在尝试为 C99 中的旅行商问题实现我自己的深度优先搜索算法，但我遇到了意外的分段错误。

我有一小部分节点（大致）对应于英国的地方，它们之间有对称的路径。问题出现在newNode()方法的早期，我创建一个新节点并设置其初始状态。这涉及为节点创建一个路径数组，该数组将指定连接的节点和它们之间的“距离”，其中每个路径的节点元素被初始化为 NULL。这些数组比我当前实现的示例图所需的要大得多（请参阅 参考资料MAX_PATHS），因此以后很容易扩展。

在这种情况下，paths数组可以包含 16 个元素。初始化此数组的 FOR 循环在i = 3. 完全让我想不通的原因。我gdb在代码下方添加了一些输出。希望它有所帮助，或者您可能更喜欢使用自己的方法。

谢谢; 任何帮助将不胜感激！

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NODES 4
#define MAX_PATHS 16

typedef struct _node_t node_t;
typedef struct _path_t path_t;

struct _node_t
{
    char name[64];
    struct _path_t* paths;
};

struct _path_t
{
    struct _node_t* node;
    int dist;
};

node_t* nodes[NODES];

node_t* newNode(char* name)
{
    node_t* toReturn = (node_t*) malloc(sizeof(node_t*));

    if (toReturn == NULL)
    {
        perror("malloc");
        exit(EXIT_FAILURE);
    }

    printf("toReturn (%p)\n", toReturn);

    strcpy(toReturn->name, name);

    toReturn->paths = (path_t*) malloc(sizeof(path_t) * MAX_PATHS);

    if (toReturn->paths == NULL)
    {
        perror("malloc");
        exit(EXIT_FAILURE);
    }

    printf("toReturn->paths (%p)\n", toReturn->paths);

    for (int i = 0; i < MAX_PATHS; i++)
        toReturn->paths[i].node = NULL; /* !!! */

    return toReturn;
}

void addPath(node_t* node1, node_t* node2, int dist)
{
    int i = 0;

    while (i < MAX_PATHS)
    {
        if (node1->paths[i].node == NULL)
        {
            node1->paths[i].node = node2;
            node1->paths[i].dist = dist;
            break;
        }

        i++;
    }

    if (i == MAX_PATHS)
    {
        fprintf(stderr, "Ran out of paths!!\n");
        exit(EXIT_FAILURE);
    }

    i = 0;

    while (i < MAX_PATHS)
    {
        if (node2->paths[i].node == NULL)
        {
            node2->paths[i].node = node1;
            node2->paths[i].dist = dist;
            break;
        }

        i++;
    }

    if (i == MAX_PATHS)
    {
        fprintf(stderr, "Ran out of paths!!\n");
        exit(EXIT_FAILURE);
    }
}

int getNodeIndex(node_t* node)
{
    for (int i = 0; i < NODES; i++)
        if (nodes[i] == node)
            return i;

    return -1;
}

void depthFirstSearch(node_t* node, int* visited, int depth, int length)
{
    printf("%s\n", node->name);

    int i = 0; /* Path pointer */

    int thisVisited[NODES];
    memcpy(thisVisited, visited, sizeof(int) * NODES);

    /* Set this node as visited */

    visited[getNodeIndex(node)] = 1;

    /* Now traverse all connected nodes that haven't been visited */

    while (node->paths[i].node != NULL)
    {
        if (visited[getNodeIndex(node->paths[i].node)] == 0)
            depthFirstSearch(node->paths[i].node, thisVisited, depth + 1,
                                  node->paths[i].dist);

        i++;
    }

    for (int j = 0; j < depth; j++)
        putchar(' ');
}

int main(int argc, char** argv)
{
    nodes[0] = newNode("Liverpool");
    nodes[1] = newNode("London");
    nodes[2] = newNode("Manchester");
    nodes[3] = newNode("Norwich");

    addPath(nodes[0], nodes[1], 212);
    addPath(nodes[0], nodes[2], 34);
    addPath(nodes[1], nodes[2], 208);
    addPath(nodes[1], nodes[3], 114);
    addPath(nodes[2], nodes[3], 191);

    int visited[NODES] = {0};

    depthFirstSearch(nodes[0], visited, 0, 0);

    return EXIT_SUCCESS;
}

在malloc()ing 节点及其路径数组之后：

(gdb) p toReturn
$16 = (node_t *) 0x602010
(gdb) p toReturn->paths
$17 = (struct _path_t *) 0x602030

在 FOR 循环之前：

(gdb) p toReturn->paths[0]
$18 = {node = 0x0, dist = 0}
(gdb) p toReturn->paths[1]
$19 = {node = 0x0, dist = 0}
(gdb) p toReturn->paths[2]
$20 = {node = 0x602030, dist = 0} // (I don't understand this value here.)
(gdb) p toReturn->paths[3]
$21 = {node = 0x0, dist = 0}
(gdb) p toReturn->paths[4]
$22 = {node = 0x0, dist = 0}
(gdb) p toReturn->paths[5]
$23 = {node = 0x0, dist = 0}
(gdb) p toReturn->paths[6]
$24 = {node = 0x0, dist = 0}
(gdb) p toReturn->paths[7]
$25 = {node = 0x0, dist = 0}
(gdb) p toReturn->paths[8]
$26 = {node = 0x0, dist = 0}
(gdb) p toReturn->paths[9]
$27 = {node = 0x0, dist = 0}
(gdb) p toReturn->paths[10]
$28 = {node = 0x0, dist = 0}
(gdb) p toReturn->paths[11]
$29 = {node = 0x0, dist = 0}
(gdb) p toReturn->paths[12]
$30 = {node = 0x0, dist = 0}
(gdb) p toReturn->paths[13]
$31 = {node = 0x0, dist = 0}
(gdb) p toReturn->paths[14]
$32 = {node = 0x0, dist = 0}
(gdb) p toReturn->paths[15]
$33 = {node = 0x0, dist = 0}

toReturnFOR循环之前的状态：

(gdb) p *toReturn
$36 = {
  name = "Liverpool", '\000' <repeats 15 times>, "\021\001", '\000' <repeats 37 times>, paths = 0x602030}

它保持不变，直到它在 FOR 循环中意外更改时i = 3

(gdb) p *toReturn
$40 = {
  name = "Liverpool", '\000' <repeats 15 times>, "\021\001", '\000' <repeats 37 times>, paths = 0x0}
4

1 回答 1

5 
node_t* toReturn = (node_t*) malloc(sizeof(node_t*));

这看起来不对。您需要分配node_tnot的大小node_t *。当我们这样做的时候，不要使用 malloc。

于 2013-02-27T22:17:43.117 回答