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;

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