ЛЕКЦИЯ 6. ДЕК. РАЗРЕЖЕННЫЕ МАТРИЦЫ


 

Цель лекции.

1. Рассмотреть принципы реализации дека.

2.Ознакомиться с основными принципами организации данных для хранения и работы с разреженными матрицами,

Основные рассматриваемые вопросы:дек, матрицы с математическим описанием местоположения элементов, Матрицы со случайным расположением элементов.

Продолжим рассмотрение динамических структур.

Дек - это структура данных, представляющая собой последовательность элементов, в которой можно добавлять и удалять в произвольном порядке элементы с только с двух сторон. Первый и последний элементы дека соответствуют входу и выходу дека.

 

 


 

Выделяют ограниченные деки:

- дек с ограниченным входом - из конца дека можно только извлекать элементы;

- дек с ограниченным выходом - в конец дека можно только добавлять элементы.

Данная структура является наиболее универсальной из рассмотренных выше линейных структур. Накладывая дополнительные ограничения на операции с началом и/или концом дека, можно осуществлять моделирование стека и очереди.

Дек также можно реализовывать как статическую структуру данных в виде одномерного массива, а можно как динамическую структуру - в виде линейного списка

Поскольку в деке, как и в очереди, осуществляется работа с обоими концами структуры, то целесообразно использовать те же подходы к организации дека, что применялись и для очереди

Описание элементов дека аналогично описанию элементов линейного двунаправленного списка, где DataType является типом элементов дека. Поэтому здесь приводить его не будем. Но, как и для очереди, введем дополнительно два указателя на начало и конец дека:

Основные операции, производимые с деком:

- добавить элемент в начало;

- добавить элемент в конец;

- извлечь элемент из начала;

- извлечь элемент из конца;

- очистить дек;

- проверка пустоты дека.

 


 

 

Применение динамических структур данных рассмотрим на примере организации

разреженных матриц.

 



Дата добавления: 2018-05-10; просмотров: 1056;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.007 сек.