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

Очередь на основе массива - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 31, средняя оценка - 4.90
blackbanny
128 / 115 / 2
Регистрация: 14.11.2010
Сообщений: 707
14.01.2011, 14:42     Очередь на основе массива #1
когда создаю пустую очередь размерностью 2 в main() вот так BoundQueue <int> a(2);
выводится ошибка:
C++
1
main.cpp(13) : error C2259: 'BoundQueue<T>' : cannot instantiate abstract class
пишу в Visual Studio 2008

подскажите в чем дело...

вот код классов:
Queue.h
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
#include <iostream>
using namespace std;
#pragma once
template <class T>
class Queue
{
public:
    //Виртуальный деструктор для переопределения в реализациях
    virtual ~Queue() {}
 
    //Операции с абстрактной очередью:
 
    //Добавление элемента в очередь. Может возникнуть ситуация 
    //QueueOverflow, если в очереди нет места для записи нового элемента.
    virtual void enqueue(const T & e) = 0;
 
    //Удаление элемента из головы очереди. Если ни одного элемента
    //в очереди нет, может возникнуть ситуация QueueUnderflow
    virtual void dequeue() = 0;
 
    //Проверка того, что очередь пуста(не имеет ни одного элемента)
    virtual bool empty() const = 0;
 
    //Четыре функции доступа для чтения/записи 
    //элемента в голове и хвосте очереди
    virtual T & head() = 0;
    virtual const T & head() const = 0;
    virtual T & tail() = 0;
    virtual const T & tail() const = 0;
};
BoundQueue.h
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
#include "Queue.h"
#include <iostream>
#pragma once
using namespace std;
template <class T> 
class BoundQueue: public Queue<T> 
{
    T *array; //массив элементов очереди
    int MaxSize; //количество элементов в массиве
    int pHead; //индекс первого элемента
    int pTail; //индекс последнего элемента
    int nCount; //количество элементов очереди
 
public:
 
    //Конструктор ограниченной очереди BoundQueue
    BoundQueue(int size);
 
    //Конструктор копирования BoundQueue
    BoundQueue(const BoundQueue<T> & src);
 
    //Деструктор освобождает память, занятую элементами очереди.
    virtual ~BoundQueue() {count = 0; delete[] array;}
 
    //Реализация абстрактных операций над очередью:
 
    //Включение нового элемента в конец очереди
    void enqueue(const T & item);
    //Удаление элемента из головы очереди
    void dequeue();
    //Проверка очереди на пустоту
    bool empty() {return nCount;}
    //Доступ к головному элементу очереди
    T & head();
    const T & head() const;
    //Доступ к хвостовому элементу очереди
    T & tail();
    const T & tail() const;
};
 
//Конструктор нового пустого стека
template <class T> BoundQueue<T>::BoundQueue(int size)
{
    try
    {
        array = new T[MaxSize = size];
    }
    catch(...)
    {
        throw WrongQueueSize("Incorrect size!");
    }
    count = 0;
}
 
//Конструктор копирования 
template <class T> BoundQueue<T>::BoundQueue(const BoundQueue<T> &src)
{
    //Прежде всего выделяется новая память под элементы нового массива
    try
    {
        array = new T[MaxSize = src.MaxSize];
    }
    catch(...) 
    {
        throw WrongStackSize("Incorrect size!");
    }
    //Теперь производится копирование элементов 
    count = src.count;
    for(int i = 0; i < count; i++) array[i] = src.array[i];
}
 
template <class T> void BoundQueue<T>::enqueue(const T &item)
{
    //Проверка, есть ли в массиве место для нового элемента 
    if(nCount == MaxSize) throw QueueOverflow();
    //Помещение элемента в массив
    if(++pTail == MaxSize) pTail = 0;
    array[pTail] = item;
    nCount++;
}
 
template <class T> void BoundQueue<T>::dequeue()
{
    //Проверка, есть ли в очереди хоть один элемент
    if(nCount == 0) throw QueueUnderflow();
    if(++pHead == MaxSize) pHead = 0;
    //Уменьшение счетчика числа элементов
    nCount--;
}
 
template <class T> T & BoundQueue<T>::head()
{
    //Проверка, есть ли в очереди хоть один элемент
    if(nCount == 0) throw QueueUnderflow();
    //Результат - ссылка на головной элемент
    return array[pHead];
}
 
template <class T> const T & BoundQueue<T>::head() const
{
    //Проверка, есть ли в очереди хоть один элемент
    if(nCount == 0) throw QueueUnderflow();
    //Результат - ссылка на головной элемент
    return array[pHead];
}
 
template <class T> T & BoundQueue<T>::tail()
{
    //Проверка, есть ли в очереди хоть один элемент
    if(nCount == 0) throw QueueUnderflow();
    //Результат - ссылка на хвостовой элемент
    return array[pTail];
}
 
template <class T> const T & BoundQueue<T>::tail() const
{
    //Проверка, есть ли в очереди хоть один элемент
    if(nCount == 0) throw QueueUnderflow();
    //Результат - ссылка на хвостовой элемент
    return array[pTail];
}
Добавлено через 1 час 24 минуты
нашел ошибку надо было не virtual bool empty() const = 0;
а virtual bool empty() = 0;
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nick Alte
Эксперт С++
1590 / 982 / 115
Регистрация: 27.09.2009
Сообщений: 1,897
Завершенные тесты: 1
15.01.2011, 09:33     Очередь на основе массива #2
Надо было писать virtual bool empty() const и в Queue, и в BoundQueue - это однозначно константный метод.
blackbanny
128 / 115 / 2
Регистрация: 14.11.2010
Сообщений: 707
15.01.2011, 10:14  [ТС]     Очередь на основе массива #3
Цитата Сообщение от Nick Alte Посмотреть сообщение
Надо было писать virtual bool empty() const и в Queue, и в BoundQueue - это однозначно константный метод.
т.е. в Queue vitrual bool empty() const =0;
а в BoundQueue bool empty() const;

я брал методы с const из учебника, но там не описано почему именно const нужно...

вот два метода
T & tail();
const T & tail() const;

делают тоже самое...зачем во втором нужен const?
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
15.01.2011, 10:54     Очередь на основе массива #4
const в начале говорит, что будет возвращена константная ссылка на объект типа T (т.е. будет возвращена ссылка на объект (не будет происходить копирования самого объекта), но изменить объект мы не сможем, поскольку ссылка константная). Второй const говорит о том, что в самой функции не будут происходить изменения элементов-данных того объекта, для которого эта функция вызывается.
blackbanny
128 / 115 / 2
Регистрация: 14.11.2010
Сообщений: 707
15.01.2011, 11:46  [ТС]     Очередь на основе массива #5
вот когда я пишу в main():
C++
1
2
3
BoundQueue <int> a(2);
a.push(1);
a.tail(); ---- здесь вызывается метод T & tail();
а как написать, чтобы вызывался метод const T & tail() const;
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
15.01.2011, 11:48     Очередь на основе массива #6
blackbanny, он вызывается по необходимости (например, в функции, которая сама является константной). Сами вы его вызвать не сможете.
blackbanny
128 / 115 / 2
Регистрация: 14.11.2010
Сообщений: 707
15.01.2011, 11:52  [ТС]     Очередь на основе массива #7
Цитата Сообщение от silent_1991 Посмотреть сообщение
blackbanny, он вызывается по необходимости (например, в функции, которая сама является константной). Сами вы его вызвать не сможете.
а можете пример написать, когда бы он вызывался бы...
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
15.01.2011, 11:55     Очередь на основе массива #8
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
#include <iostream>
 
class A
{
public:
    A(int a = 0): _a(a) { }
 
    const int &return_a() const { return _a; } // Константный вариант функции return_a
    int &return_a() { return _a; } // Неконстантный вариант функции return_a
 
    void const_func() const { std::cout << return_a() << std::endl; } // Здесь будет вызван константный вариант
    void non_const_func() { std::cout << ++return_a() << std::endl; } // А здесь - неконстантный (инкремент гарантирует это)
 
private:
    int _a;
};
 
int main()
{
    A a1(2);
    
    a1.const_func();     // Выводим значение
    a1.non_const_func(); // Здесь значение инкрементируется, а затем выводится
    a1.const_func();     // Здесь снова выводится значение (для подтверждения того, что инкремент сработал)
 
    return 0;
}
blackbanny
128 / 115 / 2
Регистрация: 14.11.2010
Сообщений: 707
15.01.2011, 12:45  [ТС]     Очередь на основе массива #9
тут загвоздка произошла, когда делала на основе кольцевого списка очередь...
в main() CircularListQueue <int> b(3);

ошибка:
C++
1
main.cpp(18) : error C2664: 'CircularListQueue<T>::CircularListQueue(const CircularListQueue<T> &)' : cannot convert parameter 1 from 'int' to 'const CircularListQueue<T> &'
CircularListQueue.h
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
#include "Queue.h"
#include "CircularList.h"
#include <iostream>
#pragma once
using namespace std;
//Шаблон, представляющий реализацию абстрактной
//очереди ограниченного размера в кольцевого списка элементов
 
template <class T>
class CircularListQueue: public Queue<T>
{
    CircularList<T> list; //Базовый список
 
public:
    //Конструкторы и деструкторы.
    CircularListQueue(): list() {}
    CircularListQueue(const CircularListQueue & src) {list = src.list;}
    virtual ~CircularListQueue() {}
 
    //Теперь определим и реализуем все абстрактные операции.
    void enqueue(const T & item) {list.insertTail(item);}
    void dequeue();
    bool empty() const {return list.empty();}
    T & head();
    const T & head() const;
    T & tail();
    const T & tail() const;
};
 
//Оперция удаления из очереди
template <class T> void CircularListQueue<T>::dequeue()
{
        return list.removeHead();
}
 
//Функции доступа к головному элементу очереди
template <class T> T & CircularListQueue<T>::head()
{
    return list.head();
}
 
template <class T> const T & CircularListQueue<T>::head() const
{
    return list.head();
}
 
//Функции доступа к хвостовым элементам списка
template <class T> T & CircularListQueue<T>::tail()
{
    return list.tail();
}
 
template <class T> const T & CircularListQueue<T>::tail() const
{
    return list.tail();
}
CircularList.h
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
#pragma once
#include <iostream>
using namespace std;
//Реализация шаблона класса кольцевого списка
template <class T> 
class CircularList
{
    //Элементы списка состоят из собственно хранимого значения 
    //и указателя на следующий элемент списка
 
    struct ListItem{
        T item; //элемент списка
        ListItem *next; //указатель на следующий
 
        ListItem(T i, ListItem *n) {item = i; next = n}
        };
 
    //Список представлен указателем на последний элемент списка,
    //который, в свою очередь, содержит указатель на первый элемент.
    //Этот указатель будет пустым, если список не содержит элементов.
 
public:
 
    //Конструктор по умолчанию создает новый список.
    CircularList() { last = NULL;}
 
    //Конструктор копирования создает
    //копию аргумента с помощью присваивания.
    CircularList(const CircularList<T> & src) {*this = src;}
 
    //Деструктор освобождает память, занятую элементами списка.
    virtual ~CircularList() {destroy();}
 
    //Вставка новых элементов может производиться
    //как в начало, так и в конец.
    void insertHead(const T & item);
    void insertTail(const T & item);
 
    //Удалять можно только первый элемент
    void removeHead();
 
    //Функция 'empty' проверяет, содержит ли список хоть один элемент.
    bool empty() {return last;}
 
    //Функции доступа дают возможность чтения/записи
    //в первый и последний элементы списка
    T & head();
    const T & head() const;
    T & tail();
    const T & tail() const;
 
    //Оператор присваивания 
    CircularList<T> & operator = (const CircularList<T> & src);
 
    //Функция разрушает список, освобождает память, занятую под его элементами.
    void destroy();
};
 
template <class T> void CircularList<T>::insertHead(const T &item)
{
    if(last == NULL) {
        //Новый элемент будет одновременно первым и последним 
        last = new ListItem(item);
        last->next = last;
    }else 
        //Новый элемент вставляется за последним
        last->next = new ListItem(item, last->next);
}
 
template <class T> void CircularList<T>::insertTail(const T &item)
{
    insertHead(item);
    //Чтобы первый элемент стал последним в кольцевом списке,
    //достаточно сдвинуться вперед на один шаг 
    last = last->next;
}
 
template <class T> void CircularList<T>::removeHead()
{
    if(last == NULL) throw QueueUnderflow("QueueUnderflow!");
    if(last->next == last)
    {
        //удаляется единственный элемент
        delete last;
        last = NULL;
    }else
    {
        ListItem *itemToDelete = last->next;
        last->next = last->next->next;
        delete itemToDelete;
    }
}
 
template <class T> T & CircularList<T>::head()
{
    if(last == NULL) throw QueueUnderflow("Queue Underflow!");
    return last->next->item;
}
 
template <class T> const T & CircularList<T>::head() const
{
    if(last == NULL) throw QueueUnderflow("Queue Underflow!");
    return last->next->item;
}
 
template <class T> T & CircularList<T>::tail()
{
    if(last == NULL) throw QueueUnderflow("Queue Underslow!");
    return last->item;
}
 
template <class T> const T & CircularList<T>::tail() const
{
    if(last == NULL) throw QueueUnderflow("Queue Underslow!");
    return last->item;
}
 
//Оператор присваивания 
template <class T> CircularList<T> & CircularList<T>::operator =(const CircularList<T> & src)
{
    destroy();
    if(!src.empty())
    {
        ListItem *current = src.last->item; //указатель на первый элемент
        do{
            insertTail(current->item);
            if(current == src.last) break; //последний элемент добавлен
            current = current->next;
        }while(true);
    }
    return *this;
}
 
template <class T> void CircularList<T>::destroy()
{
    while(last) removeHead();
}
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
15.01.2011, 13:01     Очередь на основе массива #10
main.cpp выложите тоже.
blackbanny
128 / 115 / 2
Регистрация: 14.11.2010
Сообщений: 707
15.01.2011, 13:01  [ТС]     Очередь на основе массива #11
уже исправил...
ступил и написал CircularListQueue <int> b(3), а надо CircularListQueue <int> =)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.10.2011, 18:24     Очередь на основе массива
Еще ссылки по теме:

C++ Очередь на основе массива
Очередь на основе динамического массива. Изучение функций ввода/вывода в программном интерфейсе Win32 C++
C++ "Очередь" на основе динамического массива

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

Или воспользуйтесь поиском по форуму:
валентин777
0 / 0 / 0
Регистрация: 01.06.2011
Сообщений: 45
04.10.2011, 18:24     Очередь на основе массива #12
а на коде С можно ?
Yandex
Объявления
04.10.2011, 18:24     Очередь на основе массива
Ответ Создать тему
Опции темы

Текущее время: 07:25. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru