Lila25mila
Lila25mila5 апреля 2019 г. 3:26

Связанный список

В этом уроке вы узнаете о связанном списке и его приложениях. Вы также узнаете, как создавать и выполнять различные операции со связанным списком.


В игре «Охота за сокровищами» вы начинаете с поиска первой подсказки. Когда вы найдете его, вместо того, чтобы найти сокровище, вы найдете местоположение следующей подсказки, а затем следующей и так далее. Вы продолжаете следовать за подсказками, пока не доберетесь до сокровища.

Связанный список похож на пример с игрой. Это серия связанных «узлов», которая содержит «адрес» следующего узла. Каждый узел может хранить точку данных, которая может быть числом, строкой или любым другим типом данных.

Представление связанного списка

Нужно начать с чего-нибудь, поэтому мы даем адресу первого узла специальное имя, называемое HEAD. Кроме того, последний узел в связанном списке может быть идентифицирован, потому что его следующая часть указывает на NULL.

Как ссылаются на другой узел?

Давайте подумаем о том, что содержит каждый узел:

  • Элемент данных;
  • Адрес другого узла.

Мы объединяем элемент данных и ссылку на следующий узел в структуру как:

struct node
{
  int data;
  struct node *next;
};

Понимание структуры связанного узла списка является ключом к пониманию.

Каждый структурный узел имеет элемент данных и указатель на другой структурный узел. Давайте создадим простой связанный список с тремя элементами, чтобы понять, как это работает.

/* Инициализируем узлы */
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;

/* Выделяем память */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));

/* Назначаем значения данных */
one->data = 1;
two->data = 2;
three->data=3;

/* Соединяем узлы */
one->next = two;
two->next = three;
three->next = NULL;

/* Сохраняем адрес первого узла в голове */
head = one;

Если вы не поняли ни одной из вышеперечисленных строк, все, что вам нужно, это обновить указатели и структуры.

Всего за несколько шагов мы создали простой связанный список с тремя узлами.

Приемущество связного списка происходит от способности разорвать цепь и присоединить к ней. Например, если вы хотите поместить элемент 4 между 1 и 2, выполните следующие шаги:

  • Создайте новый узел структуры и выделите для него память.
  • Добавьте его значение данных как 4
  • Направьте следующий указатель на узел структуры, содержащий 2 в качестве значения данных
  • Измените следующий указатель «1» на узел, который мы только что создали.

Чтобы сделать что-то похожее в массиве, потребовалось бы сместить позиции всех последующих элементов.

Утилита связанного списка

Списки являются одной из самых популярных и эффективных структур данных, которые реализуются на всех языках программирования, таких как C, C ++, Python, Java и C #.

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

Рекомендуем хостинг TIMEWEB
Рекомендуем хостинг TIMEWEB
Стабильный хостинг, на котором располагается социальная сеть EVILEG. Для проектов на Django рекомендуем VDS хостинг.

Вам это нравится? Поделитесь в социальных сетях!

Комментарии

Только авторизованные пользователи могут публиковать комментарии.
Пожалуйста, авторизуйтесь или зарегистрируйтесь
B

C++ - Тест 002. Константы

  • Результат:16баллов,
  • Очки рейтинга-10
B

C++ - Тест 001. Первая программа и типы данных

  • Результат:46баллов,
  • Очки рейтинга-6
FL

C++ - Тест 006. Перечисления

  • Результат:80баллов,
  • Очки рейтинга4
Последние комментарии
k
kmssr8 февраля 2024 г. 18:43
Qt Linux - Урок 001. Автозапуск Qt приложения под Linux как сделать автозапуск для флэтпака, который не даёт создавать файлы в ~/.config - вот это вопрос ))
АК
Анатолий Кононенко5 февраля 2024 г. 1:50
Qt WinAPI - Урок 007. Работаем с ICMP Ping в Qt Без строки #include <QRegularExpressionValidator> в заголовочном файле не работает валидатор.
EVA
EVA25 декабря 2023 г. 10:30
Boost - статическая линковка в CMake проекте под Windows Ошибка LNK1104 часто возникает, когда компоновщик не может найти или открыть файл библиотеки. В вашем случае, это файл libboost_locale-vc142-mt-gd-x64-1_74.lib из библиотеки Boost для C+…
J
JonnyJo25 декабря 2023 г. 8:38
Boost - статическая линковка в CMake проекте под Windows Сделал всё по-как у вас, но выдаёт ошибку [build] LINK : fatal error LNK1104: не удается открыть файл "libboost_locale-vc142-mt-gd-x64-1_74.lib" Хоть убей, не могу понять в чём дел…
G
Gvozdik18 декабря 2023 г. 21:01
Qt/C++ - Урок 056. Подключение библиотеки Boost в Qt для компиляторов MinGW и MSVC Для решения твой проблемы добавь в файл .pro строчку "LIBS += -lws2_32" она решит проблему , лично мне помогло.
Сейчас обсуждают на форуме
P
Pisych27 февраля 2023 г. 4:04
Как получить в массив значения из связанной модели? Спасибо, разобрался:))
AC
Alexandru Codreanu19 января 2024 г. 11:57
QML Обнулить значения SpinBox Доброго времени суток, не могу разобраться с обнулением значение SpinBox находящего в делегате. import QtQuickimport QtQuick.ControlsWindow { width: 640 height: 480 visible: tr…
BlinCT
BlinCT27 декабря 2023 г. 8:57
Растягивать Image на парент по высоте Ну и само собою дял включения scrollbar надо чтобы был Flickable. Так что выходит как то так Flickable{ id: root anchors.fill: parent clip: true property url linkFile p…
Дмитрий
Дмитрий10 января 2024 г. 4:18
Qt Creator загружает всю оперативную память Проблема решена. Удалось разобраться с помощью утилиты strace. Запустил ее: strace ./qtcreator Начал выводиться весь лог работы креатора. В один момент он начал считывать фай…
Evgenii Legotckoi
Evgenii Legotckoi12 декабря 2023 г. 6:48
Побуквенное сравнение двух строк Добрый день. Там случайно не высылается этот сигнал textChanged ещё и при форматировани текста? Если решиать в лоб, то можно просто отключать сигнал/слотовое соединение внутри слота и …

Следите за нами в социальных сетях