Функция: определить, содержит ли односвязный список циклы

@lavan · Регистрация: 21.03.2009

Студворк — интернет-сервис помощи студентам

По скольку я не могу задавать вопросы в разделе С++ для специалистов,задаю его здесь
Была тема

Написать функцию, определяющую содержит ли односвязный список циклы (например, последний ссылается на второй).

Может я чего то не допонял(просто мне показалось,что приведенные решения были очень раздуты),но в односвязном списке зациклиться может только при участии последнего узла.Если нам зарание известно кол-во узлов то,все сводится к тому куда указывает

C++
1
2
if(last_node->next==NULL)
cout<<"Циклов нет";

Если зарание не известно сколько узлов то алгоритм Флойда подходит только частично,про построении матрицы смежности,чтобы по ней определить есть ли цикл

@taras atavin · 09.08.2011, 13:58

Сообщение от lavan

Может я чего то не допонял,но в односвязном списке зациклиться может только при участии последнего узла

Правильно. Но откуда известно, какой из них последний? Вот поэтому то и используется проверка всего списка, пока не встретится указатель, который уже был.

@castaway · 09.08.2011, 13:59

А в чем, собственно, вопрос?

@lavan · 09.08.2011, 17:50 **[ТС]**

Вопроса,по сути нет,есть попытка разобраться зачем нужна такая сложная(на мой взгляд) реализация простого алгоритма?Часто сталкиваюсь с тем что люди замысловато кодируют не сложные вещи,поэтому хочу понять как все таки правильно делать?Я пишу код по правилу: Все должно быть очень просто!
А STL библиотеку использую только если заранее известно,что нужно будет часто использовать ее алгоритмы.Даже если и использовать в этом случае STL наверно лучше использовать queue потому что это
лучше подходит к однонаправленному списку?

Но откуда известно, какой из них последний?

Отсюда известно

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <class T>
singly_linked<T>& singly_linked<T>::push(const T& val)
{
    node<T>* new_node = new node<T>(val, NULL);
 
    if(!first)
        first = new_node;
    else
        last->next = new_node;
    last = new_node;
 
    ++sz;//Если это подсчет узлов
    
    return *this;
}

@castaway · 09.08.2011, 18:05

Допустим у тебя есть указатель на 1-й элемент списка. Ты отталкиваясь от него идешь на следующий, следующий и так далее... Так вот если этот следующий == первому значит список цикличен.
Я себе так это представляю.

@ValeryLaptev · 09.08.2011, 18:31

lazybiz, Не обязательно равен первому . Может быть ссылка на людой элемент списка. В том числе - на себя.

@lavan · 09.08.2011, 18:44 **[ТС]**

Вопрос не в том,как определить есть ли цикл!А наверное как правильно кодировать такого рода задачи
вы не правильно представляете,а если последний указывает на второй или на третий? не будете же вы каждый новый узел сравнивать со всеми предыдущими!
Здесь достаточно узнать адрес последнего узла и в нем посмотреть чему равняется last_node->next и поскольку адреса в куче выделяются последовательно,то

C++
1
2
if(&last_node>&last_node->next)
//есть цикл

А если использовать алгоритм флойда то строить матрицу смежности пока значение

C++
1
matr[i][j]>i

@castaway · 09.08.2011, 18:48

Сообщение от lavan

поскольку адреса в куче выделяются последовательно

Это вот почему ты так решил?

@lavan · 09.08.2011, 19:11 **[ТС]**

В книги прочитал.Только в какой сейчас не вспомню

Добавлено через 17 минут
кроме того,если бы это было не так,то была бы возможна такая ситуация,что в куче есть две ячейки размером word идущие не последовательно и объект размером dword тогда для этого объекта не бало бы места,а это не рациональное использование памяти

@Deviaphan · 09.08.2011, 19:29

Сообщение от lavan

наверно лучше использовать queue потому что это
лучше подходит к однонаправленному списку?

Открой тайну мироздания, как очередью можно заменить односвязный список?

@lavan · 09.08.2011, 19:33 **[ТС]**

а где мной написанно ЗАМЕНИТЬ?

@Deviaphan · 09.08.2011, 19:36

В принципе, если список односвязный, то без разницы с какого узла начинать проверку.
Нужно сохранить адрес первого проверяемого узла и ринуться дальше, до конца. Если есть цикл, то в итоге вернёшься к этому же узлу. т.е. дополнительно требуется всего один указатель и сложность линейно зависит от количества элементов. В любых других ситуациях речь идёт уже о двух односвязных списках.
Проверить можно точно так же, но сложность станет квадратичной. Но два списка вместо одного - ошибка.
Я вообще не понимаю, что это за задача. Наверное постановка не корректна.

Добавлено через 54 секунды

Сообщение от lavan

ЗАМЕНИТЬ?

А слово Использовать что подразумевало? Как вообще очередь там оказалась?

@grizlik78 · 09.08.2011, 19:42

Сообщение от lavan

роме того,если бы это было не так,то была бы возможна такая ситуация,что в куче есть две ячейки размером word идущие не последовательно и объект размером dword тогда для этого объекта не бало бы места,а это не рациональное использование памяти

Можешь смеяться, но так и есть. В куче может быть такая ситуация, что 100 МБ свободно, но при этом нельзя выделить и 1 МБ. Избежать фрагментации кучи — не такое уж и лёгкое дело (в общем случае).

@lavan · 09.08.2011, 19:58 **[ТС]**

https://www.cyberforum.ru/cpp-... 08978.html
Там был использован контейнер set,а я сказал,что может лучше использовать queue для сохранения элементов списка поскольку очередь лучше отображает однонаправленный список

Добавлено через 6 минут
grizlik78, а можешь направить где это можно прочесть?

@Deviaphan · 09.08.2011, 20:05

Сообщение от lavan

Там был использован контейнер set,а я сказал,что может лучше использовать queue для сохранения элементов списка поскольку очередь лучше отображает однонаправленный список

ПОЧЕМУ НЕ std::list??? Каким образом ты можешь заменить set/list очередью? Это не совместимые контейнеры. Если ты можешь заменить set очередью, то это ошибка проектирования. Или совершенно без разницы, какой контейнер использовать и тогда нужно использовать std::vector.

@grizlik78 · 09.08.2011, 20:10

Сообщение от lavan

grizlik78, а можешь направить где это можно прочесть?

Не знаю. Но давай попробуем смоделировать. Вот есть куча с размером в 100 объектов некоторого типа. И мы последовательно создаём 100 элементов списка. Пусть при этом память нам выделялась последовательно, тогда действительно каждый следующий элемент имеет адрес бльше предыдущего, а в куче больше нет места. Теперь удаляем элемент из головы (с освобождением памяти) и пытаемся создать новый в конце. Какой у него будет адрес? Естественно адрес бывшего первого элемента, ведь вся остальная часть кучи занята.
Да даже и такие сложности ни к чему, если вспомнить, что обмен значений в списке производится обычно просто заменой ссылок (указателей), а сами элементы остаются в куче на своих местах.

@lavan · 09.08.2011, 20:16 **[ТС]**

Потому что List больше подходит для двусвязного списка.А на счет выбора контейнера ты по сути прав.Я смотрел реализации которые были предложены и они мне показались не много "раздуты" вот я и пытаюсь разобраться

@Deviaphan · 09.08.2011, 20:22

Сообщение от lavan

Потому что List больше подходит для двусвязного списка

Очередь не может заменить список (никакой), та же как и set не может заменить список.

Если память мне не изменяет, в STL список как-раз двусвязный. Это было бы вполне логично, т.к. оверхэда всё равно нет, благодаря особенностям распределения памяти.

@easybudda · 10.08.2011, 01:53

Может я, любитель, чего-то не понимаю, но обратные ссылки в списке как-то так должны бы находиться:

C
1
2
3
4
5
6
7
8
9
10
11
12
node_t * find_ref_ptr(node_t * head){
    node_t * ptr;
    
    while ( head ){
        for ( ptr = head->next; ptr != NULL; ptr = ptr->next )
            if ( ptr->next == head )
                return ptr;
        head = head->next;
    }
    
    return NULL;
}

Ну по-простому, без всяких там

Сообщение от lavan

использовать алгоритм флойда

@lavan · 10.08.2011, 13:35 **[ТС]**

Всем спасибо за участие!

Новые блоги и статьи Все статьи Все блоги /
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	Влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .

@castaway 4986 / 3093 / 456 Регистрация: 10.11.2010 Сообщений: 11,170 Записей в блоге: 10
	09.08.2011, 13:59
	А в чем, собственно, вопрос? 0

@castaway 4986 / 3093 / 456 Регистрация: 10.11.2010 Сообщений: 11,170 Записей в блоге: 10
	09.08.2011, 18:05
	Допустим у тебя есть указатель на 1-й элемент списка. Ты отталкиваясь от него идешь на следующий, следующий и так далее... Так вот если этот следующий == первому значит список цикличен. Я себе так это представляю. 0

@ValeryLaptev 1069 / 848 / 60 Регистрация: 30.04.2011 Сообщений: 1,659
	09.08.2011, 18:31
	lazybiz, Не обязательно равен первому . Может быть ссылка на людой элемент списка. В том числе - на себя. 0

@lavan 53 / 53 / 8 Регистрация: 21.03.2009 Сообщений: 371
	09.08.2011, 19:11 [ТС]
	В книги прочитал.Только в какой сейчас не вспомню Добавлено через 17 минут кроме того,если бы это было не так,то была бы возможна такая ситуация,что в куче есть две ячейки размером word идущие не последовательно и объект размером dword тогда для этого объекта не бало бы места,а это не рациональное использование памяти 0

@lavan 53 / 53 / 8 Регистрация: 21.03.2009 Сообщений: 371
	09.08.2011, 19:33 [ТС]
	а где мной написанно ЗАМЕНИТЬ? 0

@lavan 53 / 53 / 8 Регистрация: 21.03.2009 Сообщений: 371
	09.08.2011, 19:58 [ТС]
	https://www.cyberforum.ru/cpp-... 08978.html Там был использован контейнер set,а я сказал,что может лучше использовать queue для сохранения элементов списка поскольку очередь лучше отображает однонаправленный список Добавлено через 6 минут grizlik78, а можешь направить где это можно прочесть? 0

@lavan 53 / 53 / 8 Регистрация: 21.03.2009 Сообщений: 371
	09.08.2011, 20:16 [ТС]
	Потому что List больше подходит для двусвязного списка.А на счет выбора контейнера ты по сути прав.Я смотрел реализации которые были предложены и они мне показались не много "раздуты" вот я и пытаюсь разобраться 0

@lavan 53 / 53 / 8 Регистрация: 21.03.2009 Сообщений: 371
	10.08.2011, 13:35 [ТС]
	Всем спасибо за участие! 0