forum.boolean.name - Списки данных

forum.boolean.name (http://forum.boolean.name/index.php)

- C++ (http://forum.boolean.name/forumdisplay.php?f=22)

- - Списки данных (http://forum.boolean.name/showthread.php?t=3101)

Списки данных

Как организовать списки? стеки/очереди?
гугл ничо вразумительного не говорит.

Re: Списки данных

смотри STL =) std::list, std::vector, std::map, std::hash_map, std::queue, std::stack и еще куча всякого добра =)
или те руками нада? =)

Re: Списки данных

руками надо

Re: Списки данных

А в чем проблема?

Re: Списки данных

ну руками смотри в сторону связанных списков =)
он чо-то типа этого:

Код:

template<typename _Ty>

class LinkedList

{

    public:

        LinkedList * _prev;

        _Ty          _data;

        LinkedList * _next;

};

методы нужные сам напишешь =)
З.Ы. ммм, а зачем вообще те руками писать? =) чем стандартные не устраивают?

Re: Списки данных

http://www.boolean.name/showthread.php?t=1253 ну вот жеш. разве не то? принцип один и тот же

Re: Списки данных

все потихоньку на С++ переходят...

Re: Списки данных

Цитата:

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

все потихоньку на С++ переходят...

Это суровая правда жизни... :)

Re: Списки данных

вот моя реализация однонаправленного списка, стека и очереди на его основе. Может, где-то криво, но работает.

Re: Списки данных

Magus
Неплохо. Осталось написать поиск и обобщить с помощью шаблонов)

Re: Списки данных

еще вопросы:
1 - чем хороши шаблоны?
2 - как с помощью них обобщать?

Re: Списки данных

Используя шаблон, не нужно привязываться к определенному типу.
Если, например, список написать при помощи шаблонов, можно будет создать списки любого типа, включая типы, определенные пользователем.

Так в STL сделано. И это единственно верный вариант.

Re: Списки данных

Вот моя реализация двунаправленных списков (отдельная спасиба Магусу за понятный и красивый код):

Код:

#include "stdafx.h"

#include <iostream.h>





class item

{

public:

        int x;

        item* next;

        item* prev;

};



class list

{

public:

        item* first;

        item* last;

//===================================================

        list(){

                first=NULL;

                last=NULL;

        }

//===================================================

        item* append()

        {

                item* temp;

                temp = new item;

                if(!first){

                        first=temp;

                        first->prev=NULL;

                        first->next=NULL;

                }else{

                        if(!last){

                                last=temp;

                                first->next=last;

                                last->prev=first;

                                last->next=NULL;

                        }else{

                                temp->next=NULL;

                                temp->prev=last;

                                last->next=temp;

                                last=temp;

                        }



                }

                return temp;

        }

//==================================================

        item* crash(item* el)

        {



                if(!(el->next))

                {

                        if(el->prev){

                        el->prev->next=NULL;

                        last=el->prev;}

                }else{

                        if(!(el->prev)){

                                if(el->next){

                                el->next->prev=NULL;

                                first=el->next;}

                        }else{

                                el->next->prev=el->prev;

                                el->prev->next=el->next;                                

                        }

                }

                item* ret;

                if (el->prev){ret=el->prev;}else{ret=NULL;}

                delete el;

                return ret;                

        }

};









int main(int argc, char* argv[])

{



        list l;



l.append()->x=34;

l.append()->x=10;

l.append()->x=18;

l.append()->x=20;

l.append()->x=30;

l.append()->x=34;

l.append()->x=21;



        printf("Hello World!\n");

        for (item* e=l.first;e;e=e->next)

        {

                printf("x=%d\n",e->x);

        }



        for (e=l.first;e;e=e->next)

        {

                if (!(e->x % 10)){e=l.crash(e);}

        }

        printf("===========================================\n");



        for (e=l.first;e;e=e->next)

        {

                printf("x=%d\n",e->x);

        }

        cout<<endl<<"enter char"<<endl;



        char h;

        cin>>h;

        return 1;

}

в коде мне нравиться структура типа

Код:

        for (item* e=l.first;e;e=e->next)

        {

                printf("x=%d\n",e->x);

        }

понятно и просто делаются переборы.

собственно вопрос (с которыми я наверное уже вас всех достал):
есть класс item.
у него поле данных int x;
так вот, если мне необходимо чтоб у него были поля другого типа (да и другое количество) ?
есть идея - создать класс на основе класса item, например:

Код:

class bullet : item

{

public:

        float y,z;

        float spd;

        int l;

};

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

Re: Списки данных

как раз надо использовать шаблоны =)
например:

Код:

template<typename _Ty>

class item

{

public:

    _Ty x;

    item* next;

    item* prev;

};

это раз, потом сам list аналогично:

Код:

template<typename _Ty>

class list

{

public:

    item<_Ty>* first;

    item<_Ty>* last;

}

ну а потом пишешь:

Код:

list<int> list1;

ну и во всех функциях поменять типы возращаемых значений и аргументов по такой же схеме =)

Re: Списки данных

спасибо Knightmare
не, item ненадо шаблонить. это базовый класс от него будем плясать при создании элементов для списков.
а вот list надо зашоблонить чтобы можно было юзать новоиспеченные классы - потомки item'a.

Re: Списки данных

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

Re: Списки данных

Код:

// test2.cpp : Defines the entry point for the console application.

//



#include "stdafx.h"

#include <iostream.h>





class item

{

public:

        int x;

        item* next;

        item* prev;

};



class bullet

{

public:

        float x,y,z;

        float spd;

        int l;

        bullet* next;

        bullet* prev;

};



template<typename item_>

class list

{

public:

        item_* first;

        item_* last;

//===================================================

        list(){

                first=NULL;

                last=NULL;

        }

//===================================================

        item_* append()

        {

                item_* temp;

                temp = new bullet;

                if(!first){

                        first=temp;

                        first->prev=NULL;

                        first->next=NULL;

                }else{

                        if(!last){

                                last=temp;

                                first->next=last;

                                last->prev=first;

                                last->next=NULL;

                        }else{

                                temp->next=NULL;

                                temp->prev=last;

                                last->next=temp;

                                last=temp;

                        }



                }

                return temp;

        }

//==================================================

        item_* crash(item_* el)

        {

                if((!(el->next)) && (!(el->prev)))

                {

                        first=NULL;

                        last=NULL;

                        delete el;

                        return NULL;

                }else

                {

                if(!(el->next))

                {

                        if(el->prev){

                        el->prev->next=NULL;

                        last=el->prev;}

                }else{

                        if(!(el->prev)){

                                if(el->next){

                                el->next->prev=NULL;

                                first=el->next;}

                        }else{

                                el->next->prev=el->prev;

                                el->prev->next=el->next;                                

                        }

                }

                item_* ret;

                if (el->prev){ret=el->prev;}else{ret=NULL;}

                delete el;

                return ret;        

                }

        }

};









int main(int argc, char* argv[])

{



        list<bullet> l;



l.append()->x=34;

l.append()->x=10;

l.append()->x=18;

l.append()->x=20;

l.append()->x=30;

l.append()->x=34;

l.append()->x=21;



        printf("Hello World!\n");

        for (bullet* e=l.first;e;e=e->next)

        {

                cout<<e->x<<endl;

        }





        for (e=l.first;e;e=e->next)

        {

                if((e->x)<25){e=l.crash(e);}

        }



        printf("===========================================\n");



        

        for (e=l.first;e;e=e->next)

        {

                cout<<e->x<<endl;

        }

        cout<<endl<<"enter char"<<endl;



        char h;

        cin>>h;

        return 1;

}

короче появилась идея, нафиг не шаблонить item а создаавать совершенно новый класс, прчием две строчки-
<имя класса*>prev
<имя класса*>next
все же придеться вручную набирать, не могу пока придумать как это автоматизировать.
а List зашаблонить так, чтобы в качестве типа указывать класс, (bullet) например.
пример выше.
ЗЫ. Криво работает удаление (удаление в переборе) :(

Re: Списки данных

как вариант - шаблонить list и передавать туды класс любой но чтобы он имел поля next и prev =) хз бует или нет работать не пробовал такой изврат =) т.е. имеем нечто такое:

Код:

template<typename _Ty>

class List

{

   private:

      _Ty * first;

      _Ty * last;

   public:

      //методы всякие

};

в общем ка то так =) пробуй =)
З.Ы. а нафиг те вообще такой изврат? опиши ситуацию мож чо лучше придумаем =)

Re: Списки данных

ситуация:
я вполне привык к билтцевским типам, ищщу альтернативу. думаю такая фигня не покатит, при инициализации экземпляра класса list будут проблемы (list<item<bla-bla-bla>> gnom). хз конечно, я серьезно c++ не так давно изучаю.

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

Re: Списки данных

HolyDel
брр
делай связаный список с шаблоном и ложи ето отдельно

а потом юзай обычный класс пули
не вижу смысла шаблоны применять в items

Re: Списки данных

я тоже не вижу :)
поэтому и не применяю ;)

Re: Списки данных

гммм... и все проблемы из-за привычки? =) ну в общем то дело твое, но знание STL обычно является обязательным условием при приеме на работу =) хотя если это только типо хобби то не страшно, хотя... вообще вот это:

Код:

list<item<bla-bla-bla>> gnom

работать не станет =) а вот это:

Код:

list<item<bla-bla-bla> > gnom;

станет =) а вообще я ведь предлагал не так малость ну да ладно =)
воообще как вариант есть ведь typedef:

Код:

typedef item<bla-bla-bla> gnomeitem;

list<gmoneitem> gnome;

и вообще посмотри все таки STL'овские вектора, мапы, списки =) думаю они тебе понравится больше чем блитзевские =)
З.Ы. а чо удаление не работает?

Re: Списки данных

Цитата:

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

ситуация:
я вполне привык к билтцевским типам, ищщу альтернативу.

Зачем тогда писать на С++, если сам себе ставить ограничения, которые были в блице? Лучше тогда ориентироваться на БМаксовский структуры, так как там ООП.
Да, в STL перебор, удаление, произвольное удаление, поиск - это все уже реализовано и проверено годами. Ты уверен, что сделаешь лучше?)

Re: Списки данных

Может пригодиться:
http://www.gamedev.ru/articles/?id=70103