Форум программистов
 
Контакты: о проблемах с регистрацией, почтой и по другим вопросам пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail.

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

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

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

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

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

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

icq: 482-373-277
По умолчанию

Определяем структуру узла:
Код:

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
Репутация: 225
По умолчанию

Не совсем то, что мне нужно... Нужно реализовать через шаблон. Ниже выложу, что начал писать, но там почему неправильно работает 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
Репутация: 473

icq: 482-373-277
По умолчанию

Заменяйте тип 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
Репутация: 225
По умолчанию

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, 13:17   #8
tema93
 
Регистрация: 10.11.2010
Сообщений: 7
Репутация: 10
Печаль очередь на базе массива

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

Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход

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


18:49.


Powered by vBulletin® Version 3.8.8 Beta 2
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.

RusProfile.ru


Справочник российских юридических лиц и организаций.
Проекты отопления, пеллетные котлы, бойлеры, радиаторы
интернет магазин respective.ru