4

我正在做一个模拟操作系统进程调度程序的计算机科学项目。我有多个单链表，需要在它们之间移动节点。我正在尝试编写一个通用函数来实现这一点，但我认为我使用指针的弱点阻碍了我。

如何实现所需的功能？到目前为止，我有以下内容：

typedef struct process_list_struct ProcessList;

struct process_list_struct
{
    Process proc;
    ProcessList* next;
};

void change_lists(ProcessList* node, ProcessList* newlist)
{
    ProcessList* temp = NULL;
    debug_printf("change_lists reached\n");
    temp = node;
    if(!node)
    {
        debug_printf("Error: change_lists failed!\n");
        return;
    }
    node = node->next;
    temp->next = newlist;
    newlist = temp;
    return;
}

结果很奇怪......我最终得到的第一个列表只包含我想要移动的节点并且其他所有内容都丢失了（与我想要的效果几乎相反），并且新列表（测试为开始为空）仍然是空的。

我在单个列表中查找了节点交换的实现，并且看到人们使用双指针代替，但这真的让我感到困惑。有人可以告诉我如何在这种情况下应用它们吗？我尝试使用它们，但它们与结构的引用指针元素结合起来真的很混乱。

非常感谢帮助！

4

4 回答 4

1

您按照四个步骤将节点从一个列表转移到另一个列表是错误的：

temp = node
node = node->next;
temp->next = newlist;
newlist = temp;

见下面我用图表显示：

假设您在链表 1 中有节点： 

    +---+----+----+      +----+----+----+      +---+----+----+
  ->|   zero      |----->|      one     |----->|    two      |--
    +---+----+----+      +----+----+----+      +---+---+-----+
                             ^   ^
                             |   |
                             |  node 
    after temp=node        temp

之后：node = node->next;事情变成：

    +---+----+----+      +----+----+----+      +---+----+----+
  ->|   zero      |----->|      one     |----->|    two      |--
    +---+----+----+      +----+----+----+      +---+---+-----+
                             ^                        ^
                             |                        |
                             temp                    node

在temp->next = newlist;这之后？ 

    +---+----+----+      +----+----+----+      +---+----+----+
  ->|   zero      |----->|      one     |      |    two      |--
    +---+----+----+      +----+----+----+      +---+---+-----+
                             ^       |                ^
                             |       |                |
                             temp    |                node     
                                     |
                                     |
                                     |    "head node"
                                     |   +---+----+----+   +---+----+---+
         "This is your list-2"       |-->|   FIVE      |-->|   SIX      |--
                                         +---+---+-----+   +---+----+---+ 
                                          newlist

你的背阔肌步骤newlist = temp;？

                           newlist                    
                            |
                            ▼ "head node"
    +---+----+----+      +----+----+----+      +---+----+----+
  ->|   zero      |----->|      one     |      |    two      |--
    +---+----+----+      +----+----+----+      +---+---+-----+
                             ^       |                ^
                             |       |                |
                             temp    |                node     
                                     |
                                     |    
                                     |   +---+----+----+   +---+----+---+
         "This is your list-2"       |-->|   FIVE      |-->|    SIX     |--
                                         +---+---+-----+   +---+----+---+

这是你做的。但这不是你想要的？
您将节点从一个列表转移到另一个列表的算法是错误的另外您犯了技术错误，您正在按值传递指针（您需要指向指针的指针以反映调用函数时的更改）

因为你想将节点从一个列表转移到另一个，并传递一个列表中的指针和node另一个列表的头，你需要传递指针的指针来反映调用函数的变化，因此你的声明在我看来是错误的： 

void change_lists(ProcessList* node, ProcessList* newlist)

我认为应该是：

void change_lists(ProcessList** node, ProcessList** newlist)

使用此原型编写代码以转移节点。

编辑：（建议）

您的代码中的基本问题是，要在列表一中移动一个节点（例如一个），您不会更改指向先前节点（图中的零节点）的指针，您需要使 

[zero] ---> [two]

@CodeRat 在他的列表中犯了类似的错误：在单链表中交换节点

我给了他一个我认为会帮助你实现代码的答案。

旧答案：

我能找到的一个错误：而不是

*temp = *node;

你应该写

temp = node;

地址不是值

这样做*temp = *node;是未定义的行为，因为您没有为 temp 分配内存，您需要在 temp 中分配地址。（temp 指向 NULL）因为您想将节点从一个列表转移到另一个列表，这就是您需要的原因temp = node;

于 2013-04-09T15:06:24.753 回答
0

我相信你的原型是错误的，它太简单了。

您不能移动单链表的节点，而不能以某种方式在以后更改哪个节点被视为列表的开头。

否则，如果移动第一个节点会发生什么？周围的代码将保留指针，但节点现在逻辑上是移动目标列表的一部分，并且一切都被破坏了。

此外，这同样适用于目的地列表：如果在移动之前它是空的怎么办？

于 2013-04-09T15:10:18.973 回答
0

这段代码中明显错误的一件事是*temp = *node;when temp= NULL。您不能取消引用 NULL 指针。

此外，如果node属于单链表，如果您只有一个指向node. 要删除它，您需要更改指向的节点，node使其不再指向node，而是指向NULL或指向后面的节点node。如果您使用双向链表，您可以找到node仅给出指向 的指针的邻居节点node。

于 2013-04-09T15:12:28.690 回答
0

要从单链表中删除一个节点，它的前一个节点是必需的。前一个节点必须链接到下一个节点。

如果前一个节点对函数可用，那么很好，但如果没有，则必须从头部开始查找。因此，需要头部。

两个列表的标题都是必需的。并且由于删除或添加操作可以更改头指针，因此很自然地将它们作为指针传递。

于 2013-04-09T15:45:12.360 回答