VPF::Шаблоны класса - Форум программистов

shinoby

Дата 29.3.2008, 09:53 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 50
Регистрация: 6.3.2008

Репутация: нет
Всего: нет

Как происходит реализация "однонаправленного линейного списка" и "двунаправленного кольцевого списка" (пожалуйста примеры в виде кода и желательно скоментариями для лучшего понимания). Интересны так же все возможные варианты реализации начиная от уровня новичок. Для каких целей применяется первый и второй вариант.

Это сообщение отредактировал(а) shinoby - 29.3.2008, 10:15

comcon1

Дата 29.3.2008, 14:29 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 838
Регистрация: 11.6.2005
Где: Москва ДАС-МГУ

Репутация: нет
Всего: 17

Вот безитераторный шаблон для однонаправленного списка.
Написал вставку и удаление, остальное лень как-то.. сам допишешь?

Код


template<class T>
class LIST {
 private:
 data_type *first;
 data_type *last;
 public:
 struct data_type {
   T data;
   data_type *next;
   data_type(T dat_, data_type_ *nxt_):
     data(dat_), next(nxt_) {;}
 };
 LIST(): first(0), last(0) {;}
 inline data_type *first() const {return first;}
 inline data_type *last() const {return last;}
 void push_back(T dat_) {
    if (last)
       last->next = new data_type(dat_, NULL);
    else {
       first = new data_type(dat_, NULL);
       last = first;
    }
 }
 void insert(data_type *ptr, T _dat) {
   data_type *elem = new data_type(_dat,ptr->next);
   ptr->next = elem;
 }
 void delete(data_type *ptr) {
   data_type *cur;
   for(cur = first; cur != 0; cur = cur->next) {
     if (cur->next == ptr) break;
   }
   cur->next = ptr->next;
   delete ptr;
 }
};

Это сообщение отредактировал(а) comcon1 - 29.3.2008, 14:33

--------------------

comcon1 on twitter

shinoby

Дата 29.3.2008, 21:59 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 50
Регистрация: 6.3.2008

Репутация: нет
Всего: нет

Цитата(comcon1 @ 29.3.2008, 14:29)

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

chipset

Дата 29.3.2008, 23:59 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Экс. модератор
Сообщений: 4071
Регистрация: 11.1.2003
Где: Seattle, US

Репутация: 2
Всего: 164

примерно такая-же реализация как и сomcon1 только есть ещё prev указатель и соответственно функции по перенаправлению prev/next.

--------------------

Цитата(Jimi Hendrix)

Well, I stand up next to a mountain
And I chop it down with the edge of my hand

warmonger_

Дата 31.3.2008, 00:50 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 155
Регистрация: 7.7.2007
Где: г. Киев

Репутация: 1
Всего: 3

Цитата(chipset @ 29.3.2008, 22:59

)

и соответственно функции по перенаправлению prev/next.

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

--------------------

Make everything as simple as possible, but not simpler.Albert Einstein

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »