Автор: Пользователь скрыл имя, 30 Марта 2013 в 21:12, лабораторная работа
Цели работы:
- Ознакомиться с особенностями создания и обработки списка в типизированном файле;
- Создать проект в системе Delphi7, в котором реализованы основные операции обработки списка в типизированном файле.
Различные динамические структуры данных можно размещать не только в динамической памяти, но и в двоичных или текстовых файлах.
В данной лабораторной работе рассматривается размещение однонаправленного связанного списка в типизированном файле.
Лабораторная работа № 5
Реализация списка в типизированном файле
СОДЕРЖАНИЕ
Лабораторная работа № 5
Реализация линейного списка в типизированном файле.
Цели работы:
- Ознакомиться с особенностями создания и обработки списка в типизированном файле;
Различные динамические структуры данных можно размещать не только в динамической памяти, но и в двоичных или текстовых файлах.
В данной лабораторной работе рассматривается размещение однонаправленного связанного списка в типизированном файле.
При размещении связанного списка в файле, адресом элемента списка является номер записи файла, в которой находится этот элемент. Номер записи файла – это число, следовательно, поле-указатель на следующий элемент списка на самом деле является теперь не указателем, а целым числом, номером записи, в которой хранится следующий элемент списка.
Реализация списка в файле имеет еще одну особенность – адрес первого элемента списка необходимо хранить в самом файле в отдельной записи файла, например в ее поле Next. Такая запись называется «заголовок списка» и всегда хранится в начале файла.
Поскольку поле Next не является указателем, то оно не может содержать значение Nil. В качестве признака того, что список пуст или элемент списка последний – используется значение -1 или любое другое значение меньше нуля, так как в типизированном файле записи нумеруются с нуля.
При реализации списка в файле необходимо обеспечить наличие процедур, которые выполняют действия, подобные действию процедур New и Dispose при размещении списка в динамической памяти.
При удалении элементов из списка в файле образуются свободные записи, называемые «дырами». Не следует для каждого удаления или вставки нового элемента в список осуществлять сдвиг элементов, как это делается в массиве, так как для файла это операция, дорогостоящая по времени.
Следует отметить, что для учета свободных мест (записей) в файле и быстрого их поиска, «дыры» организованы в список.
Как список элементов, так и список дыр должен иметь свой заголовок в начале файла.
Таким образом, при реализации списка в файле, в его начале расположен заголовок списка дыр и заголовок списка элементов.
Физическая структура данных для реализации списка в файле приведена на рисунке 5.1.
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 | ||||||||
Загол. списка дыр |
2 |
Загол. списка |
4 |
Дыра |
3 |
Дыра |
6 |
Арбуз |
5 |
Бобер |
7 |
Дыра |
-1 |
Кеда |
-1 |
Рисунок 5.1 – Физическая структура связанного списка в типизированном файле
Алгоритмы обработки списка в файле аналогичны алгоритмам по обработке списка в динамической памяти.
Для того чтобы представить разницу в обработке элемента списка, рассмотрим таблицу 5.1, где происходит изменение поля Name элемента списка, адрес которого содержится в переменной WP.
Таблица 5.1 – Сравнительная таблица, представляющая изменение поля текущего элемента списка при размещении его в куче и в файле.
Для кучи |
Для файла |
Type TPRec=^TRec; TRec=record Name:string[15]; Next: TPRec; end;
var Wp: TPRec; begin . . . Wp^.Name := ‘Иванов’; |
Type TRec=record Name:string[15]; Next: TPRec; end; TFile= file of TRec;
Var f:TFile; r : TRec; WP : integer; Begin . . . Seek(f, wp); Read (f, r); r.Name := ‘Иванов’; Seek(f, wp); Write (f, r); |
Как отмечалось выше, при реализации списка в файле тип данных – указатель не используется. Адрес следующего элемента списка – это номер записи файла, в которой он записан, то есть – целое число.
Для реализации списка в файле нет необходимости в глобальной переменной Start, содержащей адрес первого элемента списка, так как его всегда можно взять из заголовочной записи в файле.
Файловая переменная, соответствующая файлу со списком должна быть глобальной.
Пример описания типов для списка в файле приведен на рисунке 5.2.
Type TRec=record Name : string[20]; Bal : real; Next : integer; end;
TFile = file of TRec;
var F : TFile; |
Рисунок 5.2 – Описание типов и объявление глобальных переменных для реализации списка в типизированном файле
Для реализации списка в файле необходимо обеспечить выполнение следующих операций:
Процедура открытия или создания файла для списка получает имя файла и возвращает файловую переменную. В ней выполняется попытка открыть существующий файл с заданным именем. Если при открытии существующего файла возникает ошибка, то осуществляется создание нового файла с заданным именем и выполняется вызов процедуры инициализации файла, описанной ниже (см. п. 5.3.2).
Процедура открытия или создания файла для списка представлена на рисунке 5.3.
Procedure OpenFile(FileName:string; var f:TFile);
begin
AssignFile(f,FileName);
{$I-}
reset(f);
{$I+}
if IOResult()<>0
then
begin
rewrite(f); // если файла нет, то создаем
Init_File(f); // инициализируем файл
end;
end; |
Рисунок 5.3 – Процедура открытия файла
Инициализация списка в файле заключается в создании двух заголовочных записей в файле. В поля Next этих записей заносим значения -1 – признак того, что список дыр и список элементов пусты.
Процедура инициализации представлена на рисунке 5.4.
Procedure Init_File(var f:TFile);
var rec:TRec;
begin
rec.Next := -1;
rewrite(f);
write(f,rec,rec);
end; |
Рисунок 5.4 – Процедура иницализации файла
Для вывода списка на экран будем использовать компонент ListBox.
Процедура получает файловую переменную, адрес первого єлемента списка и компонент ListBox.
Процедура вывода списка в компонент ListBox представлена на рисунке 5.5.
Procedure ShowInListBox(var f:TFile; Start:integer;LB:TListBox); var rec:TRec; WP: integer; begin // Очистка ЛистБокса LB.Clear;
// Инициализация рабочего "указателя" WP:=Start; While WP <> -1 do begin // чтение текущего элемента seek(f,WP); read(f,rec); //вывод текущего элемента в ЛистБокс LB.Items.Add(rec.Name); // переход на следующий элемент WP:=rec.Next; end; end; |
Рисунок 5.5 – Процедура вывода списка в ListBox
Процедура поиска физического места для размещения нового элемента в файле выполняет туже задачу, что и процедура New для кучи – возвращает адрес свободного участка памяти, где можно разместить новый элемент. Отличие состоит в том, что процедура New встроенная в язык Object Pascal, а для файла необходимо реализовать эту процедуру разработчику.
Поскольку в файле есть список дыр, т.е. список свободных записей, то новый элемент можно разместить в одной из таких «дыр», а не в конце файла. В таком случае будет сэкономлена память на внешнем носителе и размер файла не увеличится.
Процедура поиска физического места в файле получает файловую переменную, а возвращает позицию (номер записи), в которой можно разместить новый элемент.
Алгоритм процедуры следующий:
Процедура поиска физического места в файле для размещения нового элемента приведена на рисунке 5.6.
Procedure New_in_File(var f:Tfile; var NewPos : integer); var rec : TRec; begin // читаем заголовок списка дыр seek(f,0); read(f,rec); if rec.Next=-1 // если список дыр пуст then NewPos:=FileSize(f) // то позиция - в конце файла else // иначе позиция - первая по списку дыра begin NewPos:=rec.Next; seek(f,NewPos); read(f,rec); seek(f,0); // адрес
второй дыры заносим в // запись списка дыр write(f,rec); end; end; |
Рисунок 5.6 – Процедура поиска физического места для размещения нового элемента в файле
Назначение этой процедуры сходно с назначением процедуры Dispose для кучи.
В результате удаления єлемента из списка остается запись в файле, которая не входит теперь в список єлементов и еще не включена в список дыр. Процедура вставляет новую дыру (номер записи которой приходит в процедуру) в начало списка дыр. В результате изменяется поле Next заголовочной записи. Кроме позиции новой дыры, процедура получает как параметр файловую переменную.
Процедура освобождения физического места в файле после удаления элемента из списка представлена на рисунке 5.7.
Procedure Dispose_in_File(var f:Tfile; DelPos: integer); var rec: TRec; wpos: integer; begin // читаем заголовок списка дыр из файла seek(f,0); read(f,rec); // в прочитанном заголовке в поле Next находится адрес первой дыры // теперь эта дыра будет второй, значит то, что записано в поле Next // заголовочной записи, записываем в поле next новой дыры, теперь она // первая. Надписываем не отдельно значение поля next, а полностью //запись, так как информация в дырах для нас не важна seek(f,DelPos); write(f,rec); // Изменяем поле Next заголовочной записи, теперь в нем адрес вновь //добавленной дыры rec.Next:=DelPos; seek(f,0); write(f,rec); end; |
Рисунок 5.7 – Процедура освобождения физического места в файле после удаления элемента из списка
Алгоритм процедуры добавления нового элемента в отсортированный список в файле аналогичен алгоритму такой процедуры для «кучи». Отличия возникают только из-за особенностей обращения к записям файла.
До вызова данной процедуры новый элемент должен быть уже записан в файл, его поле Next должно содержать значение -1.
Процедура добавления элемента в отсортированный список имеет следующие параметры:
Процедура добавления нового элемента в упорядоченный список представлена на рисунке 5.8.
Procedure AddToList(var f:TFile; var Start:integer; NewPos:integer); var rec,rec_new:TRec; pp, wp : integer; ok:boolean; begin // читаем новый элемент, нам понадобится его ключевое поле seek(f,NewPos); read(f, rec_new); // инициализация рабочих указателей wp:=Start; pp:=-1; // цикл для поиска места вставки нового элемента While wp<> -1 do begin seek(f,wp); read(f,rec); //читаем текущий элемент списка if rec_New.Name <= rec.Name // если нашли место вставки then break; // то выход из цикла pp:=wp; // иначе переходим к следующему элементу wp:=rec.Next; end; // После цикла wp и pp содержат адреса элементов, // между которыми необходимо вставить новый в списке
// в поле Next нового элемента //заносим wp - адрес следующего и перезаписываем // новый элемент обратно в файл rec_new.Next:=wp; seek(f,NewPos); write(f,rec_new); // проверяем - новый элемент будет первым в списке // или нет if pp=-1 then // если первый, то Start будет // содержать его адрес Start:=NewPos else begin // если не первый, то у предыдущего // элемента в поле Next заносим //адрес нового seek(f,pp); read(f,rec); rec.Next:=NewPos; seek(f,pp);// после изменения поля next у // предыдущего элемента, его необходимо // перезаписать обратно в файл write(f,rec); end; end; |
Информация о работе Реализация линейного списка в типизированном файле