有几种方法可以进行归并排序,但我特别需要它像自然归并排序一样工作。该算法会在文件中生成更小的数字列表,如下所示:
原始列表: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;
}
最佳答案
我发现的第一个错误是在合并函数的末尾:
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。
关于c++ - 归并排序函数(自然归并排序),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6671847/