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