Однонаправленные списки и операции над ними

End.

Begin

Пример 3.

Составить программу, которая в вещественном массиве с 1500 элементами находит элемент, номер которого равен наибольшему значению массива, состоящему из 3000 целых чисел.

Алгоритм решения.

1) организуем динамический массив из целых чисел [1..3000]

2) найдем в нем наибольший элемент к

3) освободим память от этого массива и создадим динамический массив действительных чисел

4) найдем элемент в этом массиве, номер которого равен к.

program ex3;

uses crt;

type ra=array[1..1500]of real;

ia=array[1..3000] of integer;

var k,i:integer;

p:^ra;q:^ia;

clrscr; randomize; k:=0;

new(q);

for i:=1 to 30 do

begin

q^[i]:=random(15)+6; write(q^[i]:4);

if q^[i]>k then k:=q^[i];

end;

writeln; writeln;

writeln('k= ',k); dispose(q);

new(p);

for i:=1 to 30 do

begin

p^[i]:=random(15)+random; write(p^[i]:5:1);

end;

writeln; writeln;

writeln('iskom element = ', p^[k]:4:1);

readkey;

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

Структура «однонаправленный список» строится подобно очереди на прием к врачу: клиенты сидят на любых свободных местах, но каждый из них знает, за кем он стоит (т.е. данные размещаются на свободных местах в памяти, но каждый элемент содержит ссылку на предыдущий или следующий элемент).

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

Каждое звено списка обычно является записью, состоящей из двух частей:

1. информационная часть (одно или несколько полей). Если р - ссылка на звено, то p^.имя поля1, p^.имя поля2, … - имена полей такого звена.

2. Ссылочная часть содержит ссылку на следующее (или предыдущее) звено списка.

Описание списка.

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

Type te=тип инф.части;

Ss=^zveno; {ссылка на звено}

Zveno =record {звено}

Inf: te; {информационная часть}

Sled:ss {ссылочная часть}

End;

Var p,u:ss;

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