Типы связанного списка - односвязные, двусвязные и круговой

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

Существует три распространенных типа связанного списка.

  • Единственный связанный список
  • Двусвязный список
  • Круговой связанный список
Единственный связанный список

Это самый распространенный. Каждый узел имеет данные и указатель на следующий узел.

Где адрес первого узла специальное имя, называемое 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;
Двусвязный список

Мы добавляем указатель на предыдущий узел в двусвязном списке. Таким образом, мы можем идти в любом направлении: вперед (next) или назад (prev).

Узел представлен как:

struct node {
    int data;
    struct node *next;
    struct node *prev;
}

Двусвязный список из трех участников может быть создан как:

/* Инициализируем узлы */
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;
one->prev = NULL;

two->next = three;
two->prev = one;

three->next = NULL;
three->prev = two;

/* Сохраняем адрес первого узла в голове */
head = one;
Круговой связанный список

Круговой связанный список - это вариант связанного списка, в котором последний элемент связан с первым элементом. Это образует круговую петлю.

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

  • Для односвязного списка указатель next последнего элемента указывает на первый элемент;
  • В двусвязном списке указатель prev первого элемента также указывает на последний элемент.

Круговой односвязный список из трех членов может быть создан как:

/* Инициализируем узлы */
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 = one;

/* Сохраняем адрес первого узла в голове */
head = one;
Рекомендуем хостинг TIMEWEB
Рекомендуем хостинг TIMEWEB
Стабильный хостинг, на котором располагается социальная сеть EVILEG. Для проектов на Django рекомендуем VDS хостинг.

Комментарии

Только авторизованные пользователи могут публиковать комментарии.
Пожалуйста, авторизуйтесь или зарегистрируйтесь
TT
13 июня 2019 г. 19:01
Taimoor Tanweer

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

  • Результат:66баллов,
  • Очки рейтинга-1
TT
13 июня 2019 г. 18:51
Taimoor Tanweer

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

  • Результат:75баллов,
  • Очки рейтинга2
ВМ
13 июня 2019 г. 12:30
Ваня Мороз

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

  • Результат:100баллов,
  • Очки рейтинга10
Последние комментарии
i
17 июня 2019 г. 6:10
ingenfly

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

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

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

Можно классу, который описывает точку, добавить сигнал, который подавать (emit), когда точка перемещается (переопределить mouseMoveEvent или mouseReleaseEvent). Так вот эти сигналы у каждой из...
i
13 июня 2019 г. 14:09
ingenfly

Здравствайте! Подскажите, пожалуйста: customPlot->xAxis2->setTickLabels(true); //Здесь включается отображение данных на оси xAxis2. а можно как-то продублировать информацию cus...
Сейчас обсуждают на форуме
I
19 июня 2019 г. 13:41
Intruder

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

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

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

Добрый день.В этом учебнике представлен код INSTALLED_APPS = ( ... 'rest_framework', 'snippets.apps.SnippetsConfig',) На строчке 'snippets.apps.SnippetsConf...
18 июня 2019 г. 14:24
Михаиллл

Спасибо, работает.Послушаю вашего совета.
Ищу работу?
25,000.00 руб. - 30,000.00 руб.
Разработчик Qt/C++
Barnaul, Altai Krai, Russia

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

EVILEG
О нас
Услуги
Присоединяйтесь к нам
© EVILEG 2015-2019
Рекомендует хостинг TIMEWEB