1.8. Абстрактные (определяемые пользователями) типы данных

Основной идеей АТД является то, что при его определении специфицируется не только структура значений типа, но и набор допустимых операций над переменными и значениями этого типа.

Имеется много разновидностей языков с АТД, языковые средства которых весьма различаются. Кроме того, к этому семейству языков примыкают языки объектно-ориентированного программирования.

1.8.1. Представление типа

При программировании с использованием АТД возможны три подхода (они могут быть смешаны): (1) перед началом написания основной программы полностью определить все требуемые типы данных; (2) определить только те характеристики АТД, которые требуются для написания программы и проверки ее синтаксической корректности; (3) воспользоваться готовыми библиотечными определениями.

Подобная внешняя характеристика АТД называется его представлением или спецификацией. Представление включает имя АТД и набор спецификаций доступных пользователю операций со значениями этого типа. Со своей стороны, спецификация операции состоит из имени и типов параметров (в последнее время такие спецификации принято называть сигнатурами операций). Переменные, используемые для внутреннего представления значений типа называются переменными состояния, а их совокупность состоянием значений.

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

1.8.2. Реализация типа

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

1.8.3. Инкапсуляция

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

1.8.4. Наследование типов

Под наследованием типов понимается возможность создания новых типов на основе уже определенных.

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

1.8.5. Разновидности полиморфизма

Можно выделить две разновидности полиморфных операций: (1) одноименные операции одного или нескольких типов, различающиеся сигнатурами, и (2) операции с общей сигнатурой, определяемые и переопределяемые в иерархии наследования типов.

Записи

Запись – это структура данных, состоящая из фиксированного числа компонентов, называемых полями записи. В отличие от массива, компоненты (поля) записи могут быть различного типа. Чтобы можно было ссылаться на тот или иной компонент записи, поля именуются.

Структура обьявления типа записи такова:

= RECORD END

RECORD, END – зарезервированные слова (запись, конец);

- список полей; представляют собой последовательность разделов записи, между которыми ставится точка с запитой. Каждый раздел записи состоит из одного или нескольких индификаторов полей, отделяемых друг от друга запятыми. За индификатором ставится двоеточие и описание типа поля например:

type

birthday = record

day, month : byte;

year : word:

end;

var

a,b : Birthday;

. . . . . . . .

В этом примере тип Birthday есть запись с полями DAY, MONTH, и YEAR; переменные А и В содержат записи типа Birthday.

Как в массиве, значения переменных типа записи можно присваивать другим переменным того же типа, например:

a : = b;

К каждому из компонентов записи можно получить доступ, если использовать составное имя, т.е. указать имя переменной, затем точку и имя поля:

a.day := 27; b.year := 1991;

Чтобы упростить доступ к полям записи, используется оператор присоединения WITH: WITH DO.

Здесь WITH, DO – ключевые слова (с, делать);

Например:

with c.bd do month := 9;

Файлы

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

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

Типизированный файл в Паскале интерпретируется как последовательность (список) значений определенного (одного и того же) базового типа. Например, если в файле на диске хранится список вещественных чисел, то переменная в языке Pascal, через которую можно получить к ним доступ, может быть описана так:

f: file of real;

Файловый тип определяется служебными словами file of, далее идет указание базового типа, который может быть любым, кроме файлового.

Тут следует понимать такую особенность. В файле могут храниться числа, но в pascal-программе они могут быть интерпретированы как символы или строки. Все зависит от выбранного базового типа при определении файловой переменной. Возможны разные ситуации.

При определении переменной файлового типа также в программе появляется скрытый (неявный) текущий указатель файла. Его назначение – указывать на конкретный элемент файла (обеспечивать доступ к нему).

В языке программирования Паскаль все действия с файлом (чтение, запись) производятся поэлементно. Действия совершаются именно над тем элементом файла, на который указывает текущий указатель файла. После того как действие будет завершено, указатель перемещается к следующему элементу. Все элементы файла пронумерованы, начиная с нуля.

Операции с файловыми переменными включают:

• установочные и завершающие операции;

• ввод и вывод;

• перемещение по файлу;

• специальные операции.

Создание файла

Процедура assign обеспечивает связь файловой переменной программы с реальным файлом на диске. Первым аргументом указывается переменная, вторым – адресное имя файла.

Процедура rewrite открывает файл в режиме записи, т.е. мы можем вводить данные в файл с помощью процедуры вывода из программы write. Если указанный файл отсутствует на диске, то он будет создан. Если файл существует и содержит данные, то все они будут удалены и заменены в дальнейшем новыми (перезаписаны).

Запись данных в файл – результат выполнения процедуры write (f, c), где f – файловая переменная, а с – выводимый из программы, но вводимый в файл символ.

В конце требуется закрыть файл и «освободить» переменную f. Это делается с помощью процедуры close.

Типизированные файлы

Более характерным для Pascal являются типизированные файлы, или файлы произвольного доступа. Основным свойством этих файлов является то, что их структура данных представляет собой последовательность компонентов одного типа. Описывают подобный файл словосочетанием file of с последующим указанием типа компонентов файла, число которых (длина файла) не фиксируется:

var имя_файла: file of тип_компонентов

Поскольку известен тип элементов файла, а следовательно, и объем памяти, отводимой под каждый из них, можно рассчитать позицию каждого из элементов внутри файла. Это позволяет организовать непосредственный доступ к любому элементу типизированного файла.

Нетипизированные файлы

В Pascal, кроме рассмотренных, существуют также нетипизированные файлы. Они совместимы со всеми типами файлов и используются тогда, когда тип элементов файла не важен (например, при копировании). Такие файлы описываются следующим образом:

var имя_файла: file;

Например, возможно такое описание:

var FileOneType: file;

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

Списки: основные виды и способы реализации

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

Однонаправленный (односвязный) список

Элементом является структура, в число полей которой входит поле адреса, в котором хранится ссылка на следующий элемент односвязного списка, относят данную структуру хранения к связным, и поле данных, содержащее информацию, предназначенную для хранения.

Связанный список определяется адресом начала (головы списка), конец списка определяется элементом, в поле адреса которого хранится значение, не ссылающееся ни на какую область памяти (NULL)

Создание связного списка.

Выделить память для хранения адреса головы;

Выделить память для хранения элементов списка;

Обнулить поле адреса;

Записать в поле данных содержащую информацию;

Сохранить адрес головы списка в переменной, хранящей ссылку на начало списка.

Добавление элемента в конец списка.

Присвоить указателю адрес головы списка;

Проанализировать значение поля адреса. Пока оно не равно 0, присваивать указателю значение поля адреса.

Создать элемент списка и записать его в поле адрес конца списка.

Добавление элемента в произвольное место списка.

Найти заданный элемент, сохранить значение его поля адреса, создать новый элемент, записать адрес нового элемента в поле адреса заданного (найденного) элемента.

Записать в поле адреса добавляемого элемента сохраненный адрес следующего элемента.

Процедура добавления элемента в произвольное место списка показывает преимущество связного хранения перед последовательным (массивы).

Удаление элемента из конца списка.

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

Удаление произвольного элемента связного списка.

Найти удаляемый элемент, сохранить его адрес. В поле адреса предыдущего элемента записать адрес следующего. Освободить память из-под удаляемого элемента.

Кольцевой односвязный список

Структура аналогична структуре односвязного однонаправленного списка, за исключением того, что в поле адреса конечного элемента хранится адрес головы списка.

Все процессы взаимодействия со списком аналогичны вышеописанным, за исключением того, что проверка на конец списка осуществляется не с NULL, а со значением адреса головы списка.

Двунаправленный список

Каждый элемент списка содержит адрес не только следующего элемента, но и предыдущего. Голова списка в адресе предыдущего элемента содержит NULL.

Кольцевой двунаправленный список

Поле предыдущий элемент головы списка содержит адрес конца списка.

Двусвязный список

Каждый элемент списка содержит 2 ссылки на 2 следующих элемента.

Двунаправленный (двусвязный) список

Элемент такого списка помимо ссылки на  левый и правый следующие элементы содержит ссылку на предыдущий элемент.

Многосвязный список

Каждый элемент содержит n-ссылок на следующие элементы.

ТЕОРИЯ СИСТЕМ И СИСТЕМНЫЙ АНАЛИЗ

http://www.tstu.ru/education/elib/pdf/2008/chernyshov.pdf