Однонаправленные списки и операции над ними
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;