Курс лекций мдк 01. 02 «Прикладное программирование» пм 01 «Разработка программных модулей программного обеспечения для компьютерных систем»

Тема «Классы коллекций. Линейные коллекции. Коллекции с прямым доступом. Нелинейные коллекции»


Коллекции представляют собой организацию данных и определяют методы доступа к этим данным. Коллекции подразделяются на две категории: линейные и нелинейные. Линейная коллекция содержит список элементов, упорядоченных по положению. В этом списке имеется первый элемент, второй и т.д. Массив с индексом, отражающим порядок элементов является основным примером линейной коллекции.


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


Коллекции с прямым доступом


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


Запись – это базовая структура коллекций для сохранения данных, которые могут состоять из разных типов. Для многих программ различные элементы данных ассоциированы с одним объектом. Например авиабилет включает такие данные, как номер рейса, номер места, имя пассажира, стоимость. Запись связывает поля структуры данных при обеспечении прямого доступа к данным в отдельных полях.
38
Коллекции с последовательным доступом

Более общей коллекцией является список, сохраняющий элементы в определенном порядке. Структура, называемая линейным списком содержит произвольное число элементов. Размер списка изменяется, после удаления и добавления к нему новых элементов. Первый элемент находится в начале или голове списка, а последний – в хвосте списка. Каждый элемент списка имеет связь с последующим, таким образом можно передвигаться от одного элемента к другому. Для доступа к элементам списка необходимо выполнять прохождение от головы до нужной позиции. Если движение по списку можно осуществлять только в одном направлении, то список называется однонаправленным, если в двух направлениях – двунаправленный. Если элемент списка хранит информацию об одном “соседе”, то список называется односвязным, если о двух – двусвязным.

Стеки и очереди – особые версии линейного списка с ограниченным доступам к элементам данных. В стеке элементы добавляются и удаляются через один конец списка, называемым вершиной. Операция удаления элемента называется извлечением из стека, операция добавления называется помещением элемента в стек. При помещении элемента в стек все остальные элементы опускаются вниз, уступая место на вершине новому элементу. Когда элемент удаляется, остальные перемещаются в обратном порядке. Последний элемент, помещенный в стек, является первым извлекаемым.


Очередь – это список с доступом в начало и конец. Элементы вставляются в конец, а извлекаются из начала списка. Иногда используются очереди приоритетов. В них добавление новых элементов происходит в конец, а удаление – из произвольного места согласно приоритету.

В машинной системе файл – это коллекция, имеющая

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