Динамические структуры данных. Задание практикума. Язык Паскаль. Вылиток А.А - 10 стр.

информационного поиска, трансляторах, при моделировании различных
процессов. Однако по отношению к языку Паскаль список является
абстрактным понятием: в Паскале не предусмотрены ни встроенные операции
над списками, ни средства для их описания, подобные тем, что имеются,
скажем, для массивов.1 Поэтому для обработки списков на Паскале потребуется
их программная реализация. Для этого необходимо:
    1)    сконструировать средствами Паскаля структуру данных, которая будет
          представлять в программе список (в этой структуре будут храниться
          элементы списка);
    2)    описать в виде процедур и функций требуемые операции над списками.

       Мы рассмотрим два наиболее типичных способа реализации списков:
посредством массивов и с помощью цепочки звеньев.


         Реализация списков посредством массивов

      В этой реализации элементы списка располагаются по порядку в
компонентах массива, начиная с первой; i-й элемент списка хранится в i-ой
компоненте. Размер массива определяет максимально возможную длину списка.
В программе размер массива зададим константой maxlen. Для работы со
списком требуется ещё знать его текущую длину (или номер компоненты
массива, в которой находится текущий последний элемент). Опишем тип list
(список) как запись, имеющую два поля: первое с именем elems (от англ.
elements – элементы) – собственно массив; второе с именем last – позиция
последнего элемента списка. Дадим также описание переменной L типа list:

const
  maxlen =           … {подходящее для конкретной задачи целое
                                                       число};
type
  elemtype = … {подходящий для задачи тип элементов};
  list = record
           elems: array [1..maxlen] of elemtype;
           last: integer
         end;
var L: list;

Выражение L соответствует понятию «список». Конструкция               L.elems[i]
обозначает в программе i -й элемент списка.

      Пусть в качестве elemtype задан перечислимый тип: (Monday,
Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday).
Реализация списка названий дней недели < Monday, Wednesday, Friday,
Saturday> на схеме будет выглядеть так (считаем, что maxlen = 7) :
1
 В языке Лисп, напротив, список является основной структурой данных с богатым набором
операций, а массивы отсутствуют.

                                       - 10 -