С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
lavan
53 / 53 / 1
Регистрация: 21.03.2009
Сообщений: 371
#1

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

09.08.2011, 13:51. Просмотров 1037. Ответов 19
Метки нет (Все метки)

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

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

Может я чего то не допонял(просто мне показалось,что приведенные решения были очень раздуты),но в односвязном списке зациклиться может только при участии последнего узла.Если нам зарание известно кол-во узлов то,все сводится к тому куда указывает
C++
1
2
if(last_node->next==NULL)
cout<<"Циклов нет";
Если зарание не известно сколько узлов то алгоритм Флойда подходит только частично,про построении матрицы смежности,чтобы по ней определить есть ли цикл
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.08.2011, 13:51
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Функция: определить, содержит ли односвязный список циклы (C++):

Задали односвязный линейный список с целыми числами. Создать новый список, который содержит элементы заданного списка в обратном порядке - C++
Задали односвязный линейный список с целыми числами. Создать новый список, который содержит элементы заданного списка в обратном порядке.

Односвязный список.Функция удаления - C++
Здравствуйте.Пытался организовать функцию удаления,но не получилось,добавлял цикл для начального заполнения,а потом удаления,не...

Односвязный список: функция добавления записи не работает - C++
Вообщем написал функцию для добавления записи в конец, все работает без ошибок, но когда просматриваю список функцией для просмотра, пишет,...

Функция добавления элемента в односвязный список в указанную позицию - C++
Здравствуйте! Помогите пожалуйста написать функцию добавления элемента в односвязный список в указанную позицию.Не могу сообразить как...

Сформировать список из 10 книг, используя динамическую структуру данных односвязный список - C++
друзья спасайте Сформировать список из 10 книг, используя динамическую структуру данных односвязный список С++

Линейный массив содержит значения некоторой функции.Определить сколько раз функция сменила знак. - C++
Помогите пожалуйста!! 1. Линейный массив содержит значения некоторой функции y(x) на интервале от 0 до 2 с шагом 0,01. Определить сколько...

19
taras atavin
3570 / 1754 / 91
Регистрация: 24.11.2009
Сообщений: 27,567
09.08.2011, 13:58 #2
Цитата Сообщение от lavan Посмотреть сообщение
Может я чего то не допонял,но в односвязном списке зациклиться может только при участии последнего узла
Правильно. Но откуда известно, какой из них последний? Вот поэтому то и используется проверка всего списка, пока не встретится указатель, который уже был.
0
castaway
Эксперт С++
4916 / 3024 / 370
Регистрация: 10.11.2010
Сообщений: 11,081
Записей в блоге: 10
Завершенные тесты: 1
09.08.2011, 13:59 #3
А в чем, собственно, вопрос?
0
lavan
53 / 53 / 1
Регистрация: 21.03.2009
Сообщений: 371
09.08.2011, 17:50  [ТС] #4
Вопроса,по сути нет,есть попытка разобраться зачем нужна такая сложная(на мой взгляд) реализация простого алгоритма?Часто сталкиваюсь с тем что люди замысловато кодируют не сложные вещи,поэтому хочу понять как все таки правильно делать?Я пишу код по правилу: Все должно быть очень просто!
А 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;
}
0
castaway
Эксперт С++
4916 / 3024 / 370
Регистрация: 10.11.2010
Сообщений: 11,081
Записей в блоге: 10
Завершенные тесты: 1
09.08.2011, 18:05 #5
Допустим у тебя есть указатель на 1-й элемент списка. Ты отталкиваясь от него идешь на следующий, следующий и так далее... Так вот если этот следующий == первому значит список цикличен.
Я себе так это представляю.
0
ValeryLaptev
Эксперт С++
1046 / 825 / 48
Регистрация: 30.04.2011
Сообщений: 1,659
09.08.2011, 18:31 #6
lazybiz, Не обязательно равен первому . Может быть ссылка на людой элемент списка. В том числе - на себя.
0
lavan
53 / 53 / 1
Регистрация: 21.03.2009
Сообщений: 371
09.08.2011, 18:44  [ТС] #7
Вопрос не в том,как определить есть ли цикл!А наверное как правильно кодировать такого рода задачи
вы не правильно представляете,а если последний указывает на второй или на третий? не будете же вы каждый новый узел сравнивать со всеми предыдущими!
Здесь достаточно узнать адрес последнего узла и в нем посмотреть чему равняется last_node->next и поскольку адреса в куче выделяются последовательно,то
C++
1
2
if(&last_node>&last_node->next)
//есть цикл
А если использовать алгоритм флойда то строить матрицу смежности пока значение
C++
1
matr[i][j]>i
0
castaway
Эксперт С++
4916 / 3024 / 370
Регистрация: 10.11.2010
Сообщений: 11,081
Записей в блоге: 10
Завершенные тесты: 1
09.08.2011, 18:48 #8
Цитата Сообщение от lavan Посмотреть сообщение
поскольку адреса в куче выделяются последовательно
Это вот почему ты так решил?
1
lavan
53 / 53 / 1
Регистрация: 21.03.2009
Сообщений: 371
09.08.2011, 19:11  [ТС] #9
В книги прочитал.Только в какой сейчас не вспомню

Добавлено через 17 минут
кроме того,если бы это было не так,то была бы возможна такая ситуация,что в куче есть две ячейки размером word идущие не последовательно и объект размером dword тогда для этого объекта не бало бы места,а это не рациональное использование памяти
0
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1306 / 1221 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
09.08.2011, 19:29 #10
Цитата Сообщение от lavan Посмотреть сообщение
наверно лучше использовать queue потому что это
лучше подходит к однонаправленному списку?
Открой тайну мироздания, как очередью можно заменить односвязный список?
0
lavan
53 / 53 / 1
Регистрация: 21.03.2009
Сообщений: 371
09.08.2011, 19:33  [ТС] #11
а где мной написанно ЗАМЕНИТЬ?
0
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1306 / 1221 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
09.08.2011, 19:36 #12
В принципе, если список односвязный, то без разницы с какого узла начинать проверку.
Нужно сохранить адрес первого проверяемого узла и ринуться дальше, до конца. Если есть цикл, то в итоге вернёшься к этому же узлу. т.е. дополнительно требуется всего один указатель и сложность линейно зависит от количества элементов. В любых других ситуациях речь идёт уже о двух односвязных списках.
Проверить можно точно так же, но сложность станет квадратичной. Но два списка вместо одного - ошибка.
Я вообще не понимаю, что это за задача. Наверное постановка не корректна.

Добавлено через 54 секунды
Цитата Сообщение от lavan Посмотреть сообщение
ЗАМЕНИТЬ?
А слово Использовать что подразумевало? Как вообще очередь там оказалась?
0
grizlik78
Эксперт С++
1972 / 1465 / 122
Регистрация: 29.05.2011
Сообщений: 3,033
09.08.2011, 19:42 #13
Цитата Сообщение от lavan Посмотреть сообщение
роме того,если бы это было не так,то была бы возможна такая ситуация,что в куче есть две ячейки размером word идущие не последовательно и объект размером dword тогда для этого объекта не бало бы места,а это не рациональное использование памяти
Можешь смеяться, но так и есть. В куче может быть такая ситуация, что 100 МБ свободно, но при этом нельзя выделить и 1 МБ. Избежать фрагментации кучи — не такое уж и лёгкое дело (в общем случае).
0
lavan
53 / 53 / 1
Регистрация: 21.03.2009
Сообщений: 371
09.08.2011, 19:58  [ТС] #14
http://www.cyberforum.ru/cpp-experts/thread308978.html
Там был использован контейнер set,а я сказал,что может лучше использовать queue для сохранения элементов списка поскольку очередь лучше отображает однонаправленный список

Добавлено через 6 минут
grizlik78, а можешь направить где это можно прочесть?
0
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1306 / 1221 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
09.08.2011, 20:05 #15
Цитата Сообщение от lavan Посмотреть сообщение
Там был использован контейнер set,а я сказал,что может лучше использовать queue для сохранения элементов списка поскольку очередь лучше отображает однонаправленный список
ПОЧЕМУ НЕ std::list??? Каким образом ты можешь заменить set/list очередью? Это не совместимые контейнеры. Если ты можешь заменить set очередью, то это ошибка проектирования. Или совершенно без разницы, какой контейнер использовать и тогда нужно использовать std::vector.
0
09.08.2011, 20:05
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.08.2011, 20:05
Привет! Вот еще темы с ответами:

Создать двусвязный список групп факультета, где каждая группа представляет собой односвязный список студентов - C++
Задание: создайте двусвязный список групп факультета. Каждая группа представляет собой односвязный список студентов. Помогите пожалуйста,...

Односвязный список - C++
Посмотрите программу, правильно ли я вывожу список? Почему список выводится только из 7 цифр, и как можно написать с помощью функций?...

Односвязный список C++ - C++
помогите решить проблему с выводом суммы, буду благодарен #include &lt;iostream&gt; #include &lt;cctype&gt; using namespace std; struct...

Односвязный список - C++
Люди помогите пожалуйста с лабораторной сделал прогу по заданию а преподаватель говорит что не правильно сделана функция поиска и вообще...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.