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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 36, средняя оценка - 4.97
M@k7
6 / 6 / 0
Регистрация: 17.10.2011
Сообщений: 165
#1

Как описать абстрактный тип данных? - C++

06.12.2011, 22:17. Просмотров 4853. Ответов 16
Метки нет (Все метки)

очередь
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ramarren14
2 / 2 / 0
Регистрация: 14.07.2011
Сообщений: 49
06.12.2011, 22:24     Как описать абстрактный тип данных? #2
По идее как двусторонний массив(данные можно добавлять и в конец, и в начало).
Jupiter
Каратель
Эксперт С++
6550 / 3970 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
06.12.2011, 22:26     Как описать абстрактный тип данных? #3
Цитата Сообщение от M@k7 Посмотреть сообщение
Как описать абстрактный тип данных?
Это типа предложение сделать за вас? На форуме вообще-то есть поиск, и точно существует тема посвященная спискам, стекам, очередям и другим абстрактным структурами данных
Chelioss
179 / 179 / 4
Регистрация: 08.01.2011
Сообщений: 1,133
06.12.2011, 22:28     Как описать абстрактный тип данных? #4
Цитата Сообщение от ramarren14 Посмотреть сообщение
По идее как двусторонний массив(данные можно добавлять и в конец, и в начало).
Двусторонний массив? Это как?
DU
1480 / 1056 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
06.12.2011, 22:35     Как описать абстрактный тип данных? #5
Абстрактный - подразумевает наличие чисто виртуальных ф-ий. Интерфейс короче. У FIFO (first input first output) очереди интерфейс из двух ф-ий. одна для засовывания объекта в очередь, другая для высовывания из нее. Не шаблонная очередь для интов выглядит так:

C++
1
2
3
4
5
6
7
8
class Queue
{
public:
  virtual ~Queue() {}
 
  virtual void push(int val) = 0;
  virtual int pop() = 0;
};
Можно дополнить полезными ф-иями для определения количества объектов в очереди и т.п.
Реализовывать интерфейс можно как захочется. хоть на массивах, хоть на списках.
alex_x_x
бжни
2445 / 1650 / 84
Регистрация: 14.05.2009
Сообщений: 7,162
06.12.2011, 22:36     Как описать абстрактный тип данных? #6
предлагаю как в лиспе
тип пара + 4 оператора
абстрактней некуда
Chelioss
179 / 179 / 4
Регистрация: 08.01.2011
Сообщений: 1,133
06.12.2011, 22:36     Как описать абстрактный тип данных? #7
Цитата Сообщение от DU Посмотреть сообщение
Абстрактный - подразумевает наличие чисто виртуальных ф-ий.
ТС не об этом написал.
Jupiter
Каратель
Эксперт С++
6550 / 3970 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
06.12.2011, 22:38     Как описать абстрактный тип данных? #8
Цитата Сообщение от DU Посмотреть сообщение
Абстрактный - подразумевает наличие чисто виртуальных ф-ий
DU, стоит различать абстрактный типы и структуры данных
DU
1480 / 1056 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
06.12.2011, 22:39     Как описать абстрактный тип данных? #9
какой вопрос, такой ответ. заголовок + содержимое наталкивает на абстрактный интерфейс для очереди. если нет, то что такое абстрактный тип данных?
M@k7
6 / 6 / 0
Регистрация: 17.10.2011
Сообщений: 165
06.12.2011, 22:50  [ТС]     Как описать абстрактный тип данных? #10
Абстра́ктный тип да́нных (АТД) — это тип данных, который предоставляет для работы с элементами этого типа определённый набор функций, а также возможность создавать элементы этого типа при помощи специальных функций.

Мне нужен пример желательно с описантем.
DU
1480 / 1056 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
06.12.2011, 22:58     Как описать абстрактный тип данных? #11
не хотите абстрактных классов. ок. вот очередь, которая соответствует вашему определению АТД

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
class Queue
{
public:
  void push(int val)
  {
    m_list.push_front(val);
  }
 
  int pop()
  {
    const int ret = m_list.back();
    m_list.pop_back();
    return ret;
  }
 
  unsigned size() const
  {
    return unsigned(m_list.size());
  }
 
  bool empty() const
  {
    return m_list.empty();
  }
 
private:
  std::list<int> m_list;
};
ramarren14
2 / 2 / 0
Регистрация: 14.07.2011
Сообщений: 49
06.12.2011, 23:04     Как описать абстрактный тип данных? #12
Цитата Сообщение от Chelioss Посмотреть сообщение
Двусторонний массив? Это как?
Ну как то вот так!
http://pikucha.ru/i7fNG
Chelioss
179 / 179 / 4
Регистрация: 08.01.2011
Сообщений: 1,133
06.12.2011, 23:45     Как описать абстрактный тип данных? #13
Цитата Сообщение от DU Посмотреть сообщение
std::list<int> m_list;
std::deque же.
Цитата Сообщение от ramarren14 Посмотреть сообщение
Ну как то вот так!
http://pikucha.ru/i7fNG
И где там написано про двусторонний массив?
DU
1480 / 1056 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
07.12.2011, 00:18     Как описать абстрактный тип данных? #14
похоже вы не видите связи между тем определением, которое привели и тем классом, который я тут привел.

Поясняю
Абстра́ктный тип да́нных (АТД) — это тип данных
Queue - тип данных

, который предоставляет для работы с элементами этого типа определённый набор функций
C++
1
2
3
4
void Queue::push(int)
int Queue::pop()
unsigned Queue::size() const
bool Queue::empty() const
Все эти методы и есть тот самый набор ф-ий, который позволяет что-то делать с очередью

, а также возможность создавать элементы этого типа при помощи специальных функций.
Можете считать дефолтный конструктор для Queue той самой ф-ией, которая и создает экзепляр абстрактного типа данных Очередь.

list<int> m_list - это деталь имплементации этой очереди. Она скрыта от пользователей очереди. Если вам не нравится std::list<int> , можете использовать любой другой std-ый контейнер или написать свой или еще как вам угодно это сделать. Пользователей класса Queue детали реализации вообще не должны волновать. Они работают с публичным набором функций (интерфейсом) класса Queue. Про инкапсюляцию слышали? Вот это и есть ее проявление: в классе Queue детали реализации скрыты за публичным интерфейсом.
Chelioss
179 / 179 / 4
Регистрация: 08.01.2011
Сообщений: 1,133
07.12.2011, 00:24     Как описать абстрактный тип данных? #15
Даже не читал полностью ваше сообщениею
Адаптер std::queue содержит по умолчанию контейнер типа std::deque.
DU
1480 / 1056 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
07.12.2011, 00:43     Как описать абстрактный тип данных? #16
Адаптер std::queue содержит по умолчанию контейнер типа std::deque.
Можно же и списком параметризовать. deque - вероятно самый оптимальный для этих целей.
Но дело не в этом. Вопрос у ТС - как описать очередь. Можно трактовать двояко:
1 Где мне взять готовую очередь?
2 Как мне самому написать класс, представляющий очередь?
Подобного рода вопросы возникают в вузах, а там на начальных этапах требуют самодельной реализацииачальнии всяких динамических массивов, сортировок, очередей и т.д. Использование stl считается недопустимым читом. Поэтому в кратце и был изложен сбособ самодельной реализации (описания) очереди. Что действительно нужно ТС - хз.

Вот кстати пример требований к очереди:
С++ структура даных очередь
Хотят иметь возможность добавлять в начало очереди. с такими требованиями стандартная queue не подходит. Придется свой класс писать.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.12.2011, 02:43     Как описать абстрактный тип данных?
Еще ссылки по теме:

C++ Абстрактный тип данных
C++ Абстрактный тип данных
Абстрактный тип данных C++
Как правильно описать тип данных C++
C++ Разработайте и реализуйте абстрактный тип данных

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

Или воспользуйтесь поиском по форуму:
alkagolik
Заблокирован
07.12.2011, 02:43     Как описать абстрактный тип данных? #17
Цитата Сообщение от DU Посмотреть сообщение
Использование stl считается недопустимым читом.
это факт, "а факты, как известно вещь упрямая".
Yandex
Объявления
07.12.2011, 02:43     Как описать абстрактный тип данных?
Ответ Создать тему
Опции темы

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