Знайте, Intuit, лекция, абстрактни типове данни
Анотация: основни абстрактни типове данни, като например стекове и опашки, както и изпълнението с помощта на основни структури от данни.
Развитие на абстрактни модели и методи за обработка на данни на данните е критичен компонент в процеса на решаване на проблеми с компютъра. Примери за това можем да видим и на ниско ниво в ежедневието програмиране (например, като се използват масиви и свързани списъци, разгледани в "Начални структури от данни"), както и на по-високо ниво за решаване на приложни проблеми (като при решаването на проблема с връзката с помощта на съюза-намерят гора в "Въведение"). Тази лекция обсъжда абстрактни типове данни (абстрактен тип данни. Освен това ADT), което позволява да се създаде програма, която използва абстракции от високо ниво. Абстрактни типове данни позволяват отделно абстрактно (концептуална) превръщане кои програми работят на данни от всяка конкретна представяне на структури от данни и всяка конкретна реализация на алгоритъма.
Всички компютърни системи са базирани на нива на абстракция: някои физични свойства на силиций и други материали дават възможност да се вземе един абстрактен модел на битовете, които могат да се двоични стойности на 0-1; след това на динамичните свойства на стойности на определени части от комплекта построен абстрактен модел на машината; Освен това, въз основа на принципа на работа на машината под контрола на една програма в машинен език изгради абстрактен модел на език за програмиране; и накрая конструирана абстрактно понятие на алгоритъма, който се осъществява под формата на програма на C ++. Абстрактни типове данни дават възможност да продължи този процес по-далеч и да се разработят механизми за абстрактни определени изчислителни задачи на по-високо ниво от това, предоставена от C ++ система, развитие на абстрактните механизми. ориентирани приложения и е подходящ за решаване на проблеми в много области на приложение, и да се създаде абстрактни механизми на по-високо ниво, които използват тези основни структури. Абстрактни типове данни, с които разполагаме за неопределено време разтегателен инструментариум за решаване на все повече и повече проблеми.
От една страна, използването на абстрактни дизайни освободи от тревогите на подробния устройствен изпълнението им; От друга страна, когато изпълнението на програмата е важно, е необходимо да се знае цената на извършване на основни операции. Ние използваме много основни абстракции, които са вградени в хардуера на компютъра и осигуряват основата за машинни инструкции; изпълнява и други абстракции в софтуера; и да използвате допълнителен абстракция на писмено рано софтуерна система. Абстрактни дизайн на високо ниво често са създадени на базата на по-прости модели. На всички нива, той има един и същ основен принцип: необходимо е да се намери най-важните операции в програмите и най-важните характеристики на данните, а след това да определят точно тези и други на абстрактно ниво и да се разработят ефективни механизми за тяхното специфично изпълнение. В тази глава ще разгледаме много примери за този принцип.
Да се разработи се изисква ново ниво на абстракция (1) да определят абстрактни обекти, които трябва да бъдат манипулирани и операции. да се извършва върху тях; (2) представя данните в структурата на данните и осъществяване на операцията; (3) и (най-важното), за да се гарантира, че тези съоръжения са били полезни за приложения. Тези елементи се отнасят за прости типове данни, така че основните механизми за подкрепа на типове данни, които са били разгледани в "Начални структури от данни." Той може да бъде адаптиран за нашите цели. Въпреки това, ++ механизъм за удължаване език C предлага важна структура, наречена клас (клас). Класове са изключително полезни при създаване нива на абстракция и следователно се счита като основен инструмент, използван за тази цел в останалата част на книгата.
Определение 4.1. тип Резюме на данни (ADT) - това е от типа на данните (набор от ценности, както и набор от операции за тези стойности), който може да бъде достъпен само чрез интерфейса. Програма, която използва ADT ще се обадя на клиента и програмата със спецификацията на този тип данни - реализация.
Тази дума само прави абстрактен тип данни: ADT в случай на клиентските програми не разполагат с достъп до стойностите на данните по някакъв друг начин, с изключение на операциите, описани в интерфейса. Представянето на тези данни и функции, които изпълняват тези операции. Те са за изпълнение и напълно отделени от клиентския интерфейс. Ние казваме, че интерфейсът не е прозрачна: клиентът не може да види изпълнението на интерфейса.
Програмите в C ++, тази разлика обикновено се извършват малко по-ясни, тъй като най-лесният начин за създаване на интерфейс. включва представяне на данни. но посочи, че клиентския софтуер не е разрешено директен достъп до данните. С други думи, разработчиците на клиентски приложения могат да знаят представяне на данните. но по никакъв начин не може да го използва.
Като пример, помислете за вида на интерфейса на данни за точки (Програма 3.3) от раздел 3.1, "елементарни структури от данни." изрично обявен в интерфейса, че точките са представени като структура, състояща се от двойка числа с плаваща запетая, обозначени х и у. Такова използване на типове данни, се среща често в големи софтуерни системи: ние се разработи серия от споразумения за представяне на данни (също определя редица свързани с тях сделки) и да предостави тези правила за интерфейса. така че те могат да използват клиентски програми, които са част от по-голяма система. типа на данните осигурява последователност във всички части на системата с основните цялата система структури от данни производителност. Без значение колко добър може да бъде такава стратегия, той има един недостатък: ако искате да промените данните на изображението. ще трябва да се променят всички програми на клиента. Програма 3.3 пак ни дава един прост пример: една от причините за развитието на този вид данни - използваемостта на клиентските програми с точките, и ние очакваме, че ако е необходимо, клиентите ще имат достъп до отделните координатите на точката. Но ние не можем да отидете в друга представяне на данни (например, за да полярни координати, или триизмерни координати, или дори други типове данни за отделните координати), без да променя всички клиентски програми.
За разлика от това, програмата съдържа 4,1 прилагане абстрактен тип данни, типа данни на съответните програми 3.3, но с помощта на езика C ++ клас, които някога са идентифицирани данни, така и на свързаните с тях операции. Програма 4.2 е клиент програма, която работи с този тип данни. Тези две програми се представят същите изчисления като програмата 3.3 и 3.8. Те илюстрират някои от основните свойства на класовете, които ние сега се разгледа.
Когато се напише програма, сякаш съм на определение вътр, посочено от нас система за резервиране на площ с памет за данни (вградени) тип Int. които могат да бъдат достъпни от името и. С ++ език е достъпно за подобни структури Терминът обект. Когато записвате в програмата на такова решение, тъй като точка Р, че създадете обект от клас Point. които могат да бъдат достъпни от името на р. В този пример, всеки обект съдържа два елемента от данни, с имената на х и у. Както и в случая на структури, те могат да бъдат достъпни от имена като p.y.
Елементите на данните на х и у са наречени член на класа данни. Класът може да бъде определена и член-функции, които изпълняват операции. , свързани с този вид данни. Например, клас. определени в програмата 4.1 има две функции страни с имена POINT и разстояние.
Клиентски програми, като например програмата 4.2, могат да причинят функцията член свързан с предмета, като посочва техните имена по същия начин, както и тези имена са във всяка структура структура. Например, p.distance експресия (р) изчислява разстоянието между точките Р и Q (същото разстояние трябва да се върне и q.distance (р) повикване). ТОЧКА () функция - първата функция в програмата 4.1 - е специален член функция се нарича конструктор: той има същото име като на класа, и той се нарича, когато искате да се създаде обект от този клас.
Програма 4.1. ТОЧКА клас изпълнение (точка)
Този клас определя типа данни. който се състои от набор от стойности, представляващи "чифт плаваща точка" (приема се, че те се интерпретират като точка на декартовата равнина), както и две функции на потребителя, определени за всички случаи на точката на клас. ТОЧКА () функция. който е конструктор инициализиране координати със случайни стойности от 0 до 1, и функцията на разстояние (точка). изчислява разстоянието до друга точка. Подаване на данни е поверително (частни), и се прилагат само за член-функции може да го или го променят. член-функции Сами са публични (обществени) и са на разположение на всеки клиент. Можете да запишете кода, например, във файл, наречен ТОЧКА .cxx.
Програма 4.2. Клиент софтуер за точката на клас (намиране на най-близката точка)
Тази версия 3.8 е клиент, който използва ADT момент. определено в програмата 4.3. Операция нов [] масив от обекти, създава точка (точка обадите на строителя (), за да се инициализира всеки обект случайни стойности на координатите). Експресия на [Ь] .distance (а [й]) за обекта причинява [Ь] член функция -distance с аргумент на [й].
Определяне точка Р в резултатите от клиентската програма в освобождаването на областта на паметта за новия обект и след това (функция чрез точката ()) за определяне на всеки две от нейните елементи стойности случайни данни, вариращи от 0 до 1.
Този стил на програмиране, който понякога се нарича обектно-ориентираното програмиране, напълно подкрепена дизайнерски език клас C ++. Класът може да се счита за продължаване на понятието за структура, която не само обединява данните, но също така се определят операциите на тези данни. Не може да има много и различни предмети, принадлежащи към един и същи клас, но всички те са сходни с това, че членовете на техните данни могат да вземат един и същ набор от ценности, както и тези държави-данни, които може да работи със същия набор от операции - като цяло преписи от същия тип данни. В обектно-ориентираното програмиране, обектите са предназначени да се справят с нейните членове данни (за разлика от помощта на независими функции за обработка на данните, съхранявани в обекти).
Ние считаме, че по примера на малък клас описано по-горе, само за да се запознаят с основните функции на класовете; така че това е далеч от приключване. Действителният код за точката на клас ще имаме много повече операции. Така например, в програмата няма дори 4,1 експлоатация. позволява обучение стойности х и у координати. Както ще видим, добавянето на тези и други операции - доста проста задача. В част 5, ние погледнем по-отблизо в класовете за точки и други геометрични абстракции, например, линии и полигони.
В C ++ (но не и в) имат структури могат също да бъдат свързани функции. Основната разлика между класовете и структури, свързани с достъпа до информация, която се характеризира с ключовата дума частни и публични. За частни (лични) член на класа могат да бъдат достъпни само в рамките на класа, и на обществеността (обществени) на класа могат да бъдат достъпни от всеки клиент. Частни членове могат да бъдат както на данни и функции на програмата са само 4.1 лични данни, но ние продължаваме да виждаме много примери за упражнения, които също са частни член функции. По подразбиране, членовете на групата са частни и членове на структури - на разположение на обществеността.
Например, програмата клиент, който използва клас ТОЧКА. Вие не може да се отнася за членовете на данни p.x, p.y т.н. как може да се направи ТОЧКА структура. като членове на клас х и у са частни. За обработка на точките може да отнеме само се възползват от публично достъпни член функции. Тези функции имат пряк достъп до членовете на данни на обект от този клас. Например, обаждания p.distance (р) разстояние функция от името на програмата х 4.1 оператора DX = х - брадва отнася до х-елемент от точка Р (тъй като функцията на разстояние е извикана като функция -Member например п) и ос име се отнася до х-елемент от точка Q на (защото р -. действителното параметър, който съответства формален параметър). Може да бъде написана DX = това-> х-a.x за да се изключи възможността за неяснота или объркване - тази ключова дума е указател към обекта. за които функцията се нарича -Member.
Когато от данни на членовете на използвани статични ключова дума. Това, както в случая на обикновени членове, означава, че има само едно копие на тази променлива (отнасящи се към клас), а не на няколко копия (свързани с отделни обекти). Тази функция често се използва, например, за да следите статистиката на обектите: можете да включите в ТОЧКА клас променлива статично вътр N. Добавяне N ++ конструктор - и след това ще бъде възможно да се знае броя на точките, създали.
Разбира се, можем да предположим, че функция. изчисляване на разстоянието между две точки, които не трябва да имат аргумент (всеки две точки), и, както в предишния изпълнение, два параметъра (две точки), която е по-естествено. В C ++, този подход може да се осъществява чрез определяне на клас ТОЧКА определението друга разстояние функция:
-Member статична функция може да получите достъп до членовете на класа, но не трябва да се ползва за конкретен обект.
Свързани статии