Энциклопедия Turbo Pascal. Главы 1-4 - Использование связанного списка для организации разреженного массива
ОГЛАВЛЕНИЕ
Использование связанного списка для организации разреженного массива
При реализации разреженного массива с помощью связанного списка формируется запись, которая содержит информационные поля для каждого элемента массива и поле позиции элемента в массиве, а также указатели на предыдущий и следующий элементы списка. Все записи в списке упорядочены по индексу массива. Доступ к элементам массива осуществляется путем прохода по связям элементов списка.
Например, может использоваться следующая запись для создания разреженного массива:
str128 = string[128];
str9 = string[9];
CellPointer = ^cell;
cell = record
CellName: str9; {содержит название ячейки}
formula: str128; {содержит формулу}
next: CellPointer; {указатель на следующую запись}
prior: CellPointer; {указатель на предыдущую запись}
end;
В этом примере поле "CellName" содержит строку с названием ячейки, например, А1, В34 или Z19. Строка "formula" содержит формулу для каждой ячейки электронной таблицы. Ниже приводятся несколько примерных программ, использующих разреженные матрицы на базе связанного списка. (Следует помнить, что имеется много способов реализации электронных таблиц. К приводимым ниже структурам данных и программам следует относиться только как к примерам использования таких методов). Для указателей начала и конца связанного списка используются следующие глобальные переменные:
start, last: CellPointer;
Когда вы вводите формулу в ячейку типичной электронной таблицы, вы фактически создаете новый элемент разреженной матрицы. Если электронная таблица строится на базе связанного списка, то вставка нового элемента будет производится с помощью функции "DLS_Store", которая рассматривается в главе 2. (Поскольку Паскаль позволяет создавать независимые функции указанная функция может использоваться фактически без всяких изменений). В приводимом примере список сортируется по названию ячейки (т.е. А12 предшествует А13 и т.д.)
{ упорядоченная вставка элементов в список и установка указателя
на начало списка }
function DLS_Store(info, start: CellPointer;
var last: CellPointer): CellPointer;
var
old, top: CellPointer;
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^.CellName < info^.CellName 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 }Для удаления элемента из электронной таблицы необходимо удалить соответствующую запись из списка и возвратить занимаемую им память системе с помощью функции Dispose. Функция DL_Delete удаляет ячейку из списка по заданному названию:
{ удаление ячейки из списка }
function DL_Delete(start: CellPointer;
key str9): CellPointer;
var
temp, temp2: CellPointer;
done: boolean;
begin
if start^.CellName=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^.CellName=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
begin
temp2 := temp;
temp := temp^.next; end;
end;
DL_Delete := start; { начало не изменяется }
if not done then WriteLn('not found');
end;
end; { конец процедуры удаления элемента из списка }Функция Find позволяет обратиться к любой конкретной ячейке. Эта функция имеет важное значение, так как многие формулы электронной таблицы имеют ссылки на другие ячейки и нужно эти ячейки найти, чтобы обновить их значения. В этой функции используется линейный поиск и, как показано в главе 2, среднее число операций при линейном поиске равно n/2, где n является числом элементов в списке. Кроме того, значительные потери будут из-за того, что каждая ячейка может содержать ссылки на другие ячейки и тогда потребуется выполнить поиск этих ячеек. Ниже дается пример функции Find (см.след.стр.).
{ найти конкретную ячейку и установить указатель на нее }
function Find(cell: CellPointer): CellPointer;
var
c: CellPointer;
begin
c := start;
while c<>nil do
begin
if c^.CellName=cell^.CellName then find:=c
else c := c^.next;
end;
WriteLn('cell not found');
Find:=nil;
end; { конец процедуры поиска }Создание, поддержка и обработка разряженных массивов имеет один большой недостаток, когда такой массив строится на базе связанного списка. Этот недостаток заключается в необходимости использовать линейный поиск каждой ячейки списка. Без дополнительной
информации, которая требует дополнительного расхода памяти, нельзя обеспечить двоичный поиск ячейки. Даже процедура вставки использует линейный поиск для нахождения соответствующего места для вставки новой ячейки в отсортированный список. Эти проблемы можно решить, используя для построения разреженного массива двоичное дерево.