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

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

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

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

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

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

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

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

10% refund of hotel reservation amount on Booking
10% refund of hotel reservation amount on Booking
We offer a link with a 10% return on the amount of the order when booking a hotel through Booking

Comments

Only authorized users can post comments.
Please, Log in or Sign up
TT
June 13, 2019, 7:01 p.m.
Taimoor Tanweer

C++ - Test 001. The first program and data types

  • Result:66points,
  • Rating points-1
TT
June 13, 2019, 6:51 p.m.
Taimoor Tanweer

C++ - Test 002. Constants

  • Result:75points,
  • Rating points2
ВМ
June 13, 2019, 12:30 p.m.
Ваня Мороз

C++ - Test 001. The first program and data types

  • Result:100points,
  • Rating points10
Last comments
МБ
June 20, 2019, 6:23 p.m.
Михаил Булатов

А если мне нужно сделать конект из дочернего qml?Сигнал работает только из main.qml
i
June 17, 2019, 6:10 a.m.
ingenfly

Только по осям xAxis2, уAxis2 значения начинаются с 0. Почему-то xAxis2 и xAxis не синхронизированы по данным. Ну и QCustomPlot последний.
June 16, 2019, 8:21 p.m.
Евгений Легоцкой

Добрый день. Ну точно также добавляете ту же самую информацию на ось xAxis2, только добавляете другое форматирование customPlot->xAxis2->setDateTimeFormat("hh:mm"); если я ...
EF
June 14, 2019, 1:56 p.m.
Egor Fomin

Спасибо за ваш ответ, у меня получилось реализовать это. Тем не менее появилась другая проблема, поэтому опять надеюсь на вашу помощь. Скажем, я уже выставил точки и они соеденены. Когда я нач...
d
June 13, 2019, 2:47 p.m.
damix

Можно классу, который описывает точку, добавить сигнал, который подавать (emit), когда точка перемещается (переопределить mouseMoveEvent или mouseReleaseEvent). Так вот эти сигналы у каждой из...
Now discuss on the forum
June 20, 2019, 9:30 a.m.
IscanderChe

Вернулся к этой задачке только-только, поэтому и не ответил ничего раньше.Как переопределить mouseReleaseEvent(QMouseEvent* event) у QTableView, если QTableView задан в ui? Или задавать QTabl...
I
June 19, 2019, 1:41 p.m.
Intruder

Всем добрый день. При разборе XML файла наткнулся на тег вот такого плана: <TagName attribute1="value1" attribute2="value2" /> При попытке проверить на наличие такого элеме...
June 19, 2019, 12:55 p.m.
Михаиллл

Скажите пожалуйста, как его в таком случае перемещать и удалять?
June 18, 2019, 7:50 p.m.
Дмитрий

Большое спасибо! SDK заработал.К сожалению удалось продвинутся только на один шаг. При сборке чистого проекта NDK выдаёт следующие ошибки C:\Android\ndk-bundle/toolchains/arm-linux-andr...
June 18, 2019, 4:59 p.m.
Михаиллл

Добрый день.В этом учебнике представлен код INSTALLED_APPS = ( ... 'rest_framework', 'snippets.apps.SnippetsConfig',) На строчке 'snippets.apps.SnippetsConf...
Looking for a Job?
25,000.00 руб. - 30,000.00 руб.
Разработчик Qt/C++
Barnaul, Altai Krai, Russia

For registered users on the site there is a minimum amount of advertising

EVILEG
About
Services
Join us
© EVILEG 2015-2019
Recommend hosting TIMEWEB