Однонаправленные (линейные) списки. Описание, создание, просмотр списка, добавление и удаление элементов

ELSE

END

END

BEGIN

ELSE

END

BEGIN

BEGIN

BEGIN

VAR

BEGIN

ELSE

END

BEGIN

BEGIN

BEGIN

ELSE

BEGIN

VAR

BEGIN

BEGIN

TYPE

POINT=^ZAP;

ZAP=RECORD

INF1: INTEGER; { первое информационное поле }

INF2: STRING; { второе информационное поле }

NEXT:POINT; {ссылочное поле на следующий элемент}

PREV:POINT; {ссылочное поле на предыдущий элемент}

END;

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

Формирование пустого списка.

PROCEDURE CREATE_EMPTY_LIST (VAR FIRST: EL);

FIRST = NIL;

END;

Формирование очередного элемента списка.

PROCEDURE CREATE_NEW_ELEM(VAR P: EL);

NEW (P);

WRITELN ('ВВЕДИТЕ ЗНАЧЕНИЕ ПЕРВОГО ИНФОРМАЦИОННОГО ПОЛЯ: ');

READLN (P^.INF1);

WRITELN ('ВВЕДИТЕ ЗНАЧЕНИЕ ВТОРОГО ИНФОРМАЦИОННОГО ПОЛЯ: ');

READLN (P^.INF2);

P^.NEXT:= NIL;

{ ВСЕ ПОЛЯ ЭЛЕМЕНТА ДОЛЖНЫ БЫТЬ ИНИЦИАЛИЗИРОВАНЫ }

END;

Подсчет числа элементов списка

FUNCTION COUNT_EL(FIRST:EL):INTEGER;

K: INTEGER;

Q: EL;

IF FIRST = NIL THEN

K:=0 { СПИСОК ПУСТ }

BEGIN {СПИСОК СУЩЕСТВУЕТ}

K:=1; {В СПИСКЕ ЕСТЬ ХОТЯ БЫ ОДИН ЭЛЕМЕНТ}

Q:=FIRST;

{ПЕРЕБОР ЭЛЕМЕНТОВ СПИСКА НАЧИНАЕТСЯ С ПЕРВОГО}

WHILE Q^.NEXT <> NIL DO

K:=K+1;

Q:=Q^.NEXT;

{ПЕРЕХОД К СЛЕДУЮЩЕМУ ЭЛЕМЕНТУ СПИСКА}

END;

END;

COUNT_EL:=K;

END;

Вставка элемента в начало списка.

PROCEDURE INS_BEG_LIST(P: EL; {АДРЕС ВКЛЮЧАЕМОГО ЭЛЕМЕНТА}

VAR FIRST: EL);

IF FIRST = NIL THEN

FIRST:= P;

P^.NEXT:= NIL

P^.NEXT:=FIRST;{ССЫЛКА НА БЫВШИЙ ПЕРВЫМ ЭЛЕМЕНТ}

FIRST:=P;{ ВКЛЮЧАЕМЫЙ ЭЛЕМЕНТ СТАНОВИТСЯ ПЕРВЫМ }

END;

END;

Удаление элемента из начала списка

PROCEDURE DEL_BEG_LIST (VAR FIRST: EL);

P: EL;

ANSWER: STRING;

IF FIRST <> NIL THEN

BEGIN { СПИСОК НЕ ПУСТ }

WRITELN ('ВЫ ХОТИТЕ УДАЛИТЬ ПЕРВЫЙ ЭЛЕМЕНТ?(ДА/НЕТ) ');

READLN (ANSWER);

IF ANSWER = 'ДА' THEN

P:=FIRST;

IF P^.NEXT = NIL THEN {В СПИСКЕ ОДИН ЭЛЕМЕНТ }

DISPOSE (P); {УНИЧТОЖЕНИЕ ЭЛЕМЕНТА}

FIRST:=NIL; {СПИСОК СТАЛ ПУСТЫМ }

P:= FIRST;{АДРЕС УДАЛЯЕМОГО ЭЛЕМЕНТА }

FIRST:=FIRST^.NEXT;

{АДРЕС НОВОГО ПЕРВОГО ЭЛЕМЕНТА}

DISPOSE(P);

{УДАЛЕНИЕ БЫВШЕГО ПЕРВОГО ЭЛЕМЕНТА }

END;

WRITELN (' СПИСОК ПУСТ, УДАЛЕНИЕ ПЕРВОГО ЭЛЕМЕНТА НЕВОЗМОЖНО');

END;

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

Список - структура данных, в которой каждый элемент имеет информационное поле (поля) и ссылку (ссылки), то есть адрес (адреса), на другой элемент (элементы) списка. Список - это так называемая линейная структура данных, с помощью которой задаются одномерные отношения.

Каждый элемент списка содержит информационную и ссылочную части.

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

Ссылки однотипны, но число их может быть различным в зависимости от типа списка. В связи с этим для описания элемента списка подходит только тип «запись», так как только этот тип данных может иметь разнотипные поля.

В зависимости от числа ссылок список называется одно-, двунаправленным…

В однонаправленном списке каждый элемент содержит ссылку на последующий элемент. Если последний элемент списка содержит «нулевую» ссылку, то есть содержит значение предопределенной константы NIL и, следовательно, не ссылается ни на какой другой элемент, такой список называется линейным.

Для доступа к первому элементу списка, а за ним - и к последующим элементам необходимо иметь адрес первого элемента списка. Этот адрес обычно записывается в специальное поле - указатель на первый элемент, дадим ему специальное, «говорящее» имя - FIRST. Если значение FIRST равно NIL, это значит, что список пуст, он не содержит ни одного элемента. Оператор FIRST:= NIL; должен быть первым оператором в программе работы со списками. Он выполняет инициализацию указателя первого элемента списка, иначе говоря, показывает, что список пуст. Всякое другое значение будет означать адрес первого элемента списка.

Формирование пустого списка.

PROCEDURE CREATE_EMPTY_LIST (VAR FIRST: EL);

Дата добавления: 2015-04-24