• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Спадкування

End.

Repeat

Begin

Else

Begin

Begin

Begin

Begin

Begin

Begin

Begin

Begin

Begin

Type

Repeat

Begin

Begin

Begin

Begin

Begin

Begin

Begin

Begin

Begin

Begin

Алгоритми

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 thenindex:=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]<>kdoindex:=index-1;

end;

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

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

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

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

varl,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

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;

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

constnotfound = -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), наприклад:

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;

procedureDot.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:

withDotl do

Init(100,100);

Show;

Move(50,50);

end;

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

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

program ObjDot;

uses crt, graph;

typeDot=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

thenWriteLn(GraphErrorMsg(Err))

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

Dotl.Show;

while KeyPressed do

a:=ReadKey;

a:=ReadKey;

caseord(a) of

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

80:Dotl.Move(0,5);

77:Dotl.Move(5,0);

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

end;

until а = chr(27);

end;

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

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

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

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

Припустимо, ми створюємо програму, у якій крім об'єкта-точки, фігурує, також об'єкт-коло. Звичайно, можна було б опис цього нового типу створити з нуля, подібно тому, як ми описали тип Dot у попередньому розділі. Однак цей новий тип коло (назвемо його Ring) має багато загального з існуючим типом Dot. Насправді, як і точка, коло характеризується двома координатами: А и В, що визначають положення її центра. Однак для створюваного об'єкта необхідно додати поле, що задає радіус кола.

Що стосується методів, то для нового типу Ring підійшов би метод Move, оскільки переміщення точки і переміщення кола (власне, її центра) по екрану здійснюється однаково. Однак метод, що ініціалізує об'єкт (Init), а також методи, що роблять коло видимим чи невидимим (Show і Hide), прийдеться створити нові.

Отже, ми з'ясували, що новий тип Rіng де в чому повторює тип Dot. А чи не можна новий тип створити на основі вже існуючого, просто додавши в нього нові поля і методи? Виявляється, це можливо завдяки властивості об'єктних типів, відомому як спадкування. Оскільки мова йде про спадкування, відповідно до генеалогічної термінології існуючий тип, що є основою для створення нового об'єкта, називають предком, чи батьківським типом, а створюваний об'єкт:— нащадком, чи дочірнім типом. Нащадок автоматично успадковує всі поля і методи свого предка.

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

А тепер повернемося до наших типів Dot і Ring. B описі типу-нащадка повинний вказуватися ім'я батьківського типу (у круглих дужках після зарезервованого слова OBJECT):

typeRing = object (Dot)

Rad : integer;

end;

У приведеному описі типу Ring мається поле Rad, яке визначає радіус кола, якого не було в типу Dot. Крім того, тип Ring успадкував усі поля свого предка (два значення типу INTEGER, що визначають положення точки на екрані). Однак тут поки відсутні методи. От як може виглядати опис типу Ring, доповнене відповідними методами:

Ring = object (Dot)

Rad : integer

procedure Init (x, у, r : integer)

procedure Show;

procedureHide;

end;

procedure Ring.Init;

Читайте також:

1. Аутосомно_рецесивний тип успадкування.
2. Здійснення права на спадкування. Оформлення права на спадщину.
3. Зчеплене успадкування.
4. Зчеплене успадкування.
5. Крок 1. Успадкування батьківських методів.
6. Множинне спадкування
7. Особливості спадкування за законом
8. Поняття спадкового права. Порядок спадкування.
9. Поняття спадкового права. Спадкування.
10. Поняття спадкування
11. Поняття спадкування, час і місце відкриття спадщини.
12. Поняття спадкування. Види спадкування

Переглядів: 814