Добавил:
wmir
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз:
Предмет:
Файл:Инженерия ПЗ Бакалавр / templates
.txt
// -----------------------------------------------------------//
// Шаблон класса Стек
#include <iostream>
#include <iomanip>
using namespace std;
template <typename T>
class Stack
{
private:
T *stackPtr; // указатель на стек
int size; // размер стека
T top; // вершина стека
public:
Stack(int = 10);// по умолчанию размер стека равен 10 элементам
~Stack(); // деструктор
bool push(const T ); // поместить элемент в стек
bool pop(); // удалить из стека элемент
void printStack();
};
int main()
{
Stack <int> myStack(5);
// заполняем стек
cout << "Заталкиваем элементы в стек: ";
int ct = 0;
while (ct++ != 5)
{
int temp;
cin >> temp;
myStack.push(temp);
}
myStack.printStack(); // вывод стека на экран
cout << "\nУдаляем два элемента из стека:\n";
myStack.pop(); // удаляем элемент из стека
myStack.pop(); // удаляем элемент из стека
myStack.printStack(); // вывод стека на экран
return 0;
}
// конструктор
template <typename T>
Stack<T>::Stack(int s)
{
size = s > 0 ? s: 10; // инициализировать размер стека
stackPtr = new T[size]; // выделить память под стек
top = -1; // значение -1 говорит о том, что стек пуст
}
// деструктор
template <typename T>
Stack<T>::~Stack()
{
delete [] stackPtr; // удаляем стек
}
// элемент функция класса Stack для помещения элемента в стек
// возвращаемое значение - true, операция успешно завершена
// false, элемент в стек не добавлен
template <typename T>
bool Stack<T>::push(const T value)
{
if (top == size - 1)
return false; // стек полон
top++;
stackPtr[top] = value; // помещаем элемент в стек
return true; // успешное выполнение операции
}
// элемент функция класса Stack для удаления элемента из стек
// возвращаемое значение - true, операция успешно завершена
// false, стек пуст
template <typename T>
bool Stack<T>::pop()
{
if (top == - 1)
return false; // стек пуст
stackPtr[top] = 0; // удаляем элемент из стека
top--;
return true; // успешное выполнение операции
}
// вывод стека на экран
template <typename T>
void Stack<T>::printStack()
{
for (int ix = size -1; ix >= 0; ix--)
cout << "|" << setw(4) << stackPtr[ix] << endl;
}
// ------------------------------------------- //
// Шаблон Стек
#ifndef STACK_H
#define STACK_H
#include <cassert> // для assert
#include <iostream>
#include <iomanip> // для setw
template <typename T>
class Stack
{
private:
T *stackPtr; // указатель на стек
const int size; // максимальное количество элементов в стеке
int top; // номер текущего элемента стека
public:
Stack(int = 10); // по умолчанию размер стека равен 10 элементам
Stack(const Stack<T> &); // конструктор копирования
~Stack(); // деструктор
inline void push(const T & ); // поместить элемент в вершину стека
inline T pop(); // удалить элемент из вершины стека и вернуть его
inline void printStack(); // вывод стека на экран
inline const T &Peek(int ) const; // n-й элемент от вершины стека
inline int getStackSize() const; // получить размер стека
inline T *getPtr() const; // получить указатель на стек
inline int getTop() const; // получить номер текущего элемента в стеке
};
// реализация методов шаблона класса STack
// конструктор Стека
template <typename T>
Stack<T>::Stack(int maxSize) :
size(maxSize) // инициализация константы
{
stackPtr = new T[size]; // выделить память под стек
top = 0; // инициализируем текущий элемент нулем;
}
// конструктор копирования
template <typename T>
Stack<T>::Stack(const Stack<T> & otherStack) :
size(otherStack.getStackSize()) // инициализация константы
{
stackPtr = new T[size]; // выделить память под новый стек
top = otherStack.getTop();
for(int ix = 0; ix < top; ix++)
stackPtr[ix] = otherStack.getPtr()[ix];
}
// функция деструктора Стека
template <typename T>
Stack<T>::~Stack()
{
delete [] stackPtr; // удаляем стек
}
// функция добавления элемента в стек
template <typename T>
inline void Stack<T>::push(const T &value)
{
// проверяем размер стека
assert(top < size); // номер текущего элемента должен быть меньше размера стека
stackPtr[top++] = value; // помещаем элемент в стек
}
// функция удаления элемента из стека
template <typename T>
inline T Stack<T>::pop()
{
// проверяем размер стека
assert(top > 0); // номер текущего элемента должен быть больше 0
stackPtr[--top]; // удаляем элемент из стека
}
// функция возвращает n-й элемент от вершины стека
template <class T>
inline const T &Stack<T>::Peek(int nom) const
{
//
assert(nom <= top);
return stackPtr[top - nom]; // вернуть n-й элемент стека
}
// вывод стека на экран
template <typename T>
inline void Stack<T>::printStack()
{
for (int ix = top - 1; ix >= 0; ix--)
cout << "|" << setw(4) << stackPtr[ix] << endl;
}
// вернуть размер стека
template <typename T>
inline int Stack<T>::getStackSize() const
{
return size;
}
// вернуть указатель на стек (для конструктора копирования)
template <typename T>
inline T *Stack<T>::getPtr() const
{
return stackPtr;
}
// вернуть размер стека
template <typename T>
inline int Stack<T>::getTop() const
{
return top;
}
#endif // STACK_H
// ------------------------------------------- //
// Шаблон Очередь
#ifndef QUEUE_H
#define QUEUE_H
#include <cassert>
template<typename T>
class Queue
{
private:
T *queuePtr; // указатель на очередь
const int size; // максимальное количество элементов в очереди
int begin, // начало очереди
end; // конец очереди
int elemCT; // счетчик элементов
public:
Queue(int =10); // конструктор по умолчанию
Queue(const Queue<T> &); // конструктор копирования
~Queue(); // деструктор
void enqueue(const T &); // добавить элемент в очередь
T dequeue(); // удалить элемент из очереди
void printQueue();
};
// реализация методов шаблона класса Queue
// конструктор по умолчанию
template<typename T>
Queue<T>::Queue(int sizeQueue) :
size(sizeQueue), // инициализация константы
begin(0), end(0), elemCT(0)
{
// дополнительная позици поможет нам различать конец и начало очереди
queuePtr = new T[size + 1];
}
// конструктор копии
template<typename T>
Queue<T>::Queue(const Queue &otherQueue) :
size(otherQueue.size) , begin(otherQueue.begin),
end(otherQueue.end), elemCT(otherQueue.elemCT),
queuePtr(new T[size + 1])
{
for (int ix = 0; ix < size; ix++)
queuePtr[ix] = otherQueue.queuePtr[ix]; // копируем очередь
}
// деструктор класса Queue
template<typename T>
Queue<T>::~Queue()
{
delete [] queuePtr;
}
// функция добавления элемента в очередь
template<typename T>
void Queue<T>::enqueue(const T &newElem)
{
// проверяем, ести ли свободное место в очереди
assert( elemCT < size );
// обратите внимание на то, что очередь начинает заполняться с 0 индекса
queuePtr[end++] = newElem;
elemCT++;
// проверка кругового заполнения очереди
if (end > size)
end -= size + 1; // возвращаем end на начало очереди
}
// функция удаления элемента из очереди
template<typename T>
T Queue<T>::dequeue()
{
// проверяем, есть ли в очереди элементы
assert( elemCT > 0 );
T returnValue = queuePtr[begin++];
elemCT--;
// проверка кругового заполнения очереди
if (begin > size)
begin -= size + 1; // возвращаем behin на начало очереди
return returnValue;
}
template<typename T>
void Queue<T>::printQueue()
{
cout << "Очередь: ";
if (end == 0 && begin == 0)
cout << " пустая\n";
else
{
for (int ix = end; ix >= begin; ix--)
cout << queuePtr[ix] << " ";
cout << endl;
}
}
#endif // QUEUE_H
//---------------------------------------------------//
// Шаблон Вектор
#include <iostream>
#include <string>
#include <cassert>
#include <algorithm>
using namespace std;
template <class T>
class Vector
{
public:
typedef T * iterator;
Vector();
Vector(unsigned int size);
Vector(unsigned int size, const T & initial);
Vector(const Vector<T> & v);
~Vector();
unsigned int capacity() const;
unsigned int size() const;
bool empty() const;
iterator begin();
iterator end();
T & front();
T & back();
void push_back(const T & value);
void pop_back();
void reserve(unsigned int capacity);
void resize(unsigned int size);
T & operator[](unsigned int index);
Vector<T> & operator=(const Vector<T> &);
private:
unsigned int my_size;
unsigned int my_capacity;
T * buffer;
};
// Your code goes here ...
template<class T>
Vector<T>::Vector()
{
my_capacity = 0;
my_size = 0;
buffer = 0;
}
template<class T>
Vector<T>::Vector(const Vector<T> & v)
{
my_size = v.my_size;
my_capacity = v.my_capacity;
buffer = new T[my_size];
for (int i = 0; i < my_size; i++)
buffer[i] = v.buffer[i];
}
template<class T>
Vector<T>::Vector(unsigned int size)
{
my_capacity = size;
my_size = size;
buffer = new T[size];
}
template<class T>
Vector<T>::Vector(unsigned int size, const T & initial)
{
my_size-size;
my_capacity = size;
buffer = new T [size];
for (int i = 0; i < size; i++)
buffer[i] = initial;
T();
}
template<class T>
Vector<T> & Vector<T>::operator = (const Vector<T> & v)
{
delete[ ] buffer;
my_size = v.my_size;
my_capacity = v.my_capacity;
buffer = new T [my_size];
for (int i = 0; i < my_size; i++)
buffer[i] = v.buffer[i];
return *this;
}
template<class T>
typename Vector<T>::iterator Vector<T>::begin()
{
return buffer;
}
template<class T>
typename Vector<T>::iterator Vector<T>::end()
{
return buffer + size();
}
template<class T>
T& Vector<T>::Vector<T>::front()
{
return buffer[0];
}
template<class T>
T& Vector<T>::Vector<T>::back()
{
return buffer[size - 1];
}
template<class T>
void Vector<T>::push_back(const T & v)
{
if (my_size >= my_capacity)
reserve(my_capacity +5);
buffer [my_size++] = v;
}
template<class T>
void Vector<T>::pop_back()
{
my_size--;
}
template<class T>
void Vector<T>::reserve(unsigned int capacity)
{
if(buffer == 0)
{
my_size = 0;
my_capacity = 0;
}
T * buffer = new T [capacity];
assert(buffer);
copy (buffer, buffer + my_size, buffer);
my_capacity = capacity;
delete[] buffer;
buffer = buffer;
}
template<class T>
unsigned int Vector<T>::size()const//
{
return my_size;
}
template<class T>
void Vector<T>::resize(unsigned int size)
{
reserve(size);
size = size;
}
template<class T>
T& Vector<T>::operator[](unsigned int index)
{
return buffer[index];
}
template<class T>
unsigned int Vector<T>::capacity()const
{
return my_capacity;
}
template<class T>
Vector<T>::~Vector()
{
delete[]buffer;
}
// ------------------------------------------------------------------
Шаблон Список
#include <iostream>
#include <algorithm>
using namespace std;
template <class T> class Link;
template <class T> class List_iterator;
template <class T>
class List
{
public:
typedef List_iterator<T> iterator;
List();
List(const List<T> & l);
~List();
bool empty() const;
unsigned int size() const;
T & back() const;
T & front() const;
void push_front(const T & x);
void push_back(const T & x);
void pop_front();
void pop_back();
iterator begin() const;
iterator end() const;
void insert(iterator pos, const T & x);
void erase(iterator & pos);
List<T> & operator=(const List<T> & l);
protected:
Link<T> * first_link;
Link<T> * last_link;
unsigned int my_size;
};
template <class T>
List<T>::List()
{
first_link = 0;
last_link = 0;
my_size = 0;
}
template <class T>
List<T>::List(const List & l)
{
first_link = 0;
last_link = 0;
my_size = 0;
for (Link<T> * current = l.first_link; current != 0; current = current -> next_link)
push_back(current -> value);
}
template <class T>
typename List<T>::iterator List<T>::begin() const
{
return iterator(first_link);
}
template <class T>
class Link
{
private:
Link(const T & x): value(x), next_link(0), prev_link(0) {}//pg. 204
T value;
Link<T> * next_link;
Link<T> * prev_link;
friend class List<T>;
friend class List_iterator<T>;
};
template <class T> class List_iterator
{
public:
typedef List_iterator<T> iterator;
List_iterator(Link<T> * source_link): current_link(source_link) { }
List_iterator(): current_link(0) { }
List_iterator(List_iterator<T> * source_iterator): current_link(source_iterator.current_link) { }
T & operator*(); // dereferencing operator
iterator & operator=(const iterator & rhs);
bool operator==(const iterator & rhs) const;
bool operator!=(const iterator & rhs) const;
iterator & operator++();
iterator operator++(int);
iterator & operator--();
iterator operator--(int);
protected:
Link<T> * current_link;
friend class List<T>;
};
template <class T>
T & List_iterator<T>::operator*()
{
return current_link -> value;
}
template <class T>
List_iterator<T> & List_iterator<T>::operator++()
{
current_link = current_link -> next_link;
return *this;
}
template <class T>
void List<T>::push_back(const T & x)
{
link<T> * last_link = new link<T> (x);
if (empty())
first_link = last_link;
else
{
last_link->prev_link = last_link;
last_link->prev_link = last_link;
last_link = last_link;
}
}
Соседние файлы в папке Инженерия ПЗ Бакалавр