80

Тут говорят!
Авторизация
Список форумов
Войти через акаунт
 

Списки в Си
Подписаться/отписаться на тему (функция доступна только для зарегистрированных пользователей) Любимая тема (вкл/выкл) []

Страницы: 1  2   из  2
Добавление сообщений к этой теме для незарегистрированных пользователей невозможно
Тему смотрит 1 незарегистрированный пользователь
Модераторы
Рейтинг темы:   (1677 просмотров)
Вы не можете создавать новые темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения
 

Ogonek Ogonek в оффлайне

графоман
Сообщений: 2 602

Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный

Кароче такой вопрос .. допустим есть список .. ну первый элемент указывает на второй, второй на третий, третий на четвёртый , и тд .. а например 7ой указывает на второй !!обычная прямой список в си можно вывести типа так a->cur=topwhile (curr){cout a; // чтонить выводимcurr = curr -> next; // переходим на следущую }и выведется он благодоря тому что паследний элемент в нём указывает на null а первый на top а теперь представим что мы имеем такой список как я описал в начале и не знаем де он зацикливается не знаем его размера, но нам нужно вывести все его элементы ... можт кто поможет как это сделать ?

--------------------
любая диктатура в конечном итоге кончается рано или поздно катастрофой для страны и для народа
 

Ogonek Ogonek в оффлайне

графоман
Сообщений: 2 602

Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный

ps )) как мне стыдно что не знаю си

--------------------
любая диктатура в конечном итоге кончается рано или поздно катастрофой для страны и для народа
 

alexey_public alexey_public в оффлайне

графоман
Сообщений: 5 817

alexey_public популярный alexey_public популярный alexey_public популярный alexey_public популярный alexey_public популярный alexey_public популярный alexey_public популярный alexey_public популярный alexey_public популярный alexey_public популярный alexey_public популярный

А какие проблемы - да и С тут не при чем.У тбя обязательно должен быть адрес первого элемента списка (иначе все - память потеряна). И начиная с него ты можешь пройти по всему списку и найти все необходимое.

--------------------
Алексей
 

Ogonek Ogonek в оффлайне

графоман
Сообщений: 2 602

Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный

Адрес первого есть !! а какойто элемент указывает на второй напрмер ... и тогда такой цикл while (curr){ \ выводим чтониьcurr = curr -> next; // переходим на следущую }просто зацикливает , т.к. curr никогда не смениься на null

--------------------
любая диктатура в конечном итоге кончается рано или поздно катастрофой для страны и для народа
 

alexey_public alexey_public в оффлайне

графоман
Сообщений: 5 817

alexey_public популярный alexey_public популярный alexey_public популярный alexey_public популярный alexey_public популярный alexey_public популярный alexey_public популярный alexey_public популярный alexey_public популярный alexey_public популярный alexey_public популярный

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

--------------------
Алексей
 

Аноним Аноним в оффлайне

забанен
Сообщений: 0

Аноним популярный Аноним популярный Аноним популярный Аноним популярный Аноним популярный Аноним популярный Аноним популярный Аноним популярный Аноним популярный Аноним популярный Аноним популярный

тут два цикла будетпервый от начала и до nullвторой от начала и до первогои смотришь не равен ли указатель на следующий элемент из первого цикла на какой-нить элемент из второго циклаесли равен, значит кольцо, выходи
 
 

Govage Govage в оффлайне

графоман
Сообщений: 3 934

Govage популярный Govage популярный Govage популярный Govage популярный Govage популярный Govage популярный Govage популярный Govage популярный Govage популярный Govage популярный Govage популярный

Ogonek (09.01.07 13:36) писал(a):
Адрес первого есть !! а какойто элемент указывает на второй напрмер ... и тогда такой цикл while (curr){ выводим чтониьcurr = curr -> next; // переходим на следущую }просто зацикливает , т.к. curr никогда не смениься на null

Выходить, когда curr == первому элементу списка.

--------------------
Менск, Беларусь.
 

Ogonek Ogonek в оффлайне

графоман
Сообщений: 2 602

Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный

Govage (09.01.07 17:46) писал(a):
Выходить, когда curr == первому элементу списка.

навсегда зациклит же...

--------------------
любая диктатура в конечном итоге кончается рано или поздно катастрофой для страны и для народа
 

Аноним Аноним в оффлайне

забанен
Сообщений: 0

Аноним популярный Аноним популярный Аноним популярный Аноним популярный Аноним популярный Аноним популярный Аноним популярный Аноним популярный Аноним популярный Аноним популярный Аноним популярный

Govage (09.01.07 17:46) писал(a):
Выходить, когда curr == первому элементу списка.

ага, 10 элемент ссылается на 4будет так:начинаем с 1 доходим до 10, возвращаемся в 4, опять до 10 и так вечночто не понятного? надо проверять все от 1 до curr != curr->next;
 

Ogonek Ogonek в оффлайне

графоман
Сообщений: 2 602

Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный

Loki (09.01.07 13:42) писал(a):
тут два цикла будетпервый от начала и до nullвторой от начала и до первогои смотришь не равен ли указатель на следующий элемент из первого цикла на какой-нить элемент из второго циклаесли равен, значит кольцо, выходи

а можешь код написать, хоть наброски какие нить ) ?

--------------------
любая диктатура в конечном итоге кончается рано или поздно катастрофой для страны и для народа
 

Аноним Аноним в оффлайне

забанен
Сообщений: 0

Аноним популярный Аноним популярный Аноним популярный Аноним популярный Аноним популярный Аноним популярный Аноним популярный Аноним популярный Аноним популярный Аноним популярный Аноним популярный



curr=top;

while (curr)
{
cout a;

curr2 = top;
while(curr2 != curr)
{
if(curr2 == curr->next)
return; //НАШЛИ КОЛЬЦО

curr2 = curr2->next;
}

curr = curr->next;
}
 

Sinner Sinner в оффлайне

писатель
Сообщений: 1 251

Sinner популярный Sinner популярный Sinner популярный Sinner популярный Sinner популярный Sinner популярный Sinner популярный Sinner популярный Sinner популярный Sinner популярный Sinner популярный

Loki (09.01.07 18:13) писал(a):


curr=top;

while (curr)
{
cout a;

curr2 = top;
while(curr2 != curr)
{
if(curr2 == curr->next)
return; //НАШЛИ КОЛЬЦО

curr2 = curr2->next;
}

curr = curr->next;
}

O(n^2).
но если скорость не критчна то хорошее решение. А вообще задача распространенная. Т.е. имеется граф, обходя который ищутся циклы. Нарыл на полочке у себя пособее такое хорошее, когда в институте нам читали комбинаторные алгоритмы. Так вот уткнувшиьс в аглоритм Краскала(построения кратчайшего свзяывающего дерева на графе), нашел такую же проблему. Решается там проблема эта при помощи решения еще более распроестраненной задачи - "Объединить-найти":
" Задано множество M и разбиение его на непересекающиеся подмножества : M1,...Mn .
Необходимо уметь выполнять произвольную последовательность операций Найти (Find) и Объединить (Union).
Find (i) - для заданного элемента найти подмножество M(i) , содержащее этот элемент.
Union (Mi, Mj): - объединить подмножества Mi и Mj.
В начале работы алгоритма каждая из вершин образует отдельное подмножество. Для того, чтобы выяснить, образует ли рассматриваемое ребро (i,j) цикл с ранее выбранными, достаточно найти, в каких подмножествах содержатся концы этого ребра, т.е. выполнить две операции Найти: = Find(i) и = Find(j). Если Mi = Mj , то это значит, что вершины i и j находятся в одном и том же поддереве, ребро образует цикл с ребрами этого поддерева . Если же нет , то вершины i и j находятся в разных поддеревьях, ребро не образует цикл с ребрами, выбранными ранее, выполняем объединить: Union (i,j )
"
далее описывается как оценку можно улучшить до O(n * log n)

--------------------
Can You Handle Life?
 
 

Мунька Мунька в оффлайне

графоман
Сообщений: 31 482

Мунька имеет репутацию, которую нельзя пошатнуть Мунька имеет репутацию, которую нельзя пошатнуть Мунька имеет репутацию, которую нельзя пошатнуть Мунька имеет репутацию, которую нельзя пошатнуть Мунька имеет репутацию, которую нельзя пошатнуть Мунька имеет репутацию, которую нельзя пошатнуть Мунька имеет репутацию, которую нельзя пошатнуть Мунька имеет репутацию, которую нельзя пошатнуть Мунька имеет репутацию, которую нельзя пошатнуть Мунька имеет репутацию, которую нельзя пошатнуть Мунька имеет репутацию, которую нельзя пошатнуть

Блин, такая задача тривиальная, что мне даже мозгами шевелить не хотелось, просто почитала, как тут ее решили. Если скорость и объемы не критичны, то можно и собственный алгоритм сходу придумать. Типа завести динамический массив указателей, а потом с каждым новым указателем смотреть, нет ли его в этом массиве. Тупо, идиотично, но я - практик, я высокой теорией не занимаюсь, у меня главное - чтобы задача была решена. Можно еще что-нибудь придумать. Типа повторного просмотра списка при переходе на каждый новый элемент.

--------------------
Самыми опасные дураки - это дураки с высоким интеллектом; они думают, что они самые умные.
 

alexey_public alexey_public в оффлайне

графоман
Сообщений: 5 817

alexey_public популярный alexey_public популярный alexey_public популярный alexey_public популярный alexey_public популярный alexey_public популярный alexey_public популярный alexey_public популярный alexey_public популярный alexey_public популярный alexey_public популярный

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

--------------------
Алексей
 

sa76 sa76 в оффлайне

энтузиаст
Сообщений: 313

sa76 на старте

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

Sinner Sinner в оффлайне

писатель
Сообщений: 1 251

Sinner популярный Sinner популярный Sinner популярный Sinner популярный Sinner популярный Sinner популярный Sinner популярный Sinner популярный Sinner популярный Sinner популярный Sinner популярный

sa76 (11.01.07 14:56) писал(a):
Факт того, что в списке образовались какие-то неконтролируемые циклы, говорит о том, что все плохо, например возможна потеря объектов, которые не попали в один цикл с головным указателем. Программа не должна быть так написана.

ну почему не должна, может быть это реализация ориентированного графа, по-которому мы проходимся(хотя конечно, такой обход графа не совсем правильный)

--------------------
Can You Handle Life?
 

sa76 sa76 в оффлайне

энтузиаст
Сообщений: 313

sa76 на старте

Sinner (11.01.07 15:14) писал(a):
ну почему не должна, может быть это реализация ориентированного графа, по-которому мы проходимся(хотя конечно, такой обход графа не совсем правильный)

Невырожденный граф описывается двумерной матрицей смежности, например в виде двумерного массива (узлы:соседи). Структура такого типа уже сложней одномерного однонаправленного списка, о котором ведет речь Ogonek, как очевидно из первых сообщений.
Если у него есть и другой способ обхода, кроме упомянутого одномерного списка - тогда не страшно.
 

Sаnya Sаnya в оффлайне

энтузиаст
Сообщений: 484

Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный

Есть задачка на эту тему:
Имеется односторонний список, необходимо неиспользуя дополнительной памяти и используя средства только С утвердить или опровергнуть факт наличия в нем циклов. Данных об используемой машне не имеем.
 

Ынг - профиль удален пользователем

Guest

Sаnya (12.01.07 04:33) писал(a):
Есть задачка на эту тему: Имеется односторонний список, необходимо неиспользуя дополнительной памяти и используя средства только С утвердить или опровергнуть факт наличия в нем циклов. Данных об используемой машне не имеем.

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

Ogonek Ogonek в оффлайне

графоман
Сообщений: 2 602

Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный Ogonek популярный

Ынг (12.01.07 15:12) писал(a):
Если можно изменять элементы списка - помечай как-нибудь пройденные. Тогда можно обойтись одним циклом.

я думал так сделать .. но .. какойто способ .. как отмазка какая-то .. хз

--------------------
любая диктатура в конечном итоге кончается рано или поздно катастрофой для страны и для народа
 

Sаnya Sаnya в оффлайне

энтузиаст
Сообщений: 484

Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный

А если имем оди итератор?
 

Sаnya Sаnya в оффлайне

энтузиаст
Сообщений: 484

Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный

Впринципе решение дано.А если имем один итератор? Помечать естественно ничего нельзя.
 

alexey_public alexey_public в оффлайне

графоман
Сообщений: 5 817

alexey_public популярный alexey_public популярный alexey_public популярный alexey_public популярный alexey_public популярный alexey_public популярный alexey_public популярный alexey_public популярный alexey_public популярный alexey_public популярный alexey_public популярный

Массив тогда

--------------------
Алексей
 

Sinner Sinner в оффлайне

писатель
Сообщений: 1 251

Sinner популярный Sinner популярный Sinner популярный Sinner популярный Sinner популярный Sinner популярный Sinner популярный Sinner популярный Sinner популярный Sinner популярный Sinner популярный

Sаnya (12.01.07 18:51) писал(a):
Впринципе решение дано.А если имем один итератор? Помечать естественно ничего нельзя.

тогда задача, как говорят математики, алгоритмически не разрешима имхо

--------------------
Can You Handle Life?
 

Sаnya Sаnya в оффлайне

энтузиаст
Сообщений: 484

Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный

разрешима
 

Sаnya Sаnya в оффлайне

энтузиаст
Сообщений: 484

Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный

Никто задачку не решил? Решение давать?
 

Sinner Sinner в оффлайне

писатель
Сообщений: 1 251

Sinner популярный Sinner популярный Sinner популярный Sinner популярный Sinner популярный Sinner популярный Sinner популярный Sinner популярный Sinner популярный Sinner популярный Sinner популярный

решение в студию!

--------------------
Can You Handle Life?
 

Sаnya Sаnya в оффлайне

энтузиаст
Сообщений: 484

Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный

Даю ДЫРЯВУЮ реализацию, идея думаю ясна. Если вы это у себя запустите и у вас что нибудь рухнет, это ваша вина, а не моя. Итак:typedef struct{void* next;}list;bool NoCycle(const list *header){if (list==NULL)return false; unsigned long step=0, maxLegalStep=1
 

Sinner Sinner в оффлайне

писатель
Сообщений: 1 251

Sinner популярный Sinner популярный Sinner популярный Sinner популярный Sinner популярный Sinner популярный Sinner популярный Sinner популярный Sinner популярный Sinner популярный Sinner популярный

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

жук

--------------------
Can You Handle Life?
 

Sаnya Sаnya в оффлайне

энтузиаст
Сообщений: 484

Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный Sаnya популярный

Первое что пришло в голову, вообще-то эта моя проблема, у меня как правило все сырцы переписываются три-четыре раза.
Страницы: 1  2   из  2
 
Быстрый переход
[]
Вверх
HOSTER.BY: профессиональный хостинг и регистрация доменов .BY
Более 35000 сайтов выбрали нас. Присоединяйтесь!
 
РЕСУРСЫ ПОРТАЛА
   Все ресурсы