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 に答える