Холбогдсон хоёр жагсаалтын нэгдэл ба огтлолцол  


Хэцүү байдлын түвшин Дунд
Байнга асуудаг 24 * 7 инновацийн лаборатори Accolite Амазоны Flipkart Комли медиа Microsoft- Такси4 VMware Walmart лабораторууд
Хаш Холбогдсон жагсаалт Ангилах

Хоёр өгсөн холбоотой жагсаалт, одоо байгаа жагсаалтын элементүүдийн нэгдэл ба огтлолцлыг олж авахын тулд өөр хоёр холбоотой жагсаалтыг үүсгээрэй.

Жишээ нь  

Орц:

Жагсаалт1: 5 → 9 → 10 → 12 → 14

Жагсаалт2: 3 → 5 → 9 → 14 → 21

Үр дүн:

Уулзварын жагсаалт: 14 → 9 → 5

Холбооны жагсаалт: 21 → 14 → 12 → 10 → 9 → 5 → 3

Тайлбар: Холбогдсон жагсаалт бол зангилааны цуглуулга юм. Бүх зангилаа дарааллаар холбогдсон байдаг. Бид авах боломжтой огтлолцол болон холбоо хэд хэдэн аргыг ашиглан холбосон хоёр жагсаалтын. Гэхдээ энэ тохиолдолд ашиглах үр дүнтэй арга бол эхлээд холбосон жагсаалтыг хоёуланг нь эрэмбэл нэгтгэх холбосон жагсаалтын огтлолцол ба нэгдлийг авахын тулд эрэмбэлэгдсэн холбосон жагсаалтыг хоёуланг нь шугаман байдлаар шалгана. Холбогдсон жагсаалтыг эрэмбэлэхэд тааруухан гүйцэтгэдэг бусад алгоритмаас илүү нэгтгэх ангиллыг ихэвчлэн илүүд үздэг.

Алгоритм  

  1. Жагсаалтын толгой ба дараагийн заагчийг зарлан холбосон жагсаалтыг үүсгээрэй.
  2. Insert func ашиглан элементүүдийг жагсаалтад хоёуланд нь оруулна уу.
  3. Холбогдсон жагсаалтыг хоёуланг нь нэгтгэх эрэмбийн алгоритм ашиглан эрэмбэл.
  4. Эцэст нь эрэмбэлэгдсэн жагсаалтыг хоёуланг нь шугаман байдлаар сканнердаж жагсаалтын нэгдэл ба огтлолцлыг авна.

Тайлбар  

Нэгдүгээрт, бид холбосон жагсаалтаа үүсгэж болохын тулд So програм дээрээ Node анги үүсгэж зангилаа үүсгэдэг. Манай хөтөлбөрт бид хоёр дараалалгүй холбоосын жагсаалтыг үүсгэдэг. Үүний дараа бид эрэмбэлэх алгоритмаа ашиглан холбосон жагсаалтыг хоёуланг нь эрэмбэлээд дараа нь холбосон жагсаалтынхаа нэгдэл ба огтлолцлыг авахын тулд функцийг бий болгодог. Холбогдсон жагсаалтыг хоёуланг нь эрэмбэлсний дараа холбосон жагсаалтын нэгдэл, огтлолцлыг олж авахын тулд тэдгээрийг шугаман байдлаар хайхад хялбар болно.

мөн үзнэ үү
Толгой заагчгүйгээр холбосон жагсаалтаас зангилаа устгах

Жишээлбэл, 'list1' ба 'list2' гэсэн хоёр холбоотой жагсаалтыг үүсгээд хоёуланд нь элементүүдийг java эсвэл Node дээр манай Node класс оруулна уу. c ++ дахь бүтэц. Үүний дараа бид холбосон хоёр жагсаалтын толгойг аргумент болгон авсан "get_union" функцийг ашиглан холбосон жагсаалтуудын жагсаалт1 ба list2-ийн нэгдлийг олж, нэгдлийг хадгалах түр зуурын жагсаалтыг гаргадаг. хоёр жагсаалтын тус бүр дэх элемент while давталт first while давталтад эхний жагсаалтын элементийг оруулах. жагсаалт, жагсаалтын 2 элементийг түр зуур оруулах. Хэрэв тэдгээр нь жагсаалтад ороогүй бол жагсаалтыг оруулаад эцэст нь холбосон жагсаалтад хоёуланд нь түгээмэл тохиолддог элементүүдээр жагсаалтыг гаргана. Үүний дараа бид холбосон хоёр жагсаалтын огтлолцлыг олохын тулд 'авах огтлолцол' аргыг ашиглана. while давталт холбосон жагсаалтын аль алинд нь нийтлэг тохиолдолд л холбосон жагсаалтын элементийг оруулах.

Хэрэгжүүлэх  

Хоёр холбосон жагсаалтын нэгдэл ба огтлолцолд зориулсан C ++ програм

#include<iostream>
#include<stdlib.h>
using namespace std;

struct Node
{
    int value;
    struct Node* next;
};

void insert(struct Node** head, int new_value)
{
    struct Node* NewNode = (struct Node*) malloc(sizeof(struct Node));

    NewNode->value = new_value;

    NewNode->next = (*head);

    (*head) = NewNode;
}

void Front_Back(struct Node* source, struct Node** front, struct Node** back)
{
    struct Node* fast;
    struct Node* slow;
    if (source==NULL || source->next==NULL)
    {
        *front = source;
        *back = NULL;
    }
    else
    {
        slow = source;
        fast = source->next;

        while (fast != NULL)
        {
            fast = fast->next;
            if (fast != NULL)
            {
                slow = slow->next;
                fast = fast->next;
            }
        }

        *front = source;
        *back = slow->next;
        slow->next = NULL;
    }
}

struct Node* Sort_merge(struct Node* fst, struct Node* sec)
{
    struct Node* result = NULL;

    if (fst == NULL)
        return(sec);
    else if (sec==NULL)
        return(fst);

    if (fst->value <= sec->value)
    {
        result = fst;
        result->next = Sort_merge(fst->next, sec);
    }
    else
    {
        result = sec;
        result->next = Sort_merge(fst, sec->next);
    }
    return(result);
}

void Sort(struct Node** head)
{
    struct Node *head_node= *head;
    struct Node *a, *b;

    if ((head_node == NULL) || (head_node->next == NULL))
        return;

    Front_Back(head_node, &a, &b);

    Sort(&a);
    Sort(&b);

    *head = Sort_merge(a, b);
}

struct Node *get_Union(struct Node *head1, struct Node *head2)
{
    struct Node *result = NULL;
    struct Node *t1 = head1, *t2 = head2;

    while (t1 != NULL && t2 != NULL)
    {
        if (t1->value < t2->value)
        {
            insert(&result, t1->value);
            t1 = t1->next;
        }

        else if (t1->value>t2->value)
        {
            insert(&result, t2->value);
            t2 = t2->next;
        }
        else
        {
            insert(&result, t2->value);
            t1 = t1->next;
            t2 = t2->next;
        }
    }

    while (t1 != NULL)
    {
        insert(&result, t1->value);
        t1 = t1->next;
    }
    while (t2 != NULL)
    {
        insert(&result, t2->value);
        t2 = t2->next;
    }

    return result;
}

struct Node *get_Intersection(struct Node *head1, struct Node *head2)
{
    struct Node *result = NULL;
    struct Node *t1 = head1, *t2 = head2;

    while (t1 != NULL && t2 != NULL)
    {
        if (t1->value < t2->value)
            t1 = t1->next;

        else if (t1->value > t2->value)
            t2 = t2->next;

        else
        {
            insert(&result, t2->value);

            t1 = t1->next;
            t2 = t2->next;
        }
    }

    return result;
}

void printList (struct Node *node)
{
    while (node != NULL)
    {
        cout<<node->value << " ";
        node = node->next;
    }
    cout<<endl;
}

int main()
{
    struct Node* head1 = NULL;
    struct Node* head2 = NULL;
    struct Node* intersection_list = NULL;
    struct Node* union_list = NULL;

    insert(&head1, 20);
    insert(&head1, 4);
    insert(&head1, 15);
    insert(&head1, 10);
    insert(&head1, 11);

    insert(&head2, 10);
    insert(&head2, 2);
    insert(&head2, 4);
    insert(&head2, 8);

    Sort(&head1);
    Sort(&head2);

    intersection_list = get_Intersection(head1, head2);
    union_list = get_Union(head1, head2);

    cout<<"First list is \n";
    printList(head1);

    cout<<"\nSecond list is \n";
    printList(head2);

    cout<<"\nIntersection list is \n";
    printList(intersection_list);

    cout<<"\nUnion list is \n";
    printList(union_list);

    return 0;
}
First list is
4 10 11 15 20

Second list is
2 4 8 10

Intersection list is
10 4

Union list is
20 15 11 10 8 4 2

Хоёр холбосон жагсаалтын нэгдэл ба огтлолцолд зориулсан Java програм

class Solution1
{
    Node head;


    class Node
    {
        int data;
        Node next;
        Node(int d)
        {
            data = d;
            next = null;
        }
    }


    void get_union(Node hd1, Node hd2)
    {
        Node t1 = hd1, t2 = hd2;


        while (t1 != null)
        {
            insert(t1.data);
            t1 = t1.next;
        }


        while (t2 != null)
        {
            if (!is_Present(head, t2.data))
                insert(t2.data);
            t2 = t2.next;
        }
    }

    void get_intrSection(Node hd1, Node hd2)
    {
        Node rst = null;
        Node t1 = hd1;


        while (t1 != null)
        {
            if (is_Present(hd2, t1.data))
                insert(t1.data);
            t1 = t1.next;
        }
    }


    void printList()
    {
        Node temp = head;
        while (temp != null)
        {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println();
    }


    void insert(int new_data)
    {

        Node new_node = new Node(new_data);


        new_node.next = head;


        head = new_node;
    }


    boolean is_Present(Node head, int data)
    {
        Node t = head;
        while (t != null)
        {
            if (t.data == data)
                return true;
            t = t.next;
        }
        return false;
    }


    public static void main(String args[])
    {
        Solution1 llist1 = new Solution1();
        Solution1 llist2 = new Solution1();
        Solution1 unin = new Solution1();
        Solution1 intersecn = new Solution1();


        llist1.insert(20);
        llist1.insert(4);
        llist1.insert(15);
        llist1.insert(10);


        llist2.insert(10);
        llist2.insert(2);
        llist2.insert(4);
        llist2.insert(8);

        intersecn.get_intrSection(llist1.head, llist2.head);
        unin.get_union(llist1.head, llist2.head);

        System.out.println("First List is");
        llist1.printList();

        System.out.println("Second List is");
        llist2.printList();

        System.out.println("Intersection List is");
        intersecn.printList();

        System.out.println("Union List is");
        unin.printList();
    }
}
First List is
10 15 4 20
Second List is
8 4 2 10
Intersection List is
4 10
Union List is
2 8 20 4 15 10

Хоёр холбосон жагсаалтын нэгдэл ба огтлолцлын нарийн төвөгтэй байдлын шинжилгээ  

Цаг хугацааны нарийн төвөгтэй байдал

 O (m + n) хаана "М" болон "N" нь эхний ба хоёр дахь жагсаалтад тусгагдсан элементүүдийн тоо юм.

мөн үзнэ үү
Өгөгдсөн холбосон жагсаалтын төгсгөлөөс Nth зангилааг устгана уу

Сансрын нарийн төвөгтэй байдал

 O (m + n) хаана "М" болон "N" нь эхний ба хоёр дахь жагсаалтад тусгагдсан элементүүдийн тоо юм.