PDA

Просмотр полной версии : Работа с Деком.



Aleno4ka
16.04.2009, 13:23
Разработать пакет процедур и функций для работы с деком. Обязательно должны быть реализованы следующие операции:
1. Вычисление длины дека
2. Добавление элемента в дек (с обеих сторон) -числа
3. Удаление элемента из дека (с обеих сторон)
4. Вывод на экран крайних элементов дека
5. Вывод на экран всех элементов дека.
6. Уничтожение дека и очистка занимаемой им памяти.

Помогите пожалуйста!!!
Буду рада любой помощи... Хоть частично- хоть какую-нибудь функцию...

Romeo
16.04.2009, 14:15
Перемещено из "С и С++".

Rycharg
18.04.2009, 11:18
Приветствую.
Хочу оказать медвежью услугу.
Т.к. писать функции мне было не интересно(да, и тебе было бы не интересно получить готовый ответ;)), дек был оформлен как шаблон класса.



#include <iostream.h>
// Извиняюсь перед разработчиками stl за такую убогую пародию ).
template<class T>
class deque{
//__________________________________________________ _________________________
public:
deque() : bound_size(5){
array = new T[ bound_size * 2 ];
first.left_bound = last.left_bound = array;
first.cur = last.cur = first.left_bound + bound_size;
first.right_bound = last.right_bound = first.cur + bound_size;
}
~deque(){ delete[] array; }
class iterator{
public:
T* cur;
T* left_bound;
T* right_bound;
};
inline T& operator[]( unsigned long N ){ return *(first.cur + N); }
inline unsigned long size() const{ return last.cur - first.cur; }
inline void push_back( const T& val ){
if( last.cur == last.right_bound ) d_realloc();
*last.cur++ = val;
}
inline void push_front( const T& val ){
if( first.cur == first.left_bound ) d_realloc();
*--first.cur = val;
}
inline void pop_back(){
if( last.cur != last.left_bound){
--last.cur;
}else{
d_realloc();
}
}
inline void pop_front(){
if( first.cur != first.right_bound){
++first.cur;
}else{
d_realloc();
}
}
inline void SetBoundSize(unsigned long val){
bound_size = val;
d_realloc();
}
//__________________________________________________ _________________________
private:
T* array;
iterator first;
iterator last;
unsigned long bound_size;
inline void d_realloc(){
unsigned long Size = size();
T* temp = new T[ Size + bound_size*2];
memcpy( temp + bound_size, first.cur, Size * sizeof(T));
delete[] array;
array = temp;
first.left_bound = array;
first.cur = array + bound_size;
first.right_bound = first.cur + bound_size;
last.cur = first.cur + Size;
last.left_bound = last.cur - bound_size;
last.right_bound = last.cur + bound_size;
}
};
//------------------------------------------------------------------------------
int main(int argc, char* argv[])
{
deque<int> Deque;
for( int i = 0; i < 10; ++i){
Deque.push_back(i);
Deque.push_front(i);
}
cout << "Size: " << Deque.size() << endl;
cout << "First: " << Deque[0] << endl;
cout << "Last: " << Deque[ Deque.size() - 1 ] << endl;
cout << "All: ";
for(int i = 0; i < Deque.size(); ++i){
cout << Deque[i] << " ";
}
char a;
cin >> a;
return 0;
}
//---------------------------------------------------------------------------

Если будут вопросы по "даунгрейду" этого кода до функций - обращайся.
З.Ы. Если было нужно организовать дек через список, то извиняюсь за оффтоп.