Тема: применение связанного списка для создания динамического массива
Программерская шутка:
Сообщение: "Press a Key"
Перевод: "Нажмите кнопку a"
Значение: "Пока вы не нажмете кнопку 'a'
ничего не произойдет"
В Borland Pascal нет динамических массивов, длину которых можно изменять во время работы программы. Такие массивы давно существуют в С++ и появились в Object Pascal/Delphi.
В данной работе мы покажем, как их можно создать
Что уже имеется?
Для работы с массивами строк имеется объект TStringCollection в модуле Object. Для объектов - TCollection. Оба удобны, но требуют знания хотя бы основ объектно - ориентированного программирования. Давайте сейчас обойдемся без них, хотя и позаимствует идею работы. Использование объектов пусть будет темой отдельного разговора.
Будем создаватьмассив целых чисел (изменить тип элементов очень просто) с помощью связанного списка. Связанный список - это последовательность записей (структур), которые хранят данные, а также адрес - ссылку на другую запись такого же типа. Элемент списка называют узлом. Здесь показан пример односвязного линейного списка. Каждый элемент хранит ссылку только на один элемент (линейный) и только на следующий (односвязный). Если это последний элемент списка , то он ни на кого не ссылается. Значение указателя на следующий узел равно NIL - константа Паскаля.
Создавать такие списки в "обычной" памяти компьютера нет смысла. Связанные списки организуют в динамической памяти. Обращение к ним производится через указатели. Если Вы уже встретили термины, которые еще плохо понимаете, не расстраивайтесь, а задайте вопрос по адресу, который указан ниже. Мы, между прочим, для того здесь и поставлены, чтобы на вопросы отвечать. Только постарайтесь конкретизировать вопрос, если это возможно
В чем заключаются сложности использования такого списка? Сами судите:
- Нужно помнить, как следует начинать список, как с ним работать. Например, если Вы не сохраните адрес начала списка (случайно его измените), то обратиться к первым элементам уже не сможете!
- Всегда есть опасность, что пользователь сам обратится к какому-то элементу массива, не используя специальные подпрограммы. Иногда это можно, но и результат может быть непредсказуемым.
Ниже показан пример реализации без использования объектов. Имеется возможность работать с несколькими массивами. Для этого каждой подпрограмме передается имя массива.
Если Вы решитесь на использование объектов (и правильно сделаете !), но еще не умеете это делать, то пишите sPascal@mail.ru.
Если Вы встретили термины, которые еще плохо понимаете, не расстраивайтесь, а задайте вопрос по адресу, который указан выше. Мы, между прочим, для того здесь и поставлены, чтобы на вопросы отвечать.Только постарайтесь конкретизировать вопрос, если можно.
program Din_Arr;
uses CRT;
CONST
ArMax = 20;
TYPE
PArray = ^TArray; {Новый тип переменной: указатель на новую структуру}
TArray = record {Описание нового типа переменной}
Mass: array[1..ArMax] of Integer; {Хранимая информация}
Next: PArray; {Это и есть указатель на следующую запись}
end;
{Функция создает новый пустой узел}
function NewNode: PArray;
var P: PArray;
begin
New(p); p^.next:=nil; {Следующего нет}
NewNode:=p
end;
{Инициализация списка}
procedure Init( var Ar: PArray);
begin
if Ar <> nil then Exit; {Уже создан}
Ar:=NewNode;
end;
{Удаление списка из памяти компьютера}
procedure Destroy(var Ar: PArray);
var
P : PArray;
begin
if Ar = nil then Exit; {Нечего разрушать}
REPEAT
P:=Ar^.Next;
Dispose(Ar);
Ar:=P
until Ar = nil;
end;
{Записать значение в элемент массива с индексом Index. Если места
для этого элемента еще нет, то будут добавлены новые узлы}
procedure PutValue(var Ar: PArray; Index: Integer; Value: Integer);
var Saved: PArray;
begin
Saved:=Ar;
{Делаем копию. Точку входа менять нельзя.
Вернее можно, но получится сложнее. Надо будет
создавать двунаправленный список}
While Index > ArMax do begin
if Ar^.Next = nil then
Ar^.Next:=NewNode;
Ar:=Ar^.Next;
dec(Index, ArMax);
end;
Ar^.Mass[Index]:=Value;
Ar:=Saved
end;
{Функция: получить значение величины, которая хранится в
элементе с индексом Index}
function GetValue(const Ar: PArray; Index: Integer): Integer;
var
p: PArray;
begin
p:=Ar;
while Index > ArMax do
begin
p:=p^.Next;
dec(Index, ArMax);
if p = nil then
begin GetValue := 1111; Exit end;
{Тут надо решать самому, что получим, если захочешь
получить больше, чем положил}
end;
GetValue:=p^.Mass[Index]
end;
CONST
A: PArray = nil; {Начало списка. Не смотрите, что написано CONST. Менять ее можно!}
VAR
i: Integer;
BEGIN
ClrScr;
WriteLn('Вот сколько динамической памяти в начале работы: ',MemAvail); {}
Init(A);
i:=2251;
{ Для примера запишем что-нибудь в элемент с индексом i,
а потом прочитаем его, чтобы удостовериться}
PutValue(A, i, 5);
WriteLn('Value No ',i,' = ',GetValue(A, i));
WriteLn('Столько стало: ',MemAvail);
Destroy(A);
WriteLn('А это после очистки (при правильной работе должно получиться столько же, сколько
было: ',MemAvail);
WriteLn('Нажмите любую клавишу ...'); ReadKey
END.
Если Вы все поняли, то дополните программу какими-нибудь полезными свойствами и функциями, например, занесите нули во все вновь организуемые элементы, просуммируйте все элементы массива, найдите элемента.
А если и это просто для Вас, то попробуйте реализовать следующее:
- удалите группу с заданным номером;
- удалите один элемент массива с заданным индексом, сдвинув "старшие" на одну позицию "влево";
- вставьте элемент в позицию с заданным индексом. Тот, что стоял на этом месте, и с ним все остальные должны сместиться на позицию вправо.
Удачи. © Борис
