Модераторы: JackYF, bsa
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Удалить повторяющиеся элементы списка 
:(
    Опции темы
Aoizora
Дата 25.2.2017, 22:22 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 24
Регистрация: 18.11.2016

Репутация: нет
Всего: нет



Есть односвязный список, нужно удалить из него все элементы, которые встречаются более одного раза. Расстояние между повторяющимися элементами любое. Для решения задачи я использовал хеш-таблицу:

Код

#include <iostream>
#include <set>

template<typename T>
struct node
{
    T data;
    struct node *next;
    node(T data) : data(data), next(nullptr) {}
};

template<typename T>
class list
{
private:
    node<T> *head;
public:
    list() : head(nullptr) {}
    void insert(T data);
    void remove(T data);
    void show(void);
    void remove_dups(void);
};

template<typename T>
void list<T>::insert(T data)
{
    node<T> *tail = new node<T>(data);
    if (head == nullptr)
    {
        head = tail;
        return;
    }
    node<T> *iter = head;
    while (iter->next)
    {
        iter = iter->next;
    }
    iter->next = tail;
}

template<typename T>
void list<T>::remove(T data)
{
    node<T> *iter = head;

    if (!iter) return;    

    if (iter->data == data)
    {
        head = head->next;
        delete iter;
        return;
    }

    while (iter->next)
    {
        if (iter->next->data == data)
        {
            node<T> *next = iter->next;
            iter->next = iter->next->next;
            delete next;
            return;
        }
        iter = iter->next;
    }

        
template<typename T>
void list<T>::show(void)
{
    node<T> *iter = head;
    while (iter)
    {
        std::cout << iter->data << std::endl;
        iter = iter->next;
    }
}    

template<typename T>
void list<T>::remove_dups(void)
{
    std::set<T> visited;
    node<T> *iter = head;
    node<T> *temp = nullptr;

    while (iter->next)
    {
        if (iter->next->data == *visited.find(iter->next->data))
        {
            temp = iter->next;
            iter->next = iter->next->next;
            delete temp;
        }
        else
        {
            visited.insert(iter->next->data);
        } 
        iter = iter->next;
    }
}

int main()
{
    list<int> ls;

    ls.insert(1);
    ls.insert(2);
    ls.insert(3);
    ls.insert(2);
    ls.insert(1);
    ls.insert(1);
    ls.insert(3);

    ls.show();

    ls.remove_dups();
    ls.show();

}


Интересующая процедура - remove_dups. При ее вызове происходит сегфолт. Так как у меня на старый ноут не устанавливается студия с отладчиком и я собираю программу в сигвине, отлаживать тут тяжело, поэтому я пытаюсь воспользоваться своим хрустальным шаром и найти ошибку глазами, но не получается. Помогите определить, где используется нулевой указатель или что-то еще вредное.
PM MAIL   Вверх
volatile
Дата 26.2.2017, 00:41 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 16
Всего: 85



Цитата(Aoizora @  25.2.2017,  22:22 Найти цитируемый пост)
 if (iter->next->data == *visited.find(iter->next->data))
разыменовывать .end() нельзя.
если не найдено, find возращает .end()
надо как-то так:
Код

  if (visited.end() != visited.find(iter->next->data))


ps: больше ничего не смотрел

PM MAIL   Вверх
azesmcar
Дата 26.2.2017, 18:57 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


uploading...
****


Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 52
Всего: 211



плюс к сказанному: head пропускается при поиске дубликатов. итерация начинается со второго элемента, а также для пустого списка будет segfault по той же самой причине.

Добавлено через 2 минуты и 25 секунд
также можно избежать повторного поиска в insert и find. функция std::set<T>::insert возвращает в паре флаг обозначающий успех вставки. Можно сразу пытаться вставить в set и в случае возвращения false считать элемент обработанным.
PM   Вверх
Google
  Дата 17.1.2020, 18:25 (ссылка)  





  Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "C/C++: Для новичков"
JackYF
bsa

Запрещается!

1. Публиковать ссылки на вскрытые компоненты

2. Обсуждать взлом компонентов и делиться вскрытыми компонентами

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


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, JackYF, bsa.

 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Для новичков | Следующая тема »


 




[ Время генерации скрипта: 0.0826 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.