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

Интрузивный и не интрузивный список - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 24, средняя оценка - 4.79
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
03.04.2013, 22:05     Интрузивный и не интрузивный список #1
Здорова господа!
Что такое обычный список это понятно есть узел в котором находится указатель на соседний элемент и переменная которая содержит значение узла.
А от интрузивный список хз. Там я от посмотрел в узле содержится токо два указателя на элементы, а где же хранятся данные? От примерчик из википедии:

C++
1
2
3
4
5
6
7
8
9
10
struct list_link 
{
    list_link *prev, *next;
};
 
struct element
{
    int x, y;
    list_link link;
};
Чото мне кажется они наверно ошиблись нужно list_link* наверно заменить на element*
Отак:
C++
1
2
3
{
    element *prev, *next;
};
Тада хоть как то можно его построить? хз?
Вообще не пойму как его строить если в узле токо указатели без данных.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.04.2013, 22:05     Интрузивный и не интрузивный список
Посмотрите здесь:

Список: связный список, в котором информация о книгах сортируется по убыванию стоимости. C++
C++ 3 класса: список, стек(как список), очередь(как список)
list. Cоздать список из результатов(с массивами), а потом просмотреть весь список C++
C++ создать список л3 из элементов входящих и в список л1 и в список л2
C++ Необходимо создать список, элемент которого может быть список
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
lemegeton
 Аватар для lemegeton
2908 / 1337 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
05.04.2013, 09:25     Интрузивный и не интрузивный список #41
Я показал пример с кольцевым двусвязным списком, где признаком конца является первый элемент (у меня он назван origin). Т.е. в моем коде последний элемент будет такой, у которого next == origin. Если элемент только один, его next и prev указывают на сам элемент.
Смысл кольцевого списка в том, что указатели next и prev всегда валидны и не могут быть null, если вообще определен origin.

В моем примере приведено добавление элемента в конец, удаление элемента из конца и показ последнего элемента.

Посмотрите лучше код, составленный ninja2. У него концепт по-проще.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
yoghurt92
373 / 344 / 22
Регистрация: 17.05.2012
Сообщений: 1,049
05.04.2013, 14:26     Интрузивный и не интрузивный список #42
lemegeton, спасибо за пояснение, но как я понял, в интрузивном списке каждый элемент знает кто спереди а кто сзади, тогда мне кажется код ninja2 ошибочен.

Цитата Сообщение от ninja2 Посмотреть сообщение
if(data==0)
* * * * {
* * * * * * cout <<"nety elementov"<<endl;
* * * * * * data=a;
* * * * * * data->next=0;
* * * * * * data->prev=0;
* * * * }
* * * * else
* * * * {
* * * * * * cout <<"ect6 elementu"<<endl;
* * * * * * data->next=a;
* * * * * * a->prev=data;
* * * * * * data=a;
* * * * }
смотрите, если список пуст, мы добавляем первый элемент, и следующий и предшествующий NULL, при добавлении последующих он говорит текущему что есть следующий, а следующему что есть предыдущий, для текущего нужно указать еще и про будущий, я не прав? И спасибо, я разобрался, не привычно так сразу понять концепцию интрузивных списков
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
05.04.2013, 15:14  [ТС]     Интрузивный и не интрузивный список #43
смотрите, если список пуст, мы добавляем первый элемент, и следующий и предшествующий NULL, при добавлении последующих он говорит текущему что есть следующий, а следующему что есть предыдущий, для текущего нужно указать еще и про будущий, я не прав? И спасибо, я разобрался, не привычно так сразу понять концепцию интрузивных списков
У тебя код точь вточ такой же как у меня. Ничем не отличается.

Добавлено через 4 минуты
А next =0 там же конструктор есть. Я мог бы просто записать
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
if(data==0)
* * * * {
* * * * * * cout <<"nety elementov"<<endl;
* * * * * * data=a;
* * * * * * //data->next=0;они и так равны ноль
* * * * * * //data->prev=0;//и так ноль
* * * * }
* * * * else
* * * * {
* * * * * * cout <<"ect6 elementu"<<endl;
* * * * * * data->next=a;
* * * * * * a->prev=data;
* * * * * * data=a;
//а->next=0; и так сам по себе :)
* * * * }
yoghurt92
373 / 344 / 22
Регистрация: 17.05.2012
Сообщений: 1,049
05.04.2013, 15:36     Интрузивный и не интрузивный список #44
ninja2, не обратил внимания на конструктор тогда все, ок)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.04.2013, 15:41     Интрузивный и не интрузивный список
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
lemegeton
 Аватар для lemegeton
2908 / 1337 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
05.04.2013, 15:41     Интрузивный и не интрузивный список #45
Цитата Сообщение от yoghurt92 Посмотреть сообщение
для текущего нужно указать еще и про будущий, я не прав?
Прав. Возможно, стоит гарантировать null в указателе на следующий элемент, если не можете положиться на состояние хранимого класса.

Например, если элемент уже изымался из списка и добавляется в конец, содержимое его поля next не определено и может отличаться от null.
Yandex
Объявления
05.04.2013, 15:41     Интрузивный и не интрузивный список
Ответ Создать тему
Опции темы

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