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

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

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

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

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

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

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

Комментарии

Только авторизованные пользователи могут публиковать комментарии.
Пожалуйста, авторизуйтесь или зарегистрируйтесь
Ищу работу?
25,000.00 руб. - 30,000.00 руб.
Разработчик Qt/C++
Barnaul, Altai Krai, Russia

Для зарегистрированных пользователей на сайте присутствует минимальное количество рекламы

s
18 сентября 2019 г. 17:19
sanyalitv

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

  • Результат:33баллов,
  • Очки рейтинга-10
s
18 сентября 2019 г. 17:12
sanyalitv

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

  • Результат:80баллов,
  • Очки рейтинга4
d
18 сентября 2019 г. 7:34
dbuzin

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

  • Результат:33баллов,
  • Очки рейтинга-10
Последние комментарии
M
20 сентября 2019 г. 11:25
Mark

вызываю метод get у m_downloader в другом методе и приложение начинает вылетать. В чем ошибка?
M
19 сентября 2019 г. 5:45
Mark

А вот как выгрузить файл на сервер по http протоколу? Допустим на regRu. И как получить путь файла, которой отображается в файловом менеджере regRu, чтобы загрузить его.
17 сентября 2019 г. 6:07
Misha Lebedev

Кстати интересные темы нашёл тут https://emacsway.github.io/ru/django-framework/#django-models Может что полезного тоже Евгений найдёте
17 сентября 2019 г. 4:50
Misha Lebedev

Доброго времени суток. Спасибо за хороший ответ, У меня ситуация така что в галлереи будет несколько миллионов фотографий с фильтрами и тегами , и я опасаюсь за производительност . Это ос…
17 сентября 2019 г. 3:23
Евгений Легоцкой

Добрый день. Да, я тоже читал ту статью в своё время и согласен с тем, что внешние ключи гораздо лучше, чем GenericForeignKey. Выборки в ряде случае работают быстрее. Но лично мне про…
Сейчас обсуждают на форуме
20 сентября 2019 г. 4:56
Pavel K.

Привет , подскажите кто-нибудь , как сделать драг н дроп , не нарушая при этом логику работы зума? import QtQuick 2.6 import QtGraphicalEffects 1.0 Page { id:win property string fi…
19 сентября 2019 г. 8:03
Михаиллл

Скопировал базу в папку пользователей и тогда получилось записывать в нее
19 сентября 2019 г. 5:32
Михаиллл

Но мне же нужно еще получить этот id и вернуть его пользователю, а при таком запросе ничего не вернется.
M
18 сентября 2019 г. 17:35
Mark

Понятно Тогда можно ли достать только параметры файла? Например только дату его изменения
p
17 сентября 2019 г. 5:02
pstMem

Да, действительно нужно дебажить, по другому не словить исключение. Уже решил проблему, был выход за предел массива, не правильные входные данные, так что всегда проверяйте размер массива.
EVILEG
О нас
Услуги
© EVILEG 2015-2019
Рекомендует хостинг TIMEWEB