Реализация односвязного списка c++ Часть 1 | Урок
HTML-код
- Опубликовано: 16 янв 2018
- В этом уроке мы начнём писать собственный односвязный список на языке программирования C++ с подробными пояснениями.
Односвязный список | Динамические структуры данных #1
Теория goo.gl/E5KrVi
Определение методов вне класса. Вынести функцию в из класса. Вынести описание метода вне класса. #89
goo.gl/gqh536
Шаблоны классов с++ примеры. Обобщенные классы. Изучение С++ для начинающих. Урок #126
goo.gl/U99h9t
✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅
Если вам нравятся мои уроки, вы хотите поддержать меня и развитие канала, то можете сделать это тут!=)
🔴🔴🔴 www.donationalerts.ru/r/simple...
или тут
🔴🔴🔴 / simplecode
✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅
Уроки по программированию
Наша группа ВК smplcode
Подписывайтесь на канал / @simplecodeit
Спасибо вам большое. Я сама студентка и нам сказали лабы писать на С++, теперь вся група смотрит вас и учиться. Вы хорошо рассказываете, понятно. Спасибо.
Пожалуйста!
+
@@SimpleCodeIT Сергей, подскажите, пожалуйста, в каком уроке появился синтаксис типа "current->pnext" или "current-> data" 20:34
@@user-mm8hc5uu1e Урок про указатель this №94.
Коротко: с прототипа класса к полям обращаемся через точку, с указателя через ->
Node current;
current.pNext;
Node *current;
current->pNext;
храни тебя господь, долгих тебе лет жизни, спасибо за огромнейший труд, на твоем канале довольно давно сижу, всю процедурку вместе с тобой прошел, почти все ООП, понял как работает односвязный список, спасибо тебе огромное, настоящий учитель)))))))))
*Cамый лучший способ сказать "спасибо" - поставить лайк и и поделиться уроком с друзьями. Это очень мотивирует создавать полезные уроки =)*
Зачем создавать шаблонный Node, когда он и так объявлен в шаблонном List. Тип T для всех будет один, разве нет?
нет
Миша Якименко я проверил, лишний шаблон не нужен
@@borisshabanov6702 у меня тоже так сработало, не пойму смысла Node делать шаблонным. В code::blocks вообще ошибку выдает.
Более того компилятор не запускает программу , так как не может понять параметр T, я пишу в code blocks, может в studio по другому
Памятник при жизни Сергею поставлю!!! Спасибо вам Сергей за ваши труды, здоровья вам и вашим близким, долгих лет жизни, и хороших людей рядом!!!
Спасибо за урок! Для учащихся - в процессе урока пишите код, на не понятных моментах делайте паузы и перебирайте код отладчиком или глазами, так легче мозг принимает информацию.
Очень полезный урок. Ребят, если вы переписывайте код, то не забывайте его комментировать во-первых для того, чтобы самому лучше понять как и что работает, а во-вторых, чтобы при просмотре вашего кода, например через месяц, вы не путались в огромном количестве строк кода.
А также не забывайте комментировать и ставить лайки под такими видео, чтобы увеличить их популярность.
Не описать словами чувство удовлетворения от понимания устройства односвязного списка после ваших разъяснений! Спасибо большое!
Спасибо за столь не простой урок. По уровню сложности я бы его оценил как урок про конструкторор копирования. Однако, пересматривая урок по несколько раз с каждым разом, понимание становится лучше и лучше.
ну ты дал, Сергей!:)) загрузил так загрузил:) самое удивительное, что я все понял, а я новичок в этом) Спасибо! и присоединяюсь про бабосы с первой зп. Это заслуженно 100%.
Господи это реально лучший канал по си плюсам, Чувак ты лучший❤️❤️❤️
Я не знаю, как бы я изучил ЭТО без таких прекрасных объяснений. Это шедевр
Огромное спасибо! Отличные, понятные, содержательные уроки. Очень полезно!
#односвязныйсписок #динамическиеструктурыданных #SimpleCode #урокипрограммирования
классный урок, спасибо Сергей!
Вообще не знаю, как бы я понимал программирование без Сергея. Спасибо, друг.
Спасибо большое за урок. Преподы не могут так объяснить как вы!)
Обещаю часть своей первой зарплаты (от работы програмиста) отправить вам на поддержку канала!
Присоединяюсь, отличная идея!
peace да ball
@Artur Golovenko Тебе так хочется верить. Я отучился на программиста, за 5 лет обучения я знаю меньше чем с уроков ютуба(т.к там преподу пофигу знаешь ты или нет. Он приходит сидит там мямлет что то себе под нос, читая слайд шоу. На ютубе ты можешь выбрать канал, а препода в универе нет.При обучении я просто ненавидил с++.) Конечно нужно еще почитать кое какой инфы и книг, много гуглить, много проб и ошибок. Этот диплом, что я получил мне абсолютно никакой пользы не принес. Работаю не по специальности. Данная работа мне приносит, для моего опыта и возраста колоссальный доход ,какие то цифры я приводить не буду, дабы тут не хвастаться не перед кем. Но у данной моей работы есть огромные минусы. Она очень тяжелая, много грязи, и еще связана с командировками(причем бывают и по пол года). Поэтому я решил вернуться к истокам с чего и начинал, к программированию. Смотря курс Сергея(ему огромное отдельное спасибо!!!!). Я постиг много во, теперь действительно могу что то написать. Читаю книги Бьерна Страуструппа, все свое свободное время просто вкладываю в обучение. Учу параллельно английский. Главное вера в себя, хорошая усидчивость, голова на плечах и руки не из одного места:) Сергею еще раз большое спасибо, из всех просмотренных мной каналов это самый лучший. Он действительно хорошо все объясняет, как говорят, нам все разжевал - осталось только в рот положить. По сравнению с тем же Дударем(давайте создадим переменную, а хотя можно и не создавать) - его смотреть это когда все знаешь.
@@iii-mk7no Ну, как бы суть современного высшего образования в том, что тебе указывают нужное направление, а дальше ты сам в интернете и библиотеках учишься.
@@jojomajo 1) Російська мова не є моя рідна 2) Гроші я переказав, можеш спитати у автора 3) Зараз працюю в Європі айтішніком :) За допомогою цього вже всю Європу об'їздив, фотки вислати?)
Спасибо за урок!
Спасибо за отличный урок!
Спасибо!
Спасибо большое Сергей за реализацию списка!
Спасибо за урок
Very available explained!Like!
Просто безумно интересно, продолжай в таком же духе Сергей!!! От меня лайк.
спасибо большое, очень понравился урок, продолжай в том же духе!!!
Спасибо за бесценный труд!)
большое спасибо за урок!!! Удачи Вам) а каналу 500К подписчиков!!!
Спасибо большое за урок!
Спасибо за урок.
видео класс, жду уроков про очередь и бинарное дерево)
Thank you for the lesson!
Пришел из курса по C#. Тема Рекурсия. Плюсы таки сложнее шарпа, но смотреть интересно. Автор канала крут!
Мы создаём объект List. Внутри объекта лист счётчик и капсула Node с адресом следующей капсулы и данными. Функция push_back создаёт указатель на первую капсулу. Если адрес следующей капсулы равен нулю, то в переменной pNext мы создаём новую капсулу, если же там есть адрес то мы перебираем все адреса путём присваивания из капсулы head параметра pNext следующего адреса в переменную current. И так пока адрес следующей капсулы не будет равен 0. И опять же дойдя до этого элемента присваиваем в параметр pNext следующую капсулу. 3 дня ушло чтобы это всё понять)
Привет а зачем нужно создавать временный указатель(current) ?
@@user-oo9tn8fj7i она типа временная, я тоже задался этим вопросом. Попробовал сделать без нее используея this->head ну и это даже не компилилось)
Это позволяет, я так понял, обращаться по очереди к каждому адресу это в случае перегрузки operator[], а в PushBack() это позволяет последовательно создавать новые элементы списка. Трудно объяснить к сожалению, но отладчиком все хорошо можно проследить)
По сути в этом нет ничего сложного, просто столько времени уходит на понимание, потому что никто не умеет нормально объяснять, выделяя основную суть что и зачем делается. Что автор, который заваливает кодом, нежели говорит суть, что этот комментарий, под которым я пишу, в котором уровень пунктуации на крайне печальном уровне. Из-за этого вполне простые вещи в голове разбрасываются в хаотичном порядке, и становится сложнее втройне, просто потому что людям не дано нормально объяснять
@@nick-ei2og Сказал человек, который растянул мысль на целый параграф)))
@@user-oo9tn8fj7i Указатель current мы создаём потому что он перебирает все элементы, тем самым присваивая себе эти элементы по очереди, пока не дойдёт до последнего элемента и дальше не создаст новый(речь идёт о Push_Back), а head нельзя изменять потому что это начальный элемент
Серега спасибо!
Большое спасибо за урок
В очередной раз огромная благодарность Вам за доходчивое разъяснение и внятный, толковый пример.
этот чувак просто гений у него есть настоящий дар учителя потрясающий контент!
очень интересно
Блин, ну вроде бы понял как это всё работает, спасибо Сергею за такой труд)
Классное видео! Кстати можно было избежать цикла while при добавлении не первого элемента в push_back, например, объявив Node* last рядом с head и далее использовать в push_back.
Уважаемый, Сергей! 10к подписчиков, с чем я вас сильно поздравляю=). Надеюсь ролик о том, как вы стали программистом монтируется(просто не терпится послушать).
Спасибо! Я всё помню, ролик будет завтра.
Огромное спасибо !!!!
Благодаря вам сдала лабу по программе, большое спасибо ~
Мощно)2 ой день уже смотрю)
Это просто нереально полезный для меня урок
Не знаю как в VS17 а в VSCode и компиляторе g++, чтобы исключить ошибку декларирования
("error: declaration of template parameter 'T' shadows template parameter") можно писать так:
template
class List
{
private:
template //Т - ненадо объявлять, т.к. переменная объявлена ранее
class Node
{
public:
Node *pNext;
T data;
Node(T data = T(), Node *pNext = nullptr)
{
this->data = data;
this->pNext = pNext;
}
};
Node *head;
int Size;
public:
List(/* args */);
~List();
void push_back(T data);
int GetSize() { return Size; }
T &operator[](const int index);
};
Огромное спасибо. Очень выручил!
3 часа бился над ошибкой, почему не выводит результат lst[2], при этом забыв завести команду lst.push_back(22). Только отладчиком понял, что условие if не возвращает результат, потому что 3 переменную листа не завёл)) Кстати в кодблокс пришлось у Node делать тип T1, иначе не работает. Спасибо комментариям снизу. Тема обсуждалась, когда число подписчиков было 10 тыс, а я смотрю когда уже 233 тыс. Спасибо, Сергей за отличные уроки. Надеюсь через год переквалифицируюсь из инженера-конструктора в программисты.
спасибо чувак.. сними уроки для c#. буду благодарен
Разобрал я этот пример и подумал про себя а умно все это сделано=)
безмерная благодарность Тебе
Автору огромное спасибо за урок! Скажите, пожалуйста, обязательно ли внутренний класс Node делать шаблонным? Ведь и класс List, и класс Node всегда будут работать с одинаковыми типами данных.
Спасибо!!!
Сегодня на собесе загрузили по данной теме, хотя опыт 20 лет на сях. Всегда есть чему учится.
спасибо
Отличный курс!!!!!!!!!!!!!!!!!
Спасибо за разъяснение.Всё толково и понятно!❤
чего добился за эти 5 мес?
@@Hikikomori123всё работает хорошо.Список у меня из структур.Хотел что бы происходила сортировка по какой либо записи структуры,но пока не знаю как используя стандартные средства среды это сделать?
Данная программа не компилируется, выдается ошибка (declaration of template parameter 'T'). Проверил в нескольких компиляторах везде одна и та же ошибка. Как её решить? А главная, почему программа в ролике вообще компилируется ???????????????
У вас в плейлисте "Основы C++. Программирование для начинающих" не хватает теории про односвязный список. (то что ссылка в описании видел)
и весь остальной плейлист про динамические структуры данных
Спасибо.
Ну push_back можно было бы оптимизировать. Просто в list хранить ещё и указатель на последний элемент. Далее мы в поле последнего элемента приравниваем новый указатель new Node (data), после чего просто в указатель в List мы приравниваем вновь созданный указатель
Спасибо за урок, но было бы лучше, если на простые вещи было бы меньше акцента, а на более сложные - больше.
Главное, что определение методов внутри определения класса делает их встроенными, что не нужно в большинстве случаев. А уже потом это загромождает код.
Урок предельно понятный и информативный, но нужно еще и самому всё это написать и пробежаться отладчиком.
Я думаю объект типа T в функцию push_back надо передавать по ссылке, а не по значению.
А то получается ты копируешь объект 3 раза: из main в push_back, из push_back в конструктор Node и из конструктора Node в переменную data класса Node
Для тех кто не понял как работает pNext:
while просматривает значение current->pNext, если оно не nullptr то берет значение адреса памяти следущего елемента.
а присваиваеться это следущее значение текущему в функции push_back этими строчками:
Node* current = this->head;//создаеться указатель на первый указатель класса
если у первего указателя переменная pNext = null; то создаеться новый екземпляр класса Node с pNext = null, а pNext у head(если изменить значение у указателя то значение основного обьекта также смениться) становиться равным адрессу памяти нового екземпляра при помощи:
current->Nextptr = new Node(data);
и так можно добавлять елементы до бесконечности, каждый елемент будет хранить указатель на следущий
Вопрос: как сохраняется указатель *current, который создался в методе push_back? Разве он не должен уничтожится когда мы выходим за область видимости?
Было бы неплохо добавить указатель на последний элемент этого списка, т.к. при больших значениях узлов такого списка, его создание займёт огромное количество времени
лучший!
в реализации оператора индексации, после цикла while желательно написать обработку ситуации, когда индекс меньше количества элементов. Т.е.
while(current!=nullptr) выполнится раньше, чем найдем индекс.
Обычно компиляторы такой код не компилят, но х3. Спасибо, брооо
а не должно быть - while(current->Nextptr != nullptr) ?
Подскажите, пожалуйста,в каких уроках начинается синтаксис типа "current->data"?
Ребята, подскажите пожалуйста, каким образом новый экземляр класса Node присваивается укателю header в области видимости метода pushback 16:30 строка 60 (Node* header = new Node(data)). Как это работает? Обычно к указателям можно присвоить ссылки.
КРАСАВА
Спасибо за уроки, Сергей! Надеюсь еще читаете эти комментарии.
Такой вопрос:
Решил после просмотра серии уроков про список, написать самостоятельно по полученным знаниям свой класс списка. И на моменте описания перегрузки оператора [ ] у меня получились расхождения с вами.
В моем случае я эту перегрузку описал так:
template
T& List::operator[](int index)
{
int counter = 0;
Node* current = head;
while (counter != index)
{
current = current->pNext;
counter++;
}
return current->data;
}
Подскажите, как мне кажется мой вариант более компактный, однако он допускает значения индекса больше, чем список имеет значений. И в случае превышения индекса программа завершается с ошибкой, как это было бы с обычным массивом, выйдя за его пределы. В вашем же случае, при выходе за границы результат всегда будет 0.
Помню вы говорили, что лучше если программа завершится с ошибкой, чем выдаст какое-то значение, из-за которого дальнейшая работа будет некорректна и мы устанем искать причину такого поведения.
Собственно вопрос, как лучше описывать эту перегрузку?)
Node *current = this->head;
for (int i = 0; i < index; i++)
{
current = current->pNext;
}
return current->data;
Я описал это вот так. Но в моём случае при отрицательном значении индекса оператор возвращает первый элемент списка. Но не думаю, что это большая проблема
браво
я целых часов 5 наверное сидел и перетирал что вообще происходит(в частности с тем откуда 2 поля(pNext) у 1 переменной )
А если через оператор индексирования нужно вывести несколько элементов, как это сделать?
Может кому-то будет изначально не понятно как и мне. Указатель head содержит адрес по которому одновременно хранятся данные + указатель на следующий элемент. Соответственно когда в функции push_back мы создаем указатель current то в него попадает, то что лежит по первому элементу List (это два поля данные и указатель(который, для случая, что у нас только 1 элемент листа все еще равен nullptr). Затем мы в поле указателя ячейки листа у которой поле указателя на следующий элемент равно nullptr присваиваем адрес данных (новая ячейка) которую мы функцией Push_back добавляем.
спасибо.
Знаю вопрос глупый, но! Не могли бы вы объяснить почему мы не можем класс Node вписать вне класса List и потом просто к нему обращаться
Если мы динамически выделяем здесь память, почему нет ее освобождения?
Здравствуйте!
Можете ли сказать,почему когда мы выделяем дин память под елемент,мы не удаляем его в конце в деструкторе?
Мы же по сути не очищали память,а все равно прога компилируется
Сергей, привет! Спасибо за реализацию списка! Это твоё первое видео такой внушительной продолжительностью...насколько я помню было одно длительностью 30 минут конструктор копирования! Когда будешь записывать видео ответы на ваши вопросы озвучь, пожалуйста, с помощью какой программы монтируешь видео! Случайно не Sony Vegas Pro 13? ))))
Пожалуйста! Монтирую с помощью Vegas Pro 14
даужь, начались наконец то уроки по сложнее
Здравствуйте! Подскажите, пожалуйста, как так же сразу вставить код класса? (как на 2:42)
А где можно посмотреть урок на счет указателя в классе? А то не понял момент на счет Node *pNext
head = head->pNext;//head получает адрес следующего элемента списка
Но где в коде описано когда этот адрес на следующий элемент получен? Когда head->pNext получило какое-то значение, а не nullptr?
А как реализовать “Очередь” на основе односвязного списка? Это как вообще? Что-то логику не поняла
выдает ошибку error: declaration of template parameter 'T' shadows template parameter|
Потому что Node не должен быть шаблоном, если List - шаблон. Или, по крайней мере, имя шаблонного параметра у Node не должно совпадать с таковым у List. Но лучше все-таки первый вариант.
Сложно, но понять можно!
Окей, а что там с деструктором?
Ловите мой вариант функции push_back
void List::push_back(T info)
{
if (tail == NULL)
tail = head = new Node(info, head);
else
tail = tail->next = new Node(info);
size++;
}
в этом варианте в классе должен быть еще Node*tail, который всегда будет находиться в самом низу списка (он все еще односвязный), tail->next всегда = NULL. Такой вариант кода позволяет не пробегать по всему списку каждый раз, когда элемент надо добавить вниз.
невозможно преобразовать аргумент 1 из "Т" в "List::Node *"
Нашёл решение?
@@Andrey-qj9sjнет
поміняй місцями параметри в класі нут в круглих дужках
спочатку напиши T data=T() а потім Node *pNext
@@oljaolsa7261 Вы серьезно думаете что все знают укр язык?
Код целиком скинь
Я правильно понимаю, что pop_back невозможно сделать за O(1), так как даже, если у нас есть указатель на послед. элемент, то, имея односвязный список: []->[]->[]->nullptr , чтобы удалить последний нужно предпоследнему сделать nullptr, иначе будет висячий указатель(последний же удалится). Предпоследний же нужно также перебирать сначала списка.
мозг кипит)
Было бы круто хранить текущий size и tail тогда все кроме взятия индекса за О(1))))))
а должен ли оператор квадратных скобок возвращать что либо если по какой либо причине индекс выходит за размер листа? (ну, имхо, я проверял бы как-нибудь)
Можно проверять и бросать exception в случае выхода за границы списка, но это уже тонкости реализации.
Кстати. Запустил прогу, вписал 50 тыщь, и консоль затупила)) Теперь я понял в чем разница списка и массива. Массив быстрее работает с большими индексами.
Ахахахах, тоже показательный пример
Посоветуйте, пожалуйста, источники с обучением программированию на языке java
script.
Nikita klinchev w3school
Вы говорите что прошлый урок №132 посвящен теоретической части односвязного списка. Но он посвящен: "Динамический массив и умные указатели"
Я вот не понял как head.pNext получает адрес current.
Так как в методе push_back, я как понимаю, к current присваиваем адрес head.