Рубрики

Свести многоуровневый связанный список

Связанный список

Учитывая связанный список, где в дополнение к следующему указателю каждый узел имеет дочерний указатель, который может указывать или не указывать на отдельный список. Эти дочерние списки могут иметь одного или нескольких собственных дочерних элементов и т. Д., Чтобы создать многоуровневую структуру данных, как показано на рисунке ниже. Вам предоставляется глава первого уровня списка. Выровняйте список так, чтобы все узлы отображались в одноуровневом связанном списке. Вы должны сгладить список так, чтобы все узлы на первом уровне были первыми, затем узлы второго уровня и так далее.

Каждый узел является структурой C со следующим определением.

struct List

{

    int data;

    struct List *next;

    struct List *child;

};

Приведенный выше список следует преобразовать в 10-> 5-> 12-> 7-> 11-> 4-> 20-> 13-> 17-> 6-> 2-> 16-> 9-> 8-> 3 -> 19-> 15

Проблема ясно говорит о том, что нам нужно выравнивать уровень за уровнем. Идея решения состоит в том, что мы начинаем с первого уровня, обрабатываем все узлы один за другим, если у узла есть дочерний элемент, то мы добавляем дочерний элемент в конец списка, в противном случае мы ничего не делаем. После обработки первого уровня все узлы следующего уровня будут добавлены после первого уровня. Тот же процесс выполняется для добавленных узлов.

1) Take "cur" pointer, which will point to head of the fist level of the list
2) Take "tail" pointer, which will point to end of the first level of the list
3) Repeat the below procedure while "curr" is not NULL.
    I) if current node has a child then
    a) append this new child list to the "tail"
        tail->next = cur->child
    b) find the last node of new child list and update "tail"
        tmp = cur->child;
        while (tmp->next != NULL)
            tmp = tmp->next;
        tail = tmp;
    II) move to the next node. i.e. cur = cur->next

Ниже приведена реализация вышеуказанного алгоритма.

C ++

// C ++ Программа для выравнивания списка с
// Следующие и дочерние указатели
#include <bits/stdc++.h>

using namespace std;

  
// Макрос для поиска количества элементов в массиве
#define SIZE(arr) (sizeof(arr)/sizeof(arr[0])) 

  
// Узел связанного списка содержит данные,
// следующий указатель и дочерний указатель

class Node 

{ 

    public:

    int data; 

    Node *next; 

    Node *child; 

}; 

  
// Утилита для создания связанного списка
// с n узлами. Данные узлов взяты
// из обр. []. Все дочерние указатели установлены в NULL

Node *createList(int *arr, int n) 

{ 

    Node *head = NULL; 

    Node *p; 

  

    int i; 

    for (i = 0; i < n; ++i) 

    { 

        if (head == NULL) 

            head = p = new Node();

        else 

        { 

            p->next = new Node();

            p = p->next; 

        } 

        p->data = arr[i]; 

        p->next = p->child = NULL; 

    } 

    return head; 

} 

  
// Утилита для печати
// все узлы связанного списка

void printList(Node *head) 

{ 

    while (head != NULL) 

    { 

        cout << head->data << " "; 

        head = head->next; 

    } 

    cout<<endl; 

} 

  
// Эта функция создает ввод
// список. Созданный список такой же
// как показано на рисунке выше

Node *createList(void) 

{ 

    int arr1[] = {10, 5, 12, 7, 11}; 

    int arr2[] = {4, 20, 13}; 

    int arr3[] = {17, 6}; 

    int arr4[] = {9, 8}; 

    int arr5[] = {19, 15}; 

    int arr6[] = {2}; 

    int arr7[] = {16}; 

    int arr8[] = {3}; 

  

    / * создать 8 связанных списков * /

    Node *head1 = createList(arr1, SIZE(arr1)); 

    Node *head2 = createList(arr2, SIZE(arr2)); 

    Node *head3 = createList(arr3, SIZE(arr3)); 

    Node *head4 = createList(arr4, SIZE(arr4)); 

    Node *head5 = createList(arr5, SIZE(arr5)); 

    Node *head6 = createList(arr6, SIZE(arr6)); 

    Node *head7 = createList(arr7, SIZE(arr7)); 

    Node *head8 = createList(arr8, SIZE(arr8)); 

  

  

    / * изменить дочерние указатели на

    создать список, показанный выше * /

    head1->child = head2; 

    head1->next->next->next->child = head3; 

    head3->child = head4; 

    head4->child = head5; 

    head2->next->child = head6; 

    head2->next->next->child = head7; 

    head7->child = head8; 

  

  

    / * Вернуть указатель головы первого

    связанный список. Обратите внимание, что все узлы

    достижимы с головы1 * /

    return head1; 

} 

  
/ * Основная функция, которая выравнивает
многоуровневый связанный список * /

void flattenList(Node *head) 

{ 

    /*Базовый вариант*/

    if (head == NULL) 

    return; 

  

    Node *tmp; 

  

    / * Найти хвостовой узел связанного списка первого уровня * /

    Node *tail = head; 

    while (tail->next != NULL) 

        tail = tail->next; 

  

    // Один за другим пройти через все узлы первого уровня

    // связанный список, пока мы не достигнем хвостового узла

    Node *cur = head; 

    while (cur != tail) 

    { 

        // Если текущий узел имеет дочерний

        if (cur->child) 

        { 

            // затем добавляем дочерний элемент в конец текущего списка

            tail->next = cur->child; 

  

            // и обновляем хвост до нового последнего узла

            tmp = cur->child; 

            while (tmp->next) 

                tmp = tmp->next; 

            tail = tmp; 

        } 

  

        // Изменить текущий узел

        cur = cur->next; 

    } 

} 

  
// Код драйвера

int main(void) 

{ 

    Node *head = NULL; 

    head = createList(); 

    flattenList(head); 

    printList(head); 

    return 0; 

} 

  
// Этот код предоставлен rathbhupendra

С

// Программа для выравнивания списка со следующими и дочерними указателями
#include <stdio.h>
#include <stdlib.h>

  
// Макрос для поиска количества элементов в массиве
#define SIZE(arr) (sizeof(arr)/sizeof(arr[0]))

  
// Узел связанного списка имеет данные, следующий указатель и дочерний указатель

struct Node

{

    int data;

    struct Node *next;

    struct Node *child;

};

  
// Вспомогательная функция для создания связанного списка с n узлами. Данные
// узлов берется из arr []. Все дочерние указатели установлены в NULL

struct Node *createList(int *arr, int n)

{

    struct Node *head = NULL;

    struct Node *p;

  

    int i;

    for (i = 0; i < n; ++i) {

        if (head == NULL)

            head = p = (struct Node *)malloc(sizeof(*p));

        else {

            p->next = (struct Node *)malloc(sizeof(*p));

            p = p->next;

        }

        p->data = arr[i];

        p->next = p->child = NULL;

    }

    return head;

}

  
// Утилита для печати всех узлов связанного списка

void printList(struct Node *head)

{

    while (head != NULL) {

        printf("%d ", head->data);

        head = head->next;

    }

    printf("\n");

}

  
// Эта функция создает список ввода. Созданный список такой же
// как показано на рисунке выше

struct Node *createList(void)

{

    int arr1[] = {10, 5, 12, 7, 11};

    int arr2[] = {4, 20, 13};

    int arr3[] = {17, 6};

    int arr4[] = {9, 8};

    int arr5[] = {19, 15};

    int arr6[] = {2};

    int arr7[] = {16};

    int arr8[] = {3};

  

    / * создать 8 связанных списков * /

    struct Node *head1 = createList(arr1, SIZE(arr1));

    struct Node *head2 = createList(arr2, SIZE(arr2));

    struct Node *head3 = createList(arr3, SIZE(arr3));

    struct Node *head4 = createList(arr4, SIZE(arr4));

    struct Node *head5 = createList(arr5, SIZE(arr5));

    struct Node *head6 = createList(arr6, SIZE(arr6));

    struct Node *head7 = createList(arr7, SIZE(arr7));

    struct Node *head8 = createList(arr8, SIZE(arr8));

  

  

    / * изменить дочерние указатели, чтобы создать список, показанный выше * /

    head1->child = head2;

    head1->next->next->next->child = head3;

    head3->child = head4;

    head4->child = head5;

    head2->next->child = head6;

    head2->next->next->child = head7;

    head7->child = head8;

  

  

    / * Вернуть указатель головы первого связанного списка. Обратите внимание, что все узлы

       достижимы с головы1 * /

    return head1;

}

  
/ * Основная функция, которая выравнивает многоуровневый связанный список * /

void flattenList(struct Node *head)

{

    /*Базовый вариант*/

    if (head == NULL)

       return;

  

    struct Node *tmp;

  

    / * Найти хвостовой узел связанного списка первого уровня * /

    struct Node *tail = head;

    while (tail->next != NULL)

        tail = tail->next;

  

    // Один за другим пройти через все узлы первого уровня

    // связанный список, пока мы не достигнем хвостового узла

    struct Node *cur = head;

    while (cur != tail)

    {

        // Если текущий узел имеет дочерний

        if (cur->child)

        {

            // затем добавляем дочерний элемент в конец текущего списка

            tail->next = cur->child;

  

            // и обновляем хвост до нового последнего узла

            tmp = cur->child;

            while (tmp->next)

                tmp = tmp->next;

            tail = tmp;

        }

  

        // Изменить текущий узел

        cur = cur->next;

    }

}

  
// Программа драйвера для проверки вышеуказанных функций

int main(void)

{

    struct Node *head = NULL;

    head = createList();

    flattenList(head);

    printList(head);

    return 0;

}

Джава

// Java-программа для выравнивания связанного списка с указателями next и child

  

class LinkedList {

      

    static Node head;

      

    class Node {

          

        int data;

        Node next, child;

          

        Node(int d) {

            data = d;

            next = child = null;

        }

    }

  

    // Вспомогательная функция для создания связанного списка с n узлами. Данные

    // узлов берется из arr []. Все дочерние указатели установлены в NULL

    Node createList(int arr[], int n) {

        Node node = null;

        Node p = null;

          

        int i;

        for (i = 0; i < n; ++i) {

            if (node == null) {

                node = p = new Node(arr[i]);

            } else {

                p.next = new Node(arr[i]);

                p = p.next;

            }

            p.next = p.child = null;

        }

        return node;

    }

  

    // Утилита для печати всех узлов связанного списка

    void printList(Node node) {

        while (node != null) {

            System.out.print(node.data + " ");

            node = node.next;

        }

        System.out.println("");

    }

      

    Node createList() {

        int arr1[] = new int[]{10, 5, 12, 7, 11};

        int arr2[] = new int[]{4, 20, 13};

        int arr3[] = new int[]{17, 6};

        int arr4[] = new int[]{9, 8};

        int arr5[] = new int[]{19, 15};

        int arr6[] = new int[]{2};

        int arr7[] = new int[]{16};

        int arr8[] = new int[]{3};

  

        / * создать 8 связанных списков * /

        Node head1 = createList(arr1, arr1.length);

        Node head2 = createList(arr2, arr2.length);

        Node head3 = createList(arr3, arr3.length);

        Node head4 = createList(arr4, arr4.length);

        Node head5 = createList(arr5, arr5.length);

        Node head6 = createList(arr6, arr6.length);

        Node head7 = createList(arr7, arr7.length);

        Node head8 = createList(arr8, arr8.length);

  

        / * изменить дочерние указатели, чтобы создать список, показанный выше * /

        head1.child = head2;

        head1.next.next.next.child = head3;

        head3.child = head4;

        head4.child = head5;

        head2.next.child = head6;

        head2.next.next.child = head7;

        head7.child = head8;

  

        / * Вернуть указатель головы первого связанного списка. Обратите внимание, что все узлы

         достижимы с головы1 * /

        return head1;

    }

  

    / * Основная функция, которая выравнивает многоуровневый связанный список * /

    void flattenList(Node node) {

          

        /*Базовый вариант*/

        if (node == null) {

            return;

        }

          

        Node tmp = null;

  

        / * Найти хвостовой узел связанного списка первого уровня * /

        Node tail = node;

        while (tail.next != null) {

            tail = tail.next;

        }

  

        // Один за другим пройти через все узлы первого уровня

        // связанный список, пока мы не достигнем хвостового узла

        Node cur = node;

        while (cur != tail) {

  

            // Если текущий узел имеет дочерний

            if (cur.child != null) {

  

                // затем добавляем дочерний элемент в конец текущего списка

                tail.next = cur.child;

  

                // и обновляем хвост до нового последнего узла

                tmp = cur.child;

                while (tmp.next != null) {

                    tmp = tmp.next;

                }

                tail = tmp;

            }

  

            // Изменить текущий узел

            cur = cur.next;

        }

    }

      

    public static void main(String[] args) {

        LinkedList list = new LinkedList();

        head = list.createList();

        list.flattenList(head);

        list.printList(head);

    }

}

  
// Этот код предоставлен Mayank Jaiswal

python3

# Python3 Программа для выравнивания списка
# Следующие и дочерние указатели

  
# Узел связанного списка содержит данные,
# следующий указатель и дочерний указатель

class Node:

    def __init__(self, data):

        self.data = data

        self.next = None

        self.child = None

  
# Возвратный узел

def newNode(data):

    return Node(data) 

  
# Основная функция, которая выравнивает
# многоуровневый связанный список

def flattenlist(head):

      

    # Базовый вариант

    if not head:

        return

      

    # Найти хвостовой узел связанного списка первого уровня

    temp = head

    while(temp.next != None):

        temp = temp.next

    currNode = head

      

    # Один за другим пройти через все узлы

    # связанного списка первого уровня

    # пока мы не достигнем хвостового узла

    while(currNode != temp):

          

        # Если текущий узел имеет дочерний

        if(currNode.child):

              

            # затем добавить ребенка

            # в конце текущего списка

            temp.next = currNode.child

              

            # и обновить хвост до нового последнего узла

            tmp = currNode.child

            while(tmp.next):

                tmp = tmp.next

            temp = tmp

              

        # Изменить текущий узел

        currNode = currNode.next

      
# Утилита для печати
# все узлы связанного списка

def printList(head): 

    if not head: 

        return

    while(head): 

        print("{}".format(head.data), end = " ") 

        head = head.next

  
# Код драйвера

if __name__=='__main__': 

      

    # Детский список 13

    child13 = newNode(16)

    child13.child = newNode(3)

      

    # Список детей из 10

    head1 = newNode(4)

    head1.next = newNode(20)

    head1.next.child = newNode(2) # Ребенок 20

    head1.next.next = newNode(13)

    head1.next.next.child = child13

      

    # Ребенок 9 лет

    child9 = newNode(19)

    child9.next = newNode(15)

  

    # Список детей 17

    child17 = newNode(9)

    child17.next = newNode(8)

    child17.child = child9

  

    # Список детей 7

    head2 = newNode(17)

    head2.next = newNode(6)

    head2.child = child17

      

    # Основной список

    head = newNode(10)

    head.child = head1

    head.next = newNode(5)

    head.next.next = newNode(12)

    head.next.next.next = newNode(7)

    head.next.next.next.child = head2

    head.next.next.next.next = newNode(11)

  

    flattenlist(head)

  

    print("\Flattened list is: ", end = "") 

    printList(head)

  
# Этот код предоставлен 0_hero

C #

// C # программа для выравнивания связанного списка
// со следующими и дочерними указателями

using System;

  

public class LinkedList

{

    static Node head;

      

    class Node 

    {

        public int data;

        public Node next, child;

          

        public Node(int d)

        {

            data = d;

            next = child = null;

        }

    }

  

    // Полезная функция для создания

    // связанный список с n узлами. Данные

    // узлов берется из arr [].

    // Все дочерние указатели установлены в NULL

    Node createList(int []arr, int n) 

    {

        Node node = null;

        Node p = null;

          

        int i;

        for (i = 0; i < n; ++i) 

        {

            if (node == null) 

            {

                node = p = new Node(arr[i]);

            } 

            else 

            {

                p.next = new Node(arr[i]);

                p = p.next;

            }

            p.next = p.child = null;

        }

        return node;

    }

  

    // Утилита для печати

    // все узлы связанного списка

    void printList(Node node)

    {

        while (node != null) 

        {

            Console.Write(node.data + " ");

            node = node.next;

        }

        Console.WriteLine("");

    }

      

    Node createList() 

    {

        int []arr1 = new int[]{10, 5, 12, 7, 11};

        int []arr2 = new int[]{4, 20, 13};

        int []arr3 = new int[]{17, 6};

        int []arr4 = new int[]{9, 8};

        int []arr5 = new int[]{19, 15};

        int []arr6 = new int[]{2};

        int []arr7 = new int[]{16};

        int []arr8 = new int[]{3};

  

        / * создать 8 связанных списков * /

        Node head1 = createList(arr1, arr1.Length);

        Node head2 = createList(arr2, arr2.Length);

        Node head3 = createList(arr3, arr3.Length);

        Node head4 = createList(arr4, arr4.Length);

        Node head5 = createList(arr5, arr5.Length);

        Node head6 = createList(arr6, arr6.Length);

        Node head7 = createList(arr7, arr7.Length);

        Node head8 = createList(arr8, arr8.Length);

  

        / * изменить дочерние указатели на

        создать список, показанный выше * /

        head1.child = head2;

        head1.next.next.next.child = head3;

        head3.child = head4;

        head4.child = head5;

        head2.next.child = head6;

        head2.next.next.child = head7;

        head7.child = head8;

  

        / * Вернуть указатель головы первого

        связанный список. Обратите внимание, что все узлы

         достижимы с головы1 * /

        return head1;

    }

  

    / * Основная функция, которая выравнивает

    многоуровневый связанный список * /

    void flattenList(Node node)

    {

          

        /*Базовый вариант*/

        if (node == null)

        {

            return;

        }

          

        Node tmp = null;

  

        / * Найти хвостовой узел первого

        список связанных уровней * /

        Node tail = node;

        while (tail.next != null) 

        {

            tail = tail.next;

        }

  

        // Один за другим пройти через

        // все узлы первого уровня

        // связанный список, пока мы не достигнем хвостового узла

        Node cur = node;

        while (cur != tail) 

        {

  

            // Если текущий узел имеет дочерний

            if (cur.child != null) 

            {

  

                // затем добавляем ребенка в

                // конец текущего списка

                tail.next = cur.child;

  

                // и обновляем хвост до нового последнего узла

                tmp = cur.child;

                while (tmp.next != null) 

                {

                    tmp = tmp.next;

                }

                tail = tmp;

            }

  

            // Изменить текущий узел

            cur = cur.next;

        }

    }

      

    // Код драйвера

    public static void Main() 

    {

        LinkedList list = new LinkedList();

        head = list.createList();

        list.flattenList(head);

        list.printList(head);

    }

}

  
/ * Этот код предоставлен PrinciRaj1992 * /


Выход:

10 5 12 7 11 4 20 13 17 6 2 16 9 8 3 19 15

Сложность времени: поскольку каждый узел посещается не более двух раз, сложность времени равна O (n), где n — количество узлов в данном связанном списке.

Эта статья составлена Нарендрой Кангралкар . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Свести многоуровневый связанный список

0.00 (0%) 0 votes