- •Содержание
- •Введение
- •Структуры данных Классификация структур данных
- •Операции над данными
- •Понятие алгоритма
- •Массивы Описание массива
- •Представление массивов в памяти
- •Рис 1. Представление вектора в памяти
- •Рис 2. Представление вектора ml в памяти
- •Алгоритмы поиска
- •Алгоритмы сортировки
- •Пример сортировки простыми вставками.
- •Описание записи
- •Операции над записями
- •Записи с вариантами
- •Представление записи в памяти
- •Общие процедуры и функции для работы с файлами
- •Процедуры и функции для работы с типизированными файлами.
- •Сортировка содержимого файлов (Внешняя сортировка)
- •Пример внешней сортировки прямым слиянием
- •Пример внешней сортировки естественным слиянием
- •Динамическая память и данные с динамической структурой
- •Ссылочный тип в языке Pascal
- •Типизированные указатели
- •Нетипизированные указатели
- •Операции над переменными ссылочного типа.
- •Динамические списки
- •Реализация списков на языке Pascal.
- •Стек, очередь, дек
- •Рекурсия
- •Нелинейные структуры данных. Деревья
- •Бинарные деревья
- •Реализация бинарных деревьев
- •Способы обхода бинарных деревьев
- •Сортировка с прохождением бинарного дерева
Представление записи в памяти
В памяти эта структура представлена в виде последовательности полей, занимающих непрерывную область памяти. При такой организации достаточно иметь один указатель на начало области и смещение относительно начала. Это дает экономию памяти, но лишнюю трату времени на вычисление адресов полей записи.
Под переменную записного типа отводиться объём памяти, равный сумме объемов полей, описанных в записи.
Особенность вариантной части записи заключается в том, что каждому из вариантов выделяется одна и та же область памяти.
Память распределяется следующим образом: сумма объёмов полей общей части + объем памяти, достаточный для размещения самого большого варианта (см. рис.3.)
окружность |
прямоугольник |
треугольник | |||
TGeomfigure x0 y0 cvet radius не используется |
1 байт |
TGeomfigure x0 y0 cvet h w не используется |
1 байт |
TGeomfigure x0 y0 cvet x1 x2 y1 y2 |
1 байт 2 байт 2 байт 1 байт 2 байт 2 байт 2 байт 2 байт |
2 байт |
2 байт | ||||
2 байт |
2 байт | ||||
1 байт |
1 байт | ||||
2 байт |
2 байт | ||||
6 байт |
2 байт | ||||
4 байт |
Рис. 3. Выделение памяти для записи с вариантами
Как видно из рисунка, под запись с вариантами выделяется в любом случае объем памяти, достаточный для размещения самого большого варианта. Если же выделенная память используется для меньшего варианта, то часть ее остается неиспользуемой. Общая для всех вариантов часть записи размещается так, чтобы смещения всех полей относительно начала записи были одинаковыми для всех вариантов. Очевидно, что наиболее просто это достигается размещением общих полей в начале записи, но это не строго обязательно. Вариантная часть может и "вклиниваться" между полями общей части. Поскольку в любом случае вариантная часть имеет фиксированный (максимальный) размер, смещения полей общей части также останутся фиксированными.
Файлы.
Операции над файлами сводятся к работе с внешним устройством.
В любом случае работа с файлом складывается из трех пунктов:
- открытие файла (для чтения или/и записи),
- чтение или/и запись,
- закрытие файла.
Любые файлы становятся доступны программе только после выполнения особой процедуры открытия файла.
Эта процедура заключается в связывании ранее объявленной файловой переменной с именем существующего или вновь создаваемого файла, а также в указании направления обмена информацией: чтение из файла или запись в него.
Для этого служит процедура Assign (<ф.п.>,<имя файла>).
Type
TStudent =record
Fam, imia: string[30];
num: integer;
datarozhd: record;
…..
end;
var
Student: TStudent;
fofStud: file of Student;
f: file of Byte;
Begin
Assign(fofStud, ‘’);
rewrite(fofStud);
Close(fofStud);
…
Reset(fofStud);
read(fofStud, Student);
with Student do
begin
write(num);
write(fam);
end;
…..
End.
Каждому типу файлов свойственны свои особенности работы с ним.
Операция |
Текстовый файл (<ф.п> : TEXT) |
Типизированный файл (<ф.п.> : FILE OF <тип>) |
Нетипизорованный файл (<ф.п> : FILE) |
0. Связывание файла с <ф.п.> |
Assign (<ф.п.>, <имя файла>) | ||
1. Открытие1 | |||
- только для чтения |
Reset (<ф.п.>) |
|
|
- только для записи |
Append (<ф.п>)2 |
|
|
- для чтения и/или записи |
|
Reset (<ф.п.>) |
Reset (<ф.п.>,<длина элемента>)4 |
- для перезаписи |
Rewrite(<ф.п.>)3 |
Rewrite(<ф.п.>,<длина элемента>)4 | |
2. Чтение и/или запись | |||
2.1. чтение данных из файла |
Read (<ф.п.>, <имя перем-ой>) {считывает по одному элементу и записывает в заданную переменную} Readln (---//---) {считывает данные построчно} |
Read (<ф.п>, <имя перем-ой>) |
BlockRead (<ф.п>, <перем-ая>, <кол-во блоков>) |
2.2. запись данных в файл |
Write (<ф.п>, <имя перем-ой>) WriteLn (<ф.п>, <имя перем-ой>) {после записи элемента выполняется переход на новую строку файла} |
Write (<ф.п>,<имя перем-ой>) |
BlockWrite (<ф.п>,<перем-ая>, <кол-во блоков>) |
3. Закрытие файла |
Close(<ф.п.>) |
1 подготавливает файл к чтению информации. В результате, специальная переменная-указатель, связанная с этим файлом будет указывать на начало файла, т.е. на первый компонент с порядковым номером 0, если файл не пустой.
2 открытие файла для дозаписи в ранее созданныйтекстовый файл, при этом указатель файла устанавливается в егоконец. Если текстовый файл был ранее открыт процедуройRewriteилиReset, то вызов этой процедуры приведет к закрытию файла и открытию его вновь, для добавления записей.
3 подготавливает файл к приему новой информации при этом указатель принимает значение 0. При открытии этой процедурой уже существующего файла старые данные будут уничтожены. Если сразу после этой процедуры выполнить закрытие файлаClose(<ф.п.>), то таким образом. будет созданпустой файл.
4 длина указывается в байтах, если длина не указана, то, по умолчанию, элемент принимает размер = 128 байт