37. Структуры данных. Списковые структуры данных.

Стуктуры данных. Структурные типы в Паскале.

Массив
Массив – это одно- или многомерная таблица данных одного типа. Каждая ячейка таблицы имеет свой индекс (в одномерном случае) или набор индексов (в многомерном). Массив называют структурой данных со случайным доступом, поскольку к любому элементу массива можно обратиться, просто указав его индексы, т.е. все элементы одинаково доступны в любой момент времени. Массив определяется, прежде всего, общим типом его элементов и их количеством. Количество элементов массива, в свою очередь, определяется количеством индексов и диапазоном их изменения. При описании переменной типа массив под каждый элемент выделяется фиксированный объем памяти, что и является главным недостатком этой структуры, во-первых, потому что в некоторых системах программирования Паскаль под переменную выделяется ограниченное количество памяти, что не позволяет использовать массивы больших размеров, во-вторых, потому что такая организация не дает возможности изменять размер массива, что приводит к определенного рода неудобствам, когда приходится впустую копировать большие объемы памяти, например, при передаче параметра-массива подпрограмме.

Записи
Запись – связанная структура, состоящая из нескольких элементов (полей) разных (можно и одинаковых) типов. По сути, запись очень похожа на одномерный массив, но с элементами разных типов, кроме того, доступ к конкретному полю записи осуществляется уже не через индекс, а указанием идентификатора (т.е. имени) этого поля. Более того, в Паскале существует возможность менять тип конкретного поля в зависимости от ситуации. Такие структуры называются записями с вариантами. Правда, в любой записи может быть только одна вариантная часть, и, если она есть, ее описание должно располагаться за всеми фиксированными частями. Замечательная особенность вариантной части состоит в том, что все варианты как бы «накладываются» друг на друга, т.е. каждому из них выделяется одна и та же область памяти. Это открывает дополнительные возможности преобразования типов.

Файлы
Файл – динамическая структура данных, размер которой может меняться в процессе выполнения над ним каких-либо действий (он может быть равен нулю, что соответствует пустому файлу). Вообще-то, понятие файла используют и как абстракцию данных, хранящихся в памяти, что позволяет единообразно определить их общие характеристики и операции над ними. Однако свойства физического файла почти полностью совпадают со свойствами АТД файла, из-за чего абстракция в данном случае теряет весь смысл. Файл – структура, состоящая из последовательности компонент одного типа. Свойства последовательности определяет последовательный доступ к элементам, т.е. в каждый момент времени может быть доступен только один элемент файла. Основная операция над файлами – конкатенация (или слияние) файлов – позволяет создавать файлы неограниченной длины. Существует несколько видов файлов в Паскале. Текстовые файлы трактуются как последовательности строк переменной длины. В конце каждой строки ставится специальный признак конца строки EOLN. Типизированные файлы – последовательности компонент определенного типа. Длина любого элемента типизированного файла строго постоянна, что дает возможность организовать прямой доступ к каждому компоненту. В некоторых СП Паскаля это действие реализуется процедурой SEEK. Также, в отличие от текстовых файлов, здесь не работают процедуры READLN и WRITELN, поскольку нет нужды в переводе строки. Нетипизированные файлы объявляются предложением FILE и отличаются тем, что для них не указан тип компонент. Такой подход делает нетипизированные файловые переменные совместимыми с файлами любых типов, а также позволяет организовать высокоскоростной обмен данными между оперативной и внешней памятью. При инициации таких файлов процедурами RESET или REWRITE нужно указывать их длину в байтах, причем для достижения максимальной скорости обмена лучше, если эта длина кратна размеру физического сектора на внешней памяти.

Динамические структуры
Хотя динамика и не является отличительной чертой языка Паскаль, все же существует возможность создавать динамические объекты и оперировать с ними. Динамический объект представляет собой область памяти без идентификатора. Для обращения к этой области заводится специальная ссылочная переменная, которая описывается в программе. Элементами множества значений ссылочного типа являются значения адресов оперативной памяти. Чаще всего динамические структуры состоят из объектов, являющихся записями из нескольких полей, одна или несколько из которых являются ссылками на такой же объект. Таким образом можно составлять цепочки или более сложные структуры ссылающихся друг на друга объектов. Размер таких структур ограничивается только объемом свободной памяти и может легко меняться при удалении и создании объектов, что и определило основную область их применения – моделирование нелинейных последовательных структур данных (например, деревьев). Однако, несмотря на кажущееся отсутствие недостатков, динамические структуры тоже имеют свои минусы. Главный из них – отсутствие наглядности программы – вызывает трудности при создании особо крупных структур.

Hosted by uCoz