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

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

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

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

03.04.2013, 22:05. Просмотров 3216. Ответов 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
Составить базу данных об учащихся, предусмотрев поля: Ф.И.О., предметы по выбору, экзаменационные оценки по каждому из них. Составить...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Venzo
125 / 123 / 4
Регистрация: 03.07.2011
Сообщений: 354
03.04.2013, 22:10 #2
C++
1
2
3
4
5
6
7
8
9
10
struct List
{
    Elem *elem;
};
 
struct Elem
{
    Data *next, *prev;
    int x, y;
};
как-то так должно быть.
Т.е. каждый элемент содержит указатели на следующий и предыдущий элементы + какие-то свои данные
1
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
03.04.2013, 22:25  [ТС] #3
Цитата Сообщение от Venzo Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
struct List
{
    list *prev, *next;
    Data *data;
};
 
struct Data
{
    int x, y;
};
как-то так должно быть.
Т.е. каждый элемент содержит указатели на следующий и предыдущий элементы + какие-то свои данные
Это обычный не интрузивный список, а мне нужен интрузивный.

Добавлено через 1 минуту
Выше смотри я из википедии http://ru.wikipedia.org/wiki/%D0%98%...81%D0%BE%D0%BA
взял пример, токо как он работает не понятно.

Добавлено через 11 минут
Видимо здесь ошибка:
C++
1
2
3
4
5
struct list_link 
{
    list_link *prev, *next;
   //добавить наверно сюда нужно element* data;
};
0
Venzo
125 / 123 / 4
Регистрация: 03.07.2011
Сообщений: 354
03.04.2013, 22:29 #4
странная какая-то вещь, можно голову сломать...
1
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
03.04.2013, 22:38  [ТС] #5
Да и правильно записано. Токо как его строить в таком виде хз. Там все таки без ошибок так и есть в узле токо ссылки на соседние элементы и все.

Добавлено через 39 секунд
Ну чо тут гуру нету чтоле? Хелп новичкам!

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

Добавлено через 5 минут
Как работает данный список:
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;
};
?????
Или как хотябы строится?
0
Venzo
125 / 123 / 4
Регистрация: 03.07.2011
Сообщений: 354
03.04.2013, 22:38 #6
http://stackoverflow.com/questions/3...ation-for-java
как я понял, то список "встраивается" в сам класс, данные которого вы хотите хранить в списке. В этом классе вы реализовываете операции для получения следующего и предыдущего элемента.
т.е вы хотите хранить в списке объекты Foo
C++
1
2
3
class Foo {
    int bar;
}
нужно в этот класс добавить указатели на предыдущий и следующий элементы и реализовать операции
C++
1
2
3
4
5
class Foo {
    int bar;
    Foo *prev;
    Foo *next;
}
или отнаследоваться от Foo и добавить указатели на предыдущий и следующий и реализовать операции
1
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
03.04.2013, 22:54  [ТС] #7
Ничо не понял хз.
Но вроде не подходит под описание. http://ru.wikipedia.org/wiki/%D0%98%...81%D0%BE%D0%BA

Добавлено через 2 минуты
Если так посмотреть на класс:
C++
1
2
3
4
5
struct element
{
    int x, y;
    list_link link;
};
то они добавлены. list_link это как бы указатель на предыдущий и следующий элемент, токо при переходе к следующему элементу как мы данные извлечем?

Добавлено через 2 минуты
Давай этот пример рассмотрим из википедии:
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;
};
Ну я перехожу на следующий элемент link.next. Ну есть адрес следующего элемента и что дальше? Где мне даные элемента брать?

Добавлено через 4 минуты
А все понял list_link это базовый класс, делать нужно от него производный класс какой нить элемент и уже он как бы будет содержать данные.
C++
1
2
3
4
struct data : public list_link 
{
    int data;
};
Добавлено через 56 секунд
Отак короче без добавления указателей Просто элемент наследником сделать.

Добавлено через 36 секунд
ну это считай обычный список получается.
0
Venzo
125 / 123 / 4
Регистрация: 03.07.2011
Сообщений: 354
03.04.2013, 23:01 #8
вы наверно правы были в первом посте,
тут
Цитата Сообщение от ninja2 Посмотреть сообщение
list_link *
тогда должен быть указатель на element
иначе вообще не понятно

Добавлено через 1 минуту
Цитата Сообщение от ninja2 Посмотреть сообщение
ну это считай обычный список получается.
в обычном списке надо разыменовать данные, затем указатель на следующий/предыдущий элемент, а здесь сразу указатель на след/предыдущий
0
lemegeton
2924 / 1353 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
03.04.2013, 23:15 #9
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Интрузивные контейнеры это такая хитрая концепция, позволяющая хранить только данные. При этом сами данные должны заботиться о том, чтобы их можно было хранить. В случае хранения в виде двусвязного списка, сама хранимая структура должна иметь некие указатели на следующий и предыдущий элементы. При этом интрузивный контейнер не создает дополнительных объектов типа "нод" для хранения каждой единицы данных.

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


Обратите внимание, в классе-контейнере ничего не аллоцируется, не удаляется, не создается копий...
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
#include <ctime>
#include <cstdlib>
#include <iostream>
 
struct Storable {
  int number;
  Storable *prev, *next;
};
 
template <class T>
class IntrusiveStorage {
 public:
  IntrusiveStorage() : origin(0) {}
  void pushBack(T &data) {
    if (origin == 0) {
      origin = &data;
      origin->next = origin;
      origin->prev = origin;
    } else {
      data.next = origin;
      data.prev = origin->prev;
      data.next->prev = data.prev->next = &data;
    }
  }
  T &getLast() {
    if (origin == 0) {
      // Г*ГҐГІ Г¤Г*Г*Г*ûõ, èñêëþ÷åГ*ГЁГҐ?
    }
    return *(origin->prev);
  }
  void popBack(T &data) {
    if (origin == 0) {
      // Г*ГҐГІ Г¤Г*Г*Г*ûõ, èñêëþ÷åГ*ГЁГҐ?
    }
    if (origin->next = origin) {
      origin = 0;
    } else {
      T *data = origin->prev;
      data->prev->next = data->next;
      data->next->prev = data->prev;
    }
  }
 private:
  T *origin;
};
 
int main(int argc, char **argv) {
  srand(time(0));
  IntrusiveStorage<Storable> storage;
  
  Storable s;
  s.number = 5;
  storage.pushBack(s);
  std::cout << storage.getLast().number << std::endl;
  
  std::cin.get();
  return 0;
}
Мое мнение -- с этим довольно трудно работать, легче хранить стандартный контейнер указателей. Смысл тот же, оверхеад не чудовищный.
7
yoghurt92
374 / 345 / 22
Регистрация: 17.05.2012
Сообщений: 1,049
03.04.2013, 23:23 #10
lemegeton, а где можно поподробней почитать?
0
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
03.04.2013, 23:51  [ТС] #11
Venzo, Фиг его знает. Новое определение я его не сильно понимаю.
0
Jupiter
Каратель
Эксперт С++
6554 / 3975 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
04.04.2013, 01:44 #12
Цитата Сообщение от yoghurt92 Посмотреть сообщение
а где можно поподробней почитать?
"вступление" в boost.intrusive
0
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
04.04.2013, 16:35  [ТС] #13
Здорова!
Я тут всетаки домучил как бы эти списки и от свои построил два с примерами интрузивный и не интрузивный.
Как думаете правильно я построил? Интересно мнение гуру.
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
//intryzivnui cpicok
#include <iostream>
using std::cout;
using std::endl;
#include <cstdlib>
using std::exit;
 
//#include "intryctiv.h"
 
//eto intryzivnui cpicok tak ckazat6 vctraivaemui
struct List
{
    List *next, *prev;
    int val;
    List(int a):val(a),next(0),prev(0){}
};
 
struct intr
{
    List* data;
public:
    //konctryktor po ymolchaniyu
    intr():data(0){}
    void add(List* a)
    {
        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;
        }
    }
    
    //vuvod c konca;
    void print()
    {
        if(data==0)
        {
            cout <<"cpicok pyct"<<endl;
        }
        else
        {
            cout <<"ne pyct req vuzov"<<endl;
            printHelper(data);
        }
    }
    void printHelper(List* ptr)
    {
        if(ptr!=0)
        {
            cout <<ptr->val<<' ';
        }
        if(ptr->prev!=0)
        {
            printHelper(ptr->prev);
        }
    }
};
 
//ne intryzivnui cpicok
struct Listn
{
    Listn *next, *prev;
    int val;
    Listn(int a):val(a),next(0),prev(0){}
};
 
class listn
{
    Listn * data;
public:
    listn():data(0){}
    
    void add(int a)
    {
        if(data==0)
        {
            cout <<"cpicok pyck"<<endl;
            data=new Listn(a);
        }
        else
        {
            cout <<"cpicok ne pyck"<<endl;
            addHelper(data,a);
        }
    }
    void addHelper(Listn* ptr,int& a)
    {
        if(ptr->next==0)
        {
            ptr->next=new Listn(a);
        }
        else
        {
            addHelper(ptr->next,a);
        }
    }
    
    void print()
    {
        if(data==0)
        {
            cout <<"cpicok pyct"<<endl;
        }
        else
        {
            printHelper(data);
        }
    }
    void printHelper(Listn* ptr)
    {
        if(ptr!=0)
        {
            cout <<ptr->val<<' ';
            if(ptr->next!=0);
            {
                printHelper(ptr->next);
            }
        }
    }
};
 
 
 
int main()
{
//не интрузивный тест.
    listn l;
    l.add(5);
    l.add(6);
    l.add(7);
    l.print();
    cout <<endl;
    
    
    //интрузивный тест.
    intr ne;
    
    List a(3);
    ne.add(&a);
    
    List b(4);
    ne.add(&b);
    ne.print();
    
    cout <<endl;    
    
    return 0;
}
Добавлено через 3 минуты
Я так понимаю интрузивный это встроеный список, а не интрузивный это кода просто передается елемент, а затем место выделяется под список. Если это так, то разница какая в них? Это ж одно и тоже. В любом случае место выделяется, просто записи разные. Там в самом классе выделяется, а в интрузивном нужно в программе выделить. хз.? Никак не допру.
0
ForEveR
В астрале
Эксперт С++
7972 / 4734 / 321
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
04.04.2013, 16:36 #14
ninja2, Настоятельно рекомендую все же почитать http://www.boost.org/doc/libs/1_52_0..._vs_nontrusive
0
taras atavin
Ушёл с форума.
3569 / 1753 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
04.04.2013, 16:39 #15
Цитата Сообщение от ninja2 Посмотреть сообщение
struct list_link
{
* * list_link *prev, *next;
};
struct element
{
* * int x, y;
* * list_link link;
};
Что не понятного? Данные в иксе и игреке, а указатели на соседей вынесены в специальную подструктуру.

Добавлено через 2 минуты
Цитата Сообщение от ninja2 Посмотреть сообщение
Чото мне кажется они наверно ошиблись нужно list_link* наверно заменить на element*
Отак:
И как ты получишь список? Это только два элемента и указывающая на них структура, для списка соседи сами должны уметь кудато указывать.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.04.2013, 16:39
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
04.04.2013, 16:39
Ответ Создать тему
Опции темы

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