|
Страница 41 из 60
Оптимальное использование доступной памяти
Если вы являетесь профессиональным программистом, то вам
возможно приходилось сталкиваться с трудностями, возникающими
когда размер доступной памяти заранее неизвестен. Эти трудности
возникают при разработке программы, определенные характеристики
которой зависят от размера памяти некоторых или всех ЭВМ, где она
будет выполняться. Примерами таких программ являются программы
управления электронными таблицами, программы обработки списков
почтовых корреспонденций и программы сортировки. Например, прог-
рамма внутренней сортировки, способная отсортировать 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.
|