1

我有两个简单的结构：

struct Address
{
    char city[255];
};
typedef Address* AddressPtr;

struct Person
{
    char fullName[255];
    Address* address;
    Person* next;
};
typedef Person* PersonPtr;

Person 结构形成链接列表，其中新元素被添加到列表的开头。我想要做的是对它们进行排序fullName。起初我尝试交换链接，但我丢失了列表的开头，结果我的列表被部分排序。然后我决定通过交换节点的值来对列表进行排序。但我得到了奇怪的结果。对于名称列表：Test3, Test2, Test1，我得到Test3, Test3, Test3.

这是我的排序代码：

void sortByName(PersonPtr& head)
{
    TaskPtr currentNode, nextNode;
    for(currentNode = head; currentNode->next != NULL; currentNode = currentNode->next)
    {
        for(nextNode = currentNode->next; nextNode != NULL; nextNode = nextNode->next)
        {
            if(strcmp(currentNode->fullName, nextNode->fullName) > 0)
            {
                swapNodes(currentNode, nextNode);
            }
        }

    }
}

void swapNodes(PersonPtr& node1, PersonPtr& node2)
{
    PersonPtr temp_node = node2;
    strcpy(node2->fullName, node1->fullName);
    strcpy(node1->fullName, temp_node->fullName);

    strcpy(node2->address->city, node1->address->city);
    strcpy(node1->address->city, temp_node->address->city);
}

排序完成后，节点值有点奇怪。

更新

这就是我交换链接的方式：

void swapNodes(PersonPtr& node1, PersonPtr& node2)
{
    PersonPtr temp_person;
    AddressPtr temp_address;

    temp_person = node2;
    node2 = node1;
    node1 = temp_person;

    temp_address = node2->address;
    node2->address = node1->address;
    node1->address = temp_address;
}
4

4 回答 4

1

当您使用单链表交换两个元素时，您应该从头开始运行它，直到最后一个要交换的元素。在运行时，需要找到指向这两个必须交换的元素的两个先前的指针（如果元素是列表中的第一个元素，则一个先前的指针可能为空）。然后这个循环完成（在要交换的第二个元素处）你必须有四个：要交换的第一个元素（first），第一个元素之前的元素（first_prev；可能为空），第二个元素（second）和要交换的前一个元素（second_prev ; 可能为空）。然后你只需要像这样交换它们：

  temp_first_next = first->next;
  temp_second_next = second->next;

  /* put first element at place of the second */
  first->next = temp_second_next;
  if (second_prev) {
    second_prev->next = first;
  }

  /* put second element at place of the first */
  second->next = temp_first_next;
  if (first_prev) {
    first_prev->next = next;
  }

如果你真的在使用 C++，最好切换到使用std::string，std::list并为每个元素使用类。它会更容易，更少的指针。:)

于 2013-11-11T16:12:44.790 回答
1

您不需要使用 strcpy。当你交换节点时，你可以通过交换 .next 成员变量来完成。使用链表的唯一原因是复制一堆数据。

在这种情况下，最好在纸上画出情况。在一行中画几个框：

 W["1"] -> X["3"] -> Y["2"] -> Z["4"]

好的，所以，我们有四个节点，WXY 和 Z，设置为 W 指向 X，X 指向 Y，Y 指向 Z。

每个节点都有一个字符串值。W的值为1，X的值为3，Y的值为2，Z的值为4。

我们想要对节点进行排序，以便字符串值按升序排列：1、2、3、4。

现在，您一直在尝试通过交换实际数据值来实现这一点：

swap(X.data, Y.data)

... 导致：

W["1"] -> X["2"] -> Y["3"] -> Z["4"]

这会起作用，但这不是一个好主意，原因有很多。一方面，它非常容易出错。对于两个，你放弃了使用链表的主要好处：交换链接，而不是数据。

如果你交换节点链接，它会是什么样子：

 W["1"] -> Y["2"] -> X["3"] -> Z["4"]

注意没有数据移动——W 的值仍然是 1，X 的值仍然是 3，Y 的值仍然是 2，Z 的值仍然是 4。但是我们重新安排了遍历顺序：现在 W 导致 Y，这导致 X，这导致 Z，给出 1、2、3、4 的预期结果。

这可能听起来令人困惑，但一旦你进入正确的心态，它就很简单。让我们一次一个地分解这些步骤。

我们的初始状态有什么区别...

 W["1"] -> X["3"] -> Y["2"] -> Z["4"]

...以及我们想要的状态？

 W["1"] -> Y["2"] -> X["3"] -> Z["4"]

啊哈，不同的是我们交换了中间的两个节点。所以这就是我们需要弄清楚如何做的操作：如何交换两个相邻节点？

好吧，让我们这样看。W过去通向X，X通向Y，Y通向Z。

我们希望 W 导致 Y；我们希望 Y 导致 X；我们希望 X 通向 Z。

你有看到？这涉及修改三个节点。如果您只知道其中两个节点，您将无法做到这一点。您必须能够连续修改三个。

让我们摆脱一些混乱：

A -> B -> C -> D

我们想要交换 B 和 C，这样它最终看起来像：

A -> C -> B -> D

如何？

好吧，该图等效于以下内容：

A -> A.next -> A.next.next -> A.next.next.next

所以这就是我们可以做的。让我们定义一个操作，它接受一个节点，并交换它之后的两个节点。因此，如果我们在 A 上使用我们的操作，那么它将交换 B 和 C。或者如果我们在 B 上使用我们的操作，那么它将交换 C 和 D。

就是这样。

void swapAfter( Node* node ) {
  Node* A = node;
  Node* B = node->next;
  Node* C = node->next->next;
  Node* D = node->next->next->next;

  A->next = C; // Lead A to C
  C->next = B; // Lead C to B
  B->next = D; // Lead b to D

  // Now we have A->C->B->D!
}

我们开始了。现在我们有了一种交换任意两个节点的方法。

我决定以这种（迂回）方式解释它的原因是帮助您理解和可视化链接列表的情况。初学者经常在精神上难以理解操作过程中发生的事情。通常他们只会盲目地做一本书告诉他们做的事情，而不是真正理解它为什么有效。而在这个例子中，每一步都非常明显。

但是，如果您尝试直接使用“swapAfter”功能，它可能对您不是很有用。一方面，如果您尝试在最后一个节点上使用它，它会崩溃，因为它没有错误检查。但重点是让您了解链表是如何工作的，而不是给您一个 swapNodes 函数。:-)

主要的收获是你没有为你的 swapNodes 函数提供足够的参数......如果你想交换“curNode”和“nextNode”，那么此时你必须知道哪个节点在 curNode 之前（“prevNode”）。然后你会做类似的事情：

Node* finalNode = nextNode->next;

// right now, we have..
//   prevNode -> curNode -> nextNode -> finalNode

// we want..
//   prevNode -> nextNode -> curNode -> finalNode

// so..
prevNode->next = nextNode;
nextNode->next = curNode;
curNode->next = finalNode;

请注意，您必须进行错误检查才能使其完全正常工作……例如，如果 nextNode 为 NULL 怎么办？或者，如果 prevNode 为 NULL（意味着 curNode 是第一个节点？）如何处理每个案例。

如果你想回避所有这些复杂性，真的没有理由使用链表。相反，您可以创建一个指针数组：

Person** people = new Person*[4];
for ( int i = 0; i < 4; i++)
  people[i] = new Person();

然后你可以通过交换它的元素来对该数组进行排序：

if ( strcmp(people[1]->fullName, people[2]->fullName) > 0 )
  swap( people[1], people[2] );

不再处理“下一个”指针。但是现在如果你想在你的数组中添加超过 4 个人，你将不得不重新分配它，因为它是一个固定的大小。所以这就是权衡。

无论如何，我希望这有点帮助。这是我第一次真正的 Stack Overflow 评论，所以如果有点粗鲁，我深表歉意。

于 2013-11-11T16:48:22.907 回答
1

为了交换单链表中的节点，您需要的不仅仅是要交换的两个节点。至少要修改三个指针。

+--------+ next +---------+ next +---------+ next +---------+
| before |----->|  node1  |----->|  node2  |----->|  after  |
+--------+      +---------+      +---------+      +---------+

要交换node1and node2，您需要交换node1->nextand node2->next，然后before->next指向node2。当然，为了修改before->next，你需要知道before. （如果节点不相邻，您还必须更新node2的父节点。）

现在，如果您只是交换数据而不是指针，那么只需交换两个节点就可以了。但是，如果这是目标，那么您正在做两件事非常错误。

  1. temp_node== node2。这意味着它们都指向同一个对象。*node1因此，当您从into复制数据时*node2，您正在修改相同的对象temp_node指向。然后，当您从*temp_nodeinto复制时*node1，您实际上是在复制刚刚覆盖的数据。最终结果：所有节点的地址对象都包含相同的位。

    你需要temp_node指向一个独立的对象，或者干脆让它成为一个节点对象而不是一个指针，或者将数据复制到一个缓冲区什么的。

  2. 如果你想完成某件事，交换指针和交换数据是相互排斥的。在这里，您交换节点指针，然后交换数据指针......？有点违背了目的，不是吗？

    手表：

        //    node1             node2
    //    +----------+ next +----------+
    //    |   node   |----->|   node   |
    //    +----------+      +----------+
    //          | address        | address
    //          v                v
    //    +----------+      +----------+
    //    | address1 |      | address2 |
    //    +----------+      +----------+

    temp_person = node2;
    node2 = node1;
    node1 = temp_person;

    //    node2             node1
    //    +----------+ next +----------+
    //    |   node   |----->|   node   |
    //    +----------+      +----------+
    //          | address        | address
    //          v                v
    //    +----------+      +----------+
    //    | address1 |      | address2 |
    //    +----------+      +----------+

    到目前为止，一切都很好。两个指针互换。这意味着node1->address看到第二个节点的地址。

    但是等等：然后你交换地址指针。

        temp_address = node2->address;
    node2->address = node1->address;
    node1->address = temp_address;

    //    node2             node1
    //    +----------+ next +----------+
    //    |   node   |----->|   node   |
    //    +----------+--+   +----------+
    //           address|        | address
    //          +-------|--------+
    //          v       |
    //    +----------+  |   +----------+
    //    | address1 |  +-->| address2 |
    //    +----------+      +----------+

    所以现在，node1->address指向address1。您已取消交换数据。

    所以决定是否要交换指针或数据。如果交换数据，只需要两个节点的指针，不要修改next指针。另一方面，如果要交换整个节点，则需要“之前”节点，并且不要触摸数据指针-交换指针的全部目的是重新排列数据。

于 2013-11-11T15:59:49.637 回答
0

问题源于您在迭代列表时交换了列表的元素。

另一种方法可能是遍历列表并交换对象，直到它遍历列表一次而不交换任何元素。

于 2013-11-11T15:53:12.930 回答