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

@Jaksn · Регистрация: 26.03.2011

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

@Jtalk · 14.05.2011, 18:15

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

@Jaksn · 14.05.2011, 18:58 **[ТС]**

Спасибо, конечно, но я все равно не понимаю. Просто я не знаю как это все с помощью списка организовать.

@Jtalk · 14.05.2011, 19:09

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

Спасибо, конечно, но я все равно не понимаю. Просто я не знаю как это все с помощью списка организовать.

Ступайте в интернет и ищите, что такое список и как он организуется. В ячейке двусвязного списка должны быть указатели на предыдущий и следующий элемент (this->next и this->prev, например) - по ним и обходят список. Плюс хранимые в списке значения должны иметь соответствующий оператор сравнения (как минимум "==").

Так как элементы списка обычно не индексируют, то обмен значений можно реализовать банальной заменой значений указателей next и prev.

@Jaksn · 14.05.2011, 19:28 **[ТС]**

Да я искал в интернете, но что-то так и не могу четко понять. Можешь разъяснить подробно как работать со списками, а то вообще засада у меня с ними.

@Jtalk · 14.05.2011, 19:59

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

Да я искал в интернете, но что-то так и не могу четко понять. Можешь разъяснить подробно как работать со списками, а то вообще засада у меня с ними.

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

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

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

C++

struct item
{
    item* next,prev; //указатель на следующий и предыдущий элемент
    storage_type* storage; //указатель на данные в ячейке
}

Соответственно, обход списка осуществляется по принципу

C++

item* current; //ранее инициализированный текущий элемент списка. Идентификатор типа \
оставлен для понятности
current = current->next; //теперь current указывает на следующую ячейку списка.
current->storage; //а тут извлекаем значение из текущей ячейки

@Jaksn · 14.05.2011, 22:19 **[ТС]**

Спасибо, попробую разобраться

@Jtalk 95 / 81 / 4 Регистрация: 13.05.2011 Сообщений: 279
	14.05.2011, 18:15	#2
	Идите от начального звена вперед и назад, ища E. Когда найдете, сравнивайте, чтобы убедиться, что это не один и тот же элемент. Потом просто идите от них к центру, переставляя по ходу элементы. 1

@Jaksn 3 / 3 / 0 Регистрация: 26.03.2011 Сообщений: 114
	14.05.2011, 18:58 [ТС]	#3
	Спасибо, конечно, но я все равно не понимаю. Просто я не знаю как это все с помощью списка организовать. 0

@Jtalk 95 / 81 / 4 Регистрация: 13.05.2011 Сообщений: 279
	14.05.2011, 19:09	#4
	Сообщение от Jaksn Спасибо, конечно, но я все равно не понимаю. Просто я не знаю как это все с помощью списка организовать. Ступайте в интернет и ищите, что такое список и как он организуется. В ячейке двусвязного списка должны быть указатели на предыдущий и следующий элемент (this->next и this->prev, например) - по ним и обходят список. Плюс хранимые в списке значения должны иметь соответствующий оператор сравнения (как минимум "=="). Так как элементы списка обычно не индексируют, то обмен значений можно реализовать банальной заменой значений указателей next и prev. 1

@Jaksn 3 / 3 / 0 Регистрация: 26.03.2011 Сообщений: 114
	14.05.2011, 19:28 [ТС]	#5
	Да я искал в интернете, но что-то так и не могу четко понять. Можешь разъяснить подробно как работать со списками, а то вообще засада у меня с ними. 0

@Jaksn 3 / 3 / 0 Регистрация: 26.03.2011 Сообщений: 114
	14.05.2011, 22:19 [ТС]	#7
	Спасибо, попробую разобраться 0

@Jaksn 3 / 3 / 0 Регистрация: 26.03.2011 Сообщений: 114
		#1
	Кольцевой двунаправленный список - C++ 14.05.2011, 17:20. Просмотров 2453. Ответов 6 Метки нет (Все метки) Дали задачу на практике. Пусть L обозначает кольцевой двунаправленный список с заглавным звеном.Описать функцию или процедуру, которая в списке L переставляет в обратном порядке все элементы между первым и последним вхождениями элемента Е, если Е входит в L не менее двух раз. Помогите решить хоть как-нибудь, а то в списках совсем не шарю , а сдавать уже скоро. 0

Опции темы

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

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