VPF::динамическая структура - Форум программистов

f999t1

Дата 23.4.2006, 12:37 (ссылка)

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

Загрузка ...

Шустрый

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

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

как реализовать динамическую структуру данных в виде очереди smile

CPlusPlusFAN

Дата 24.4.2006, 00:53 (ссылка)

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

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 315
Регистрация: 1.11.2005
Где: Воронеж

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

std::deque

MAKCim

Дата 24.4.2006, 07:27 (ссылка)

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

Загрузка ...

Воін дZэна

Профиль
Группа: Экс. модератор
Сообщений: 5644
Регистрация: 10.12.2005
Где: Менск, РБ

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

Код


struct queue_cell
{
    typedef queue_cell* cell_ptr;
    cell_ptr next, previos;
};

struct queue
{
    queue(): head(0), tail(0) {}
    queue_cell* head, *tail;
};

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

Ах, у елі, ах, у ёлкі, ах, у елі злыя волкі ©

chaos

Дата 24.4.2006, 07:37 (ссылка)

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

Загрузка ...

Серийный программист

Профиль
Группа: Завсегдатай
Сообщений: 2979
Регистрация: 7.7.2004
Где: Екатеринбург

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

Heremum, ручками это ХХ век smile

зачем постоянно изобретать велосипед? STL

Heremum

Дата 24.4.2006, 10:07 (ссылка)

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

Загрузка ...

Шустрый

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

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

chaos
Если человек не знаеткак это сделать, значит он совсем newbie, а раз он таковой, то значит ему надо уметь изобретать велосипед, что знать как он работает, что им пользоваться.
ИМХО.

pablo

Дата 24.4.2006, 11:08 (ссылка)

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

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 320
Регистрация: 12.2.2005
Где: Вильнюс, Литва

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

если я не ошибаюсь, то в стандартной библиотеке есть уже класс queue, а это не что иное, как реализация очереди. Но в принципе можно её сделать и из дека или из связного списка.

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

Первый блин всегда похож на сферу, иногда бывает и куб.

CPlusPlusFAN

Дата 24.4.2006, 13:42 (ссылка)

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

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 315
Регистрация: 1.11.2005
Где: Воронеж

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

Цитата(Heremum @ 24.4.2006, 10:07

)

то значит ему надо уметь изобретать велосипед

Я с тобой согласен, что если ты чайник в вопросах построения динамических структур, то лучше раз 20 написАть очередь руками. А совсем другое дело, когда ты опытный, то лучше использовать, что дают и не создавать очередь в 21-й раз.

threef

Дата 26.4.2006, 20:36 (ссылка)

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

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 375
Регистрация: 27.10.2005
Где: Запорожье

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

Цитата

то лучше использовать, что дают и не создавать очередь в 21-й раз.

Ага, и через двадцать лет ты будешь знать как назывались очереди в STL, SuperSTL, NewMircocosmSTL, NOStandardSTL и т.п. И в очередной раз будешь ждать, когда тебе кто-ньть чо-ньть даст.

CPlusPlusFAN

Дата 26.4.2006, 21:49 (ссылка)

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

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 315
Регистрация: 1.11.2005
Где: Воронеж

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

Цитата(threef @ 26.4.2006, 20:36

)

И в очередной раз будешь ждать, когда тебе кто-ньть чо-ньть даст.

Это, во всяком случае, лучше, чем одно и то же 250 раз руками создавать.

sgrey

Дата 27.4.2006, 06:40 (ссылка)

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

Загрузка ...

Опытный

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

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

Класс:

Код


class Queue
{
public:
    Queue();                    //default constructor
    Queue(const Queue& Q);        //copy constructor
    ~Queue();                        //destructor

    bool isEmpty() const;        //check if the queue is empty
    void insert(int number);    
    //insert an item at the back of the queue
    void remove();
    //remove an item from the front of the queue
    void getFront(int& number);
    //retrieve front item
private:
    struct QNode
    {
        int item;
        QNode *next;
    };
    QNode *backPtr, *frontPtr;
};//end of class
//end of header file

Фуникции:

Код


#include"queueS.h"
#include<cstddef>
#include<cassert>

Queue::Queue()//default constructor
{
    frontPtr = NULL;
    backPtr = NULL;
}//end of default constructor

Queue::Queue(const Queue& Q) //copy constructor
{
    frontPtr = new QNode;
    assert(frontPtr != NULL);
    frontPtr -> item = Q.frontPtr -> item;
     QNode *newPtr = frontPtr;
    
    for (QNode *fPtr = Q.frontPtr -> next; fPtr != NULL; fPtr = fPtr -> next)
    {
        newPtr -> next = new QNode;
        assert(newPtr -> next != NULL);
        newPtr = newPtr -> next;
        newPtr -> item = fPtr -> item;
    }
    newPtr -> next = NULL;
    backPtr = newPtr;

}
Queue::~Queue() //destructor
{
    while(!isEmpty())
    remove();
    assert((backPtr == NULL) && (frontPtr == NULL));
}
bool Queue::isEmpty() const //check if queue is empty
{
    return backPtr == NULL;
}
void Queue::insert(int number) //insert item in the back of the queue
{
    QNode *newPtr = new QNode;

    if (newPtr == 0)
        cout << "Cannot allocete memory\n";
    else
    {
        newPtr -> item = number;
        newPtr -> next = 0;

        if(isEmpty())
            frontPtr = newPtr;
        else
            backPtr -> next = newPtr;
        backPtr = newPtr;
    }
}
void Queue::getFront(int& number)//retrieve first item in the queue
{
    if (isEmpty())
    {
        cout << "Cannot retrieve, queue is empty\n";
    }
    else
    {
        number = frontPtr -> item;
    }
}
void Queue::remove() //remove front item from the queue
{
    if(isEmpty())
        cout << "Empty queue, connot remove\n";
    else
    {

        QNode *tempPtr = frontPtr;
        if (frontPtr == backPtr)
        {
            frontPtr = 0;
            backPtr = 0;
        }
        else
            frontPtr = frontPtr -> next;
        
        tempPtr -> next = 0;
         delete tempPtr;
    }
}
//end of file

Меняй как хочешь сам... тип данных любой можешь поставить

Это сообщение отредактировал(а) sgrey - 27.4.2006, 06:46

threef

Дата 27.4.2006, 10:30 (ссылка)

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

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 375
Регистрация: 27.10.2005
Где: Запорожье

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

Еще одна очередь без реализации основной функции и с добавлением нехарактерной. Вот поэтому и нужно писАть. Хотя бы 1 раз. А так - все чудесно реализовано и в C#, и в Java, и в Object Pascal. ИМХО

Знак

Дата 27.4.2006, 17:27 (ссылка)

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

Загрузка ...

Шустрый

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

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

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

Ведь не даром Москва спаленная пожаром
была французу отданаа.. ...

хехе

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

Ищу 2 файлаowl.tchwindows.tch

threef

Дата 28.4.2006, 20:53 (ссылка)

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

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 375
Регистрация: 27.10.2005
Где: Запорожье

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

Очередь:
обязательные свойства
     голова,
     хвост
обязательные действия
     обработка(просмотр) головы
     удаление головы
     добавление в хвост.

В списке добавляется обработка( просмотр) списка

В очереди с приоритетами и сортированном списке добавляется вставка элемента

Очередь со свтавкой в произвольное место - это не очередь. Это просто другая сущность. Да, можно (и легко) добавить просмотр стека, сортировку списка и очереди, но это уже будут не стек,не очередь и не список. Это будут совершенно другие обьекты, предусматривающие не свойственные для очереди или списка дисциплины обслуживания.
Хотя, кого это сейчас, слегкой руки STL ?

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