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

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

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

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

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

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

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

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

We recommend hosting TIMEWEB
We recommend hosting TIMEWEB
Stable hosting, on which the social network EVILEG is located. For projects on Django we recommend VDS hosting.

Comments

Only authorized users can post comments.
Please, Log in or Sign up
Donate

Hello, Dear Users of EVILEG!!!

If the site helped you, then support the development of the site financially, please.

You can do it by following ways:

Thank you, Evgenii Legotckoi

AT
Dec. 10, 2019, 8:06 a.m.
Anastasija Troschenkova

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

  • Result:60points,
  • Rating points-1
AT
Dec. 10, 2019, 8:02 a.m.
Anastasija Troschenkova

Qt - Test 001. Signals and slots

  • Result:73points,
  • Rating points1
g
Dec. 10, 2019, 4:51 a.m.
gisLu

C ++ - Test 004. Pointers, Arrays and Loops

  • Result:40points,
  • Rating points-8
Last comments
Dec. 9, 2019, 3:41 a.m.
Evgenij Legotskoj

Эта ошибка invalid use of incomplete type ‘class Ui::AnotherWindow’ обычно говорит о том, что не найдено определение класса или структуры. Типичная проблема - не подключён заголовочны…
NB
Dec. 9, 2019, 3:36 a.m.
Nikolaj Batmanov

Ну, не настолько со мной всё полхо...))) Вроде бы. Я ж кнопки отрисовываю.
Dec. 9, 2019, 3:14 a.m.
Evgenij Legotskoj

Добрый день. У вас ui файлов по ходу нет. UI файлы используются для вёрстки в графическом дизайнере.
NB
Dec. 9, 2019, 3:05 a.m.
Nikolaj Batmanov

Здравствуйте! Полностью скопировал ваш пример к себе, чтобы разобраться. А он не хочет запускаться, дает ошибку: invalid use of incomplete type ‘class Ui::AnotherWindow’ ui(new Ui…
Dec. 8, 2019, 7:23 a.m.
Evgenij Legotskoj

У меня здесь есть одна старая статья с примером векторного редактора. Там есть ответы на ваши вопросы. Поизучайте Qt/C++ - Урок 072. Пример векторного редактора на Qt QGraphicsItem, QG…
Now discuss on the forum
MU
Dec. 11, 2019, 8:27 a.m.
Maciej Urmański

Thank you! Now works, and this is solution. num_embed = Embed.objects.filter(added_by=recipe.added_by).count()
Dec. 11, 2019, 8:12 a.m.
Mihailll

Так работает. Взял этот пример https://api-2d3d-cad.com/face_recognition_with_opencv/ void MainWindow::on_pushButton_4_clicked() //фото определение лица{ // Load Face cascade (.xml…
TD
Dec. 10, 2019, 4:14 a.m.
Timur Dosov

Спасибо, работает. А ещё вопрос: как загрузить страницу с динамической подгрузкой контента по скроллингу? Например - [https://ntvplus.ru/tv/]. Пока делаю через костыль - QApplication::s…
Dec. 9, 2019, 7:16 a.m.
qml_puthon_user

Я сделал простой вывод текста по испусканию сигнала... Чего не хватает программе?) Python: # системные библиотекиimport cv2import numpy as npimport sysimport threading# PyQt б…
SK
Dec. 8, 2019, 4:11 p.m.
Semen Kosandjak

інтерфейс qt, приклад того додаю на малюнку, я натискаю на кнопку і у мене з'являється 2 текст лайну в які я вводжу значення, тобто в 1 цифри,у другому випадку це літери, тобто c++, без графічно…
EVILEG
About
Services
© EVILEG 2015-2019
Recommend hosting TIMEWEB