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

Функция добавления и увеличения элемента из очереди с приоритетами - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.68
Polinka93
2 / 2 / 0
Регистрация: 05.06.2012
Сообщений: 14
06.06.2012, 08:03     Функция добавления и увеличения элемента из очереди с приоритетами #1
У меня еще одна проблема нужно написать функцию добавления и увеличения элемента из очереди с приоритетами. При необходимости можно вызвать функцию КеерНеар, описав ее прототип. Помогите пожалуйста, у меня сдача зачета а я не могу понять задание совсем

Добавлено через 4 часа 53 минуты
зараннее всем спасибо...)))
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.06.2012, 08:03     Функция добавления и увеличения элемента из очереди с приоритетами
Посмотрите здесь:

C++ функция для увеличения размера букв
Функция добавления C++
класс список, функция добавления элемента в конец C++
C++ Реализовать приложение, содержащее функции добавления нового элемента в массив и удаления элемента из массива. (Имитируется “резиновый” массив)
C++ править код (создание очереди и удаление элемента очереди по усмотрению пользователя)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
06.06.2012, 08:04     Функция добавления и увеличения элемента из очереди с приоритетами #2
В магазине очередь видела? Нет? Ну собери всех друзей и попроси поиграть в магазин, а "продавца" попроси тормозить по полной. В информатике очередь - то же самое. Кто первый пришёл - встаёт у прилавка, это начало очереди. Кто пришёл последним - встаёт в конец очереди. Того, кто в начале очереди, могут обслужить и больше это не член очереди, а на его место встаёт тот, кто пришёл сразу после него. В очереди-контейнере данных обслуживание - это чтение. В любой момент, не зависимо от того, кого уже обслужили, в конец очереди может встать ещё кто то. Вставание в конец - это добавление элемента. Теперь приоритеты. Стоит очередь в 1000 человек и вдруг приходит колонна ветеранов ВОВ челок из ста. Они обслуживаются вне очереди, то есть имеют право сразу пройти к прилавку, но между собой то они равны и когда их 100 человек одновременно, то и они будут стоять в очереди, но все 100 вместе в её начале у прилавка, кто то у самого прилавка, а кто то на сотом месте, в зависимости от того, в каком порядке пришли, а остальные сдвигаются на 100 позиций к концу. 20 ветеранов обслужили, осталось 80, а всего людей в очереди 1080 и приходит ещё 1 человек. Если и он - ветеран, то будет после всех ветеранов 81-м, а если нет, то последним во всей очереди, то есть 1081-м. Очередь с такими правилами - это и есть приоритетная очередь.
Vergil111
31 / 31 / 6
Регистрация: 30.11.2010
Сообщений: 81
06.06.2012, 08:07     Функция добавления и увеличения элемента из очереди с приоритетами #3
Книжку Кормена почитайте, глава 6. Все подробно написано.
Polinka93
2 / 2 / 0
Регистрация: 05.06.2012
Сообщений: 14
06.06.2012, 08:09  [ТС]     Функция добавления и увеличения элемента из очереди с приоритетами #4
спасибо)) но мне не судьба выразить это все в функцию(( но все равно спасибо))

Добавлено через 49 секунд
Цитата Сообщение от Vergil111 Посмотреть сообщение
Книжку Кормена почитайте, глава 6. Все подробно написано.
поздно
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
06.06.2012, 09:10     Функция добавления и увеличения элемента из очереди с приоритетами #5
Функция зависит от внутреннего представления данных очереди. Очередь ведь можно и на массиве делать, а можно на линейном списке. Можно иметь один указатель только на начало очереди, а можно два: на начало и на конец. При наличии приоритетов можно завести массив с указателями на концы каждого фрагмента, состоящего из элементов в равными приоритетами, по числу поддерживаемых приоритетов и отдельно на начало всей очереди. Конец фрагмента, состоящего из элементов с приоритетом выше низшего и начало фрагмента, состоящего из элементов со следующим в порядке понижения приоритетом - соседние позиции. Или массив указателей по числу поддерживаемых приоритетов +1 для хранения и указателя на начало очереди, и концов её фрагментов. Или массив структур по числу поддерживаемых приоритетов с указателями и на начала, и на концы всех фрагментов. Или два массива указателей, в один собрать указатели на начала, а в другой - на концы. Или для каждого приоритета выделить по отдельной очереди. А они могут быть сделаны опять таки на массиве, или на линейном списке. Получается массив массивов, или массив списков. А можно список очередей с каждым приоритетом, тогда список массивов, или список списков. Приоритетная очередь - это верхний уровень абстракции, а на нижнем вместо одной приоритетной может быть две очереди: основная и очередь внеочередников. Элементы основной будут обслуживаться только в том случае, если очередь внеочередников пуста. Но очередь внеочередников - это и есть очередь тех, кто имеет высокий приоритет. Вариантов много, выбор одного отражается на функции. А на используемых в ней идентифкаторах отражается и декларация очереди.

Добавлено через 5 минут
Я ведь на вижу здесь декларации. И метод - тоже функция, только это функция-член. А в классе есть свои синтаксические нюансы. Или это функция-друг? Ничего же не известно.

Добавлено через 1 минуту
Нет даже количества приоритетов и их обозначений. Может они enumом обозначены, или строкой? А может числом? Какого типа?

Добавлено через 1 минуту
Приоритетную очередь можно сделать даже на дереве очередей.
Polinka93
2 / 2 / 0
Регистрация: 05.06.2012
Сообщений: 14
06.06.2012, 09:21  [ТС]     Функция добавления и увеличения элемента из очереди с приоритетами #6
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include "stdafx.h"
#include <iostream>
#include <conio.h>
 
using std::cin;
using std::cout;
 
 
struct list
 { int val;
   list *next;
 };
 
//----- Постановка элемента в конец очереди
// list *PH[2]; - заголовок очереди
void intoFIFO(list *ph[], int v)
{
list *p= new list;                               // создать элемент списка;
p->val = v;                                              // и заполнить его
p->next = NULL;                                // новый элемент - последний
if (ph[0] == NULL)                                    // включение в пустую
     ph[0] = ph[1] = p;                                          // очередь
else                                              // включение за последним
     {                                                         // элементом
     ph[1]->next = p;                     // следующий за последним = новый
     ph[1] = p;                                        // новый = последний
     }
}
void scan(list *ph[])
 {
 
 for(list* p=ph[0];p!=NULL;p=p->next)
 cout<<p->val<<" ";
 cout<<"\n";
 }
 
 
 
//----- Извлечение из очереди
int fromFIFO(list *ph[])
{ list *q;
if (ph[0] ==NULL) return -1;                               // очередь пуста
q = ph[0];                                            // исключение первого
ph[0] = q->next;                                                // элемента
if (ph[0] ==NULL)
     ph[1] = NULL;                                  // элемент единственный
int v = q->val;
 
return v;
}
 
void main()
{
    list A3={7,NULL}, A2={5,&A3}, A1={1,&A2};
list*  ph[2];
ph[0]=&A1, ph[1]=&A3;
scan(ph);
intoFIFO (ph,10);
intoFIFO (ph,2);
scan(ph);
int vv= fromFIFO (ph);
scan(ph);
 
 
getch();
}
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
06.06.2012, 10:15     Функция добавления и увеличения элемента из очереди с приоритетами #7
Моё предложение:
1. Приоритет представлен целым беззнаковым числом, чем оно меньше, тем приоритет выше.
C++
1
2
3
4
5
6
struct list
{
 int value;
 unsigned int prioritet;
 list *next;
};
.
2. Объявить исключение QueryIsEmpty.
C++
1
2
3
4
5
6
7
8
class QueryIsEmpty: publiuc std::exception
{
 virtual char *what ()
 {
  static char s[]="Query is empty";
  return s;
 }
};
.
3. Из дополнительных данных прикрутить к очереди 1 указатель - только на её начало.
C++
1
list *query=nullptr;
.
Тогда функция добавления
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
void AddItemToQuery(list *&query, list &item)
{
 list *p;
 list *b;
 if (query==NULL)
 {
  query=new list;
  query->value=item.value;
  query->prioritet=item.prioritet;
  query->next=nullptr;
 }
 else
 {
  for (p=query; (p->next!=nullptr)&&(p->next->prioritet<=item.prioritet); ++p);
  if (p->Next!=nullptr)
  {
   b=new list;
   b->next=p->next;
   p->next=b;
  }
  else
  {
   p->next=new list;
  }
  p->next->value=item.value;
  p->next->prioritet=item.prioritet;
 }
}
, функция чтения
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
list ReadFromQuery(list *&query)
{
 list r;
 list *b;
 if (query==nullptr)
 {
  throw QueryIsEmpty;
 }
 else
 {
  list r=*query;
  b=query;
  query=query->next;
  delete b;
 }
}
, функция удаление очереди
C++
1
2
3
4
5
6
7
8
9
10
void FreeQuert(list *&query)
{
 list *b=query;
 while (query!=nullptr)
 {
  p=query->next;
  delete query;
  query=b;
 }
}
и всё целиком
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <iostream>
class QueryIsEmpty: publiuc std::exception
{
 virtual char *what ()
 {
  static char s[]="Query is empty";
  return s;
 }
}; 
struct list
{
 int value;
 unsigned int prioritet;
 list *next;
};
list *query=nullptr;
void AddItemToQuery(list *&query, list &item)
{
 list *p;
 list *b;
 if (query==NULL)
 {
  query=new list;
  query->value=item.value;
  query->prioritet=item.prioritet;
  query->next=nullptr;
 }
 else
 {
  for (p=query; (p->next!=nullptr)&&(p->next->prioritet<=item.prioritet); ++p);
  if (p->Next!=nullptr)
  {
   b=new list;
   b->next=p->next;
   p->next=b;
  }
  else
  {
   p->next=new list;
  }
  p->next->value=item.value;
  p->next->prioritet=item.prioritet;
 }
}
list ReadFromQuery(list *&query)
{
 list r;
 list *b;
 if (query==nullptr)
 {
  throw QueryIsEmpty;
 }
 else
 {
  list r=*query;
  b=query;
  query=query->next;
  delete b;
 }
}
void FreeQuert(list *&query)
{
 list *b=query;
 while (query!=nullptr)
 {
  p=query->next;
  delete query;
  query=b;
 }
}
void main()
{
 char c;
 list item;
 do
 {
  std::cout<<"A - добавить элемент,"<<std::endl;
  std::cout<<"R - читать элемент,"<<std::endl;
  std::cout<<"E - выход."<<std::endl;
  std::cin>>c;
  std::cout<<std::endl;
  switch (c)
  {
   case 'a':
   case 'A': std::cout<<"Данные элемента: ";
             std::cin>>item.value;
             std::cout<<", приоритет элемента: ";
             std::cin>>item.prioritet;
             std::cout<<std::endl;
             AddItemToQuery(query, item); 
             break;
   case 'r':
   case 'R': item=ReadFromQuery(query);
             std::cout<<"Данные элемента: "<<item.value<<"."<<std::endl;
             break;
   case 'e':
   case 'E': FreeQuert(query);
             break;
   default : std::cout<<"Не правильный вариант."<<std::endl;
  }
 } while ((c!='e')&&(c!='E'));
 return 0;
}
.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.06.2012, 18:11     Функция добавления и увеличения элемента из очереди с приоритетами
Еще ссылки по теме:

Функция создания очереди C++
Освобождение памяти (функция удаления элемента Очереди) C++
C++ Функция добавления элемента в кольцевой список

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

Или воспользуйтесь поиском по форуму:
Polinka93
2 / 2 / 0
Регистрация: 05.06.2012
Сообщений: 14
06.06.2012, 18:11  [ТС]     Функция добавления и увеличения элемента из очереди с приоритетами #8
спасибо всем огромное
Yandex
Объявления
06.06.2012, 18:11     Функция добавления и увеличения элемента из очереди с приоритетами
Ответ Создать тему
Опции темы

Текущее время: 05:33. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru