Рубрики

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

Предположим, структура узла связанного списка выглядит следующим образом.

struct Node

{

  int data;

  struct Node *next;

};

Объясните функциональность следующих функций C.

1. Что делает следующая функция для данного связанного списка?

void fun1(struct Node* head)

{

  if(head == NULL)

    return;

   

  fun1(head->next);

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

}

fun1 () печатает данный связанный список в обратном порядке. Для связанного списка 1-> 2-> 3-> 4-> 5 fun1 () печатает 5-> 4-> 3-> 2-> 1.

2. Что делает следующая функция для данного связанного списка?

void fun2(struct Node* head)

{

  if(head== NULL)

    return;

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

  

  if(head->next != NULL )

    fun2(head->next->next);

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

}

fun2 () печатает альтернативные узлы данного связанного списка, сначала от головы до конца, а затем от конца к голове. Если Linked List имеет четное число узлов, fun2 () пропускает последний узел. Для связного списка 1-> 2-> 3-> 4-> 5 fun2 () печатает 1 3 5 5 3 1. Для связного списка 1-> 2-> 3-> 4-> 5-> 6, fun2 ( ) печатает 1 3 5 5 3 1.

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

C ++

#include <bits/stdc++.h>

using namespace std;

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

class Node 

    public:

    int data; 

    Node *next; 

}; 

  

  
/ * Печатает связанный список в обратном порядке * /

void fun1(Node* head) 

    if(head == NULL) 

        return

      

    fun1(head->next); 

    cout << head->data << " "

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

void fun2(Node* start) 

    if(start == NULL) 

        return

    cout<<start->data<<" "

      

    if(start->next != NULL ) 

        fun2(start->next->next); 

    cout << start->data << " "

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ ДЛЯ ТЕСТИРОВАНИЯ fun1 () и fun2 () * /
/ * Дана ссылка (указатель на указатель) на голову
списка и int, нажмите новый узел на передней панели
из списка. * /

void push(Node** head_ref, int new_data) 

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

    Node* new_node = new Node();

      

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

    new_node->data = new_data; 

      

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

    new_node->next = (*head_ref); 

      

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

    (*head_ref) = new_node; 

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

int main() 

    / * Начнем с пустого списка * /

    Node* head = NULL; 

      

    / * Использование push () для построения списка ниже

        1-> 2-> 3-> 4-> 5 * /

    push(&head, 5); 

    push(&head, 4); 

    push(&head, 3); 

    push(&head, 2); 

    push(&head, 1); 

      

    cout<<"Output of fun1() for list 1->2->3->4->5 \n"

    fun1(head); 

      

    cout<<"\nOutput of fun2() for list 1->2->3->4->5 \n"

    fun2(head); 

  

    return 0; 

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

С

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

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

struct Node

{

  int data;

  struct Node *next;

};

  

  
/ * Печатает связанный список в обратном порядке * /

void fun1(struct Node* head)

{

  if(head == NULL)

    return;

  

  fun1(head->next);

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

}

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

  от головы до конца, а затем от конца к голове. * /

void fun2(struct Node* start)

{

  if(start == NULL)

    return;

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

  

  if(start->next != NULL )

    fun2(start->next->next);

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

}

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ ДЛЯ ТЕСТИРОВАНИЯ fun1 () и fun2 () * /
/ * Дана ссылка (указатель на указатель) на голову

  списка и int, нажмите новый узел на передней панели

  из списка. * /

void push(struct Node** head_ref, int new_data)

{

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

  struct Node* new_node =

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

   

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

  new_node->data  = new_data;

   

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

  new_node->next = (*head_ref);

   

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

  (*head_ref)    = new_node;

}

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

int main()

{

  / * Начнем с пустого списка * /

  struct Node* head = NULL;

  

  / * Использование push () для построения списка ниже

    1-> 2-> 3-> 4-> 5 * /

  push(&head, 5);

  push(&head, 4);

  push(&head, 3);

  push(&head, 2);

  push(&head, 1);   

   

  printf("Output of fun1() for list 1->2->3->4->5 \n");

  fun1(head);

  

  printf("\nOutput of fun2() for list 1->2->3->4->5 \n"); 

  fun2(head);

          

  getchar();

  return 0;

}

Джава

// Реализация кода Java для вышеуказанного подхода

class GFG 

{

  

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

    static class Node 

    {

        int data;

        Node next;

    };

  

    / * Печатает связанный список в обратном порядке * /

    static void fun1(Node head)

    {

        if (head == null)

        {

            return;

        }

  

        fun1(head.next);

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

    }

  

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

    от головы до конца, а затем от конца к голове. * /

    static void fun2(Node start)

    {

        if (start == null)

        {

            return;

        }

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

  

        if (start.next != null)

        {

            fun2(start.next.next);

        }

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

    }

  

    / * ПОЛЕЗНЫЕ ФУНКЦИИ ДЛЯ ТЕСТИРОВАНИЯ fun1 () и fun2 () * /

    / * Дана ссылка (указатель на указатель) на голову

    списка и int, нажмите новый узел на передней панели

    из списка. * /

    static Node push(Node head_ref, int new_data) 

    {

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

        Node new_node = new Node();

  

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

        new_node.data = new_data;

  

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

        new_node.next = (head_ref);

  

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

        (head_ref) = new_node;

        return head_ref;

    }

  

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

    public static void main(String[] args) 

    {

        / * Начнем с пустого списка * /

        Node head = null;

  

        / * Использование push () для просмотра списка

        1-> 2-> 3-> 4-> 5 * /

        head = push(head, 5);

        head = push(head, 4);

        head = push(head, 3);

        head = push(head, 2);

        head = push(head, 1);

  

        System.out.print("Output of fun1() for "

                         "list 1->2->3->4->5 \n");

        fun1(head);

  

        System.out.print("\nOutput of fun2() for " +

                           "list 1->2->3->4->5 \n");

        fun2(head);

    }

}

  
// Этот код предоставлен Rajput-Ji

C #

// реализация кода C # для вышеуказанного подхода

using System;

  

class GFG 

{

  

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

    public class Node 

    {

        public int data;

        public Node next;

    };

  

    / * Печатает связанный список в обратном порядке * /

    static void fun1(Node head)

    {

        if (head == null)

        {

            return;

        }

  

        fun1(head.next);

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

    }

  

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

    от головы до конца, а затем от конца к голове. * /

    static void fun2(Node start)

    {

        if (start == null)

        {

            return;

        }

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

  

        if (start.next != null)

        {

            fun2(start.next.next);

        }

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

    }

  

    / * ПОЛЕЗНЫЕ ФУНКЦИИ ДЛЯ ТЕСТИРОВАНИЯ fun1 () и fun2 () * /

    / * Дана ссылка (указатель на указатель) на голову

    списка и целого, толкнуть новый узел на фронте

    из списка. * /

    static Node Push(Node head_ref, int new_data) 

    {

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

        Node new_node = new Node();

  

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

        new_node.data = new_data;

  

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

        new_node.next = (head_ref);

  

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

        (head_ref) = new_node;

        return head_ref;

    }

  

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

    public static void Main(String[] args) 

    {

        / * Начнем с пустого списка * /

        Node head = null;

  

        / * Использование.Push () для просмотра списка

        1-> 2-> 3-> 4-> 5 * /

        head = Push(head, 5);

        head = Push(head, 4);

        head = Push(head, 3);

        head = Push(head, 2);

        head = Push(head, 1);

  

        Console.Write("Output of fun1() for "

                        "list 1->2->3->4->5 \n");

        fun1(head);

  

        Console.Write("\nOutput of fun2() for " +

                        "list 1->2->3->4->5 \n");

        fun2(head);

    }

}

  
// Этот код предоставлен Rajput-Ji


Выход:

 Output of fun1() for list 1->2->3->4->5 
5 4 3 2 1 
Output of fun2() for list 1->2->3->4->5 
1 3 5 5 3 1 

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

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

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

0.00 (0%) 0 votes