Аватар для SkYMaaN
25 / 19 / 9
Регистрация: 05.04.2019
Сообщений: 338

Реализация функций erase,insert,clear - для односвязного списка

17.09.2020, 04:36. Показов 13184. Ответов 133
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Есть следующая реализация односвязаного списка:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class List
{
private:
    size_t size;
    //------------------------------
        template<class T>
        class Node
        {
        public:
            Node* ptrNext;
            T data;
            Node(T data_ = T(), Node* ptrNext_ = nullptr)
            {
                this->data = data_;
                this->ptrNext = ptrNext_;
            }
        };
    //------------------------------
public:
    List();
    ~List();    
    Node<T>* head;
    void push_back(T data_);
    void erase(const size_t index);
    void insert(const size_t position, T date_);
    void clear();
    void lout();
    int getSize() { return size; };
    void randIntInit(size_t count,int min,int max);
    T& operator[](const size_t index);
    
};
И есть следующие функции написанные мною без заглядывания в любой источник знаний:

erase - удаление
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
template<class T>
void List<T>::erase(const size_t index)
{
        size_t counter{ 0 };
        Node<T>* current = this->head;
        Node<T>* ptrprevious = this->head;
        while (current != nullptr)
        {
            if (counter == index-1)
            {
                if (index-1 == 0)
                {
                    this->head = current->ptrNext;
                    delete current;
                    size--;
                    break;
                }
                else
                {
                    ptrprevious->ptrNext = current->ptrNext;
                    delete current;
                    size--;
                    break;
                }
            }
            else
            {
                ptrprevious = current;
                current = current->ptrNext;
                counter++;
            }
 
        }
}
//------------------------------
lout - вывод
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template<class T>
void List<T>::lout()
{   
    if (this->getSize()>0)
    {
        cout << "List elements count: " << this->getSize() << endl;
        Node<T>* current = this->head;
        size_t fakesize{ 1 };
        while (current != nullptr)
        {
            cout << fakesize << "::" << current->data << endl;
            current = current->ptrNext;
            fakesize++;
        }
        cout << endl;
    }
    else
    {
        cout << "List empty!" << endl;
    }
}
//------------------------------
clear - полная очистка
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<class T>
void List<T>::clear()
{
    Node<T>* current = this->head;
    Node<T>* ptrprevious = this->head;
    while (current != nullptr)
    {   
        ptrprevious = current;
        current = current->ptrNext;
        delete ptrprevious;
        size--;
    }
}
//------------------------------
insert - вставка на позицию
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
template<class T>
void List<T>::insert(const size_t position, T date_)
{
    Node<T>* current = this->head;
    Node<T>* ptrprevious = this->head;
    size_t counter{ 0 };
    while (current != nullptr)
    {
        if (counter == position-1)
        {
            if (position == 1)
            {
                this->head = new Node<T>(date_);
                this->head->ptrNext = ptrprevious;
                size++;
                break;
            }
            else
            {
                Node<T>* NewNode = new Node<T>(date_, current);
                ptrprevious->ptrNext = NewNode;
                size++;
                break;
            }
        }
        else
        {
            ptrprevious = current;
            current = current->ptrNext;
            counter++;
        }
    }
}
В функциях я натыкал как чувствую - лишних операторов if:
В функции erase оператор if нужен чтобы определить когда пытаются удалить первый элемент и изменить реализацию удаления.
В функции insert оператор if нужен чтобы определить когда пытаются добавить элемент в начало списка и "сдвинуть" список с заменой главного элемента.
В функции lout ( вывод ) оператор if нужен чтобы определить когда список пустой.



Это допустимая/нормальная реализация этих функций или нужно их изменить? ( Можно ли сделать красивее без такого количества if-ов или и так адекватно? )
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
17.09.2020, 04:36
Ответы с готовыми решениями:

Метод insert и erase для шаблонного класса списка
Всем привет. Подскажите как реализовать методы добавления и удаление элемента из указанной позиции в односвязном списке Вот мое удаление:...

Реализация функций reserve и clear для вектора
Мне нужно самой написать реализацию. От что у меня есть: template&lt;typename T&gt; void Vector&lt;T&gt;::PopBack() { mVector.~T(); ...

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

133
Комп_Оратор)
Эксперт по математике/физике
 Аватар для IGPIGP
9007 / 4708 / 630
Регистрация: 04.12.2011
Сообщений: 14,003
Записей в блоге: 16
27.09.2020, 15:10
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от SkYMaaN Посмотреть сообщение
C++
1
2
3
4
5
void List<T>::insert_after(Node* position,const T &data_)
 {
 if (!position)
 {
 head = new Node(data_, head);
То есть, если кому-то захочется перадать ноль у вас утечёт вес список и умрут все данные?
0
 Аватар для SkYMaaN
25 / 19 / 9
Регистрация: 05.04.2019
Сообщений: 338
27.09.2020, 15:13  [ТС]
Цитата Сообщение от IGPIGP Посмотреть сообщение
утечёт вес список и умрут все данные
нет, всё отлично
Миниатюры
Реализация функций erase,insert,clear - для односвязного списка  
0
 Аватар для SkYMaaN
25 / 19 / 9
Регистрация: 05.04.2019
Сообщений: 338
27.09.2020, 15:20  [ТС]
Если я неверно понял вопрос?
У пользователя нету доступа к функции insert_after, она в private секции и используется внутри функции insert
0
Комп_Оратор)
Эксперт по математике/физике
 Аватар для IGPIGP
9007 / 4708 / 630
Регистрация: 04.12.2011
Сообщений: 14,003
Записей в блоге: 16
27.09.2020, 15:24
Цитата Сообщение от SkYMaaN Посмотреть сообщение
Если я неверно понял вопрос?
У пользователя нету доступа к функции insert_after, она в private секции и используется внутри функции insert
Этого не ожидал. Тогда может и нормально всё. Легче всё-таки проверить а не ноль ли head? Где-то же вы создадите список? А уже потом будете его методом-членом втыкать ему в голову? Иначе вы создаёте себе и всем кому захочется поддержать, квест. Впрочем, если в private - хозяин-барин.
1
6772 / 4565 / 1844
Регистрация: 07.05.2019
Сообщений: 13,726
27.09.2020, 15:30
Цитата Сообщение от SkYMaaN Посмотреть сообщение
Вот что вышло в итоге, стоит что изменить или это уже похоже на правду?:
Ну, если исключить то, что в списках не должно быть операций для доступа по индексу, а в односвязном списке (в твоём варианте) не должно быть метода push_back, то что уже более-менее похожее.
0
 Аватар для SkYMaaN
25 / 19 / 9
Регистрация: 05.04.2019
Сообщений: 338
27.09.2020, 15:32  [ТС]
IGPIGP, если я правильно понял ваше замечание:
C++
1
if (!position)
Цитата Сообщение от SkYMaaN Посмотреть сообщение
Как это логически прочитать: "если указателя нету?" - find_previous - вернула nullptr потому что элемент первый и перед ним соответственно ничего нету, значит добавлять в начало
0
6772 / 4565 / 1844
Регистрация: 07.05.2019
Сообщений: 13,726
27.09.2020, 15:32
Цитата Сообщение от SkYMaaN Посмотреть сообщение
Node* find_previous(const T &data_);
            template<typename TFunc>
            Node* find_previous_if(TFunc&& predicat);
            void remove_next(Node* previousobj);
            void push_begin(const T &data_);
            void insert_after(Node* pos, const T& data_);
И не надо делать эти методы приватными. Это основные операции для работы с односвязным списком.
1
 Аватар для SkYMaaN
25 / 19 / 9
Регистрация: 05.04.2019
Сообщений: 338
27.09.2020, 15:35  [ТС]
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
Ну, если исключить то, что в списках не должно быть операций для доступа по индексу, а в односвязном списке (в твоём варианте) не должно быть метода push_back
Тобиж единственный способ добавления элемента в список это вставка в начало, как уже писал IGPIGP, , верно? Остальных способов добавления лучше не делать даже?

Руководствовался методами из реализации List STL
0
6772 / 4565 / 1844
Регистрация: 07.05.2019
Сообщений: 13,726
27.09.2020, 15:38
Цитата Сообщение от SkYMaaN Посмотреть сообщение
Тобиж единственный способ добавления элемента в список это вставка в начало, как уже писал IGPIGP, , верно? Остальных способов добавления лучше не делать даже?
Это единственный эффективный способ. Для других нужно использовать find_prev и insert_afer. Т.е. все другие способы - производные, которые можно не делать в виде методов
1
 Аватар для SkYMaaN
25 / 19 / 9
Регистрация: 05.04.2019
Сообщений: 338
27.09.2020, 15:39  [ТС]
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
И не надо делать эти методы приватными
Не может возникнуть ситуация когда пользователь вызывает один из выше перечисленных методов и ломает его работу неправильно переданными данными?
0
6772 / 4565 / 1844
Регистрация: 07.05.2019
Сообщений: 13,726
27.09.2020, 15:42
Для push_back нужно, чтобы в твоём списке кроме указателя на первый элемент, Node *head, был ещё указатель на последний элемент Node *tail

Добавлено через 1 минуту
Цитата Сообщение от SkYMaaN Посмотреть сообщение
Не может возникнуть ситуация когда пользователь вызывает один из выше перечисленных методов и ломает его работу неправильно переданными данными?
Ну, сам будет виноват. Ты решил сделать защиту от дурака? Не рекомендую этим заниматься.

Добавлено через 49 секунд
Во-первых, не сделаешь. Во-вторых, у тебя и без этого конь не валялся
1
 Аватар для SkYMaaN
25 / 19 / 9
Регистрация: 05.04.2019
Сообщений: 338
27.09.2020, 15:44  [ТС]
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
был ещё указатель на последний элемент
это из соображений производительности? чтобы не проходить в цикле весь список?
0
6772 / 4565 / 1844
Регистрация: 07.05.2019
Сообщений: 13,726
27.09.2020, 15:46
Цитата Сообщение от SkYMaaN Посмотреть сообщение
это из соображений производительности? чтобы не проходить в цикле весь список?
Само собой
1
Комп_Оратор)
Эксперт по математике/физике
 Аватар для IGPIGP
9007 / 4708 / 630
Регистрация: 04.12.2011
Сообщений: 14,003
Записей в блоге: 16
27.09.2020, 20:10
Цитата Сообщение от SkYMaaN Посмотреть сообщение
IGPIGP, если я правильно понял ваше замечание:
C++
Это если бы вы делали упорядочивающие вставки было бы удобно. Но и там find_previous лучше бы вызвать внутри insert. И искать предыдущий - да. И полученный по искомому значению указатель - там внутри юзать. А метод find возвращающий указатель - прямо на найденный в интерфейсе должен быть. Итераторов вы пока не умеете, значит указатель придётся дать юзеру. Если вы кроме головоеда что-то планируете. Тут уж ни чего не сделаешь. Только указатель на нод связывает данные и список. А уж если юзер заделетит указатель то... указатель на то и указатель, чтобы мозг работал. Любой сырой указатель можно взорвать.
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
27.09.2020, 20:10

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

Реализация односвязного списка c++
Пытаюсь разобраться в том как работают списки , но ничего не компилируется , помогите найти ошибку . template&lt;typename T&gt; ...

Нужна реализация односвязного списка
Народ спасайте! Возможно у кого-то есть реализация простого списка, или знает кто какую статью на эту тему, или книгу какую по АТД! У меня...

Реализация односвязного списка (конструктор)
Доброго времени суток. Вот реализую односвязный список, застрял на конструкторе который принимает два итератора: List(iterator b,...

Реализация односвязного списка через классы
Реализую односвязный список, но почему-то на перегрузке оператора индексирования вызывается ошибка в форме &quot;несоответствие в списке...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
134
Ответ Создать тему
Опции темы

Новые блоги и статьи
Установка MinGW GCC 16.2 и CMake
8Observer8 10.08.2026
VK Видео: https:/ / vkvideo. ru/ video-240781534_456239017 YouTube: eY5-5PyI9NM Текстовая версия
Неделя из жизни имитационной модели склада: мои кривые руки растут, откуда надо
anaschu 10.08.2026
Неделя из жизни имитационной модели склада: как я почти написал неправильную логику и что с этим делать Работаю сейчас над учебно-рабочим проектом: строю в AnyLogic имитационную модель процессов. . .
Калькулятор для расчета родства
russiannick 07.08.2026
1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь
Мир по моей воле
kumehtar 07.08.2026
Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .
Кредитный калькулятор
Maks 05.08.2026
Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .
У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35".
kumehtar 04.08.2026
С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .
Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники).
Hrethgir 04.08.2026
Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .
Термопринтер QR701
Argus19 03.08.2026
Термопринтер QR701 Купил два термопринтера QR701. На сэлф-тесте написано: Language: PC936 (GB18030). Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru