Структури даних для обробки інформації (стр. 2 из 3)
name:string;
next:elem;
end;
var
a1,a:elem;
begin
new(a1);
a1^.name:='Иванов';
a1^.next:=nil;
writeln(a1^.name);
{Добавимо елемент 'Петров' на початок}
writeln('Формування стеку:');new(a);
a^.name:='Петров';
a^.next:=a1;
write(a^.name,' ');
a:=a^.next;
writeln(a^.name);
end.
Результат роботи програми:
Иванов
Формування стеку:
Петров Иванов
Приклад 2. Наступна програма демонструє формування безкінечного стеку.
type
elem=^zapis;
zapis=record
name:string;
next:elem;
end;
var a1,a:elem;
name:string;
begin
repeat
readln(name);
if name<>'' then
begin
new(a);
a^.name:=name;
a^.next:=a1;
a1:=a;
end;
until name='';
while a<>nil do
begin
writeln(a^.name);
a:=a^.next;
end;
end.
Результат роботи програми:
елемент1
елемент2
елемент3
елемент4
елемент5
елемент6
елемент6
елемент5
елемент4
елемент3
елемент2
елемент1
Розглянемо докладніше як працює з попереднього прикладу структура:
new(a);
a^.name:=name;
a^.next:=a1;
a1:=a;
 | ||||
 | ||||
 | ||||
 | ||||
При повторному виконанні вказівок:
new(a);
a^.name:=name;
a^.next:=a1;
a1:=a;
в пам’яті ПК відбудуться наступні перетворення:
Бачимо, що кожен наступний елемент (Name2) встановлюється на початок списку. Останній елемент, який увійде у стек – перший з нього виходить (він буде на першому місці, тобто при читанні стеку, буде першим).
1.3. ЗВ’ЯЗАНИЙ СПИСОК. ЧЕРГА.
Формування черги (вставка елементів в кінець списку).
 | ||
| Список після внесення елемента «Ільчук» в чергу |
 |  |
typeelem=^zapis;
zapis=recordname:string;
next:elem;
end;
var
s1, s, sn:elem;
begin
new(s);
readln(name);
s^.name:=name;
s^.next:=nil;
if s1=nil then s1:=s
else sn^.next:=s;
sn:=s;
end.
В результаті роботи такої програми три вказівника будуть вказувати на перший елемент черги.
При повторному виконанні вказівок
new(s);
readln(name);
s^.name:=name;
s^.next:=nil;
if s1=nil then s1:=s
else sn^.next:=s;
sn:=s;
новий елемент s^ буде добавлено в кінець списку. При цьому s1 буде вказувати на перший елемент списку, а s та sn – на добавлений елемент списку (останній елемент).
Розглянемо на схемі повторну дію згаданих вище вказівок:
 | |||||||
| | |||||||
 | |||||||
 |  | ||||||
ТЕКСТ ПРОГРАМИ ФОРМУВАННЯ ЧЕРГИ:
type
elem=^zapis;
zapis=record
name:string;
next:elem;
end;
var s1, s, sn:elem;
name:string;
BEGIN
s1:=nil; s:=nil;
repeat
new(s);
readln(name);
if name<>’’ then begin
s^.name:=name;
s^.next:=nil;
if s1=nil then s1:=s;
else sn^.next:=s;
sn:=s;
end;
until name=’’;
while s1<>nil do begin
writeln('--',s1^.name);
s1:=s1^.next;
end;
END.
ФОРМУВАННЯ ВПОРЯДКОВАНОГО СПИСКУ.
S1 – вказівник на перший елемент списку
S_new – вказівник на новий елемент списку
S_p – вказівник на елемент, після якого необхідно здійснити вставку нового елемента
Buf – деякий допоміжний вказівник на елемент, який проглядається в процесі пошуку місця для вставки нового елемента.
type
elem=^spisok;
spisok=record
name:string;
next:elem;
end;
var
s1,s_new,buf,s_p:elem;
BEGIN
s1:=nil;s_new:=nil;buf:=nil;
repeat
new(s_new);
readln(s_new^.name);
s_p:=nil;
buf:=s1;
if s_new^.name<>'' then
begin
while (buf^.name<s_new^.name)and(buf<>nil) do
begin
s_p:=buf;
buf:=buf^.next;
if s_p=nil then
begin
s_new^.next:=s1;
s1:=s_new;
end
else
begin
s_new^.next:=s_p^.next;
_p^.next:=s_new;
end;
end;
until s_new^.name='';
while s1<>nil do
begin
writeln('--',s1^.name);
s1:=s1^.next;
end;
END.
ВИДАЛЕННЯ ЕЛЕМЕНТА ЗІ СПИСКУ
Якщо у деякому сформованому списку вказівник s_1 вказує на перший елемент списка, то програмний код знищення елементів, що вводяться з клавіатури (якщо він присутній у списку, то нехай buf – це вказівник на елемент, що знаходиться перед ним) , може мати наступний вигляд:
{Формування списку}
repeat
writeln('Введите элемент, который хотите уничтожить со списка:’);
readln(name);
if name<>'' then
begin
if s1^.name=name then s1:=s1^.next
else
begin
buf:=s1;
while (buf^.next^.name<>name)and(buf^.next<>nil) do buf:=buf^.next;
if buf^.next^.name=name then buf^.next:=buf^.next^.next;
end;
end;
until name='';
ОБЕРНЕННЯ ЕЛЕМЕНТІВ СПИСКУ (ЗМІНЕННЯ НАПРЯМКІВ УСІХ ВКАЗІВНИКІВ НА ПРОТИЛЕЖНИЙ)
1 спосіб (шляхом «переміщення» кожного елемента списку, починаючи з другого, на його початок)
Зауваження! Під переміщенням елемента розуміємо не фізичне переміщення його на початок списку. На початок списку «направляємо» лише вказівник елемента, який з даного списка видаляється.
S_1 – вказівник на перший елемент списку
S – вказівник на поточний елемент списку
Buf – вказівник на наступний за поточним елементом (на елемент що переміщається на початок списку
s:=s_1;
buf:=s_1;
while s^.next<>nil do
begin
buf:=s^.next;
s^.next:=s^.next^.next;
buf^.next:=s_1;
s_1:=buf;
end;
2 спосіб (шляхом зміни напрямків вказівників на протилежний)
S_1 – вказівник на перший елемент списку
S – вказівник на поточний елемент списку
Left – вказівник на елемент, що знаходиться лівіше від поточного
Right – вказівник на елемент, що знаходиться правіше від поточного
right:=s_1;
s:=nil;
repeat
left:=s;
s:=right;
right:=right^.next;
s^.next:=left;
until right=nil;
РОЗДІЛ ІІ. ДЕРЕВА. БІНАРНЕ ДЕРЕВО
Деревом називається динамічна структура, у якій кожен вузол містить не один, а декілька вказівників на декілька інших вузлів.
Кореневий вузол (корінь дерева) – це самий верхній вузол (вузол a – кореневий) . Якщо з деякого вузла (наприклад, вузла а) вказівники вказують на інші вузли (в нашому випадку на вузли b та c), то такий вузол називають предком. Вузли ж на які вказують вказівники від предка називаються потомками.Все сказане вище ілюструє малюнок 1, якщо його розглянути то можна зробити висновки про те, що:
· Лівий потомок вузла а – вузол b
· Правий потомок – вузол c.
· Вузли b та c мають спільного предка – вузол а
Якщо вузол не має потомків, то такий вузол називають листком дерева, тому згідно малюнка вершини d, g та f – є листками.
Дерево, кожен вузол якого не може мати більше двох потомків називається бінарним.
2.1. РЕАЛІЗАЦІЯ БІНАРНОГО ДЕРЕВА ЗА ДОПОМОГОЮ ДИНАМІЧНИХ ЗМІННИХ
Розглянемо динамічну змінну b, що має таку структуру, як показано на малюнку 2. А саме, змінна b є записам з 5 полів:
Parent –вказівник на предка
Left – вказівник на лівого потомка
Right – вказівник на правого потомка
Data – поле даних (наприклад, прізвище)
Key – ключ (цілочисельне значення), по якому ідентифікується елемент.
Тип такої динамічної змінної виглядає наступнич чином:
type
BinarTree=^node;
node=record
key:integer;
data:string;
left,right,
parent:BinarTree;
end;
Сформуємо дерево керуючись таким принципом: ключ кожного лівого потомка менший за ключ предка, а ключ правого потомка – більший або рівний ключа предка.
Наприклад, бінарне дерево з трьох вузлів (Іванов (ключ=5), Петров (ключ=3) та Сидоров (ключ=8)) має вигляд як показано на мал.3. Добавимо в дерево елемент Ільїн з ключем 6. Цей елемент буде лівим потомком елемента Сидоров (так як 6>5 та 6<8). Якби ключ елемента Ільїн був рівний 4, то він був би правим потомком елемента Петров (бо 4<5 та 4>3)