Кольцевые, циклические списки. Описание, создание, просмотр списка, добавление и удаление элементов

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 заменяется на адрес первого элемента списка.

Действия со списками:

Описание элемента двунаправленного списка

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