Repeat begin

Begin

Begin

Begin

Begin

Begin

Begin

Begin

Begin

Repeat

Begin

Begin

Begin

Begin

Begin

Begin

Begin

Begin

Begin

Алгоритми

Дерево

Список

Масив

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

Для того щоб зберігати таблицю, нам буде потрібно запис із двох полів: сам масив і цілочисльне поле, що позначає поточний розмір масиву:

const maxsize = 2000; {максимальний розмір таблиці}

type tTable = record

a: array [1..maxsize] of tItem; {це сам масив}

n: integer; {а це - реальне число елементів}

end;

var Table: tTable;

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

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

Як виглядає така таблиця на Паскалі нам уже відомо:

type tItemPtr = ^tItem; {покажчик на елемент списку}

tItem = record {елемент списку}

key: tKey;

data: tData;

next: tItemPtr;

end;

tList: tItemPtr; {задається покажчиком на перший елемент}

var Table: tList {таблиця є списком}

Як зберігати і шукати дані в двійковому дереві, ми вже знаємо, а таблицю можна задати так:

type tItemPtr = ^tItem; {покажчик на елемент}

tItem = record {елемент}

key: tKey;

data: tData;

left, right: tItemPtr;

end;

tTree = tItemPtr;

var Table: tTree; {таблиця є деревом}

1. Лінійний пошук у масиві

Нехай таблиця представлена у виді масиву. Тоді перше, що приходить у голову з приводу пошуку елемента — це обхід всіх елементів, починаючи з першого, доти, поки не буде знайдений елемент із шуканим ключем, чи поки масив не скінчиться. Такий спосіб називається лінійним пошуком у неупорядкованому масиві. Оформимо його на Паскалі у виді процедури:

procedure LinearSearch(var T:tTable; k:tKey; var index:integer);

var i: integer;

i:=1; index:=0;

while (i<=T.n) and (index=0) do begin

if T.a[i].key=k then index:=i;

i:=i+1;

end;

end;

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

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

procedure LinearSearch2(var T:tTable; k:tKey; var index:integer);

var i: integer;

T.a[0]:=k;

index:=T.n; index:=0;

while T.a[index]<>k do index:=index-1;

end;

У такому варіанті стає значно менше порівнянь, отже, алгоритм працює швидше попереднього.

2. Двійковий пошук

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

procedure BinarySearch(var T:tTable; k:tKey; var index:integer);

var l,c,r: integer;

index:=0;

l:=1; r:=T.n;

while (index=0) and (l<=r) do begin

c:=(l+r) div 2;

if T.a[c].key=k then index:=c

else if T.a[c].key>k then r:=c-1

else l:=c+1;

end;

end;

Змінні l, r і c позначають відповідно номер лівого краю, центра і правого краю частини масиву, у якій ми шукаємо елемент із заданим ключем. Пошук припиняється або якщо елемент знайдений (index <> 0), або якщо частина масиву, у якій потрібно шукати, була вичерпана (тобто номер лівого краю перевищив номер правого). Усередині циклу знаходимо номер середини частини масиву (c), потім порівнюємо ключ цього середнього елемента із шуканим ключем. Якщо виконалася рівність, то елемент знайдений, якщо середній більше шуканого, то встановлюємо праву границю частини масиву рівною c-1, якщо більше — змінюємо ліву границю на c+1.

3. Лінійний пошук у списку

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

procedure SearchInList(T: tTable; k: tKey; var p: tItemPtr);

var notfound: boolean;

notfound:=true;

p:=T;

while (p<> nil) and (notfound) do begin

if p^.key=k then notfound:=false;

p:=p^.next;

end;

end;

Параметр T у цьому випадку не потрібно робити параметром-змінною, оскільки він є тільки покажчиком на початок таблиці, а сама таблиця лежить у динамічній пам'яті. Замість номера знайденого елемента будемо повертати користувачу нашої процедури покажчик на нього (якщо пошук був удалим) чи nil, якщо пошук невдалий.

Скорочувати число перевірок у циклі за допомогою бар'єра було б нерозумно: щораз бар'єр прийдеться ставити в «хвіст» списку, а для цього потрібно спочатку обійти весь список, починаючи з голови, затрачаючи при цьому багато часу.

Змішані таблиці

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

Дозволимо даним розташовуватися в будь-яких елементах масиву, а не тільки в перших n. Щоб відрізняти порожні елементи від зайнятих нам знадобиться спеціальне значення ключа, яке ми будемо заносити в ключове поле всіх порожніх комірок. Якщо ключ — число, а всі корисні ключі позитивні, то можна як ключ порожньої комірки використовувати 0, якщо ключі — рядки, що містять прізвища, то ключем порожньої комірки можна зробити порожній рядок і т.п. Нехай ключами є рядки, тоді для таблиці будуть потрібні такі оголошення:

const empty = '';

nmax = 1000;

type tKey = string;

tData =.....;

tItem = record

key: tKey;

data: tData;

end;

tTable = array [0..nmax-1] of tItem;

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

Реалізована описаним способом таблиця називається змішаною (чи hash-таблицею), а функція — функцією розміщення ключів (hash-функцією). Такі назви зв'язані з тим, що дані безладно розкидано по масиву.

Тепер покажемо, як усе сказане втілити в програму на Паскалі. Як ключі в наших прикладах використовуються рядки, тому можна запропонувати такий варіант хэш-функции: скласти коди всіх символів рядка, і, щоб отримане число не виходило за максимально можливий індекс масиву, візьмемо залишок від ділення на розмір масиву:

function hash(key: tKey): integer;

var i: integer;

sum:=0;

for i:=1 to length(key) do sum:=sum+ord(key[i]);

hash:= sum mod nmax;

end;

Процедура додавання елемента в таблицю в попередньому варіанті буде виглядати так:

procedure AddItem(var t: tTable; item: tItem);

var h: integer;

h:=hash(item.key);

t[h]:=item.key;

end;

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

Найбільш проста хэш-функція буде додавати до номера зайнятої комірки яке-небудь постійне число:

const HC = 7;

function hash2(n: integer, key: tKey): integer;

hash2:= (n + HC) mod nmax;

end;

Залишок від ділення на nmax знадобилося обчислювати по тій же причині, що й у первинній хэш-функції.

Зараз можна написати остаточний варіант процедури додавання елемента даних у таблицю:

procedure AddItem(var t: tTable; item: tItem);

var h: integer;

h:=hash(item.key);

while t[h].key<>empty do h:=hash2(h,item.key);

t[h].key:=item.key;

t[h].data:=item.data;

end;

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

const notfound = -1;

continue = -2;

procedure Search(var t: tTable; key: tKey; var index: integer);

var h: integer;

h:=hash(key);

index:=continue;

if t[h].key = key then index:=h

else if t[h].key = empty then index:= notfound

else h:=hash2(h,key);

until index<>сontinue;

end;

Процедура видає відповідь про результати пошуку через параметр-змінну index. При вдалому пошуку там буде лежати номер знайденого елемента, при невдалому — константа notfound. Константа continue означає «поки не знайдений» і використовується тільки усередині процедури. При пошуку спочатку обчислюється значення первинної хэш-функції, а в index заноситься значення continue. Потім виконується перевірка на рівність ключів, якщо вона виконується, то комірка масиву знайдена, і ми записуємо її номер у index, інакше, якщо комірка порожнія, то елемент не знайдений (у index записуємо notfound), у третьому випадку знаходимо значення вторинної функції. Ці дії продовжуються доти, доки index не перестане бути рівним continue.

Об’єктно-орієнтоване програмування.

Що таке об’єктно-орієнтоване програмування

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

Пізніше ідея структурування програм одержала подальший розвиток. Мова йде про концепцію модулів. Модуль— це файл який компілюється Turbo Pascal, і у якому можуть міститися описи констант, типів даних, змінних, а також процедур і функцій.

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

Необхідно відзначити, що объектно-ориентироване програмування— це не для простих програм, що виконують нескладні розрахунки. Якщо в подібному випадку застосувати методи ООП, така програма буде виглядати перевантаженою зайвими мовними конструкціями. Якщо ж створювана програма досить об'ємна, засоби ООП виявляються дуже і дуже до речі.

В основі объектно-ориентированного програмування лежать три основних принципи: інкапсуляція, спадкування і поліморфізм. З зазначеними принципами ми познайомимося нижче.

Інкапсуляція

Опис об'єкта (як і всіх інших типів) повиний міститися в розділі описів. Дані, що містить об'єкт, називаються nолями об'єкта. Опис найпростішого об'єктного типу дуже схожий на опис запису, тільки замість одного зарезервованого слова (RECORD) використовується інше (OBJECT), наприклад:

type

Dot = object

a, b: integer;

end;

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

Як уже відзначалося, крім даних у виді полів (які можуть належати будь-якому типу, у тому числі й об'єктному), об'єкт також може містити підпрограми, що описують дії, припустимі над цими полями. Такі підпрограми називаються методами. Метод має доступ до полів об'єкта, не потребуючи передачі їх йому як параметрів. Властивість об'єктів, містити в собі не тільки дані (поля), але й описи дій, припустимих над цими даними (методи), називається інкапсуляцією.

При цьому безпосередньо в описі об'єкта присутні тільки заголовки підпрограм, а тіло кожної підпрограми задається окремо. Повернемося до типу Dot з попереднього приклада. От як виглядає опис цього об'єктного типу, доповнений необхідними методами (описи полів завжди повинні передувати заголовкам методів):

Dot=object

a, b: integer;

procedure Init (x,y: integer);

procedure Show;

procedure Hide;

procedure Move (Da,Db: integer)

end;

procedure Dot.Init;

a:=x;b:=y;

end;

procedure Dot.Show;

PutPixel (a,b,White);

end;

procedure Dot.Hide;

PutPixel (a,b,Black);

end;

procedure Dot.Move;

Hide;

a:=a+Da; b:=b+Db;

Show

end;

У цьому прикладі об'єкт містить чотири методи. Метод Init инициализирует об'єкт (тобто приcвоює точці на екрані деякі початкові значення). Методи Show і Hide "запалюють" і "гасять" точку на екрані. Нарешті, метод Move переміщає точку по екрані.

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

var Dotl: Dot;

Тут оголошена (статична) змінна Dotl (чи екземпляр об'єкта), що належить типу Dot. Після того як екземпляр об'єкта створений, його поля стають доступні для методів, хоча до полів об'єкта можливий і безпосередній доступ— як до полів запису (цього Turbo Pascal не забороняє). Для того щоб безпосередньо застосувати до поля об'єкта яку-небудь стандартну підпрограму, досить скористатися його складеним ім'ям — вказати ідентифікатор об'єкта і (через крапку) ідентифікатор цього поля. Однак такий підхід був би відступом від принципів об’єктно-орієнтованого програмування (ООП). ООП припускає використання при маніпулюванні полями об'єкта тільки його методів. Наприклад:

Dotl.Init(100,100);

Dotl.Show;

Dotl.Move(50,50);

Так само, як до записів, до об'єктів застосуємо оператор WITH:

with Dotl do

begin

Init(100,100);

Show;

Move(50,50);

end;

Представлені вище послідовності операторів еквівалентні.

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

program ObjDot;

uses crt, graph;

type Dot= object

a, b: integer;

procedure Init (x,y:integer);

procedure Show;

procedure Hide;

procedure Move (Da, Db: integer);

end;

procedure Dot.Init;

a:=x; b:=y;

end;

procedure Dot.Show;

PutPixel (a,b,White);

end;

procedure Dot,Hide;

PutPixel (a,b,0);

end;

procedure Dot.Move;

Hide;

a:=a+Da;

b:=b+Db;

Show

end;

var i,j,k,Err: integer;

а: char;

Dotl: Dot;

begin {тіло програми}

i:=detect;

initgraph (i,j,");

Err:= GraphResult;

If Err <> grOK then

WriteLn (GraphErrorMsg(Err))

el s e begin

Dotl.Init(GetMaxX div 2, GetMaxY div 2)

Dotl.Show;

while KeyPressed do

a:=ReadKey;

a:=ReadKey;

case ord (a) o f

72:Dotl.Move(0,-5);

80:Dotl.Move(0,5);

77:Dotl.Move(5,0);

75:Dotl.Move(-5,0);

end;

end;

until а = chr(27);

end;

end.

У програмі оголошений уже знайомий нам об'єкт Dot, що містить два поля: А и В, що визначають положення точки на екрані, а так само чотири методи: Init, Show, Hide і Move.

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

Далі стоїть оператор REPEAT, що виявляє натискання визначеної клавіші. Оператор CASE тут містить чотири варіанти, що відповідають чотирьом клавішам-стрілкам. Кожний зі згаданих варіантів викликає метод Move c фактичними параметрами, що забезпечують переміщення світної точки в потрібному напрямку і на визначену відстань — на п'ять пікселей.

Умовою завершення циклу, організованого за допомогою оператора REPEAT, є натискання клавіші, що генерує скен-код 27 (це клавіша <Esc>). На цьому завершує роботу і вся програма в цілому.

Дата добавления: 2014-12-16