Начало
Учебные материалы
Этапы решения алгоритмической задачи. Базовые структуры данных
Этапы решения алгоритмической задачи Важные типы задач Линейные структуры данных Графы Деревья Множества и словари
Множества и словари
Конкретное множество можно задать либо в виде явного списка элементов (например, `S ={2,3,5,7}`),
либо в виде указания условия, которому должны удовлетворять все элементы множества и только они (например,
`S ={n| n — "простое число" ^^ n< 10})`.
--
Если множество `U` состоит из `n` элементов,
то любое его подмножество `S` можно представить в виде строки из `n` битов, в
которой `i`-й элемент равен 1 тогда и только тогда, когда `i`-й элемент множества
`U` включен в подмножество `S`. Например, если
`U ={1,2,3,4,5,6,7,8,9}`, то подмножество `S ={2,3,5,7}` можно представить
в виде битовой строки 011010100.
Описанный способ представления множеств
позволяет реализовать стандартный набор операций над множеством в виде очень
быстрых процедур. Однако платой за скорость является большой объем
оперативной памяти, необходимой для представления элементов множества.
--
Следующий способ заключается в представлении элементов множества
в виде списка. При этом важно понимать отличия между списком и множеством:
* в множестве не может быть одинаковых элементов, а в списке — может (но в *мультимножестве* элементы не обязательно различны);
* изменение порядка элементов множества не изменяет само множество, а список определяется как упорядоченный набор элементов
В том случае, когда множество представляется в виде списка, его элементы обычно отсортированы по возрастанию.
В алгоритмах над множеством (мультимножеством) чаще всего выполняются следующие операции:
поиск заданного элемента, добавление нового элемента и удаление элемента из совокупности.
Третьим способом является двоичное дерево поиска.
--
*Словарь* (*ассоциативный массив*, отображение) обобщает структуры данных множество и массив и позволяет хранить пары вида (ключ, значение).
К основным операциям над словарем относятся: добавления пары, поиска и удаления пары по ключу.
Для словарей можно использовать массивы, связные списки и двоичные деревья поиска.
---
##### Задания для практики
1. Предложите, как можно реализовать каждую из перечисленных ниже операций над последовательностями так, чтобы время ее выполнения не зависело от размера `n`.\
а) Замена i-го элемента\
б) Удаление i-го элемента (один раз, многократно)\
в) Добавление в конец последовательности\
г) Добавление в начало последовательности\
д) Добавление после указанного элемента\
Как это может повлиять на последующие действия с последовательностью (например, проход по всех элементам последовательности)?
2. Каким будет содержимое стека после выполнения каждой команды приведенной ниже последовательности, считая, что в исходном состоянии стек пуст:\
push (a), push(b), pop, push(с), push(d), pop.
3. Изобразите содержимое очереди после выполнения каждой команды приведенной ниже последовательности, считая, что в исходном состоянии очередь пуста:\
enqueue(a), enqueue(b), dequeue, enqueue(с), enqueue(d), dequeue.
4. Как бы вы реализовали словарь, содержащий достаточно малое количество элементов `n`, при условии, что все его элементы различны (например, представляют собой названия 50 штатов США)? Опишите реализацию каждой операции, выполняемой словарем.
