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

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

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

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

@Nosey · 21.11.2014, 19:58

C++

#include "stdafx.h"
#include <iostream>
#include <sstream>
#include <list>
#include <algorithm>
 
class Data
{
    int _value = rand();
public:
    Data() {};
    int value() const { return _value; }
    void value(int value) { _value = value; }
};
 
std::ostream& operator<<(std::ostream& out, const Data& data)
{
    out << data.value();
    return out;
}
 
struct Swap
{
    int ind1;
    int ind2;
    int curInd = 0;
    Data* data1 = nullptr;
    Data* data2 = nullptr;
    bool isSwap = false;
 
    void operator()(Data& value)
    {
        if (isSwap)
        {
            return;
        }
        if (curInd == ind1)
        {
            data1 = &value;
        }
        else if (curInd == ind2)
        {
            data2 = &value;
        }
        if (data1 != nullptr && data2 != nullptr)
        {
            std::swap(*data1, *data2);
            isSwap = true;
        }
        curInd++;
    }
};
 
void main()
{
    std::list<Data> list;
    int count = 20;
    while (--count >= 0)
    {
        list.emplace_back();
    }
 
    std::ostream_iterator<Data> ost(std::cout, " ");
    std::copy(list.begin(), list.end(), ost);
    std::cout << std::endl;
 
    Swap swap;
    std::cin >> swap.ind1 >> swap.ind2;
    std::for_each(list.begin(), list.end(), swap);
 
    std::cout << std::endl;
    std::copy(list.begin(), list.end(), ost);
}

@Dennis Ritchie · 21.11.2014, 20:10 **[ТС]**

Nosey, огромное спасибо. А не могли бы вы прокомментировать код, чтобы легче разбираться было?

@Nosey · 21.11.2014, 20:17

Dennis Ritchie, Да, могу.
Что непонятно?
Или зачем вам это задание понадобилось?
Чтобы понять что рассказывать

@Dennis Ritchie · 21.11.2014, 20:26 **[ТС]**

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

Или зачем вам это задание понадобилось?

Учусь в ВУЗ'е. Преподаватель уже замучил. Я знаю, что если я ему завтра покажу такой код, то он закидает меня вопросами с ног до головы. И в итоге скажет, чтобы я переписал код более просто или же объяснил работу этого кода.

В общем, желательно прокомментировать в коде код структуры и код класса. Чем больше прокомментируете, тем лучше. Этот код поможет не только мне, если я смогу разобраться.

@TheCalligrapher · 21.11.2014, 20:29

Сообщение от Dennis Ritchie

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

Когда речь идет о списках, хранящих какие-то "полезные данные", задание "поменять местами два элемента" - неоднозначно.

* Во-первых, в списке "поменять местами два элемента" можно путем перецепления ссылок на узлы списка. "Полезные данные" останутся на прежних местах в памяти, но порядок физических узлов в списке изменится.

* Во-вторых, в списке "поменять местами два элемента" можно просто путем обмена "полезных данных", хранящихся в узлах, оставив ссылки нетронутыми. В таком случае наоборот, "полезные данные" обменяются в памяти, но порядок физических узлов в списке останется прежним.

С точки зрения распечатки содержимого списка, результат будет одним и тем же в обоих случаях. Однако побочные эффекты этих вариантов различаются. Например, если у меня есть два посторонних внешних указателя на обмениваемые узлы списка, то в первом способе "полезные данные", видимые через эти указатели, останутся прежними. А во втором способе они тоже обменяются.

О каком именно обмене идет речь?

Второй способ, понятное дело, применим к любому контейнеру. Поэтому когда в задаче явно говорят о списке, то это зачастую является "намеком" именно на первый способ.

@Dennis Ritchie · 21.11.2014, 20:34 **[ТС]**

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

Так о каком именно обмене идет речь?

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

@Nosey · 21.11.2014, 22:03

Давно я своих листов не писал )))
Думаю вы разберётесь и без комментариев.

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)
    {
        index1--;
        index2--;
        MineListNode* prevIndex1Node = nullptr;
        MineListNode* prevIndex2Node = nullptr;
        MineListNode* index1Node = nullptr;
        MineListNode* index2Node = nullptr;
 
        int index = 0;
 
        if (index1 < 0)
        {
            index1Node = _head;
        }
        if (index2 < 0)
        {
            index2Node = _head;
        }
 
        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++;
        }
 
        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;
            index2Node->next = index1Node->next;
 
            prevIndex2Node->next = index1Node;
            index1Node->next = temp;
            _head = index2Node;
        }
        else if (prevIndex2Node == nullptr)
        {
            temp = index2Node->next;
            prevIndex1Node->next = index2Node;
            index2Node->next = index1Node->next;
 
            index1Node->next = temp;
            _head = index1Node;
        }
    }
};
 
 
void main()
{
    MineList mineList;
    int c = 100;
    while (--c >= 0)
    {
        mineList.pushBeginData(Data(c));
    }
 
    std::cout << " --------------- " << std::endl;
    mineList.printList();
    mineList.swapListNodeByIndex(3, 0);
    std::cout << " --------------- " << std::endl;
    mineList.printList();
 
    system("pause");
}

@Dennis Ritchie · 21.11.2014, 22:39 **[ТС]**

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

Давно я своих листов не писал )))

Спасибо за код ))) Отличная работа!

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

Думаю вы разберётесь и без комментариев.

Не знаю насчёт, как разберусь, но из отладчика придётся долго не вылезать...

@Nosey · 21.11.2014, 22:52

Dennis Ritchie, Очень советую приложить к отладчику ручку и бумажку

и всё станет легче.

@Dennis Ritchie · 21.11.2014, 22:57 **[ТС]**

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

Dennis Ritchie, Очень советую приложить к отладчику ручку и бумажку

и всё станет легче.

У меня всегда лежит ручка и бумажка перед ноутбуком.

@TheCalligrapher · 21.11.2014, 23:37

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

Думаю вы разберётесь и без комментариев.

Я бы реализовал ваш 'swapListNodeByIndex' так. Мой код короче и более трудночитаем. Сплошные премущества!

C++

  void swapListNodeByIndex(int index1, int index2)
  {
    if (index1 > index2)
      std::swap(index1, index2);
 
    if (index1 < 0 || index1 == index2)
      return;
 
    MineListNode **pn = &_head;
    int index = 0;
 
    for (; index < index1 && *pn != nullptr; ++index, pn = &(*pn)->next);
 
    MineListNode **pn1 = pn;
    if (*pn1 == nullptr)
      return;
 
    for (; index < index2 && *pn != nullptr; ++index, pn = &(*pn)->next);
 
    MineListNode **pn2 = pn;
    if (*pn2 == nullptr)
      return;
 
    if ((*pn1)->next != *pn2)
    {
      std::swap((*pn1)->next, (*pn2)->next);
      std::swap(*pn1, *pn2);
    }
    else
    {
      MineListNode *n3 = (*pn2)->next;
      (*pn2)->next = *pn1;
      *pn1 = *pn2;
      *pn2 = n3;
    }
  }

@Nosey · 21.11.2014, 23:49

Не по теме:

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

Я бы реализовал ваш 'swapListNodeByIndex' так. Мой код короче и более трудночитаем. Сплошные премущества!

Сто грамм, этому господину от меня и бутылку рома от преподавателя который получит целый час весёлого настроения слушая от половины группы объяснение как они это реализовали :)

@TheCalligrapher · 22.11.2014, 00:44

... но в общем и целом работа со списком через двойной указатель (как 'MineListNode **') позволяет вам в большинстве случаев избавиться о необходимости рассматривать работу с самым первым элементом списка, как особую ситуацию.

Вот в данном случае в коде Nosey эти 'if (prevIndex1Node == nullptr)' приходится выписывать именно потому, что первый элемент необходимо обрабатывать особо. А вот в моем варианте таких 'if'ов нет.

@Nosey · 22.11.2014, 01:31

TheCalligrapher, Да, спасибо большое. Я пока новенький в плюсах, и теперь ещё один фокус с "**" в голову положил. Спасибо

@Kuzia domovenok · 22.11.2014, 01:58

Nosey, абсолютно неграмотный свап для списка. А если у меня в списке хранятся структуры по несколько мегабайт? Так и будешь копировать их по значению swapом? Не для того указатели и списки придумали!

короче, тему не читал. Прочёл до 6го коммента - полностью с ним согласен.

@Nosey · 22.11.2014, 02:27

Kuzia domovenok

Не по теме:

В деревне построили вышку сотовой связи. Через месяц население подало жалобу, мол у населения головные боли, ухудшение самочувствия, работоспособности и т.д. и т.п.
Ответ директора оператора сотовой связи:
- Фигня всё это. Вы только представьте, что будет, когда мы её включим...

Так вот, вы только представьте глаза преподавателя который увидит девочку божий-одуванчик рассказывающую что она накатала шаблон листа

И я что-то не понимаю, где же копирование при свапе? Я даже проверился, вдруг я и правда что-то не учёл

А если же вы, не про свап говорили, а про

C++

void pushBeginData(Data& data)
    {
        MineListNode* head = new MineListNode();
        head->data = data;
        head->next = _head;
        _head = head;
    }

То да, стоит писать шаблоны и оставлять на совесть использующего.

@Kuzia domovenok · 22.11.2014, 11:02

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

Так вот, вы только представьте глаза преподавателя который увидит девочку божий-одуванчик рассказывающую что она накатала шаблон листа

как-бэ преподаватель ей это и задал. Хотел бы препод увидеть банальное swap(a,b) - никакой бы "задачи" из этого не выросло. В этом и суть изучения списков - программист должен понимать их настолько, чтобы самому ими пользоваться легко было.
+ ты преувеличиваешь сложность списков. В школьном курсе Си они изучаются не более чем через полгода после начала изучения программирования с полного нуля.
+ возвращаясь к тому, что программист должен понимать списки. У списков, в отличие от массивов, есть очень важное свойство. В них операции вставки и удаления никогда не приводят к появлению недействительных итераторов, указателей и ссылок (если они не относятся к удаляемым элементам). В общем случае операции вставки и удаления в блоковых контейнерах(массивах, векторах...) могут привести к тому, что все итераторы, указатели и ссылки станут недействительными. А в списках - нет. Твоя идея со свапом всё это портит!

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

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

И я что-то не понимаю, где же копирование при свапе?

тута

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

std::swap(*data1, *data2);

@Dennis Ritchie · 22.11.2014, 12:01 **[ТС]**

Nosey, препод быстро сломал вашу программу. Попробуйте ввести размер списка c = 2 и поменять нулевой элемент с первым. С функцией от TheCalligrapher всё работает, но я ещё не показывал эту программу.

@Nosey · 22.11.2014, 17:19

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

C++

    void swapListNodeByIndex(int index1, int index2)
    {
        index1--;
        index2--;
        MineListNode* prevIndex1Node = nullptr;
        MineListNode* prevIndex2Node = nullptr;
        MineListNode* index1Node = nullptr;
        MineListNode* index2Node = nullptr;
 
        int index = 0;
 
        if (index1 < 0)
        {
            index1Node = _head;
        }
        if (index2 < 0)
        {
            index2Node = _head;
        }
 
 
        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++;
        }
 
        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;
        }
    }

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

Kuzia domovenok, Вы про первую версию, ну и стоит писать вот так и отдавать на откуп использующему:

C++

template <typename T>
struct Swap
{
    int ind1;
    int ind2;
    int curInd = 0;
    T* data1 = nullptr;
    T* data2 = nullptr;
    bool isSwap = false;
 
    void operator()(T& value)
    {
        if (isSwap)
        {
            return;
        }
        if (curInd == ind1)
        {
            data1 = &value;
        }
        else if (curInd == ind2)
        {
            data2 = &value;
        }
        if (data1 != nullptr && data2 != nullptr)
        {
            std::swap(*data1, *data2);
            isSwap = true;
        }
        curInd++;
    }
};

Но спасибо что заставляете думать

@Nosey 1379 / 406 / 144 Регистрация: 22.10.2014 Сообщений: 872
	22.11.2014, 01:31	15
	TheCalligrapher, Да, спасибо большое. Я пока новенький в плюсах, и теперь ещё один фокус с "**" в голову положил. Спасибо 0

@Kuzia domovenok 4064 / 3318 / 924 Регистрация: 25.03.2012 Сообщений: 12,495 Записей в блоге: 1
	22.11.2014, 01:58	16
	Nosey, абсолютно неграмотный свап для списка. А если у меня в списке хранятся структуры по несколько мегабайт? Так и будешь копировать их по значению swapом? Не для того указатели и списки придумали! короче, тему не читал. Прочёл до 6го коммента - полностью с ним согласен. 0

@Kuzia domovenok 4064 / 3318 / 924 Регистрация: 25.03.2012 Сообщений: 12,495 Записей в блоге: 1
	22.11.2014, 11:02	18
	Сообщение от Nosey Так вот, вы только представьте глаза преподавателя который увидит девочку божий-одуванчик рассказывающую что она накатала шаблон листа как-бэ преподаватель ей это и задал. Хотел бы препод увидеть банальное swap(a,b) - никакой бы "задачи" из этого не выросло. В этом и суть изучения списков - программист должен понимать их настолько, чтобы самому ими пользоваться легко было. + ты преувеличиваешь сложность списков. В школьном курсе Си они изучаются не более чем через полгода после начала изучения программирования с полного нуля. + возвращаясь к тому, что программист должен понимать списки. У списков, в отличие от массивов, есть очень важное свойство. В них операции вставки и удаления никогда не приводят к появлению недействительных итераторов, указателей и ссылок (если они не относятся к удаляемым элементам). В общем случае операции вставки и удаления в блоковых контейнерах(массивах, векторах...) могут привести к тому, что все итераторы, указатели и ссылки станут недействительными. А в списках - нет. Твоя идея со свапом всё это портит! Добавлено через 2 минуты Сообщение от Nosey И я что-то не понимаю, где же копирование при свапе? тута Сообщение от Nosey std::swap(data1, data2); 0

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

Решение

Решение

@Dennis Ritchie 555 / 148 / 58 Регистрация: 27.07.2014 Сообщений: 2,446
		1
	Поменять местами два элемента односвязного списка 21.11.2014, 19:19. Показов 13688. Ответов 28 Метки нет (Все метки) Дан односвязный список. Требуется напечатать исходный список. Поменять местами два элемента списка, номера которых введёт пользователь с клавиатуры. Напечатать получившийся список. 0

@Dennis Ritchie 555 / 148 / 58 Регистрация: 27.07.2014 Сообщений: 2,446
	21.11.2014, 20:10 [ТС]	3
	Nosey, огромное спасибо. А не могли бы вы прокомментировать код, чтобы легче разбираться было? 0

@Nosey 1379 / 406 / 144 Регистрация: 22.10.2014 Сообщений: 872
	21.11.2014, 20:17	4
	Dennis Ritchie, Да, могу. Что непонятно? Или зачем вам это задание понадобилось? Чтобы понять что рассказывать 0

@Dennis Ritchie 555 / 148 / 58 Регистрация: 27.07.2014 Сообщений: 2,446
	21.11.2014, 20:26 [ТС]	5
	Сообщение от Nosey Или зачем вам это задание понадобилось? Учусь в ВУЗ'е. Преподаватель уже замучил. Я знаю, что если я ему завтра покажу такой код, то он закидает меня вопросами с ног до головы. И в итоге скажет, чтобы я переписал код более просто или же объяснил работу этого кода. В общем, желательно прокомментировать в коде код структуры и код класса. Чем больше прокомментируете, тем лучше. Этот код поможет не только мне, если я смогу разобраться. 0

@TheCalligrapher Вездепух 11696 / 6375 / 1724 Регистрация: 18.10.2014 Сообщений: 16,071
	21.11.2014, 20:29	6
	Сообщение от Dennis Ritchie Поменять местами два элемента списка, Когда речь идет о списках, хранящих какие-то "полезные данные", задание "поменять местами два элемента" - неоднозначно. * Во-первых, в списке "поменять местами два элемента" можно путем перецепления ссылок на узлы списка. "Полезные данные" останутся на прежних местах в памяти, но порядок физических узлов в списке изменится. * Во-вторых, в списке "поменять местами два элемента" можно просто путем обмена "полезных данных", хранящихся в узлах, оставив ссылки нетронутыми. В таком случае наоборот, "полезные данные" обменяются в памяти, но порядок физических узлов в списке останется прежним. С точки зрения распечатки содержимого списка, результат будет одним и тем же в обоих случаях. Однако побочные эффекты этих вариантов различаются. Например, если у меня есть два посторонних внешних указателя на обмениваемые узлы списка, то в первом способе "полезные данные", видимые через эти указатели, останутся прежними. А во втором способе они тоже обменяются. О каком именно обмене идет речь? Второй способ, понятное дело, применим к любому контейнеру. Поэтому когда в задаче явно говорят о списке, то это зачастую является "намеком" именно на первый способ. 0

@Dennis Ritchie 555 / 148 / 58 Регистрация: 27.07.2014 Сообщений: 2,446
	21.11.2014, 20:34 [ТС]	7
	Сообщение от TheCalligrapher Так о каком именно обмене идет речь? Я это сам пытался понять, но так и не понял. Я предполагаю, что элементы нужно поменять путём перецепления ссылок на узлы списка. 0

@Dennis Ritchie 555 / 148 / 58 Регистрация: 27.07.2014 Сообщений: 2,446
	21.11.2014, 22:39 [ТС]	9
	Сообщение от Nosey Давно я своих листов не писал ))) Спасибо за код ))) Отличная работа! Сообщение от Nosey Думаю вы разберётесь и без комментариев. Не знаю насчёт, как разберусь, но из отладчика придётся долго не вылезать... 0

@Nosey 1379 / 406 / 144 Регистрация: 22.10.2014 Сообщений: 872
	21.11.2014, 22:52	10
	Dennis Ritchie, Очень советую приложить к отладчику ручку и бумажку и всё станет легче. 0

@Dennis Ritchie 555 / 148 / 58 Регистрация: 27.07.2014 Сообщений: 2,446
	21.11.2014, 22:57 [ТС]	11
	Сообщение от Nosey Dennis Ritchie, Очень советую приложить к отладчику ручку и бумажку и всё станет легче. У меня всегда лежит ручка и бумажка перед ноутбуком. 0

@Nosey
	21.11.2014, 23:49 #13
	Не по теме: Сообщение от TheCalligrapher Я бы реализовал ваш 'swapListNodeByIndex' так. Мой код короче и более трудночитаем. Сплошные премущества! Сто грамм, этому господину от меня и бутылку рома от преподавателя который получит целый час весёлого настроения слушая от половины группы объяснение как они это реализовали :) 0

@TheCalligrapher Вездепух 11696 / 6375 / 1724 Регистрация: 18.10.2014 Сообщений: 16,071
	22.11.2014, 00:44	14
	... но в общем и целом работа со списком через двойной указатель (как 'MineListNode ') позволяет вам в большинстве случаев избавиться о необходимости рассматривать работу с самым первым элементом списка, как особую ситуацию. Вот в данном случае в коде Nosey** эти 'if (prevIndex1Node == nullptr)' приходится выписывать именно потому, что первый элемент необходимо обрабатывать особо. А вот в моем варианте таких 'if'ов нет. 1

@Dennis Ritchie 555 / 148 / 58 Регистрация: 27.07.2014 Сообщений: 2,446
	22.11.2014, 12:01 [ТС]	19
	Nosey, препод быстро сломал вашу программу. Попробуйте ввести размер списка c = 2 и поменять нулевой элемент с первым. С функцией от TheCalligrapher всё работает, но я ещё не показывал эту программу. 0