Основы программирования. Указатели. Динамические структуры данных. Абстрактные типы данных. Классы - 19 стр.

UptoLike

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

Рубрика:

function NewNode(data: integer; next: PNode): PNode;

begin

New(Result);

Result^.data:=data;

Result^.next:=next;

end;

Основными действиями с линейным односвязным списком являются вставка,

удаление, поиск элементов, проход по списку и сортировка. Будем считать, что во

всех приводимых операциях указатель p типа PNode хранит адрес текущего эле-

мента списка.

Если поле данных data элемента списка содержит значение x, то для про-

стоты

будем говорить, что элемент или узел имеет значение x.

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

Пусть первый элемент является текущим (указатель p хранит адрес первого

элемента):

3 5 7

Создадим новый элемент со значением x, поле next которого указывает на пер-

вый элемент, после чего сделаем этот элемент первым, присвоив его адрес указа-

телю p:

p:=NewNode(x,p);

3 5 7

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

(p=nil). При многократном ее выполнении происходит заполнение списка, при-

чем, элементы в списке будут располагаться в порядке, обратном порядку их

включения.

2. Удаление элемента из начала непустого списка.

3 5 7

Запомним адрес первого элемента в переменной t, после чего переместим

указатель на первый элемент вперед и освободим элемент, контролируемый ука-

зателем t: