Динамічні структури даних
Створення динамічних структур та списку шляхом додавання елементів в кінець списку, шляхом вставляння елемента в середину списку. Відмінності стека від списку, основні операції із стеком. Формування та основні операції над кільцем, обхід кільця.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | реферат |
| Язык | украинский |
| Дата добавления | 07.09.2011 |
| Размер файла | 170,8 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru
Размещено на http://www.allbest.ru
Список. Створення списку шляхом додавання елементів в кінець списку. Проглядання списку
Списком називається структура даних, кожний елемент якої за допомогою покажчика зв'язується з наступним елементом.
З визначення виходить, що кожний елемент списку містить поле даних (Data) (воно може мати складну структуру) і поле посилання на наступний елемент (Next). Поле посилання останнього елемента повинне містити порожній покажчик (Nil).
Схематично це виглядає так:
Спробуємо разом сформувати невеликий список шляхом додавання елементів в кінець списку.
Задача. Сформувати список, що містить цілі числа 3, 5, 1, 9.
Для цього спочатку визначимо запис типу S з двома полями. В одному полі міститимуться деякі дані (в нашому випадку числа 3, 5, 1 і 9), а в другому полі буде знаходиться адреса наступного за ним елемента.
Примітка. Потрібно розуміти, що поле даних взагалі кажучи може містити в собі скільки завгодно полів; це залежить від конкретно поставленої задачі.
Type
Ukazatel = ^S;
S = Record
Data: integer;
Next: Ukazatel;
End;
Таким чином, ми описали вказівниковий тип, за допомогою якого можна створити наш зв'язаний однонаправлений список.
Помітимо, що всі елементи списку взаємозв'язані, тобто де знаходиться наступний елемент, "знає" тільки попередній. Тому найголовніше в програмі, це не втратити, де знаходиться початок списку. Тому на початок списку ставитимемо покажчик з ім'ям Head і стежитимемо за тим, щоб протягом виконання програми значення цього покажчика не мінялося.
А зараз опишемо змінні для вирішення нашої задачі:
динамічний структура список стек кільце
Var
Head {покажчик на початок списку}
x {допоміжний покажчик для створення чергового елемента списку}
: Ukazatel;
Створимо перший елемент:
New(x); {виділимо місце в пам'яті для змінної типу S}
x^.Data:= 3; {заповнимо поле Data першого елемента}
x^.Next:= Nil; {заповнимо поле Next першого елемента: покажчик в Nil}
Head:= x; {поставимо на наш перший елемент покажчик голови списку}
Таким чином, до виділеної області пам'яті можна звернутися через два покажчики.
Продовжимо формування списку, для цього потрібно додати елемент в кінець списку. Тому допоміжна змінна вказівного типу х зберігатиме адресу останнього елемента списку. Зараз останній елемент списку співпадає з його початком.
Тому можна записати рівність:Head^.Next = x^.Next;
Head^.Data = x^.Data;
Head = x;
Виділимо область пам'яті для наступного елемента списку.
New(x^.Next);
Присвоїмо змінній х значення адреси виділеної області пам'яті, інакше, переставимо покажчик на знову виділену область пам'яті:
x:= x^.Next;
Визначимо значення цього елемента списку, інакше, заповнимо поля:
x^.Data:= 5;
x^.Next:= Nil;
Отже, тепер у нас список містить два елементи. Зрозуміло, щоб створити третій і четвертий елементи, потрібно виконати ті ж самі операції.
Тепер спробуємо підсумувати наші міркування.
Оформимо створення списку у вигляді процедури, в якій його елементи вводяться з клавіатури.
Procedure Init(Var u: Ukazatel);
Var
x: Ukazatel;
Digit: integer; {Значення інформаційної частини елемента списку}
Begin
Writeln('Введіть список ');
Head:= Nil; {Список порожній}
Writeln ('Введіть елементи списку. Кінець введення 0');
Read (Digit);
if Digit <> 0
then {Формуємо і вставляємо перший елемент списку}
Begin
New(x);
x^.Next:= Nil;
x^.Data:= Digit;
Head:= x
Read (Digit);
while Digit<>0 do
Begin
New(x^.Next); {Формуємо і вставляємо елемент в кінець списку}
x:= x^.Next;
x^.Next:= Nil;
x^.Data:= Digit;
Read(Digit);
End;
Writeln;
End;
Розгляньте формування списку дещо іншим способом.
Procedure Init(Var u: Ukazatel);
Var
x, у: Ukazatel;
Digit: integer;
Begin
Writeln('Введіть список ');
Head:= Nil;
Writeln ('Введіть елементи списку. Кінець введення 0');
Read (Digit);
while Digit<>0 do
Begin
New(y);
y^.Next:= Nil;
y^.Data:= Digit;
if u=Nil
then
u:= у
else
x^.Next:= у;
x:= у;
Read(Digit);
End;
Writeln;
End;
Проглядання списку
Проглядання елементів списку здійснюється послідовно, починаючи з його початку. Покажчик р послідовно посилається на перший, другий, і т.д. елементи списку до тих пір, поки весь список не буде пройдений. При цьому з кожним елементом списку виконується операція виводу на екран. Початкове значення р - адреса першого елемента списку p^. Якщо р вказує на кінець списку, то його значення рівно Nil, тобто while p<>Nil do
Begin
Write(p^.Data, ' ');
p:= p^.Next;
End.
Створення списку шляхом вставляння елементів.
Завдання. Шляхом додавання елемента в початок списку отримати список, зображений на малюнку:
Цю задачу Ви вирішите самі трохи пізніше, а зараз розглянемо як додати в цей список деякий елемент, наприклад 2. Тобто отримати такий список:
Виконаємо наступні дії:
New(x); {Створення нової динамічної змінної}
x^.Data:= 2; {Інформаційне поле створеного елемента}
x^.Next:= Head; {Приєднаємо елементи списку до створеного елемента}
u:= x; {Змінимо значення покажчика початку списку}
Отже, потрібний елемент вставлений. Тепер Ви можете сформувати весь даний список повністю.
Впорядковування списку. Вставляння елемента в середину списку.
Сформуємо список цілих чисел впорядкований по зростанню, тобто кожний наступний елемент списку повинен бути більшим або рівним попередньому.
Для вирішення цієї задачі розглянемо основні частини алгоритму, який ми втілюватимемо в програмі.
Після введення чергового числа з клавіатури визначаємо його місце в списку. Помітимо, що при цьому елемент може бути вставлений або в початок списку, або в кінець його, або у середину. Перший і другий випадки ми вже розглянули вище. Зупинимося на третьому випадку.
Для того, щоб вставити в список елемент із значенням Digit між двома елементами, потрібно знайти ці елементи і запам'ятати їх адреси (перша адреса - в змінній dx, другій - в рх), після чого встановити нові зв'язки із змінною, в якій зберігається значення Digit.
Графічно це можна представити так:
Оператори, що виконують дану задачу будуть наступними:
New(x);
x^.Data:= Digit;
px^.Next:= x;
x^.Next:= dx;
Приведемо процедуру InsInto, яка шукає місце в списку і вставляє елемент, переданий їй як параметр. В результаті відразу виходить впорядкований список. Адреса першого елемента списку зберігається в глобальній змінній Head.
Procedure InsInto(Digit: integer; Var Head: Ukazatel);
Var
dx, px, x: Ukazatel;
Begin
New(x);
x^.Data:= Digit;
x^.Next:= Nil;
if Head = Nil
then {Якщо список порожній, то вставляємо перший елемент}
Head:= x
else
{Якщо список не порожній, то проглядаємо його до тих пір, поки не відшукається відповідне місце для x^ або не закінчиться список}
Begin
dx:= Head;
px:= Head;
while (px<>Nil) and (px^.Data<=Digit) do
Begin
dx:= px;
px:=px^.Next;
End;
if px=Nil
then {Пройдений весь список}
dx^.Next:= x {Елемент додається в кінець списку}
else {Пройдений не весь список}
Begin
x^.Next:= px;
if px=Head
then
Head:= x {Вставляємо в початок списку}
else
dx^.Next:= x; {Вставляємо всередину списку}
End;
End;
End;
Приклади задач, вирішуваних за допомогою списку.
Задача 1. Перевірити чи є і скільки разів зустрічається список М1 в списку М2.
Program BaranovA;
Uses
Crt;
Type
EXS = ^ S;
S = Record
Data: integer;
Next: EXS;
End;
Var
u, x, m1, m2: EXS;
i, Kol: integer;
Procedure Poisk(Var x1, x2: EXS);
Var
m3, m4: EXS;
Begin
Kol:= 0;
m3:= m1;
m4:= m2;
while m4 <> Nil do
Begin
if m4^.Data = m3^.Data
then
Begin
m3:= m3^.Next;
m4:= m4^.Next;
if m3 = Nil
then
Begin
Kol:= Kol+1;
m3:= m1;
End;
End;
else
Begin
m3:= m1;
m4:= m4^.Next;
End;
End;
End;
Procedure Init (Var u: EXS);
Var
у: EXS;
Digit: integer;
Begin
Writeln('Введіть список. Кінець введення - 0');
u:= Nil;
Read(Digit);
while Digit <> 0 do
Begin
New(y);
y^.Next:= Nil;
y^.Data:= Digit;
if u = Nil
then
u:= у
else
x^.Next:= у;
x:= у;
Read(Digit);
End;
Writeln;
End;
Procedure Print(X: EXS);
Begin
while X <> Nil do
Begin
Write(X^.Data: 5);
X:= X^.Next;
End;
Readln;
Writeln;
End;
Begin
ClrScr;
Init(m1);
Init(m2);
Writeln('***Список 1***');
Print(m1);
Writeln('***Список 2***');
Print(m2);
Poisk(m1, m2);
Writeln('Список 1 зустрічається в списку 2 ', Kol, ' разів (и)');
Readln;
End.
Задача 2. З текстового файлу, що складається з рядків, сформувати список, знайти слово і видалити це слово із списку.
Program;
Uses
Crt;
Type
EXS = ^ Spisok;
Spisok = Record
Data: string;
Next: EXS;
End;
Var
Golova_Spiska, Golova_Spiska_Udalen_: EXS;
F: text;
S, St: string;
Procedure Smotr(x: EXS);
Begin
TextColor(LightRed);
Write('Ваш список...');
while x <> Nil do
Begin
Writeln (x^.Data,' ');
x:= x^.Next;
End;
End;
Procedure Reading;
Begin
Reset (F);
Writeln('Ваш файл...');
while no Eof(F) do
Begin
Readln (F, St);
Writeln (St);
End;
close (F);
End;
Procedure CreateFile;
Begin
Writeln('Створення файлу');
Write('Введіть ім'я файлу...');
Readln(S);
Assign (F, S);
rewrite('Вводите текст у файл (закінчення введення - <Enter>');
Repeat
Readln(St);
Writeln (F, St);
until St = '';
Write('Файл створений');
close (F);
Reading;
End;
Procedure Proverka;
Var
x, у, u: EXS;
i: integer;
Begin
Reset (F);
while not Eof (F) do
Begin
Readln (F, St[i]);
while i < Length (St) do
Begin
New (x);
x^.Next:= Nil;
if (St[i]<> ' ') or (St[i]<> St[Length(St)])
then
x^.Data:= x^.Data + St[i];
if u = Nil
then
u:= x
else
y^.Next:= x;
у:= x;
End;
End;
close (F);
Smotr (u);
End;
Begin
ClrScr;
TextColor (White);
CreateFile;
Proverka;
End.
Видалення елементу із списку
Тому для вирішення поставленої перед нами задачі видалення деякого елемента із списку, нам потрібно знайти по якій-небудь ознаці цей елемент, що, сподіваюся не складе для Вас труднощів.
Уточнимо поставлену перед нами задачу: видалити із списку елемент із заданою інформаційною частиною.
Позначимо Head - початковий список, Digit - значення інформаційної частини елемента, що видаляється.
При дослідженні списку на наявність в ньому заданого елемента може зустрітися три різні випадки. Розглянемо їх.
Видалення елемента з початку списку
Зобразимо видалення графічно:
Напишемо фрагмент програми:
x:= Head; {Запам'ятаємо адресу першого елемента списку}
Head:= Head^.Next; {Тепер Head указує на другий елемент списку}
Dispose(x); {Звільнимо пам'ять, зайняту змінній x^}
Видалення елемента з середини списку
Для цього потрібно знати адреси елемента і елемента, що знаходиться в списку перед ним, що видаляється.
Зобразимо видалення графічно:
x:= Head; {Змінна х для зберігання адреси елемента, що видаляється}
{Знайдемо адреси потрібних елементів списку}
while (x<>Nil) and (x^.Data<>Digit) do
Begin
dx:= x;
x:= x^.Next
End;
dx^.Next:= x^.Next;
Dispose(x);
Видалення елемента з кінця списку
Видалення елемента з кінця списку проводиться, коли покажчик dx показує на передостанній елемент списку, а х - на останній.
Зобразимо видалення графічно:
{Знайдемо передостанній елемент}
x:= Head;
dx:=Head;
while x^.Next<>Nil do
Begin
dx:= x;
x:= x^.Next;
End;
{Видаляємо елемент x^ із списку і звільняємо пам'ять, яку він займав}
dx^.Next:= Nil;
Dispose(x);
Тепер опишемо процедуру видалення елементів із списку в загальному випадку:
Procedure Del(Gigit: integer; Var u: Ukazatel);
Var
x, dx: UKAZATEL;
Begin
x:= Head;
while x<>Nil do
if x^.Data=Digit
then
Begin
if x=y
then
Begin
Head:= Head^.Next;
Dispose(x);
x:= Head;
End;
else
Begin
dx^.Next:= x^.Next;
Dispose(x);
x:= dx^.Next;
End;
End;
else
Begin
dx:= x;
x:= x^.Next;
End;
End;
Стек. Відмінності стека від списку. Основні операції із стеком
В програмуванні структурою, що часто використовується, є стек.
Стек - це лінійний список, в якому додавання нових елементів і видалення існуючих проводиться тільки з одного кінця, званого вершиною стека.
Стек часто називають структурою LIFO [скорочення LIFO означає Last In - First Out (останній прийшов, перший вийшов)]. Це скорочення представляє зручний спосіб запам'ятати механізм роботи стека
Зображений стек графічно:
При програмуванні на Паскалі стек реалізується частіше за все у вигляді однонаправленого списку. Кожний елемент структури містить покажчик на наступний. Вважається лише, що для цього списку не існує обхід елементів. Доступ можливий тільки до верхнього елемента структури.
Стек припускає вставку і видалення елементів, тому він є динамічною, постійно змінною структурою.
Стеки досить часто зустрічаються в практичному житті. Простий приклад: дитяча піраміда. Процес її збірки і розбирання подібний процесу функціонування стека.
Отже, якщо стек - це список, то додавання або витягання елементів відбувається з початку і лише з початку (або можливо з кінця і лише з кінця) списку.
Значенням покажчика, що представляє стек, є посилання на вершину стека, кожний елемент стека містить поле посилання.
Таким чином, описати стек можна таким чином:
Type
EXST = ^ST;
ST = record
Data: integer;
Next: EXST;
end;
Var
Stack: EXST; {Поточна змінна}
Якщо стек порожній, то значення покажчика рівно Nil.
Розглянемо можливі операції із стеком.
Занесення елемента в стек
Занесення елемента в стек проводиться аналогічно вставці нового елемента в початок списку. Процедура занесення елемента в стек повинна містити два параметри: перший задає вершину стека, в який потрібно занести елемент, другий - значення елемента стека, що заноситься.
Процедура формування стека матиме наступний вигляд:
Procedure FormStack;
Var
Stack: EXST; {Поточна змінна}
Digit: integer;
Procedure writeStack(Var u: EXST; Digit: integer);
Var
x: EXST;
Begin
new(x); {виділяємо пам'ять під зберігання нового елемента стека}
x^.Data:= Digit; {заповнюємо поле даних елемента}
x^.Next:= u; {новий елемент "пов'язуємо" із стеком}
u:= x; {створений елемент визначаємо як вершину стека}
End;
Begin
Stack:= Nil; {ініціалізація стека}
writeln('Введіть елементи стека. Закінчення введення - 0');
read(Digit);
while Digit <> 0 do
begin
writeStack(Stack, Digit);
read(Digit);
end;
End;
Вилучення елемента із стека
В результаті виконання цієї операції деякої змінної i повинне бути привласнено значення першого елемента стека і значення покажчика на початок списку повинне бути перенесений на наступний елемент стека.
Procedure readStack(Var u: EXST; Var i: integer);
Var
x: EXST;
Begin
i:= u^.Data; {прочитуємо значення поля даних в змінну}
x:= u; {запам'ятовуємо адресу вершини стека}
u:= u^.Next; {переносимо вершину стека на наступний елемент}
dispose(x); {звільняємо пам'ять, зайняту вже непотрібним елементом стека}
End.
Недоліком описаної процедури є припущення про те, що стек не порожній. Для його виправлення слід розробити логічну функцію перевірки порожності оброблюваного стека.
Function FreeStack(u: EXST): boolean;
Щоб наочно розглянути роботу стека, наберіть наступну програму.
Program D1;
Uses
Crt, Graph;
Type
sp=^spis;
spis=record
elem: byte;
next: sp;
End;
Var
а, b: byte;
s: string;
gd, gm, с: integer;
head, some, x: sp;
bol: boolean;
ch: char;
Procedure OutX(x, у: integer);
Begin
Line(x+50,y+10,x+70,y+10);
Line(x+50,y+10,x+55,y+10-3);
Line(x+50,y+10,x+55,y+10+3);
Line(x+55,y+13,x+55,y+10-3);
OutTextXY(x+70,y+10,'x');
End;
Procedure Wiv (x, у: integer; ss: sp);
Begin
Line(x,y,x+50,y);
Line(x,y,x,y+20);
Line(x,y+20,x+50,y+20);
Line(x+50,y,x+50,y+20);
Line(x+30,y,x+30,y+20);
if some=ss
then
Begin
Line(x+50,y+10,x+70,y+10);
Line(x+50,y+10,x+55,y+10-3);
Line(x+50,y+10,x+55,y+10+3);
Line(x+55,y+13,x+55,y+10-3); End;
Str(ss^.elem, s);
OutTextXY(x+10,y+10,s);
if (ss^.next<>nil)
then
Begin
Line(x+40,y+10,x+40,y+40);
Line(x+40,y+40,x+37,y+40-5);
Line(x+40,y+40,x+43,y+40-5);
Line(x+43,y+40-5,x+37,y+40-5);
Wiv(x,y+40,ss^.next);
End
else
Begin
Line(x+40,y+10,x+40,y+30);
Line(x+40,y+30,x+37,y+25);
Line(x+40,y+30,x+43,y+25);
Line(x+43,y+25,x+37,y+25);
Line(x+35,y+32,x+45,y+32);
Line(x+36,y+35,x+44,y+35);
Line(x+38,y+38,x+42,y+38);
End;
End;
Procedure Insertsp(x: byte);
Begin
Cleardevice;
OutTextXY(50,20,'NEW(X)');
new(some);
Line(20,100,20+50,100);
Line(20,100,20,100+20);
Line(20,100+20,20+50,100+20);
Line(20+50,100,20+50,100+20);
Line(20+30,100,20+30,100+20);
Outx(20,100);
if head<>nil
then
Wiv(20,140,head);
Delay(1000);
Cleardevice;
OutTextXY(50,20,'X^.NEXT:=TAIL');
OutTextXY(50,40,'TAIL:=X');
some^.next:=head;
head:=some;
Wiv(20,100,head);
Delay(1000);
Cleardevice;
Str(x,s);
OutTextXY(50,20,'SOME^.ELEM:='+s);
some^.elem:=x;
Wiv(20,100,head);
Delay(1000);
End;
Procedure DelSp;
Begin
Cleardevice;
if head=nil
then
Begin
У(50,20,'Элемент не існує!');
Delay(1000);
End
else
if head^.next<>nil
then
Begin
OutTextXY(50,20,'X:=TAIL');
OutTextXY(50,40,'TAIL:= TAIL^.NEXT');
some:=some^.next;
Wiv(20,100,head);
OutX(20,100);
Delay(1000);
Cleardevice;
OutTextXY(50,20,'DISPOSE(X)');
Wiv(20,100,head);
OutX(20,100);
Setcolor(red);
Line(20,90,70,130);
Line(70,90,20,130);
Setcolor(white);
Delay(1000);
Cleardevice;
head:=head^.next;
some:=head;
Wiv(20,100,head);
End
else
Begin
OutTextXY(50,20,'DISPOSE(TAIL)');
Wiv(20,100,head);
Setcolor(red);
Line(20,90,70,130);
Line(70,90,20,130);
Setcolor(white);
Delay(1000);
ClearDevice;
head:=nil;
some:=head;
End;
End;
Begin
ClrScr;
bol:=false;
gD:= Detect;
InitGraph(gD, gM,'c:\tp7\bgi\');
TextBackGround(black);
Setbkcolor(black);
Head:=nil;
Some:=head;
Repeat
OutTextXY(250,200,'1 * Додати елемент');
OutTextXY(250,220,'2 * Видалити елемент');
OutTextXY(250,240,'Esc Вихід');
ch:=readkey;
case ch
'1': Begin
OutTextXY(250,260,'Введіть число:');
gotoxy(48,17);
readln(b);
InsertSp(b);
End;
'2': delsp;
#27: Begin
CloseGraph;
Halt;
End;
End;
until bol;
CloseGraph;
End.
Приклади задач
Приклад 1. Використовуючи стек, надрукувати вміст текстового файлу, виписуючи літери кожного його рядка в зворотному порядку.
Program MordovskihK;
Type
EXST = ^ST;
ST = record
Data: char;
Next: EXST;
End;
Var
Stack: EXST; {Поточна змінна}
i: integer;
f: text;
Stroka: string;
з: char;
Procedure writeStack(Var u: EXST; Simvol: char);
Var
x: EXST;
Begin
new(x);
x^.Data:= Simvol;
x^.Next:= u;
u:= x;
End;
Procedure Print(Var u: EXST);
Begin
while u <> Nil
Begin
write (u^.Data);
u:= u^.Next;
End;
End;
Begin
Stack:= Nil;
Assign(f, 'c:\autoexec.bat');
Reset(f);
while Not Eof(f) do
Begin
readln (f, Stroka);
For i:= 1 to Length(Stroka) do
writeStack(Stack, Stroka[i]);
End;
close(f);
Print(Stack);
End.
Приклад 2. Написати програму, перевіряючу своєчасність закриття дужок в рядку символів.
Для вирішення задачі визначимо стек, елементами якого є символи:
Type
EXST = ^ST;
ST = record
Data: char;
Next: EXST;
End;
Рухатимемося по рядку а: string до її кінця. Якщо в процесі перегляду зустрінеться одна з дужок, що закриваються ({, ([), занесемо її в стек. При виявленні дужки, що закривається, відповідній дужці, що знаходиться у вершині стека, остання віддаляється. При невідповідності дужок видається повідомлення про помилку.
Нехай факт наявності помилки зберігається в змінній логічного типу f, тобто f=True, поки помилка не знайдена і f=False в протилежному випадку. Тоді умова роботи циклу виглядатиме так:
while (i<>Length(a)) and f do...
Залишилося з'ясувати, як визначити, чи відповідає чергова дужка, що закривається, дужці, що знаходиться у вершині стека. Можна помітити, що коди відповідних один одному дужок відрізняються не більше ніж на 2, що можна перевірити за допомогою функції Ord(x)):{ } 123-125
[ ] 91-93
() 40-41
Причому код дужки, що відкривається, менше. Тобто можна записати наступну умову відповідності:
if (Ord(а[i]-Ord(stack^.Data))<=2
then
...
А зараз проглянете повний текст програми:
Program Skobki;
Type
EXST = ^ST;
ST = record
Data: char;
Next: EXST;
end;
Var
а: string;
f: boolean;
i: integer;
Procedure writeStack(Var x1: EXST; з: integer);
Var
u: EXST;
Begin
new(u); {створення нового елемента стека}
u^,Data:= с;
u^.Next:= x1;
x1:= u; {створений елемент визначити як вершину стека}
End;
Procedure DelStack(Var x1: EXST); {процедура видалення верхнього елемента стека}
Var
u: EXST;
Begin
u:= x1;
x1:= x1^.Next;
dispose(u);
End.
Procedure Solve(а: string); {процедура правильності розстановки дужок}
Var
Stack: EXST;
Begin
Stack:= Nil;
i:= 1;
while (i<=Length(a)) and f do
begin
if (а[i]='(') or (а[i]='{') or (а[i]='[')
then
writeStack(Stack, а[i])
else
if (а[i]=')') or (а[i]='}') or (а[i]=']')
then
if Ord(Stack ^.Data)-Ord(а[i])<=2
then
DelStack(Stack)
else
f:= False;
Inc(i);
end;
End.
Begin
writeln('Введіть стрічку');
readln(a);
f:= True;
if a<>' '
then
begin
Solve(a);
if f
then
writeln('Всі дужки розставлені вірно')
else
writeln('Дужка ',a[i-1],' закрита достроково');
end
else
writeln('Стрічка порожня');
readln;
End.
Черги. Основні операції над чергою
Черга - лінійний список, елементи в який додаються тільки в кінець, а видаляються з початку.
Зобразимо чергу графічно:
При програмуванні на Паскалі також вважається, що для черги не існує обхід елементів. Доступ можливий тільки до нижнього елемента структури.
Отже, черга - це вид зв'язаного списку, в якому видалення елементів відбувається з початку списку, а додавання нових елементів - з кінця.
Черга є динамічною структурою - з часом змінюється і її довжина, і набір становлячих її елементів.
Опишемо чергу на мові програмування:
Type
EXO = ^O;
Про = record
Data: integer;
Next: EXO;
end;
Над чергою визначено дві операції: занесення елемента в чергу і видалення елемента з черги.
В черзі, через її визначення, доступні дві позиції: її кінець, куди заносяться нові елементи, і її початок, звідки витягуються елементи. Тому для роботи з чергою необхідно описати дві змінні:
Var
BeginO, EndO: EXO;
де BeginO - відповідає початку черги і використовуватиметься для виводу елемента з черги, EndO - відповідає кінцю черги і використовуватиметься для додавання нових елементів в чергу.
Занесення елемента в чергу
Занесення елемента в чергу відповідає занесенню елемента в кінець списку. Розгляньте процедуру, описану нижче.
Procedure writeO(Var BeginO, EndO: EXO; с: integer);
Var
u: EXO;
Begin
new(u);
u^.Data:= с;
u^Next:= Nil;
if BeginO =Nil {перевіряємо чи порожня черга}
then
BeginO:= u {ставимо покажчик початку черги на перший створений елемент}
else
EndO^.Next:= u; {ставимо створений елемент в кінець черги}
EndO:= u; {переносимо покажчик кінця черги на останній елемент}
End;
Видалення елемента з черги
Процедура видалення елемента з черги аналогічна видаленню елемента з початку списку. Оскільки видалення елемента з порожньої черги здійснити не можна, опишемо логічну функцію, перевіряючу, чи є елементи в черзі.
Procedure readO(Var BeginO, EndO: EXO; Var с: integer);
Var
u: EXO;
Function FreeO(x1: EXO): boolean;
Begin
FreeO:= (x1=Nil);
End;
Begin
if FreeO(BeginO)
then
writeln('Очередь пуста');
else
begin
с:= BeginO^.Data; {прочитуємо шукане значення в змінну с}
u:= BeginO; {ставимо проміжний покажчик на перший елемент черги}
BeginO:= BeginO^.Next;{покажчик початку переносимо на наступний елемент}
dispose(u); {звільняємо пам'ять, зайняту вже непотрібним першим елементом}
end;
End;
Щоб наочно розглянути роботу черги, наберіть наступну програму.
Program D2;
Uses
Crt, Graph;
Type
sp=^spis;
spis=record
elem: byte;
next: sp;
End;
Var
а
b: byte;
s: string;
gd, gm, з: integer;
head, some, x: sp;
bol: boolean;
ch: char;
Procedure OutHead(x, у: integer);
Begin
Line(x+20,y+35,x+20,y+20);
Line(x+20,y+20,x+17,y+25);
Line(x+20,y+20,x+23,y+25);
Line(x+23,y+25,x+17,y+25);
OutTextXY(x+6, y+38, 'head');
End;
Procedure OutX(x, у: integer);
Begin
Line(x+40,y-15,x+40,y);
Line(x+40,y,x+37,y-5);
Line(x+40,y,x+43,y-5);
Line(x+43,y-5,x+37,y-5);
OutTextXY(x+28,y-25,'x');
End;
Procedure wiv(x,y:integer;ss:sp);
Begin
Line(x,y,x+50,y);
Line(x,y,x,y+20);
Line(x,y+20,x+50,y+20);
Line(x+50,y,x+50,y+20);
Line(x+30,y,x+30,y+20);
if some=ss
then
Begin
Line(x+40,y-15,x+40,y);
Line(x+40,y,x+37,y-5);
Line(x+40,y,x+43,y-5);
Line(x+43,y-5,x+37,y-5);
OutTextXY(x+28,y-25,'tail');
End;
if ss^.elem<255
then
Begin
str(ss^.elem,s);
outtextxy(x+10,y+10,s);
End;
if ss^.next<>nil
then
Begin
Line(x+40,y+10,x+60,y+10);
Line(x+60,y+10,x+60,y-10);
Line(x+60,y-10,x+100,y-10);
Line(x+100,y-10,x+100,y);
Line(x+100,y,x+97,y-5);
Line(x+100,y,x+103,y-5);
Line(x+103,y-5,x+97,y-5);
Wiv(x+70, у, ss^.next);
End
else
Begin
Line(x+40,y+10,x+40,y+30);
Line(x+40,y+30,x+37,y+25);
Line(x+40,y+30,x+43,y+25);
Line(x+43,y+25,x+37,y+25);
Line(x+35,y+32,x+45,y+32);
Line(x+36,y+35,x+44,y+35);
Line(x+38,y+38,x+42,y+38);
End;
End;
Procedure InsertOch(x: byte);
Begin
Cleardevice;
OutTextXY(50,20,'NEW(SOME^.NEXT)');
new(some^.next);
some^.next^.next:=nil;
some^.next^.elem:=255;
Wiv(20,100,head^.next);
OutHead(20,100);
Delay(1000);
Cleardevice;
OutTextXY(50,20,'SOME:=SOME^.NEXT');
some:= some^.next;
some^.next:= nil;
Wiv(20,100,head^.next);
OutHead(20,100);
Delay(1000);
Cleardevice;
Outtextxy(50,20,'SOME^.NEXT:=NIL');
Str(x,s);
OutTextXY(50,40,'SOME^.ELEM:='+s);
some^.elem:= x;
Wiv(20,100,head^.next);
OutHead(20,100);
Delay(1000);
end;
Procedure DelOch;
Begin
Cleardevice;
if head^.next^.elem=255
then
Begin
OutTextXY(50,20,'Элемент не існує!');
Delay(1000);
End
else
if head^.next^.next<>nil
then
Begin
OutTextXY(50,20,'X:=HEAD');
OutTextXY(50,40,'HEAD:=HEAD^.NEXT');
Wiv(20,100,head^.next);
OutX(15,100);
OutHead(90,100);
Delay(1000);
Cleardevice;
OutTextXY(50,20,'DISPOSE(X)');
Wiv(20,100,head^.next);
OutX(20,100);
OutHead(90,100);
Setcolor(red);
Line(20,90,70,130);
Line(70,90,20,130);
Setcolor(white);
Delay(1000);
Cleardevice;
head:=head^.next;
Wiv(20,100,head^.next);
OutHead(20,100);
End
else
Begin
OutTextXY(50,20,'DISPOSE(HEAD)');
Wiv(20,100,head^.next);
OutHead(20,100);
setcolor(red);
Line(20,90,70,130);
Line(70,90,20,130);
setcolor(white);
delay(1000);
cleardevice;
OutHead(20,100);
head^.next^.elem:=255;
some:=head;
End;
End;
Begin
TextBackGround(black);
ClrScr;
bol:=false;
gD:= Detect;
InitGraph(gD, gM,'c:\tp7\bgi\');
new(head);
some:=head;
some^.next:=nil;
Repeat
OutTextXY(50,200,'1 * Додати елемент');
OutTextXY(50,220,'2 * Видалити елемент');
OutTextXY(50,240,'Esc Вихід');
ch:=readkey;
case ch
'1': Begin
OutTextXY(50,260,'Введіть число:');
Gotoxy(23,17);
readln(b);
InsertOch(b);
End;
'2': DelOch;
#27: Begin
CloseGraph;
Halt;
End;
End;
until bol;
CloseGraph;
End.
Приклади рішення задач
Приклад 1. За один перегляд файлу дійсних чисел і з використанням черги надрукувати елементи файлу в наступному порядку: спочатку - всі числа, менші а, потім - всі числа з відрізка [а, b], і нарешті - вся решта чисел, зберігаючи початковий порядок в кожній з цих трьох груп чисел. Числа а і b задає користувач.
Program MordovskihK;
Type
EXO = ^O;
Про = record
Data: integer;
Next: EXO;
End;
Var
i: Real;
Min, Vibr, Other, EndMin, EndVibr, EndOther: EXO;
f: File real;
Stroka: string;
Procedure writeO(Var BeginO, EndO: EXO; з: real);
...
Procedure PrintO(u: EXO);
...
Begin
Min:= Nil;
Vibr:= Nil;
Other:= Nil;
EndMin:= Nil;
EndVibr:= Nil;
EndOther:= Nil;
writeln ('Введіть ім'я файлу >');
readln(Stroka);
writeln ('Введіть проміжок >');
readln(а, b);
assign(f, Stroka);
reset(f);
while not Eof(f) do
begin
read(f, i);
if i<a
then
writeO(Min, x, i)
else
if (i>=a) and (i<=b)
then
writeO(Vibr, x, i)
else
writeO(Other, x, i)
end;
close(f);
writeln('Числа, менші ', а);
Print(Min);
writeln('Числа з проміжку [', а, b, ']');
Print(Vibr);
writeln('Числа, великі ', b);
Print(Other);
End.
Приклад 2. Із заданого тексту перенести всі цифри в кінець кожного рядка, зберігши їх порядок.
Program BaranovA;
Type
EXO = ^O;
Про = record
Data: integer;
Next: EXO;
End;
Var
i: integer;
O1, EndO1, O2, EndO2: EXO;
f1, f2: text;
Name, NewName, Stroka, NewStroka: string;
Procedure writeO(Var BeginO, EndO: EXO; до: char);
...
Procedure readO(u: EXO);
...
ModifStr(St: string, NewSt: string);
Var
l: char;
O1:= Nil;
EndO1:= Nil;
O2:= Nil;
EndO2:= Nil;
NewSt:= '';
for i:= 1 to Length(St) do
if St[i] in ['1', '2', '3', '4', '5', '6', '7', '8', '8', '9', '0']
then
writeO(O2, EndO2, St[i])
else
writeO(O1, EndO1, St[i]);
while O1 <> Nil do
begin
readO(O1, EndO1, l);
NewSt:= NewSt + l;
end;
while O2 <> Nil do
begin
readO(O2, EndO2, l);
NewSt:= NewSt + l;
end;
End;
Begin
write('Введіть ім'я початкового файлу: ');
readln(Name);
write('Введіть ім'я файлу-результату: ');
readln(NewName);
assign(f1, Name);
assign(f2, NewName);
reset(f1);
rewrite(f2);
while not Eof(f1) do
begin
readln(f1, Stroka);
ModifStr(Stroka, NewStroka);
writeln(f2, NewStroka);
end;
close(f1);
close(f2);
End.
Кільце. Формування кільця. Основні операції над кільцем
Кільце - це вид зв'язаного списку, в якому покажчик останнього елемента посилається на перший елемент.
Розгляньте його графічне уявлення.
При програмуванні на Паскалі вважається, що для кільця існує обхід елементів. Доступ можливий до будь-якого елемента структури.
Кільце є динамічною структурою - залежно від користувача програми може змінюється довжина і набір становлячих його елементів.
Опишемо кільце на мові програмування:
Type
TypeCircle = ^K;
До = record
Data: integer;
Next: TypeCircle;
End;
Var
Circle1: TypeCircle;
Формування кільця
Розгляньте процедуру формування кільця. Для роботи цієї процедури заводяться дві локальні змінні типу TypeCircle для зберігання адрес проміжної і завершальної ланки списку, останнім оператором перетворюваного в кільце.
Procedure FofmK(Var u: TypeCircle);
Var
x, у: TypeCircle;
i, N: integer;
Begin
write('Введіть кількість ланок кільця: ');
readln(N);
for i:= 1 to N do
begin
new(x); {виділяємо пам'ять для зберігання нового елемента кільця}
write('Введіть дані в ланку: ');
readln(i);
x^.Data:= i; {заносимо інформацію в полі даних}
if u=nil {якщо кільце ще не створено}
then
u:= x {то покажчик першого елемента ставимо на новий елемент}
else
y^.Next:= x; {приєднуємо новий елемент до останнього елемента}
у:= x; {переносимо покажчик у на останній елемент}
end;
x^.Next:= u; {перетворюваний список в кільце, що вийшов}
End;
Над кільцем визначено три операції: занесення елемента в кільце, видалення елемента з кільця і обхід кільця.
Обхід кільця
Для того, щоб обійти кільце і вивести на екран інформацію, що міститься в ньому, необхідно в локальній змінній типу TypeCircle запам'ятати адресу першого елемента, що виводиться. В цьому випадку можна уникнути повторення і зациклення програми. Вивід даних можна починати з будь-якого елемента кільця; це залежить від адреси першого елемента, переданого в процедуру обходу.
Розгляньте процедуру обходу кільця.
Procedure PrintК(u: TypeCircle);
Var
x: TypeCircle;
Begin
x:= u;
repeat
write(x^.Data,' ');
x:= x^.Next;
until x=u;
readln;
End;
Приклади задач
Задача 1. N учасників гри розміщені по колу. Почавши відлік від першого, видаляють кожного k-го, звужуючи при цьому коло. Визначити порядок видалення учасників з кола.
Для збереження даних про учасників гри використовується список.
Program Schitalka;
Type
Children = ^Child;
Child = record
Data: integer;
Next: Children;
end;
Var
Circl, p, Temp: Children;
i, j, NumName: integer;
text: string;
Function NumSlov(Var S: string): integer;
Var
i, d: integer;
Begin
d:= 0;
i:= 1;
while i < Length(S) do
begin
while S[i] = ' ' do
Inc(i);
while S[i] <> ' ' do
Inc(i);
d:= d+1;
end;
if S[Length(S)] = ''
then
d:= d-1;
NumSlov:= d;
End;
Procedure AddName(Var Old, Young: Children);
Begin
Young^.Next:= Old;
Young^.Prev:= Old^.Prev;
Old^.Prev^.Next:= Young;
Old^.Prev:= Young;
End;
Procedure DeleteName(Var Old: Children);
Begin
Old^.Next^.Prev:= Old^.Prev;
Old^.Prev^.Next:= Old^.Next;
End;
Begin
new(Circl);
Circl^.Next:= Circl;
Circl^.Prev:= Circl;
Circl^.Name:= '';
writeln('Считалка');
writeln('Введите текст считалки >');
readln(text);
writeln('Сколько человек в кругу? >');
readln(NumName);
if NumName>0
then
begin
write('Введите ',i,'-е имя: ');
new(p);
readln(p^.name);
temp:= head^.next;
while temp <> head do
temp:= temp^.next;
AddName(temp, p);
end;
for i:= 1 to NumName-1 do
begin
temp:= head;
for j:= 1 to NumSlov(text) do
begin
temp:= temp^.next;
if temp^.name = ''
then
temp:=temp^.next;
end;
writeln(temp^.name, '- вышел');
deleteName(temp);
end;
writeln(head^.next^.name, '- остался');
End.
Приклад 2. Вивести на екран працюючий світлофор
Program GrushinK;
Uses
Crt, Graph;
Type
TypeCircle = ^K;
K = record
Data: char;
Next: TypeCircle;
end;
Const
XX = 80;
R = 50;
Var
Svetofor, x: TypeCircle;
FraphDriver, GraphMode, Y: integer;
Procedure Picture;
Begin
SetViewPort(240, 1, 400, 477, ClipOff);
Line(0, 1, 0, 477);
Line(160, 1, 160, 477);
Line(0, 1, 160, 1);
Line(0, 477, 160, 477);
Line(0, 150, 156, 150);
Line(0, 330, 156, 330);
Line(-240, 480, 0, 100);
Line(400, 480, 160, 100);
Line(380, 460, 160, 460);
Line(160, 440, 368, 440);
Line(368, 440, 380, 460);
Line(-220, 460, -208, 440);
SetFillStyle(1, White);
FloodFill(375, 455, White);
FloodFill(-215, 455, White);
SetFillStyle(7, 6);
FloodFill(-230, 200, White);
SetColor(4);
Line(-240, 150, -120, -1);
Line(400, 150, 240, -1);
SetColor(15);
SetFillStyle(9, 4);
FloodFill(-240, 0, 4);
FloodFill(390, 10, 4);
SetFillStyle(1, 8);
FloodFill(-100, 470, White);
Y:= 74;
Circle(XX, Y, R);
Y:= 240;
Circle(XX, Y, R);
Y:= 405;
Circle(XX, Y, R);
SetFillStyle(9, 6);
FloodFill(5, 5, White);
End;
Procedure Yellow(Y: integer);
Begin
Picture;
Y:= 240;
SetFillStyle(1, 14);
FloodFill(XX, Y, 15);
Delay(850);
ClearViewPort;
End;
Procedure Green(Y: integer);
Begin
Picture;
Y:= 405;
SetFillStyle(1, 2);
FloodFill(XX, Y, 15);
Delay(1500);
ClearViewPort;
End;
Procedure Red Yellow(Y: integer);
Begin
Picture;
Y:= 240;
SetFillStyle(1, 14);
FloodFill(XX, Y, 15);
Delay(1500);
ClearViewPort;
End;
Procedure Red(Y: integer);
Begin
Picture;
Y:= 74;
SetFillStyle(1, 4);
FloodFill(XX, Y, 15);
Delay(2000);
ClearViewPort;
End;
Procedure Vibor;
Begin
case x^.Data of
'R': Red(Y);
'2': Red Yellow(Y);
'G': Green(Y);
'Y': Yellow(Y);
End;
Begin
GraphDriver:= Detect;
InitGraph(GraphDriver, GraphMode, '..\BGI');
new(x);
u:= x;
x^.Data:= 'R';
new(x^.Next);
x:= x^.Next;
x^.Data:= '2';
new(x^.Next);
x:= x^.Next;
x^.Data:= 'G';
new(x^.Next);
x:= x^.Next;
x^.Data:= 'Y';
x^.Next:= u;
x:= u;
while not KeyPressed do
begin
Vibor;
x:= x^.Next;
end;
End.
Дерева, графи
Граф - це непорожня множина точок (вершин) і множина відрізків (ребер), кінці яких належать заданій множині крапок.
Якщо на кожному ребрі задати напрям, то граф буде орієнтованим.
Якщо, рухаючись по ребрах графа в заданому напрямі, можна потрапити із заданої вершини 1 в задану вершину 2, то говорять, що ці вершини сполучені шляхом.
Замкнутий шлях, що складається з різних ребер, називається циклом.
Граф називається зв'язаним, якщо будь-які дві його вершини сполучено шляхом.
Зв'язний граф без циклів називається деревом.
З кожною вершиною дерева зв'язується кінцеве число окремих дерев, званих піддеревами.
Розгляньте приклад дерева, у вузлах якого розташовуються символи.
Для подальшої роботи з деревами необхідно визначити ряд понять.
Вершина у, що знаходиться безпосередньо нижче за вершину х, називається безпосереднім нащадком х, а вершина х називається предком у.
Якщо вершина не має нащадків, то вона називається термінальною вершиною або листом, якщо має, то називається внутрішньою вершиною.
Кількість безпосередніх нащадків внутрішньої вершини називається її ступенем.
Ступенем дерева називається максимальний ступінь всіх вершин.
Наприклад
вершини F, D, E є безпосередніми нащадками вершини В;
вершини F, D, E є листям;
вершини С, G, H - внутрішні;
ступінь вершини В - 3, а вершини Н - 1;
ступінь дерева рівний 3.
Двійкове дерево - це дерево, в якому з кожної вершини виходить не більше двох ребер.
Дана програма демонструє створення довільного двійкового дерева.
Program D3;
Uses
Crt, Graph;
Const
Arr: array [1..6] integer=(160,80,40,20,10,5);
Arr1: array [1..6] integer=(120,80,70,60,50,40);
Type
ss=^sp;
sp=record
elem:byte;
Next: array[1..2] ss;
end;
Var
а, b, с, d: longint;
s: string;
grDriver: integer;
grMode: integer;
a1, b1: real;
x, Some, Max, Min: ss;
Procedure Zap(у: ss; n: integer);
Var
aa,bb:integer;
Begin
y^.elem:=random(99)+1;
bb:=random(3);
if n<1
then
bb:=2;
if n<a
then
for aa: =1 to bb do
begin
new(y^.next[aa]);
y^.next[aa]^.next[1]:=nil;
y^.next[aa]^.next[2]:=nil;
zap(y^.next[aa],n+1);
end;
End;
Procedure Strel(x1, y1: integer; до: Real);
Var
aa: Real;
Begin
aa:=arctan(k);
if k>0
then
begin
line(x1,y1,x1+round(10*cos(aa+pi/18)), y1-round(10*sin(aa+pi/18)));
line(x1,y1,x1+round(10*cos(aa-pi/18)), y1-round(10*sin(aa-pi/18)));
line(x1+round(10*cos(aa+pi/18)),y1- round(10*sin(aa+pi/18)),x1+ round(10*cos(aa-pi/18)),y1- round(10*sin(aa-pi/18)));
end
else
begin
aa:=-aa;
line(x1,y1,x1-round(10*cos(aa+pi/18)), y1-round(10*sin(aa+pi/18)));
line(x1,y1,x1-round(10*cos(aa-pi/18)), y1-round(10*sin(aa-pi/18)));
line(x1-round(10*cos(aa+pi/18)),y1- round(10*sin(aa+pi/18)),x1- round(10*cos(aa-pi/18)),y1- round(10*sin(aa-pi/18)));
end
end;
Procedure Wiv(у: ss; n, x1, y1: integer);
Var
spi: ss;
Begin
SetColor(n+1);
Circle(x1,y1,10);
Str(y^.elem, s);
if length(s)=2
then
OutTextXY(x1-6, y1-2, s)
else
OutTextXY(x1-3, y1-2, s);
if n<a
then
begin
if y^.next[1]<>nil
then
begin
SetColor(n+1);
Line(x1,y1+10,x1-(arr[n] div 2),y1+((arr1[n]-20) div 2)+10);
SetColor(n+2);
Line(x1-(arr[n] div 2),y1+((arr1[n]-20) div 2)+10,x1-arr[n],y1+arr1[n]-10);
Strel(x1-arr[n],y1+arr1[n]-10 (arr1[n]-20)/arr[n]);
Wiv(y^.next[1],n+1,x1-arr[n],y1+ arr1[n]);
end;
if y^.next[2]<> nil
then
begin
SetColor(n+1);
Line(x1,y1+10,x1+arr[n],y1+arr1[n]-10);
SetColor(n+2);
Line(x1+(arr[n] div 2),y1+((arr1[n]-20) div 2)+10,x1+arr[n],y1+arr1[n]-10);
Strel(x1+arr[n],y1+arr1[n]-10, - (arr1[n]-20)/arr[n]);
Wiv(y^.next[2],n+1,x1+arr[n],y1+ arr1[n]);
end;
end;
end;
Begin
ClrScr;
Randomize;
Repeat
new(x);
а:=6;
x^.next[1]:=Nil;
x^.next[2]:=Nil;
Zap(x,0);
Max:=x;
Min:=x;
writeln;
grDriver:= Detect;
InitGraph(grDriver, grMode,'c:\tp7\bgi\');
SetFillStyle(solidfill,15);
SetColor(15);
Wiv(x,1,320,50);
Delay(5000);
until KeyPressed;
End.
Дерево - це складна динамічна структура даних, що застосовується для ефективного зберігання інформації.
Очевидно, що для опису потрібні посилання. Опишемо, як змінні з фіксованою структурою - самі вершини, тоді ступінь дерева визначатиме число посилальних компонент, вказуючих на вершини піддерев. В бінарному дереві їх два: ліве і праве.
Type
TreeLink = ^Tree;
Tree = Record
Data: <тип данных>;
Left, Right: TreeLink;
End;
Корінь дерева опишемо в розділі опису змінних:
Var
kd: TreeLink;
До основних операцій над деревами відносяться:
ь занесення елемента в дерево;
ь обхід дерева;
ь видалення елемента з дерева.
Розглянемо вставку і обхід дерева на прикладі наступної задачі.
Задача. Створити і вивести на екран дерево, елементи якого вводяться з клавіатури і мають цілий тип. Причому для кожної вершини дерева у всіх лівих вершинах повинні знаходитися числа менші, а в правій більші, ніж числа, що зберігаються в цій вершині. Таке дерево називається деревом пошуку.
Опишемо процедуру вставки в дерево нової вершини. При вставці в дерево вершина вставляється або як поддерево вже існуючої вершини або як єдина вершина дерева. Тому і лівий і правий зв'язки нової вершини повинні бути Nil. Коли дерево порожнє, значення передаване у вигляді параметра посилання рівно Nil. В цьому випадку потрібно змінити її так, щоб вона указувала на нову вершину, яка була вставлена як коренева. При вставці другого елемента переданий з основної програми параметр t вже не буде рівний Nil, і треба ухвалювати рішення про те, в яке піддерево необхідно вставити нову вершину.
Procedure InsTree(n: integer; Var t: TreeLink);
Begin
if t=nil
then
begin
new(t);
with t^ do
begin
Left:= nil;
Right:= nil;
Data:= n;
end;
end;
else
if n<=t^.data
then
InsTree(n, t^.Left)
else
InsTree(n, t^.Right)
End;
Опишемо процедуру виведення значень елементів двійкового дерева на екран. Для цього необхідно виконати повний обхід дерева. При обході дерева його окремі вершини відвідуються в окремому порядку. Вивід двійкового дерева можна проводити рекурсивно, виконуючи для кожної вершини три дії:
Вивід числа, що зберігається у вузлі;
обхід лівого піддерева;
обхід правого піддерева.
Порядок виконання цих дій визначає спосіб обходу дерева.
Способи виведення:
прямий вивід (зверху вниз);
зворотний вивід (зліва направо);
кінцевий вивід (від низу до верху).
Процедура зворотного виводу дерева має наступний вигляд:
Procedure PrintTree(t: TreeLink);
Begin
if t<>Nil
then
begin
PrintTree(t^.Left);
Write(t^.Data:3);
PrintTree(t^.Right);
end;
End;
Основна програма здійснює введення чисел з клавіатури. Використовуються: змінна nd типу TreeLink - значення покажчика на корінь дерева; змінна Digit типу integer для зберігання чергового введеного числа.Begin
writeln('Введіть вершини дерева. Закінчення введення - 0');
kd:= nil;
read(Digit);
while Digit <> 0 do
begin
InsTree(Digit, kd);
writeln(' Введіть число ');
read(Digit);
end;
PrintTree(kd);
End.
В дереві пошуку можна знайти місце кожного елемента, рухаючись від кореня і переходячи на ліве або праве піддерево залежно від значень даних, що зустрічаються.
Використовування дерев пошуку значно скорочує час рішення задачі.
Правильно організованим деревом вважається ідеально збалансоване дерево, тобто для кожної його вершини кількість вершин в лівому і правому піддереве відрізняються не більше ніж на 1.
Сформуємо ідеально збалансоване дерево, елементами якого є N чисел, що вводяться з клавіатури.
Оскільки вимагається побудувати ідеально збалансоване дерево, то його вузли в процесі побудови повинні розподілятися рівномірно. Сформуємо правило рівномірного розподілу вузлів при відомому їх числі:
Узяти один вузол як корінь.
Побудувати ліве піддерево з числом вузлів n1=N div 2 тим же способом.
Побудувати праве піддерево з числом вузлів n2=N-n1-1 тим же способом.
Program BalansTree;
Uses
Crt;
Type
Pt = ^Node;
Node = record
Data: integer;
Left, Right: Pt;
end;
Var
n: integer;
kd: Pt;
f: text;
Function Tree(n: integer): Pt;
Var
NewNode: Pt;
x, n1, n2: integer;
Begin
if n=0
then
Tree:= Nil
else
begin
n1:= n Div 2;
n2:= n-n1-1;
read(f,x);
new(NewNode);
with NewNode^ do
begin
Data:= x;
Left:= Tree(n1);
Right:= Tree(n1);
end;
Tree:= NewNode;
end;
End;
Procedure PrintTree(t: Pt; h: integer);
Var
i: integer;
Begin
if t<>nil
then
with t^ do
begin
PrintTree(Left, h+1);
for i:= 1 to h do
write(' ');
writeln(Data:6);
PrintTree(Right, h+1);
end;
End;
Begin
ClrScr;
assign(f, 'c:\f.pas');
reset(f);
write('n=');
readln(n);
kd:= Tree(n);
PrintTree(kd, 0);
readln;
End.
Пошук і включення елемента в дерево.
Задача. Задана послідовність слів. Визначити частоту входження кожного із слів в послідовності.
Для вирішення задачі будь-яке слово шукається в дереві, яке на початковому етапі порожнє. Якщо слово знайдено, то лічильник його входжень збільшується на 1, якщо ні, то слово включається в дерево з одиничним значенням лічильника.
Program Poisk;
Uses
Crt;
Type
Words = ^WordTree;
WordTree = record
Data: string;
до: integer;
Left, Right: Words;
end;
Var
n: integer;
kd: Words;
x: string;
f: text;
Procedure Tree(x: string; Var p: Words);
Begin
if p=nil
then
begin
new(p);
with p^ do
begin
до:= 1;
Data:= x;
Left:= Nil;
Right:= Nil;
end;
end;
else
if x>p^.Data
then
Tree(x. p^.Left)
else
if x<p^.Data
then
Tree(x. p^.Right)
else
Inc(p^.k);
End;
Procedure PrintTree(t: Words; h: integer);
Var
i: integer;
Begin
if t <> Nil
then
with t^ do
begin
PrintTree(Left, h+1);
for i:= 1 to h do
write(' ');
writeln(Data, ',(', до, ')');
PrintTree(Right, h+1);
end;
End;
Begin
ClrScr;
assign(f, 'c:\f.dan');
reset(f);
write('n=');
readln(n);
kd:= Nil;
while n>0 do
begin
readln(f,x);
Tree(x, kd);
Dec(n);
end;
close(f);
PrintTree(kd, 0);
readln;
End.
Ця задача називається задачею пошуку по дереву з включенням.
Видалення з дерева
Безпосереднє видалення елемента з впорядкованого дерева реалізується достатньо просто, якщо ця вершина є кінцевою або з неї виходить тільки одне ребро. Для цього потрібно змінити відповідне посилання у попередньої вершини.
Якщо ж з вершини, що видаляється, виходить дві гілки, то потрібно знайти відповідну вершину дерева, яку можна було б вставити на місце вершини, що видаляється.
З вищесказаного виходить, що процедура видалення елемента з дерева повинна розрізняти три випадки.
Вершина, що видаляється, має два піддерева. Елемент, що в цьому випадку видаляється, потрібно замінити або на найправіший елемент його лівого піддерева, або на найлівіший елемент його правого піддерева. При цьому вони повинні мати не більше одного нащадка.
Вершина, що видаляється, має не більше одного піддерева (0 або 1).
Вершини в дереві, що видаляється, немає.
Прогляньте рекурсивну процедуру DelTree, яка відшукує елемент із заданим ключем і видаляє його. В процедурі DelTree описана процедура d1, яка працює тільки в першому з трьох перерахованих випадків.
Допоміжна процедура d1 "рухається" по правій гілці лівого піддерева елемента q^, що виключається, і замінює значення ключа в q^ на відповідне значення з найправішого елемента r^ лівого піддерева.
Type
Pt = ^Node;
Node = Record
Data: integer;
Left, Right: Pt;
End;
Procedure DelTree(x: integer; Var p: Pt);
Var
q: Pt;
Procedure D1(Var r: Pt);
Begin
if r^.Right <> Nil
then
d1(r^.Right)
else
begin
q^.Data:= r^.Data;
q:= r;
r:= r^.Left;
Dispose(q);
end;
End;
Begin
if p=nil
then
writeln('Елемента з ключем ', x, 'в дереві немає.')
else
if x<p^.Data
then
DelTree(x, p^.Left)
else
if x>p^.Data
then
DelTree(x, p^.Right)
else
begin
q:= p;
if q^.Right = Nil
then
begin
p:= q^.Left;
dispose(q);
end;
else
if q^.Left = Nil
then
begin
p:= q^.Right;
dispose(q);
end;
else
D1(q^.Left)
end;
End;
Размещено на Allbest.ru
Подобные документы
Основні операції над стеком. Бінарне дерево пошуку. Абстрактний тип даних "Черга". Динаміка вмісту списку при внесенні до нього елемента. Написання програми синтаксичного аналізу відповідностей відкриваючих і закриваючих дужок в арифметичному виразі.
курсовая работа [2,9 M], добавлен 14.05.2015Структури даних як способи їх організації в комп'ютерах. Підтримка базових структури даних в програмуванні. Дерево як одна з найпоширеніших структур даних. Бінарні дерева на базі масиву. Створення списку - набору елементів, розташованих у певному порядку.
контрольная работа [614,7 K], добавлен 18.02.2011Розробка структури, алгоритму роботи програми, яка забезпечує можливість покупки товарів. Створення списку користувачів та списку продуктів. Розробка структур даних та основних процедур програми. Алгоритм створення платформи під назвою "Сlaude Monet".
курсовая работа [121,3 K], добавлен 14.05.2019Динамічні структури даних. Списки та їх різновиди. Практична реалізація динамічних структур на мові програмування С++. Динамічна пам’ять, операції NEW та DELETE. Побудова динамічних структур з використанням стандартних шаблонів: бібліотеки Stack та Queue.
курсовая работа [72,4 K], добавлен 07.09.2010Программа формирования матрицы смежности по заданному списку окрестностей вершин ориентированного графа. Формирование динамического списка дуг ориентированного графа по заданному списку окрестностей. Анализ временной и емкостной сложности алгоритма.
курсовая работа [8,1 M], добавлен 07.09.2012Пристрої базової конфігурації персонального комп’ютера. Порядок роботи зі списками даних в текстовому редакторі: створення нумерованого або маркірованого списку, використання багаторівневих списків, перетворення їх в звичайний текст, додавання позицій.
реферат [1,0 M], добавлен 27.09.2011Опис предметної області та середовища розробки бази даних. Модель реальної системи - ієрархія діаграм DFD. Складання таблиці списку подій. Переробка ERD в реляційне відношення клієнтів, постачальників та автомобілів. Створення ключових полів таблиць БД.
курсовая работа [606,4 K], добавлен 04.02.2013Текстовий редактор Word, його функціональні можливості. WinRAR як один з найбільш потужних і зручних архіваторів для Windows. Метод стиснення для текстів. Створення списку, вставити або перетворити в нумерований або маркірований список в свій документ.
презентация [219,7 K], добавлен 25.09.2011Характеристика об'єктно-орієнтованої мови програмування Java. Розробка програми з кнопками доступу до хімічної таблиці, списку елементів та додаткової інформації про програму та про продукт (ким був розроблений та звідки була взята інформація для нього).
отчет по практике [2,6 M], добавлен 18.05.2014Складання багаторівневого списку за допомогою редактора Word, їх класифікація та різновиди. Порядок побудови діаграми по даних таблиці, структурної схеми, математичних формул. Графічне супроводження інформації. Структура інтерфейсу користувача Windows.
контрольная работа [372,5 K], добавлен 09.05.2010
