双向链表的归并排序
Merge Sort on Doubly Linked List
如何合并 2 个给定的 DList 而不必先对它们进行排序?
当我在屏幕上显示时,我的排序功能似乎不起作用(它不合并项目)
DoublyLinkedList MergeSort(DoublyLinkedList &ls1, DoublyLinkedList &ls2)
{
DoublyLinkedList ls;
Initial(ls);
if(isEmpty(ls1))
return ls2;
if(isEmpty(ls2))
return ls1;
if(ls1.head->data <= ls2.head->data)
{
InsertLast(ls, ls1.head->data);
RemoveFirst(ls1);
}
else
{
InsertLast(ls, ls2.head->data);
RemoveFirst(ls2);
}
ls = MergeSort(ls1, ls2);
return ls;
}
这是我的主要
int main()
{
DoublyLinkedList ls1,ls2,ls;
Initial(ls1);
Initial(ls2);
Initial(ls);
InsertLast(ls1, 9);
InsertLast(ls1, 5);
InsertLast(ls1, 1);
InsertLast(ls1, 4);
InsertLast(ls1, 3);
InsertLast(ls2, 12);
InsertLast(ls2, 6);
InsertLast(ls2, 2);
ls=MergeSort(ls1, ls2);
Print(ls);
return 0;
}
输出:9 5 1 4 3 12 6 2
在查阅了评论后,我修复了该功能。重新使用 QSort 对给定列表进行排序
DoublyLinkedList MergeSort(DoublyLinkedList &ls1, DoublyLinkedList &ls2)
{
DoublyLinkedList ls;
Initial(ls);
if(isEmpty(ls1))
return ls2;
else if(isEmpty(ls2))
return ls1;
QuickSort(ls1);
QuickSort(ls2);
Node *p = ls1.head;
Node *q = ls2.head;
while(p != NULL && q != NULL)
{
if(p->data <= q->data)
{
InsertLast(ls, p->data);
p = p->next;
}
else
{
InsertLast(ls, q->data);
q = q->next;
}
}
while(p != NULL)
{
InsertLast(ls, p->data);
p = p->next;
}
while(q != NULL)
{
InsertLast(ls, q->data);
q = q->next;
}
return ls;
}
这是我的子函数(InsertLast)
void InsertLast(DoublyLinkedList &ls, int data)
{
Node *p = CreateNode(data);
if(p == NULL)
return;
if(isEmpty(ls))
{
ls.head = ls.tail = p;
}
else
{
ls.tail->next = p;
p->prev = ls.tail;
ls.tail = p;
}
}
如何合并 2 个给定的 DList 而不必先对它们进行排序? 当我在屏幕上显示时,我的排序功能似乎不起作用(它不合并项目)
DoublyLinkedList MergeSort(DoublyLinkedList &ls1, DoublyLinkedList &ls2)
{
DoublyLinkedList ls;
Initial(ls);
if(isEmpty(ls1))
return ls2;
if(isEmpty(ls2))
return ls1;
if(ls1.head->data <= ls2.head->data)
{
InsertLast(ls, ls1.head->data);
RemoveFirst(ls1);
}
else
{
InsertLast(ls, ls2.head->data);
RemoveFirst(ls2);
}
ls = MergeSort(ls1, ls2);
return ls;
}
这是我的主要
int main()
{
DoublyLinkedList ls1,ls2,ls;
Initial(ls1);
Initial(ls2);
Initial(ls);
InsertLast(ls1, 9);
InsertLast(ls1, 5);
InsertLast(ls1, 1);
InsertLast(ls1, 4);
InsertLast(ls1, 3);
InsertLast(ls2, 12);
InsertLast(ls2, 6);
InsertLast(ls2, 2);
ls=MergeSort(ls1, ls2);
Print(ls);
return 0;
}
输出:9 5 1 4 3 12 6 2
在查阅了评论后,我修复了该功能。重新使用 QSort 对给定列表进行排序
DoublyLinkedList MergeSort(DoublyLinkedList &ls1, DoublyLinkedList &ls2)
{
DoublyLinkedList ls;
Initial(ls);
if(isEmpty(ls1))
return ls2;
else if(isEmpty(ls2))
return ls1;
QuickSort(ls1);
QuickSort(ls2);
Node *p = ls1.head;
Node *q = ls2.head;
while(p != NULL && q != NULL)
{
if(p->data <= q->data)
{
InsertLast(ls, p->data);
p = p->next;
}
else
{
InsertLast(ls, q->data);
q = q->next;
}
}
while(p != NULL)
{
InsertLast(ls, p->data);
p = p->next;
}
while(q != NULL)
{
InsertLast(ls, q->data);
q = q->next;
}
return ls;
}
这是我的子函数(InsertLast)
void InsertLast(DoublyLinkedList &ls, int data)
{
Node *p = CreateNode(data);
if(p == NULL)
return;
if(isEmpty(ls))
{
ls.head = ls.tail = p;
}
else
{
ls.tail->next = p;
p->prev = ls.tail;
ls.tail = p;
}
}