Програмне забезпечення ЕОМ. Структури даних та алгоритми

ЗМІСТ

  1. Введення ..…..…………………………………………………………… 3
  2. Огляд методів роботи з динамічними структурами даних ………….. 7
    • Стек ….…………………………………………………………………. 7
    • Циклічний список ….……….…….…….……………………………… 8
    • Збалансоване дерево ….………….….………………………………… 9
  3. Практична частина. Використання динамічних структур для обчислення арифметичних виразів, заданих в постфіксній формі ………..….. 11
  4. Висновок ……………….….….………………………………………… 20
  5. Список використаної літератури ….………………………………….. 21

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  1. Введення

 

Динамічні структури даних — це структури даних, пам’ять під які виділяється і звільняється в міру необхідності.

Динамічні структури даних в процесі існування в пам’яті можуть змінювати не тільки число складових їх елементів, а й характер зв’язків між елементами. При цьому не враховується зміна вмісту самих елементів даних. Така особливість динамічних структур, як несталість їх розміру і характеру відносин між елементами, призводить до того, що на етапі створення машинного коду програма-компілятор не може виділити для всієї структури в цілому ділянку пам’яті фіксованого розміру, а також не може зіставити з окремими компонентами структури конкретні адреси. Для вирішення проблеми адресації динамічних структур даних використовується метод, званий динамічним розподілом пам’яті, тобто пам’ять під окремі елементи виділяється в момент, коли вони «починають існувати» в процесі виконання програми, а не під час компіляції. Компілятор в цьому випадку виділяє фіксований обсяг пам’яті для зберігання адреси динамічне розміщеного елемента, а не самого елементу.

Динамічна структура даних характеризується тим що:

  • Вона не має імені;
  • Їй виділяється пам’ять в процесі виконання програми;
  • Кількість елементів структури може не фіксуватися;
  • Розмірність структури може змінюватися в процесі виконання програми;
  • В процесі виконання програми може змінюватися характер взаємозв’язку між елементами структури.

Кожної динамічної структурі даних зіставляється статична змінна типу покажчик (її значення – адресу цього об’єкта), за допомогою якої здійснюється доступ до динамічної структурі.

Самі динамічні величини не вимагають опису в програмі, оскільки під час компіляції пам’ять під них не виділяється. Під час компіляції пам’ять виділяється тільки під статичні величини. Покажчики — це статичні величини, тому вони вимагають опису.

Необхідність в динамічних структурах даних зазвичай виникає в наступних випадках.

  • Використовуються змінні, що мають досить великий розмір (наприклад, масиви великої розмірності), необхідні в одних частинах програми і абсолютно не потрібні в інших.
  • У процесі роботи програми потрібен масив, список чи інша структура, розмір якої змінюється в широких межах і важко передбачуваний.
  • Коли розмір даних, що обробляються в програмі, перевищує обсяг сегмента даних.

Динамічні структури, за визначенням, характеризуються відсутністю фізичної суміжності елементів структури в пам’яті, непостійністю і непередбачуваністю розміру (числа елементів) структури в процесі її обробки.

Оскільки елементи динамічної структури розташовуються по непередбачуваним адресами пам’яті, адреса елементу такої структури не може бути обчислений з адреси початкового або попереднього елемента. Для встановлення зв’язку між елементами динамічної структури використовуються покажчики, через які встановлюються явні зв’язки між елементами. Таке уявлення даних у пам’яті називається зв’язковим.

Гідності зв’язкового представлення даних — в можливості забезпечення значною мінливості структур:

  • розмір структури обмежується тільки доступним об’ємом машинної пам’яті;
  • при зміні логічної послідовності елементів структури потрібно не переміщення даних в пам’яті, а тільки корекція покажчиків;
  • велика гнучкість структури.

Разом з тим, зв’язне уявлення не позбавлене і недоліків, основними з яких є наступні:

  • на поля, що містять покажчики для зв’язування елементів один з одним, витрачається додаткова пам’ять;
  • доступ до елементів зв’язної структури може бути менш ефективним за часом.

Останній недолік є найбільш серйозним і саме їм обмежується застосовність зв’язкового представлення даних. Якщо в суміжному поданні даних для обчислення адреси будь – якого елементу нам у всіх випадках достатньо було номера елемента і інформації, що міститься в дескрипторі структури, то для зв’язкового уявлення адреса елемента не може бути обчислений з вихідних даних. Дескриптор зв’язної структури містить один або кілька покажчиків, що дозволяють увійти в структуру, далі пошук необхідного елемента виконується проходженням по ланцюжку покажчиків від елемента до елементу. Тому зв’язне уявлення практично ніколи не застосовується в задачах, де логічна структура даних має вигляд вектора або масиву – з доступом за номером елемента, але часто застосовується в задачах, де логічна структура вимагає іншої вихідної інформації доступу (таблиці, списки, дерева і т.д.).

Порядок роботи з динамічними структурами даних наступний:

  • створити (відвести місце в динамічній пам’яті);
  • працювати за допомогою покажчика;
  • видалити (звільнити зайняте структурою місце).

Класифікація динамічних структур даних

У багатьох задачах потрібно використовувати дані, в яких конфігурація, розміри і склад можуть змінюватися в процесі виконання програми. Для їх подання використовують динамічні інформаційні структури. До таких структур відносять:

  • односпрямовані (однозв’язні) списки;
  • двонаправлені (двосвязні) списки;
  • циклічні списки;
  • стек;
  • дек;
  • чергу;
  • бінарні дерева.

Вони відрізняються способом зв’язку окремих елементів і (або) допустимими операціями. Динамічна структура може займати несуміжні ділянки оперативної пам’яті.

Динамічні структури широко застосовують і для більш ефективної роботи з даними, розмір яких відомий, особливо для вирішення завдань сортування.

 

 

  1. Огляд методів роботи з динамічними структурами даних.

 

  • Стек

 

Стек – різновид лінійного списку, структура даних, яка працює за принципом «останнім прийшов – першим пішов» . Всі операції (наприклад, видалення елементу) в стеку можна проводити тільки з одним елементом, який знаходиться на верхівці стеку та був введений в стек останнім. Стек можна розглядати як певну аналогію до стопки тарілок, з якої можна взяти верхню, і на яку можна покласти верхню тарілку.

Операції зі стеком:

  • push («заштовхнути елемент»): елемент додається в стек та розміщується в його верхівці. Розмір стеку збільшується на одиницю. При перевищенні розміру стека граничної величини, відбувається переповнення стека (англ. stack overflow);
  • pop («виштовхнути елемент»): отримує елемент з верхівки стеку. При цьому він видаляється зі стеку і його місце в верхівці стеку займає наступний за ним відповідно до правила LIFO, а розмір стеку зменшується на одиницю. При намаганні «виштовхнути» елемент з вже пустого стеку, відбувається ситуація «незаповнення» стеку (англ. stack underflow)

Кожна з цих операцій зі стеком виконується за фіксований час 0 (1) і не залежить від розміру стеку. Додаткові операції (присутні не у всіх реалізаціях стеку):

  • isEmpty: перевірка наявності елементів в стеку; результат: істина (true), коли стек порожній.
  • isFull: перевірка заповненості стека. Результат: істина, коли додавання нового елементу неможливе.
  • clear: звільнити стек (видалити усі елементи).
  • top: отримати верхній елемент (без виштовхування).
  • size: отримати розмір (кількість елементів) стека.
  • swap: поміняти два верхніх елементи місцями.

Організація в пам’яті комп’ютера

Стек може бути організований як масив або множина комірок в певній області комп’ютера з додатковим зберіганням ще й вказівника на верхівку стека. Заштовхування першого елемента в стек збільшує адресу вказівника, виштовхування елементу зменшує її. Таким чином, адреса вказівника завжди відповідає комірці масиву, в якій зараз знаходиться верхівка стеку.

 

  • Циклічний список

 

Циклічний (кільцевий) список — це структура даних, що представляє собою послідовність елементів, останній елемент якої містить покажчик на перший елемент списку, а перший (у разі двонаправленого списку) — на останній.

Основна особливість такої організації полягає в тому, що в цьому списку немає елементів, що містять порожні покажчики, і, отже, не можна виділити крайні елементи.

Циклічні списки, так само як і лінійні, бувають односпрямованим і двонаправленими.

Циклічний односпрямований список схожий на лінійний односпрямований список, але його останній елемент містить покажчик, що зв’язує його з першим елементом.

Для повного обходу такого списку достатньо мати покажчик на довільний елемент, а не на перший, як в лінійному однонаправленому списку. Поняття «перший» елемента тут досить умовно і не завжди потрібно. Хоча іноді буває корисно виділити деякий елемент як «перший» шляхом установки на нього спеціального покажчика. Це потрібно, наприклад, для запобігання «зациклення» при перегляді списку.

 

Рисунок 2.1

  • Основні операції, здійснювані з циклічним односпрямованим списком:
  • створення списку;
  • друк (перегляд) списку;
  • вставка елемента в список;
  • видалення елемента зі списку;
  • пошук елемента в списку;
  • перевірка порожнечі списку;
  • видалення списку

 

  • Збалансоване дерево

 

В програмуванні збалансоване дерево в загальному розумінні цього слова – це такий різновид бінарного дерева пошуку, яке автоматично підтримує свою висоту, тобто кількість рівнів вершин під коренем є мінімальною. Ця властивість є важливою тому, що час виконання більшість алгоритмів на бінарних деревах пошуку пропорційний до їхньої висоти, і звичайні бінарні дерева пошуку можуть мати досить велику висоту в тривіальних ситуаціях. Процедура зменшення (балансування) висоти дерева виконується за допомогою трансформацій, відомих як обернення дерева, в певні моменти часу (переважно при видаленні або додаванні нових елементів).

Більш точне визначення збалансованих дерев було дане Г. Адельсон-Вельським та Є. Ландісом.

Ідеально збалансоване дерево, за Адельсон-Вельським та Ландісом – це дерево, у якого для кожної вершини різниця між висотами лівого та правого піддеревне перевищує одиниці. Однак, така умова доволі складна для виконання на практиці і може вимагати значної перебудови дерева при додаванні або видаленні елементів.

Тому було запропоноване менш строге визначення, яке отримало назву умови АВЛ(AVL)-збалансованості і говорить, що бінарне дерево є збалансованим, якщо висоти лівого та правого піддерев різняться не більше ніж на одиницю. Дерева, що задовольняють таким умовам, називаються AVL-деревами. Зрозуміло, що кожне ідеально збалансоване дерево є також АВЛ-збалансованим, але не навпаки.

Незбалансоване дерево                 Те само дерево після збалансування

Рисунок 2.2

 

 

  1. Практична частина. Використання динамічних структур для обчислення арифметичних виразів, заданих в постфіксній формі

 

program p;

uses crt;

const fl=’file.out’;

type num=record

v:real;

next:pointer;

end;

stack=record;

fs,l,t,b:^num;

count:integer;

end;

 

var

store:stack;

i,j:integer;

n1,n2,res:real;

s:char;

pexpr, st:string;

f:text;

procedure initializationS;

var i:integer;

begin

new(store.fs);

store.t:=store.fs;

for i:=2 to 100 do

begin

new(store.l);

store.t^.next:=store.l;

store.t:=store.l;

 

end;

store.t:=store.fs;

store.b:=NIL;

store.l^.next:=NIL;

store.count:=0;

end;

 

procedure push(val:real);

begin

if store.count=100 then

begin

writeln(‘Error. Stack overflow’);

readkey;

exit;

end;

 

store.b:=store.t;

store.t^.v:=val;

store.t:=store.b^.next;

Inc(store.count);

end;

 

procedure pop(var val:real);

begin

if store.t=store.fs then

begin

writeln(‘Error! Stack is empty.’);

readkey;

exit;

end;

 

if store.fs^.next=store.t then

begin

store.t:=store.fs;

val:=store.t^.v;

Dec(store.count);

exit;

end;

 

store.b:=store.fs^.next;

while store.b^.next<>store.t do

begin

store.b:=store.b^.next;

end;

 

store.t:=store.b;

store.b:=Nil;

val:=store.t^.v;

Dec(store.count);

end;

 

function getC:char;

begin

getC:=pexpr[1];

Delete(pexpr,1,1);

end;

 

BEGIN

clrscr;

initializationS;

Assign(f,fl);

Rewrite(f);

write(‘Enter the expression > ‘);

readln(pexpr);

for j:=1 to 6 do

write(f,’-‘);

write(f,’+’);

for j:=1 to 15 do

write(f,’-‘);

write(f,’+’);

for j:=1 to 30 do

write(f,’-‘);

writeln(f,»);

writeln(f,’Symbol’:6,’|’,’Input’:15,’|’,’Stack’:30);

for j:=1 to 6 do

write(f,’-‘);

write(f,’+’);

for j:=1 to 15 do

write(f,’-‘);

write(f,’+’);

for j:=1 to 30 do

write(f,’-‘);

writeln(f,»);

while pexpr<>» do

begin

s:=getC;

write(f,s:6,’|’);

if pos(s,’+-*/^’)=0 then

begin

write(s,’: ‘);

readln(n1);

write(f,’ ‘,s,’=’,n1:0:2);

Str(n1:0:2,st);

write(f,’ ‘:15-length(st)-3,’|’);

push(n1);

end else

begin

write(f,’ ‘:15,’|’);

if store.count<=1 then

begin

writeln(‘WRONG EXPRESSION’);

writeln(‘Press any key…’);

readkey;

rewrite(f);

writeln(f,’WRONG EXPRESSION’);

close(f);

exit;

end else

begin

pop(n2);

pop(n1);

if(s=’/’)and(abs(n2)<1E-10) then

begin

writeln(‘DIVIDE BY 0’);

writeln(‘press any key…’);

readkey;

rewrite(f);

writeln(f,’DIVIDE BY 0′);

close(f);

exit;

end else

begin

case s of

‘+’: res:=n1+n2;

‘-‘: res:=n1-n2;

‘*’: res:=n1*n2;

‘/’: res:=n1/n2;

‘^’: res:=Exp(n2*Ln(n1));

end;

push(res);

end;

end;

end;

write(f,’ ‘);

store.b:=store.fs;

while store.b<>store.t do

begin

write(f,store.b^.v:0:1,’ ‘);

store.b:=store.b^.next;

end;

writeln(f);

end;

 

for j:=1 to 6 do

write(f,’-‘);

write(f,’+’);

for j:=1 to 15 do

write(f,’-‘);

writeln(f,’+’);

 

if store.count=1 then

begin

writeln(f,’Result = ‘, store.fs^.v:0:2);

end else

begin

writeln(‘WRONG EXPRESSION’);

writeln(‘Press any key…’);

readkey;

rewrite(f);

writeln(f,’WRONG EXPRESSION’);

close(f);

exit;

end;

 

close(f);

clrscr;

reset(f);

while not EOF(f) do

begin

readln(f,pexpr);

writeln(pexpr);

end;

close(f);

writeln(‘Press any key for continue…’);

readkey;

END.

 

Обчислювальний експеримент

Правильні арифметичні вирази

 

Рисунок 3.1

 

 

 

 

Рисунок 3.2

 

Неправильний арифметичний вираз

 

Рисунок 3.3

 

 

 

 

Рисунок 3.4

 

 

 

  1. Висновок

 

Під час виконання цієї роботи я розглянула динамічні структури даних та методи роботи з ними. Реалізувала алгоритм для розрахування арифметичних виразів та протестувала його на правильність виконання.

Дана робота є прикладом обробки інформації, представленої у вигляді бінарного дерева, які наочно дозволяє побачити можливості реалізації запитів, передбачених алгоритмом, тобто здійснення ряду операцій над даними такої структури.

Опис алгоритму програмним способом реалізовано за допомогою мови Паскаль.

Робота з різного роду даними є дуже актуальною. Вирішення таких завдань дозволяється скоротити витрачається час на обробку даних і підвищити ефективність самої роботи.

 

 

  1. Список використаної літератури

 

1). http://studopedia.org/10-14068.html

2). http://www.slideshare.net/Akcionerr/pascal-20185004

3). http://www.cyberforum.ru/turbo-pascal/thread615673.html

4). http://vidpo.net/shho-take-stek-v-programuvanni.html

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s