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

алгоритм, связанный список, сортировка

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

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

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

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

Нужно начать с чего-нибудь, поэтому мы даем адресу первого узла специальное имя, называемое 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 хостинг.

Комментарии

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

Здравствуйте, уважаемые пользователи EVILEG !!!

Если сайт вам помог, то поддержите разработку сайта финансово, пожалуйста.

Вы можете сделать это следующими способами:

Спасибо, Евгений Легоцкой

D
15 ноября 2019 г. 10:16
Daulet

C++ - Тест 004. Указатели, Массивы и Циклы

  • Результат:40баллов,
  • Очки рейтинга-8
ЛП
12 ноября 2019 г. 19:22
Лев Пархимович

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

  • Результат:50баллов,
  • Очки рейтинга-4
ЛП
12 ноября 2019 г. 18:35
Лев Пархимович

C++ - Тест 005. Структуры и Классы

  • Результат:66баллов,
  • Очки рейтинга-1
Последние комментарии
b
9 ноября 2019 г. 19:28
bastonc

спасибо ещё раз. огромное, за уделённое время
b
9 ноября 2019 г. 19:24
bastonc

Спасибо Вам большое. Буду изучать.
9 ноября 2019 г. 16:58
Евгений Легоцкой

Добрый день. По первым двум вопросам вы найдёте ответ в этой статье - PyQt5 - Урок 008. Работа с QTableWidget (Обновление урока 006) Что касается последнего вопроса, то я вам…
9 ноября 2019 г. 13:50
Евгений Легоцкой

Как и обещал, вы можете посмотреть новую статью QML - Урок 037. Кастомизация кнопок в QML (Обновление урока 002) . Там же найдёте ссылку на Git репозиторий. Не забудьте поставить звёз…
b
8 ноября 2019 г. 18:40
bastonc

Приветствую. Подскажите пожалуйста пару моментов. 1. Как сделать столбец не редактируемый, а остальные ячейки остаются редактируемыми 2. Как оталвливать события двойного клика для реда…
Сейчас обсуждают на форуме
15 ноября 2019 г. 15:06
Евгений Легоцкой

Что это такое Wrngdatalib ? Это namespace ? Скорее всего проблема в том, что те объекты тех классов, которые там присутствуют для обработки xml наследованы от QObject…
15 ноября 2019 г. 14:48
Евгений Легоцкой

Ну собственно поэтому я и сказал, что бесполезное это занятие.
15 ноября 2019 г. 14:27
Евгений Легоцкой

Добрый день. Вот эта статья кажется вполне подходящей к вашему вопросу Install OpenCV 3.4.4 on Ubuntu 16.04 (C++ and Python) Единственное, возможно, что вам потребуется ппра…
15 ноября 2019 г. 14:23
Евгений Легоцкой

Я нашёл решение от разработчиков PyQt5 в списке рассылки. os.environ['QT_QUICK_CONTROLS_STYLE'] = 'Material' Попробуйте его ещё
15 ноября 2019 г. 14:20
Евгений Легоцкой

Добрый день. Пробовали jintArray ?
EVILEG
О нас
Услуги
© EVILEG 2015-2019
Рекомендует хостинг TIMEWEB