1

我正在查看来自http://publications.gbdirect.co.uk/c_book/chapter6/structures.html的示例 6.7

（为了方便贴在这里）

struct list_ele *
sortfun( struct list_ele *list )
{

      int exchange;
      struct list_ele *nextp, *thisp, dummy;

      /*
       * Algorithm is this:
       * Repeatedly scan list.
       * If two list items are out of order,
       * link them in the other way round.
       * Stop if a full pass is made and no
       * exchanges are required.
       * The whole business is confused by
       * working one element behind the
       * first one of interest.
       * This is because of the simple mechanics of
       * linking and unlinking elements.
       */

      dummy.pointer = list;
      do{
              exchange = 0;
              thisp = &dummy;
              while( (nextp = thisp->pointer)
                      && nextp->pointer){
                      if(nextp->data < nextp->pointer->data){
                              /* exchange */
                              exchange = 1;
                              thisp->pointer = nextp->pointer;
                              nextp->pointer =
                                      thisp->pointer->pointer;
                              thisp->pointer->pointer = nextp;
                      }
                      thisp = thisp->pointer;
              }
      }while(exchange);

      return(dummy.pointer);
}

我明白了基本的想法，但我无法真正解释那里发生了什么。有人可以更深入但以简单的方式解释该排序功能中发生了什么吗？

一般的一些问题：

  • 为什么dummy.pointer = list;需要？dummy然后在函数末尾返回，为什么列表仍然排序？
  • 评论The whole business is confused by working one element behind the first one of interest.是什么意思？
4

2 回答 2

2

该算法通过列表查看每个列表项及其之后的项。如果它们出现故障，它们就会被调换。然后重复该过程。最终不会有任何不合适的地方，也没有任何东西被转换；到那时所有的工作都完成了（如exchanged保持为零所示）。换句话说，最后一次通过列表，没有任何东西可以互换。

dummy 用于跟踪列表本身（以防前 2 个列表项被切换）。它被使用（而不仅仅是一个简单的指向列表的指针，因为它也可以用作假的第一项，以便可以比较列表中的原始第一项。它消除了对结果列表的特殊情况的需要第一项与原始列表的第一项不同。

在纸上列出 1、2、3 和 4 个项目。然后你会看到它是如何工作的。当您完成它时，请尝试将列表按顺序排列并运行算法。然后交换列表中的 2 个项目，然后再做一次。

关于整个业务被混淆的评论，恕我直言，您必须跟踪单链表中的 3 个节点才能交换其中两个节点。如果列表中有 ACB 项（目标是列表为 ABC），当您交换 B 和 C 时，您还必须有权访问 A - 它的“下一个节点”指针必须从 C 更改为 B。

于 2012-06-09T20:09:48.443 回答
2

dummy是一个局部变量，首先设置为列表的开头。临时变量thisp被设置为指向dummy，所以当它被更新时，指向的内容dummy也会被更新。因此，dummy.pointer最终将指向作为排序列表新开始的元素。 list仍将指向列表的原始开头，因此返回值以便可以更新头指针。

我认为他们混淆的意思是我们感兴趣的元素是nextp，而不是当前元素（或thisp）。也就是说，我们将列表中的下一个元素与当前元素进行比较，而不是将当前元素与前一个元素进行比较。我想这很令人困惑，但我真的不这么认为。

注意：这是冒泡排序。更好的排序算法是Merge Sort ，在http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html上有一个实现。

于 2012-06-09T20:06:34.263 回答