Privacy policyContactsAbout siteOpinionsGitHubDonate
© EVILEG 2015-2018
Recommend hosting
TIMEWEB

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

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

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

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

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

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

Нужно начать с чего-нибудь, поэтому мы даем адресу первого узла специальное имя, называемое 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
AA
April 17, 2019, 7:40 p.m.
Anton Ablin

Qt - Test 001. Signals and slots

  • Result:73points,
  • Rating points1
E
April 17, 2019, 6:16 p.m.
Evgeny

Qt - Test 001. Signals and slots

  • Result:100points,
  • Rating points10
E
April 17, 2019, 6:14 p.m.
Evgeny

Qt - Test 001. Signals and slots

  • Result:78points,
  • Rating points2
Last comments
U
April 18, 2019, 3:37 p.m.
Unreal_man

А как иконку в хедер задать?
u
April 18, 2019, 2:15 a.m.
uaa

доброго времени,большое спасибо за пример для начинающего)при адаптации к своему проекту столкнулся с таким ньансом:в vepolyline.h в 47 строке нужна инициализация по умолчанию: int m_pointF...
E
April 11, 2019, 12:49 p.m.
Evgeny

Спасибо за ответ) У меня компоновщик на нее ругался просто. Оказалось, просто забыл Q_OBJECT в начале класса указать.
April 11, 2019, 12:29 p.m.
Евгений Легоцкой

Добрый день. Вы имели ввиду реализацию? Для сигналов в Qt реализация не пишется, это всё генерируется в moc файлах под капотом Qt.
E
April 11, 2019, 12:15 p.m.
Evgeny

Здравствуйте. А где описание функции signal1()?
Now discuss on the forum
R
April 19, 2019, 9:55 a.m.
RED_Spider

мені важко це зараз навіть перевірити, тому що знайшов коміт, це ще було в 2016 році, і цей код не буде працювати коректно зараз, єдине скажу що це були QThread
i
April 17, 2019, 3:03 p.m.
ilya.guzikov

BlinCT, на стороне ++ это делать необходимо так как в qml при использовании функции append происходит перерисовка всех точек лини(как я понимаю) и из-за этого при использовании больших массиво...
April 10, 2019, 11:20 a.m.
Алексей Внуков

может тоже кому надо будет - QML не принимает QVector<QVector<int>> , при попытке вывести полученый вектор QML показывает что это QVariant(QVector<QVector<int> ...
SN
April 10, 2019, 9:36 a.m.
Stanislav Nykytiuk

Как реализовать такое меню, что бы нажмаешь меню подменю и выбор позиции? Данные меню и подменю в базе SQL.
Join us in social networks

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