Элемент Описание

item, pitem Тип для одного элемента списка (запись) и указателя на него

data Поле данных (информационная часть элементов списка)

next, prev Указатели следующего, предыдущего элементов (указующая часть)

head, top Указатели на первый и последний элемент списка

pl, p2 Рабочие указатели

Опишем тип одного элемента односвязного списка и указателя на этот эле­мент:

Type

Pitem=^item;

item=record

data:...{простой или определяемый пользователем тип }

next: pitem; { или prev:pitem; }

end;

Перейдем к примерам. Наиболее просто реализуются действия со стеком, поэтому первый пример демонстрирует использование стека. Все действия со стеком выполняются только на одном конце, который на­зывается вершиной стека. Стеки как структуры данных имеют широкое при­менение в системном программировании (например, при разработке ком­пиляторов). В частности, область памяти, в которую помещаются парамет­ры и локальные переменные подпрограмм, имеет структуру стека. Именно благодаря устройству стека возможны такие приемы программирования, как вложенные подпрограммы и рекурсия.

		nil

…

	top

N n-1 1

Конечно, в примере реализуется учебный стек, содержащий целые числа.

Листинг 1 Действия со стеком

type

pitem=^item;

item=record { элемент стека }

data: integer; { значение элемента }

prev: item; { адрес предыдущего элемента }

end;

var

top,p:pitem:

n,k:integer;

procedure add(x:integer); { добавляет элемент на вершину стека }

begin

new(p); { создаем произвольный элемент р }

p^.data:=x;

р^.prev:=top;

top:=p; { устанавливаем toр вершиной стека }

end;

procedure deltop; { удаляет узел с вершины стека }

begin

if top<>nil then

begin { если стек не пустой }

p:=top^.prev; { запоминаем предшествующий вершине элемент }

dispose(top);

top:=p; { устанавливаем toр вершиной стека }

end;

end;

procedure writestack; { выводит стек на экран }

begin

writeln('Содержимое стека (начиная с вершины): ');

p:=top;

while p<>nil do

begin

write(р^.data,' ');

p:=p^.prev;

end;

writeln;

end;

BEGIN { начало программы }

top:=nil;

for k:=l to 10 do

add(k); { заполняем стек числами от 1 до 10 }

writestack;

writeln('Введите значение элемента для добавления в стек:'); readln(n);

add(n);

writestack;

writeln('Сколько элементов стека нужно удалить?'); readln(n);

for k:=l to n do

deltop;

writestack;

readln

END.

{ Комментарии}

В примере реализованы две основные операции со стеком: добавление и уда­ление элементов. Для решения задачи потребовалось всего два указателя типа pitem. Один из них (top) всегда указывает на вершину стека, второй (р) — ра­бочий указатель, предназначенный для временного хранения адресов различ­ных элементов. Обратите внимание на типовую процедуру вывода списка при помощи цикла while. Стандартное действие p:=p^.prev; означает переход к следующему элементу стека (для стека правильнее назвать этот элемент не следующим, а предыдущим, т. к. он был помещен в стек раньше). Поэтому эле­менты стека можно вывести только в порядке, обратном тому, в котором они вводились.

В следующем примере при формировании списка указующие поля заполняются таким образом, что каждый элемент списка действительно указывает на следующий за ним элемент, т. е. элемент, помещенный в список позже. Таким образом, при выводе списка его элементы появятся на экране именно в том порядке, в котором заполнялся список. Такой способ формирования списка используется при реализации очередей. Но в данном примере рассматривается общий случай списка и приводятся процедуры вставки и удаления элементов в произвольную позицию списка.

Листинг 2. Вставка и удаление элементов в произвольной позиции

type

pitem=^item;

item=record

data:integer;

next:pitem;

end;

var

head,p,p1:pitem;

n,k,l:integer;

procedure add(x,i:integer);

var

j:integer;

begin

if (i>0) and (i<=n+l) then

begin

new(p);

p^.data:=x;

if i=l then

begin

p^.next:=head;

head:=p;

end

else

begin

p1:=head;

for j:=2 to i-1 do (находим i-1-й элемент }

pl:=pl^.next;

p^.next:=р1^.next;

pl^.next:=p;

end;

n:=n+l;

end;

end;

procedure delitem(i:integer);

var

k:integer;

begin

if (i>=l) and (i<=n) and (head<>nil) then

if i=l then

begin { если нужно удалить первый элемент }

р:=head^.next;

dispose(head);

head:=p;

end

else

begin

p:=head;

for к:=2 to i-1 do { находим i-1-й элемент }

p:=p^.next;

pl:=p^.next; { pl-i-й элемент }

р^.next:=р1^.next; { p^.next ссылается на i+1-й элемент }

dispose(pi);

end;

end;

procedure writelist;

begin

p1:=head;

writeln('Содержимое списка');

while p1<>nil do

begin

write(р1^.data,' ');

pl:=pl^.next;

end;

writeln;

end;

BEGIN

n:=0; head:=nil;

for k:=l to 10 do

add(k,k); { заполняем список числами от 1 до 10 }

writequeue;

write('Введите значение добавляемого элемента:');

readln(k);

write('Введите позицию добавляемого элемента');

readln(l);

add(k,l);

writelist;

write('Введите номер удаляемого элемента:'); readln(k);

delitem(k); writelist;

readln

END.

{Комментарии}

Проанализировав процедуры вставки и удаления элементов в произвольное место списка, можно прийти к выводу, что сама операция добавления и удале­ния выполняется на удивление просто — достаточно лишь переставить указа­тели. Гораздо больше времени уходит на то, чтобы найти элемент с заданным номером в списке. Список — это не массив, и обратиться по индексу к элементу нельзя. Остается только один вариант — двигаться по цепочке от одного эле­мента к другому, начиная от самого первого элемента.

Подведем итоги. Итак, связанные списки и массивы — две основные струк­туры в оперативной памяти, которые используются для обработки данных. Сравним их между собой, выделив главные моменты:

¨ организация данных в памяти в виде связанных списков обеспечивает более экономное использование памяти по сравнению с массивами;

¨ другим преимуществом связанных списков является удобство вставки и удаления элементов. Вспомним, что в массиве для этих целей приходи­лось раздвигать или сдвигать элементы.В списке для удаления и вставки достаточно только поменять значения указующих по­лей соседних элементов;

¨ явным достоинством массивов является простота их использования по сравнению со списками (в этом вы, очевидно, убедились);

¨ еще более существенным преимуществом массива является высокая ско­рость доступа к элементу массива по его индексу. Исходя из того, что уже рассказано о списках, можно легко догадаться, что для получения доступа к последнему элементу односвязного списка необходимо после­довательно обойти всю цепочку, начиная с самого первого элемента.

Из сказанного можно сделать вывод — при решении задач обработки дан­ных во многих случаях выбор между массивом и списком сделать непросто. Необходимо тщательно взвесить все плюсы и минусы обоих вариантов, а далее действовать по обстоятельствам. Начинающим рекомендуем не бо­яться указателей и динамических структур, т. к. программирование дейст­вий с ними — хороший способ развития логического мышления.

Модули

Модул ь в Турбо-Паскале - специальным образом оформленная библиотека определений типов, констант, переменных, а также процедур и функций. В отличие от программы, модуль не может быть запущен на выполнение самостоятельно, а может только участвовать в построении другого модуля или программы.

Модуль компилируется предварительно независимо от использующей его программы. Результатом компиляции модуля является файл с расширением.TPU(Turbo Pascal Unit). Для того, чтобы подключить модуль к программе(или к другому модулю) следует указать его в директиве USES.

Все системные библиотеки Турбо-Паскаля реализованы как модули и чтобы ими воспользоваться, нужно указать директиву:

Uses

CRT,DOS,GRAPH;

и далее пользоваться содержимым библиотек CRT,DOS,GRAPH, как будто оно определено в языке.