Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 24, средняя оценка - 4.79
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
#1

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

03.04.2013, 22:05. Просмотров 3402. Ответов 44
Метки нет (Все метки)

Здорова господа!
Что такое обычный список это понятно есть узел в котором находится указатель на соседний элемент и переменная которая содержит значение узла.
А от интрузивный список хз. Там я от посмотрел в узле содержится токо два указателя на элементы, а где же хранятся данные? От примерчик из википедии:

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;
};
Тада хоть как то можно его построить? хз?
Вообще не пойму как его строить если в узле токо указатели без данных.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.04.2013, 22:05
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Интрузивный и не интрузивный список (C++):

Создать список L3 из элементов, входящих и в список L1 и в список L2 - C++
создать список л3 из элементов входящих и в список л1 и в список л2

Имеется список женихов и список невест. Объединить эти списки в список пар с учетом требований партнерам - Delphi
Имеется список женихов и список невест. Каждая запись списка содержит пол, имя, возраст, рост, вес, а также требования к партнеру:...

программа которая берет список и создает список другой из этого же списка + тот же список без последнего элемента - Prolog
надо написать программу которая берет список и создает список другой из этого же списка + тот же список без последнего элемента к...

Составить программу, которая формирует список L, включив в него по одному разу элементы, которые входят в список L1 но не входят в список L2 - Pascal
Составить программу, которая формирует список L, включив в него по одному разу элементы, которые входят в список L1 но не входят в список...

Создать список L, включив в него по одному разу элементы, которые входят в список L1, но не входят в список L2 - C (СИ)
Описать процедуру, которая формирует список L, включив в него по одному разу элементы, которые входят в список L1, но не входят в...

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

44
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
04.04.2013, 17:15  [ТС] #31
yoghurt92, мой пример кода смотри яж написал для оценки, там как интрузивный так и обычный с аллокацией элемента.

Добавлено через 27 секунд
Слово аллокация новое лучше с созданием элемента так понятнее.

Добавлено через 51 секунду
Я ж написал выше в посте там правдо не красиво и кое как написано, но суть показывает как интрузивного так и не интрузивного списка.

Добавлено через 40 секунд
Там здоровый код два списка можеш даже скомпилировать.

Добавлено через 35 секунд
Ну там конечно не достойная демонстрация. Но хоть какаето.
0
yoghurt92
374 / 345 / 22
Регистрация: 17.05.2012
Сообщений: 1,049
04.04.2013, 17:19 #32
ninja2, это конечно все хорошо, но я бы хотел посмотреть BOOST-ую реализацию... а так, если сходу, то быстро не разберешься...

Добавлено через 2 минуты
ninja2, я сегодня вечером попробую написать свою реализацию, потом покажу что получиться
0
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
04.04.2013, 17:20  [ТС] #33
yoghurt92, ок
0
kamre
126 / 130 / 4
Регистрация: 25.12.2011
Сообщений: 443
04.04.2013, 17:53 #34
Цитата Сообщение от lemegeton Посмотреть сообщение
На таких маленьких типах данных разницы не прочувствовать. Создайте хранимый объект, который будет содержать динамически выделяемую память в большом количестве -- несколько мегабайт. И поворочайте с сотню таких объектов в интрузивном и неинтрузивном контейнере.
Такие толстые объекты обычно заворачиваются в std::shared_ptr и уже именно эти указатели хранятся в контейнере. Также можно через эти указатели и в других контейнерах одновременно хранить. Зачем нужны интрузивные контейнеры, в чем их преимущества?
0
gray_fox
What a waste!
1522 / 1227 / 70
Регистрация: 21.04.2012
Сообщений: 2,565
Завершенные тесты: 3
04.04.2013, 18:38 #35
Цитата Сообщение от kamre Посмотреть сообщение
Зачем нужны интрузивные контейнеры, в чем их преимущества?
Они не управляют памятью, в частности за счёт этого у некоторых операций более строгие гарантии относительно исключений.
0
yoghurt92
374 / 345 / 22
Регистрация: 17.05.2012
Сообщений: 1,049
04.04.2013, 21:08 #36
ninja2, еще не совсем понял полностью что тут прям такого хорошего, но я понял что ваша реализация не верна, так как в процедуре добавления элемента в список вы реализуете процедуру как для двусвязного списка, у вас элемент указывает на следующий а следующий на предыдущий, но это не правильно, это типичный двусвязный список, внимательнее посмотрите вариант предложенный lemegeton.

Добавлено через 4 минуты
lemegeton, мне вот что не понятно, исходя из вашего варианта (спасибо конечно за демонстрацию), каким образом я смогу вывести содержимое на консоль, где признак конца списка? в обычных списках NULL служит признаком конца, а тут я не понял...
0
lemegeton
2925 / 1354 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
04.04.2013, 22:18 #37
Цитата Сообщение от yoghurt92 Посмотреть сообщение
lemegeton, мне вот что не понятно, исходя из вашего варианта (спасибо конечно за демонстрацию), каким образом я смогу вывести содержимое на консоль, где признак конца списка? в обычных списках NULL служит признаком конца, а тут я не понял...
В примере я привел недоработанный кольцевой связный список.
0
yoghurt92
374 / 345 / 22
Регистрация: 17.05.2012
Сообщений: 1,049
04.04.2013, 23:04 #38
lemegeton, можете хотя бы показать как будет функция добавления элемента в список, мне чтобы разобраться больше не надо

Добавлено через 33 минуты
lemegeton, не знаю все ли я правильно понял, но не могли бы вы посмотреть мой код, там все 2 метода, думаю это не займет много времени, заранее спасибо!

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
using namespace std;
 
struct List_Int
{
    int data;
    List_Int *next, *prev;
};
 
template <typename T>
class List_IntNode
{
    private:
        T *link;
 
    public:
        List_IntNode():link(NULL) {}
 
        void pushBack(T &data)
        {
            if (link == NULL)
            {
                link = &data;
                link -> next = NULL;
                link -> prev = NULL;
            }
            else
            {
                data.next = NULL;
                data.prev = link;
                link = &data; 
            }
        }
 
        void showList_Int()
        {
            T *tmp = link;
            while(tmp != NULL)
            {
                cout << tmp -> data << endl;
                tmp = tmp -> prev;
            }
        }
};
 
int _tmain(int argc, _TCHAR* argv[])
{
    List_IntNode<List_Int> List;
 
    List_Int first, second, third;
    first.data = 1;
    second.data = 2;
    third.data = 3;
 
    List.pushBack(first);
    List.pushBack(second);
    List.pushBack(third);
 
    List.showList_Int();
 
    cout << "\n\n";
    return 0;
}
правильно ли я понял?
0
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
04.04.2013, 23:33  [ТС] #39
yoghurt92, на мой посмотри я его доработал, признак конца списка. Ты сразу находишся в конце либо next=0

Добавлено через 1 минуту
Там же два один интрузивный один не интрузивный, а отличие в том что просто уже готовый объект данных передаешь. Там может быть и три указателя это неважно.

Добавлено через 1 минуту
У тебя если prev=0 указывать должно что это первый элемент, а если next=0 , то это как бы последний.

Добавлено через 3 минуты
yoghurt92, я посмотрел правильно ты все сделал не парься.
0
yoghurt92
374 / 345 / 22
Регистрация: 17.05.2012
Сообщений: 1,049
04.04.2013, 23:52 #40
ninja2,

Цитата Сообщение от ninja2 Посмотреть сообщение
else
* * * * {
* * * * * * cout <<"ect6 elementu"<<endl;
* * * * * * data->next=a;
* * * * * * a->prev=data;
* * * * * * data=a;
* * * * }
я вот о чем имел ввиду, а чему равно тогда у тебя a -> next - ? нужно же указывать и на предшествующий и на следующий... а у тебя получилось только на предшествующий...
0
lemegeton
2925 / 1354 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
05.04.2013, 09:25 #41
Я показал пример с кольцевым двусвязным списком, где признаком конца является первый элемент (у меня он назван origin). Т.е. в моем коде последний элемент будет такой, у которого next == origin. Если элемент только один, его next и prev указывают на сам элемент.
Смысл кольцевого списка в том, что указатели next и prev всегда валидны и не могут быть null, если вообще определен origin.

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

Посмотрите лучше код, составленный ninja2. У него концепт по-проще.
0
yoghurt92
374 / 345 / 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, при добавлении последующих он говорит текущему что есть следующий, а следующему что есть предыдущий, для текущего нужно указать еще и про будущий, я не прав? И спасибо, я разобрался, не привычно так сразу понять концепцию интрузивных списков
0
ninja2
231 / 187 / 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; и так сам по себе :)
* * * * }
0
yoghurt92
374 / 345 / 22
Регистрация: 17.05.2012
Сообщений: 1,049
05.04.2013, 15:36 #44
ninja2, не обратил внимания на конструктор тогда все, ок)
0
lemegeton
2925 / 1354 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
05.04.2013, 15:41 #45
Цитата Сообщение от yoghurt92 Посмотреть сообщение
для текущего нужно указать еще и про будущий, я не прав?
Прав. Возможно, стоит гарантировать null в указателе на следующий элемент, если не можете положиться на состояние хранимого класса.

Например, если элемент уже изымался из списка и добавляется в конец, содержимое его поля next не определено и может отличаться от null.
0
05.04.2013, 15:41
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.04.2013, 15:41
Привет! Вот еще темы с ответами:

3 класса: список, стек(как список), очередь(как список) - C++
препод дал задание: написать 3 класса (список, стек, очередь), методы: вывод, добавление, удаление. Использовать при обращении указатель...

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

Список: Сформировать третий список, содержащий числа Фибоначи исходных списков - Turbo Pascal
Дано два однонаправленных списка целых чисел.Сформировать третий список, содержащий числа Фибоначи исходных списков. Как это записывается?

Вывести список ровесников и список сотрудников со стажем, большим заданного числа - C (СИ)
Дан список N сотрудников с указанием фамилии, даты рождения,стажа работы и зарплаты.Вывести: список ровесников и список сотрудников со...


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

Или воспользуйтесь поиском по форуму:
45
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.