Ноу Інти, лекція, абстрактні типи даних

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

Розробка абстрактних моделей для даних і способів обробки цих даних є найважливішим компонентом в процесі вирішення завдань за допомогою комп'ютера. Приклади цього ми бачимо і на низькому рівні в повсякденному програмуванні (наприклад, при використанні масивів і зв'язкових списків, розглянутих в "Елементарні структури даних"), і на високому рівні при вирішенні прикладних задач (як при вирішенні завдання зв'язності за допомогою лісу об'єднання-пошук в "Введення"). У цій лекції розглядаються абстрактні типи даних (abstract data type. Надалі АТД), що дозволяють створювати програми з використанням високорівневих абстракцій. Абстрактні типи даних дозволяють відокремлювати абстрактні (концептуальні) перетворення, які програми виконують над даними, від будь-якого конкретного уявлення структури даних і будь-якої конкретної реалізації алгоритму.

Всі обчислювальні системи засновані на рівнях абстракції: певні фізичні властивості кремнію та інших матеріалів дозволяють прийняти абстрактну модель біта, який може приймати виконавчі значення 0-1; потім на динамічних властивостях значень певного набору бітів будується абстрактна модель машини; далі, на основі принципу роботи машини під управлінням програми на машинній мові будується абстрактна модель мови програмування; і, нарешті, будується абстрактне поняття алгоритму, що реалізовується у вигляді програми на мові C ++. Абстрактні типи даних дають можливість продовжувати цей процес далі і розробляти абстрактні механізми для певних обчислювальних задач на більш високому рівні, ніж це забезпечується системою C ++, розробляти абстрактні механізми. орієнтовані на конкретні програми і відповідні для вирішення завдань в численних прикладних областях, а також створювати абстрактні механізми вищого рівня, в яких використовуються ці базові конструкції. Абстрактні типи даних надають в наше розпорядження розширюваний до нескінченності набір інструментальних засобів для вирішення все нових і нових завдань.

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

Для розробки нового рівня абстракції буде потрібно (1) визначити абстрактні об'єкти, з якими необхідно маніпулювати, і операції. які повинні виконуватися над ними; (2) представити дані в деякій структурі даних і реалізувати операції; (3) і (найголовніше) забезпечити, щоб ці об'єкти було зручно використовувати для вирішення прикладних завдань. Ці пункти можна застосувати й до простих типів даних, так що базові механізми для підтримки типів даних, які були розглянуті в "Елементарні структури даних". можна адаптувати для наших цілей. Однак мова C ++ пропонує важливе розширення механізму структур, зване класом (class). Класи виключно корисні при створенні рівнів абстракції і тому розглядаються в якості основного інструменту, який використовується для цієї мети в решти книги.

Визначення 4.1. Абстрактний тип даних (АТД) - це тип даних (набір значень і сукупність операцій для цих значень), доступ до якого здійснюється тільки через інтерфейс. Програму, яка використовує АТД, будемо називати клієнтом, а програму, яка містить специфікацію цього типу даних - реалізацією.

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

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

Як приклад розглянемо інтерфейс типу даних для точок (програма 3.3) з розділу 3.1 "Елементарні структури даних". У цьому інтерфейсі явно оголошується, що точки представлені як структури, що складаються з пари чисел з плаваючою точкою, що позначаються x і у. Подібне застосування типів даних є звичайним в великих системах програмного забезпечення: ми розробляємо набір угод про подання даних (а також визначаємо ряд пов'язаних з ними операцій) і робимо ці правила доступними через інтерфейс. щоб ними могли користуватися клієнтські програми, що входять до складу великої системи. Тип даних забезпечує узгодженість всіх частин системи з поданням основних загальносистемних структур даних. Якою б гарною така стратегія не була, вона має одну ваду: якщо необхідно змінити уявлення даних. то потрібно змінити і всі клієнтські програми. Програма 3.3 знову дає нам простий приклад: одна з причин розробки цього типу даних - зручність роботи клієнтських програм з точками, і ми очікуємо, що в разі потреби у клієнтів буде доступ до окремих координатам точки. Але ми не можемо перейти до іншого поданням даних (скажімо, до полярних координат, або тривимірним координатам, або навіть до інших типів даних для окремих координат) без зміни всіх клієнтських програм.

На відміну від цього, програма 4.1 містить реалізацію абстрактного типу даних, відповідно до типу даних з програми 3.3, але з використанням класу мови C ++, в якому відразу визначені як дані, так і пов'язані з ними операції. Програма 4.2 є клієнтською програмою, яка працює з цим типом даних. Ці дві програми виконують ті ж самі обчислення, що і програми 3.3 і 3.8. Вони ілюструють ряд основних властивостей класів, які ми зараз розглянемо.

Коли ми пишемо в програмі визначення на кшталт int i, ми вказуємо системі зарезервувати область пам'яті для даних (вбудованого) типу int. до якої можна звертатися по імені i. У мові C ++ для подібних сутностей є термін об'єкт. При записи в програмі такого визначення, як POINT p, кажуть, що створюється об'єкт класу POINT. до якого можна звертатися по імені p. У нашому прикладі кожен об'єкт містить два елементи даних, з іменами x і у. Як і в випадку структур, до них можна звертатися за іменами на кшталт p.y.

Елементи даних x і у називаються даними-членами класу. У класі можуть бути також визначені функції-члени, які реалізують операції. пов'язані з цим типом даних. Наприклад, клас. визначений у програмі 4.1, має дві функції-члена з іменами POINT і distance.

Клієнтські програми, такі як програма 4.2, можуть викликати функції-члени, пов'язані з об'єктом, вказуючи їх імена точно так же, як і імена даних, що знаходяться в якій-небудь структурі struct. Наприклад, вираз p.distance (q) обчислює відстань між точками p і q (таку ж відстань повинен повертати і виклик q.distance (p)). Функція POINT () - перша функція в програмі 4.1 - є особливою функцією-членом, званої конструктором: у неї таке ж ім'я, як і у класу, і вона викликається тоді, коли потрібно створити об'єкт цього класу.

Програма 4.1. Реалізація класу POINT (точка)

В цьому класі визначено тип даних. який складається з набору значень, що представляють собою "пари чисел з плаваючою точкою" (мається на увазі, що вони інтерпретуються як точки на декартовій площині), а також дві функції-члена, визначені для всіх екземплярів класу POINT. функція POINT (). яка є конструктором, ініціалізувалися координати випадковими значеннями від 0 до 1, і функція distance (POINT). обчислює відстань до іншої точки. Подання даних є приватним (private), і звертатися до нього або модифікувати його можуть тільки функції-члени. Самі функції-члени є загальнодоступними (public) і доступні для будь-якого клієнта. Код можна зберегти, наприклад, у файлі з ім'ям POINT .cxx.

Програма 4.2. Програма-клієнт для класу POINT (знаходження найближчої точки)

Ця версія програми 3.8 є клієнтом, який використовує АТД POINT. визначений у програмі 4.3. Операція new [] створює масив об'єктів POINT (викликаючи конструктор POINT () для ініціалізації кожного об'єкта випадковими значеннями координат). Вираз a [i] .distance (a [j]) викликає для об'єкта a [i] функцію-член distance з аргументом a [j].

Визначення POINT p в програмі-клієнті приводить до виділення області пам'яті під новий об'єкт і потім (за допомогою функції POINT ()) до присвоєння кожному з двох його елементів даних випадкового значення в діапазоні від 0 до 1.

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

Ми розглядаємо описаний вище приклад невеликого класу просто щоб познайомитися з основними рисами класів; тому він далеко не повний. У реальному коді для класу точки у нас буде набагато більше операцій. Наприклад, в програмі 4.1 відсутні навіть операції. що дозволяють дізнаватися значення координат x і y. Як ми побачимо, додавання цих та інших операцій - досить просте завдання. У частині 5 ми більш детально розглянемо класи для точки і інших геометричних абстракцій, наприклад, ліній і багатокутників.

У мові C ++ (але не в С) у структур також можуть бути пов'язані з ними функції. Ключове відмінність між класами і структурами пов'язане з доступом до інформації, який характеризується ключовими словами private і public. До приватному (private) члену класу можна звертатися тільки всередині класу, а до загальнодоступного (public) члену класу може звертатися будь-який клієнт. Приватним членами можуть бути як дані, так і функції: в програмі 4.1 приватними є лише дані, але далі ми побачимо численні приклади класів, в яких приватними будуть також функції-члени. За замовчуванням члени класів є приватними, а члени структур - загальнодоступними.

Наприклад, в клієнтській програмі, що використовує клас POINT. не можна посилатися на дані-члени p.x, p.y і т.д. як це можна зробити для структури POINT. оскільки члени класу x і y є приватними. Для обробки точок можна лише скористатися загальнодоступними функціями-членами. Такі функції мають прямий доступ до даних-членам будь-якого об'єкта свого класу. Наприклад, при виклику p.distance (q) функції distance з програми 4.1 ім'я x в операторі dx = x - ax відноситься до даного-члену x з точки p (оскільки функція distance була викликана як функція -член примірника p), а ім'я ax відноситься до даного-члену x з точки q (тому що q - фактичний параметр. відповідний формальному параметру a). Для виключення можливої ​​двозначності або плутанини можна було б записати dx = this-> x-a.x - ключове слово this означає покажчик на об'єкт. для якого викликана функція -член.

Коли до даних-членам застосовується ключове слово static. це, як і у випадку звичайних членів, означає, що існує тільки одна копія цієї змінної (що відноситься до класу), а не безліч копій (що відносяться до окремих об'єктів). Ця можливість часто використовується, наприклад, для відстеження статистики, що стосується об'єктів: можна включити в клас POINT змінну static int N. додати в конструктор N ++ - і тоді з'явиться можливість знати кількість створених точок.

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

Статична функція -член може мати доступ до членів класу, але не повинна викликатися для конкретного об'єкта.