Энциклопедия Turbo Pascal. Главы 1-4
Страница 41. Оптимальное использование доступной памяти


Оптимальное использование доступной памяти

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

 
« Предыдущая статья