Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में डौबली लिंक्ड लिस्ट के लिए मर्ज सॉर्ट

समस्या कथन

एक डौबली लिंक्ड लिस्ट दी गई है। इसे मर्ज सॉर्ट एल्गोरिदम का उपयोग करके सॉर्ट करें।

List: 10→20→8→17→5→13→4
Sorted list: 4→5→8→10→13→17→20

एल्गोरिदम

1. यदि हेड NULL है या लिस्ट में केवल एक तत्व है तो लिस्ट लौटाएं
2. मूल लिस्ट को 2 भागों में विभाजित करके दो लिस्ट बनाएं
3. लिस्ट के पहले और दूसरे भाग को सॉर्ट करें
4. दोनों सॉर्ट की गई लिस्ट को मर्ज करें

C++ उदाहरण

#include <iostream>
#include <new>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;

struct Node {
    int data;
    struct Node *next, *prev;
};

Node* createList(int *arr, int n) {
    Node *head, *p, *q;
    p = head = new Node;
    head->data = arr[0];
    head->prev = head->next = NULL;
    for (int i = 1; i < n; ++i) {
        q = new Node;
        q->data = arr[i];
        q->prev = p;
        q->next = NULL;
        p->next = q;
        p = q;
    }
    return head;
}

void displayList(Node *head) {
    while (head != NULL) {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}

Node* mergeSortedLists(Node *head1, Node *head2) {
    if (!head1) return head2;
    if (!head2) return head1;
    if (head1->data < head2->data) {
        head1->next = mergeSortedLists(head1->next, head2);
        head1->next->prev = head1;
        head1->prev = NULL;
        return head1;
    } else {
        head2->next = mergeSortedLists(head1, head2->next);
        head2->next->prev = head2;
        head2->prev = NULL;
        return head2;
    }
}

void splitList(Node *src, Node **fRef, Node **bRef) {
    Node *fast = src->next, *slow = src;
    while (fast != NULL) {
        fast = fast->next;
        if (fast != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
    }
    *fRef = src;
    *bRef = slow->next;
    slow->next = NULL;
}

void mergeSort(Node **head) {
    Node *p = *head, *a = NULL, *b = NULL;
    if (!p || !p->next) return;
    splitList(p, &a, &b);
    mergeSort(&a);
    mergeSort(&b);
    *head = mergeSortedLists(a, b);
}

int main() {
    int arr[] = {10, 20, 8, 17, 5, 13, 4};
    Node *head = createList(arr, SIZE(arr));
    cout << "Unsorted list: " << endl;
    displayList(head);
    mergeSort(&head);
    cout << "Final sorted list: " << endl;
    displayList(head);
    return 0;
}

आउटपुट

Unsorted list: 10 20 8 17 5 13 4
Final sorted list: 4 5 8 10 13 17 20
  1. C++ में मल्टीलेवल लिंक्ड सूची को समतल करना C++ में मल्टीलेवल लिंक्ड सूची को समतल करना

    इस समस्या में, हमें एक मल्टीलेवल लिंक्ड सूची दी गई है। हमारा कार्य मल्टीलेवल लिंक्ड सूची को समतल करने के लिए एक प्रोग्राम बनाना है। समतल करने का ऑपरेशन इस तरह से किया जाता है कि पहले स्तर के नोड्स पहले लिंक्ड सूची में आएंगे और फिर दूसरे स्तर के नोड्स आएंगे। मल्टीलेवल लिंक्ड सूची एक बहुआयामी डेटा संर

  1. C++ में डबल लिंक्ड सर्कुलर सूचियाँ C++ में डबल लिंक्ड सर्कुलर सूचियाँ

    सर्कुलर लिंक्ड सूची लिंक्ड सूची का एक रूपांतर है जिसमें पहला तत्व अंतिम तत्व की ओर इशारा करता है और अंतिम तत्व पहले तत्व की ओर इशारा करता है। सिंगली लिंक्ड सूची और डबल लिंक्ड सूची दोनों को सर्कुलर लिंक्ड सूची में बनाया जा सकता है। डबल लिंक्ड सूची में, अंतिम नोड का अगला पॉइंटर पहले नोड की ओर इशारा

  1. C++ में डबल लिंक्ड लिस्ट का उपयोग करके प्राथमिकता कतार C++ में डबल लिंक्ड लिस्ट का उपयोग करके प्राथमिकता कतार

    हमें डेटा और प्राथमिकता एक पूर्णांक मान के रूप में दी गई है और कार्य दिए गए प्राथमिकता के अनुसार डबल लिंक्ड लिस्ट बनाना और परिणाम प्रदर्शित करना है।कतार एक FIFO डेटा संरचना है जिसमें पहले डाला गया तत्व सबसे पहले हटाया जाता है। प्राथमिकता कतार एक प्रकार की कतार है जिसमें तत्वों को प्राथमिकता के आधार