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

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

17.09.2020, 04:36. Показов 13026. Ответов 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
24.09.2020, 20:11
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
А у меня тогда какой, по-твоему?
Я не говорил что он у тебя не такой. Я вообще не по мужикам. Я скобки чуть не там поставил:
Цитата Сообщение от IGPIGP Посмотреть сообщение
Тогда имело бы смысл сделать предикат параметром шаблона (со значением по умолчанию std::equal_to<T> )
имел ввиду:
Цитата Сообщение от IGPIGP Посмотреть сообщение
Тогда имело бы смысл сделать предикат параметром шаблона со значением по умолчанию std::equal_to<T>
То есть делают?
Биндингов и инвоуков не было там где я спрашивал о унарном.
oleg-m1973, толчём воду. Предлагаю просто остановиться.

Добавлено через 3 минуты
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
Параметр шаблона:
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
Обычный параметр
Это ни к чему, просто.
0
 Аватар для SkYMaaN
25 / 19 / 9
Регистрация: 05.04.2019
Сообщений: 338
25.09.2020, 02:17  [ТС]
Ознакомился я с тем что такое предикат. В моём случае предикаты должны иметь следующий вид для использования их в функции 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
template<class T>
    bool List<T>::predicat_is_previous_element(const Node &obj)
    {
        if (find_previous(obj))
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    //------------------------------
 
    template<class T>
    bool List<T>::predicat_if_data(const T &data_)
    {
        Node* current = this->head;
        while (current->ptrNext != nullptr)
        {
            if (current->ptrNext->data == data_)
            {
                return true;
            }
            else
            {
                current = current->ptrNext;
            }
        }
        return false;
    }
0
Комп_Оратор)
Эксперт по математике/физике
 Аватар для IGPIGP
9007 / 4708 / 630
Регистрация: 04.12.2011
Сообщений: 14,003
Записей в блоге: 16
25.09.2020, 10:05
Цитата Сообщение от SkYMaaN Посмотреть сообщение
Ознакомился я с тем что такое предикат.
Где нашли сведения?
0
6772 / 4565 / 1844
Регистрация: 07.05.2019
Сообщений: 13,726
25.09.2020, 13:19
Цитата Сообщение от SkYMaaN Посмотреть сообщение
Ознакомился я с тем что такое предикат. В моём случае предикаты должны иметь следующий вид для использования их в функции erase?
Предикат это функция, которая возвращает true/false, bool.
Я ж вроде показал, как нужно делать в https://www.cyberforum.ru/post14860927.html,
C++
1
2
template <typename T> template <typename TFunc>
typename List<T>::Node* List<T>::find_prev_if(TFunc &&pred)
pred - это предикат
0
Комп_Оратор)
Эксперт по математике/физике
 Аватар для IGPIGP
9007 / 4708 / 630
Регистрация: 04.12.2011
Сообщений: 14,003
Записей в блоге: 16
25.09.2020, 15:45
Там еще можно значение (целевое) передать. Легче искать, когда знаешь, что именно нужно бы найти. Потом проходя по элементам нужно передать предикату что-то из элемента и упомянутый аргумент. То есть, он бинарным должен бы быть, если не извращаться.
0
6772 / 4565 / 1844
Регистрация: 07.05.2019
Сообщений: 13,726
25.09.2020, 15:49
Цитата Сообщение от IGPIGP Посмотреть сообщение
То есть, он бинарным должен бы быть, если не извращаться.
В std::find_if унарный
0
Комп_Оратор)
Эксперт по математике/физике
 Аватар для IGPIGP
9007 / 4708 / 630
Регистрация: 04.12.2011
Сообщений: 14,003
Записей в блоге: 16
25.09.2020, 16:56
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
В std::find_if унарный
Дык я же и говорил, - все чётные легко понаходить будет
Цитата Сообщение от по ссылке
p - unary predicate which returns ​true for the required element.
а искать по значению, легче-таки, если есть значение. oleg-m1973, я не настаиваю. Кому-как легче) Предикат может иметь состояние и ему можно воткнуть что угодно. Включая значение. Тогда по умолчанию equal_to<T> не подойдёт. Да. Ну и бог с ним.
0
6772 / 4565 / 1844
Регистрация: 07.05.2019
Сообщений: 13,726
25.09.2020, 17:07
Цитата Сообщение от IGPIGP Посмотреть сообщение
а искать по значению, легче-таки, если есть значение. oleg-m1973, я не настаиваю. Кому-как легче)
Нет. При поиске унарный предикат сделан потому, что критерий поиска неизвестен. Там может понадобиться как один дополнительный параметр, так и два и три. Их достаточно легко передать через лямбду. Поэтому можно не заморачиваться.
Хотя по мне, как я и говорил, лучше в дополнение к предикату передавать ещё параметры. Не знаю, почему в стандартной библиотеке так не сделали.
При этом ни о каких "бинарных предикатах" речи как не шло, так и не идёт. Количество параметров от единицы до, скажем так, бесконечности.
0
Комп_Оратор)
Эксперт по математике/физике
 Аватар для IGPIGP
9007 / 4708 / 630
Регистрация: 04.12.2011
Сообщений: 14,003
Записей в блоге: 16
25.09.2020, 17:26
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
При этом ни о каких "бинарных предикатах" речи как не шло, так и не идёт.
У вас конечно. Вы же не просто признаёте:
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
Не знаю, почему в стандартной библиотеке так не сделали.
Вы же просто признаёте что не понимаете (понимаете, конечно, но делаете вид, что не понимаете о чем я говорю) почему для сортировок, множеств и словарей предикаты заданы как бинарные. Не будем же мы грузить ТС такими вещами как трихотомия и транзитивность, где равенство - один из видов сравнения. Оно, по правде говоря и не обязательно. ТС занят внедрением в dll целого контейнера. Я не против. Можно хоть
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
Количество параметров от единицы до, скажем так, бесконечности.
Хотя, когда что-то ищешь и у него уже определён оператор сравнения на равенство, писать предикат - на любителя. Но свобода - пуще неволи.
0
6772 / 4565 / 1844
Регистрация: 07.05.2019
Сообщений: 13,726
25.09.2020, 17:36
Цитата Сообщение от IGPIGP Посмотреть сообщение
Вы же просто признаёте что не понимаете почему для сортировок, множеств и словарей предикаты заданы как бинарные.
Для сортировки и т.д. предикаты бинарные, потому что внутри функции им необходимо передавать два параметра. При поиске внутри функции доступен и передаётся только один. Параметры, которые можно передать снаружи, при вызове std::sort или std::find_if, ни там не там не учитываются. Т.е. для сортировки достаточен и необходим бинарный предикат, для поиска достаточен и необходим унарный. Поэтому в стандартной библиотеке так и сделано. И поэтому я изначально и показал ТС именно такой вариант, как необходимый и достаточный.

По-моему, ты чего-то не понимаешь.
0
Комп_Оратор)
Эксперт по математике/физике
 Аватар для IGPIGP
9007 / 4708 / 630
Регистрация: 04.12.2011
Сообщений: 14,003
Записей в блоге: 16
25.09.2020, 18:48
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
По-моему, ты чего-то не понимаешь.
Пускай.
0
 Аватар для SkYMaaN
25 / 19 / 9
Регистрация: 05.04.2019
Сообщений: 338
25.09.2020, 19:01  [ТС]
Цитата Сообщение от IGPIGP Посмотреть сообщение
Где нашли сведения?
Видеоурок на ютубе ,SimpleCode - Предикаты С++"
"
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
pred - это предикат
Я понял. По вашему примеру и делал. Как я понял реализация "pred" должна быть подобна такой?:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template<class T>
    bool List<T>::predicat_if_data(const T &data_)
    {
        Node* current = this->head;
        while (current->ptrNext != nullptr)
        {
            if (current->ptrNext->data == data_)
            {
                return true;
            }
            else
            {
                current = current->ptrNext;
            }
        }
        return false;
    }
Добавлено через 5 минут
Возвращать true/false - в зависимости от наличия данных
0
6772 / 4565 / 1844
Регистрация: 07.05.2019
Сообщений: 13,726
25.09.2020, 19:30
Цитата Сообщение от SkYMaaN Посмотреть сообщение
понял. По вашему примеру и делал. Как я понял реализация "pred" должна быть подобна такой?:
Я ж тебе показало там реализацию предикатов для поиска по значению
C++
1
2
3
4
[&data](const T &val)
    {
        return data == val;
    }
и для поиску по индексу
C++
1
2
3
4
[&index](const T &val)
    {
        return (index--) == 0;
    }
Это и есть те самые предикаты.

Что ты ещё пытаешься сделать?
0
Комп_Оратор)
Эксперт по математике/физике
 Аватар для IGPIGP
9007 / 4708 / 630
Регистрация: 04.12.2011
Сообщений: 14,003
Записей в блоге: 16
25.09.2020, 19:39
Цитата Сообщение от SkYMaaN Посмотреть сообщение
Возвращать true/false - в зависимости от наличия данных
Вам предложено поисковое условие сделать полностью собственностью предиката. То есть, искомый элемент или поле функтора или захватываемый из контекста элемент (что то же самое). Нормальные герои всегда идут в обход. Зато изучите функторы и лямбды попутно. Рыбы придётся съесть больше (совет от Г. Шилдта). В рыбе фосфор.
0
 Аватар для SkYMaaN
25 / 19 / 9
Регистрация: 05.04.2019
Сообщений: 338
25.09.2020, 20:03  [ТС]
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
пытаешься сделать
Понять, и написать самому но понимая ваш пример. Копируя готовое - я не вижу смысла в своей работе.
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
[&data](const T &val)
это аргумент для предиката
C++
1
find_prev_if(TFunc &&pred)
как я понимаю, но для одного параметра там два аргумента!?
C++
1
[&data]
- это ссылка на объект типа Node?
C++
1
const T &val
- ссылка на поле data объекта типа Node?
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
return data == val;
( возвратит data если data == val? )
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
return (index--) == 0;
( возвратит -1 от значения index если index == 0? -1 тобиж? )
т
0
6772 / 4565 / 1844
Регистрация: 07.05.2019
Сообщений: 13,726
25.09.2020, 20:08
Цитата Сообщение от SkYMaaN Посмотреть сообщение
как я понимаю, но он "двойной"?
Это лямбда-функции
https://habr.com/ru/post/66021/
https://en.cppreference.com/w/cpp/language/lambda
1
19501 / 10106 / 2461
Регистрация: 30.01.2014
Сообщений: 17,825
25.09.2020, 20:58
Цитата Сообщение от SkYMaaN Посмотреть сообщение
возвратит data если data == val?
возвратит bool: true или false.

Цитата Сообщение от SkYMaaN Посмотреть сообщение
return (index--) == 0;
возвратит bool: true или false.
0
 Аватар для SkYMaaN
25 / 19 / 9
Регистрация: 05.04.2019
Сообщений: 338
25.09.2020, 21:11  [ТС]
DrOffset,
Цитата Сообщение от DrOffset Посмотреть сообщение
возвратит bool: true или false.
если data == val?
0
19501 / 10106 / 2461
Регистрация: 30.01.2014
Сообщений: 17,825
25.09.2020, 21:13
Цитата Сообщение от SkYMaaN Посмотреть сообщение
data == val?
В этом выражении участвует оператор ==, который возвращает bool - результат сравнения data и val. Если data равно val, то вернется true, если не равно -- false.

Цитата Сообщение от SkYMaaN Посмотреть сообщение
return (index--) == 0;
Здесь точно так же.
1
 Аватар для SkYMaaN
25 / 19 / 9
Регистрация: 05.04.2019
Сообщений: 338
26.09.2020, 02:22  [ТС]
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);
}
Цитата Сообщение от DrOffset Посмотреть сообщение
C++
1
return (index--) == 0;
сначало переменная индекса уменьшается на 1, потом если значение переменной == 0, возвращается true?
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
[&data](const T &val)
Не могу отследить, а где присвоение значения &val? Сравнение data and val есть, а значение val откуда берётся?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
26.09.2020, 02:22

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
100
Ответ Создать тему
Новые блоги и статьи
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 Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru