VPF::Удалить повторяющиеся элементы списка

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. При ее вызове происходит сегфолт. Так как у меня на старый ноут не устанавливается студия с отладчиком и я собираю программу в сигвине, отлаживать тут тяжело, поэтому я пытаюсь воспользоваться своим хрустальным шаром и найти ошибку глазами, но не получается. Помогите определить, где используется нулевой указатель или что-то еще вредное.

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: больше ничего не смотрел

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 считать элемент обработанным.

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