Энциклопедия Turbo Pascal. Главы 1-4 - Оптимальное использование доступной памяти на примере текстового редактора
ОГЛАВЛЕНИЕ
Оптимальное использование доступной памяти на примере текстового редактора
Если вы являетесь профессиональным программистом, то вам возможно приходилось сталкиваться с трудностями, возникающими когда размер доступной памяти заранее неизвестен. Эти трудности возникают при разработке программы, определенные характеристики которой зависят от размера памяти некоторых или всех ЭВМ, где она будет выполняться. Примерами таких программ являются программы управления электронными таблицами, программы обработки списков почтовых корреспонденций и программы сортировки. Например, программа внутренней сортировки, способная отсортировать 10 000 адресов в ЭВМ с памятью 256К, сможет отсортировать лишь 5 000 адресов в ЭВМ с памятью 128К. Если эту программу предполагается использовать на ЭВМ, размер памяти которой заранее неизвестен, то трудно выбрать оптимальный размер фиксированного массива для хранения сортируемой информации: либо программа не будет работоспособна для ЭВМ с малой памятью, либо программа будет рассчитана на худший случай и нельзя будет воспользоваться дополнительной памятью, когда она имеется. Выход из этого положения заключается в динамическом выделении памяти.
Подобные трудности и их решение хорошо можно проиллюстрировать на примере программы редактирования текста. Большинство текстовых редакторов не рассчитаны на использование фиксированного числа символов. Напротив, они используют всю память ЭВМ, которая идет на хранение текста, введенного пользователем. Например, при вводе каждой строки делается выделение памяти и достраивается список строк. При удалении строки память возвращается системе. Для реализации такого текстового редактора может использоваться следующая запись для каждой строки:
LinePointer = ^Line;
str80 = string[80];
Line = record
next: str80; { для хранения каждой строки }
num: integer;
next: LinePointer; {указатель на следующую строку}
prior: LinePointer; {указатель на предыдущую запись }
end;
Для простоты в этом случае для каждой строки выделяется память под 80 символов. На практике будет выделяться память под точное число символов в строке и изменение строки потребует дополнительных затрат. В элементе "num" содержится номер каждой строки текста. Это позволяет использовать стандартную функцию "DLS_Store" для создания и поддержки текстового файла в виде упорядоченного списка с двойной связью.
Ниже приводится полная программа для простого текстового редактора. Он обеспечивает вставку и удаление любых строк с указанием номера строки. Он позволяет также просматривать текст и помещать его на диск.
В целом работа текстового редактора строится на базе применения упорядоченного связанного списка строк текста. В качестве ключа сортировки используется номер строки. Указывая начальный номер строки можно не только легко делать нужные вставки в текст, но также легко можно удалить текст. Единственной необычной функцией является функция "Patchup", которая перенумеровывает строки текста, когда этого требуют операции вставки и удаления.
В этом примере размер текста, который может размещаться в редакторе, зависит от доступной пользователю памяти. Таким образом, этот редактор будет автоматически использовать дополнительную память и не потребует перепрограммирования. Возможно это является самым важным достоинством динамического распределения памяти.
Возможности приводимой программы очень ограничены, однако она обеспечивает основные функции текстового редактора. Эту программу можно усовершенствовать и получить текстовый редактор с требуемыми возможностями.
{ очень простой текстовый редактор }
program TextEd;
type
str80 = string[80];
LinePointer = ^Line;
line = record
text: str80;
num: integer;
next: LinePointer; {указатель на следующую строку}
prior: LinePointer; {указатель на предыдущую запись }
end;
DataItem = line;
filType = file of line;
var
text: filtype;
start, last: LinePointer;
done: boolean;
iname: str80;
{ возвращает выбранную пользователем функцию }
function MenuSelect: char;
var
ch: char;
begin
WriteLn('1. Enter text');
WriteLN('2. Delete a line');
WriteLn('3. Display the file');
WriteLn('4. Save the file');
WriteLn('5. Load the file');
WriteLn('6. Quit');
repeat
WriteLn;
Write('Enter your choice: ');
ReadLn(ch); ch := UpCase(ch);
until (ch>='1') and (ch<='6')
MenuSelect := ch;
end;{ конец выбора по меню }
{ поиск заданной строки и выдача указателя на нее }
function Find(num: integer): LinePointer;
var
i: LinePointer;
begin i:= start;
find := nil;
while (i<>nil) do begin
if lnum=i^.num then find :=i;
i := i^.next;
end;
end;
{ формирование номеров строк при вставке или удаления из
текста }
procedure PatchUp(lnum, incr: integer);
var
i:LinePointer;
begin
i := Find(lnum)
while (i<>nil) do begin
i^.num := i^.num +incr;
i := i^.next
end:
end;
{ упорядоченная вставка строк в текст }
function DLS_Store(info, start: LinePointer;
var last: LinePointer): LinePointer;
var
old, top: LinePointer;
done: boolean;
begin
top := start;
old := nil;
done := FALSE;
if start = nil then begin { первый элемент списка }
info^.next := nil;
last := info;
info^.prior :=nil;
DLS_Store := info;
end else
begin
while (start<>nil) and (not done) do
begin
if start^.num < info^.num then
begin
old := start;
start := start^.next;
end else
begin { вставка в середину }
if old <>nil then
begin
old^.next := info;
info^.next := start;
start^.prior := info;
info^.prior := old;
DLS_Store := top; { сохранение начала }
done := TRUE;
end else
begin
info^.next := start;{новый первый элемент }
info^.prior := nil;
DLS_Store := info;
done := TRUE;
end;
end;
end; { конец цикла }
if not done then begin
last^.next := info;
info^.next := nil;
info^.prior := last;
last := info;
DLS_Store := top; { сохранение начала }
end;
end;
end; { конец функции DLS_Store }
{ удаление строки текста }
function DL_Delete(start: LinePointer
key: str[80]:) LinePointer
var
temp, temp2: LinePointer
done: boolean;
begin
if star^.num = key then begin { первый элемент
списка }
DL_Delete := start^.next;
if temp^.next <> nil then
begin
temp := start^.next;
temp^.prior := nil;
end;
dispose(start);
end else
begin
done := FALSE;
temp := start^.next;
temp2 := start;
while (temp <> nil) and (not done) do
begin
if temp^.num = key then
begin
temp2^.next := temp^.next;
if temp^.next = <> nil then
temp^.next^.prior := temp2
done := TRUE
last := temp^.prior
dispose(temp);
end else
temp2 := temp;
temp := temp^.next;
end;
end;
DL_Delete := start; { начало не изменяется }
if not done then Writeln('not found');
else PatchUp(key+1,-1);
end;
end; { конец функции DL_Delete }
{ подсказка пользователю для ввода номера удаляемой строки }
procedure Remove;
var
num:integer;
begin
Writeln('Enter line to delete: ');
Readln(num);
start := DL_Delete(start,num);
end; { конец процедуры удаления }
{ ввод строк текста }
procedure Enter;
var
info: LinePointer;
done: boolean;
begin
done := FALSE;
Write('Enter starting lnie number: ');
Readln(num);
repeat
new(info) { получить новую запись }
info^.num := num;
Write(info^.num,':')
Readln(info^.text);
if Length(info^.text = 0 then done := TRUE
else begin
if Find(num)<> nil then PatchUp(num,1);
start := DLS_Store(info, start, last);
end;
num := num +1;
until done;
end; { конец ввода }
{ вывод файла на экран }
procrdure Display(start: LinePointer);
begin
while start <> nil do begin
Write(start^.num,':');
Writeln(start^.text);
start := start^.next
end;
Writeln;
end;
{ записать файл на диск }
procedure Save(var f:FilType; start: LinePointer):
begin
Writeln('saving file');
rewrite(f);
while start <> nil do begin
write(f,start);
start := start^.next;
end;
end;
{ загрузчика файла с диска и получение указателя на начало
списка }
procedure Load(var f:FilType; start: LinePointer):
LinePointer;
var
temp: LinePointer
begin
Writeln('load file');
reset(f);
while start <> nil do begin
temp := start^.next
dispose(start);
start := temp;
end;
start := nil; last := nil;
if not eof(f) then begin
begin
New(temp);
Read(f,temp^);
start := DLS_Store(temp, start, last);
end;
begin
start := nil; { сначала список пустой }
last := nil;
done := FALSE;
Write('Enter Filename: ');
Readln(filename);
Assign(text,filename);
repeat
case MenuSelect of
'1': Enter;
'2': Remove;
'3': Display(start);
'4': Save(text,start);
'5': start := Load(text);
'6': done := TRUE;
end;
until done = TRUE;
end.