Список ссылок C ++ в определенном порядке - PullRequest
Новая
       80

Список ссылок C ++ в определенном порядке

0 голосов
/ 31 марта 2020

Мне нужно заказать данный список ссылок 1 -> 2 -> 3 -> 4 -> 5, следуя шаблону low -> high -> low -> high -> low, что приводит к 1 -> 3 -> 2 - > 5 -> 4.

Я кодировал это: 

#include <iostream>

using namespace std;

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

class linked_list
{
private:
    node *head,*tail;
public:
    linked_list()
    {
        head = NULL;
        tail = NULL;
    }

    void add_node(int n)
    {
        node *tmp = new node;
        tmp->data = n;
        tmp->next = NULL;

        if(head == NULL)
        {
            head = tmp;
            tail = tmp;
        }
        else
        {
            tail->next = tmp;
            tail = tail->next;
        }
    }

    node* getHead()
    {
        return head;
    }
};

int main()
{
    linked_list a;
    a.add_node(1);
    a.add_node(2);
    a.add_node(3);
    a.add_node(4);
    a.add_node(5);
    bool leave= false;
    int direction = 1;
    node* considered_node = new node(*(a.getHead()));
    while(true)
    {
        if (considered_node->next == NULL)
        {
            break;
        }
        else if (direction*considered_node->next->data < direction*considered_node->data)
        {
            int t= direction*considered_node->next->data;
            int p = direction*considered_node->data;
            int tmp = considered_node->next->data;
            considered_node->next->data = considered_node->data;
            considered_node->data = tmp;
        }
        delete considered_node;
        considered_node = considered_node->next;
        direction = -1*direction;
    }
    return 0;
}

Но я допускаю ошибку в том, как я перебираю список ссылок и удаляю указатели, чтобы избежать утечки памяти , Я не хочу изменять объявление списка ссылок только для l oop.

Ответы [ 2 ]

1 голос
/ 31 марта 2020

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

Если это так, то нет необходимости использовать оператор new для изменения порядка в списке.

Вот демонстрационная программа. Я внес небольшие изменения в определение списка. Например, узел структуры должен быть скрыт от пользователя списка. Он должен быть определен как закрытый элемент данных внутри определения списка. 

#include <iostream>
#include <utility>

class linked_list
{
private:
    struct node
    {
        int data;
        node *next;
    } *head = nullptr, *tail = nullptr;

public:
    linked_list() = default;

    void add_node( int data )
    {
        node *tmp = new node { data, nullptr };

        if ( head == NULL )
        {
            head = tail = tmp;
        }
        else
        {
            tail = tail->next = tmp;
        }
    }

    void reorder()
    {
        int direction = 0;

        auto condition = [&direction]( const auto &a, const auto &b )
        {
            return ( direction ^= 1 ) ?  b < a : a < b;
        };

        node **current = &head;

        for ( ; *current && ( *current )->next; current = &( *current )->next )
        {
            if ( condition( ( *current )->data, ( *current )->next->data ) )
            {   
                node * &next = ( *current )->next;
                std::swap( *current, next );
                std::swap( ( *current )->next, next->next );
            }
        }

        tail = *current;
    }

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

        return os << "null";
    }   
};

int main() 
{
    linked_list list;
    int a[] = { 1, 2, 3, 4, 5 };

    for ( int data : a ) list.add_node( data );

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

    list.reorder();

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

    int b[] = { 6, 7, 8, 9, 10 };

    for ( int data : b ) list.add_node( data );

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

    list.reorder();

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

    return 0;
}

Его вывод 

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

Обратите внимание на то, что после переупорядочения списка необходимо настроить хвост указателя из списка. В противном случае добавление новых элементов в список может быть недопустимым.

0 голосов
/ 31 марта 2020

Здесь я попытался объяснить. См. https://ideone.com/PdBY6W. 

int direction = 1;

node* considered_node = new node(*(a.getHead()));
while(true)
{
    if (considered_node->next == NULL)
    {
        break;
    }

    // do not need else here
    if (direction*considered_node->next->data < direction*considered_node->data)
    {
        // do not need t and p
        // int t= direction*considered_node->next->data;
        // int p = direction*considered_node->data;
        int tmp = considered_node->next->data;
        considered_node->next->data = considered_node->data;
        considered_node->data = tmp;
    }

    // if you delete considered_node, then you can not access it's address
    // after deleting it. So comment the deletion
    // delete considered_node;
    considered_node = considered_node->next;
    direction = -1*direction;
}

// Notice after finishing the for loop, considered_node is now at the tail
// node of the list. So, before deleting considered_node move it's reference
// to the next node and then delete. Otherwise, if you delete without moving
// the reference, the deletion will delete the tail node, in which case the 
// list will be 1-> 3 -> 2 -> 5 -> 0.
considered_node = considered_node->next;
delete considered_node;

// now the list is 1-> 3 -> 2 -> 5 -> 4
...