IPB
ЛогинПароль:

> Внимание!

1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным.
В описании темы указываем язык!!!

Наладить общение поможет, если вы подпишитесь по почте на новые темы в этом форуме.

2 страниц V  1 2 >  
 Ответить  Открыть новую тему 
> шаблон класса очередь на С++, может у кого есть?
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 10
Пол: Мужской

Репутация: -  0  +


Нужен очень шаблон класса "очередь" на С++, с простыми операциями, такими как вставить новый элемент в очередь, взять вершину очереди, проверка на пустоту очереди, размер очереди, вывод элементов и т.п. Может у кого есть что-нить подобное? smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


в FAQ есть это все на паскале.
Ну и поиском пользуйся...


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Гость






Здесь выкладывался шаблонный class TQueue: моделирование работы банка

(реализация - в присоединенном файле, на расширение не смотри, это именно C++, просто тогда еще нельзя было присоединять СРР файлы)
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Новичок
*

Группа: Пользователи
Сообщений: 11
Пол: Мужской
Реальное имя: Максим

Репутация: -  0  +


С шаблонами и классами работаю первый раз. Попытался написать очередь через массив.
Не понимаю, почему функции showHead () и showTail () работают не так… nea.gif
И вообще, если кто может проверьте правильность реализации…smile.gif
Компилятор Dev-C++.


/*

Шаблон очереди и модуль тест.
Язык реализации: С++

*/

#include <iostream>

// размер массива (по умолчанию) под очередь
#define N 10

using namespace std;

//////////////////////////////////////////////////////////
// Начало шаблона
//////////////////////////////////////////////////////////


template <class T>
class queue {

private :

T *q; // указатель на массив
int begin; // первый элемент очереди
int end; // последний элемент очереди

public :

queue (void); // конструктор
~queue (); // деструктор
bool isEmpty (); // проверка на пустоту
T size (); // количество элементов в очереди
T pop (void); // взятие элемента
void push (T i); // добавление элемента
T showHead (); // посмотреть первый элемент
T showTail (); // посмотреть последний элемент
T makeEmpty (); // очистить очередь
};


// конструктор
template <class T>
queue <T> :: queue (void) {
if (!(q = new T[N])) {
cout << "Can't create array, because hav't free memory!\n";
return;
}
begin = end = 0;
cout << "Initialization ok.\n";
}

// дестуктор
template <class T>
queue <T> :: ~queue () {
delete q;
cout << "\nDestroyed.";
}

// проверка на пустоту
template <class T>
bool queue <T> :: isEmpty () {
return begin;
}

// размер очереди
template <class T>
T queue <T> :: size () {
return (begin-end);
}

// заполнение очереди
template <class T>
void queue <T> :: push (T i) {
if (begin == N) {
cout << "Full.\n";
return;
}
q[begin++] = i;
}

// вынимает элемент
template <class T>
T queue <T> :: pop (void) {
if (begin == end) {
cout << "Empty.\n";
return 0;
}
return q[end++];
}

//////////////////////////////////////////
// НЕ РАБОТАЕТ!!!
/////////////////////////////////////////

// посмотреть первый элемент
template <class T>
T queue <T> :: showHead () {
cout << "\nHead - " << q[end];
}

// посмотреть хвост
template <class T>
T queue <T> :: showTail () {
if (begin == end) {
cout << "\nTail - " << q[begin];
}
else cout << "\nTail - " << q[begin-1];
}

// очистка очереди
template <class T>
T queue <T> :: makeEmpty () {
begin = 0;
end = 0;
}


//////////////////////////////////////////////////////////
// Конец шаблона
//////////////////////////////////////////////////////////


//////////////////////////////////////////////////////////
// Начало модуль теста
//////////////////////////////////////////////////////////


int main(int argc, char *argv[])
{

// создаем объекты
queue <int> a;
queue <double> b;
queue <long int> c;

// начинаем тестировать работу
cout << "Now queue is empty (return 0):";
cout <<"\n" << a.isEmpty();

for (int i = 0; i < N; i++) {
a.push(i);
}

a.showHead();
cout << "\n" <<a.size();
cout <<"\n" << a.isEmpty();
a.showTail();

// вынимаем элементы очереди
cout << endl;
for (int i = 0; i < N; i++) {
cout << a.pop() << " ";
}

// функции не правильно работают
a.showHead();

b.showHead();
b.showTail();

b.push(2.5);
b.push(3.5);
b.push(6.89);

cout << "\n" << b.size();

b.showHead();
b.showTail();
cout << "\n" <<b.pop() << " ";
cout << "\n" <<b.pop() << " ";
cout << "\n" <<b.pop() << " ";
cout << "\n" << b.size();
// явный вызов деструктора
a.~queue();
b.~queue();

system("PAUSE");
return EXIT_SUCCESS;
}

//////////////////////////////////////////////////////////
// Конец модуль теста и программы
//////////////////////////////////////////////////////////



--------------------
Я не боюсь казаться смешным. Хмм..это не каждый может себе позволить...
Чтобы избежать критики, ничего не делайте, ничего не говорите, будьте никем...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Гость






Цитата
Не понимаю, почему функции showHead () и showTail () работают не так…
Измени showHead вот так, и посмотри, ЧТО ты пытаешься выводить:
template <class T>
T queue <T> :: showHead () {
cout << "\nend = " << end << " ";
cout << "Head - " << q[end];
}
(допустимые индексы - от 0 до 9, чтобы было понятно, о чем я)
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Новичок
*

Группа: Пользователи
Сообщений: 11
Пол: Мужской
Реальное имя: Максим

Репутация: -  0  +


volvo
Да и правда… smile.gif
Но теперь вообще запутался…Как написать тогда функции просмотра головы и хвоста, подсказать можешь?
И если я вынимаю один элемент их очереди, то место освобождается, а всунуть я получается ничего уже не могу туда sad.gif unsure.gif


--------------------
Я не боюсь казаться смешным. Хмм..это не каждый может себе позволить...
Чтобы избежать критики, ничего не делайте, ничего не говорите, будьте никем...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Гость






Значит, так...

Проблема - в том, что такой способ не очень подходит для реализации очереди, это вообще-то для реализации Стека было придумано - с очередью надо будет поизвращаться... Я вот тут кое-что набросала - в MinGW вроде работает:

Что еще хотелось бы отметить: половину из этих методов можно внести прямо в определение класса, кроме этого -
// посмотреть первый элемент
template <class T>
T queue <T> :: showHead () {
cout << "\nHead - " << q[end];
}
Метод ничего не возвращает - я сделала его void-ом...


Прикрепленные файлы
Прикрепленный файл  test.cpp ( 2.49 килобайт ) Кол-во скачиваний: 315
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Новичок
*

Группа: Пользователи
Сообщений: 11
Пол: Мужской
Реальное имя: Максим

Репутация: -  0  +


Большое спасибо smile.gif
Вот эту функцию можно пояснить еще:


template <class T>
T queue <T> :: pop (void) {
if (end < 0) {
cout << "Empty.\n";
return 0;
}
T value = q[begin];
for(int i = 0; i < end; ++i) q[i] = q[i + 1];
end -= 1;
return value;
}



Что такое: T value = q[begin]; ?
И что делается в цикле и почему i++ и end -= 1?


--------------------
Я не боюсь казаться смешным. Хмм..это не каждый может себе позволить...
Чтобы избежать критики, ничего не делайте, ничего не говорите, будьте никем...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Новичок
*

Группа: Пользователи
Сообщений: 10
Пол: Мужской

Репутация: -  0  +


Алена, volvo, w@rlock
здорово smile.gif good.gif
правда функцию pop тоже не до конца понял... wink.gif комментарии мона? rolleyes.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Гость






Цитата(w@rlock @ 8.01.2007 18:28)

Что такое:
T value = q[begin];
?
Запоминание первого (головного) элемента для того, чтобы вернуть его значение из функции...
Цитата(w@rlock @ 8.01.2007 18:28)
И что делается в цикле и почему i++ и end -= 1?

В цикле происходит последовательный сдвиг всех элементов до "хвостового" включительно на 1 позицию влево - т.е., ближе к "голове", ибо произошло выталкивание одного элемента из очереди, остальные должны занять его место... Обойму пистолетную в руках держал? Когда вытаскиваешь верхний патрон, все остальные сдвигаются, правда? Здесь то же самое (несмотря на то, что что к обойме более применимо понятие стека)...

А end -= 1 это уменьшаем номер "хвостового" элемента на 1, один элемент из очереди ушел...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Новичок
*

Группа: Пользователи
Сообщений: 10
Пол: Мужской

Репутация: -  0  +


volvo
спасибо. cool.gif smile.gif
но почему ++i, а не i++ ? вроде бы менял, изменений не заметил... blink.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Гость






Цитата
но почему ++i, а не i++
А для отдельно стоящего оператора это не играет роли... Обе версии выполняют одинаковые действия (увеличение значения переменной на 1)...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Новичок
*

Группа: Пользователи
Сообщений: 10
Пол: Мужской

Репутация: -  0  +


да. но ведь в данном примере в цикле pop при ++i значение i[1] присвоется i[2]. а при i++ i[0] присвоется i[1] ?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Гость






for(int i = 0; i < end; ++i) q[i] = q[i + 1];
аналогично

int i = 0;
while(i < end) {
q[i] = q[i + 1];
++i;
}


какая разница, будет последним оператором ++i или i++, объясни мне!!! Он же здесь НЕ в выражении, а отдельный оператор! А НЕ в выражении разницы между префиксным/постфиксным инкрементом НЕТ.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Новичок
*

Группа: Пользователи
Сообщений: 11
Пол: Мужской
Реальное имя: Максим

Репутация: -  0  +


а вот если ещё конструктор копирования написать свой? как это сделать?


--------------------
Я не боюсь казаться смешным. Хмм..это не каждый может себе позволить...
Чтобы избежать критики, ничего не делайте, ничего не говорите, будьте никем...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Новичок
*

Группа: Пользователи
Сообщений: 11
Пол: Мужской
Реальное имя: Максим

Репутация: -  0  +


Писал-писал этот шаблон, а так и не сдал sad.gif
Сказали сменить реализацию blink.gif dry.gif mad.gif Аргументы примерно такие, что неприлично делать очередь с линейным временем доступа...sad.gif Кто что может подсказать? Как написать правильно? Очень срочно нужно...sad.gif


--------------------
Я не боюсь казаться смешным. Хмм..это не каждый может себе позволить...
Чтобы избежать критики, ничего не делайте, ничего не говорите, будьте никем...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Гость






Ссылка на то, как правильно - в третьем сообщении темы... Однако, тебе это не понравилось, ты стал делать по-своему... Тогда извини, но я не понимаю, что ты хочешь... Делай по-своему дальше...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Новичок
*

Группа: Пользователи
Сообщений: 11
Пол: Мужской
Реальное имя: Максим

Репутация: -  0  +


он у меня не компилится просто...sad.gif тем более как просто от туда очередь то выдрать? sad.gif


--------------------
Я не боюсь казаться смешным. Хмм..это не каждый может себе позволить...
Чтобы избежать критики, ничего не делайте, ничего не говорите, будьте никем...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Новичок
*

Группа: Пользователи
Сообщений: 10
Пол: Мужской

Репутация: -  0  +


Я тут тоже очередь пытаюсь всё сделать (некоторые вещи уже из выше написаного взял) wink.gif У volvo не беру по причине, что ещё не такого уровня, многие вещи не понимаю, поэтому пытаюсь свою.

Внизу то, что пока получилось...Только говорят, что у меня некорректная работа с памятью...смотрите мол конструктор и деструктор и думайте...
Что не так и как исправить?

#include <iostream>

#define N 20

using namespace std;

template <class T>
class queue{

private:

T q[N];
T *begin;
T *end;

public:

queue();
~queue();
void push(T);
T pop();
T showHead();
bool isEmpty();
void makeEmpty();
};

template <class T>
queue<T> :: queue(){
begin = end = q;
cout << "\n:: Initialization ok.";
}

template <class T>
queue <T> :: ~queue() {
cout << "\n:: Destroyed.";
}

template <class T>
bool queue <T> :: isEmpty(){
return (begin == end);
}

template <class T>
void queue <T> :: push(T i){
*end = i;
if(end ==(q + N-1)){
end = q;
}
else{end++;}
}

template <class T>
void queue <T> :: makeEmpty() {
begin = end = q;
cout << "\n:: Queue is cleaned.";
}

template <class T>
T queue <T> :: showHead(){
if(this->isEmpty()){
cout << "\n:: Queue is empty.";
return 0;
}
else { return (*begin);}
}

T queue <T> :: pop(){
if(this->isEmpty()){
cout << "\n:: Queue is empty.";
return 0;
}
else{
T first = this->showHead();
if (begin == q + N - 1) {
begin = q;
}
else { begin++; }
return first;
}
}

main() {

cout << "::::::: Module test ::::::::";
cout << "\n:: Creating new queue.";

queue <int> a;

cout << "\n:: Elements pushing in <int> queue...";
a.push(14);
a.push(12);
a.push(16);
a.push(17);

for (int i = 0; i < 9; i++) {
a.push(i);
}

cout << "\n:: Head - " << a.showHead() << endl;
cout << "\n:: Poped head - " << a.pop();
cout << "\n:: Head - " << a.showHead() << endl;

cout << "\n:: All elements: ";
cout << "\n:: ";
for (int i = 0; i < 12; i++) {
cout << a.pop() << " ";
}

// явный вызов деструктора
a.~queue();

// return 0
system("PAUSE");
return EXIT_SUCCESS;

}



Сообщение отредактировано: lays -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #20


Гость






Цитата
он у меня не компилится просто...
Не знаю, что там может НЕ компилиться... Вот выдранная из той программы очередь:

(проверено под Turbo C++)
Прикрепленный файл  Q01.CPP ( 1.67 килобайт ) Кол-во скачиваний: 609


(проверено под GCC/MinGW)
Прикрепленный файл  test.cpp ( 1.44 килобайт ) Кол-во скачиваний: 574


Других компиляторов не держу...

lays, у тебя будет то же самое, что и в предыдущем варианте - опять не понравится преподавателю... Ну не делается так очередь, это же ДСД - Динамическая Структура Данных, нельзя ее ограничивать сразу же массивом...
 К началу страницы 
+ Ответить 

2 страниц V  1 2 >
 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 19.03.2024 16:44
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name