ЛЕКЦИЯ 6. ДЕК. РАЗРЕЖЕННЫЕ МАТРИЦЫ
Цель лекции.
1. Рассмотреть принципы реализации дека.
2.Ознакомиться с основными принципами организации данных для хранения и работы с разреженными матрицами,
Основные рассматриваемые вопросы:дек, матрицы с математическим описанием местоположения элементов, Матрицы со случайным расположением элементов.
Продолжим рассмотрение динамических структур.
Дек - это структура данных, представляющая собой последовательность элементов, в которой можно добавлять и удалять в произвольном порядке элементы с только с двух сторон. Первый и последний элементы дека соответствуют входу и выходу дека.
Выделяют ограниченные деки:
- дек с ограниченным входом - из конца дека можно только извлекать элементы;
- дек с ограниченным выходом - в конец дека можно только добавлять элементы.
Данная структура является наиболее универсальной из рассмотренных выше линейных структур. Накладывая дополнительные ограничения на операции с началом и/или концом дека, можно осуществлять моделирование стека и очереди.
Дек также можно реализовывать как статическую структуру данных в виде одномерного массива, а можно как динамическую структуру - в виде линейного списка
Поскольку в деке, как и в очереди, осуществляется работа с обоими концами структуры, то целесообразно использовать те же подходы к организации дека, что применялись и для очереди
Описание элементов дека аналогично описанию элементов линейного двунаправленного списка, где DataType является типом элементов дека. Поэтому здесь приводить его не будем. Но, как и для очереди, введем дополнительно два указателя на начало и конец дека:
|
|
|
Основные операции, производимые с деком:
- добавить элемент в начало;
- добавить элемент в конец;
- извлечь элемент из начала;
- извлечь элемент из конца;
- очистить дек;
- проверка пустоты дека.
Применение динамических структур данных рассмотрим на примере организации
разреженных матриц.
Разреженные матрицы
Разреженная матрица - двухмерный массив, большинство элементов которого равны между собой, так что хранить в памяти достаточно лишь небольшое число значений, отличных от основного (фонового) значения остальных элементов.
Различают два типа разреженных матриц:
1) матрицы, в которых местоположения элементов со значениями,
отличными от фонового, могут быть математически описаны;
2) матрицы со случайным расположением элементов.
В случае работы с разреженными матрицами вопросы размещения их в памяти реализуются с учетом их типа.
Матрицы с математическим описанием местоположения элементов
|
|
|
К данному типу матриц относятся матрицы, у которых местоположение элементов со значениями, отличными от фонового, может быть математически описано, т. е. в их расположении есть какая-либо закономерность.
Элементы, значения которых являются фоновыми, называют нулевыми, а элементы, значения которых отличны от фонового, называют ненулевыми. Но необходимо помнить, что фоновое значение не всегда равно нулю.
Ненулевые значения хранятся, как правило, в одномерном массиве (векторе), а связь между местоположением в разреженной матрице и в новом, одномерном, описывается математически с помощью формулы, преобразующей индексы матрицы в индексы вектора.
На практике для работы с разреженной матрицей разрабатываются функции:
1) для преобразования индексов матрицы в индекс вектора;
2) для получения значения элемента матрицы из ее упакованного представления по двум индексам (строка, столбец);
3) для записи значения элемента матрицы в ее упакованное представление по двум индексам.
При таком подходе обращение к элементам матрицы выполняется с помощью указанных функций. Например, пусть имеется двумерная разреженная матрица, в которой все ненулевые элементы расположены в шахматном порядке, начиная со второго элемента. Для такой матрицы формула вычисления индекса элемента в линейном представлении будет следующей:
Дата добавления: 2018-05-02; просмотров: 847; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!