c++ - 归并排序函数(自然归并排序)

Question

有几种方法可以进行归并排序，但我特别需要它像自然归并排序一样工作。该算法会在文件中生成更小的数字列表，如下所示:

原始列表:35 27 24 28 31 37 1 4 7 6 8 9

较小的列表部分:[35]、[27]、[24、28]、[31、37]、[1、4、7]、[6、8、9]

如您所见，每当未排序列表遇到一个小于其现值的数字时，就会创建一个新单位。一旦列表结束，这个列表就会以另一种方式分成另外两个列表:

第一个列表:[35]、[24、28]、[1、4、7]

第二个列表:[27]、[31、37]、[6、8、9]

最后一步涉及再次将两个列表拉到一起，并在遍历时比较第一个列表项和第二个列表项中的单元值。例如，将列表一中的第一个单元与列表二中的第一个单元进行比较，并保持数字顺序。任何剩余的单元都将添加到最后(未显示)。

合并两个列表:[27, 35], [24, 28, 31, 37], [1, 4, 6, 7, 8, 9]

此过程将重复，直到列表以一个单元排序。

除了合并两个列表之外，我已在此算法中设置了一切以正常工作，并且调试或定位问题非常困难。在进入段错误之前，它已经进行了大约一半。无论如何，我不能在这个程序上使用归并排序 STL，它都在链表中。

注意:构造函数和其他必要的函数已经到位。我故意遗漏了其他功能，以体现特定功能。

class mergeList
{
   public:

      //Setters
      void setNumber(int item);
      void setStart(bool newStatus);
      void setEnd(bool newStatus);
      void setPrev(mergeList* node);
      void setNext(mergeList* node);

      //Getters
      int getNumber();
      bool getStart();
      bool getEnd();
      mergeList* getPrev();
      mergeList* getNext();

   private:
      int number;

      bool startSection;
      bool endSection;

      mergeList* prev;
      mergeList* next;
};

class mergeListObject
{
   public:
     mergeList* firstNode;
     mergeList* lastNode;

   void mergeLists(mergeListObject &firstList,
                   mergeListObject &secondList);

   //Other functions in program are in here.
};

void mergeListObject::mergeLists(mergeListObject &firstList,
                                 mergeListObject &secondList)
{
   mergeList* combTraverse = firstNode;
   mergeList* firstTraverse = firstList.firstNode;
   mergeList* secondTraverse = secondList.firstNode;

   bool listDone = false;

   //This will clear the combination list for insertion
   while (combTraverse != NULL)
   {
      combTraverse->setNumber(-1);
      combTraverse->setStart(false);
      combTraverse->setEnd(false);

      combTraverse = combTraverse->getNext();
   }

   combTraverse = firstNode;

   combTraverse->setStart(true);

   while (listDone == false)
   {
      //This will go until the first list is traversed.
      do
      {
         bool exception = false;

         int j = firstTraverse->getNumber();
         int k;

         //If the second list is still active, this will
         //grab its current value for comparison.
         if (secondTraverse != NULL)
            k = secondTraverse->getNumber();

         //Second list is done, will automatically grab
         //first list's value and traverse through to the end.
         if (secondTraverse == NULL)
            combTraverse->setNumber(firstTraverse->getNumber());

         else
         {
            //Both values from both lists are compared.
            if (j <= k)
               combTraverse->setNumber(firstTraverse->getNumber());

            else
            {
                exception = true;
                combTraverse->setNumber(secondTraverse->getNumber());
            }
         }

         //If the first value unit was used, move the first list iterator up.
         //Otherwise, the second list's iterator moves up.
         if (exception == false)
            firstTraverse = firstTraverse->getNext();

         else
            secondTraverse = secondTraverse->getNext();

         exception = false;
      }
      while (firstTraverse->getEnd() == false);

      //If the second list isn't done, this will finish it.
      do
      {
         combTraverse->setNumber(secondTraverse->getNumber());

         secondTraverse = secondTraverse->getNext();
         combTraverse = combTraverse->getNext();
      }
      while (secondTraverse->getEnd() == false);

      combTraverse->setEnd(true);

      //Marks the end of the section and sets the next one,
      //considering it isn't the end of the list.
      if (combTraverse->getNext() != NULL)
         combTraverse->getNext()->setStart(true);

      //Both of these should end up at the start of a unit in their own lists.
      firstTraverse = firstTraverse->getNext();
      secondTraverse = secondTraverse->getNext();

      //Are both lists done?
      if (firstTraverse == NULL &&
          secondTraverse == NULL)
         listDone = true;
   }

   return;
}

int main()
{
   mergeListObject one;
   mergeListObject two;
   mergeListObject combined;

   //The two lists are already separated. All
   //other functions have already been called.

   combined.mergeLists(one, two);

   return 0;
} 

Answer 1

我发现的第一个错误是在合并函数的末尾:

firstTraverse = firstTraverse->getNext();
secondTraverse = secondTraverse->getNext();

可能会产生运行时错误(“访问冲突”或“段错误”，具体取决于编译器和操作系统)，您必须将其更改为

if (firstTraverse)
    firstTraverse = firstTraverse->getNext();
if (secondTraverse)
    secondTraverse = secondTraverse->getNext();

请注意，这些指针实际上可以为 NULL。

您还必须将 while (firstTraverse->getEnd() == false); 更改为 while(firstTraverse & firstTraverse->getEnd() == false); 同样，只要第一个列表的分区数少于第二个列表，firstTravers 就可以为 NULL。