Как изменить связанный список с помощью рекурсии?

ProgramBox

Как изменить связанный список с помощью рекурсии?

Post author:admin
Запись опубликована:16 апреля, 2023
Post category:Вопросы по программированию

#c #algorithm #recursion #data-structures #linked-list

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

Вопрос:

Я пытаюсь изменить связанный список с помощью рекурсии. Ранее я написал код для этого, используя простой while цикл, и он отлично сработал. Я не могу понять, почему мой код рекурсии не работает.

 #include<iostream>

using std::cout;
using std::endl;

struct node
{
    int data;
    node* next;
};

class LinkedLists
{
    private: 
    node* head;
    node* temp;
    
    public:
    LinkedLists() // default constructor
    {
        head = NULL;
        temp = NULL;
    }

    void add_data(int d)
    {   
        node* new_node = new node; // create a pointer to the new node
        new_node->next = NULL;
        new_node->data = d;
        if (head == NULL)
        {   head = new_node;
            temp = head;
        }
        else
        {   
            temp = head;
            while(temp->next != NULL)
            {
                temp = temp->next;
            }
            temp->next = new_node; // final node now points to the new_node
        }

    }

    void print_list()
    {
        temp = head;
        while(temp!=NULL)
        {
            std::cout<<temp->data<<" ";
            temp = temp->next;
        }
    }

    void reverse()
    {
        // reverse a linked list
        node* prev_node;
        node* next_node;
        node* temp_ptr;

        prev_node = NULL;
        temp_ptr = head;
        next_node = temp_ptr->next;

        while(next_node != NULL)
        {
            temp_ptr->next = prev_node;
            prev_node = temp_ptr;
            temp_ptr = next_node;
            next_node = temp_ptr->next;
        }

        temp_ptr->next = prev_node;

        head = temp_ptr;

    }

    void repeat(node* prev_node, node* temp_ptr,node* next_node)
    {
        temp_ptr->next = prev_node;
        prev_node = temp_ptr;
        temp_ptr = next_node;

        if (next_node != NULL)
        {
            next_node = temp_ptr->next;
            repeat(prev_node,temp_ptr,next_node);
        }
        head = temp_ptr;
    }

    void recursive_reverse()
    {
        node* prev_node;
        node* next_node;
        node* temp_ptr;

        prev_node = NULL;
        temp_ptr = head;
        next_node = temp_ptr->next;

        repeat(prev_node,temp_ptr,next_node);

    }
};

int main()
{
    LinkedLists l; // create a linked list object
    l.add_data(110);
    l.add_data(140);
    l.add_data(101);
    l.add_data(140);
    l.add_data(101);
    l.add_data(140);
    l.add_data(101);
    l.add_data(120);

    cout<<endl;
    l.print_list();


    l.reverse();

    cout<<endl;
    l.print_list();


    l.recursive_reverse();
    cout<<endl;
    l.print_list();

}

Вывод:

 110 140 101 140 101 140 101 120
120 101 140 101 140 101 140 110
101 120

Ожидаемый результат:

 110 140 101 140 101 140 101 120
120 101 140 101 140 101 140 110
110 140 101 140 101 140 101 120

1. Несвязанный: вы используете, new но не delete . Ваша программа дает утечку. Я бы сказал, что исправление этого важнее, чем его изменение.

2. Где я должен использовать delete ? Разве это не приведет к удалению узла? Или мне не следует использовать new в первую очередь?

3. Если вы создаете LinkedLists и заполняете его данными, а LinkedLists он выходит за пределы области видимости — предполагается, что это очистит всю выделенную ему память. Вы просто оставляете его выделенным. Если вы будете делать это в цикле, у вас в конечном итоге закончится память. Иногда вы можете использовать интеллектуальные указатели, но для такого рода вещей, вероятно, вам нужны необработанные указатели, но это делает управление памятью действительно важным. Первым шагом может быть деструктор, такой как: ~LinkedList() { for(node* temp; head; head = temp) { temp = head->next; delete head; } } или аналогичный.

4. О delete вопросе: просто реализуйте деструктор LinkedLists::~LinkedLists() , который удалит все ранее выделенные данные. Вы также можете сделать это рекурсивно, однако обычно лучше выполнять такого рода действия итеративно для больших объектов.

5. @Yatin Да, вам нужен деструктор (подобный тому, который я показал выше), но вам также нужно подумать о правиле трех / пяти / нуля

Ответ №1:

Для начала неясно, почему класс связанного списка имеет имя во множественном числе.

 class LinkedLists
               ^^^

Будет более естественно назвать его как LinkedList без окончания 's' .

Элемент данных temp является избыточным и должен быть удален. Вместо этого вы можете заменить этот элемент данных локальными переменными в функциях-членах.

Структура node должна быть закрытым членом класса LinkedList .

Я не просмотрел все ваши реализации функций, но функция recursive_reverse может быть определена следующим образом, как показано в демонстрационной программе ниже.

Вот вы где.

 #include <iostream>
#include <functional>

class LinkedList
{
private: 
    struct node
    {
        int data;
        node* next;
    } *head = nullptr;


public:
    LinkedList() = default;

    // These two special member functions you can implement yourself
    LinkedList( const LinkedList amp;) = delete;
    LinkedList amp; operator =( const LinkedList amp; ) = delete;

    ~LinkedList()
    {
        clear();
    }
    
    void clear()
    {
        while ( head )
        {
            delete std::exchange( head, head->next );
        }
    }
    
    void add_data( int d )
    {   
        node **current = amp;head;
        
        while ( *current ) current = amp;( *current )->next;
        
        *current = new node { d, nullptr };
    }       

    friend std::ostream amp; operator <<( std::ostream amp;os, const LinkedList amp;list )
    {
        for ( const node *current = list.head; current != nullptr; current = current->next )
        {
            os << current->data << " -> ";
        }
        
        return os << "null";
    }

    void recursive_reverse()
    {
        if ( head != nullptr amp;amp; head->next != nullptr )
        {
            node *current = head;
            head = head->next;
            
            recursive_reverse();
            
            current->next->next = current;
            current->next = nullptr;
        }
    }
};

int main() 
{
    LinkedList list; // create a linked list object
    const int N = 10;
    
    for ( int i = 0; i < N; i   )
    {
        list.add_data( i );
    }       

   
    std::cout << list << 'n';


    list.recursive_reverse();

    std::cout << list << 'n';

    list.recursive_reverse();

    std::cout << list << 'n';

    return 0;
}

Вывод программы

 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 -> null
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null

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

Вот демонстрационная программа.

 #include <iostream>
#include <functional>

class LinkedList
{
private: 
    struct node
    {
        int data;
        node* next;
    } *head = nullptr;

    static void repeat( node *previous, node * amp;head )
    {
        if ( head )
        {
            node *current = head;
            
            if ( head->next ) 
            {
                head = head->next;
                repeat( current, head );
            }
            
            current->next = previous;
        }
    }
    
public:
    LinkedList() = default;
    ~LinkedList()
    {
        clear();
    }
    
    void clear()
    {
        while ( head )
        {
            delete std::exchange( head, head->next );
        }
    }
    
    void add_data( int d )
    {   
        node **current = amp;head;
        
        while ( *current ) current = amp;( *current )->next;
        
        *current = new node { d, nullptr };
    }       

    friend std::ostream amp; operator <<( std::ostream amp;os, const LinkedList amp;list )
    {
        for ( const node *current = list.head; current != nullptr; current = current->next )
        {
            os << current->data << " -> ";
        }
        
        return os << "null";
    }
    
    void recursive_reverse()
    {
        repeat( nullptr, head );
    }
};

int main() 
{
    LinkedList list; // create a linked list object
    const int N = 10;
    
    for ( int i = 0; i < N; i   )
    {
        list.add_data( i );
    }       

   
    std::cout << list << 'n';


    list.recursive_reverse();

    std::cout << list << 'n';

    list.recursive_reverse();

    std::cout << list << 'n';

    return 0;
}

Выходные данные программы такие же, как показано выше

 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 -> null
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null

Ответ №2:

Ваш код излишен, вам не нужно так много локальных переменных и аргументов функции для реализации рекурсии. Также в этой части:

         if (next_node != NULL)
        {
            next_node = temp_ptr->next;
            repeat(prev_node,temp_ptr,next_node);
        }
        head = temp_ptr;

кажется, вы присваиваете nullptr своему head when next_node == nullptr .

Исправленная версия:

     void repeat(node* previous, node* current)
    {
      node* next_node = current->next;
      current->next = previous;
      if (next_node == nullptr)
      {
        head = current;
        return;
      }
      repeat(current, next_node);
    }

    void recursive_reverse()
    {
        repeat(nullptr, head);
    }

Кроме того, у вас есть утечки памяти, потому что вы никогда не delete выделяли память. Реализуйте деструктор и пометьте свои конструкторы копирования / назначения как deleted явно (или вы также можете реализовать их, если у вас есть время):

 LinkedLists(const LinkedListsamp; other) = delete;

чтобы избежать дальнейших ошибок и соблюдать правило трех (или пяти, или нуля).