Форум программистов, компьютерный форум CyberForum.ru

Кольцевой двунаправленный список - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.89
Jaksn
3 / 3 / 0
Регистрация: 26.03.2011
Сообщений: 114
14.05.2011, 17:20     Кольцевой двунаправленный список #1
Дали задачу на практике.
Пусть L обозначает кольцевой двунаправленный список с заглавным звеном.Описать функцию или процедуру, которая в списке L переставляет в обратном порядке все элементы между первым и последним вхождениями элемента Е, если Е входит в L не менее двух раз.
Помогите решить хоть как-нибудь, а то в списках совсем не шарю , а сдавать уже скоро.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.05.2011, 17:20     Кольцевой двунаправленный список
Посмотрите здесь:

кольцевой список C++
C++ Кольцевой список
Кольцевой список C++
кольцевой список C++
C++ Двунаправленный кольцевой список
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Jtalk
93 / 79 / 4
Регистрация: 13.05.2011
Сообщений: 279
14.05.2011, 18:15     Кольцевой двунаправленный список #2
Идите от начального звена вперед и назад, ища E. Когда найдете, сравнивайте, чтобы убедиться, что это не один и тот же элемент. Потом просто идите от них к центру, переставляя по ходу элементы.
Jaksn
3 / 3 / 0
Регистрация: 26.03.2011
Сообщений: 114
14.05.2011, 18:58  [ТС]     Кольцевой двунаправленный список #3
Спасибо, конечно, но я все равно не понимаю. Просто я не знаю как это все с помощью списка организовать.
Jtalk
93 / 79 / 4
Регистрация: 13.05.2011
Сообщений: 279
14.05.2011, 19:09     Кольцевой двунаправленный список #4
Цитата Сообщение от Jaksn Посмотреть сообщение
Спасибо, конечно, но я все равно не понимаю. Просто я не знаю как это все с помощью списка организовать.
Ступайте в интернет и ищите, что такое список и как он организуется. В ячейке двусвязного списка должны быть указатели на предыдущий и следующий элемент (this->next и this->prev, например) - по ним и обходят список. Плюс хранимые в списке значения должны иметь соответствующий оператор сравнения (как минимум "==").

Так как элементы списка обычно не индексируют, то обмен значений можно реализовать банальной заменой значений указателей next и prev.
Jaksn
3 / 3 / 0
Регистрация: 26.03.2011
Сообщений: 114
14.05.2011, 19:28  [ТС]     Кольцевой двунаправленный список #5
Да я искал в интернете, но что-то так и не могу четко понять. Можешь разъяснить подробно как работать со списками, а то вообще засада у меня с ними.
Jtalk
93 / 79 / 4
Регистрация: 13.05.2011
Сообщений: 279
14.05.2011, 19:59     Кольцевой двунаправленный список #6
Цитата Сообщение от Jaksn Посмотреть сообщение
Да я искал в интернете, но что-то так и не могу четко понять. Можешь разъяснить подробно как работать со списками, а то вообще засада у меня с ними.
Что конкретно непонятно? Что такое указатели известно? Список - это набор ячеек, соединенных между собой посредством указателей (каждая ячейка содержит указатель на следующую ячейку - как минимум -, и на предыдущую, если список двусвязный). То, что список кольцевой, означает, что указатель на следующую ячейку последнего элемента указывает на первый элемент списка (а указатель на предыдущий элемент первого элемента списка указывает на последний элемент).

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

Вот описание ячейки списка:

C++
1
2
3
4
5
struct item
{
    item* next,prev; //указатель на следующий и предыдущий элемент
    storage_type* storage; //указатель на данные в ячейке
}
Соответственно, обход списка осуществляется по принципу

C++
1
2
3
4
item* current; //ранее инициализированный текущий элемент списка. Идентификатор типа \
оставлен для понятности
current = current->next; //теперь current указывает на следующую ячейку списка.
current->storage; //а тут извлекаем значение из текущей ячейки
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.05.2011, 22:19     Кольцевой двунаправленный список
Еще ссылки по теме:

Двунаправленный кольцевой список (удаление узлов) C++
C++ Кольцевой, связанный, двунаправленный список

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

Или воспользуйтесь поиском по форуму:
Jaksn
3 / 3 / 0
Регистрация: 26.03.2011
Сообщений: 114
14.05.2011, 22:19  [ТС]     Кольцевой двунаправленный список #7
Спасибо, попробую разобраться
Yandex
Объявления
14.05.2011, 22:19     Кольцевой двунаправленный список
Ответ Создать тему
Опции темы

Текущее время: 01:00. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru