Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 18.09.2010, 17:08   #1
TwiX
Участник клуба
 
Аватар для TwiX
 
Регистрация: 28.07.2009
Сообщений: 1,510
По умолчанию Чем отличается Очередь на базе списка от Очереди на базе массива?

В универе дали задачу написать Очередь на базе списка... А представляю, как писать очередь на базе массива - причём это довольно легко. А что изменится в очереди на базе списка?
TwiX вне форума Ответить с цитированием
Старый 18.09.2010, 17:57   #2
Stilet
Белик Виталий :)
Старожил
 
Аватар для Stilet
 
Регистрация: 23.07.2007
Сообщений: 57,792
По умолчанию

Ничего. список это тот же массив.
Единственное что - элементы в списке не обязательно стоят рядом.
Они могут быть разбросаны в памяти безструктурно. Каждый элемент списка знает где лежат его соседи.
Ну а в случае с очередью просто напросто из списка будет выбираться элементы не из его конца а из его головы, таким образом, следующий после первого элемента станет главным
I'm learning to live...
Stilet вне форума Ответить с цитированием
Старый 18.09.2010, 19:01   #3
TwiX
Участник клуба
 
Аватар для TwiX
 
Регистрация: 28.07.2009
Сообщений: 1,510
По умолчанию

Т.е. можно запрогать через упорядоченный массив? Или можно через неупорядоченный массив, но его элементы будут хранить не только то, что им нужно хранить, но ещё и номер следующего за ним? Как лучше?) Спасибо
TwiX вне форума Ответить с цитированием
Старый 18.09.2010, 19:18   #4
Гром
Старожил
 
Аватар для Гром
 
Регистрация: 21.03.2009
Сообщений: 2,193
По умолчанию

Определяем структуру узла:
Код:
struct Node
{
Node* next;
int value;
};
(плюс конструктор желательно). Далее реализуем очередь:
Код:
class Queue
{
public:
Queue();
~Queue();
void push(int val);
int pop();
private:
Node* top;
Node* bottom;
};
При помощи push вставляем новый узел с нужными данными следом за bottom, делаем для вставленного
Код:
bottom -> next = 0;
При вызове pop возвращаем данные из узла top, попутно удаляя этот узел, top'ом становится next удаленного узла.
Плюс проверки на равенство нулю top и bottom когда надо.
Если у узла будет деструктор
Код:
Node::~Node()
{
if (next)
   delete next;
}
то перед удалением top в push присваиваем его next ноль, чтобы не удалить сразу весь список.
Вот так вот можно сделать очередь на базе списка.
P.S. Ну или можно вставлять новый узел перед top, а удалять узел bottom - как вам будет удобней.
Простые и красивые программы - коды программ + учебник C++
Создание игры - взгляд изнутри - сайт проекта
Тема на форуме, посвященная ему же
Гром вне форума Ответить с цитированием
Старый 18.09.2010, 23:05   #5
TwiX
Участник клуба
 
Аватар для TwiX
 
Регистрация: 28.07.2009
Сообщений: 1,510
По умолчанию

Не совсем то, что мне нужно... Нужно реализовать через шаблон. Ниже выложу, что начал писать, но там почему неправильно работает Push (переменная i создаётся не новая, а используются старая и если попробовать запушить 3 числа, то после выталкивания последнего, получим муть)
Код:
template <class T>
struct TItem
{
	TItem* prev;
	T value;
};

template <class T>
class TQueue
{
public:
	TQueue();
	int push(const T&);
	int pop(T&);
	int isEmpty() { return size == 0 ; }
private:
	int size ;  // Number of elements on Stack
	TItem<T>* top;
	TItem<T>* bottom;
};


template <class T>
TQueue<T>::TQueue()
{
	size=0;
	top=0;
	bottom=0;
}

template <class T>
int TQueue<T>::push(const T& item)
{
	TItem<T> i; //вот тут что-то не то
	i.value=item;
	i.prev=0;
	if (size==0)
	{
		top=&i;
		bottom=top;
	}
	else
	{
		top->prev=&i; //*top->prev=i;
		top=&i;
		top->prev=0;
	}
	size++;
}

template <class T>
int TQueue<T>::pop(T& item)
{
	T i;
	i=(*top).value;
	item=i;
	top=top->prev;
	size--;
}
Думал изменить struct на class, но не помогло (вроде в С++ это одно и то же)
TwiX вне форума Ответить с цитированием
Старый 18.09.2010, 23:38   #6
Гром
Старожил
 
Аватар для Гром
 
Регистрация: 21.03.2009
Сообщений: 2,193
По умолчанию

Заменяйте тип value в узле с int на шаблонный - и будет то, что надо.
Далее, по вашему коду. Общий совет - в конструкторах лучше использовать списки инициализации. Для встроенных типов это, может быть, и безразлично, а вот для объектов классов (особенно без конструктора по умолчанию), констант и ссылок - это критично. Поэтому желательно всегда использовать подход, основанный на списке инициализации:
Код:
template <class T>
TQueue<T>::TQueue():
	size(0),
	top(0),
	bottom(0)
	{
	}
По поводу push и pop - я бы реализовал их так (переделать под шаблон будет легко):
Код:
Node::Node(int val):
 value(val), next(0)
 {
 }

void Queue::push(int val)
{
Node* NewNode = new Node(val);   //Кстати, вы объявляете новый элемент статически - потому у вас и получается полный бред
if (bottom) //Если есть последний элемент, т.е. есть хотя бы один
 bottom -> next = NewNode;
else
 {
 top = NewNode;
 bottom = NewNode;
 }
}

int pop()
{
if (top) //Если хоть один элемент есть
 {
 Node* del = top;
 int val = del -> value;
 top = top -> next;
 del -> next = 0;
 delete del;
 return val;
 }
else //Ошибка, к примеру, сообщим о ней и просто вернем ноль
 {
 std::cerr << "Queue is empty!" << std::endl;
 return 0;
 }
}
Вставляем элемент следом за bottom, извлекаем top (а вы как вставляете почему-то перед top, так и извлекаете top, а это уже какой-то стек вообще).
И обычно в односвязных списках все-таки ссылаются на "следующий", а не на "предыдущий" элемент - это насчет названий prev и next.
Простые и красивые программы - коды программ + учебник C++
Создание игры - взгляд изнутри - сайт проекта
Тема на форуме, посвященная ему же
Гром вне форума Ответить с цитированием
Старый 19.09.2010, 01:01   #7
TwiX
Участник клуба
 
Аватар для TwiX
 
Регистрация: 28.07.2009
Сообщений: 1,510
По умолчанию

Pop я в конце писал... Там и правда надо было bottom писать - тупанул. Сейчас попробую исправить
Спасибо

Добавлено:
По поводу ссылки на следующий - это всё-таки дело вкуса=) Я очередь себе представляю как столбик, где сверху вставляют элементы, а снизу забирают) Поэтому и удобней prev использовать =)

Добавлено:
И не понял, почему у меня не работало и что такое списки инициализации)

Добавлено:
Всё, разобрался. Нужно у меня просто исправить TItem<T> i; на TItem<T>* i = new TItem<T>; (я раньше так и хотел, но думал, что так только массивы создаются - пробовал писать new TItem<T> i xD

Последний раз редактировалось TwiX; 19.09.2010 в 01:20.
TwiX вне форума Ответить с цитированием
Старый 16.02.2011, 12:17   #8
tema93
 
Регистрация: 10.11.2010
Сообщений: 7
Печаль очередь на базе массива

Цитата:
Сообщение от TwiX Посмотреть сообщение
В универе дали задачу написать Очередь на базе списка... А представляю, как писать очередь на базе массива - причём это довольно легко. А что изменится в очереди на базе списка?
Доброго времени дня! А я не представляю как на базе массива создать двунаправленную очередь (дек) с ограничением по входу и удалить , прибавить элемент, очистить дек и проверить на пустоту.
Если Вы представляете - поделитесь своим предствлением, пожалуйста
tema93 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Чем отличается журналист от корреспонедента? Golovastik Свободное общение 3 24.06.2010 19:08
Очередь с приоритетами на базе кучи Nastenova Помощь студентам 1 15.06.2010 16:11
Чем отличается IA-64 от IA-32 Ivan_32 Assembler - Ассемблер (FASM, MASM, WASM, NASM, GoASM, Gas, RosAsm, HLA) и не рекомендуем TASM 2 09.06.2009 16:13
Чем отличается кампилятор от интерпретатора prikolist Помощь студентам 1 20.06.2008 12:16
Чем отличается AX от BX? veter_s_morya Assembler - Ассемблер (FASM, MASM, WASM, NASM, GoASM, Gas, RosAsm, HLA) и не рекомендуем TASM 3 05.05.2008 16:50