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

@Dennis Ritchie · Регистрация: 27.07.2014

Author24 — интернет-сервис помощи студентам

Дан односвязный список. Требуется напечатать исходный список. Поменять местами два элемента списка, номера которых введёт пользователь с клавиатуры. Напечатать получившийся список.

@Dennis Ritchie · 22.11.2014, 17:40 **[ТС]**

Сообщение от Nosey

Извиняюсь, забыл эту ситуацию рассмотреть.

Nosey, не только эту. Вы попробуйте теперь ввести c = 5 и поменять минус десятый элемент с шестым. У TheCalligrapher'a по-прежнему всё корректно работает. Просто препод сказал, что на следующей неделе проверит программу на тестах, в которых индексы списка выходят за пределы.

И ещё он сказал, что в таком случае элементы списка не должны меняться, т. е. программа не должна ничего делать.

@TheCalligrapher · 22.11.2014, 17:50

Сообщение от Nosey

И если вы надумаете разбираться с реализацией TheCalligrapher, то идея там в следующем, мы меняем указатели next найденных объектов, а сами найденные объекты свапаем по значению,

Нет, нет, целые объекты (в смысле - целые элементы списка) по значению у меня не свапаются нигде. В моем коде везде идет манипуляция указателями и только указателями.

Вот это

C++

1	std::swap(pn1, pn2);

свапает только указатели 'next', хранящиеся в предыдущих объектах. 'pn1' и 'pn2' - это указатели на указатель, а не указатели на целые объекты.

@Nosey · 22.11.2014, 17:59

Dennis Ritchie, Да, проверку входных данных я не реализовал, и собственно вот она:

C++

........
        MineListNode* head = _head;
        while (head != nullptr)
        {
            if (index == index1)
            {
                prevIndex1Node = head;
                index1Node = head->next;
            }
            if (index == index2)
            {
                prevIndex2Node = head;
                index2Node = head->next;
            }
            head = head->next;
            index++;
        }
// !!!!
        if (index2Node == nullptr || index1Node == nullptr)
        {
            return;
        }
// !!!!
.....

А также извиняюсь я вас обманул в предыдущем сообщении про свап по значению в реализации TheCalligrapher, там pn1 указывает на моё prevIndex1Node->next, в общем, очень красивая реализация, попробуйте разобраться в ней.

Добавлено через 1 минуту

Не по теме:

TheCalligrapher, Да, спасибо большое, я на перекуре разобрался :)

@Dennis Ritchie · 22.11.2014, 18:25 **[ТС]**

Сообщение от Nosey

Да, проверку входных данных я не реализовал, и собственно вот она...

А попробуйте ввести c = 5 и поменять местами минус первый и минус пятый элемент.

Сообщение от Nosey

А также извиняюсь я вас обманул в предыдущем сообщении про свап по значению в реализации TheCalligrapher...

Да, не за что извиняться.

Сообщение от Nosey

в общем, очень красивая реализация, попробуйте разобраться в ней.

Я знаю, что у TheCalligrapher'a практически всегда красивая реализация. Когда-нибудь разберусь, когда лучше изучу C++.

@Nosey · 22.11.2014, 18:58

Dennis Ritchie,

C++

    void swapListNodeByIndex(int index1, int index2)
    {
        if (index1 > index2)
        {
            int temp = index1;
            index1 = index2;
            index2 = temp;
        }
 
        if (index1 < 0 || index1 == index2)
        {
            return;
        }
 
        MineListNode* prevIndex1Node = nullptr;
        MineListNode* prevIndex2Node = nullptr;
        MineListNode* index1Node = nullptr;
        MineListNode* index2Node = nullptr;
 
        int index = 0;
 
        if (index1 == 0)
        {
            index1Node = _head;
        }
 
        MineListNode* head = _head;
        while (head != nullptr && !index1Node)
        {
            index++;
            if (index == index1)
            {
                prevIndex1Node = head;
                index1Node = head->next;
                index--;
                break;
            }
            head = head->next;
        }
        if (index1Node == nullptr)
        {
            return;
        }
        while (head != nullptr)
        {
            index++;
            if (index == index2)
            {
                prevIndex2Node = head;
                index2Node = head->next;
                break;
            }
            head = head->next;
        }
 
        if (index2Node == nullptr)
        {
            return;
        }
 
        MineListNode* temp;
        if (prevIndex1Node != nullptr && prevIndex2Node != nullptr)
        {
            temp = index2Node->next;
            prevIndex1Node->next = index2Node;
            if (index2Node != index1Node->next)
            {
                index2Node->next = index1Node->next;
            }
            else
            {
                index2Node->next = index1Node;
            }
 
            prevIndex2Node->next = index1Node;
            if (index1Node != temp)
            {
                index1Node->next = temp;
            }
            else
            {
                index1Node->next = index2Node;
            }
        }
        else if (prevIndex1Node == nullptr)
        {
            temp = index2Node->next;
            if (index2Node != index1Node->next)
            {
                index2Node->next = index1Node->next;
            }
            else
            {
                index2Node->next = index1Node;
            }
 
            prevIndex2Node->next = index1Node;
            if (index1Node != temp)
            {
                index1Node->next = temp;
            }
            else
            {
                index1Node->next = index2Node;
            }
            _head = index2Node;
        }
        else if (prevIndex2Node == nullptr)
        {
            temp = index2Node->next;
            prevIndex1Node->next = index2Node;
            if (index2Node != index1Node->next)
            {
                index2Node->next = index1Node->next;
            }
            else
            {
                index2Node->next = index1Node;
            }
 
            if (index1Node != temp)
            {
                index1Node->next = temp;
            }
            else
            {
                index1Node->next = index2Node;
            }
            _head = index1Node;
        }
    }

@Dennis Ritchie · 22.11.2014, 19:18 **[ТС]**

Nosey, теперь кажется всё. К следующей неделе помимо модернизации данной программы (надеюсь, что больше ничего модернизировать не придётся) надо составить аналогичную программу для двусвязного списка.
Поможете?

@Dennis Ritchie · 29.11.2014, 14:55 **[ТС]**

Nosey, можете, пожалуйста, заменить class на что-нибудь более простое? Преподаватель до сих пор задачу не принял...

C++

#include <iostream>
 
struct Data
{
    int value;
    Data() {}
    Data(int value) : value(value) {}
};
 
class MineListNode
{
public:
    MineListNode() : next(nullptr) {}
    MineListNode* next;
    Data data;
};
 
class MineList
{
private:
    MineListNode* _head;
public:
    MineList() : _head(nullptr) {}
    MineListNode* head()
    {
        return _head;
    }
 
    void pushBeginData(Data& data)
    {
        MineListNode* head = new MineListNode();
        head->data = data;
        head->next = _head;
        _head = head;
    }
 
    void printList()
    {
        MineListNode* head = _head;
        while (head != nullptr)
        {
            std::cout << head->data.value << " ";
            head = head->next;
        }
        std::cout << std::endl;
    }
 
    void swapListNodeByIndex(int index1, int index2)
    {
        if (index1 > index2)
        {
            int temp = index1;
            index1 = index2;
            index2 = temp;
        }
 
        if (index1 < 0 || index1 == index2)
        {
            return;
        }
 
        MineListNode* prevIndex1Node = nullptr;
        MineListNode* prevIndex2Node = nullptr;
        MineListNode* index1Node = nullptr;
        MineListNode* index2Node = nullptr;
 
        int index = 0;
 
        if (index1 == 0)
        {
            index1Node = _head;
        }
 
        MineListNode* head = _head;
        while (head != nullptr && !index1Node)
        {
            index++;
            if (index == index1)
            {
                prevIndex1Node = head;
                index1Node = head->next;
                index--;
                break;
            }
            head = head->next;
        }
        if (index1Node == nullptr)
        {
            return;
        }
        while (head != nullptr)
        {
            index++;
            if (index == index2)
            {
                prevIndex2Node = head;
                index2Node = head->next;
                break;
            }
            head = head->next;
        }
 
        if (index2Node == nullptr)
        {
            return;
        }
 
        MineListNode* temp;
        if (prevIndex1Node != nullptr && prevIndex2Node != nullptr)
        {
            temp = index2Node->next;
            prevIndex1Node->next = index2Node;
            if (index2Node != index1Node->next)
            {
                index2Node->next = index1Node->next;
            }
            else
            {
                index2Node->next = index1Node;
            }
 
            prevIndex2Node->next = index1Node;
            if (index1Node != temp)
            {
                index1Node->next = temp;
            }
            else
            {
                index1Node->next = index2Node;
            }
        }
        else if (prevIndex1Node == nullptr)
        {
            temp = index2Node->next;
            if (index2Node != index1Node->next)
            {
                index2Node->next = index1Node->next;
            }
            else
            {
                index2Node->next = index1Node;
            }
 
            prevIndex2Node->next = index1Node;
            if (index1Node != temp)
            {
                index1Node->next = temp;
            }
            else
            {
                index1Node->next = index2Node;
            }
            _head = index2Node;
        }
        else if (prevIndex2Node == nullptr)
        {
            temp = index2Node->next;
            prevIndex1Node->next = index2Node;
            if (index2Node != index1Node->next)
            {
                index2Node->next = index1Node->next;
            }
            else
            {
                index2Node->next = index1Node;
            }
 
            if (index1Node != temp)
            {
                index1Node->next = temp;
            }
            else
            {
                index1Node->next = index2Node;
            }
            _head = index1Node;
        }
    }
};
 
 
void main()
{
    MineList mineList;
    int c;
    std::cout << "vvedite razmer spiska:" << std::endl;
    std::cin >> c;
    while (--c >= 0)
    {
        mineList.pushBeginData(Data(c));
    }
 
    std::cout << " --------------- " << std::endl;
    mineList.printList();
    int first, last;
    std::cout << "\nvvedite nomera elementov spiska, kotorye neobkhodimo pomenyat' mestami:" << std::endl;
    std::cin >> first >> last;
    mineList.swapListNodeByIndex(first, last);
    std::cout << " --------------- " << std::endl;
    mineList.printList();
 
    std::cout << std::endl;
}

Добавлено через 27 минут
Хотя уже принял: я просто заменил слово class на struct, и программа заработала.

C

#include <iostream>
 
struct Data
{
    int value;
    Data() {}
    Data(int value) : value(value) {}
};
 
struct MineListNode
{
    MineListNode() : next(nullptr) {}
    MineListNode* next;
    Data data;
};
 
struct MineList
{
    MineListNode* _head;
    MineList() : _head(nullptr) {}
    MineListNode* head()
    {
        return _head;
    }
 
    void pushBeginData(Data& data)
    {
        MineListNode* head = new MineListNode();
        head->data = data;
        head->next = _head;
        _head = head;
    }
 
    void printList()
    {
        MineListNode* head = _head;
        while (head != nullptr)
        {
            std::cout << head->data.value << " ";
            head = head->next;
        }
        std::cout << std::endl;
    }
 
    void swapListNodeByIndex(int index1, int index2)
    {
        if (index1 > index2)
        {
            int temp = index1;
            index1 = index2;
            index2 = temp;
        }
 
        if (index1 < 0 || index1 == index2)
        {
            return;
        }
 
        MineListNode* prevIndex1Node = nullptr;
        MineListNode* prevIndex2Node = nullptr;
        MineListNode* index1Node = nullptr;
        MineListNode* index2Node = nullptr;
 
        int index = 0;
 
        if (index1 == 0)
        {
            index1Node = _head;
        }
 
        MineListNode* head = _head;
        while (head != nullptr && !index1Node)
        {
            index++;
            if (index == index1)
            {
                prevIndex1Node = head;
                index1Node = head->next;
                index--;
                break;
            }
            head = head->next;
        }
        if (index1Node == nullptr)
        {
            return;
        }
        while (head != nullptr)
        {
            index++;
            if (index == index2)
            {
                prevIndex2Node = head;
                index2Node = head->next;
                break;
            }
            head = head->next;
        }
 
        if (index2Node == nullptr)
        {
            return;
        }
 
        MineListNode* temp;
        if (prevIndex1Node != nullptr && prevIndex2Node != nullptr)
        {
            temp = index2Node->next;
            prevIndex1Node->next = index2Node;
            if (index2Node != index1Node->next)
            {
                index2Node->next = index1Node->next;
            }
            else
            {
                index2Node->next = index1Node;
            }
 
            prevIndex2Node->next = index1Node;
            if (index1Node != temp)
            {
                index1Node->next = temp;
            }
            else
            {
                index1Node->next = index2Node;
            }
        }
        else if (prevIndex1Node == nullptr)
        {
            temp = index2Node->next;
            if (index2Node != index1Node->next)
            {
                index2Node->next = index1Node->next;
            }
            else
            {
                index2Node->next = index1Node;
            }
 
            prevIndex2Node->next = index1Node;
            if (index1Node != temp)
            {
                index1Node->next = temp;
            }
            else
            {
                index1Node->next = index2Node;
            }
            _head = index2Node;
        }
        else if (prevIndex2Node == nullptr)
        {
            temp = index2Node->next;
            prevIndex1Node->next = index2Node;
            if (index2Node != index1Node->next)
            {
                index2Node->next = index1Node->next;
            }
            else
            {
                index2Node->next = index1Node;
            }
 
            if (index1Node != temp)
            {
                index1Node->next = temp;
            }
            else
            {
                index1Node->next = index2Node;
            }
            _head = index1Node;
        }
    }
};
 
 
void main()
{
    MineList mineList;
    int c;
    std::cout << "vvedite razmer spiska:" << std::endl;
    std::cin >> c;
    while (--c >= 0)
    {
        mineList.pushBeginData(Data(c));
    }
 
    std::cout << " --------------- " << std::endl;
    mineList.printList();
    int first, last;
    std::cout << "\nvvedite nomera elementov spiska, kotorye neobkhodimo pomenyat' mestami:" << std::endl;
    std::cin >> first >> last;
    mineList.swapListNodeByIndex(first, last);
    std::cout << " --------------- " << std::endl;
    mineList.printList();
 
    std::cout << std::endl;
}

@volodymyr27 · 25.01.2021, 19:24

САМИЙ ЕЛЕМЕНТАРНИЙ СПОСОБ СВОП
ПРАВДА ИЩЕ НЕ ДОБАВИЛ ШОБ 1 ЕЛЕМЕНТ ВИДЕЛ....

C++

#include<iostream>
#include<cstdlib>
#include<vector>
 
using namespace std;
 
template<class T>
class List
{
private:
 
    template<class T>
    struct Node
    {
        T val;
        Node<T>* next;
    };
 
    Node<T>* first = nullptr;
 
    void del()
    {
        while (first != nullptr)
        {
            auto tmp = first->next;
            delete first;
            first = tmp;
        }
    }
    Node<T>* getLast2(Node<T>* node, int64_t cnt = -1)
    {
        while (node->next && cnt != 0)
        {
            cnt += (cnt == -1 ? 0 : -1);
            node = node->next;
        }
        return node;
    }
 
    int lenght = 0;
public:
    size_t getsize() { return lenght; }
 
    List() {}
    ~List()
    {
        del();
    }
 
    void push_back(const T& val)
    {
        if (first)
        {
            getLast2(first)->next = new Node<T>{ val, nullptr };
            lenght++;
        }
        else
        {
            first = new Node<T>{ val, nullptr };
            lenght++;
        }
 
        //  (items ? getLast2(items)->next : items) = new Node<T>{ val, nullptr };
    }
 
    void delete_element(size_t vall)
    {
        if (first->val == vall)
        {
            Node<T>* current = first;
            first = first->next;
            delete current;
            lenght--;
        }
 
        else
        {
            Node<T>* tmp = first;
            Node<T>* obj = first->next;
            while (first->next != NULL)
            {
                if (obj->val == vall)
                    break;
                else
                {
                    tmp = obj;
                    obj = obj->next;
                }
            }
            if (obj == NULL)
                cout << "not found!!!\n";
            else
            {
                tmp->next = obj->next;
                delete obj;
                lenght--;
            }
        }
    }
 
    void swap_element(int a, int b)
    {
        Node<T>* temp_res1 = first->next;
        Node<T>* temp_res2 = first->next;
        bool a1=false;
        bool a2 = false;
        while (first != NULL)
        {
            if (temp_res1->val == a)
            {
                temp_res1->val = a;
                a1 = true;
            }
            else
                temp_res1 = temp_res1->next;
 
            if (temp_res2->val == b)
            {
                temp_res2->val = b;
                a2 = true;
            }
            else
                temp_res2 = temp_res2->next;
            if (a1 && a2)
            {
                swap(temp_res1->val, temp_res2->val);
                break;
            }
        }   
    }
 
    T& operator [](size_t ind)
    {
        return getLast2(first, ind)->val;
    }
};
 
int main()
{   
    List<int> list;
    list.push_back(4);
    list.push_back(5);
    list.push_back(10);
    list.push_back(7);
    list.push_back(8);
 
 
    //list.delete_element(80);
    //list.delete_element(8);
    list.swap_element(10, 5);
 
    for (size_t i = 0; i < list.getsize(); i++)
    {
        cout << list[i] << endl;
    }
}

@TheCalligrapher · 25.01.2021, 19:48

Сообщение от volodymyr27

САМИЙ ЕЛЕМЕНТАРНИЙ СПОСОБ СВОП

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

Сообщение от volodymyr27

C++

template<class T>
class List
{
private:
    template<class T>
    struct Node
    {

Очередной шаблон внутри шаблона...

Это даже скомпилировать не получится.

Код

error: declaration of template parameter 'T' shadows template parameter
   12 |     template<class T>
      |              ^~~~~

Сообщение от volodymyr27

C++

            if (temp_res1->val == a)
            {
                temp_res1->val = a;
                a1 = true;
            }

Что это за удивительные манипуляции?

Сообщение от volodymyr27

C++

1	while (first != NULL)

Что это за загадочный цикл такой, в котором условие никогда не меняется?

И что же, интересно, произойдет с этим циклом, если хотя бы одно из искомых значений не будет найдено?

Сообщение от volodymyr27

int lenght = 0;

Lenght...

@Dennis Ritchie 555 / 148 / 58 Регистрация: 27.07.2014 Сообщений: 2,446
	22.11.2014, 19:18 [ТС]	26
	Nosey, теперь кажется всё. К следующей неделе помимо модернизации данной программы (надеюсь, что больше ничего модернизировать не придётся) надо составить аналогичную программу для двусвязного списка. Поможете? 0

@Dennis Ritchie 555 / 148 / 58 Регистрация: 27.07.2014 Сообщений: 2,446
	22.11.2014, 17:40 [ТС]	21
	Сообщение от Nosey Извиняюсь, забыл эту ситуацию рассмотреть. Nosey, не только эту. Вы попробуйте теперь ввести c = 5 и поменять минус десятый элемент с шестым. У TheCalligrapher'a по-прежнему всё корректно работает. Просто препод сказал, что на следующей неделе проверит программу на тестах, в которых индексы списка выходят за пределы. И ещё он сказал, что в таком случае элементы списка не должны меняться, т. е. программа не должна ничего делать. 0

@Dennis Ritchie 555 / 148 / 58 Регистрация: 27.07.2014 Сообщений: 2,446
	22.11.2014, 18:25 [ТС]	24
	Сообщение от Nosey Да, проверку входных данных я не реализовал, и собственно вот она... А попробуйте ввести c = 5 и поменять местами минус первый и минус пятый элемент. Сообщение от Nosey А также извиняюсь я вас обманул в предыдущем сообщении про свап по значению в реализации TheCalligrapher... Да, не за что извиняться. Сообщение от Nosey в общем, очень красивая реализация, попробуйте разобраться в ней. Я знаю, что у TheCalligrapher'a практически всегда красивая реализация. Когда-нибудь разберусь, когда лучше изучу C++. 0