更新。它在 FOR 循环中为 65,519 工作。如果我将它增加到 65,520，它就会失败。完全奇怪。
此程序不适用于大量输入。它非常适合小输入。我在 Xcode 上遇到异常。
Thread 1 : EXC_BAD_ACCESS (code=2, address = 0x7fff5f3fffb8).
请告诉我如何绕过这个奇怪的错误。
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
typedef struct Node * nodePtr;
struct Node{
int data;
nodePtr next;
};
nodePtr globalHead;
void partition(nodePtr head, nodePtr *front, nodePtr *back){
nodePtr fast;
nodePtr slow;
if (head == NULL || head->next == NULL){
*front = head; // &a
*back = NULL; // &b
}else{
slow = head;
fast = head->next;
while(fast != NULL){
fast = fast->next;
if(fast != NULL){
slow = slow->next;
fast = fast->next;
}
}
*front = head; // a
*back = slow->next; // b
slow->next = NULL;
//printList(*front);
//printList(*back);
}
}
nodePtr mergeLists(nodePtr a, nodePtr b){
nodePtr mergedList = NULL;
if (a == NULL){
return b;
}else if (b == NULL){
return a;
}
try {
if (a->data <= b->data){
mergedList = a;
mergedList->next = mergeLists(a->next, b);
}else{
mergedList = b;
mergedList->next = mergeLists(a, b->next);
}
}
catch (int e) {
cout << "Error is . . " << e << endl;
}
return mergedList;
}
void mergeSort(nodePtr *source){
nodePtr head = *source;
nodePtr a = NULL;
nodePtr b = NULL;
if(head == NULL || head->next == NULL){
return;
}
partition(head, &a, &b);
mergeSort(&a);
mergeSort(&b);
*source = mergeLists(a, b);
}
void push(nodePtr *head, int data){
nodePtr newNode = (nodePtr) malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
if ((*head) == NULL){
*head = newNode;
globalHead = *head;
}else{
(*head)->next = newNode;
*head = newNode;
}
}
void printList(nodePtr head){
nodePtr current = head;
while(current != NULL){
printf("%d ",current->data);
current = current->next;
}
printf("\n");
}
// *head = head in the main function,
// it is only there to connect the two and
// not let make the function return anything
// passed by reference
// globalHead points to the start of the linked list
// if you are passing the address over here you have to
// make a double pointer over there in the function
int main(void)
{
nodePtr head = NULL;
// linked list is formed from top to bottom fashion
// push is done in constant time O(1)
long long int i;
//Pushing 200,000 Elements to the Linked List.
for(i=1 ; i<=200000 ; i++) {
push(&head, rand()%200000);
}
printList(globalHead);
mergeSort(&globalHead);
cout << "After Sorting . . \n";
printList(globalHead);
return 0;
}
最佳答案
使用递归 mergeLists() 是个问题，它会为列表中的每个节点调用自身。尝试更改代码，以便代码循环并将节点附加到最初为空的 mergeList，使用指向节点的第二个指针，或者可选地使用指向最初设置为 &mergeList 的节点的指针的指针。例如，使用名称 pMerge 而不是 mergeList:
Node * mergeLists(Node *a, Node *b)
{
Node *pMerge = NULL; // ptr to merged list
Node **ppMerge = &pMerge; // ptr to pMerge or prev->next
if(a == NULL)
return b;
if(b == NULL)
return a;
while(1){
if(a->data <= b->data){ // if a <= b
*ppMerge = a;
a = *(ppMerge = &(a->next));
if(a == NULL){
*ppMerge = b;
break;
}
} else { // b <= a
*ppMerge = b;
b = *(ppMerge = &(b->next));
if(b == NULL){
*ppMerge = a;
break;
}
}
}
return pMerge;
}
这是一个快速方法的示例代码，它使用指向列表 aList[] 的指针数组对链表进行排序，其中 aList[i] 指向大小为 2 的 i 次方的列表，它使用 mergeLists( ).
#define NUMLISTS 32 // size of aList
Node * mergeSort(NODE *pList)
{
Node * aList[NUMLISTS]; // array of pointers to lists
Node * pNode;
Node * pNext;
int i;
if(pList == NULL) // check for empty list
return NULL;
for(i = 0; i < NUMLISTS; i++) // zero array
aList[i] = NULL;
pNode = pList; // merge nodes into array
while(pNode != NULL){
pNext = pNode->next;
pNode->next = NULL;
for(i = 0; (i < NUMLISTS) && (aList[i] != NULL); i++){
pNode = mergeLists(aList[i], pNode);
aList[i] = NULL;
}
if(i == NUMLISTS)
i--;
aList[i] = pNode;
pNode = pNext;
}
pNode = NULL; // merge array into one list
for(i = 0; i < NUMLISTS; i++)
pNode = mergeLists(aList[i], pNode);
return pNode;
}
关于c++ - C++中的合并排序单链表因大输入而失败，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33732551/