Реализация связных списков на С++
Более подробно про структуры данных и алгоритмы, используемые статье можно прочитать тут:
Однонаправленный связанный список. Очередь
В данной своей статье я хотел бы рассмотреть такую интересную структуру данных, как связанный список или как его еще называют динамический список. Связный список — это динамическая структура данных, состоящая из узлов, которые содержат в себе в классическом варианте два значения: первое — это какое-либо данное (этим данным может быть что угодно: обычная переменная, объект класса и так далее), а второе — это указатель на следующий узел в списке (не зря же список является связанным).
Список связный потому что все узлы списка связаны между собой с помощью указателей, а динамический потому что динамически во время выполнения программы можно расширять данную структуру путем добавления новых узлов в список. В отличие от массива будь то статического, либо динамического, динамический список можно увеличивать во время работы программы. В этом то и есть его очень большой плюс. А вот давайте теперь и рассмотрим все это на рисунке:
На рисунке мы видим узлы, содержащие в себе два значения — данное и указатель. Указатель всегда указывает (содержит в себе адрес памяти) на следующий узел связанного списка. И самое важное — это то, что указатель последнего узла должен всегда выставляться в нуль (NULL, nullptr или просто 0). Этим он сообщает что является последним узлом связанного списка и что дальше указывать не на что. Если нужно будет добавить новый узел в динамический список, то это значение NULL заменяется на адрес нахождения в памяти нового узла (как это делается мы рассмотрим ниже), а сам же указатель нового узла опять выставляется в NULL. По ходу работы программы мы можем сколь угодно создавать таких узлов нашего связанного списка, единственное ограничение накладывает размер свободной оперативной памяти компьютера (ее конечно же должно хватать). Логически мы видим, что все узлы расположены как бы по порядку, хотя на самом деле в памяти компьютера они могут располагаться где угодно. И найти его не составит никакого труда, т.к. у нас есть в узле поле-указатель, указывающий на нужную ячейку памяти.
Давайте теперь последовательно рассмотрим работу связанного списка. Итак, мы описали в своей программе структуру, представляющую собой узел динамического списка. Эта структура из двух полей — данное и указатель на структуру того же типа. Такие структуры еще называются самоссылающимися (или структуры с самоадресацией). Вот как это будет выглядеть
А теперь нужно создать сам объект «связанный список», который и будет хранить эти самоссылающиеся узлы (Node — с англ. узел). Вот как мы это сделаем
Итак, если с первой структурой Node все понятно, то со структурой List , представляющей «связанный список» нам нужно сейчас разобраться. Мы выяснили, что динамический список состоит из узлов, значит класс List должен манипулировать этими узлами: создавать их, удалять, выводить на печать и так далее. Пока что остановимся только на таких моментах как создавать и выводить на печать, удаление оставим на потом. Как видите, в нашем классе List имеются два метода: addNode() — создает новый узел в динамическом списке, printList() — выводит содержание списка (всех узлов поочереди) на печать. Также у нас есть закрытое поле класса head типа Node — это так называемая «голова» связанного списка и судя из названия должна всегда указывать на начало списка в памяти компьютера, т.е. на его первый узел (этот момент мы не обсуждали выше, но он логически понятен — должен же быть указатель, указывающий просто на начало динамического списка и не содержащий никаких данных). Зная, где начинается связанный список, на него нам указывает «голова» head , и где заканчивается, об этом нам сообщает указатель последнего узла, выставленный в NULL , мы можем путешествовать по всему динамическому списку и произодить с них необходимые операции.
Изначально в конструкторе класса List переменной head выставляется значение в NULL , т.к. при создании объекта класса List связанный список еще пуст и узлов в нем нет, соответственно и указывать не на что. Складываем все вышеупомянутое и получаем рабочую программу, реализующую динамический список.
Результат работы программы будет выглядеть так: 
Думаю, что метод, добавляющий новый узел в список ( addNode ) нужно рассмотреть подробнее — не всем и все здесь будет понятно сразу же:
Итак, первая строка кода
Node *nd = new Node;
динамически (new) создает новый объект типа Node , т.е. новый узел. Как вы знаете, после отработки данной строки, в указатель nd , при успешном создании объекта, записывается адрес созданного объекта в памяти (в неудачном случае будет записано NULL , т.е. объект не создан). Идем дальше…
В этих двух строках кода мы уже обращаемся к полям созданного узла и присваиваем им необходимые значения: задаем данное — это данное метод addNode() принимает в качестве аргумента, выставляем указатель в NULL , т.к. вновь созданный узел всегда у нас будет последним (в данном варианте программы узлы добавляются в конец связанного списка — классический вариант). Далее…
Следующая конструкция выбора служит для определения: создается первый узел в списке или он уже не первый. В случае, если создается только первый узел, то head будет в NULL и выполнится условие после if , т.е. head присвоится адрес первого узла в памяти. В последующих случаях, когда создаются 2, 3, 4, 5, . узлы будет срабатывать блок после else . Его рассмотрим подробнее…
Создаем вспомагательную переменную типа Node и присваиваем ей указатель на начало списка. Далее в цикле мы последовательно проходимся по нашему связанному списку, пока не дойдем до узла, который был создан последним прошлый раз и присваиваем его указателю адрес нашего вновь созданного узла. Описанный процесс показан на рисунке:
Однонаправленный связнный список. Стек
Нами был рассмотрен классический вариант динамического списка, в котором новые узлы добавляются в конец, но есть еще вариант, когда узлы добаляются в начало, кстати, код такой программы немного меньше и проще. Его мы сейчас и рассмотрим.
Рассмотрев код программы, видим, что изменился метод добавления нового узла в список. Теперь новый узел как бы вклинивается между «головой» списка и следующим после нее узлом. Соответственно, в результатах работы мы видим в какой последовательности выводятся значения, находящиеся в узлах. Если вам подходит такой вариант обратного вывода, то можете использовать этот код.
Двунаправленный связанный список. Дек
В однонаправленном мы могли перемещаться только в одно направление и не могли вернуться назад, т.к. любой из следующих узлов не содержал в себе указателя на предыдущий. Также я добавил в программу возможность добавлять узлы как в начало списка, так и в конец, удалять узлы можно по условию, задаваемому функциональным объектом:
Создание списка и добавление в него элементов
Написан класс для организации вопроса, ответы в нем представлены в виде списка. Никак не выходит ввести список ответов в List .
- Один
- Ни одного. Это аппаратная проблема, программисты их не решают
- Много
Правильный ответ: 2
Как создать список ответов и добавить в него конкретные ответы?
Создание List и добавление в него элементов:
Альтернативный вариант через метод .Add() :
Передача questionAnswers в конструктор Question :
я это представляю как то так: в таблице вопросов(Question) хранятся вопросы и хеши ответов на них, в таблице ответов(Answer) возможные варианты ответов, QuestionAnswers необходим для того что бы можно было вывести возможные варианты ответов(как на экзамене в гибдд: ответы похожи за небольшим исключением). формируем список Вопросов для него получаем возможные варианты ответов(правильный и два любых других) все это сортируем(ответы, вопросы) показываем пользователю.
Списки в C++. Односвязный список
Стандартная библиотека C++ включает достаточно много структур данных. Среди них есть списки, очереди, стеки, множества и т. д. Но если вы хотите эффективно их использовать, необходимо понимать особенности их работы. В этой статье поговорим о базовой структуре в С++ — односвязном списке.
Односвязный список: теория
Если хотите понять, как построен односвязный список, представьте цепь. У неё есть и начало, и конец, плюс звенья последовательно соединены друг с другом. Можно легко пройти от начала до конца цепи, перебирая звенья.
Схожим образом работают односвязные списки. В них начало списка — это головной элемент, звенья — это узлы, а конец списка определяется посредством NULL — специального узла. Причём, чтобы структура списка была полезной, на каждый узел «вешают» определённое значение.
У односвязного списка есть преимущество — вставка и удаление узлов осуществляется довольно легко в любом месте списка. Однако список нельзя индексировать в качестве массива, а структура списка ограничивает доступ к узлам по индексу. Если нужно попасть на какой-нибудь узел односвязного списка, нужно пройти весь путь последовательно, начиная от головного элемента, заканчивая нужным узлом.
Интерфейс класса односвязного списка
Однонаправленный список используют при хранении упорядоченного набора однотипных элементов. Дабы не определять для каждого типа данных свой список, лучше определить шаблонный класс:
Класс односвязного списка поддерживает добавление узла в начало, получение значения головного элемента и удаление последнего добавленного узла. Также реализован обход списка посредством итераторов, плюс добавлена функция для расчета длины списка.
Определение узла осуществляется посредством структуры Node , содержащей два поля: — значение, привязанное к узлу, — m_t ; — указатель на следующий узел — m_next .
Изначально список является пустым, а значит, головной элемент указывает на NULL:
Добавляем элемент в односвязный список
Добавление узла в список производится в самое начало. То есть узел, который добавлен, сам превратится в новый головной элемент нашего списка:
Удаляем элемент из односвязного списка
В процессе удаления узла из списка усекается головной элемент. Таким образом, если в списке остаются узлы, новым головным элементом становится тот узел, который следует за головным элементом, в обратном случае — NULL:
Идём дальше. Список — динамическая структура. Когда добавляются новые узлы, из кучи выделяется память — её нужно освободить, дабы не создавались утечки памяти. А имея в наличии функцию удаления элементов, мы без проблем реализуем деструктор односвязного списка:
Односвязный список: итератор
Функциональность для удаления и добавления узлов в список не стоит смешивать с задачей его обхода. Для этих целей есть итераторы. Давайте создадим итератор списка в стиле C++. Для начала вернёмся к его определению, которое раньше пропустили:
В качестве итераторов для конца и начала нашего списка вернём следующее:
Что же, теперь мы можем легко обойти список с начала до конца. Но не стоит забывать про функцию вычисления длины. Для упрощения задачи будем использовать механизм итераторов: «`cplus template< typename T > size_t List< T >::size() const
Вместо заключения
Рассмотренный выше пример — лишь краткая демонстрация, из которой можно понять принципы работы с односвязным списком в C++. Однако практика показывает, что в реальных приложениях почти всегда лучше будет использовать стандартную библиотечную реализацию как списка, так и любой другой структуры данных. В этом случае работы от вас потребуется меньше. Кроме того, вы сразу получите в своё распоряжение оптимизированную и хорошо отлаженную версию, которой можно будет смело пользоваться.