Разработването на абстрактни модели за данни и как да се обработват тези данни е критичен компонент в процеса на решаване на проблеми с компютър. Виждаме примери за това както на ниско ниво в ежедневното програмиране (например при използване на масиви и свързани списъци, обсъдени в), така и на високо ниво при решаване на приложни проблеми (както при решаване на проблем със свързаността с помощта на гора за търсене на съюзи в "Въведение") ... Тази лекция обсъжда абстрактни типове данни (наричани по-долу ADT), които ви позволяват да създавате програми, използвайки абстракции от високо ниво. Абстрактните типове данни ви позволяват да отделите абстрактните (концептуални) трансформации, които програмите извършват върху данни от всяко конкретно представяне на структура от данни или всяка конкретна реализация на алгоритъм.
Всички изчислителни системи се основават на нива на абстракция: определени физически свойства на силиция и други материали позволяват да се приеме абстрактен модел на бит, който може да приема двоични стойности 0-1; след това се изгражда абстрактен модел на машината върху динамичните свойства на стойностите на определен набор от битове; освен това, на базата на принципа на действие на машина под управлението на програма на машинен език, се конструира абстрактен модел на език за програмиране; и накрая се изгражда абстрактна концепция за алгоритъм, която се реализира като програма на езика C ++. Абстрактните типове данни позволяват да се продължи този процес по-нататък и да се разработят абстрактни механизми за определени изчислителни проблеми на по-високо ниво от това, предоставено от системата C ++, да се разработят абстрактни механизми, ориентирани към специфични приложения и подходящи за решаване на проблеми в множество области на приложение, както и създаване на абстрактни механизми на по-високо ниво, които използват тези основни конструкции. Абстрактните типове данни ни предоставят безкрайно разширяем набор от инструменти за решаване на все повече и повече нови проблеми.
От една страна, използването на абстрактни конструкции ви освобождава от притесненията относно тяхното детайлно изпълнение; от друга страна кога производителностпрограмата е важна, трябва да знаете разходите за извършване на основни операции. Използваме много вградени основни абстракции хардуеркомпютър и служещ като основа за машинни инструкции; внедряваме други абстракции в софтуера; и използвайте допълнителни абстракции, предоставени от предварително написан системен софтуер. Абстрактните дизайни на високо ниво често се основават на по-прости дизайни. На всички нива действа един и същ основен принцип: необходимо е да се намерят най-важните операции в програмите и най-важните характеристики на данните и след това да се дефинират точно както на абстрактно ниво, така и да се разработят ефективни конкретни механизми за тяхното изпълнение. В тази лекция ще разгледаме много примери за прилагане на този принцип.
За да разработите ново ниво на абстракция, ще трябва да (1) дефинирате абстрактните обекти, които трябва да бъдат манипулирани, и операциите, които трябва да бъдат извършени върху тях; (2) представят данни в някои структури от данни и изпълняват операции; (3) и (най-важното) да се гарантира, че тези обекти са удобни за използване за решаване на приложни проблеми. Тези точки се отнасят и за прости типове данни, така че основните механизми за поддържане на типове данни, които бяха обсъдени в елементарни структури от данни, могат да бъдат адаптирани за нашите цели. Въпреки това, езикът C ++ предлага важно разширение на структурния механизъм, наречен клас. Класовете са изключително полезни за създаване на нива на абстракция и следователно се считат за основен инструмент, използван за тази цел в останалата част от тази книга.
Определение 4.1.Абстрактният тип данни (ADT) е тип данни (набор от стойности и набор от операции за тези стойности), до който се осъществява достъп само през интерфейс. Програма, която използва ADT, ще се нарича клиент, а програма, съдържаща спецификация на този тип данни, се нарича реализация.
Това е думата, която само прави типа данни абстрактен: в случай на ADT клиентските програми нямат достъп до стойностите на данните по никакъв друг начин, с изключение на операциите, описани в интерфейса. Представянето на тези данни и функциите, които изпълняват тези операции, са в изпълнение и са напълно отделени от интерфейса от клиента. Казваме, че интерфейсът е непрозрачен: клиентът не може да види реализацията през интерфейса.
В програмите на C ++ това разграничение обикновено се прави малко по-ясно, тъй като най-лесният начин да създадете интерфейс е да включите представяне на даннино уточняване, че клиентските програми нямат директен достъп до данните. С други думи, разработчиците на клиентски софтуер може да знаят представяне на даннино не мога да го използвам по никакъв начин.
Като пример, разгледайте интерфейса за тип данни за точки (програма 3.3) от раздел 3.1 "Елементарни структури от данни". Този интерфейс изрично декларира, че точките са представени като структури, състоящи се от двойка числа с плаваща запетая, обозначени x и y. Тази употреба на типове данни е често срещана в големите софтуерни системи: ние разработваме набор от конвенции за представяне на данни (и също така дефинираме редица свързани операции) и правим тези правила достъпни чрез интерфейс, така че да могат да се използват от клиентски програми които са част от голяма система. Типът данни гарантира, че всички части на системата са съвместими с представянето на основните структури от данни за цялата система. Колкото и добра да е тази стратегия, тя има един недостатък: ако трябва да се промените представяне на данни, тогава всички клиентски програми ще трябва да бъдат променени. Програма 3.3 отново ни дава прост пример: една от причините за разработването на този тип данни е удобството на клиентските програми с точки и ние очакваме клиентите да имат достъп до индивидуални координати на точки, когато е необходимо. Но не можем да преминем към различно представяне на данни (да речем полярни координати, или 3D координати, или дори различни типове данни за отделни координати), без да променим всички клиентски програми.
Обратно, Програма 4.1 съдържа реализация на абстрактен тип данни, съответстващ на типа данни на Програма 3.3, но използващ клас C ++, който незабавно дефинира както данните, така и свързаните с тях операции. Програма 4.2 е клиентска програма, която работи с този тип данни. Тези две програми извършват същите изчисления като програми 3.3 и 3.8. Те илюстрират някои от основните свойства на класовете, които сега ще разгледаме.
Когато пишем дефиниция като int i в програма, ние казваме на системата да резервира област от памет за (вградени) int данни, до които може да се получи достъп с името i. В езика C ++ има терминът обект за такива обекти. Когато пишете дефиниция като POINT p в програма, се казва, че създавате обект от клас POINT, до който може да се стигне с името p. В нашия пример всеки обект съдържа два елемента от данни, наречени x и y. Както при структурите, те могат да бъдат посочени с имена като p.y.
Членовете на данните x и y се наричат членове на данни на класа. Класът може също да дефинира функции-членове, които изпълняват операциите, свързани с този тип данни. Например, класът, дефиниран в Програма 4.1, има две функции-членове с име POINT и distance.
Клиентските програми, като Програма 4.2, могат да извикват функции-членове, свързани с обект, посочвайки имената им по същия начин като имената на данни, намерени в някаква структура. Например изразът p.distance (q) изчислява разстоянието между точките p и q (същото разстояние трябва да бъде върнато чрез извикване на q.distance (p)). Функцията POINT (), първата в Програма 4.1, е специална функция-член, наречена конструктор: тя има същото име като клас и се извиква, когато трябва да бъде създаден обект от този клас.
Програма 4.1. Реализация на клас POINT (точка)
Този клас дефинира тип данни, който се състои от набор от стойности, които са "двойки с плаваща запетая" (ако приемем, че се интерпретират като точки в декартовата равнина) и две функции-членове, дефинирани за всички екземпляри на класа POINT: функция POINT (), който е конструктор, който инициализира координатите до произволни стойности от 0 до 1, и функция за разстояние (POINT), която изчислява разстоянието до друга точка. Представяне на данние частен и само функциите-членове могат да имат достъп или да го променят. Самите функции на членовете са публични и достъпни за всеки клиент. Кодът може да бъде записан например във файл с име POINT .cxx.
#включи
Програма 4.2. Клиентска програма за клас POINT (намиране на най-близката точка)
Тази версия на програма 3.8 е клиент, който използва POINT ADT, дефиниран в програма 4.3. Операторът new създава масив от POINT обекти (чрез извикване на конструктора POINT(), за да инициализира всеки обект със произволни координати). Изразът a [i] .distance (a [j]) извиква на обект a [i] функцията за член на разстояние с аргумент a [j].
#включи
Дефинирането на POINT p в клиентската програма води до разпределяне на област с памет за нов обект и след това (с помощта на функцията POINT ()) за присвояване на всеки от двата му елемента от данни произволна стойност в диапазона от 0 до 1.
Този стил на програмиране, понякога наричан обектно-ориентирано програмиране, се поддържа напълно от конструкцията на класа C ++. Един клас може да се счита за разширение на концепцията за структура, където не само се комбинират данни, но и се дефинират операции с тези данни. Може да има много различни обекти, принадлежащи към един и същ клас, но всички те са сходни по това, че техните членове на данни могат да приемат един и същ набор от стойности и един и същ набор от операции могат да бъдат извършени върху тези членове на данните - като цяло те са екземпляри от същия тип данни. В обектно-ориентираното програмиране обектите са проектирани да обработват своите данни за членове (за разлика от използването на независими функции за обработка на данните, съхранявани в обекти).
Разглеждаме примера за малък клас, описан по-горе, само за да се запознаем с основните характеристики на класовете; следователно далеч не е завършен. В реалния код за точковия клас ще имаме много повече операции. Например, Програма 4.1 дори няма операции, които ви позволяват да разберете стойностите на координатите x и y. Както ще видим, добавянето на тези и други операции е доста проста задача. В част 5 ще разгледаме по-отблизо класовете за точкови и други геометрични абстракции като линии и многоъгълници.
В C ++ (но не и C) структурите също могат да имат функции, свързани с тях. Ключовата разлика между класовете и структурите е свързана с достъпа до информация, който се характеризира с ключови думи.
Добър ден, жители на Хабрав!
Следващата публикация е обобщение на моите мисли за естеството на класовете и ADT. Тези разсъждения са допълнени от интересни цитати от книги на гурута по разработка на софтуер.
Въведение
Нека започнем с плавно приближаване към определението на ADT. ADT е предимно тип данни, което означава следното: наличието на определени налични операции върху елементи от този тип;
както и данните, върху които се извършват тези операции (диапазон от стойности).
Какво означава думата „абстрактно“? На първо място, понятието "абстрактност" означава да се фокусираме върху нещо важно и в същото време трябва да се отклоним от маловажни в момента детайли. Определението за абстрактност е добре обхванато в книгата на Грейди Буч. Определението звучи така:
Абстракцията е подборът и придаването на набор от обекти с общи свойства, които определят техните концептуални граници и ги отличават от всички други видове обекти.
С други думи, абстракцията ни позволява да „хвърлим светлина“ върху данните за обектите, от които се нуждаем, и в същото време да „засенчим“ тези данни, които не са важни за нас.
И така, какво ще стане, ако обедините понятията „тип данни“ и „абстракция“ заедно? Ще получим тип данни, който ни предоставя набор от операции, които осигуряват поведението на обекти от този тип данни, а този тип данни също ще скрие данните, с които това поведение е реализирано. Следователно стигаме до концепцията за ADT:
ADT е тип данни, който скрива вътрешната си реализация от клиенти.
Изненадващо, използвайки абстракция, ADT ни позволява да не мислим за детайлите на внедряването на ниско ниво, а да работим със същността на реалния свят от високо ниво (Стив Макконъл).
Вярвам, че когато разработвате ADT, първо трябва да дефинирате интерфейс, тъй като интерфейсът не трябва да зависи от вътрешното представяне на данните в ADT. След като дефинирате операциите, които съставляват интерфейса, трябва да се съсредоточите върху данните, които ще реализират определеното поведение на ADT. В резултат на това ще получим някаква структура от данни - механизъм, който ви позволява да съхранявате и обработвате данни. В същото време красотата на ADT е, че ако искаме да променим вътрешното представяне на данните, тогава не е нужно да се лутаме из цялата програма и да променяме всеки ред код, който зависи от данните, които искаме да промяна. ADT капсулира тези данни, което ви позволява да промените поведението на обекти от този тип, а не на цялата програма.
Предимства на ATD
Използването на ADT има много предимства (всички описани предимства могат да бъдат намерени в книгата на Steve McConnell "Code Perfect"):
- Капсулиране на детайли за изпълнение.
Това означава, че след като капсулираме подробностите за това как работи ADT, ние предоставяме на клиента интерфейс, чрез който той може да взаимодейства с ADT. Чрез промяна на детайлите за внедряване възприятието на клиента за ADT няма да се промени.
- Намалена сложност.
Като се абстрахираме от подробностите за внедряването, ние се фокусираме върху интерфейса, което може да направи ADT, а не как се прави. Освен това ADT ни позволява да работим със същността на реалния свят.
- Ограничаване на обхвата на използване на данни.
Използвайки ADT, можем да сме сигурни, че данните, представляващи вътрешната структура на ADT, няма да зависят от други части на кода. В същото време се реализира „независимостта“ на ADT.
- Високо информационно съдържание на интерфейса.
ADT ви позволява да представите целия интерфейс по отношение на обекти на домейна, което, както виждате, увеличава четливостта и информационното съдържание на интерфейса.
Стив Макконъл препоръчва да се представят типове данни от ниско ниво, като стек или списък като ADT. Запитайте се какъв е списъкът. Ако той представя списък на банковите служители, тогава разглеждайте ATD като списък на банковите служители.
И така, разбрахме какво е ADT и назовахме предимствата на неговото използване. Сега си струва да се отбележи, че когато разработвате класове в OOP, трябва да мислите преди всичко за ADT. В същото време, както каза Стив Макконъл, вие програмирате не на езика, а с помощта на езика. Това означава, че ще програмирате извън езика, без да се ограничавате до мисли по отношение на масиви или прости типове данни. Вместо това ще мислите на високо ниво на абстракция (например по отношение на електронни таблици или списъци на служители). Класът не е нищо повече от допълнение и начин за реализиране на ADT концепцията. Можем дори да представим класа като формула:
Клас = ADT + Наследство + Полиморфизъм.
Така че защо човек трябва да мисли за ADT, когато проектира класове. Защото първо трябва да решим кои операции ще представляват интерфейса на бъдещия клас, кои данни да скрием и до кои да предоставим публичен достъп. Трябва да помислим как да направим интерфейса много информативен, лесен за оптимизиране и валидиране на кода и как можем да предоставим правилната абстракция, така че да можем да мислим за обекти от реалния свят, а не за подробности за внедряване на ниско ниво. Вярвам, че след дефиницията на ADT трябва да се замислим за въпросите на наследяването и полиморфизма.
Струва си да се отбележи, че концепцията за ADT намери широко приложение в OOP, тъй като именно тази концепция допълва OOP и ви позволява да намалите сложността на програмите в бързо променящия се свят на софтуерните изисквания.
Написах тази статия, за да привлека вниманието на разработчиците към ADT с цел подобряване на качеството на работа и разработка на софтуер.
Използвани източници:
Стив Макконъл - Code Perfect;
Робърт Седжуик - "Алгоритми в Java".
Обичайно е да се нарича абстрактен тип тип данни, който не е изрично наличен в език за програмиране; в този смисъл това понятие е относително - тип данни, който липсва в един език за програмиране, може да присъства в друг.
Абстрактен тип данни (ADT) се определя независимо от това как се прилага:
набор от възможни стойности от този тип,
и набор от операции върху стойности от този тип.
Използването на ADT може да бъде ограничено до етапа на разработка на софтуер, но за изричното му използване в програмата, трябва да имате неговата реализация въз основа на вече съществуващите (и по-рано внедрени) типове данни в езика за програмиране:
начин за представяне на стойности от този тип,
и изпълнението на операции върху стойности от този тип.
ADT не е предварително дефиниран в езика за програмиране и дори повече от това, операциите за конструиране на такива типове, предварително дефинирани в езика, изместват въпроса как да се представят стойности от този тип и как да се реализират операции със стойности на този тип на програмист-програмист. Следователно, за такива типове данни, въпросът за избора на дефиниции и методи за изпълнение на операции от формата конструктор (стойности и хранилища на данни) от този тип, селектор и модификатор Компоненти (стойности и хранилища на данни) от този тип са отговорност на разработчика-програмист.
В концепцията за ADT следните понятия имат специален статут: интерфейс отворен за потребителя и реализация скрит от него. Специалната роля на тези понятия в концепцията за ADT е свързана с основната разпоредба за независимостта на концепцията за ADT от метода на нейното прилагане.
В съвременните „практични езици за програмиране“ обикновено се използва операцията за конструиране с предварително дефиниран тип за конструиране на ADT клас , което дава на програмиста-програмист не само средствата за групиране на данни и операции (с тези данни) в едно цяло, но и средствата за капсулиране, наследяване и полиморфизъм за контрол на начина на конструиране и достъп до такива данни. Обърнете внимание, че един клас описва една възможна реализация на ADT, съпоставянето на клас в ADT се изразява чрез абстракционна функция, но обратната връзка обикновено не е функционална, може да има няколко реализации на един и същ ADT.
В изследванията върху абстрактните типове данни важната роля на понятието „ параметризация на типа ". Всъщност, например, ADT "Stack" не зависи от типа на елементите на стека, но е невъзможно да се приложи този ADT чрез посочване на "елементи от същия тип". В езика за програмиране Ada първоначално са включени съответните средства за конструиране на параметризирани типове данни, а в съвременните „практични езици за програмиране“, които инструменти се появяват едва след появата на развитието на библиотеката STL. Днес концепцията за "генерично програмиране" заема значителна позиция в практическото програмиране поради включването в "практичните езици за програмиране" средства за конструиране на параметризирани типове данни (шаблони, шаблон , общ) .
Всичко казано по-горе означава, че от методологическа и теоретична гледна точка е необходимо по-подробно и точно определение на понятието „абстрактен тип данни“. На теория понятието "абстрактен тип данни" обикновено се дефинира като многосортирана (многобазова) алгебрична система , в който, в допълнение към набора от възможни стойности (носител) и набор от операции върху такива стойности, са подчертани следните понятия:
Сортиране и подпис - тези понятия ви позволяват да класифицирате както медийните елементи, така и операциите с тях по техните типове (за операции, по типовете на техните аргументи и върнатата стойност).
Предикатите са отношения върху елементите на носителя. Това дава възможност да се определи диапазонът от възможни стойности чрез налагане на ограничения (изисквания) върху допустимите стойности, както и да се работи в естествена интерпретация с произволни логически изрази, без да се принуждават да се интерпретират като функции за членство за множества или като многозначни операции.
На тази основа е възможно да се разглеждат абстрактни типове данни от единна интегрална логико-алгебрична гледна точка, включително въпроси за конструктори (типове и стойности), селектори и модификатори на свойства за обекти от този тип.
Понятията "структура на данните" и "абстрактен тип данни" са донякъде сходни. Можете, разбира се, да считате, че тези понятия са само две възгледи за едно и също нещо. Начинът на представяне на ADT стойностите винаги се основава на някаква структура от данни, по-малко или по-сложна, и изпълнението на операции с такива стойности естествено зависи от тази избрана структура от данни. От друга страна, ако искаме, винаги можем да проектираме структурата от данни, която ни интересува като ADT.
Но все пак ще правим разлика между тези две понятия, като се има предвид:
Абстрактният тип данни предполага определено ниво на абстракция с цел фиксиране на приложен (специфичен за домейн) тип данни, независимо от начина, по който е внедрен, и е възможно този тип данни да се включи в библиотека на приложения, добре, поне за специфична разработка на конкретна софтуерна система. ADT може да има няколко алтернативни реализации, базирани на различни структури от данни.
Структурата на данните е по-скоро някаква схема на организация и управление на данните, която предполага подходяща конкретизация, когато се използва в конкретни ситуации при решаване на конкретни проблеми.
На първо място, математическите основни алгебрични системи - последователности, множества, отношения и отображения (функционални отношения, функции) - естествено принадлежат към абстрактни типове данни. Но в програмирането на преден план не е изучаването на общите свойства на тези математически понятия, а възможностите за тяхното използване при разработването на модели за решаване на проблеми от предметната област, алгоритми за решаване на тези проблеми и ефективното изпълнение на разработените алгоритми. Следователно, при програмирането под формата на ADT, от една страна, се формират ограничени версии на тези основни алгебрични системи, а от друга страна, те се разширяват със специализирани набори от операции, които представляват прагматичен интерес от гледна точка от областта на приложение.
1.2. Абстрактни типове данни
Повечето от понятията, въведени в предишния раздел, обикновено се въвеждат в курса по програмиране за начинаещи и трябва да са ви познати. Само абстрактни типове данни могат да бъдат нови, така че нека първо да обсъдим тяхната роля в процеса на разработка на програмата. Първо, нека сравним абстрактен тип данни с такова познато понятие като процедура.
Процедурата, интегрален инструмент за програмиране, може да се разглежда като обща концепция за оператор. За разлика от вградените оператори на езика за програмиране (събиране, умножение и т.н.), които са ограничени в своите възможности, програмистът може да използва процедури за създаване на свои собствени оператори и да ги прилага към операнди от различен тип, а не само основни. Пример за такава операторна процедура е стандартната рутина за умножение на матрици.
Друго предимство на процедурите (освен възможността за създаване на нови оператори) е възможността да се използват за капсулиранечасти от алгоритъма, като постави в отделен раздел на програмата всички оператори, отговорни за определен аспект от функционирането на програмата. Пример за капсулиране: използване на една процедура за четене на входни данни от всякакъв тип и проверка на тяхната коректност. Предимството на капсулирането е, че знаем кои капсулирани изрази трябва да бъдат променени в случай на проблеми във функционирането на програмата. Например, ако е необходимо да се организира проверката на входните данни за положителни стойности, трябва да се променят само няколко реда код и ние знаем точно къде се намират тези редове.
Дефиниция на абстрактен тип данни
Ние определяме абстрактен тип данни(ADT) като математически модел с набор от оператори, дефинирани в този модел. Прост пример за ADT е набор от цели числа с оператори на обединение, пресичане и разлика на множества. В модела ADT операторите могат да имат като операнди не само данни, дефинирани от ADT, но и данни от друг тип: стандартни типове на езика за програмиране или дефинирани в други ADT. Резултатът от действието на оператора може също да бъде от различен тип от дефинираните в този модел ADT. Но приемаме, че поне един операнд или резултат от който и да е оператор има типа данни, дефиниран в разглеждания ADT модел.
Двете характерни характеристики на процедурите - обобщение и капсулиране - обсъдени по-горе, са отлични за абстрактни типове данни. ADT може да се разглежда като обобщение на прости типове данни (цели числа, реални числа и т.н.), точно както процедурата е обобщение на прости оператори (+, - и т.н.). ADT капсулира типове данни в смисъл, че дефиницията на тип и всички изрази, изпълнявани върху данни от този тип, се поставят в един раздел на програмата. Ако е необходимо да се промени реализацията на ADT, ние знаем къде да намерим и какво да променим в една малка част от програмата и можем да сме сигурни, че това няма да доведе до грешки никъде в програмата при работа с този тип данни. Освен това, извън раздела за дефиницията на ADT оператори, можем да разглеждаме типовете ADT като първични типове, тъй като декларацията на типове не е формално свързана с тяхното изпълнение. Но в този случай могат да възникнат трудности, тъй като някои оператори могат да бъдат инициирани за повече от един ADT и препратките към тези оператори трябва да са в секции от няколко ADT.
За да илюстрирате основните идеи зад създаването на ADT, разгледайте алчната рутина от предишния раздел (листинг 1.3), която използва прости оператори на абстрактния тип данни LIST (списък с цели числа). Тези оператори трябва да извършат следните действия върху променливата newclr от тип LIST.
1. Направете списъка празен.
2. Изберете първия елемент от списъка и, ако списъкът е празен, върнете стойността нула.
3. Изберете следващия елемент от списъка и върнете стойността нула,ако няма следващ елемент.
4. Вмъкнете цяло число в списъка.
Възможно е да използвате различни структури от данни, с които можете ефективно да извършвате описаните действия. (Структурите от данни ще бъдат разгледани подробно в тема 2.) Ако в листинг 1.3 замените съответните оператори с изрази
MAKENULL (newcJr);
w: = ПЪРВО (newcJr);
w: = СЛЕДВАЩ (newcfr);
INSERT (v, newclr);
тогава ще бъде разбран един от основните аспекти (и предимства) на абстрактните типове данни. Можете да внедрите тип данни по всякакъв начин и програмите, които използват обекти от този тип, не зависят от това как е внедрен типът - за това отговарят процедурите, които имплементират оператори за този тип данни.
Да се върнем към абстрактния тип данни GRAPH (Graph). Обектите от този тип изискват оператори, които извършват следните действия.
1. Избира се първият неоцветен връх.
2. Проверете дали има ръб между двата върха.
3. Маркирайте върха с цвят.
4. Изберете следващия неоцветен връх.
Очевидно другите оператори остават извън полезрението на алчната процедура, като например вмъкване на върхове и ръбове в графиката или маркиране на всички върхове на графиката като отворени. Различните структури от данни, които поддържат този тип данни, ще бъдат разгледани в теми 6 и 7.
Трябва да се подчертае, че броят на операторите, приложени към обектите на този математически модел, не е ограничен. Всеки набор от оператори дефинира отделен ADT. Ето примери за оператори, които можете да дефинирате за абстрактния тип данни SET (Set).
1. MAKENULL (A), Тази процедура прави множеството A празно.
2. СЪЮЗ (А, Б, В). Тази процедура има два "входни" аргумента, набори A и B, и присвоява обединението на тези набори на "изходния" аргумент, набор C.
3. РАЗМЕР (A). Тази функция има аргумент за набор A и връща обект от целочислен тип, равен на броя на елементите от множество A. Терминът ADT реализация предполага следното: превод на декларации, дефиниращи променливи от този абстрактен тип данни в оператори на езика за програмиране, плюс процедури за всеки оператор, изпълняван върху ADT обекти. Изпълнението зависи от структури от данни,представляващ ADT. Всяка структура от данни е изградена на базата на основните типове данни на езика за програмиране, използван с помощта на наличните на този език инструменти за структуриране на данни. Структурите на масиви и записи са два важни инструмента за структуриране на данни, налични в Pascal. Например, една от възможните реализации на променлива S от тип SET може да бъде масив, съдържащ елементи от набора С.
Една от основните причини за дефинирането на две различни ADT в рамките на един и същ модел е, че върху обектите на тези ADT трябва да се извършват различни действия, т.е. дефинирайте оператори от различни типове. В този синопсис са разгледани само няколко основни математически модела, като теория на множествата и теория на графите, но за различни реализации ще бъдат изградени различни набори от оператори въз основа на тези модели на определени ADT.
В идеалния случай е желателно да се пишат програми на език, чиито основни типове данни и оператори са достатъчни за реализиране на ADT. От тази гледна точка езикът Pascal не е много подходящ език за внедряване на различни ADT, но, от друга страна, е трудно да се намери друг език за програмиране, в който да е възможно директно да се декларират ADT. За повече информация относно такива езици за програмиране вижте библиографските бележки в края на темата.
Министерство на образованието и науката на Руската федерация
Федерална държавна бюджетна образователна институция
висше професионално образование
НАЦИОНАЛЕН ИЗСЛЕДОВАТЕЛСКИ ЯДРЕН УНИВЕРСИТЕТ "МЕФИ"
Димитровград Инженерно технологичен институт
отдел Информационни технологии
Да се признае за защита "" 2012 г
Глава Председател Ракова О.А.
Курсова работа
по дисциплина"Обектно-ориентирано програмиране"
тема:„Абстрактни типове данни. списъци "
Завършен: ученик гр. VT-31
Шаяков А.Ф.
Водещ: чл. преподавател в катедра ИТ
Аленин В.А.
Норм контролер: чл. преподавател в катедра ИТ
Аленин В.А.
степен:
Дата на защита:
Димитровград, 2012г
Министерство на образованието и науката на Руската федерация
Федерална държавна бюджетна образователна институция
висше професионално образование
НАЦИОНАЛЕН ИЗСЛЕДОВАТЕЛСКИ ЯДРЕЕН УНИВЕРСИТЕТ "МЕФИ"
Димитровград Инженерно технологичен институт
за курсова работа
Дисциплина: Обектно-ориентирано програмиране
Тема: Абстрактни типове данни. Списъци
Художник: Шаяков А.Ф.
Ръководител: В. А. Аленин
1. Теоретична част:
Абстрактни типове данни. Концепция за обектно-ориентирано програмиране. Линейни едносвързани списъци.
2.Практическа част:
В C ++ напишете програма с обектно-ориентирана структура за реализиране на линейни едносвързани списъци.
Условия за изпълнение на работата по график:
Теоретична част - 15% до 5-та седмица
Практическа част - 80% до седмица 7
Експериментална секция - ____% до ____ седмица
Защита - 100% до седмица 10
Изисквания за регистрация:
Разчетът и обяснителната бележка на курсовата работа трябва да се представят на електронен и хартиен носител;
Обемът на доклада трябва да бъде най-малко 20 машинописни страници без прикачени файлове
РПЗ се подписва от лицето, отговорно за регулаторния контрол
Работен ръководител ________________
Изпълнител ________________________
Дата на издаване "_____" ___________ 2012г
А.Ф. ШАЯКОВ ТЕМА: АБСТРАКТНИ ВИДОВЕ ДАННИ. СПИСЪКИ, Курсова работа / DITI, No 230105.65-Димитровград, 2012. - 29 стр., фиг. 11, библ. име 10, приложение 1.
Ключови думи: линейни едносвързани списъци, C++, обектно-ориентирано програмиране.
Обект на изследване са линейни едносвързани списъци.
Целта на работата е да се изучат линейни едносвързани списъци и да се напише програма на C ++ с обектно-ориентирана структура за тяхното изпълнение.
Изводи: в тази работа сме проучили напълно линейните едносвързани списъци, както и методите за тяхното представяне в паметта. Програмата, написана на езика C ++, напълно отговаря на обектно-ориентираната структура, правилно и ефективно изпълнява основната си задача - изпълнява линейни едносвързани списъци.
Въведение 6
1 Теоретична част 7
1.1 Абстрактни типове данни. Линейни списъци 7
1.2 Концепция за обектно-ориентирано програмиране 8
2 Практическа част 15
3 Тестване 23
Заключение 25
Литература 26
Приложение А 27
Въведение
Често в процеса на работа с данни е невъзможно да се определи колко памет е необходима за съхраняването им; паметта трябва да се разпределя по време на изпълнението на програмата според нуждите в отделни блокове. Блоковете са свързани един с друг с помощта на указатели. Този начин на организиране на данни се нарича динамична структура от данни, тъй като се намира в купчина и преоразмерява по време на изпълнение на програмата.
В тази работа се използват линейни списъци от динамични структури. Динамичната структура, за разлика от масива или записа, може да заема несвързани области на RAM.
Динамичните структури също се използват широко за по-ефективна работа с данни, чийто размер е известен, особено за решаване на проблеми със сортиране.
Елемент от всяка динамична структура се състои от две части: информационна, за чието съхранение е създадена структурата, и указатели, които осигуряват връзката на елементите един с друг.
Теоретична част
1.1 Абстрактни типове данни. Линейни списъци
Абстрактните типове данни са ключови понятия в програмирането. Абстракцията предполага разделяне и независимо разглеждане на интерфейса и реализацията.
Абстракцията на данни включва дефинирането и разглеждането на абстрактни типове данни (ADT) или, което е същото, нови типове данни, въведени от потребителя.
Абстрактният тип данни е колекция от данни заедно с много операции, които могат да бъдат извършени върху тези данни.
Линейни списъци
В линеен списък всеки елемент е свързан със следващия и евентуално предишния. В първия случай списъкът се нарича просто свързан, във втория - двойно свързан. Ако последният елемент е свързан с указател към първия, резултатът е кръгъл списък.
Всеки елемент в списъка съдържа ключ, който идентифицира този елемент. Ключът обикновено е цяло число или низ и е част от полето за данни. Различни части от полето с данни могат да действат като ключ в процеса на работа със списъка. Ключовете на различните елементи от списъка могат да бъдат еднакви.
Можете да извършвате следните операции върху списъци:
първоначално формиране на списъка (създаване на първия елемент);
добавяне на елемент в края на списъка;
четене на елемент с даден ключ;
вмъкване на елемент на дадено място в списъка (преди или след елемент с даден ключ);
изтриване на елемент с даден ключ;
подреждане на списъка по ключ.
За да работите със списък в програма, трябва да дефинирате указател към неговото начало. Можете също да задържите курсора на мишката в края на списъка, за да улесните добавянето на нови елементи в края на списъка.
1.2 Концепция за обектно-ориентирано програмиране
Според Грейди Буч, авторитет по методите за обектно-ориентирано програмиране, „обектно ориентираното програмиране (ООП) е методология за програмиране, която се основава на представяне на програма като колекция от обекти, всеки от които е реализация на определен клас ( тип специален вид), а класовете образуват йерархия, основана на принципите на наследяване.
Обектно-ориентираната методология, подобно на структурната методология, е създадена с цел да се дисциплинира процеса на разработване на големи софтуерни пакети и по този начин да се намали тяхната сложност и цена.
Обектно-ориентираната методология преследва същите цели като структурираната методология, но ги разглежда от различна отправна точка и в повечето случаи ви позволява да управлявате по-сложни проекти от структурираната методология.
Както знаете, един от принципите за управление на сложността на проекта е разлагането. Грейди Буч разграничава два вида декомпозиция: алгоритмична (както той нарича декомпозиция, поддържана от структурни методи) и обектно-ориентирана, разликата между които според него е следната: специално значение за факторите, или причиняващи действия, или са обекти на прилагането на тези действия”.
С други думи, алгоритмичната декомпозиция взема предвид повече структурата на връзките между части от сложен проблем, докато обектно-ориентираната декомпозиция се фокусира повече върху естеството на връзките.
На практика се препоръчва да се използват и двата вида декомпозиция: при създаване на големи проекти е препоръчително първо да се приложи обектно-ориентиран подход, за да се създаде обща йерархия от обекти, които отразяват същността на програмираната задача, и след това да се използва алгоритмична декомпозиция в модули за опростяване на разработването и поддръжката на софтуерния пакет.
OO програмирането несъмнено е една от най-интересните области за професионална разработка на софтуер.
Обекти и класове
Основните градивни елементи на обектно-ориентирана програма са обекти и класове. По същество един обект може да бъде представен като нещо, което се усеща или представя и има добре дефинирано поведение. По този начин даден обект може или да бъде видян или докоснат, или поне да се знае, че той например е представен като информация, съхранявана в паметта на компютъра. Нека да дадем определението на обект, придържайки се към мнението на GradiBuch: „Обектът е осезаем обект, който ясно проявява своето поведение“.
Обектът е част от реалността, която ни заобикаля, тоест съществува във времето и пространството (за първи път понятието обект в програмирането е въведено в езика Simula). Формално обектът е труден за дефиниране. Това може да стане чрез някои свойства, а именно: обектът има състояние, поведение и може да бъде еднозначно идентифициран (с други думи, има уникално име).
Класът е набор от обекти, които споделят обща структура и общо поведение. Класът е описание (абстракция), което показва как да се конструира променлива от този клас, която съществува във времето и пространството, наречена обект. Значението на изреченията "описание на променливите на класа" и "описание на обектите на класа" е едно и също.
Обектът има състояние, поведение и паспорт (средства за уникалната му идентификация); структурата и поведението на обектите са описани в класовете, чиито те са променливи.
Нека сега дефинираме понятията състояние, поведение и идентификация на обект.
Състоянието на обекта комбинира всички негови полета с данни (статичен компонент, т.е. непроменен) и текущите стойности на всяко от тези полета (динамичен компонент, т.е. обикновено променящ се).
Поведението изразява динамиката на промените в състоянията на обекта и неговата реакция на входящи съобщения, т.е. как един обект променя състоянието си и взаимодейства с други обекти.
Идентификацията (разпознаването) на обект е свойство, което ви позволява да различавате обект от други обекти от същия или различни класове. Идентификацията се извършва чрез уникално име (паспорт), което се присвоява на обекта в програмата, както всяка друга променлива.
Вече беше казано по-горе, че процедурният (както и модулният) подход позволява да се изграждат програми, състоящи се от набор от процедури (подпрограми), които изпълняват дадените алгоритми. От друга страна, обектно-ориентираният подход представя програмите като колекция от обекти, които взаимодействат един с друг. Взаимодействието на обектите се осъществява чрез съобщения. Да приемем, че нашият обект е кръг. Тогава съобщението, изпратено до този обект, може да бъде: „нарисувай себе си“. Когато казваме, че съобщение се предава на обект, тогава всъщност ние извикваме някаква функция на този обект (компонентна функция). И така, в горния пример ще извикаме функция, която ще начертае кръг на екрана на дисплея.
Капсулиране
Капсулирането е един от основните принципи на обектно-ориентираното програмиране, чиято идея е, че всички свойства и методи се комбинират в един обект.
Самото име на термина "капсулиране" идва от английската дума encapsulate, която буквално означава "запечатване в капсула" или "покриване с черупка". По този начин един обект (капсула) съдържа методи и свойства (съдържание).
Капсулирането може да се разглежда в по-широк смисъл, далеч отвъд обектно-ориентираното програмиране като цяло. Ако говорим за капсулиране на възможно най-високо ниво на абстракция, тогава капсулирането може да се разглежда като способност на обект да съдържа различни други обекти. Така че по отношение на една компютърна програма можем да кажем, че тя капсулира няколко модула, всеки от които от своя страна капсулира някои обекти, които капсулират методи и свойства, които, между другото, също могат да бъдат обекти и т.н.
Въз основа на всичко по-горе, друго представяне на капсулирането може да бъде всяка структура на дърво, в която всеки възел на дървото капсулира всички негови непосредствени деца, които могат да бъдат или листа (примитиви, които не могат да капсулират нищо в себе си) или други възли.
И все пак, ако говорим за обектно-ориентирано програмиране, тогава капсулирането е обединението на данни и методи в рамките на обект.
Понякога, говорейки за капсулиране в обектно-ориентирано програмиране, концепцията за капсулиране се приравнява с концепцията за "черна кутия" или скриване на данни, но те не са едно и също нещо. Да, в някои обектно-ориентирани езици за програмиране, използвайки капсулиране, разработчикът може да направи своя обект черна кутия, но това се реализира с помощта на модификатори за достъп, които не са налични във всички обектно-ориентирани езици за програмиране. Самата концепция за капсулиране е много по-широка. И дори повече от това, можем да направим всички свойства и методи достъпни отвън, тоест не може да става дума за никаква черна кутия, но капсулирането все пак ще присъства във всеки обект. Следователно скриването на данни чрез модификатори за достъп е следствие от капсулирането, но по никакъв начин не са идентично равни понятия.
Първо, благодарение на капсулирането, обектите вече не са просто потребителски дефинирани структури от данни, чиято основна цел е просто да бъдат логично комбинирани няколко отделни типа данни в рамките на нов съставен тип данни. Благодарение на капсулирането всеки обект вече може да съдържа данни, описващи състоянието на обекта и неговото поведение, описано под формата на методи. С други думи, обектът в обектно-ориентираното програмиране е престанал да бъде примитивен пасивен тип данни, чийто контрол е изцяло на милостта на външната среда, а е започнал да има собствено поведение, дори може да се каже, че има някаква воля и ум, способността да реагират активно на външни влияния и да променят състоянието си и според собствените си закони и разпоредби.
Второ, капсулирането ни дава възможност да контролираме достъпа до обектни данни. Ограничението на видимостта може да се разглежда и като проява на собствената воля на обекта - обектът сам решава какво от своето поведение или свойства да направи достъпно за всички, какво да направи достъпно само за определен кръг от обекти и какво да направи напълно интимно, за което няма да знае друг обект. Защо, а защото само самият обект знае как точно да работи с него и как не. Можете дори да кажете за нова философия на програмирането, където обектите са повече върху обекти, върху които се извършват някои действия, и, ако мога така да кажа, нова форма на абстрактен синтетичен ум, взаимодействайки с който можете да постигнете желания резултат.
И още веднъж повтарям, че благодарение на капсулирането един обект може да бъде надарен с някаква воля, разум, способност да реагира на външни влияния, а не да бъде пасивно хранилище на данни.
Наследство
Наследяването е един от четирите най-важни механизма на обектно-ориентирано програмиране (заедно с капсулиране, полиморфизъм и абстракция), който ви позволява да опишете нов клас въз основа на съществуващ (родителски) клас, докато свойствата и функционалността на родителския клас са заети от новия клас.
С други думи, наследяващият клас реализира спецификацията на вече съществуващ клас (базов клас). Това ви позволява да третирате обекти от наследения клас по същия начин, както и обекти от базовия клас.
Видове наследяване
Просто наследяване
Класът, от който произлиза наследяването, се нарича базов или родител (на английски baseclass). Класовете, които се спускат от основата, се наричат наследници, потомци или производни класове.
Някои езици използват абстрактни класове. Абстрактен клас е клас, който съдържа поне един абстрактен метод, описан е в програмата, има полета, методи и не може да се използва за директно създаване на обект. Тоест можете да наследите само от абстрактен клас. Обектите се създават само на базата на производни класове, наследени от абстрактното.
Например, абстрактен клас може да бъде базов клас "университетски служител", от който се наследяват класовете "аспирант", "професор" и т. н. Тъй като производните класове имат общи полета и функции (например полето "година на раждане"), тези членове на класа могат да бъдат описани в основния клас. Програмата създава обекти на базата на класовете "аспирант", "професор", но няма смисъл да създавате обект на базата на класа "университетски служител".
Множествено наследяване
При множествено наследяване един клас може да има повече от един предшественик. В този случай класът наследява методите на всички предшественици. Предимството на този подход е по-голямата гъвкавост. Множественото наследяване е реализирано в C ++. Други езици, които предоставят тази възможност, включват Python и Eiffel. Множественото наследяване се поддържа в UML.
Множественото наследяване е потенциален източник на грешки, които могат да възникнат поради наличието на същите имена на методи в предците. В езици, които са позиционирани като наследници на C ++ (Java, C # и др.), беше решено да се изостави множественото наследяване в полза на интерфейсите. Почти винаги можете да правите без да използвате този механизъм. Въпреки това, ако все пак възникне такава необходимост, тогава за разрешаване на конфликти при използване на наследени методи със същите имена е възможно например да се приложи операцията за разширяване на видимостта - "::" - за извикване на конкретен метод на конкретен родител.
Направен е опит да се реши проблемът с наличието на същите имена на методи в предците на езика Eiffel, при който при описание на нов клас е необходимо изрично да се посочат импортираните членове на всеки от наследените класове и тяхното именуване в детския клас.
Повечето съвременни обектно-ориентирани езици за програмиране (C#, C++, Java, Delphi и т.н.) поддържат възможността едновременно да наследяват от предшественик клас и да прилагат методи на няколко интерфейса с един и същ клас. Този механизъм ви позволява до голяма степен да замените множеството наследяване - методите на интерфейса трябва да бъдат изрично отменени, което елиминира грешките при наследяване на функционалността на едни и същи методи от различни класове предшественици.
Практическа част
За решаването на този проблем се използва обектно-ориентирана програмна структура. Програмата е представена от два класа и основен cpp-файл, съдържащ потребителски интерфейс за удобство при работа със списъци.
Класът cList е линеен, едносвързан списък с обекти от класа cElement.
Класът cElement има следната структура:
cElement * следващ;
~ cElement (недействителен);
невалиден набор данни (int);
void setref (cElement *);
cElement * getref ();
Полето с данни от типа int съдържа числовата стойност на елемента от списъка, следващото поле от типа cElement * съдържа връзка към следващия елемент в списъка. Методите setdata и getdata се използват за достъп до полето за частни данни на класа, за да се получи и съответно да се зададе стойността на това поле. Методът setref се използва за задаване на връзка от текущия към следващия елемент в списъка, а getref се използва за придвижване до следващия елемент.
void cElement :: setdata (int sd)
int cElement :: getdata ()
върнете това-> данни;
void cElement :: setref (cElement * rf)
cElement * cElement :: getref ()
върнете това-> следващо;
Изпълнението на тези методи е изключително просто, както се вижда от техните програмни кодове, представени по-горе.
Сега нека разгледаме структурата на класа cList
#include "cElement.h"
cElement * глава;
void Добавяне (int);
void Вмъкване (int, int);
void Премахване (int);
void RemoveAll ();
Този клас съдържа връзка към елемента head на списъка - head, от тип cElement *. Съхраняването на тази връзка е необходимо за правилното изпълнение на операциите за добавяне, изтриване на данни и отпечатване на списъка. Факт е, че при извършване на някоя от горните операции елементите на списъка се изброяват, за да се достигне до желания, тъй като списъкът няма произволен достъп до елементите, следователно е по-рационално да започнете изброяването от " глава" на списъка. В допълнение към връзката към началото на списъка, всеки обект от този клас ще има поле elcount, което съдържа броя на елементите в списъка.
Нека продължим нашето изследване на този клас, като разгледаме внедрените в него методи за работа със списъци.
Добавяне на метод - добавяне на данни в края на списъка.
Като параметър този метод приема числова стойност (променлива xd), която трябва да бъде съхранена в добавения елемент от списъка.
void cList :: Добавяне (int xd)
Ето как се създава нов елемент и се задава стойността на неговото числово поле:
cElement * temp = newcElement;
temp-> setdata (xd);
След това се проверява броят на елементите в списъка, ако списъкът е празен, тогава се създава елементът head, в противен случай "обикновеният" компонент на списъка:
ако (elcount == 0)
temp-> setref (NULL);
temp-> setref (NULL);
p-> setref (temp);
Можете да забележите, че горната конструкция използва метода setref на класа cElement, който е необходим за задаване на връзка към следващия елемент в списъка, в противен случай списъкът ще бъде необвързан, което е изпълнено със загуба на данни и неправилна работа на програмата.
При първото стартиране на програмата описаният по-горе метод се използва за последователно добавяне на елементи към списъка, с които след това можете да работите; за да спрете въвеждането в командния ред, трябва да въведете командата "стоп" вместо числовата стойност на артикула (виж фигура 1).
Фигура 1 - Процесът на добавяне на елементи към списъка
След въвеждане на командата "стоп", списъкът се отпечатва и програмата преминава в режим на изчакване на команда (виж Фигура 2).
Фигура 2 - Отпечатан списък
Метод на печат - отпечатва списъка.
За отпечатване е важно да знаете началото на списъка, за да отпечатате последователно стойностите на всички елементи от списъка, така че в променливата temp е зададена връзка към "главата" на списъка, след което фактът за съществуването на списъка се проверява и се показва съответното съобщение, ако не е потвърдено, ако списъкът не е празен, тогава се показва:
void cList :: Печат ()
cElement * temp = глава;
if (temp == NULL) cout while (temp! = NULL)
temp = temp-> getref ();
Del метод - изтриване на началния елемент от списъка.
За да премахнете първоначалния елемент, първо трябва да преместите връзката към следващия компонент на списъка, като го направите първи по този начин, и след това да изтриете необходимия елемент:
voidcList :: Del ()
cElement * temp = глава;
глава = глава-> getref ();
Метод RemoveAll - премахва целия списък.
Този метод се основава на горното и се състои в последователно изтриване на първоначалните елементи на списъка, докато целият списък не бъде изтрит.
void cList :: RemoveAll ()
докато (elcount! = 0)
За да стартирате този метод, въведете командата "dellist" в менюто за работа със списъка (вижте фигура 3).
Фигура 3 - Въвеждане на командата за изчистване на списъка
И ако потребителят наистина е уверен в действията си, е необходимо да приеме офертата на програмата, след което целият списък ще бъде изтрит (виж фигура 4).
Фигура 4 - Празен списък
Метод за премахване - премахва конкретен елемент от списъка.
По-малко радикален метод от предишния. Само един, посочен като параметър, списъчен елемент се премахва. Това се случва по следния начин: програмата първо проверява правилността на въведения параметър, ако броят на изтрития елемент е по-малък от един или повече от общия брой елементи в списъка, тогава тя показва съобщение за грешка, но ако програмата няма оплаквания относно въведения параметър, тогава необходимите връзки на разположените в близост елементи се прехвърлят с изтрития, така че списъкът остава свързан, след което необходимият елемент се изтрива.
void cList :: Премахване (int del)
cElement * cur = глава, * de;
ако ((del> = 1) && (del
глава = глава-> getref ();
докато (j! = del-1)
cur = cur-> getref ();
de = cur-> getref ();
cur-> setref (de-> getref ());
coutsystem ("пауза");
За да стартирате този метод, въведете командата "delete" в менюто за работа със списъка. След това въведете номера на елемента, който трябва да бъде изтрит, или командата "назад", за да отмените изтриването (вижте фигура 5).
Фигура 5 - Процесът на изтриване на елемент от списъка
Списъкът след премахване на четвъртия елемент ще изглежда така (виж фигура 6).
Фигура 6 - Списък след изтриване на един елемент
Метод на вмъкване - вмъкване на нов елемент на определено място в списъка.
Този метод приема като параметри: позицията на добавения елемент и неговата цифрова стойност. Новият елемент ще стои точно на определеното място, като по този начин елементите вдясно от текущия ще бъдат изместени с една позиция. Когато добавяте нов елемент в началото на списъка, просто трябва да прехвърлите връзката от този елемент към следващия, като по този начин свържете списъка и предоставите връзка към първоначалния елемент. Малко по-различна ситуация възниква при добавяне на нов елемент между два съществуващи, за това с помощта на цикъл отидете до точката на вмъкване на елемента, след което асоциирайте компонентите, разположени вдясно и вляво от него, с новия елемент. В крайна сметка какво трябва да се направи, например, ако е необходимо да се удължи веригата: трябва да я отворите, след това да прикрепите нова връзка към първата част на веригата, да прикрепите втората към същата връзка, нещо подобно се прилага в този метод. Струва си да се отбележи, че ако посочите неправилна позиция за добавяне, която е по-малка от един или повече от общия брой елементи, програмата ще покаже подходящо съобщение за грешка.
void cList :: Вмъкване (int pos, int val)
cElement * cur = глава;
cElement * temp = нов cElement;
temp-> setdata (val);
ако ((поз.> = 1) && (поз
temp-> setref (глава);
докато (j! = pos-1)
cur = cur-> getref ();
p = cur-> getref ();
cur-> setref (temp);
temp-> setref (p);
coutsystem ("пауза");
За да стартирате този метод, въведете командата "insert" в менюто за работа със списъка. След това въведете позицията и числовата стойност на добавения елемент или командата "назад", за да отмените изтриването (вижте фигура 7).
Фигура 7 - Процесът на вмъкване на елемент
След добавяне на елемент със стойност 111 към третата позиция, списъкът ще изглежда така (виж Фигура 8).
Фигура 8 - Списък след добавяне на елемент
В хода на описанието менюто за работа със списъка беше споменато повече от веднъж, остава да се отбележи, че това меню значително улеснява работата със списъка. Алгоритъмът на неговата работа се състои в циклично извикване на същите методи, отпечатване на списък, например, докато бъде въведена определена команда. Списъкът с наличните команди може да се види, като напишете "help" в конзолата (вижте фигура 9)
Фигура 9 - Налични команди
Пълният код на менюто е показан в Приложение А.
Тестване
Често в процеса на работа възникват ситуации, свързани с неправилно въвеждане на данни, което може да доведе до неуспех на програмата. Разбира се, всяка програма трябва да прилага алгоритми за защита от неопитен потребител, предотвратявайки срива на програмата. Нека разгледаме как функционират такива алгоритми в създадената програма.
Първоначалното въвеждане на списъка се извършва със следния код:
if (atoi (ss)! = NULL)
mylist.Add (atoi (ss));
Преди да извикате метода add, за да добавите нов елемент към списъка, входният низ се проверява. Функцията atoi преобразува низ в числова стойност и връща NULL, ако входният низ не е число. По този начин при въвеждане всички редове, които не са числа, ще бъдат игнорирани, с изключение на реда с командата за спиране на въвеждането (вижте Фигура 10).
Фигура 10 - Въвеждане на неверни данни
След въвеждане на тези данни списъкът ще изглежда така (вижте фигура 11).
Фигура 11 - Получен списък
Програмата продължава да работи коректно след, дори след въвеждане на грешни данни. Подобни методи за работа с неверни данни се използват за останалите операции за въвеждане, присъстващи в програмата.
Заключение
В тази работа бяха получени понятия за абстрактните типове данни, за принципите на тяхното представяне в съвременните езици за програмиране, в частност в C ++. В повечето съвременни императивни езици основната концепция, използвана за описание на абстракциите в програмния код, е обектно-ориентираният подход. Обектно-ориентираното програмиране (OOP), подобно на ADT-базирания подход към програмирането, е до известна степен развитие на идеи за модулно програмиране. Модулите са програмни компоненти, които имат две важни свойства:
Модулите крият подробности за внедряването.
Модулите могат да се използват повторно в различни части на програмата.
Дейвид Парнас, в работата си от 1972 г., представя модулите като абстрактни машини, които съхраняват състояния в себе си и позволяват това състояние да се променя чрез специфичен набор от операции. Тази концепция е основна, както за концепцията за абстрактни типове данни, така и за обектно-ориентирано програмиране. Правейки паралели между работата на Парнас и съвременните концепции за ООП, е лесно да се види връзката между понятията клас и модул.
В тази работа линейните едносвързани списъци, които са абстрактен тип данни, са представени от разработените модули, за достъп до състоянията на които също се изпълняват специални операции, наречени методи в обектно-ориентираното програмиране.
Библиография
1. Обектно-ориентирани методи на Иън Греъм. Принципи и практика = Обектно-ориентирани методи: Принципи и практика. - 3-то изд. - М .: "Уилямс", 2004. - С. 880.
2. Антъни Синтес Овладейте обектно-ориентирано програмиране за 21 дни = Sams се научи на обектно-ориентирано програмиране за 21 дни. - М .: "Уилямс", 2002. - С. 672.
3. Бертран Майер Обектно-ориентирано проектиране на софтуерни системи + CD. Интернет университет по информационни технологии - INTUIT.ru, руско издание, 2005 г
4. Billig V.A. Основи на програмирането на C #. Интернет университет по информационни технологии - INTUIT.ru, 2006 г
5. „Нови езици за програмиране и тенденции на тяхното развитие”, В. Ушкова, 2005 г.
6. Bjarne Stroustrup "The C++ Programming Language" Special Edition или 3rd ed. Бином, Невски диалект, ISBN 5-7989-0226-2, 5-7940-0064-3, 0-201-70073-5
7. Bjarne Stroustrup "Дизайн и еволюция на езика C ++". DMK-Press, Петър, ISBN 5-469-01217-4, 0-201-54330-3
8. Bjarne Stroustrup "Принципи на програмиране и практика на използване на C ++". "ID Williams", 2011, ISBN 978-5-8459-1621-1 (руски)
9. Грейди Буч и др. "Обектно-ориентиран анализ и проектиране с примерни приложения" 2-ро или 3-то издание. Бином, Невски диалект, ISBN Williams 978-5-8459-1401-9, 0-201-89551-X, 0-8053-5340-2, 5-7989-0067-3, 5-7940-0017-1
10. Scott Meyers "Ефективно използване на C ++. 50 най-добри практики за подобряване на вашите програми и проекти" DMK, Peter, ISBN 0-201-92488-9, 5-93700-006-4, 5-469-01213-1
Приложение А
Програмен код на менюто
#include "cList.h"
#include "string.h"
използване на пространство от имена std;
coutwhile (strstr (ss, "стоп") == NULL)
if (atoi (ss)! = NULL)
mylist.Add (atoi (ss));
система ("cls");
докато (strstr (com, "изход") == NULL)
coutmylist.Print ();
if (strstr (com, "помощ")! = NULL) com_ind = 1;
if (strstr (com, "добави")! = NULL) com_ind = 2;
if (strstr (com, "insert")! = NULL) com_ind = 3;
if (strstr (com, "изтриване")! = NULL) com_ind = 4;
if (strstr (com, "dellist")! = NULL) com_ind = 5;
превключвател (com_ind)
система ("cls");
система ("cls");
coutcoutcoutcoutcoutcoutcom_ind = 0;
if (strstr (ss, "back") == NULL)
if (atoi (ss)! = NULL)
mylist.Add (atoi (ss));
система ("cls");
// вмъкване на елементи
if (strstr (ss, "back") == NULL)
if (atoi (ss)! = NULL)
система ("cls");
if (strstr (ss, "back") == NULL)
if (atoi (ss)! = NULL)
mylist.Insert (pos, atoi (ss));
система ("cls");
// изтриване на елементи
if (strstr (ss, "back") == NULL) се дефинира от набор от стойности даденои набор от операции ... свързани структури данни – списъци... Структура данниТова е колекция от елементи данни, между които ... в паметта на компютъра се извиква абстрактноили логично. По-често...
Многократни тип данни... Комплектите
Лекция >> Компютърни науки, програмиране... типподобно на простото видове данни... множествено число видовеописано в раздел видове... WU може да се опише. Резюмеизчислителни структури, описващи вход ... други случаи видовевсички компоненти списъктрябва да съвпада Типфайлови компоненти. ...
Обектно-ориентирани бази данни данниработа в разпределени мрежи
Резюме >> ИнформатикаРазработване на области на езици за програмиране с абстрактно видове даннии обектно-ориентирани езици за програмиране. ... видове данни- списък и масив. Всеки литерал е уникално идентифициран чрез индекс в масива и порядък в Списъкът ...
Резюмемодели за информационна сигурност
Резюме >> ИнформатикаЗащита на информацията ………………………………………………………… ..17 Резюмемодели за информационна сигурност ... управляващи взаимодействията и с двете видове данни(Правила за сертифициране): Всички ... различни вариации и допълнения към съществуващите Списъкът... Нива на сигурност - определени ...
