Назва роботи: Динамічні структури даних. Стеки, черги. Списки. бінарні дерева
Предметна область: Інформатика, кібернетика та програмування
Опис: При створенні дерева викликається рекурсивна процедура такого вигляду: procedure Insertvr Root: TTree; X: T; <Дополнительная процедура создающая и инициализирующая новый узел> procedure CreteNodevr p: TTree; n: T; begin Newp; p ^ .Right: = nil end; begin if Root = nil Then CreteNodeRoot X <создаем новый узел дерева> else with Root ^ do begin if vlue X then InsertRight X else if vlue X Then InsertLeft X else <Действия производимые в случае повторного.
Розмір файлу: 178.5 KB
Роботу скачали: 82 чол.
ісціпліна «Основи алгоритмізації та програмування» Динамічні структури даних
Динамічні структури даних.
Стеки, черги. Списки. Бінарні дерева.
[4] Бінарні дерева
Динамічні структури даних # 150; це структури даних, пам'ять під які виділяється і звільняється в міру необхідності.
Порядок роботи з динамічними структурами даних наступний:
- створити (відвести місце в динамічній пам'яті);
- працювати за допомогою покажчика;
- видалити (звільнити зайняте структурою місце).
У багатьох задачах потрібно використовувати дані, у яких конфігурація, розміри і склад можуть змінюватися в процесі виконання програми. Для їх уявлення використовують динамічні інформаційні структури. До таких структур відносять:
- односпрямовані (одинзв'язні) списки;
- двонаправлені (двусвязного) списки;
- циклічні списки;
- стек;
- дек;
- чергу;
- бінарні дерева.
Вони відрізняються способом зв'язку окремих елементів і / або допустимими операціями. Динамічна структура може займати несуміжні ділянки оперативної пам'яті.
Динамічні структури широко застосовують і для більш ефективної роботи з даними, розмір яких відомий, особливо для вирішення завдань сортування.
Чергою називають структуру даних, для якої визначено операції додавання і видалення елементів і елементи якої організовані таким чином, що їх видалення буде здійснюватися точно в такому ж порядку, в якому відбувалося їх додавання.
Черга є лінійний список даних, доступ до якого здійснюється за принципом "перший увійшов, перший вийшов" (іноді скорочено його називають методом доступу FIFO).
У повсякденному житті черзі зустрічаються часто. Наприклад, черга в банку або чергу в кафетеріях з швидким обслуговуванням є чергою в зазначеному вище сенсі (виключаючи ті випадку, коли людина намагається домогтися обслуговування позачергово!).
Програмним чином така структура може бути реалізована різними способами. Найпростішою є реалізація за допомогою масиву і двох покажчиків. Один з покажчиків визначає те місце масиву, куди елемент буде додаватися, і називається кінцем черзі (КК). Інший покажчик визначає те місце масиву, звідки елемент буде віддалятися, і називається початком черзі (УН). Умовою наявності елементів у черзі є нерівність покажчиків УН і КК. При цьому порядок елементів в черзі визначено таким чином, що елемент з меншим індексом надійшов раніше.
Наприклад, нехай у нас є черга з трьох елементів А, В, С, в яку першим був поміщений елемент А, потім # 151; елемент В, а останнім # 151; елемент С. Після видалення елемента А першим елементом черги буде елемент В. При цьому елемент А залишився в масиві на своєму місці, але його вже немає в черзі, так як покажчик початку черги УН вказує на елемент В, т. е. наступний елемент масиву . Якщо ми додамо в чергу новий елемент D. то він буде поміщений в кінець черги, визначається покажчиком кінця КК. При цьому значення покажчика КК повинно змінитися. Слід зазначити, що для того, щоб видалити з черги елемент С, необхідно спочатку видалити елемент В. Черга, в якій немає жодного елемента, називається порожньою. В цьому випадку обидва покажчика показують на одне і те ж місце. Операції над чергами: Init # 151; створює порожню чергу; Empty # 151; повертає значення true. якщо чергу порожня, і false у противному разі; Insert # 151; додає елемент в кінець черги; Remove # 151; видаляє елемент з початку черги.
Type Queue = array [1..maxqueue] of integer;
Procedure Init (var q: Queue;
var Free, First. integer);
Черги в програмуванні використовуються в багатьох випадках, наприклад, при моделюванні, при плануванні робіт (метод Перт або графіки Гатта), при буферизації введення-виведення.
Стеком будемо називати структуру даних, для якої визначено операції додавання і видалення елементів і елементи якої організовані таким чином, що їх видалення буде здійснюватися точно протилежно тому порядку, в якому проводилося додавання.
Організація стека в певному сенсі протилежна організації черги, оскільки тут використовується доступ за принципом "останньої пішов, перший вийшов" (такий метод доступу іноді називають методом LIFO). Уявімо собі стопку тарілок. Нижня тарілка з цієї стопки буде використана останньої, а верхня тарілка (яка була встановлена в стопку останньої) буде використана першої. Стеки широко використовуються в системному програмному забезпеченні, включаючи компілятори і інтерпретатори.
Представлений тут стек містить 6 елементів, причому елементи в стек були поміщені в наступному порядку: А, В, С, DEF витягають ж вони можуть тільки в порядку FED С, В, А, т. Е. Для того, щоб витягти з стека елемент С, необхідно спочатку отримати елементи F. Е і D.
Операції над стеками і їх реалізація: Init # 151; створює порожній стек; Empty # 151; повертає значення true. якщо стек порожній і false в іншому випадку; Push # 151; додає елемент в стек; Pop # 151; видаляє елемент з стека. Історично склалося так, що дві основні операції для стека - помістити в стек і вибрати з стека - отримали назву відповідно "заштовхнути" і "виштовхнути".
Stack = Array [1..Maxstack] of integer;
Procedure Init (var s: Stack; var tos. Integer);
Для того, щоб подивитися, що знаходиться в вершині стека, досить ввести точку. Хоча дана програма виконує арифметичні дії тільки з цілими числами, її легко можна пристосувати для чисел з плаваючою комою, змінюючи тип даних стека і перетворюючи оператор "div" в оператор ділення для чисел з плаваючою комою.
2 2 2 * + 2 21 7 / * + 100 5 / + 12 -10 2 * + = 0
Списком називатимемо деяку послідовність елементів, зв'язаних за допомогою покажчиків (посилань).
У списку елементи пов'язані один з одним логічно. Логічний порядок проходження елементів списку визначається за допомогою покажчиків. Логічний порядок проходження елементів списку може не збігатися з фізичним порядком їх розташування в пам'яті ЕОМ. Кожен елемент списку (часто званий вузлом) складається з двох частин. Перша частина містить безпосередньо дані, що належать елементу, і є інформаційною. Друга частина містить покажчик і є довідковою. Покажчик визначає місце положення елемента списку, пов'язаного з даним елементом.
Пов'язані списки використовуються в двох основних випадках. По-перше, при створенні масивів, які розташовуються в оперативній пам'яті і розмір яких заздалегідь невідомий. Якщо ви заздалегідь знаєте, якого розміру пам'ять потрібно для вирішення вашого завдання, то ви можете використовувати простий масив. Однак, якщо дійсний розмір списку вам невідомий, то ви повинні застосувати пов'язаний список. По-друге, пов'язані списки використовуються в базах даних на дисках. Пов'язаний список дозволяє швидко виконувати вставку і видалення елемента даних без реорганізації всього дискового файлу. З цих причин пов'язані списки широко використовуються в програмах з управління базами даних.
Пов'язані списки можуть мати поодинокі або подвійні зв'язки. Список з одним зв'язком містить елементи, кожен з яких має зв'язок з наступним елементом даних. У списку з подвійним зв'язком кожен елемент має зв'язок як з наступним елементом, так і з попереднім елементом. Тип пов'язаного списку вибирається залежно від розв'язуваної задачі.
Формування порожнього списку. Заводимо в пам'яті двовимірний масив. У Sp [l. i] будемо зберігати сам елемент списку, а в Sp [2, i] # 151; покажчик на наступний елемент списку.
const maxspisok = 20;
Type Spisok = array of [1..2, l..maxspisok] of integer;
Procedure NewSpisok (var Sp: Spisok; var US, UN: integer;);
for i: = l to Maxspisok-1 do Sp [2, i]: = i + 1;
Procedure InsSpisok (var Sp: Spisok; var US, UN: integer;
var Code: integer; var x: integer);
var US2: integer;
2. Права поддерево
3. Корінь поддерева
Прямий порядок проходження означає обхід в напрямку зверху-вниз, коли після відвідин чергового розгалуження триває проходження вглиб дерева, поки не пройдені всі нащадки досягнутого вузла. З цієї причини прямий порядок проходження часто називають низхідним, або проходженням в глибину.
Прямий порядок є найбільш природний спосіб перерахування вузлів дерева у формі вкладених дужок або уступчатого списку. Якщо виключити всі дужки і коми, то послідовність вузлів у формі вкладених дужок буде відповідати прямому порядку проходження дерева.
Уступи в ступінчастому списку, що представляє будь-яку ієрархічну структуру, також розташовуються в прямому порядку. У генеалогічних термінах прямої порядок проходження дерева відображає династичний порядок престолонаслідування, коли титул передається старшому нащадку.
При симетричному порядку дерево проходиться зліва-направо, породжуючи лексіграфіческі впорядковану послідовність ключів вузлів. З цієї причини симетричний порядок проходження часто називають лексіграфіческім. Симетричність порядку виражається в тому, що якщо бінарне дерево відобразити щодо вертикальної осі, помінявши місцями ліві і праві вузли, то симетричний порядок проходження заміниться на протилежний лексіграфіческій.
Якщо застосовується кінцевий порядок проходження, то виходить обхід дерева знизу-вгору, коли в момент відвідування будь-якого вузла все його нащадки вже пройдені, а корінь дерева проходиться останнім. Через цю особливість обходу, кінцевий порядок часто називають висхідним, або зворотним щодо прямого.
При виборі певного порядку проходження необхідна функціональна обробка кожного вузла відбувається після відповідного числа заходів в нього. При обході зверху-вниз кожен вузол обробляється при первинному заході в нього, при симетричному порядку проходження - в другому, а при обході знизу-вгору - в третьому.
Ще один варіант обходу - за рівнями: спочатку виводити корінь, потім - всі вузли першого рівня, за ними - вузли другого рівня, і т.д.
Це реалізується ось такою процедурою:
procedure PrintByLevel (level: integer; var items: array of TTree; count: integer);
var i, new_count: integer;
if count <> 0 then
for i: = 0 to pred (count) do
start_x: = GetMaxX div 2;
print_node (Root, 1, 0, GetMaxX div 2, GetMaxX);
Застосування бінарних дерев
Організація даних за допомогою бінарних дерев часто дозволяє значно скоротити час пошуку потрібного елемента. Пошук елемента в лінійних структурах даних зазвичай здійснюється шляхом послідовного перебору всіх елементів, присутніх в даній структурі. Пошук по дереву не вимагає перебору всіх елементів, тому займає значно менше часу. Максимальне число кроків при пошуку по дереву дорівнює висоті даного дерева, тобто кількості рівнів в ієрархічній структурі дерева.
Наступний модуль містить основні функції для роботи з бінарними деревами.
Left, Right: TTree;
procedure Insert (var Root: TTree; X: T);
procedure Remove (var Root: TTree; X: T);
function Find (Root: TTree; X: T): TTree;
procedure Delete (Root: TTree);
procedure LeafsCount (Root: TTree; var k: Integer);
function GetNode (Root: TTree): T;
procedure PrintDown (Root: TTree);
procedure PrintLex (Root: TTree);
procedure PrintUp (Root: TTree);
procedure Insert (var Root: TTree; X: T);
procedure CreateNode (var p: TTree; n: T);
Установка гідрокрекінг призначена для переробки вакуумного газойлю в присутності водню на алюмонікельмолібденовом каталізаторі з повторною переробкою Рециркулято (залишку куба колони фракціонування) для максимального виробництва дизельного або реактивного палива.