0

使用 MinGW 编译-O3 -Wall -c -fmessage-length=0 -std=c99

好吧，这就是我认为的问题所在......这是细分：

我有一个我使用的链接列表

typedef struct Coordinate{
    int x;
    int y;
    struct Coordinate *next;
} Coordinate;

我在 6x6 棋盘（矩阵）上添加“有效动作”（在黑白棋/黑白棋游戏中）。我检查移动是否有效的逻辑工作得很好——它把东西添加到让我陷入麻烦的列表中。

出于显而易见的原因，我想避免将重复值添加到列表中。但是，我尝试编写的每个函数（看起来应该可以工作）只会使应用程序崩溃，从而在漫长的一天中造成段错误。

所以这是我尝试编写的一个函数：

int inList(Coordinate *list, int x, int y) {

    if (list == NULL) return 0;

    while (list != NULL) {
        if (list->x == x && list->y == y) return 1;
        else list = list->next;
    }
    return 0;
}

并称它为：

Coordinate *validMoves = createNewCoordinate(-1, -1); // Just so that there is *something*

if (!inList(validMoves, 1, 1)) {
validMoves->next = createNewCoordinate(1, 1);
validMoves = validMoves->next;
}

据我所知，这应该可以完美运行。我已经在网上查找了示例，到目前为止，我在这个特定程序中对指针的所有真正令人费解的使用都没有遇到任何问题。

无论如何，真正的问题是，如果我不阻止重复项进入同一个列表（通过指针连接），那么我会得到一个无限循环（我想这是由于两个元素被认为是相等的，因为它们的非指针类型相等）。

我已经在 pastebin 上发布了代码的所有三个部分以供完整参考（不用担心，开源，伙计！）： othello.c othello_engine.c othello_engine.h

我试过调试，但我不是很擅长，我真的没有看到任何值得一提的东西。谁能解释可能发生的事情和/或举例说明如何避免链表中的重复？（我试过很多方法让我的大脑受伤）

编辑：我确实知道，当我稍后遍历列表时（在游戏中多次有效“转弯”之后），由于以下输出，我正在让自己进入周期性参考：

{1, 4} {3, 4} {1, 4} {3, 4} {1, 4} {3, 4}

我不知道theList = theList->next = theList（伪正确）是如何进入那里的，也许我们在矩阵中......

4

3 回答 3

1

我问你数据范围，以便我可以想一些其他方法来检查数据的重复。如果内存对您没有限制。您可以执行以下操作。这是一种检查重复数据值的逻辑类型。我有一个简单的数据值查找表，其索引和值相同，并且有一个计数字段。如果计数字段为零，则表示可以输入唯一值。删除数据时，减去计数。这样您就可以跟踪计数并确保值的唯一性。因为，它也是一个不需要遍历的数组。必须为此管理实施一些额外的代码。但是，如果设计得当，它应该是可能的。

在此处输入图像描述

于 2013-09-26T08:31:45.053 回答
1

分段错误通常是指向错误位置（可能为空）的取消引用指针。每次使用指针值时添加检查（类似于 if ptr != NULL）。

在您的代码中，我注意到一些看起来有点错误的东西。当您找到要添加的新移动时，您可以分配它：

validMovees->next = createNewCoordinate(x, y);

然后通过调用使列表本身指向最后一个节点：

validMoves = validMoves->next;

所以现在你的 validMoves 列表实际上只包含一个元素（最后一个），因为它指向列表的末尾。您根本不想更改 validMoves 指针，这应该始终是列表的开头。取而代之的是另一个指向列表末尾的指针，例如：

Coordinate *validMoves = createNewCoordinate(-1, -1); // Just so that there is *something*
Coordinate *listEnd = validMoves ;


if (!inList(validMoves, 1, 1)) {
listEnd->next = createNewCoordinate(1, 1);
listEnd = listEnd->next;
}

这可能会导致您无限添加相同的动作？？- 不确定没有看到你所有的代码

- - - 编辑 - - -

Coordinate *validMoves;
Coordinate *listEnd = validMoves;

if (!inList(validMoves, 1, 1))
{
    if (validMoves == NULL)
    {
        validMoves = createNewCoordinate(1, 1); // first time only
        listEnd = validMoves;
    }
    else
    {
        listEnd->next = createNewCoordinate(1, 1); // add new element to the end
        listEnd = listEnd->next; // Move listEnd to last element
    }
}
于 2013-09-26T06:57:26.923 回答
1

如何将新坐标添加到链表中存在问题。

validMoves是指向Coordinate有效移动列表中第一个的指针，因此最初您的链接列表看起来像：

有效移动 -> [1st_move] -> [2nd_move] -> [3rd_move] -> ... -> [last_move]

回想一下，这些箭头来自next存储在结构中的指针（例如，[1st_move]' 的next指针指向[2nd_move]，而[last_move]' 的next指针是NULL）。

现在让我们看看当代码运行时会发生什么，它将新坐标添加到列表中（特别是标记为 的行2）：

if (!inList(validMoves, 1, 1)) {
validMoves->next = createNewCoordinate(1, 1); //2
validMoves = validMoves->next;
}

在 line2中，发生了两件事：

  • createNewCoordinate(1, 1)分配一个 new Coordinate，然后返回一个指向 said 的指针Coordinate，初始内容设置为 {1,1,NULL}。
  • 然后，所next指向的结构的指针validMoves（即[1st_move]'next指针）被覆盖，并设置为指向这个{1,1,NULL}结构。

这使您的链接列表看起来像：

validMoves -> [1st_move] -> [内容为 {1,1,NULL} 的新结构]

？？？-> [2nd_move] -> [3rd_move] -> ... -> [last_move]

[1st_move]的next指针，以前是指向的[2nd_move]，现在指向你新建的坐标，现在什么都不指向了[2nd_move]！所以，原来的链表从那时[2nd_move]起就被孤立了。

gdb有助于调试此类问题。一个好的起点是在可疑代码区域之前添加一个断点，将重要变量放在显示列表上（如validMoves、validMoves->next、validMoves->next->next），然后逐步执行可疑区域并查看变量的打印值是否有意义每一步。

Coordinate为了解决这个问题，我们可以将链表走到末尾，然后将指向 {1,1,NULL} 的指针添加到那里，但是在链表的开头添加新的更容易（也更快） ，但是你将需要一个临时指针变量，如下所示：

if (!inList(validMoves, 1, 1)) {
    Coordinate *temp = createNewCoordinate(1, 1);
    temp->next = validMoves; // the new Coordinate now becomes {1,1,&[1st_move]}
    validMoves = temp;
}

现在新添加Coordinate的在链表的开头，旧[1st_move]的已经移动到第二个位置，[2nd_move]到第三个，依此类推（链表的顺序与它们添加的顺序相反，但我认为在这个用例中元素的顺序无关紧要）。

您所述的申请是针对黑白棋的。为什么不分配一个连续的size* size chars 数组来存储位置是否是有效移动，而不是使用链表？

char * validmoves = malloc(size*size);

这仅使用每个棋盘单元 1 字节的内存（您可以将其设置为 1 或 0 以指示移动是否有效），并且您不需要遍历链表来确定移动是否已经存在，只需导航到validmoves[(row*size)+col]并检查字节是否已设置；只记得在使用前初始化数组。

快乐编码！

编辑：在我上面的答案中，我假设您的createNewCoordinate函数将创建的结构的next指针的值初始化为NULL，但现在注意到您在 othello_engine.c 中的实现使其未初始化。您可能确实希望将其初始化为NULL.

于 2013-09-26T09:43:26.683 回答