Динамические структуры данных. Алексеев А.Ю - 11 стр.

UptoLike

ВУЗ: 

КамчатГТУ | Петропавловск-Камчатский

Составители: 

Рубрика: 

Unit Global;
{Здесь задается тип элементов }
{Л1–списка, реализованного }
{ модулем L1List }
Interface
type El = Char; { например }
Implementation
end {Global}.
program Main;
Uses L1List,Global;
{Программа работы со списками,}
{использующая модуль L1List }
...
var s : L1_list;
...
begin
...
end {Main}.
Рис. 1.9. Макеты программных единиц, связанных с модулем L1List:
слева - модуля Global, справа - главной программы
Таким образом, для работы с Л1–списком достаточно описать переменную
типа L1_list и воспользоваться набором базовых операций, реализованных в
модуле L1List.
1.4. Ссылочная реализация ограниченного Л1–списка на базе вектора
В ряде случаев можно реализовать Л1–список, опираясь на линейную (век-
торную) модель памяти. Такая реализация, очевидно, целесообразна на языках
типа Бейсик, Фортран и т.п. Даже в тех случаях, когда язык программирова-
ния (Паскаль, Си, Ассемблер) поддерживает модель динамической памяти,
векторная реализация может оказаться привлекательной тем, что позволяет
программисту самому управлять распределением памяти, не полагаясь на ис-
полняющую систему, частое обращение к которой может к тому же потребо-
вать значительных затрат времени при исполнении программы.
Итак, пусть память, отводимая для хранения списка, представляется одно-
мерным массивом (вектором) записей. Ссылкой будет являться номер элемен-
та вектора. Поскольку размер массива в ходе обработки списка не изменяется,
то и максимальная длина списка ограничена этим размером. В этом случае го-
ворят об ограниченном Л1–списке и добавляют к базовым операцию Not_full ,
проверяющую массив на наличие свободного места, необходимого для раз-
мещения очередного элемента списка: Not_full: L_list → Boolean.
Основная идея реализации ограниченного Л1–списка на базе вектора ясна
из рис.1.10−1.12. На рис.1.10 приведен пример размещения списка s из эле-
ментов a, b, c, d в массиве Memory типа MemoryForLists при MemMaxSize = 12.
Нижние линии на рисунке обозначают связи списка s, а верхние линии связы-
вают в список свободной памяти не занятые элементами списка s элементы
массива. Соединение свободных элементов массива в линейный список зна-
чительно упрощает реализацию. Нулевой элемент массива используется для
хранения ссылки на первый элемент списка свободной памяти. При этом на
базе одного вектора (массива типа MemoryForLists) могут быть реализованы
несколько Л1–списков, ограниченных в совокупности.
11
Unit Global;                            program Main;
{Здесь задается тип элементов }         Uses L1List,Global;
{Л1–списка, реализованного }            {Программа работы со списками,}
{ модулем L1List        }               {использующая модуль L1List }
Interface                               ...
type El = Char; { например }            var s : L1_list;
Implementation                          ...
end {Global}.                           begin
                                        ...
                                        end {Main}.

          Рис. 1.9. Макеты программных единиц, связанных с модулем L1List:
                    слева - модуля Global, справа - главной программы

   Таким образом, для работы с Л1–списком достаточно описать переменную
типа L1_list и воспользоваться набором базовых операций, реализованных в
модуле L1List.


 1.4. Ссылочная реализация ограниченного Л1–списка на базе вектора

    В ряде случаев можно реализовать Л1–список, опираясь на линейную (век-
торную) модель памяти. Такая реализация, очевидно, целесообразна на языках
типа Бейсик, Фортран и т.п. Даже в тех случаях, когда язык программирова-
ния (Паскаль, Си, Ассемблер) поддерживает модель динамической памяти,
векторная реализация может оказаться привлекательной тем, что позволяет
программисту самому управлять распределением памяти, не полагаясь на ис-
полняющую систему, частое обращение к которой может к тому же потребо-
вать значительных затрат времени при исполнении программы.
    Итак, пусть память, отводимая для хранения списка, представляется одно-
мерным массивом (вектором) записей. Ссылкой будет являться номер элемен-
та вектора. Поскольку размер массива в ходе обработки списка не изменяется,
то и максимальная длина списка ограничена этим размером. В этом случае го-
ворят об ограниченном Л1–списке и добавляют к базовым операцию Not_full ,
проверяющую массив на наличие свободного места, необходимого для раз-
мещения очередного элемента списка: Not_full: L_list → Boolean.
    Основная идея реализации ограниченного Л1–списка на базе вектора ясна
из рис.1.10−1.12. На рис.1.10 приведен пример размещения списка s из эле-
ментов a, b, c, d в массиве Memory типа MemoryForLists при MemMaxSize = 12.
Нижние линии на рисунке обозначают связи списка s, а верхние линии связы-
вают в список свободной памяти не занятые элементами списка s элементы
массива. Соединение свободных элементов массива в линейный список зна-
чительно упрощает реализацию. Нулевой элемент массива используется для
хранения ссылки на первый элемент списка свободной памяти. При этом на
базе одного вектора (массива типа MemoryForLists) могут быть реализованы
несколько Л1–списков, ограниченных в совокупности.
                                        11

Страницы