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

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

Войти
Регистрация
Восстановить пароль
 
Soup_990
0 / 0 / 0
Регистрация: 16.11.2011
Сообщений: 34
#1

Дек в виде массива - C++

24.12.2012, 00:14. Просмотров 1064. Ответов 4
Метки нет (Все метки)

Подскажите как реализовать дек в виде массива.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.12.2012, 00:14
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Дек в виде массива (C++):

Вернуть все четные числа массива в виде нового массива - C++
Функция должна вернуть все четные числа массива в виде нового массива. int *f2 (int *mas,int N) { int size=0; for(int i=0;...

Найти столбец массива с наибольшей суммой элементов и записатьегох в виде одномерного массива - C++
1 Для произвольного двумерного массива найти столбец с наибольшей суммой элементов и записать их в виде одномерного массива.

Удалить из массива A[N] вс отрицательные элементы.Удаление отрицательных элементов массива оформить в виде функции - C++
Что исправить? #include <stdio.h> #define N 10 int udalenie(int A,int k ) { int i; for(i=k;i<N;i++)

Простой список в виде массива.Как работать с элементами списка-массива через единую функцию - C++
Добрый день!Подсобите,как реализовать Простой список,но не через шаблоны или создание указателей,а как бы в виде массива.(Ну,или ваш...

Дан массив А. Образовать реверс массива А в массиве В. Вывести оба массива и индексы элементов на экран в виде трех столбцов. - C++
Дан массив А. Образовать реверс массива А в массиве В. Вывести оба массива и индексы элементов на экран в виде трех столбцов.

дек - C++
как сделать такую вещь? реализовать и протестировать контейнерный класс динамической структуры данных такой как дек. класс должен иметь...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Croessmah
Эксперт CЭксперт С++
13205 / 7476 / 839
Регистрация: 27.09.2012
Сообщений: 18,373
Записей в блоге: 3
Завершенные тесты: 1
24.12.2012, 00:17 #2
В смысле так?
Дек в виде массива
0
OhMyGodSoLong
~ Эврика! ~
1243 / 992 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
24.12.2012, 08:11 #3
Это всё же развёрнутый список.

А массив это обычно циклический буфер. Представляете себе, как реализуется тот же вектор на массиве? Есть массив, слева в нём элементы вектора, справа незанятое пространство. Элементы добавляются слева направо, начиная с нулевого.

Вот для дека надо эту точку добавления сдвинуть к центру массива. Тогда незанятое пространство в массиве будет с обеих сторон от блока с содержимым дека. Соответственно, можно быстро добавлять-удалять элементы из начала-конца, так как место есть и сдвигать элементы не придётся.

Также буфер циклический. К примеру, если мы будем добавлять постоянно элементы в начало, то они будут добавляться в левую незанятую половину. Но как только она заполнится, то мы не изменяем размер буфера, а продолжаем добавлять элементы уже с правого конца правой половины свободного пространства. Размер изменяется только тогда, когда весь буфер заполнен.
0
Avazart
Эксперт С++
7185 / 5359 / 280
Регистрация: 10.12.2010
Сообщений: 23,650
Записей в блоге: 17
24.12.2012, 14:35 #4
Цитата Сообщение от ~OhMyGodSoLong~ Посмотреть сообщение
Вот для дека надо эту точку добавления сдвинуть к центру массива. Тогда незанятое пространство в массиве будет с обеих сторон от блока с содержимым дека. Соответственно, можно быстро добавлять-удалять элементы из начала-конца, так как место есть и сдвигать элементы не придётся.
Как я помню в деке нет перераспределения памяти, поэтому такой вариант не канает думаю.

Думаю нужно нечто вроде std::vector<T*> где T* указатели на массивы, естественно нужен будет хитрый итератор
0
OhMyGodSoLong
~ Эврика! ~
1243 / 992 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
24.12.2012, 15:43 #5
Цитата Сообщение от Avazart Посмотреть сообщение
Как я помню в деке нет перераспределения памяти, поэтому такой вариант не канает думаю.

Думаю нужно нечто вроде std::vector<T*> где T* указатели на массивы, естественно нужен будет хитрый итератор
Дек — это вообще АТД; вопрос, где взять память, не относится к деку как таковому. Если брать реализацию, то да, вообще циклический буфер не особо подходит из-за этих перемещений, поэтому обычно реализуют (в STL по крайней мере так) именно как развёрнутый список: делается двусвязный список блоков, в каждом из которых хранятся два указателя, массив данных и число занятых элементов в массиве (количество элементов в массиве в идеале такое, чтобы весь блок влез в кеш-линию). Для дека можно число элементов выкинуть из блока и хранить просто два числа: заполненности двух крайних блоков; это потому, что в деке нельзя вставлять в середину, а только по краям, так что неполными могут быть только крайние блоки.

Но, просто, я так понял, что надо именно в одном массиве.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.12.2012, 15:43
Привет! Вот еще темы с ответами:

Шаблонный дек - C++
Задача реализовать шаблонный класс дека, и класс Итератора для навигации по деку. До добавления шаблонов все хорошо работало. Ныне такие...

Дек-шаблон - C++
Доброй ночи. У меня вопрос. Я хочу реализовать дек, а потом на его основе сделать шаблон. В деке могут храниться как числа, так и...

Простой дек - C++
Помогите решить задачу : Реализуйте структуру данных &quot;дек&quot;. Напишите программу, содержащую описание дека и моделирующую работу дека,...

Дек символов - C++
Доброго времени суток всем. У меня такая проблема: есть задача - Реализовать класс &quot;Дек символов&quot; (на базе списка). Реализовать...


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

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

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