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

@SkYMaaN · Регистрация: 05.04.2019

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

Есть следующая реализация односвязаного списка:

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-ов или и так адекватно? )

@SkYMaaN · 23.09.2020, 20:10 **[ТС]**

oleg-m1973, хочу переспросить за условие следующей функции ( именно из-за него удалялся не тот элемент ):

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template <typename T>
typename List<T>::Node* List<T>::find_previous(T data_)
{
        if (this->head->data==data_)
 
        {
            return nullptr;
        }
        else
        {
            Node* current = this->head;
            while (current->ptrNext && current->ptrNext->data != data_)
            {       
                current = current->ptrNext;
            }
            return current;
        }
}

C++
1
current->ptrNext->data != data_)

Если я не ошибаюсь, с таким условием сравниваются данные не от следующего от current элемента, а сравниваются от следующего от следующего от current элемента??
Я попробовал следующее условие:

C++
1
while (current->ptrNext && current->data != data_)

И ошибка с удалением элемента со значением 71 вместо элемента со значением 87 - ушла.

@oleg-m1973 · 23.09.2020, 20:18

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

Если я не ошибаюсь, с таким условием возвращаются данные не от следующего от current элемента, а возвращаются от следующего от следующего от current элемента??

Здесь всё правильно. Проверь

C++
1
2
3
auto *node = lst.find_previous(87);
std::cout << node->data << std::endl;
std::cout << node->ptrNext->data << std::endl;

Добавлено через 45 секунд
Покажи push_back и remove_next

@SkYMaaN · 23.09.2020, 20:24 **[ТС]**

Сообщение от oleg-m1973

Покажи push_back и remove_next

C++
1
2
3
4
5
6
7
8
9
10
11
12
template<class T>
void List<T>::remove_next(Node* ptr)
{   
    Node* current = this->head; 
    while (current->ptrNext != nullptr && current->ptrNext != ptr)
    {
        current = current->ptrNext;         
    }
    current->ptrNext = ptr->ptrNext;
    delete ptr;  
    size--;
}

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template<class T>
void List<T>::push_back(T data_)
{
    if (head == nullptr) 
    {
        head = new Node(data_);  
    }
    else  
    {
        Node* current = this->head;
        while (current->ptrNext != nullptr)
        {
            current = current->ptrNext; 
        }
    
        current->ptrNext = new Node(data_); 
    }
    size++;
}

@oleg-m1973 · 23.09.2020, 20:26

Скорее это происходит потому, что ты так и не исправил вот это

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

Node* current = this->head;
Node* ptrprevious = this->head;
while (current->ptrNext && current->ptrNext->data != data_)

@SkYMaaN · 23.09.2020, 20:27 **[ТС]**

Сообщение от oleg-m1973

std::cout << node->data << std::endl;

71

Сообщение от oleg-m1973

std::cout << node->ptrNext->data << std::endl;

87

@oleg-m1973 · 23.09.2020, 20:27

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

Node* current = this->head;
while (current->ptrNext != nullptr && current->ptrNext != ptr)

Это что за жесть?

@SkYMaaN · 23.09.2020, 20:28 **[ТС]**

Сообщение от oleg-m1973

Node* ptrprevious

такая переменная осталась только в функциях insert and erase , ещё не добрался до их исправления

@oleg-m1973 · 23.09.2020, 20:31

C++
1
2
3
4
5
6
7
8
9
10
11
template<class T>
void List<T>::remove_next(Node* node)
{   
    auto *p = node->ptrNext;
    if (p)
    {
        node->ptrNext = p->ptrNext;
        delete p;
        size--;
    }
}

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template<class T>
void List<T>::remove_next(Node* node)
{   
    if (!node)
    {
        auto p = head;
        head = head->ptrNext;
        delete p;
        size--;
    }
    else
    {
        auto *p = node->ptrNext;
        if (p)
        {
            node->ptrNext = p->ptrNext;
            delete p;
            size--;
        }
    }
}

@SkYMaaN · 23.09.2020, 20:39 **[ТС]**

Сообщение от oleg-m1973

if (!node)

Как это логически прочитать: "если указателя нету?" - find_previous - вернула nullptr потому что элемент первый?

Как до меня дошло, то вся эта страшная реализация заменяется парой строчек кода с использованием функций remove_next and find_previous?:

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
36
37
38
39
40
41
template<class T>
void List<T>::erase(const size_t index)
{
    size_t counter{ 0 };
        Node* current = this->head;
        Node* ptrprevious = this->head;
        while (current != nullptr)
        {
            if (counter == index-1)
            {
                if (index-1 == 0)
                {
                    this->head = current->ptrNext;
                    delete current;
                    size--;
                    break;
                }
                else if (index-1 == this->getSize())
                {
                    ptrprevious->ptrNext = nullptr;
                    delete current;
                    size--;
                    break;
                }
                else
                {
                    ptrprevious->ptrNext = current->ptrNext;
                    delete current;
                    size--;
                    break;
                }
            }
            else
            {
                ptrprevious = current;
                current = current->ptrNext;
                counter++;
            }
 
        }
}

@oleg-m1973 · 23.09.2020, 20:59

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

Как это логически прочитать: "если указателя нету?" - find_previous - вернула nullptr потому что элемент первый?

Ну да, if (node == nullptr)
Иначе каким образом ты собираешься указать на элемент предыдущий первому?

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

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

Как до меня дошло, то вся эта страшная реализация заменяется парой строчек кода с использованием функций remove_next and find_previous?:

Ну да, только параметр find_prev нужен другой. Лучше там сделать предикат

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 <typename T> template <typename TFunc>
typename List<T>::Node* List<T>::find_prev_if(TFunc &&pred)
{
    if (head->data==data_)
        return nullptr;
 
    Node* current = this->head;
    while (current->ptrNext && !pred(current->ptrNext->data))
    {       
        current = current->ptrNext;
    }
    return current;
}
 
template <typename T>
typename List<T>::Node* List<T>::find_prev(const T &data)
{
    return find_prev_if([&data](const T &val)
    {
        return data == val;
    });
}
 
template<class T>
void List<T>::erase(size_t index)
{
    auto *node = find_prev_if([&index](const T &val)
    {
        return (index--) == 0;
    });
 
    remove_next(node);
}

IGPIGP · 24.09.2020, 01:22

del

@oleg-m1973 · 24.09.2020, 12:02

Сообщение от oleg-m1973

template <typename T> template <typename TFunc>
typename List<T>::Node* List<T>::find_prev_if(TFunc &&pred)
{
if (head->data==data_)
return nullptr;

Да, здесь ошибся

C++
1
2
    if (pred(head->data))
        return nullptr;

IGPIGP · 24.09.2020, 17:58

Сообщение от oleg-m1973

Да, здесь ошибся

Идея с предикатом реализуема, но связывает контейнер некоторыми знаниями о контенте. Впрочем, это возможно. Тогда имело бы смысл сделать предикат параметром шаблона (со значением по умолчанию std::equal_to<T> ). Но тогда, это бинарная функция. Может я не понял, что происходит?

Не по теме:

и жуть как хочется увидеть шаблонный класс слинкованный как DLL

@oleg-m1973 · 24.09.2020, 19:11

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

Тогда имело бы смысл сделать предикат параметром шаблона (со значением по умолчанию std::equal_to<T> )

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

C++
1
2
3
4
5
6
template <typename T> template <typename TFunc, typename... TT>
typename List<T>::Node* List<T>::find_prev_if(TFunc &&pred, TT&&... args)
{
    if (std::invoke(pred, args..., head->data))
        return nullptr;
................................................

Тогда

C++
1
lst.find_prev_if(std::equal_to<int>(), 123);

IGPIGP · 24.09.2020, 19:28

Сообщение от oleg-m1973

Нет, в функциях предикаты не делают параметром шаблона

Нет. Делают. И в функциях и в классах. В std::sort например. Но говорить в тоне Да/Нет/Не делают не хочу. Жалею что вмешался.

@oleg-m1973 · 24.09.2020, 19:32

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

Нет. Делают. И в функциях и в классах. В std::sort например.

В std::sort сделано так же, как у меня

IGPIGP · 24.09.2020, 19:47

Сообщение от oleg-m1973

В std::sort сделано так же, как у меня

Так делают или нет?

Сообщение от oleg-m1973

Нет, в функциях предикаты не делают параметром шаблона

и почему унарный? Будет вставлять перед чётными элементами?

@oleg-m1973 · 24.09.2020, 19:53

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

Так делают или нет?

В классах предикат всегда параметр шаблона. В функциях - всегда обычный параметр.

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

и почему унарный? Будет вставлять перед чётными элементами?

Я ж показал выше, как делаю обычно

Сообщение от oleg-m1973

emplate <typename T> template <typename TFunc, typename... TT>
typename List<T>::Node* List<T>::find_prev_if(TFunc &&pred, TT&&... args)

Где ты здесь видишь унарный?

IGPIGP · 24.09.2020, 20:00

Сообщение от oleg-m1973

В классах предикат всегда параметр шаблона. В функциях - всегда обычный параметр.

В функции std::sort - параметр шаблона:
https://en.cppreference.com/w/cpp/algorithm/sort
//третий вариант

C++
1
2
template< class RandomIt, class Compare >
void sort( RandomIt first, RandomIt last, Compare comp );

Сообщение от oleg-m1973

Я ж показал выше, как делаю обычно

Но это же не значит, что всегда и все?

Сообщение от oleg-m1973

Где ты здесь видишь унарный?

Они вызываются как унарные. Или нет?
Вот:

Сообщение от oleg-m1973

Да, здесь ошибся

C++
1
2
if (pred(head->data))
 return nullptr;

и вот:

Сообщение от oleg-m1973

C++
1
while (current->ptrNext && !pred(current->ptrNext->data))

@oleg-m1973 · 24.09.2020, 20:07

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

В функции std::sort - параметр шаблона:

А у меня тогда какой, по-твоему?

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

Они вызываются как унарные. Или нет?

Сообщение от oleg-m1973

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

Сообщение от oleg-m1973

template <typename T>
template <typename TFunc, typename... TT>
typename List<T>::Node* List<T>::find_prev_if(TFunc &&pred, TT&&... args)
{
if (std::invoke(pred, args..., head->data))
return nullptr;

Сообщение от oleg-m1973

Тогда
C++Выделить код
1
lst.find_prev_if(std::equal_to<int>(), 123);

Добавлено через 4 минуты
Параметр шаблона:

C++
1
2
3
4
template <int Val> func1() {}
func<123>();
template <typename T> func1() {}
func<int>();

Обычный параметр

C++
1
2
template <typename T> func2(T &&val) {}
func2(123);

Новые блоги и статьи Все статьи Все блоги /
GitDOS: Когда я решил скрестить MS-DOS, GitHub и Claude MaGz GoLd 08.07.2026 Привет, Киберфорум! Хочу поделиться своим проектом, который, надеюсь, вас заинтересует. GitDOS — это веб-приложение, которое позволяет запускать DOS в браузере с тремя крутыми фичами: диски живут в. . .	Учебный мини "цифровой двойник" = (Сервер = Java + Flask_питон )+(3D = Гугловскаая 4T nvideo + google colab) +( WMS = Odoo на Docker) anaschu 07.07.2026 Увидел в требованиях к вакансии создателя имитационных моделей связку (REst + Api + WMS + Anylogic + питон + 3D Nvideo), и решил посмотреть, что это такое. Из этого всего я работал более менее. . .	Море в объективе 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 Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .

IGPIGP Комп_Оратор) $Эксперт по математике/физике$ 9007 / 4708 / 630 Регистрация: 04.12.2011 Сообщений: 14,003 Записей в блоге: 16
	24.09.2020, 01:22
	del 0