Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
0 / 0 / 0
Регистрация: 01.06.2017
Сообщений: 31
1

Как можно реализовать такую структуру?

22.07.2017, 16:30. Показов 415. Ответов 13
Метки нет (Все метки)

Реализовать структуру данных, которая имеет все те же операции, что массив длины n, а именно
• начать работу;
• положить в i-ю ячейку число x;
• узнать, что лежит в i-ой ячейке;
а также операцию
• указать номер минимального элемента
(точнее, одного из минимальных элементов). Количество действий для
всех операций должно быть не более C log n, не считая операции начать
работу (которая требует не более Cn действий).

Мне известно что это можно решить с помощью бинарного дерева, но не понятно как потом вызывать i-й элемент из этого дерева. подскажите пожалуйста
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
22.07.2017, 16:30
Ответы с готовыми решениями:

Как создать структуру-список, поля которой — ссылка на такую же структуру
Суть вопроса в том, как создать структуру-список, поля которой - ссылка на сл. элемент(такую же...

Можно ли реализовать такую программу на C++
Программа должна делить ip адреса например вот список ip адресов 5.44.216.0-5.44.223.255...

Как реализовать такую сортировку??
У меня имеется структура данных, я хочу ввести месяц, а мне чтобы вывелись люди, у которых в этом...

Как реализовать структуру?
Есть две структуры студент и комната в которой он проживает. Как лучше реализовать ситуацию?...

__________________

Записывайтесь на профессиональные курсы C++ разработчиков
13
353 / 134 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
22.07.2017, 17:58 2
Дерамида по неявному ключу
0
0 / 0 / 0
Регистрация: 01.06.2017
Сообщений: 31
23.07.2017, 10:36  [ТС] 3
Ромаха, Посмотрел дермиду и что-то я засомневался что мне это подходит. Там есть только добавление элемента с увеличением размеров массива, а мне это не нужно по заданию.

Я смотрел пояснения к этой задаче там написано такое : "Для решения задачи используется приём, изложенный в разделе о сортировке деревом. Именно, надстроим над элементами массива как над листьями двоичное дерево, в каждой вершине которого храним минимум элементов соответствующего поддерева. Корректировка этой информации, а также прослеживание пути из корня к минимальному элементу требуют логарифмического числа действий."
0
353 / 134 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
23.07.2017, 16:25 4
Не. Как раз подходит.
Только я проглядел..

На самом деле Вам подойдет все что угодно.
Дерево отрезков (самое простое, как по мне), бинарное, дерамида (это интереснее, но сложнее)
0
0 / 0 / 0
Регистрация: 01.06.2017
Сообщений: 31
23.07.2017, 16:43  [ТС] 5
Ромаха, Хотелось бы максимально просто сделать. А как обратиться к какому то конкретному элементу по индексу допустим в двоичном дереве? Ведь при добавлении дерево автоматически сортируется по значению и я теряю этот элемент из виду. И даже если я положу элемент в какую то ячейку по индексу, сразу после добавления дерево опять нормализуется и этот элемент будет в другом месте. Как реализовать доступ по индексу?
0
353 / 134 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
23.07.2017, 16:52 6
тыц
0
0 / 0 / 0
Регистрация: 01.06.2017
Сообщений: 31
23.07.2017, 16:57  [ТС] 7
Ромаха, но вы же скинули ссылку на поиск по значению, а мне надо по индексу
0
353 / 134 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
23.07.2017, 17:09 8
А. Ну дык заведите массивчик. В нем изменяйте элементы, а потом зная старое и новое значение, все исправьте.
0
0 / 0 / 0
Регистрация: 01.06.2017
Сообщений: 31
23.07.2017, 17:11  [ТС] 9
Ромаха, ещё один массив?
0
353 / 134 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
23.07.2017, 18:00 10
Ага.
Хотите без - пишите до (которое нерекурсивное).
Min - O(1)
Элементы можно менять за O(log)
Достать значение элемента O(1)


Или украв идею у ДО можно сделать подобное деревом поиска, где ключами будет индекс элемента. А вторым (дополнительным) параметром будет значение минимума на поддереве
Минимум за O(1)
Достать элемент за лог.
Изменить элемент за лог.
0
0 / 0 / 0
Регистрация: 01.06.2017
Сообщений: 31
23.07.2017, 18:08  [ТС] 11
Ромаха, " Или украв идею у ДО " У кого украв идею?
0
353 / 134 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
23.07.2017, 18:10 12
Дерево отрезков.
0
0 / 0 / 0
Регистрация: 01.06.2017
Сообщений: 31
23.07.2017, 18:20  [ТС] 13
Ромаха, А если в дереве поиска ключами будет индекс элемента то оно будет сортироваться по индексу или по значению?
0
353 / 134 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
23.07.2017, 20:45 14
Цитата Сообщение от Степан174174 Посмотреть сообщение
Ромаха, А если в дереве поиска ключами будет индекс элемента то оно будет сортироваться по индексу или по значению?
Индекс
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
23.07.2017, 20:45

Заказываю контрольные, курсовые, дипломные работы и диссертации здесь.

Как реализовать структуру
Доброго времени суток. Никак не могу скомпиллировать эту структуру. struct tree{ char inf;...

Как лучше реализовать структуру класса?
Есть задача создать класс авто-архив. Класс реализовал со структурой внутри класса. Создал...

Реализовать структуру моделирующую работу аэропорта; реализовать поиск по заданному полю в массиве таких структур
Здравствуйте. Каким образом можно сделать ввод данных через массив, а так же все последующие...

Как можно динамическую структуру стек преобразовать в класс со стеком?
Добрый день, у меня возник вопрос. как можно динамическую структуру стэк преобразовать в классы со...


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

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Опции темы

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