ผสานการเรียงลำดับสำหรับรายการที่เชื่อมโยงเป็นทวีคูณโดยใช้ C++

คำชี้แจงปัญหา

รับรายการที่เชื่อมโยงเป็นสองเท่า จัดเรียงโดยใช้อัลกอริธึมการจัดเรียงแบบผสาน

รายการ:10->20->8-17->5->13->4รายการที่เรียงลำดับ:4->5->8->10->13->17->20

อัลกอริทึม

<ก่อน>1. หาก head เป็น NULL หรือ list มีเพียงหนึ่งองค์ประกอบ ให้ส่งคืน list2 สร้างสองรายการโดยแบ่งรายการเดิมออกเป็น 2 ส่วน3. เรียงลำดับส่วนแรกและส่วนที่สองของ list4 รวมรายการที่เรียงลำดับทั้งสอง

ตัวอย่าง

#include #include #define SIZE(arr) (sizeof(arr) / sizeof(arr[0])) โดยใช้เนมสเปซ std;struct node { ข้อมูล int; โหนดโครงสร้าง *ถัดไป; โหนดโครงสร้าง *ก่อนหน้า;};โหนด *createList(int *arr, int n){ โหนด *หัว, *p, *q; p =หัว =โหนดใหม่; head->data =arr[0]; head->prev =NULL; head->next =NULL; สำหรับ (int i =1; i data =arr[i]; q->ก่อนหน้า =p; q->ถัดไป =NULL; p->ถัดไป =q; p =q; } return head;} void displayList(node *head){ while (head !=NULL) { cout <data <<" "; หัว =หัว -> ถัดไป; } cout <data data) { head1->next =mergeSortedLists(head1->next, head2); head1->next->prev =head1; head1->prev =NULL; กลับหัว1; } อื่น { head2->next =mergeSortedLists (head1, head2->next); head2->ถัดไป->ก่อนหน้า =head2; head2->ก่อนหน้า =NULL; กลับหัว2; }} โมฆะ splitList (โหนด * src, โหนด **fRef, โหนด ** bRef) { โหนด * เร็ว; โหนด *ช้า; ช้า =src; เร็ว =src->ถัดไป; ในขณะที่ (เร็ว !=NULL) { เร็ว =เร็ว->ถัดไป; ถ้า (เร็ว !=NULL) { ช้า =ช้า->ถัดไป; เร็ว =เร็ว -> ถัดไป; } } *fRef =src; *bRef =ช้า -> ถัดไป; ช้า -> ถัดไป =NULL;} โมฆะ mergeSort (โหนด ** หัว) { โหนด * p =* หัว; โหนด *a =NULL; โหนด *b =NULL; ถ้า (p ==NULL || p->next ==NULL) { return; } splitList(p, &a, &b); mergeSort(&a); mergeSort(&b); *head =mergeSortedLists(a, b);}int main(){ int arr[] ={10, 20, 8, 17, 5, 13, 4}; โหนด * หัว; หัว =createList(arr, SIZE(arr)); cout <<"รายการที่ไม่เรียงลำดับ:" < ผลลัพธ์
 
 เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้ -
 รายการที่ยังไม่ได้เรียงลำดับ:10 20 8 17 5 13 4 รายการที่เรียงลำดับสุดท้าย:4 5 8 10 13 17 20