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

Реализация стека - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 66, средняя оценка - 4.88
blackbanny
128 / 115 / 2
Регистрация: 14.11.2010
Сообщений: 707
13.01.2011, 20:00     Реализация стека #1
вот такие ошибки при реализации:
C++
1
2
3
stack.h(26) : error C2953: 'Stack' : class template has already been defined
liststack.h(10) : error C2955: 'Stack' : use of class template requires template argument list
boundstack.h(6) : error C2955: 'Stack' : use of class template requires template argument list
вот сами классы:
BoundStack.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
#include "Stack.h"
#include <iostream>
using namespace std;
template <class T>
class BoundStack: public Stack<T>
{
    T *array; //Указатель на массив элементов
    int count, MaxSize; //Счетчик числа элементов стека и длина массива
 
public:
    
    //В конструкторе стека задается его размер.
    BoundStack(int size);
 
    //Стандартный копирования создает новый 
    //стек и копирует в него элементы исходного стека.
    BoundStack(const BoundStack<T> &src);
 
    //Деструктор стека освобождает память, занятую под его элементы.
    ~BoundStack();
 
    //Класс будет содержать реализации абстрактных операций со стеком.
    void push(const T & e);
    void pop();
    bool empty() {return count == 0;}
    T & top();
    const T & top() const;
};
 
//Описание функций, реализающих абстрактные 
//операции над ограниченным стеком.
 
//Конструктор нового пустого стека
template <class T> BoundStack<T>::BoundStack(int size)
{
    try
    {
        array = new T[MaxSize = size];
    }
    catch(...)
    {
        throw WrongStackSize("Incorrect size!");
    }
    count = 0;
}
 
//Конструктор копирования 
template <class T> BoundStack<T>::BoundStack(const BoundStack<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> BoundStack<T>::~BoundStack()
{
    count = 0;
    delete[] array;
}
 
//Операция занесения элемента в стек
template <class T> void BoundStack<T>::push(const T &e)
{
    //проверка на переполнение 
    if(count == MaxSize) throw StackOverflow("Stack Overflow!");
    //новый элемент записывается в стек
    array[count++] = e;
}
 
//Операция выталкивания элемента из стека
template <class T> void BoundStack<T>::pop()
{
    //проверка на пустоту
    if(count == 0) throw StackUnderflow("Stack Underflow!");
    //физически верхний элемент отстается в массиве,
    //но количество элементов уменьшается 
    count--;
}
 
//Операция доступа к верхнему элементу стека 
template <class T> T & BoundStack<T>::top()
{
    //проверка на пустоту
    if(count == 0) throw StackUnderflow("Stack Underflow!");
    //верхний элемент возвращается в качестве результата
    return array[count-1];
}
 
template <class T> const T & BoundStack<T>::top() const 
{
    //проверка на пустоту стека 
    if(count == 0) throw StackUnderflow("Stack Underflow!");
    //верхний элемент возвращается в качестве результата
    return array[count-1];
}
Stack.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
#include <iostream>
using namespace std;
template <class T>
class Stack
{
public:
    //Виртуальный деструктор
    virtual ~Stack(){}
 
    //добавление нового элемента в стек; в случае ограниченного стека
    //может возникнуть ситуация переполнения стека - StackOverflow
    virtual void push(const T & e) = 0;
 
    //удаление верхнего элемента из стека;если стек пуст, то 
    //возбуждается ситуация исчерпания стека - StackUnderflow
    virtual void pop() = 0;
 
    //функция проверки пустоты 
    virtual bool empty() = 0;
 
    //Две функции доступа, позволяющие взять или изменить значение 
    //верхнего элемента из стека без его удаления с вершины стека;
    //если стек пуст, то возбуждается ситуация StackUnderflow
    virtual T &  top() = 0;
    virtual const T & top() const = 0;
};
ListStack.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
#include "Stack.h"
#include "List.h"
using namespace std;
//Шаблон, представляющий реализацию абстрактного
//в виде линейного списка элементов
 
template <class T>
 
class ListStack: public Stack<T>
{
    List<T> stack; //реализация представлена списком элементов
 
public:
    //Конструкторы стека просто создают список
    ListStack(): stack(){}
    ListStack(const ListStack & stk): stack(stk.stack) {}
 
    //ListStack(void);
    
    //Далее объявляются и частично реализуются абстрактные операции
    void push(const T & e) {stack.addFirst(e);}
    void pop();
    bool empty() {return stack.getCount() == 0;}
    T & top();
    const T & top() const;
}; //Конец объявления класса ListStack
 
 
//Операция pop удаляет первый элемент списка
template <class T> void ListStack<T>::pop()
{
    
    try{
        stack.remove();
    }
    catch(...){
        //Если удалить элемент не удается, возбуждается
        //исключительная ситуация StackUnderflow
        throw StackUnderflow("Stack Underflow!");
    }
}
 
//Операция доступа к вершине стека реализована 
//через доступ к первому элементу списка
template <class T> T & ListStack<T>::top()
{
    try{
        return stack.head();
    }
    catch(...){
        //Если доступ к первому элементу невозможен,
        //возбуждается исключительная ситуация StackUnderflow
        throw StackUnderflow("Stack Underflow!");
    }
}
 
template <class T> const T & ListStack<T>::top() const
{
    try{
        return stack.head();
    }
    catch(...){
        //Если доступ к первому элементу невозможен,
        //возбуждается исключительная ситуация StackUnderflow
        throw StackUnderflow("Stack Underflow!");
    }
}
List.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
#include <iostream>
using namespace std;
template <class T>
class List
{
    //Класс List представляет элемент списка, связанный со 
    //следующим с помощью указателя, содержащегося в поле next
 
    struct ListItem
    {
        T item; //значение элемента списка
        ListItem *next; //указатель на следующий элемент списка
 
        //Конструктор для создания нового элемента
        ListItem(int i, ListItem *n ) { item = i; next = n;}
    };
    int count; //счетчик числа элементов
    ListItem *first; //указатель на первый элемент списка
    ListItem *last; //указатель на последжний элемент списка
 
public:
 
    //Конструктор по умолчанию - создание пустого списка
    List() {count = 0; first = last = NULL;}
 
    //Конструктор копирования - создание копии имеющегося списка
    List(const List & src);
 
    //Деструктор списка
    ~List();
    
    //Доступ к первому элементу списка
    T head() const {return first->item;}
    T & head() {return first->item;}
 
    //Доступ к последнему элементу списка
    T tail() const {return last->item;}
    T & tail() {return last->item;}
 
    //Добавить один элемент в начало списка
    void addFirst(T item);
 
    //Добавить один элемент в конец списка
    void addLast(T item);
 
    //Добавить элементы другого списка в конец этого
    void addLast(const List & src);
 
    //Удалить первый элемент
    T removeFirst();
 
    //количество элементов списка
    int getCount() {return count;}
};
 
//Реализация конструктора копирования
template <class T> List<T>::List(const List<T> &src)
{
    count = 0;
    first = last = NULL;
    addLast(src); //добавление списка src в конец списка this
}
 
//Реализация деструктора 
template <class T> List<T>::~List()
{
    ListItem *current = NULL; //указатель на элемент, подлежащий удалению
    ListItem *next = first; //указатель на следующий
    while(next) //пока есть еще элементы в списке
    {
        current = next;
        next = next->next; //переход к следующему
        delete current;
    }
}
 
//Добавление одного элемента в начало списка
template <class T> void List<T>::addFirst(T item)
{
    //создаем новый элемент и присоединяем его к началу списка
    ListItem *newItem = new ListItem(item, first);
    if(first == NULL)
    {
        //список был пуст - новый элемент будет первым и последним
        last = newItem;
    }
    first = newItem;
    count++; //число элементов списка увеличилось
}
 
//Добавление одного элемента в конец списка
template <class T> void List<T>::addLast(T item)
{
    //создаем новый элемент списка
    ListItem *newItem = new ListItem(item, NULL);
    if(last == NULL)
    {
        //список был пуст - новый элемент будет и первым и последним
        first = newItem;
    } else {
        //новый элемент присоединился к последнему элементу списка
        last->next = newItem;
    }
    last = newItem;
    count++; //число элементов списка увеличилось
}
 
//Добавление элементов заданного списка в конец определяемого
template <class T> void List<T>::addLast(const List<T> &src)
{
    for(ListItem *cur = src.first; cur; cur = cur->next)
        addLast(cur->item); //используем одного элемента
}
 
//Удаление первого элемента из списка
template <class T> T List<T>::removeFirst()
{
    T res  = first->item; //содержимое первого элемента
    first = first->next; //второй элемент становиться первым
    count--; //число элементов списка уменьшилось
    return res; //удаленный элемент возвращается в качестве результата
}
не могу понять в чем дело...
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.01.2011, 20:00     Реализация стека
Посмотрите здесь:

C++ Реализация стека
Реализация стека C++
Реализация класса стека C++
реализация стека C++
Реализация стека. Но ошибка C++
Реализация стека C++
Реализация стека C++
C++ Реализация стека

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
13.01.2011, 20:23     Реализация стека #2
Обезопасьте модули от повторного включения. Если у вас VSC++ подойдет, например, #pragma once, но лучше через #ifndef
blackbanny
128 / 115 / 2
Регистрация: 14.11.2010
Сообщений: 707
13.01.2011, 20:31  [ТС]     Реализация стека #3
Цитата Сообщение от lemegeton Посмотреть сообщение
Обезопасьте модули от повторного включения. Если у вас VSC++ подойдет, например, #pragma once, но лучше через #ifndef
ок, спасибо! =)
Yandex
Объявления
13.01.2011, 20:31     Реализация стека
Ответ Создать тему
Опции темы

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