Это было очень важно, поскольку моделирование всевозможных реальных процессов становилось одной из основных областей применения ЭВМ. Моделирование приводило к абстракции, т.е. к упрощенному (или обобщенному) представлению объектов, их свойств и отношений в зависимости от поставленной задачи. Некоторые такие абстрактные объекты из-за своих полезных качеств стали необычайно «популярны». Они получили точную спецификацию и с тех пор стали называться абстрактными типами данных (или АТД). Однако абстракция на то и абстракция, чтобы абстрагироваться от многих несущественных факторов, в том числе и от того, как этот абстрактный объект представить в ЭВМ. Этим собственно и занялись языки программирования, которые, по сути, являются неким переходником между идеями человека и возможностями машины. И вот здесь как раз и пригодились вышеупомянутые структуры данных.
Структурные типы в Паскале
Массив
Массив – это одно- или многомерная таблица данных одного типа. Каждая ячейка таблицы имеет свой индекс (в одномерном случае) или набор индексов (в многомерном). Массив называют структурой данных со случайным доступом, поскольку к любому элементу массива можно обратиться, просто указав его индексы, т.е. все элементы одинаково доступны в любой момент времени. Массив определяется, прежде всего, общим типом его элементов и их количеством. Количество элементов массива, в свою очередь, определяется количеством индексов и диапазоном их изменения. При описании переменной типа массив под каждый элемент выделяется фиксированный объем памяти, что и является главным недостатком этой структуры, во-первых, потому что в некоторых системах программирования Паскаль под переменную выделяется ограниченное количество памяти, что не позволяет использовать массивы больших размеров, во-вторых, потому что такая организация не дает возможности изменять размер массива, что приводит к определенного рода неудобствам, когда приходится впустую копировать большие объемы памяти, например, при передаче параметра-массива подпрограмме.
Записи
Запись – связанная структура, состоящая из нескольких элементов (полей) разных (можно и одинаковых) типов. По сути, запись очень похожа на одномерный массив, но с элементами разных типов, кроме того, доступ к конкретному полю записи осуществляется уже не через индекс, а указанием идентификатора (т.е. имени) этого поля. Более того, в Паскале существует возможность менять тип конкретного поля в зависимости от ситуации. Такие структуры называются записями с вариантами. Правда, в любой записи может быть только одна вариантная часть, и, если она есть, ее описание должно располагаться за всеми фиксированными частями. Замечательная особенность вариантной части состоит в том, что все варианты как бы «накладываются» друг на друга, т.е. каждому из них выделяется одна и та же область памяти. Это открывает дополнительные возможности преобразования типов.
Файлы
Файл – динамическая структура данных, размер которой может меняться в процессе выполнения над ним каких-либо действий (он может быть равен нулю, что соответствует пустому файлу). Вообще-то, понятие файла используют и как абстракцию данных, хранящихся в памяти, что позволяет единообразно определить их общие характеристики и операции над ними. Однако свойства физического файла почти полностью совпадают со свойствами АТД файла, из-за чего абстракция в данном случае теряет весь смысл. Файл – структура, состоящая из последовательности компонент одного типа. Свойства последовательности определяет последовательный доступ к элементам, т.е. в каждый момент времени может быть доступен только один элемент файла. Основная операция над файлами – конкатенация (или слияние) файлов – позволяет создавать файлы неограниченной длины. Существует несколько видов файлов в Паскале. Текстовые файлы трактуются как последовательности строк переменной длины. В конце каждой строки ставится специальный признак конца строки EOLN. Типизированные файлы – последовательности компонент определенного типа. Длина любого элемента типизированного файла строго постоянна, что дает возможность организовать прямой доступ к каждому компоненту. В некоторых СП Паскаля это действие реализуется процедурой SEEK. Также, в отличие от текстовых файлов, здесь не работают процедуры READLN и WRITELN, поскольку нет нужды в переводе строки. Нетипизированные файлы объявляются предложением FILE и отличаются тем, что для них не указан тип компонент. Такой подход делает нетипизированные файловые переменные совместимыми с файлами любых типов, а также позволяет организовать высокоскоростной обмен данными между оперативной и внешней памятью. При инициации таких файлов процедурами RESET или REWRITE нужно указывать их длину в байтах, причем для достижения максимальной скорости обмена лучше, если эта длина кратна размеру физического сектора на внешней памяти.
Динамические структуры
Хотя динамика и не является отличительной чертой языка Паскаль, все же существует возможность создавать динамические объекты и оперировать с ними. Динамический объект представляет собой область памяти без идентификатора. Для обращения к этой области заводится специальная ссылочная переменная, которая описывается в программе. Элементами множества значений ссылочного типа являются значения адресов оперативной памяти. Чаще всего динамические структуры состоят из объектов, являющихся записями из нескольких полей, одна или несколько из которых являются ссылками на такой же объект. Таким образом можно составлять цепочки или более сложные структуры ссылающихся друг на друга объектов. Размер таких структур ограничивается только объемом свободной памяти и может легко меняться при удалении и создании объектов, что и определило основную область их применения – моделирование нелинейных последовательных структур данных (например, деревьев). Однако, несмотря на кажущееся отсутствие недостатков, динамические структуры тоже имеют свои минусы. Главный из них – отсутствие наглядности программы – вызывает трудности при создании особо крупных структур.
Представление абстрактных типов данных (АТД) в Паскале
Моделирование абстрактных типов данных на конкретных структурах данных Паскаля не является однозначным. Практически любой АТД может быть эффективным образом представлен как на массиве, так и на файле или на динамической структуре, но чаще всего конкретное представление диктуется особенностью доступа к элементам рассматриваемого абстрактного типа.
Стек
Стек – структура данных, представляющая собой последовательность элементов. Добавление и удаление элементов происходит только с одного конца последовательности, т.е. при изменении структуры предыдущая последовательность остается неизменной. Это значит, что по идее идеальной структурой представления для стека должен быть файл. Действительно, добавление элементов происходит только в конец файла, однако при удалении последнего элемента придется два раза переписывать весь файл, причем с подсчетом элементов. Это главный недостаток файла – для удаления компоненты требуется слишком много действий. С другой стороны время удаления элементов из файла не зависит ни от положения этого элемента в файле, ни от количества удаляемых элементов – это плюс! Стек на массиве позволяет уравнять время выполнения действий по добавлению и удалению элемента. Нужно всего лишь хранить в отдельной переменной длину последовательности и увеличивать ее или уменьшать соответственно при добавлении и удалении. Единственный недостаток такого представления – недостаток самого массива в Паскале – ограниченный размер, приводящий к переполнению стека. Использование динамических структур полностью решает эту проблему. В этом случае при добавлении и удалении элемента модифицируется только ссылка на начало цепочки динамических объектов, что снижает до минимума количество используемых для действия операторов. При этом размер стека почти неограничен.
Очередь, дек
Очередь – структура данных, как и стек представляющая собой последовательность элементов. Добавление элементов происходит с одной стороны последовательности, удаление – с другой. Дек – двусторонняя очередь, т.е. и добавление и удаление осуществляется с обеих сторон. Представление на файле этих АТД имеет такой же характер и «преимущества» как и у стека, т.е. переписывание файла происходит во всех случаях кроме добавления компоненты в его конец. Представление очередей и деков на массиве отличается тем, что последовательность элементов может «перемещаться» по массиву, следовательно, чтобы последовательность не выскочила за границы, нужно границы соединить вместе (зациклить). При этом индекс элементов (и первого и последнего) вычисляется как (x mod n), где n – размер массива. Проблемы все те же – возможность переполнения. Реализация на динамике использует ту же особенность (цикличность) и лучше всего представляется в виде кольцевого двунаправленного списка, о котором речь пойдет ниже.
Линейный список
Линейный список – одна из тех структур данных, которая если не приравнивается, то хотя бы ассоциируется с динамическими структурами. Он представляет собой упорядоченное множество (возможно пустое), в котором добавление и удаление элементов может происходить на любом месте списка. Элементы списков чаще всего представляют в виде записи, состоящей из поля информационной части и одного или двух полей-ссылок на другие узлы. Списки имеют последовательную структуру, т.е. для того чтобы перейти к какому-либо элементу, нужно пройти все элементы, предшествующие искомому. Причем если каждый элемент имеет ссылку только на следующий за ним элемент, то каждый такой проход нужно начинать с «головы» списка. Этот недостаток устраняется либо зацикливанием списка (ссылка последнего элемента указывает на первый) – в этом случае вообще теряются понятия начала и конца списка – либо использованием второй ссылки (на предыдущий элемент), чтобы можно было перемещаться в обе стороны. Представление списка на массиве является простым моделированием на массиве оперативной памяти. Элементом списка опять будет запись, состоящая из поля информационной части и поля, хранящего индекс следующего элемента в массиве (аналог ссылки). Для того чтобы смоделировать «кучу» свободной памяти, из которой берется память под новые объекты, создается список свободных элементов.
Линейные списки Pascal – курсовая работа
Деревья
Дерево – множество, состоящее из элемента, называемого корнем, и конечного (возможно пустого) множества деревьев, называемых поддеревьями данного дерева. Дерево, так же как и список, реализуется прежде всего на динамических структурах, т.е. узел дерева содержит два поля-ссылки – на левое и правое поддерево для двоичного дерева и на брата и старшего сына для дерева общего вида. Дерево уже не является линейной структурой, поэтому представление деревьев на последовательной памяти (файлах) представляет собой определенную проблему. Однако все данные хранятся во внешней памяти в виде файлов, поэтому решение этой проблемы необходимо. Тем не менее, сразу стоит оговориться, что это представление не будет в полной мере реализацией АТД дерева на структуре данных файле, поскольку требуется лишь создать обратимое отображение дерева в файл – никаких операций с файлом-деревом совершаться не будет. Создадим новый тип узла дерева (он станет компонентом файла) – запись информационного поля и поля, хранящего число поддеревьев данного узла. В файл будем последовательно записывать каждый узел так, чтобы поддеревья записывались после своего корня. Обратная операция производится с использованием рекурсии. Читаем из файла узел дерева, создаем его и ссылки на его поддеревья (столько, сколько указано в соответствующем поле). Затем для всех указанных поддеревьев повторяем ту же процедуру.
Дерево Pascal – лабораторная работа
Множества и деревья
Бинарное дерево называется упорядоченным, если для каждого его узла, имеющего поддеревья, корень больше левого поддерева и меньше правого. Используя упорядоченные бинарные деревья, можно легко реализовать математическое множество данных, для которого существует отношение порядка. При добавлении элемента нужно сохранить свойство упорядоченности, поэтому у добавляемого элемента существует единственное место в дереве (конечно, если такой элемент еще не присутствует в дереве). Проверка наличия элемента в дереве осуществляется тем же способом – переход от узла к узлу происходит по принципу максимального приближения к искомому значению. Если на том месте, где должен находиться искомый элемент, отсутствует поддерево, значит можно утверждать, что такого элемента нет во множестве.