Нелинейные списки (структуры)

Begin

Begin

Begin

Описание элемента списка

type pt=^elem; {указатель на этот список}

elem= record

data: integer; {поле данных}

next: pt; {указатель на следующий элемент}

end;

var first: pt; {указатель на первый элемент}

Основные операции:

1) просмотр элемента списка,

2) вставка элемента в список,

3) удаление элемента из списка.

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

procedure InsBegin (var first: pt, el: integer);

var NewFirst: pt;

new (NewFirst); {выделение памяти} (1)

NewFirst^data:=el;

NewFirst^next;=first; {первый элемент становится

вторым по счету} (2)

First:=NewFirst; {новый элемент становится первым}

end;

		First

(3)

Х₄

Х₃

Х₂

Х₁

(1)

(2)

2. Вставка в конец списка

procedure InsEnd (var last: pt; el: integer);

var NewFirst: pt;

new (last^next); {выделение памяти} (1)

last:=last^next; {последний элемент становится

предпоследним} (2)

last^data:=el;

last^next:=nil; {новый становится последним} (3)

end;

(2)

Х₄

Х₃

Х₂

Х₁

(1)

	Р2

(3)

3. Вставка в середину списка

Для того, чтобы вставить элемент в список, необходимо знать адрес предшествующего элемента. Мы считаем, что он не последний. При вставке разрывается существующая связь, и появляются две новые связи.

Ключевая процедура вставки строки имеет вид:

procedure InsertStr (v,w,r: integer; var x:TMyArray);

var i,j: integer;

for i:=v downto r+1 do

for j:=1 to w do

x[i+1,j]:=x[i,j];

for j:=1 to w do

x[r+1,j]:=0;

end;

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

10 марта

СРС: Отладить и принести в электронном варианте программы oсhered и Spisok.

Дата добавления: 2014-01-20