80

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

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

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

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 популярный

Первое что пришло в голову, вообще-то эта моя проблема, у меня как правило все сырцы переписываются три-четыре раза.
 

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

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

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

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

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

Guest

Sаnya (22.01.07 11:23) писал(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 популярный

Loki (26.01.07 10:02) писал(a):
эм...
а если эти элементы в список когда-то добавлялись, то наверное можно подсчитать их кол-во, считать хотя бы во время добавления.

тогда когда проходишь по списку то считаешь шаги исчо раз, если счётчик стал больше кол-ва элементов, значит есть кольцо.

кроме самого списка будет всего две переменных: размер и счётчик.

По условию задачи список дан, о моменте или том кто его формировал ничего неизвествно. Так что незачет.
 

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

Guest

Sаnya (26.01.07 11:15) писал(a):
Почему?

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

Sinner Sinner в оффлайне

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

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

Ынг (27.01.07 00:06) писал(a):
Потому что список может располагаться и не в оперативной памяти. Представьте более общий случай: функция получает на входе не указатель на голову списка, а интерфейс к методами для доступа к следующему элементу и для клонирования. Сам список может быть, например, в файле. Или же вообще генерироваться какой-либо программой.

Данная программа будет работать лишь для определенного, пусть и очень большого, списка. Как только максимум превышен - все.

а какая разница, где у нас список находится. Естественно, какие-то узлы в данный момент могут находиться и не в оперативной памяти, а в файле подкачки, например. Важно то, что адресное пространство ограничено в принципе. И ограничение сверху на максимальное кол-во адресов всегда можно найти - 2^(sizeof(list*) * 8 ) - 1, а значит и next'ов не может быть этого числа, т.е. кол-ва элементов списка вместе с NULL
если к тому же еще привязываться к конкретной ОС, к примеру, Windows, то там часть адресного пространства вообще зарезервирована и maxLegalStep реально будет гораздо меньше

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

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

Guest

Sinner (26.01.07 14:38) писал(a):
а какая разница, где у нас список находится. Естественно, какие-то узлы в данный момент могут находиться и не в оперативной памяти, а в файле подкачки, например. Важно то, что адресное пространство ограничено в принципе. И ограничение сверху на максимальное кол-во адресов всегда можно найти - 2^(sizeof(list*) * 8 ) - 1, а значит и next'ов не может быть этого числа, т.е. кол-ва элементов списка вместе с NULLесли к тому же еще привязываться к конкретной ОС, к примеру, Windows, то там часть адресного пространства вообще зарезервирована и maxLegalStep реально будет гораздо меньше

Поясню. Возьмем интерфейс:interface IList{ bool FGetNextItem(ListItem *pItem);}Функция FGetNextItem заносит следующий элемент по адресу, указанному в pItem и возвращает true; false возвращается, когда элементы исчерпаны. При помощи такого интерфейса я могу возвратить столько элементов списка, что они ни в одно адресное пространство не поместятся. И для такого рода списков (как и для списков в общем) задачу одним итератором не решить.
 

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 популярный

Ынг (27.01.07 01:52) писал(a):
Поясню. Возьмем интерфейс:

interface IList
{
bool FGetNextItem(ListItem *pItem);
}

Функция FGetNextItem заносит следующий элемент по адресу, указанному в pItem и возвращает true; false возвращается, когда элементы исчерпаны. При помощи такого интерфейса я могу возвратить столько элементов списка, что они ни в одно адресное пространство не поместятся. И для такого рода списков (как и для списков в общем) задачу одним итератором не решить.

простите, может быть я не совсем понял ваше пояснение
Код:
  IList* list = GetList();
  ListItem* item1;
  ListItem* item2;
 .......................
  ListItem* itemN;
.......................
bool b =  list->FGetNextItem(item1);
// если b == true, то по адресу item1 будет элмент, т.е. *item1 - содержит объект ListItem;
// ... и т.д.
b = list->FGetNextItem(itemN);
// ...
Элементы списка, допустим, возвращает внешняя программа. Но размер указателя ListItem* ограничен. И как тогда при помощи такого интерфейса можно возвратить столько элементов списка, сколько угодно? ведь переменных itemN не хватит просто(а я, к примеру, хочу их всех запомнить, как написал выше)....
Если вы имеете ввиду, что программа динамически возвращает элементы списка, т.е. интерфейс делает старые адреса, вообще говоря, невалидными, и по ним могут располагаться уже новые объекты(т.е. при проходе списка, адреса pItem для новых элементов могут повторяться), тогда не ясно, каким образом задачу в общем случае можно решить с двумя, тремя, и т.д. проходами по списку
Конечно, для абстрактного списка, естественно, такой алгоритм не подойдет.

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

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

Guest

Sinner (27.01.07 05:29) писал(a):
простите, может быть я не совсем понял ваше пояснение IList* list = GetList(); ListItem* item1; ListIt... ...образом задачу в общем случае можно решить с двумя, тремя, и т.д. проходами по списку Конечно, для абстрактного списка, естественно, такой алгоритм не подойдет.

Функция получения следующего элемента копирует этот самый элемент по указанному адресу (а не возвращает его адрес); получение элемента происходит так:ListItem item;pList->FGetNextItem(&item);Таким образом я могу работать с практически бесконечными списками. В случае такого списка задача решается двумя итераторами с разным шагом; встретившиеся итераторы указывают на наличие цикла. Одним итератором без использования доп. памяти задачу в общем виде не решить.
 

janek_1 janek_1 в оффлайне

новичок
Сообщений: 51

janek_1 на старте

Первоначально задача у OGONEK состояла в том, чтобы выдать на печать одонаправленный линейный список даже в том случае, если в нём по каким либо причинам появилась петля (такое может быть в случае, если несколько потоков процесса добавляют элементы в один список и они (потоки) не синхронизированы с помощью объектов синхронизации). Список не имеет ничего общего с графом. Появление петли означает, что в списке обрывается последовательный перебор его элементов и добраться к последующим элементам невозможно, как и освободить память ими занимаемую. Если не был создан массив адресов элементов списка, то остаётся сливать воду. Петля присутствует, если какой либо элемент списка ссылается на предыдущий элемент в цепи, при условии, что ссылки направлены от начала к концу списка. Работать со списками, которые не помещаются в виртуальное адресное пространство машины нет никаго практического смысла, кроме сугубо академического.

--------------------
Jak se Vám tady líbí?
 

Sinner Sinner в оффлайне

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

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

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

--------------------
Can You Handle Life?
 
Быстрый переход
[]
Вверх
HOSTER.BY: профессиональный хостинг и регистрация доменов .BY
Более 35000 сайтов выбрали нас. Присоединяйтесь!
 
РЕСУРСЫ ПОРТАЛА
   Все ресурсы