1

所以我仍在尝试用 C 语言解决链表问题。它们现在让我难以置信，因为我还没有完全理解指针，更不用说指向指针的指针，以及链表需要的动态内存分配.

我正在尝试创建一个具有独立高度和宽度值的二维数组。它们最多为 30x30。我有一个二维数组，我们称之为 arr[x][y]。arr[x][y] 填充了从 -2 到 1 的整数值，我如何将这个二维数组转换为链表？然后我将如何随心所欲地访问此链接列表中的值？我很困惑，任何帮助将不胜感激。当我们说话时，我正在浏览教程。

此外，这应该是一种堆栈链表，我可以在其中调用诸如 push（将新值推送到链表顶部）、pop（从链表顶部弹出值）、top（返回最近压入堆栈的值），isEmpty（检查堆栈是否为空）。

我不需要任何完整的代码，但代码在这里会很有帮助。我只需要了解链接列表，以及如何实现这些功能。

此外，这是与之相关的作业：作业

这是一个迷宫求解器，我已经完成了将 ascii 图片分析为二维数组的整数值的代码。如上所述，这就是我需要帮助的地方。

4

4 回答 4

3

提示：根据您的分配，堆栈不应该完全代表数组，而是代表您动态构建的路径，以找到从迷宫的起始位置到迷宫的目标位置的路径。

于 2012-11-05T20:19:06.057 回答
2

基本上，您需要创建一个链接列表，其每个节点都是作为成员包含的另一个列表的头部（从概念上讲，它向下增长），以及列表中通常的下一个指针。

要访问像 arr[3][4] 这样的二维数组这样的元素，您需要在保持 y 计数的同时遍历第一个列表，然后向下移动计数 x 或者您可以反之亦然。

这是一种常见的数据结构分配，其名称为“多堆栈或多队列”，如果通过列表实现，则可以提供您正在寻找的内容。

struct Node
{
    int data;
    struct Node *next;
    struct Node *head; // This head can be null initially as well as for the last node in a direction
};
于 2012-11-05T20:17:42.183 回答
1

首先，您需要定义正确的结构。第一次创建一个列表会更容易，该列表在指向下一个节点的指针为 NULL 时终止。之后，您将发现带有哨兵的列表、双向列表和现在的东西可能看起来太复杂了。
例如这是一个结构： 

typedef struct __node
{
    int info;
    struct __node* next;
}node;

typedef node* list;

这次假设列表和节点是一回事，您会发现列表的概念比节点的概念更精确，例如您可以在列表中存储它的长度（避免每次都计算所有节点） ，但现在让我们这样做。
您初始化列表： 

list l=NULL;

因此列表包含零个节点，要测试它是否为空，您只需查看指针是否为 NULL。
添加一个新元素： 

if(NULL==l)
{
    l=(node*)malloc(sizeof(node));
    l->next=NULL;
    l->info=0;
}

现在列表包含零个节点，创建一个函数来添加一个新节点： 

void pushBack(list* listPointer, int info)
{
    if(NULL==*listPointer)
    {
        *listPointer=(node*)malloc(sizeof(node));
        (*listPointer)->info=info;
    }
    else
    {
        node* ptr=l;
        while(ptr->next!=NULL)
            ptr=ptr->next;
        ptr->next=(node*)malloc(sizeof(node));
        ptr->info=info;
    }
}

在前面添加元素也可以提高效率。或者通过返回添加的元素来优化代码，这样你就不必每次都找到最后一个元素。我把这个留给你。现在让我们为每个元素调用pushBack函数数组： 

for(int i=0; i<N; i++)
{
    pushBack(l,arr[i]);
}

就是这样，学习实现链表的方法。

于 2012-11-05T20:29:37.047 回答
1

您不应该将整个数组转换为链表，您只应该将最佳路径转换为链表。当你遇到死胡同时，你会通过蛮力、尝试方向和回溯来做到这一点。

你的路径，链表，需要看起来像这样：

struct PathNode
{
    int coordX, coordY;
    PathNode * next, * prev;
}

如果我以后记得，我会画一张这种结构的图片或其他东西并将其添加到帖子中。在几个小时内评论这篇文章以引起我的注意。

该列表将始终包含一个起点，该起点将是列表中的第一个节点。当您一个接一个地移动到其他位置时，您会将它们推到列表的末尾。通过这种方式，您可以按照从当前位置到迷宫开头的路径，只需按顺序从列表中逐个弹出元素即可。

这个特殊的链表的特殊之处在于它有两种方式：它有一个指向下一个元素和前一个元素的指针。仅具有两者之一的列表称为单链表，具有两者的列表称为双向链表。单链表只有一种方式，并且只能在一个方向上遍历。

把你的链表想象成一堆巨大的字符串，每个字符串都有一个起始端和一个结束端。当您穿过迷宫时，您会在您访问的每个节点处系上一根绳子，然后将您带到下一个广场。如果你不得不回溯，你把绳子带回来，这样它就不再指向错误的方格了。一旦你找到了通往迷宫尽头的路，你就可以通过跟随绳子来追踪你的步骤。

你能解释一下 -> 的确切含义吗？

->是一个多合一的指针解引用和成员访问运算符。假设我们有：

PathNode * p = malloc(sizeof(*p));
PathNode q;

我们可以通过以下任何一种方式访问​​ p 和 q 的成员：

(*p).coordX;
q.coordX;
p->coordX;
(&q)->coordX;
于 2012-11-05T20:31:23.923 回答