Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.60/55: Рейтинг темы: голосов - 55, средняя оценка - 4.60
 Аватар для SkYMaaN
25 / 19 / 9
Регистрация: 05.04.2019
Сообщений: 338

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

17.09.2020, 04:36. Показов 13023. Ответов 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
Ответ Создать тему
Новые блоги и статьи
Море в объективе
kumehtar 06.07.2026
Хотел написать много проникновенных слов, но передумал. Оно само - говорит. Кто слышит тот слышит.
Doom для терминала без стрельбы и монстров. 3D Raycasting на ascii.
dcc0 05.07.2026
Попросил нейронную сеть deepai. org написать рейкастинг 3D с библиотекой ncurses для Linux. Чтобы можно было ходить на стрелочки. Чтобы стены были отрисованы символами. Справилась. Первый вариант. . .
Установка статуса документа по условию
Maks 05.07.2026
Алгоритм из решения ниже реализован на нетиповом документе "НарядПутевка" разработанного в КА2. Задача: в табличной части "Материалы" документа при записи автоматически устанавливать статус. . .
Сезонность и суточность закисления почв
anaschu 04.07.2026
200 часов это все равно моловато. Есть ситуации, но нестандартные, когда смена происходит за 5 лет. Но обычно это 50 лет и более. Наверное, закисление почвы происходит сезонно в средней. . .
В чем ценность человеческого опыта в глобальном смысле?
kumehtar 03.07.2026
Возможно, ценность человека не в том, что он однажды достигает мудрости, а в том, что он становится носителем карты пути. Он знает не только истину, но и последовательность внутренних изменений,. . .
интеграция AnyLogic с самописным REST API и переход на Odoo
anaschu 03.07.2026
Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .
Поиск всех путей на ориентированном графе. Linux
dcc0 02.07.2026
Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .
Сам себя обучал rest api
anaschu 02.07.2026
Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru