Рубрики

Сортированная вставка для круглого связанного списка

Уровень сложности: Новичок
Напишите функцию C для вставки нового значения в отсортированный круговой связанный список (CLL). Например, если вход CLL следующий.

Алгоритм:
Выделите память для вновь вставленного узла и поместите данные во вновь выделенный узел. Пусть указатель на новый узел будет new_node. После выделения памяти следующие три случая, которые должны быть обработаны.

1) Linked List is empty:  
    a)  since new_node is the only node in CLL, make a self loop.      
          new_node->next = new_node;  
    b) change the head pointer to point to new node.
          *head_ref = new_node;
2) New node is to be inserted just before the head node:    
  (a) Find out the last node using a loop.
         while(current->next != *head_ref)
            current = current->next;
  (b) Change the next of last node. 
         current->next = new_node;
  (c) Change next of new node to point to head.
         new_node->next = *head_ref;
  (d) change the head pointer to point to new node.
         *head_ref = new_node;
3) New node is to be  inserted somewhere after the head: 
   (a) Locate the node after which new node is to be inserted.
         while ( current->next!= *head_ref && 
             current->next->data data)
         {   current = current->next;   }
   (b) Make next of new_node as next of the located pointer
         new_node->next = current->next;
   (c) Change the next of the located pointer
         current->next = new_node; 

C ++

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

using namespace std;

  
/ * структура для узла * /

class Node 

    public:

    int data; 

    Node *next; 

}; 

  
/ * функция для вставки new_node в список отсортированным способом.
Обратите внимание, что эта функция ожидает указатель на головной узел
так как это может изменить заголовок связанного списка ввода * /

void sortedInsert(Node** head_ref, Node* new_node) 

    Node* current = *head_ref; 

      

    // Случай 1 вышеупомянутого алгоритма

    if (current == NULL) 

    

        new_node->next = new_node; 

        *head_ref = new_node; 

    

      

    // Случай 2 вышеупомянутого алгоритма

    else if (current->data >= new_node->data) 

    

        / * Если значение меньше значения головы,

        нам нужно изменить следующий из последнего узла * /

        while(current->next != *head_ref) 

            current = current->next; 

        current->next = new_node; 

        new_node->next = *head_ref; 

        *head_ref = new_node; 

    

      

    // Случай 3 вышеуказанного алгоритма

    else

    

        / * Найдите узел до точки вставки * /

        while (current->next!= *head_ref && 

            current->next->data < new_node->data) 

        current = current->next; 

      

        new_node->next = current->next; 

        current->next = new_node; 

    

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

void printList(Node *start) 

    Node *temp; 

      

    if(start != NULL) 

    

        temp = start; 

        do

        cout<<temp->data<<" "

        temp = temp->next; 

        } while(temp != start); 

    

  
/ * Код водителя * /

int main() 

    int arr[] = {12, 56, 2, 11, 1, 90}; 

    int list_size, i; 

      

    / * начать с пустого связанного списка * /

    Node *start = NULL; 

    Node *temp; 

      

    / * Создать связанный список из массива arr [].

        Созданный связанный список будет 1-> 2-> 11-> 12-> 56-> 90 * /

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

    

        temp = new Node();

        temp->data = arr[i]; 

        sortedInsert(&start, temp); 

    

      

    printList(start); 

      

    return 0; 

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

С

#include<stdio.h>
#include<stdlib.h>

  
/ * структура для узла * /

struct Node

{

  int data;

  struct Node *next;

};

  
/ * функция для вставки new_node в список отсортированным способом.

   Обратите внимание, что эта функция ожидает указатель на головной узел

   так как это может изменить заголовок связанного списка ввода * /

void sortedInsert(struct Node** head_ref, struct Node* new_node)

{

  struct Node* current = *head_ref;

  

  // Случай 1 вышеупомянутого алгоритма

  if (current == NULL)

  {

     new_node->next = new_node;

     *head_ref = new_node;

  }

  

  // Случай 2 вышеупомянутого алгоритма

  else if (current->data >= new_node->data)

  {

    / * Если значение меньше значения головы,

      нам нужно изменить следующий из последнего узла * /

    while(current->next != *head_ref)

        current = current->next;

    current->next = new_node;

    new_node->next = *head_ref;

    *head_ref = new_node;

  }

  

  // Случай 3 вышеуказанного алгоритма

  else

  {

    / * Найдите узел до точки вставки * /

    while (current->next!= *head_ref && 

           current->next->data < new_node->data)

      current = current->next;

  

    new_node->next = current->next;

    current->next = new_node;

  }

}

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

void printList(struct Node *start)

{

  struct Node *temp;

  

  if(start != NULL)

  {

    temp = start;

    printf("\n");

    do {

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

      temp = temp->next;

    } while(temp != start);

  }

}

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

int main()

{

  int arr[] = {12, 56, 2, 11, 1, 90};

  int list_size, i;

  

  / * начать с пустого связанного списка * /

  struct Node *start = NULL;

  struct Node *temp;

  

  / * Создать связанный список из массива arr [].

    Созданный связанный список будет 1-> 2-> 11-> 12-> 56-> 90 * /

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

  {

    temp = (struct Node *)malloc(sizeof(struct Node));

    temp->data = arr[i];

    sortedInsert(&start, temp);

  }

  

  printList(start);

  

  return 0;

}

Джава

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

  

class Node

{

    int data;

    Node next;

  

    Node(int d)

    {

        data = d;

        next = null;

    }

}

  

class LinkedList

{

    Node head;

  

    // Конструктор

    LinkedList()   { head = null; }

  

    / * функция для вставки new_node в список отсортированным способом.

     Обратите внимание, что эта функция ожидает указатель на головной узел

     так как это может изменить заголовок связанного списка ввода * /

    void sortedInsert(Node new_node)

    {

        Node current = head;

  

        // Случай 1 вышеупомянутого алгоритма

        if (current == null)

        {

            new_node.next = new_node;

            head = new_node;

  

        }

  

        // Случай 2 вышеупомянутого алгоритма

        else if (current.data >= new_node.data)

        {

  

            / * Если значение меньше значения головы,

             нам нужно изменить следующий из последнего узла * /

            while (current.next != head)

                current = current.next;

  

            current.next = new_node;

            new_node.next = head;

            head = new_node;

        }

  

        // Случай 3 вышеуказанного алгоритма

        else

        {

  

            / * Найдите узел до точки вставки * /

            while (current.next != head &&

                   current.next.data < new_node.data)

                current = current.next;

  

            new_node.next = current.next;

            current.next = new_node;

        }

    }

  

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

    void printList()

    {

        if (head != null)

        {

            Node temp = head;

            do

            {

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

                temp = temp.next;

            while (temp != head);

        }

    }

  

    // Код драйвера для проверки выше

    public static void main(String[] args)

    {

        LinkedList list = new LinkedList();

  

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

        int arr[] = new int[] {12, 56, 2, 11, 1, 90};

  

        / * начать с пустого связанного списка * /

        Node temp = null;

  

        / * Создать связанный список из массива arr [].

         Созданный связанный список будет 1-> 2-> 11-> 12-> 56-> 90 * /

        for (int i = 0; i < 6; i++)

        {

            temp = new Node(arr[i]);

            list.sortedInsert(temp);

        }

  

        list.printList();

    }

}

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

питон

# Класс узла

class Node:

  

    # Конструктор для инициализации объекта узла

    def __init__(self, data):

        self.data = data

        self.next = None

  

class LinkedList:

  

    # Функция для инициализации головы

    def __init__(self):

        self.head = None

  

    # Функция для вставки нового узла в начале

    def push(self, new_data):

        new_node = Node(new_data)

        new_node.next = self.head

        self.head = new_node

  

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

    def printList(self):

        temp = self.head

        print temp.data,

        temp = temp.next

        while(temp != self.head):

            print temp.data,

            temp = temp.next

  

    Функция "" "для вставки new_node в список отсортированным способом.

       Обратите внимание, что эта функция ожидает указатель на головной узел

       так как это может изменить заголовок связанного списка ввода "" "

    def sortedInsert(self, new_node):

          

        current = self.head

  

        # Случай 1 вышеупомянутого алгоритма

        if current is None:

            new_node.next = new_node 

            self.head = new_node

          

        # Случай 2 вышеупомянутого алгоритма

        elif (current.data >= new_node.data):

              

            # Если значение меньше значения головы, то мы

            # необходимо изменить следующий из последнего узла

            while current.next != self.head :

                current = current.next

            current.next = new_node

            new_node.next = self.head

            self.head = new_node            

  

          

        № 3 из вышеприведенного алгоритма

        else:

              

            # Найдите узел до точки вставки

            while (current.next != self.head  and 

                   current.next.data < new_node.data):

                current = current.next

  

            new_node.next = current.next

            current.next = new_node

  

  
# Драйвер программы для проверки вышеуказанной функции
#llist = LinkedList ()

arr = [12, 56, 2, 11, 1, 90]

  

list_size = len(arr)

  
# начать с пустого связанного списка

start = LinkedList()

  
# Создать связанный список из массива arr []
# Созданный связанный список будет 1-> 2-> 11-> 12-> 56-> 90

for i in range(list_size):

    temp = Node(arr[i])

    start.sortedInsert(temp)

  
start.printList()

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

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

using System;

  

class LinkedList 

    public class Node 

    

        public int data; 

        public Node next; 

  

        public Node(int d) 

        

            data = d; 

            next = null

        

    

    Node head; 

  

    // Конструктор

    LinkedList() 

    

        head = null;

    

  

    / * функция для вставки new_node

      в списке в отсортированном виде. Обратите внимание, что

      эта функция ожидает указатель

      в головной узел, так как это может изменить

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

    void sortedInsert(Node new_node) 

    

        Node current = head; 

  

        // Случай 1 вышеупомянутого алгоритма

        if (current == null

        

            new_node.next = new_node; 

            head = new_node; 

  

        

  

        // Случай 2 вышеупомянутого алгоритма

        else if (current.data >= new_node.data) 

        

  

            / * Если значение меньше чем

                Ценность головы тогда нам нужно

                изменить следующий из последнего узла * /

            while (current.next != head) 

                current = current.next; 

  

            current.next = new_node; 

            new_node.next = head; 

            head = new_node; 

        

  

        // Случай 3 вышеуказанного алгоритма

        else

        

  

            / * Найдите узел раньше

            точка вставки * /

            while (current.next != head && 

                current.next.data < new_node.data) 

                current = current.next; 

  

            new_node.next = current.next; 

            current.next = new_node; 

        

    

  

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

    void printList() 

    

        if (head != null

        

            Node temp = head; 

            do

            

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

                temp = temp.next; 

            

            while (temp != head); 

        

    

  

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

    public static void Main(String []args) 

    

        LinkedList list = new LinkedList(); 

  

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

        int []arr = {12, 56, 2, 11, 1, 90}; 

  

        / * начать с пустого связанного списка * /

        Node temp = null

  

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

          массив обр []. Создан связанный список

          будет 1-> 2-> 11-> 12-> 56-> 90 * /

        for (int i = 0; i < 6; i++) 

        

            temp = new Node(arr[i]); 

            list.sortedInsert(temp); 

        

        list.printList(); 

    

  
// Этот код был добавлен
// Арнаб Кунду


Выход:

1 2 11 12 56 90

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

Случай 2 вышеупомянутого алгоритма / кода может быть оптимизирован. Для реализации предложенного изменения нам нужно изменить вариант 2 на следующий.

// Случай 2 вышеупомянутого алгоритма

else if (current->data >= new_node->data)

{

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

  // при условии, что у нас есть функция swap (int *, int *)

  swap(&(current->data), &(new_node->data)); 

 

  new_node->next = (*head_ref)->next;

  (*head_ref)->next = new_node;

}

Пожалуйста, напишите комментарии, если вы обнаружите, что приведенный выше код / алгоритм неверен, или найдите другие способы решения той же проблемы.

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

Сортированная вставка для круглого связанного списка

0.00 (0%) 0 votes