Рубрики

Сведение связанного списка

Дан связанный список, где каждый узел представляет связанный список и содержит два указателя его типа:
(i) Указатель на следующий узел в основном списке (мы называем его «правильный» указатель в приведенном ниже коде)
(ii) Указатель на связанный список, где этот узел является головным (мы называем его указателем «вниз» в приведенном ниже коде).
Все связанные списки отсортированы. Смотрите следующий пример

       5 -> 10 -> 19 -> 28
       |    |     |     |
       V    V     V     V
       7    20    22    35
       |          |     |
       V          V     V
       8          50    40
       |                |
       V                V
       30               45

Напишите функцию flatten (), чтобы свести списки в один связанный список. Выровненный связанный список также должен быть отсортирован. Например, для вышеприведенного списка ввода список вывода должен быть 5-> 7-> 8-> 10-> 19-> 20-> 22-> 28-> 30-> 35-> 40-> 45-> 50 ,

Идея состоит в том, чтобы использовать Merge () для сортировки слиянием для связанных списков. Мы используем merge () для объединения списков один за другим. Мы рекурсивно сливаем () текущий список с уже сплющенным списком.
Указатель вниз используется для связи узлов сплющенного списка.

Ниже приведены реализации C и Java.

C / C ++

// C программа для выравнивания связанного списка
#include <stdio.h>
#include <stdlib.h>

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

typedef struct Node

{

    int data;

    struct Node *right;

    struct Node *down;

} Node;

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

   связанного списка * /

void push (Node** head_ref, int new_data)

{

    / * выделить узел * /

    Node* new_node = (Node *) malloc(sizeof(Node));

    new_node->right = NULL;

  

    / * вставить данные * /

    new_node->data  = new_data;

  

    / * связать старый список с новым узлом * /

    new_node->down = (*head_ref);

  

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

    (*head_ref)    = new_node;

}

  
/ * Функция для печати узлов в плоском связанном списке * /

void printList(Node *node)

{

    while (node != NULL)

    {

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

        node = node->down;

    }

}

  
// Утилита для объединения двух отсортированных связанных списков
Node* merge( Node* a, Node* b )
{

    // Если первый список пуст, второй список является результатом

    if (a == NULL)

        return b;

  

    // Если второй список пуст, второй список является результатом

    if (b == NULL)

        return a;

  

    // Сравниваем данные членов головных узлов обоих списков

    // и поместим меньший в результат

    Node* result;

    if (a->data < b->data)

    {

        result = a;

        result->down = merge( a->down, b );

    }

    else

    {

        result = b;

        result->down = merge( a, b->down );

    }

  

    return result;

}

  
// Основная функция, которая выравнивает данный связанный список
Node* flatten (Node* root)
{

    // Базовые случаи

    if (root == NULL || root->right == NULL)

        return root;

  

    // Объединяем этот список со списком справа

    return merge( root, flatten(root->right) );

}

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

int main()

{

    Node* root = NULL;

  

    / * Давайте создадим следующий связанный список

       5 -> 10 -> 19 -> 28

       | | | |

       V V V V

       7 20 22 35

       | | |

       V V V

       8 50 40

       | |

       V V

       30 45

    * /

    push( &root, 30 );

    push( &root, 8 );

    push( &root, 7 );

    push( &root, 5 );

  

    push( &( root->right ), 20 );

    push( &( root->right ), 10 );

  

    push( &( root->right->right ), 50 );

    push( &( root->right->right ), 22 );

    push( &( root->right->right ), 19 );

  

    push( &( root->right->right->right ), 45 );

    push( &( root->right->right->right ), 40 );

    push( &( root->right->right->right ), 35 );

    push( &( root->right->right->right ), 20 );

  

    // Давайте сгладим список

    root = flatten(root);

  

    // Давайте распечатаем связанный список

    printList(root);

  

    return 0;

}

Джава

// Java-программа для выравнивания связанного списка

class LinkedList

{

    Node head;  // заголовок списка

  

    / * Узел связанного списка * /

    class Node

    {

        int data;

        Node right, down;

        Node(int data)

        {

            this.data = data;

            right = null;

            down = null;

        }

    }

  

    // Полезная функция для объединения двух отсортированных связанных списков

    Node merge(Node a, Node b)

    {

        // если первый связанный список пуст, то второй

        // ответ

        if (a == null)     return b;

  

        // если второй связанный список пуст, то первый

        // это результат

        if (b == null)      return a;

  

        // сравниваем данные членов двух связанных списков

        // и помещаем больший результат

        Node result;

  

        if (a.data < b.data)

        {

            result = a;

            result.down =  merge(a.down, b);

        }

  

        else

        {

            result = b;

            result.down = merge(a, b.down);

        }

  

        return result;

    }

  

    Node flatten(Node root)

    {

        // Базовые случаи

        if (root == null || root.right == null)

            return root;

  

        // повторить список справа

        root.right = flatten(root.right);

  

        // теперь объединяем

        root = merge(root, root.right);

  

        // вернуть корень

        // он будет в свою очередь слит с левым

        return root;

    }

  

    / * Служебная функция для вставки узла в начале

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

    Node push(Node head_ref, int data)

    {

        / * 1 & 2: выделить узел &

                  Введите данные * /

        Node new_node = new Node(data);

  

        / * 3. Сделать следующий новый узел в качестве головы * /

        new_node.down = head_ref;

  

        / * 4. Переместить голову, чтобы указать на новый узел * /

        head_ref = new_node;

  

        / * 5. вернуться, чтобы связать его обратно * /

        return head_ref;

    }

  

    void printList()

    {

        Node temp = head;

        while (temp != null)

        {

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

            temp = temp.down;

        }

        System.out.println();

    }

  

    / * Сушилка для тестирования вышеуказанных функций * /

    public static void main(String args[])

    {

        LinkedList L = new LinkedList();

  

        / * Давайте создадим следующий связанный список

            5 -> 10 -> 19 -> 28

            | | | |

            V V V V

            7 20 22 35

            | | |

            V V V

            8 50 40

            | |

            V V

            30 45

        * /

  

        L.head = L.push(L.head, 30);

        L.head = L.push(L.head, 8);

        L.head = L.push(L.head, 7);

        L.head = L.push(L.head, 5);

  

        L.head.right = L.push(L.head.right, 20);

        L.head.right = L.push(L.head.right, 10);

  

        L.head.right.right = L.push(L.head.right.right, 50);

        L.head.right.right = L.push(L.head.right.right, 22);

        L.head.right.right = L.push(L.head.right.right, 19);

  

        L.head.right.right.right = L.push(L.head.right.right.right, 45);

        L.head.right.right.right = L.push(L.head.right.right.right, 40);

        L.head.right.right.right = L.push(L.head.right.right.right, 35);

        L.head.right.right.right = L.push(L.head.right.right.right, 20);

  

        // сгладить список

        L.head = L.flatten(L.head);

  

        L.printList();

    }

} / * Этот код предоставлен Раджатом Мишрой * /


Выход:

5 7 8 10 19 20 20 22 30 35 40 45 50

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

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

Сведение связанного списка

0.00 (0%) 0 votes