Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 25, средняя оценка - 4.84
Rabbit13245
28 / 28 / 2
Регистрация: 21.04.2012
Сообщений: 282
#1

Очередь FIFO - C++

21.05.2012, 19:37. Просмотров 3627. Ответов 11
Метки нет (Все метки)

Добрый вечер. Задали написать реализацию очереди FIFO. Загвоздка в том, как передать указание на следующий элемент при его добавлении.

Недавно писал FILO, там было так:

C++
1
2
3
4
5
6
7
8
9
10
bool stack::Push(int v){
ST_LIST *item;
item = new ST_LIST;
 
if (item) {
 item->value=v;
 item->next=first;
 first=item;
 return true;
}
а тут как? тут при добавлении нужно чтобы указатель на вершину был постоянен, а список рос с конца. Подскажите)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.05.2012, 19:37
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Очередь FIFO (C++):

Двумерная очередь (FIFO) - C++
Помогите реализовать FIFO .

Динамическая Очередь (FIFO). - C++
Здравствуйте! Ребят, кому невмоготу , помогите реализовать структуру согласно этим требованиям: 1. Динамическую структуру требуется...

Очередь целых чисел (структура FIFO) - C++
Требуется : Разработать класс «очередь целых чисел» (структура FIFO). Реализовать методы добавления и удаления элементов. Есть : ...

FIFO Очередь, как с ней разобратся?? - C++
Разработать подпрограммы работы с приоритетной очередью. Постановка запросов в очередь выполняется по приоритету, снятие - подряд из...

Изменить удаление и добавление элементов в очередь по правилу FIFO. - C++
Необходимо изменить удаление и добавление элементов в очередь (функции push и pop), по правилу первым вошёл, первым вышел главная ...

Описать класс, реализующий очередь целых чисел типа FIFO. - C++
Класс Очередь: Методы класса: а) создание очереди; б) добавление элемента в очередь (функция push); в) удаление элемента из...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
domovoi94
-19 / 6 / 1
Регистрация: 09.10.2010
Сообщений: 41
21.05.2012, 19:40 #2
это структура типа очередь. Хранишь начало, и конец. Данные забираешь сначала. Записываешь в конец
Rabbit13245
28 / 28 / 2
Регистрация: 21.04.2012
Сообщений: 282
21.05.2012, 20:55  [ТС] #3
Я в ступоре, как сделать функцию добавления в очередь((

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int k=1;
bool spis::Push(int v){
    ST_LIST *item;
    item=new ST_LIST;
    
 
    if (k==1){
        if (item){
            item->value=v;
            first=item;
            return true;
            k++;
        }
        else return false;
    }
    else {
        if (item){
            item->value=v;
            item->next=item;
            return true;
            k++;
        }
        else return false;
    }
 
}
Помогите пожалуйста, этот вариант не работает(((

Добавлено через 11 минут
при первой записи я запоминаю first, при второй - end, а потом при добавлении любого элемента end будет указывать на него, а next - на предыдущий?

Или как?

Добавлено через 49 минут
Ребят, помогите пожалуйста, очень надо до завтра...
DU
1483 / 1059 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
21.05.2012, 20:56 #4
вот топорный вариант:
имея указатель на начало списка вы всегда можете в цикле добраться до его последнего элемента (до тех пор пока item->next не станет равным нулю). вот у вас есть последний итем.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
item* getPredLastItem() // получение предпоследнего
{
  // тут алгоритм прохода от начала до предпоследнего итема. реализовать не сложно.
  return predLast;
}
 
item* getLastItem()
{
   // список может быть пустым и getPredLastItem() может вернуть 0. нужно проверять.
  return getPredLastItem()->next;
}
 
void push(int value)
{
  Item* newItem = new Item();
  newItem->value = value;
  newItem->next = 0;
   // список может быть пустым и getLastItem() может вернуть 0. нужно проверять.
  Item* lastItem = getLastItem();
  lastItem->next = newItem;
}
 
void pop()
{
   // список может быть пустым и getLastItem() может вернуть 0. нужно проверять.
  Item* predLastItem = getPredLastItem();
  delete predLastItem->next; // дестроим последний итем
  predLastItem->next = 0; // теперь предпоследний помечен как последний.
}
Rabbit13245
28 / 28 / 2
Регистрация: 21.04.2012
Сообщений: 282
21.05.2012, 21:02  [ТС] #5
DU, я не понимаю(
Чего-то туго очень все... Можно целиком работающий код?
DU
1483 / 1059 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
21.05.2012, 21:07 #6
вы спрашивайте, не стесняйтесь. что именно вам не понятно?
Rabbit13245
28 / 28 / 2
Регистрация: 21.04.2012
Сообщений: 282
21.05.2012, 21:13  [ТС] #7
мне не понятна Ваша реализация функций добавления элемента и удаления.

Вот как я понимаю очередь: записываем первый элемент - он first, на следующий, который мы запишем, будет ссылка next от того, который first...и так далее. нет?
DU
1483 / 1059 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
21.05.2012, 21:26 #8
я привел несколько упрощенный вариант, которые не рассматривает случай, когда список пустой.
предположим в списке десяток объектов. чтобы добавить в конец списка элемент, нужно:
1 создать новый
2 взять текущий последний.
3 к последнему присоединить новый.

т.е.
C++
1
2
3
4
5
6
7
8
9
10
// создаем новый
Item* newItem = new Item();
newItem->value = value;
newItem->next = 0;
 
// Теперь берем последний итем списка
Item* lastItem = getLastItem();
 
// и присоединяем к нему этот новый.
lastItem->next = newItem;
это понятно?

удаление последнего тоже вроде простое
берем предпоследний итем. по нему находим последний. удаляем последний (delete). помечаем предпоследний последним.
Rabbit13245
28 / 28 / 2
Регистрация: 21.04.2012
Сообщений: 282
21.05.2012, 21:30  [ТС] #9
Да. Это понятно.

А как реализовать, танцуя от того, что изначально очередь пустая? Можете помочь?
DU
1483 / 1059 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
21.05.2012, 21:41 #10
ну все же просто. если getLastItem вернула 0, значит список пустой. значит у него еще нет головы (первого итема.). значит новый созданный и будет его головой. т.е что-нибудь типа:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void push(int value)
{
  Item* newItem = new Item();
  newItem->value = value;
  newItem->next = 0;
 
  Item* lastItem = getLastItem();
  if (lastItem == 0) // если список пустой
  {
     firstItem = newItem;
  }
  else
  {
     lastItem->next = newItem;
  }
}

для удаления последнего элемента из списка действия такие же
если предпоследний элемент не вернулся, значит список или пустой или состоит из одного элемента. проверяем firstItem. если оно нуль - значит список пустой и ничего из него удалить не получится.
если же firstItem не ноль - то он является последним в списке. его нужно задестроить и указатель firstItem приравнять к нулю.
Rabbit13245
28 / 28 / 2
Регистрация: 21.04.2012
Сообщений: 282
21.05.2012, 22:20  [ТС] #11
Хорошо, попробую реализовать. Осталось реализовать вывод на печать...

Добавлено через 13 минут
DU, я не могу реализовать Ваш метод. У Вас не рабочего кода?

Добавлено через 23 минуты
Ребят выручите пожалуйста. Завтра сдавать, а реализовать не могу. Очень нужно
CRonaldo7
0 / 0 / 0
Регистрация: 19.06.2012
Сообщений: 22
19.06.2012, 19:45 #12
вот код посоны
#pragma once;
///////// LIFO
class Lifo
{
int *stack;
int size;
int *p;

public:
Lifo(int size=10):size(size)
{
stack=new int [size];
p=stack;
}
bool isEmpty()
{
return stack==p;
}
bool isFull()
{
return stack+size==p;
}
bool push (int value)
{
if(isFull()) return false;
*p=value;
++p;
return true;
}
int pop ()
{
if(isEmpty()) return 0;
--p;
return *p;
}

~Lifo()
{
delete[]stack;
}

void SetEmpty()
{
p=stack;
}

};
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.06.2012, 19:45
Привет! Вот еще темы с ответами:

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

Реализовать пользовательские классы - дек, стек (LIFO), очередь (FIFO) на базе класса list библиотеки STL - C++
Создать пользовательские классы - дек, стек (LIFO), очередь (FIFO) на базе класса list библиотеки STL. Написать тестирующую программу,...

Очередь «первый вошел — первый вышел» (FIFO) - C++
Очередь — это устройство для хранения данных, похожее на стек. Отли-чие в том, что в стеке последний сохраненный элемент будет первым...

Очередь (сделать очередь, чтобы добавляло, удаляло, читало. Не STL.) - C++
Помогите пожалуйста написать очередь. Есть Температура double и ее тип int ну и нужно сделать очередь, чтобы добавляло, удаляло, читало....


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
19.06.2012, 19:45
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru