- •А.Н. Горитов
- •Учебное пособие
- •Учебное пособие
- •Введение
- •1 Введение в предмет
- •1.1 Непрерывная и дискретная информация
- •1.2 Данные и эвм
- •1.3 Объекты предметной области
- •1.4 Представление информации об объектах
- •1.5 Абстрактные алфавиты. Кодирование
- •2 Основные типы и структуры данных эвм
- •2.1 Архитектурные особенности эвм, наиболее существенные для представления данных
- •2.2 Основные понятия о типах и структурах данных
- •2.3 Массивы
- •2.4 Строки
- •2.5 Записи
- •2.6 Записи с вариантами
- •2.7 Множества
- •3 Последовательный файл
- •3.1 Основные свойства последовательных файлов
- •3.2 Сортировка последовательных файлов
- •4 Полустатические структуры
- •4.1 Стек, очередь и дек как полустатические структуры
- •4.2 Представление полустатических структур с помощью массивов
- •5 Линейные динамические структуры
- •5.1 Основные свойства динамических структур
- •5.2 Реализация связного списка массивом
- •5.3 Кольцевой связный список
- •5.4 Линейный двусвязный список
- •6 Представление динамических структур с помощью указателей
- •6.1 Указатели
- •6.2 Представление стека
- •6.3 Представление очереди
- •6.4 Ведение динамических списков с помощью указателей
- •6.5 Алгоритм составления кольцевого двусвязного списка
- •7 Древовидные структуры данных
- •7.1 Основные понятия и определения
- •7.2 Представление деревьев в эвм
- •7.3 Основные операции с бинарными деревьями
- •7.4 Сильно ветвящиеся деревья
- •8 Алгоритмы на графах
- •8.1 Машинное представление графов
- •8.2 Поиск в глубину в графе
- •8.3 Поиск в ширину в графе
- •8.4 Стягивающие деревья (каркасы)
- •8.5 Отыскание фундаментального множества циклов в графе
- •8.6 Эйлеровы пути в графе
- •8.7 Алгоритмы с возвратом
- •8.8 Нахождение кратчайших путей в графе
- •8.9 Кратчайшие пути от фиксированной вершины
- •8.10 Алгоритм Дейкстры
- •8.11 Пути в бесконтурном графе
- •Литература
2.5 Записи
Дата рождения
Получение Экзамен стипендии
оценка
z—£
10
Г1..10,1..5"|
Ф
При обработке данных часто бывает необходимо собрать в одну коллекцию разнотипные данные. Для этого используются структурированные типы данных: записи – в Паскале, структуры – в Си. Например, информация о студентах (рис. 2).
Код |
/\ Гр. NOM Си Г N |
Рис. 2 Информация о студенте
Структура – иерархически упорядоченная коллекция данных. Важно не только то, что данные разных типов, но и что они располагаются на определенных уровнях. Элементами записей могут быть:
скалярные данные;
массивы;
записи. Различные составные типы могут комбинироваться различными способами.
Объявление записей
В Паскале составной структурированный тип – запись – определяется описанием типа.
TYPE T = RECORD
51 : T1;
52 : T2;
END;
Например, дата рождения
TYPE DAT = RECORD DEN : 1..31; MES : 1..12; GOD : 1950..2050 END; TYPE CODS = RECORD GR : RECORD
FAC, SP, GOD : CHAR; NOMG : 1..2 END;
NOM : INTEGER END;
Можно объявить тип записи TYPE STUDENT = RECORD
COD : CODS;
FIO : RECORD
FA, IM, OT : STRING[1..15];
END;
DR : DAT;
STIP : ARRAY[1..10] OF BOOLEAN;
EXAM : ARRAY[1..5] OF (0, 2, 3, 4, 5)
{ НЕ АТТ., НЕУД., УД., ХОР., ОТЛ. } END;
Теперь объявим переменные
VAR DECANAT : ARRAY[1..1000] OF STUDENT;
STUD : STUDENT;
FSTUD : FILE OF STUDENT;
Ограничений на типы полей в записи нет. Обращение к элементам записи осуществляется с помощью так называемых составных или квалифицированных имен, которые являются селекторами записи. Такой селектор состоит из имени записи и имен полей (подзаписей), однозначно определяющих элементарную компоненту записи. Имена разделяются точкой.
Например,
STUD.FIO.IM := 'БОРИС'; или
IF DEKANAT[I].STIP[4] THEN { получает } ELSE { нет } или
STUD := DEKANAT[274]; - пересылается вся запись из 274-го элемента массива DEKANAT в переменную STUD.
Заметим, что имя поля всегда указывается явно и в отличие от индекса в регулярном типе не может быть вычислено.
WITH - оператор присоединения
При работе с записями могут получиться слишком громоздкие тексты программ, т.к. обращаясь к элементам записи, вынуждены писать длинные имена, в которых одни и те же составляющие могут часто повторяться.
Сократить описание позволяет оператор присоединения, имеющий вид:
WITH R DO S, где WITH, DO – служебные слова; R – список имен записи (через запятую); S – любой оператор Паскаля.
Смысл: внутри оператора S имена полей записи можно использовать без префикса (имени записи и, возможно, имен старших подзаписей). Считается, что все они ссылаются на переменную R.
Например
WITH SDUT, FIO DO BEGIN
FA := 'Иванов';
IM := 'Петр';
OT :='Борисович' end;
Оператор
WITH R1, R2, ..., RN DO S эквивалентен WITH R1 DO
WITH R2 DO
WITH RN DO S; Запись и массив имеют общее свойство: оба являются структурами с произвольным доступом. Запись – более универсальная структура, т.к. не требуется, чтобы типы всех её компонент были одинаковыми.
С другой стороны, массив предоставляет большие возможности, поскольку селекторы его компонент могут вычисляться (если они представлены выражениями), тогда как селекторы компонент записи – это фиксированные идентификаторы, задаваемые в описании типа.