Абстрактен тип данни. Абстрактни типове данни

Всички вградени типове данни са абстрактни, въпреки че рядко се наричат ​​така.

Концепция за абстракция

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

Абстракция на процеса.Всички подпрограми са абстракции на процеси, те определят начина, по който програмата определя, че даден процес трябва да бъде извършен, без да уточнява подробностите как точно да го направи. Способността да абстрахирате многото детайли на алгоритъма, който изпълнява подпрограмата, ви позволява да създавате, четете и разбирате големи програми. Всяка абстракция на данни е операции, дефинирани като абстракции на процеси.

Абстракция на данни.Абстрактен тип данни е капсулиране, което съдържа само представяния на данни от един конкретен тип и подпрограми, които извършват операции върху данни от този тип. Чрез използване на контрол на достъпа, несъществени подробности за описание на типа могат да бъдат скрити от външни модули, които използват типа. Програмните модули, които използват абстрактен тип данни, могат да декларират променливи от този тип, въпреки че действителното представяне на типа е скрито от тях. Екземпляр на абстрактен тип данни се нарича обект.

Причината за създаване на абстракции на типове данни и абстракции на процеси е средство срещу сложността, начин да направите големи и/или сложни програми по-управляеми.

Капсулиране

Разделяне на програма на синтактични контейнери, които съдържат групи от логически свързани процедури и данни. Тези синтактични контейнери се наричат ​​модули, а процесът на разработка е модулиране.

Съставяне на програма от набори от процедури и данни, всяка от които може да бъде компилирана поотделно, без повторно компилиране на останалата част от програмата. Този набор се нарича компилационна единица.

Капсулирането е начин за интегриране на рутините и данните, които те обработват, в едно съгласувано цяло. Капсулирането, което се компилира отделно или независимо, е основата на абстрактна система и логическата организация на набор от свързани изчисления.

Абстрактни типове данни, дефинирани от потребителя

Абстрактните потребителски дефинирани типове данни трябва да имат следните свойства:

1) дефиниция на типа, която позволява на програмните модули да декларират променливи от този тип, като същевременно създават реално представяне на тези променливи в паметта.

2) набор от операции за манипулиране на обекти от този тип.

Формална дефиниция на абстрактен тип данни в контекста на дефинирани от потребителя типове: Абстрактен тип данни е тип данни, който отговаря на следните две условия.

Представянето (дефиниция на типа) и операциите върху обекти от този тип се съдържат в една синтактична единица, променливи от този тип могат да се създават в други модули.

Представянето на обекти от този тип е скрито от програмни модули, които използват този тип; операциите могат да се извършват върху обекти, които са директно предоставени в дефиницията на типа.

Опаковането на представянето на типа и операциите в отделна синтактична единица ви позволява да организирате вашата програма като логически единици, които могат да бъдат компилирани отделно. Второ, става възможно да се модифицират представянията на обекти от даден тип или операции с тях в отделна част на програмата. Има предимства при скриването на детайлите от представянето на даден тип. Клиентите не могат да "видят" подробностите от изгледа на обект и техният код е независим от този изглед. По този начин представянията на обектите могат да бъдат променени по всяко време, без да се изискват промени в клиентския код. Друго очевидно и важно предимство на скриването на информация е повишената надеждност. Клиентите не могат директно да променят основните представяния на обекти, умишлено или случайно, следователно целостта на такива обекти се увеличава. Обектите могат да се променят само с помощта на операциите, предвидени за това.

Проблеми с дизайна на типа

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

Има много малко общи вградени операции, които могат да се изпълняват върху обекти от абстрактни типове, за разлика от тези, предоставени от дефиниция на тип. Такива операции включват задачи и тестове за равенство и неравенство. Ако езикът не позволява на потребителите да претоварват оператора за присвояване, тогава той трябва да бъде вграден. Проверките за равенство и неравенство трябва да бъдат предварително определени в някои случаи, а не в други. Дизайнерът на типа трябва сам да дефинира операциите за повечето абстрактни типове данни.

Smalltalk, C ++ и Java директно поддържат абстрактни типове данни.

Абстрактни типове данни в C ++

Езиците Ada и Modula-2 осигуряват капсулиране, което може да се използва за моделиране на абстрактни типове данни, докато C ++ въвежда концепцията за клас, който директно поддържа абстрактни типове данни. В C ++ класовете са типове, но пакетите Ada и модулите Modula-2 не са типове. Импортират се пакети и модули, което позволява на импортиращия програмен блок да декларира променливи от всеки тип, дефиниран в пакета или модула. В програма на C ++ променливите се декларират като обекти от типа на този клас. По този начин класовете са много повече като вградени типове, отколкото пакети или модули. Програмна единица, която вижда пакет на език Ada или модул на език Modula-2, има достъп до всякакви отворени обекти само чрез техните имена. Програмна единица на C ++, която декларира екземпляр на клас, също има достъп до всички публични обекти в този клас, но само чрез екземпляр на този клас.

Последна актуализация: 04.08.2018 г

В допълнение към обичайните класове, C # има абстрактни класове... Абстрактният клас е като обикновен клас. Може също да има променливи, методи, конструктори, свойства. Единственото нещо е, че ключовата дума abstract се използва при дефиниране на абстрактни класове:

Абстрактен клас Human (public int Дължина (get; set;) public double Тегло (get; set;))

Но основната разлика е, че не можем да използваме конструктора на абстрактен клас, за да създадем неговия обект. Например, както следва:

Човешки h = нов човек ();

Защо имаме нужда от абстрактни класове? Да кажем, че в нашата програма за банковия сектор можем да дефинираме две основни субекти: банков клиент и банков служител. Всеки от тези субекти ще бъде различен, например за служител трябва да дефинирате неговата позиция, а за клиент - сумата по сметката. Съответно, Клиент и Служител ще съставляват отделни класове Клиент и Служител. В същото време и двата обекта могат да имат нещо общо, например име и фамилия, някаква друга обща функционалност. И е по-добре да преместите тази обща функционалност в някакъв отделен клас, например Person, който описва човек. Тоест, класовете Служител (служител) и Клиент (банков клиент) ще произлизат от класа Лице. И тъй като всички обекти в нашата система ще представляват или банков служител, или клиент, ние няма да създаваме обекти директно от класа Person. Така че има смисъл да го направим абстрактно:

Абстрактен клас Лице (обществен низ Име (get; set;) публичен Лице (име на низ) (Име = име;) public void Display () (Console.WriteLine (Име);)) клас Клиент: Лице (public int Sum (get ; set;) // сума на акаунта public Клиент (име на низ, int сума): база (име) (Sum = sum;)) клас Служител: Лице (публичен низ Позиция (get; set;) // позиция публичен служител ( низ име, позиция на низа): основа (име) (Позиция = позиция;))

Тогава можем да използваме тези класове:

Клиент клиент = нов клиент ("Том", 500); Служител служител = нов служител ("Bob", "Apple"); клиент.Дисплей (); служител.Дисплей ();

Или дори така:

Лице клиент = нов клиент ("Том", 500); Лице служител = нов служител ("Боб", "Оператор");

Но ние НЕ можем да създадем обект Person с помощта на конструктора на класа Person:

Лице лице = ново лице ("Сметка");

Въпреки това, въпреки факта, че не можем директно да извикаме конструктора на класа Person за създаване на обект, въпреки това конструкторът в абстрактните класове може да играе важна роля, по-специално да инициализира някои променливи и свойства, общи за производните класове, както и случай със свойството Name. Въпреки че горният пример не извиква конструктора Person, извлечените класове от Client и Employee могат да се позовават на него.

Абстрактни членове на класа

В допълнение към обичайните свойства и методи, абстрактният клас може да има членове на абстрактни класове, които се дефинират с помощта на ключовата дума abstract и нямат функционалност. По-специално, абстрактното може да бъде:

• Имоти

  Индексатори

Членовете на абстрактния клас не трябва да имат модификатора private. В този случай извлеченият клас трябва да отмени и реализира всички абстрактни методи и свойства, които са в базовия абстрактен клас. Когато се отменя в производен клас, такъв метод или свойство също се декларира с модификатора на override (както при нормалното замяна на виртуални методи и свойства). Трябва също да се отбележи, че ако даден клас има поне един абстрактен метод (или абстрактно свойство, индексатор, събитие), тогава този клас трябва да бъде дефиниран като абстрактен.

Абстрактните членове, подобно на виртуалните, са част от полиморфен интерфейс. Но ако в случай на виртуални методи кажем, че наследяващият клас наследява реализацията, в случай на абстрактни методи интерфейсът, представен от тези абстрактни методи, се наследява.

Абстрактни методи

Например, нека направим метода Display абстрактен в примера по-горе:

Абстрактен клас Лице (публичен низ Име (get; set;) публичен Лице (име на низ) (Име = име;) публичен абстрактен void Display ();) клас Клиент: Лице (public int Sum (get; set;) // sum на акаунта public Client (име на низ, int sum): база (име) (Sum = sum;) public override void Display () (Console.WriteLine ($ "(Име) има акаунт за сумата (Sum)") ;)) клас Служител: Лице (обществен низ Позиция (get; set;) // позиция публичен Служител (име на низ, позиция на низа): база (име) (Позиция = позиция;) публично замяна void Display () (Console.WriteLine ($ " (Позиция) (Име) ";))

Абстрактни свойства

Трябва да се отбележи използването на абстрактни свойства. Дефинирането им е подобно на дефинирането на автоматични свойства. Например:

Абстрактен клас Лице (публичен абстрактен низ Име (get; set;)) клас Клиент: Лице (име на частен низ; публичен заместващ низ Име (получаване (връщане "Mr / Ms." + Име;) набор (име = стойност;))) ) клас Служител: Лице (публичен низ за замяна Име (получаване; набор;))

Класът Person дефинира абстрактното свойство Name. Изглежда като автомобилна собственост, но не е автомобилна собственост. Тъй като това свойство не трябва да се прилага, то има само празни блокове get и set. В производните класове можем да заменим това свойство, за да го направим пълно свойство (като в класа Client) или да го направим автоматично (като в класа Employee).

Отхвърляне на изпълнението на абстрактни членове

Производният клас трябва да реализира всички абстрактни членове на базовия клас. Въпреки това можем да се откажем от реализацията, но в този случай извлеченият клас също трябва да бъде дефиниран като абстрактен:

Абстрактен клас Лице (публичен абстрактен низ Име (get; set;)) Мениджър на абстрактен клас: Лице ()

Пример за абстрактен клас

Пример от учебника е системата от геометрични фигури. В действителност няма геометрична фигура като такава. Има кръг, правоъгълник, квадрат, но просто няма фигура. И кръгът, и правоъгълникът обаче имат нещо общо и са форми:

// абстрактен клас на фигурата abstract class Figure (// абстрактен метод за получаване на периметъра public abstract float Perimeter (); // абстрактен метод за получаване на областта public abstract float Area ();) // производен клас на класа правоъгълник Правоъгълник: Фигура (public float Width (get; set;) public float Height (get; set;) public Rectangle (float width, float височина) (this.Width = ширина; this.Height = височина;) // отменя получаването на периметър public override float Perimeter () (връщане ширина * 2 + височина * 2;) // отменя получаване на зона public override float Area () (връщане ширина * височина;))

Приложение към работната програма по дисциплината "Структури и алгоритми за обработка на данни в компютър"

Абстрактният тип данни "Списък".

Списък- последователност от елементи от определен тип а1 , а2 , ..., а н, където н https://pandia.ru/text/78/308/images/image001_307.gif "width =" 13 "height =" 16 "> 1, след това а1

Нарича се първи елемент и ан- последният елемент от списъка. Елементите от списъка са линейно подредени според позицията им в списъка. Ai елемент предшестваелемент ai+1 за и = 1,2, н-1 и ai Трябва per ai-1 за и = 2,3, н. Всеки елемент от списъка aiТо има позиция и, и=1,2, н. Има позиция в списъка , означаващ края на списъка - нула. Следва последния елемент в списъка.

Оператори на ADT "Списък":

1. ВМЪКНЕТЕ ( х, R,Л). Този израз вмъква обект NSв позиция Рв списъка L,преместване на елементи от позиция p и по-нататък до следващата по-висока позиция. Така че, ако списъкът Лсе състои от елементи а1 , а2 , ..., ан a1, a2, ..., ap-1, x, ap, ..., ан.... Ако p приеме стойността нула, тогава ще имаме а1 , а2 , ..., ан , , NS... Ако в списъка Лняма позиция R,тогава резултатът от това изявление е недефиниран.

2. НАМЕРИ(х , Л ). Тази функция връща позицията на обекта NSв списъка Л.Ако обектът е в списъка хсе появява няколко пъти, след което се връща позицията на първия обект от началото на списъка NSАко обектът NSне е в списъка Лслед това се връща нула.

3. ИЗВЪРЧВАНЕ(стр , Л ). Тази функция връща елемента на позиция Рв списъка Л.Резултатът е недефиниран if p = нулаили в списъка Лняма позиция Р.

4. ИЗТРИЙ(стр , Л ). Този оператор премахва елемента на позиция Рсписък Л.Така че, ако списъкът Лсе състои от елементи а1 , а2 , ..., ан, то след изпълнение на този оператор ще изглежда така а1, а2, ...,, ап- и , ап+ и, ..., ан. Резултатът е недефиниран, ако списъкът съдържа Лняма позиция Рили Р = нула.

5. СЛЕДВАЩИЯ ( п, Л ) и ПРЕДИШЕН (стр, Л ). Тези функции връщат съответно следващата и предишната позиция от позицията Рв списъка Л.Ако R -последна позиция в списъка L,след това СЛЕДВАЩ (стр, Л) = нула... Функцията NEXT е недефинирана, когато p =нула... Функцията PREVIOUS е недефинирана, ако р = 1.И двете функции са недефинирани, ако списъкът Лняма позиция Р.

6. MAKENULL( Л ) ... Тази функция прави списък Лпразен и връща позицията нула.

7. ПЪРВО(Л ). Тази функция връща първата позиция в списъка L. Ако списъкът е празен, тогава позицията се връща нула.

8. СПИСЪК ЗА ПЕЧАТ(Л ). Отпечатва елементи от списъка Лв реда, в който се появяват в списъка.

Списъчен изглед с помощта на масив:

Изглед на списък с помощта на едносвързан списък:

легенда:

- указател към началото на списъка,

· последно - показалец към последния елемент в списъка ,

· максимална дължина - максималната дължина (брой елементи) в списъка.

Представяне на списък с помощта на двусвързан списък:

Упражнения:

1. Напишете програми за вмъкване, изтриване и търсене на елементи от сортиран списък, като използвате за реализиране на списъка

§ масив,

§ указатели.

2. Напишете програма за сливане

§ два сортирани свързани списъка,

§ n сортирани свързани списъци,

3. Даден е полином от вида

p (x) = c1 xд1 + ° С2 xe2 + + снNSн, където e1> e2> ...> дн> 0.

Такъв полином може да бъде представен като свързан списък, където всеки елемент има три полета: едно за коефициента сивторият е за степенника дитретият е за указател към следващия елемент. За описаното представяне на полиноми, напишете програма за събиране и умножение на полиноми, използвайки това представяне.

4. Реализирайте LIST ADT за всеки тип данни и неговите изрази INSERT, LOCATE, RETRIEVE, DELETE, NEXT, PREVIOUS, MAKENULL, PRINTLIST:

§ списъкът е даден като масив,

§ списъкът е посочен като едносвързан списък,

§ списъкът е посочен като двусвързан списък.

Работна програма раздел 2.1.2

Абстрактният тип данни "Stack".

Стек - това е специален тип списък, в който всички вмъквания и изтривания се извършват само в единия край, наречен връх , (Горна част). Аксесорът се използва за стека LIFO(последен влязъл-първи излязъл - последен влезе - първи излязъл).

Оператори на ATD "Stack":

1. MAKENULL(С). Изпразнете стека S.

2. ГОРНА ЧАСТ(С). Връща елемента от горната част на стека S. Обикновено горната част на стека се идентифицира с позиция 1, след което TOP (S) може да се запише в термините на общите списъчни оператори като ИЗВЪРЧАВАНЕ (ПЪРВО (S), S).

3. POP(С). Премахва елемент от горната част на стека (изскача от стека), по отношение на списъчните оператори, този израз може да бъде записан като DELETE (ПЪРВО (S), С).

4. НАТИСАЙТЕ(х, С ). Вмъква елемент NSдо горната част на стека S (бута артикула върху стека). Елементът, който преди това е бил в горната част на стека, става елемент до върха и т. н. По отношение на общите списъчни оператори, този израз може да бъде записан като INSERT (; c, FIRST (S), С).

5. ПРАЗЕН(С) ... Тази функция връща true, ако стекът Спразен и фалшив в противен случай.

масив:

Изглед на стека с помощта на едносвързан списък:

Упражнения:

Реализирайте STACK ADT за всеки тип данни и неговите оператори MAKENULL, TOP, POP, PUSH, EMPTY.

§ стекът е посочен като масив,

Стекът е зададен като единично свързан списък.

Работна програма раздел 2.1.2

Абстрактният тип данни "Опашка".

Опашка (опашка) е специален тип списък, където елементите се вмъкват от единия край наречен задната (отзад) и се отстраняват от другия, отпред (отпред). Опашките се наричат ​​още "списъци FIFO" (FIFO означава първи дошъл, първи излязъл: първи влезе, първи излязъл). Операторите, изпълнявани на опашки, са подобни на операторите на стека. Съществената разлика между тях е, че се вмъкват нови елементи край на списъка а не в началото, както в стекове.

Оператори на ADT "Опашка":

1. MAKENULL(В) изчиства опашката Q , правейки го празен.

2. ПРЕДНО(В) - функция, която връща първия елемент от опашката В.Можете да приложите тази функция с помощта на списъчни оператори като ИЗВЪРЧАВАНЕ (ПЪРВО (Q), Q ).

3. ENQUEUE(а, Q) вмъква елемент NSв края на опашката Q.

Със списъчни оператори този оператор може да се изпълни по следния начин: INSERT (x, END (Q), Q ).

4. DEQUEUE(В) премахва първия елемент от опашката Q . Също така приложимо със списъчни оператори като DELETE (ПЪРВО (Q), Q).

5. ПРАЗЕН(В) връща истина, ако и само ако Q е празна опашка.

цикличен масив:

легенда:

В- опашка,

В. отпред- показалец към началото на опашката,

В. отзад- указател към края на опашката.

Представяне на опашката с едносвързан списък:

Упражнения:

Реализирайте QUEUE ADT за всеки тип данни и неговите оператори MAKENULL, FRONT, ENQUEUE, DEQUEUE, EMPTY.

Опашката е посочена като кръгов масив,

Опашката е посочена като двусвързан списък.

Абстрактен тип данни "Дърво".

дърво е колекция от елементи, наречени възли (един от които е дефиниран като корен ), и връзки ("родител"), които образуват йерархична структура от възли. Възлите, точно както елементите на списък, могат да бъдат елементи от всякакъв тип. Формално дървото може да бъде дефинирано рекурсивно, както следва.

1. Един възел е дърво. Същият възел е и коренът на това дърво.

2. Нека NS -това е възел, а T1 , T2, ...,Tk- дървета с корени н1 . н2 , ..., nkсъответно. Можете да построите ново дърво, като направите NSродител на възли н1 . н2 , ..., nk... В това дърво NSще бъде коренът, a T1 , T2, ...,Tk - поддърветатози корен. възли н1 . н2 , ..., nkса наречени синове възел NS

Това определение често включва понятието нулево дърво , тоест "дърво" без възли, такова дърво се обозначава с думата нула .

Пример: Относноглава от книгата може да бъде схематично представена от дърво. Връзката родител-син се показва като линия. Дърветата обикновено се рисуват отгоре надолу с родителите над "децата".

DIV_ADBLOCK135 ">

Височина на възела дървото е дължината на най-дългия път от този възел до лист. В примера височината на възела Глава 1е равно на 1, възел Глава 2 - 2, и възел Ch. Z - 0. Височина на дървото съвпада с височината на корена. Дълбочина на възела се дефинира като дължината на пътя (той е единственият) от корена до този възел.

Синовете на възел обикновено се подреждат отляво надясно. Следователно двете дървета на фигурата са различни, тъй като реда на синовете на възела аразличен. Ако редът на синовете се игнорира, тогава такова дърво се нарича разстроен , иначе дървото се нарича подредени .

Оператори на ATD "Tree":

1. РОДИТЕЛ(н, T). Тази функция връща родителя на възела NSв дървото T.Ако NSе корен, който няма родител, тогава в този случай се връща нула... Тук нулапоказва, че е възникнало дърво извън границите.

2. НАЙ-ЛЯВ__ ДЕТЕ(н , T). Тази функция връща най-лявото дете на възела. нв дървото T.Ако не лист (и следователно няма син), тогава се връща нула.

3. НАД_ БРАТ/СЕСТРА(н , T). Тази функция връща десния брат на възела NSв дървото Tили стойност нула,. ако не съществува. За това е родителят Рвъзел NSи всички синове на възела R,тогава сред тези синове е възелът непосредствено вдясно от. възел NS

4. ЕТИКЕТ(н , T ). Връща етикета на възела н... дърво T.Тази функция изисква етикети да бъдат дефинирани на възлите на дървото.

5. СЪЗДАВАЙТЕ(v , T 1 , T 2 , ..., ти ,) е семейство от функции, които създават нов корен за всяко i = 0, 1, 2, ... rс етикет vи след това за този корен създава i синове, които стават корени на поддървета T1 , Т2, ....ти;. Тези функции връщат коренно дърво r... Имайте предвид, че ако i = 0, тогава се връща един възел r, което е едновременно корен и лист.

6. КОРЕН(T ) връща възела, който е коренът на дървото T, Ако T- празно дърво след това се връща нула.

7. MAKENULL(T ). Този оператор прави дървото Tпразно дърво.

Представяне на дърво с помощта на масив от родители:

Дървовиден изглед с помощта на свързани списъци:

Представяне на дървото чрез леви синове и десни братя.

Обозначения на фигурата:

пространство на възли – масив от възли на дърво,

етикет – етикет на възел, заглавка – индексът на левия син в списъка на синовете,

клетъчна паза – масив от списъци със синове на възли,

възел – указател към възел в масивпространство на възли , следващия – индексът на десния син в списъка на синовете.

Упражнения:

1. Дадено дърво:

DIV_ADBLOCK137 ">

§ дървото се дава като масив от записи на възел, съдържащ индекса на най-левия син, индекса на десния брат и сестра и етикет,

Свързано двоично дърво се определя с помощта на указатели към левия и десния син.

4. Напишете функции за преминаване на двоично дърво в напред, назад и симетричен ред.

Работна програма раздел 2.1.3

Абстрактният тип данни "Set".

Много обикновено се изобразява като последователност от неговите елементи, затворени в къдрави скоби, например (1, 4) означава набор, състоящ се от два елемента - числа 1 и 4. Редът, в който са записани елементите на множеството, не е съществен, така че можете да пишете (4, 1) по същия начин като (1, 4), когато пишете същия набор. Множеството не е списък (поне поради произволния ред на елементите). В набора няма дублиращи се елементи ((1, 4, 1) не е набор).

Основната концепция на теорията на множествата е концепцията за връзката принадлежащи към комплекта обозначен със символа. По този начин влизането NS NSне принадлежи към множеството А“, т.е. NSне е член на комплекта А... Има специален набор, обозначен със символ, наречен празни, много , и който няма елементи. Задайте DIV_ADBLOCK138 ">

Казват, че множеството А съдържа в комплекта V(или включва се в множество V),написано А Vили V Аако някой елемент от множеството Асъщо е елемент от комплекта V.Кога А Vсъщо така казват, че комплектът Ае подмножество на множеството V.

Например (1, 2) https://pandia.ru/text/78/308/images/image019_36.gif "width =" 15 "height =" 15 src = "> Vи AB, тогава множеството A се извиква собствено, вярно или строго подмножество множество V.

Основните операции, извършвани върху множествата, са обединение, пресичане и разлика. Консолидация комплекти Аи V(означено с А V)се нарича множество, състоящо се от елементи, принадлежащи на поне едно от множествата Аи V.

Пресичане комплекти Аи V(означено с А V)наречено множество, състоящо се само от онези елементи, които принадлежат на множеството А, и комплекта V. Разликата комплекти Аи V(означено с А\ Б) се нарича множество, състоящо се само от тези елементи на множеството Акоито не принадлежат на набора V.

Например, ако A = (a, b, c) и B = (b, a), тогава A B = (a, b, c, d), A B = (b) и A \ B = (a, c ) .

Оператори на ADT "Set":

1. СЪЮЗ(А, Б, В) Аи V С,равни А V.

2. КРЕСЪЧНИЦА(А, Б, В) има зададени "входни" аргументи Аи V, и като резултат - наборът "изход". С,равни А V..

3. РАЗЛИКА(А, Б, В) има зададени "входни" аргументи Аи V, и като резултат - наборът "изход". С,равни А \ Б.

4. СЛИВАНЕ( А , B, C) операторът изпълнява сливане (се сливат), или обединение на несвързани множества . Този оператор не се различава от оператора. СЪЮЗ, но тук се приема, че операндът се задава не се пресичат (т.е. нямат общи елементи). Операторът присвоява на набора Ссмисъл А V, но резултатът ще бъде недефиниран, ако A B, т.е. в случая, когато множествата Аи Vимат общи елементи.

5. член(х, А ) има зададени аргументи Аи обект NSот същия тип като елементите на множеството Аи връща булева стойност вярно(вярно) ако NS a "," b "," c ")) = "а".Операторът МАКС.

11.РАВЕН(А , В ) връща стойността вярноако и само ако множествата Аи Vсе състоят от едни и същи елементи.

12. НАМИРАМ(х ) работи в среда, в която има набор от несвързани множества. Връща името (единствено число) на набора, който има елемент NS

Задайте представяне:

Наборът може да бъде определен с помощта на масив или свързан списък.

Упражнения:

1. Дадени са две множества A = (1, 2, 3) и B = (3, 4, 5). Какъв ще бъде резултатът от изпълнението на следните оператори?

СЪЮЗ (ABC),

КРЕСЪЧНОТО (A, B, C),

РАЗЛИКА (A. B. C),

ЧЛЕН (л. А),

ВМЕСТЕ (1, A),

ИЗТРИВАНЕ (1, A),

2. Реализирайте Set ADT за всеки тип данни и неговите оператори MAKENULL, UNION, INTERSECTION, MEMBER, MIN.

Наборът се посочва с помощта на масив с фиксирана дължина и указател към последната заета позиция в масива,

Наборът се посочва с помощта на несортиран свързан списък,

Наборът се посочва с помощта на сортиран свързан списък,

Работна програма раздел 2.1.3

Специални видове комплекти

Двоично дърво за търсене Тип абстрактни данни

Двоично дърво за търсене - структура от данни за представяне на множества, чиито елементи са подредени чрез някаква линейна подредба. Дърветата за двоично търсене могат да прилагат оператори за набор INSERT, ИЗТРИЙ, ЧЛЕНи МИН, а времето им за изпълнение средно е от порядъка на O (log n) за набори, състоящи се от NSелементи.

Характеристика на едно двоично дърво за търсене е, че неговите възли са етикетирани с множество елементи (възлите на дървото съдържат множество елементи). Освен това всички елементи се съхраняват в възлите на лявото поддърво на всеки възел NS, по-малко от елемента, съдържащ се във възела NS,и всички елементи, съхранени във възлите на дясното поддърво на възела NS, повече от елемента, съдържащ се във възела NS

Примери за двоично дърво:

https://pandia.ru/text/78/308/images/image023_7.jpg "width =" 277 "height =" 122 src = ">

Дървовидният изглед на AVL е същият като изгледът на дървото за двоично търсене.

Друг вид дърво за балансирано търсене е 2-3 дърва. Структурата на дърво 2-3 се различава от структурата на дърво за двоично търсене. За дърво 2-3 е типично, че всички възли имат 2 или 3 сина, всички пътища от корен до лист имат еднаква дължина и всички елементи от комплекта се съдържат в листата. Възлите 2-3 на дървото са разделени на вътрешни и крайни (листа). Вътрешните възли се използват само за търсене в дърво на маршрута. Всеки вътрешен възел съдържа ключовете на най-малките елементи на втория и третия син (ако има трети син) и указатели към възлите на синовете.

Свързан дървовиден изглед за двоично търсене:

Представяне на балансирано свързано 2-3 дърво:

Упражнения:

1. Начертайте всички възможни двоични дървета за търсене за четирите елемента 1, 2, 3 и 4.

2. Вмъкнете цели числа 7, 2, 9, 0, 5, 6, 8, 1 в празно двоично дърво за търсене.

3. Покажете резултата от премахването на числото 7 и след това на числото 2 от дървото, получено в предишното упражнение.

4. Начертайте дърво 2-3, което ще бъде резултат от вмъкване на елементи 5, 2, 7, 0, 3, 4, 6, 1, 8, 9 в празното множество (представено като дърво 2-3).

5. Покажете резултата от премахването на елемент 3 от 2-3 от дървото, получено в предишното упражнение.

3. Приложете ADT в дървото на търсене за всеки тип данни и неговите изрази INSERT, DELETE, MEMBER и MIN.

Дървото е дадено като свързано двоично дърво

Дървото се дава като 2-3 дървета

Работна програма раздел 2.1.3

Абстрактен тип данни "Речник".

Речник - комплект, предназначен за съхранение на "текущи" обекти с периодично вмъкване или изтриване на някои от тях. От време на време също става необходимо да се установи дали даден елемент присъства в даден набор. Речникът се реализира с помощта на ADT на речника с оператори ВМЕСТЕ,ИЗТРИЙи ЧЛЕН... Речниковият набор от оператори също включва оператора MAKENULLза инициализиране на ADT структури от данни.

Речникът може да бъде представен с помощта на хеш таблица. Таблицата е изградена на базата на следната идея: потенциален набор от елементи (евентуално безкраен) се разделя на краен брой класове. За Vкласове, номерирани от 0 до В 1, в процес на изграждане хеш функция зтака че за всеки елемент NSоригинална зададена функция ч (х)взема цяло число от интервала 0, ..., V - 1, което съответства на класа, към който принадлежи елементът NSелемент NSчесто се обаждат ключ, ч ( х) - хаш-стойност х, и "класове" - сегменти ... Как да разрешите колизии при хеширане (два елемента от набор имат една и съща стойност ч (х)), прилагат се както публично, така и частно хеширане.

отворена хеш таблица

Извика се масив сегментна таблица и индексирани номера на сегменти 0, 1, ..., B - 1 , съдържа заглавки за Vсвързани списъци. елемент и-th list е елемент от оригиналния набор, за който з(.x :) =и.

Речниково представяне с частна хеш маса

Сегментната таблица съхранява директно елементите на речника. Следователно във всеки сегмент може да се съхранява само един речников елемент. При частно хеширане се използва техниката повторно хеширане ... Когато се опитвате да поставите елемент х за номериран сегмент з ( х ) , който вече е зает от друг елемент, се избира поредица от номера на сегменти з 1 ( х ) ,з 2 ( х ) , … къде може да се постави елементът. Заетостта на всеки от тези сегменти се проверява последователно, докато се намери свободен сегмент. Елементът се поставя в него х ... Използват се различни методи за разрешаване на сблъсък за задаване на номера на сегменти при повторно хеширане. Например, линеен метод на хеширане, метод на среден квадрат, метод на случайно хеширане

Упражнения:

1. Да предположим, че използвате хеш функцията h (i) = i% 7 за хеширане на цели числа в 7-сегментна хеш таблица.

· Дайте получената хеш таблица, ако в нея са вмъкнати точните кубчета 1, 8, 27,64,125, 216,343;

· Повторете предишната точка за затворена хеш таблица с техника за линейно разрешаване на сблъсък.

2. Да предположим, че има частна хеш таблица с 5 сегмента, хеш функция h (i) = i% 5 и техника за линейно разрешаване на сблъсък. Покажете резултата от вмъкването на последователността от числа 23, 48, 35, 4, 10 в първоначално празната хеш таблица.

3. Реализирайте ADT на речника за текстови низове и неговите INSERT изрази , ИЗТРИВАНЕ, ЧЛЕН И МАKENULL

Речникът се посочва с помощта на отворена хеш таблица,

Речникът се посочва с помощта на затворена хеш таблица с техника за линейно разделяне на сблъсък,

Работна програма раздел 2.1.3

Абстрактният тип данни "Display".

Дисплей - това е набор, върху елементите на който е дефинирана функцията за показване на елементи от същия тип ( области на дефиниция ) към елементи от друг тип ( диапазон от стойности ) от друг вид. Дисплей Мсъвпада с елемент дот тип domaintype от обхват до елемент rот тип rangetype от диапазон: М(д) = r.Празен дисплей не съдържа никакви елементи

Оператори на ADT "Дисплей":

1. MAKENULL(М ). Прави дисплей Мпразен.

2. ПРИСЛОЖИ (М г, г). Прави М(д) равни rбез значение как М(д) беше дефиниран по-рано.

3. ИЗЧИСЛЯВАНЕ ( М, г, г). Връща true и присвоява стойност на r М(д), ако последното е дефинирано и връща false в противен случай.

Изглед на дисплея:картографирането може да бъде ефективно реализирано с помощта на хеш таблици. Тук х определя стойността от обхвата на дефиницията на дисплея и елемента на таблицата с числото з ( х ) - елемент от гамата.

Работна програма раздел 2.1.3

Абстрактен тип данни на опашката с приоритет

Приоритетна опашка е набор за елементите, на които е зададена приоритетната функция, тоест за всеки елемент х set, можете да изчислите функцията R( х )- приоритет на елемента х , който обикновено приема стойности от набор от реални числа или, по-общо казано, от някакъв линейно подреден набор.

ADT "Приоритетна опашка"на базата на ADT "Set" с оператори INSERTи ИЗТРИВАНЕа също и с оператора MAKENULLза инициализиране на структурата на данните. Оператор INSERTза приоритетна опашка се разбира в обичайния смисъл, докато ИЗТРИВАНЕе функция, която връща елемента с най-нисък приоритет и като страничен ефект го премахва от набора.

Представяне на опашката с подреден двусвързан списък.

Представяне на опашката с частично подредено свързано дърво:

Основната идея зад тази реализация е да се организират елементите на опашката в двоично дърво. На по-ниско ниво, където някои листа може да липсват, всички липсващи листа могат да бъдат разположени само вдясно от сегашните листа от по-ниско ниво. По-важно е, че дървото частично поръчан . Това означава, че приоритетът на възела vне по-голям от приоритета на който и да е син на възела v, където приоритет на възел е стойността на приоритета на елемента, съхранен в този възел. От фигурата се вижда, че малките приоритетни стойности не могат да се появят на по-високо ниво, където има големи приоритетни стойности.

Функцията DELETEMIN връща елемента с най-нисък приоритет, който трябва да бъде коренът на дървото. За да не се унищожи дървото и да се запази частичното подреждане на приоритетните стойности в дървото след отстраняване на корена, се извършват следните действия: най-десният възел се намира на най-ниското ниво и временно се поставя в корена на дървото. След това този елемент се спуска надолу по клоните на дървото (до по-ниски нива), разменяйки местата си със синовете с по-нисък приоритет по пътя, докато този елемент се превърне в лист или не влезе в позиция, при която неговите синове ще имат поне не по-малък приоритет.

Представяне на опашка с помощта на масив, съдържащ възлите на частично подредено дърво:

В масив Апървият нпозициите съответстват нвъзли на дърво. елемент А съдържа корена на дървото. Ляв син на възел на дърво А[ и], ако съществува, е в клетката А, а правилният син, ако го има, е в килията А. И обратно, ако синът е в килията А[ и], тогава неговият родител е в клетката А[ и%2] ... Възлите на дървото запълват клетките А, А, … А[ н] последователно ниво по ниво, като се започне от корена, а вътре в нивото - отляво надясно. Дървото, показано по-горе, ще бъде представено в масива със следната последователност от неговите възли: 3, 5, 9, 6, 8, 9, 10, 10, 18, 9.

Упражнения:

1. Начертайте частично подредено дърво, като вмъкнете в празно дърво цели числа 5, 6, 4, 9, 3, 1 и 7. Какъв ще бъде резултатът от последователното прилагане на три оператора DELETEMIN към това дърво?

2. Реализирайте ADT на приоритетната опашка за всеки тип данни и неговите изрази INSERT, DELETEMIN и MAKENULL

§ частично подредено дърво се реализира с помощта на указатели,

§ Частично подредено дърво се реализира с помощта на масив.

Работна програма раздел 2.1.3

Абстрактният тип данни "Обединение на множества".

ADT е обединение от обекти, всеки от които е множество. Основните действия, извършвани върху такъв набор, са комбиниране на наборите в определен ред, както и проверка дали даден обект принадлежи към определен набор. Тези задачи се решават с помощта на оператори СЛИВАНЕ(Източване) и НАМИРАМ(Намирам). Оператор MERGE ( А, B, C) прави комплекта Сравно на обединението на множествата Аи Vако тези множества не се пресичат (т.е. нямат общи елементи); този оператор е недефиниран, ако множествата Аи Vпресичат се. функция НАМЕРИ ( х) връща набора, към който принадлежи елементът NS; в случай, когато NSпринадлежи на няколко набора или не принадлежи на нито един, стойността на тази функция е недефинирана.

Оператори на ADT „Обединение на множества“:

1. СЛИВАНЕ(А , V) съчетава компоненти Аи ... V,резултатът се присвоява или на А или V.

2. НАМИРАМ(х ) - функция, която връща името на компонента, към който принадлежи NS

3. НАЧАЛНАТА(А , NS ) създава компонент с име A, съдържащ само елемента NS

Представяне на обединение на множества с помощта на масиви:

Името на набора е същото като стойността на индекса на масива setheaders (име 0 )

легенда:

setheaders - масив от заглавки на набора:

§ с изброявам - броят на елементите в комплекта,

§ първи елемент - индекс на масиваименас първия елемент от комплекта,

имена – масив от списъци с елементи на множества:

име на набор - името на набора, към който принадлежи елементът, следващия елемент - индексът на следващия елемент в списъка на даденото множество (индексна стойност 0 се използва като край на списъка).

Работна програма раздел 2.1.3

Абстрактен тип данни “ Насочена графика "

Основни дефиниции:

Насочена графика (орграф ) г = (V, E)се състои от много върхове Vи много дъги Е.Върховете също се наричат възли , и дъги - ориентирани ребра . Дъгата може да бъде представена като подредена двойка върхове ( u, w), къде е върха иНаречен началото , а w - край дъги.

Казват също, че дъгата и -> w води от върха до върха w,и горната част w съседен с горна част v.

Пример за диграф 1:

Върховете на орграфа могат да се използват за представяне на обекти, а дъгите могат да се използват за представяне на връзки между обекти.

от в орграф имаме предвид последователност от върхове v1 , v2 , … , vn , , за които има дъги v1 -> v2 , v2 , -> v3, , ..., vn-1 , -> vn. Този път започва от върха v1 и преминаване през върховете v2 , v3 , ..., vn-1 завършва на върха vn. Дължина на пътя - броят на дъгите, които изграждат пътя, в този случай дължината на пътя е NS - 1 ... Като специален случай на път, разгледайте един връх vкато път с дължина 0 от върха vДа сесъщия връх v... На фигурата последователността от върхове 1, 2, 4 образува път с дължина 2 от връх 1 до връх 4.

Пътят се нарича просто , ако всички върхове на него, с възможно изключение на първия и последния, са различни. Цикъл - това е прост път с дължина най-малко 1, който започва и завършва в същия връх. На фигурата върхове 3, 2, 4, 3 образуват цикъл с дължина 3.

В много приложения е удобно да се прикачи някаква информация към върховете и дъгите на орграф. За тези цели се използва маркиран орграф , тоест орграф, в който всяка дъга и/или всеки връх има съответни етикети. Етикетът може да бъде име, тегло или стойност (дъги) или стойност на данни от някакъв даден тип.

Пример 2 на маркирана орграфа:

DIV_ADBLOCK149 ">

3. Алгоритъм за преходно затваряне (алгоритъмът на Warshall):

За графиката г = (V, Е) алгоритъмът изчислява матрицата на транзитивността T, всеки елемент от който T[и, j] = 1 само когато има път от върха идо горе jи T[ и, j] = 0 в противен случай.

4. Алгоритъм за намиране на центъра на орграф:

Нека бъде и -произволен връх на орграф г = (V, E). Ексцентричност (максимално отстраняване) върхове иопределена като

макс (минимална дължина на пътя от върха wдо горе v }

w V

Диграфски център гсе нарича върхът с минимален ексцентриситет. С други думи, центърът на орграфа е върхът, за който максималното разстояние (дължина на пътя) до други върхове е минимално.

пример:Центърът на орграфа е върхът д

		Ексцентрик-т

5. Алгоритъм за преминаване на орграфа в дълбочина (търсене в дълбочина):

При решаване на много задачи, свързани с насочени графи, е необходим ефективен метод за систематично обхождане на върхове и дъги на орграфи. Този метод е т.нар търсене в дълбочина - обобщение на метода за обхождане на дървото с предварителна поръчка. Търсенето в дълбочина започва с избиране на началния връх vброя G,този връх е маркиран с етикет посетени (посетен). След това за всеки връх, съседен на върха vи който не е бил посещаван преди, се прилага рекурсивно търсене в дълбочина. Когато всички върхове, които могат да бъдат достигнати от върха v, ще бъде "почетен" с посещение, търсенето приключва. Ако някои върхове не са били посетени, тогава се избира един от тях и търсенето се повтаря. Този процес продължава, докато не бъдат обходени всички върхове на орграфа г.

6. Алгоритъм за изграждане на дълбоко обхващащо дърво на графика:

При преминаване през графика, използвайки търсене в дълбочина, само определени дъги водят до непосетени върхове. Такива дъги, водещи до нови върхове, се наричат ​​дървесни дъги и форма за графа Първа в дълбочина обхващаща гора – дълбока гора ... При изграждането на гора се разграничават и три вида дъги: обратна, директна и напречна. Обратни дъги - такива дъги, които вървят от потомци към предци в обширната гора. Прави дъги се наричат ​​дъги, които преминават от предци към истински потомци, но които не са дъги на дървета.

Наричат ​​се дъги, свързващи върхове, които не са нито предци, нито потомци един на друг напречни дъги ... Ако при конструиране на обхващащо дърво синовете на един връх са разположени отляво надясно в реда на тяхното посещение и ако към гората се добавят и нови дървета отляво надясно, тогава всички напречни дъги вървят от дясно на ляво .

Например, дъги д-> C и G-> D- напречна, дъга ° С-> А- назад, няма прави дъги.

Когато преминавате дълбоко в дърво, често е удобно върховете да се номерират в реда, в който се посещават. Такива числа се наричат ​​числа на дълбочина.

Диграфно представяне:

§ Представяне на орграф с помощта на матрица на съседство:

Матрица на съседство за орграф G -това е матрица Аразмерът н нс булеви стойности, където А[ и, j] = вярноако и само ако има дъга от върха икъм връх j. Често в матриците на съседство стойността вярносе заменя с 1 и стойността фалшиво- до 0.

Обобщение на представянето на орграф с помощта на матрица на съседство може да се счита за представяне на маркиран орграф, също използвайки матрица на съседство, но за който елементът А[ и, j] равен на етикета на дъгата аз ->j. Ако дъги са отгоре идо горе jне съществува, тогава стойността A [ и, j] не може да бъде стойността на валиден етикет, но може да се счита за "празна" клетка.

Матрица на съседство за маркиран орграф (пример 2):

§ Представяне на орграф с помощта на списъци на съседство:

Списък на съседство на върхове инаречен списък на всички върхове, съседни на върха и, при това подредени по определен начин. Диграф гмогат да бъдат представени с помощта на масив ГЛАВА(Заглавие) чийто елемент ГЛАВА[и] е указател към списъка за съседство на върховете и.

Оператори на ATD "Orgraph":

Най-често срещаните оператори, изпълнявани върху насочени графи, включват четене на връх и етикет на дъга, вмъкване и изтриване на връх и дъга и обхождане на последователност на дъга.

За да видите набор от съседни върхове, са необходими следните три оператора.

1. ПЪРВО ( v) връща индекса на първия връх, съседен на върха v. Ако горната vняма съседни върхове, тогава се връща "нулев" връх нула.

2. СЛЕДВАЩ ( v, и) връща индекса на върха, съседен на върха v,следвайки индекса иАко аз -това е индексът на последния връх, съседен на върха v,след това се връща нула.

3. ВЪРХЪТ ( v,и) връща горната част с индекс иот множеството върхове, съседни на v.

Упражнения:

Дадена насочена графика (диграфа):

https://pandia.ru/text/78/308/images/image043_12.gif "width =" 125 "height =" 100 src = ">

Пример за несвързана графика:

Цикъл (прост) е път с (проста) дължина най-малко 3 от всеки връх до себе си. Графиката се нарича цикличен , ако има поне един цикъл. Свързан ацикличен граф, който е "дърво без корен", се нарича безплатно дърво . Втората фигура по-горе показва графика, състояща се от два свързани компонента, всеки от които е свободно дърво. Свободно дърво може да се направи "нормално" дърво, ако някой връх е обозначен като корен и всички ръбове са ориентирани в посоката от този корен.

Свободните дървета имат две важни свойства:

1. Всяко свободно дърво с броя на върховете н, н > 1 , има точно н - 1 ребра.

2. Ако добавите нов ръб към свободно дърво, определено ще получите цикъл.

Нека бъде г = (V, E) -свързан график, в който всяко ръбо ( r, w) маркирани с номер с(v, w),което се нарича цена на ребрата . Обхватно дърво броя гнаречено свободно дърво, съдържащо всички върхове Vграф Г. Цена обхващащото дърво се изчислява като сума от разходите за всички ръбове, включени в това дърво

Основни алгоритми за обработка на неориентирани графи:

1. Минимална цена за изграждане на дърво (алгоритъм на Prim):

Строят се много върхове Уот която "расте" опашното дърво. Нека бъде V = (1, 2, ...,н}. Първо U = (1).На всяка стъпка от алгоритъма се намира край на най-ниската цена ( u, v) такъв, че u Уи v V \ Uслед това отгоре vсе пренася от комплекта V \ Uв множество У... Този процес продължава до комплекта Уняма да е равно на множеството V.

Последователността на изграждане на обхващащо дърво е дадена по-долу.

https://pandia.ru/text/78/308/images/image048_12.gif "width =" 501 "height =" 384 src = ">

3. DFS обход на неориентирани графи:

Търсенето в дълбочина се използва за систематично преминаване на всички върхове на графа. Алгоритъмът за търсене в дълбочина е подобен на алгоритъма за преминаване през върховете на орграф. Последният се използва и за неориентирани графи, тъй като неориентираният ръб (v, w) може да се представи като двойка ориентирани дъги v -> wи w -> v.

Преминаването по дълбочина може да се използва за конструиране на обхващащо дърво.

Графиката и обхващащото дърво, получени чрез преминаване на неговите върхове с помощта на метода за търсене в дълбочина, са показани по-долу:

4. Търсене първо в ширина на неориентирани графи

Друг метод за систематично преминаване през върховете на граф се нарича Търсене на първо място в ширината . Той получи името си поради факта, че при достигане по време на обиколката на всеки връх vосвен това разглеждаме всички върхове, съседни на върха v, тоест върховете се сканират "по ширина". Тази техника може да се приложи и към насочени графики.

Както при търсенето в дълбочина, търсенето в широчина създава обхващаща гора при преминаване през графика. Ако след достигане на върха NSкогато гледаш реброто (x, y)връх вне е бил посещаван преди, тогава този ръб се счита за ръба на дървото. Ако горната ввече е посетено, реброто (x, y)ще бъде напречен ръб, тъй като свързва върхове, които не са свързани по наследство един с друг.

Обхватното дърво в ширина първо е показано по-долу.

Представяне на неориентирана графа с помощта на матрица на съседство:

За да представите ненасочени графи, можете да използвате същите методи като за представяне на насочени графи, ако ненасоченият ръб между върховете vи wразглежда като две ориентирани дъги от върха v къмвърха wи отгоре wдо горе v.

https://pandia.ru/text/78/308/images/image051_12.gif "width =" 159 "height =" 106 ">

Представяне на неориентирана графика с помощта на списъци на съседство:

https://pandia.ru/text/78/308/images/image053_12.gif "width =" 339 "height =" 115 src = ">

1. Изградете:

минимална цена обхващащо дърво с помощта на алгоритъма на Prim;

минимална цена обхващащо дърво с помощта на алгоритъма на Kruskal;

обхващащо дърво чрез търсене в дълбочина, започвайки от върхове a и d;

обхващащо дърво чрез търсене в широчина, като се започне от върхове a и d.

2. Реализирайте алгоритмите на Prim и Kruskal.

3. Реализирайте изграждането на обхващащо дърво, използвайки търсене в дълбочина

§ за неориентиран граф, представен от матрица на съседство,

§ за неориентиран граф, представен от списъци на съседство.

4. Реализирайте конструкцията на обхващащо дърво с помощта на търсене на първо място в ширината

§ за неориентиран граф, представен от матрица на съседство,

§ за неориентиран граф, представен от списъци на съседство.

Министерство на образованието и науката на Руската федерация

Федерална държавна бюджетна образователна институция

висше професионално образование

НАЦИОНАЛЕН ИЗСЛЕДОВАТЕЛСКИ ЯДРЕН УНИВЕРСИТЕТ "МЕФИ"

Димитровград Инженерно технологичен институт

отдел Информационни технологии

Да се ​​признае за защита "" 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.1 Абстрактни типове данни. Линейни списъци

Абстрактните типове данни са ключови понятия в програмирането. Абстракцията предполага разделяне и независимо разглеждане на интерфейса и реализацията.

Абстракцията на данни включва дефинирането и разглеждането на абстрактни типове данни (ADT) или, което е същото, нови типове данни, въведени от потребителя.

Абстрактният тип данни е колекция от данни заедно с много операции, които могат да бъдат извършени върху тези данни.

Линейни списъци

В линеен списък всеки елемент е свързан със следващия и евентуално предишния. В първия случай списъкът се нарича просто свързан, във втория - двойно свързан. Ако последният елемент е свързан с указател към първия, резултатът е кръгъл списък.

Всеки елемент в списъка съдържа ключ, който идентифицира този елемент. Ключът обикновено е или цяло число, или низ и е част от полето за данни. Различни части от полето с данни могат да действат като ключ в процеса на работа със списъка. Ключовете на различните елементи от списъка могат да бъдат еднакви.

Можете да извършвате следните операции върху списъци:

първоначално формиране на списъка (създаване на първия елемент);

добавяне на елемент в края на списъка;

четене на елемент с даден ключ;

вмъкване на елемент на дадено място в списъка (преди или след елемент с даден ключ);

изтриване на елемент с даден ключ;

подреждане на списъка по ключ.

За да работите със списък в програма, трябва да дефинирате указател към неговото начало. Можете също да задържите курсора на мишката в края на списъка, за да улесните добавянето на нови елементи в края на списъка.

1.2 Концепция за обектно-ориентирано програмиране

Според Грейди Буч, авторитет по методите за обектно-ориентирано програмиране, „обектно-ориентираното програмиране (ООП) е методология за програмиране, която се основава на представяне на програма като колекция от обекти, всеки от които е реализация на определен клас ( тип специален вид), а класовете образуват йерархия, основана на принципите на наследяване.

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

Обектно-ориентираната методология преследва същите цели като структурираната методология, но ги разглежда от различна отправна точка и в повечето случаи ви позволява да управлявате по-сложни проекти от структурираната методология.

Както знаете, един от принципите за управление на сложността на проекта е разлагането. Грейди Буч разграничава два вида декомпозиция: алгоритмична (както той нарича декомпозицията, поддържана от структурни методи) и обектно-ориентирана, разликата между които според него е следната: специално значение за факторите, или причиняващи действия, или са обекти на прилагането на тези действия”.

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

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

OO програмирането несъмнено е една от най-интересните области за професионална разработка на софтуер.

Обекти и класове

Основните градивни елементи на обектно-ориентирана програма са обекти и класове. По същество един обект може да бъде представен като нещо, което се усеща или представя и има добре дефинирано поведение. По този начин даден обект може да бъде видян или докоснат, или поне да се знае, че например е представен като информация, съхранявана в паметта на компютъра. Нека да дадем дефиницията на обект, придържайки се към мнението на GradiBuch: "Обектът е осезаем обект, който ясно проявява своето поведение."

Обектът е част от реалността, която ни заобикаля, тоест съществува във времето и пространството (за първи път понятието обект в програмирането е въведено в езика Simula). Формално обектът е труден за дефиниране. Това може да стане чрез някои свойства, а именно: обектът има състояние, поведение и може да бъде еднозначно идентифициран (с други думи, има уникално име).

Класът е набор от обекти, които споделят обща структура и общо поведение. Класът е описание (абстракция), което показва как да се конструира променлива от този клас, която съществува във времето и пространството, наречена обект. Значението на изреченията "описание на променливите на класа" и "описание на обекти от клас" е едно и също.

Обектът има състояние, поведение и паспорт (средства за уникалната му идентификация); структурата и поведението на обектите са описани в класовете, чиито те са променливи.

Нека сега дефинираме понятията състояние, поведение и идентификация на обект.

Състоянието на обект комбинира всички негови полета с данни (статичен компонент, т.е. непроменен) и текущите стойности на всяко от тези полета (динамичен компонент, т.е. обикновено се променя).

Поведението изразява динамиката на промените в състоянията на обекта и неговата реакция на входящи съобщения, т.е. как един обект променя състоянието си и взаимодейства с други обекти.

Идентификацията (разпознаването) на обект е свойство, което ви позволява да различавате обект от други обекти от същия или различни класове. Идентификацията се извършва чрез уникално име (паспорт), което се присвоява на обекта в програмата, както всяка друга променлива.

Вече беше казано по-горе, че процедурният (както и модулният) подход позволява да се изграждат програми, състоящи се от набор от процедури (подпрограми), които реализират дадените алгоритми. От друга страна, обектно-ориентираният подход представя програмите като колекция от обекти, които взаимодействат един с друг. Взаимодействието на обектите се осъществява чрез съобщения. Да приемем, че нашият обект е кръг. Тогава съобщението, изпратено до този обект, може да бъде: „нарисувай себе си“. Когато казваме, че съобщение се предава на обект, тогава всъщност ние извикваме някаква функция на този обект (компонентна функция). И така, в горния пример ще извикаме функция, която ще начертае кръг на екрана на дисплея.

Капсулиране

Капсулирането е един от основните принципи на обектно-ориентираното програмиране, чиято идея е, че всички свойства и методи се комбинират в един обект.

Самото име на термина "капсулиране" идва от английската дума encapsulate, която буквално означава "запечатвам в капсула" или "покривам с обвивка". По този начин един обект (капсула) съдържа методи и свойства (съдържание).

Капсулирането може да се разглежда в по-широк смисъл, далеч отвъд обектно-ориентираното програмиране като цяло. Ако говорим за капсулиране на възможно най-високо ниво на абстракция, тогава капсулирането може да се разглежда като способност на обект да съдържа различни други обекти. Така че по отношение на една компютърна програма можем да кажем, че тя капсулира няколко модула, всеки от които от своя страна капсулира някои обекти, които капсулират методи и свойства, които, между другото, също могат да бъдат обекти и т.н.

Въз основа на всичко по-горе, друго представяне на капсулирането може да бъде всяка структура на дърво, в която всеки възел на дървото капсулира всички негови непосредствени деца, които могат да бъдат или листа (примитиви, които не могат да капсулират нищо в себе си) или други възли.

И все пак, ако говорим за обектно-ориентирано програмиране, тогава капсулирането е обединението на данни и методи в рамките на обект.

Понякога, говорейки за капсулиране в обектно-ориентирано програмиране, концепцията за капсулиране се приравнява с концепцията за "черна кутия" или скриване на данни, но те не са едно и също нещо. Да, в някои обектно-ориентирани езици за програмиране, използвайки капсулиране, разработчикът може да направи своя обект черна кутия, но това се реализира с помощта на модификатори за достъп, които не са налични във всички обектно-ориентирани езици за програмиране. Самата концепция за капсулиране е много по-широка. И дори повече от това, можем да направим всички свойства и методи достъпни отвън, тоест не може да става дума за никаква черна кутия, но капсулирането все още ще присъства във всеки обект. Следователно скриването на данни чрез модификатори за достъп е следствие от капсулирането, но по никакъв начин не са идентично равни понятия.

Първо, благодарение на капсулирането, обектите вече не са просто потребителски дефинирани структури от данни, чиято основна цел е просто да бъдат логично комбинирани няколко отделни типа данни в рамките на нов съставен тип данни. Благодарение на капсулирането всеки обект вече може да съдържа данни, описващи състоянието на обекта и неговото поведение, описано под формата на методи. С други думи, обектът в обектно-ориентираното програмиране е престанал да бъде примитивен пасивен тип данни, чийто контрол е изцяло на милостта на външната среда, а е започнал да има собствено поведение, може дори да се каже някаква воля и ум, способността да реагират активно на външни влияния и да променят състоянието си и според собствените си закони и разпоредби.

Второ, капсулирането ни дава възможност да контролираме достъпа до обектни данни. Ограничението на видимостта може да се разглежда и като проява на собствената воля на обекта - обектът сам решава какво от своето поведение или свойства да направи достъпно за всички, какво да направи достъпно само за определен кръг от обекти и какво да направи напълно интимно, за което няма да знае друг обект. Защо, а защото само самият обект знае как точно да работи с него и как не. Можете дори да кажете за нова философия на програмирането, където обектите са повече върху обекти, над които се извършват някои действия, и, ако мога така да кажа, нова форма на абстрактен синтетичен ум, взаимодействайки с който можете да постигнете желания резултат.

И пак повтарям, че благодарение на капсулирането един обект може да бъде надарен с някаква воля, разум, способност да реагира на външни влияния, а не да бъде пасивно хранилище на данни.

Наследство

Наследяването е един от четирите най-важни механизма на обектно-ориентирано програмиране (заедно с капсулиране, полиморфизъм и абстракция), който ви позволява да опишете нов клас въз основа на съществуващ (родителски) клас, докато свойствата и функционалността на родителския клас са заети от новия клас.

С други думи, наследяващият клас изпълнява спецификацията на вече съществуващ клас (базов клас). Това ви позволява да третирате обектите от наследения клас по същия начин, както и обектите от базовия клас.

Видове наследяване

Просто наследяване

Класът, от който произлиза наследяването, се нарича базов или родител (на английски baseclass). Класовете, които произлизат от основата, се наричат ​​низходящи, низходящи или производни класове.

Някои езици използват абстрактни класове. Абстрактен клас е клас, който съдържа поне един абстрактен метод, описан е в програмата, има полета, методи и не може да се използва за директно създаване на обект. Тоест можете да наследите само от абстрактен клас. Обектите се създават само на базата на производни класове, наследени от абстрактното.

Например, абстрактен клас може да бъде базов клас "университетски служител", от който се наследяват класовете "аспирант", "професор" и т. н. Тъй като производните класове имат общи полета и функции (например полето "година на раждане"), тези членове на класа могат да бъдат описани в основния клас. Програмата създава обекти на базата на класовете "аспирант", "професор", но няма смисъл да създава обект на базата на класа "университетски служител".

Множествено наследяване

При множествено наследяване един клас може да има повече от един предшественик. В този случай класът наследява методите на всички предшественици. Предимството на този подход е по-голямата гъвкавост. Множественото наследяване е реализирано в C ++. Други езици, които предоставят тази възможност, включват Python и Eiffel. Множественото наследяване се поддържа в UML.

Множественото наследяване е потенциален източник на грешки, които могат да възникнат поради наличието на същите имена на методи в предците. В езици, които са позиционирани като наследници на C ++ (Java, C # и др.), беше решено да се изостави множественото наследяване в полза на интерфейсите. Почти винаги можете да правите без да използвате този механизъм. Въпреки това, ако все пак възникне такава необходимост, тогава за разрешаване на конфликти при използване на наследени методи със същите имена е възможно, например, да се приложи операцията за разширение на видимостта - "::" - за извикване на конкретен метод на конкретен родител.

Направен е опит да се реши проблемът с наличието на същите имена на методи в предците на езика Eiffel, при който при описание на нов клас е необходимо изрично да се посочат импортираните членове на всеки от наследените класове и тяхното именуване в детския клас.

Повечето съвременни обектно-ориентирани езици за програмиране (C#, C++, Java, Delphi и т.н.) поддържат възможността едновременно да наследяват от предшественик клас и да прилагат методи на няколко интерфейса с един и същи клас. Този механизъм ви позволява до голяма степен да замените множеството наследяване - методите на интерфейса трябва да бъдат изрично отменени, което елиминира грешките при наследяване на функционалността на едни и същи методи от различни класове предшественици.

1. Практическа част

За решаването на този проблем се използва обектно-ориентирана програмна структура. Програмата е представена от два класа и основен 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 - Налични команди

Пълният код на менюто е показан в Приложение А.

1. Тестване

Често в процеса на работа възникват ситуации, свързани с неправилно въвеждане на данни, което може да доведе до неуспех на програмата. Разбира се, всяка програма трябва да прилага алгоритми за защита от неопитен потребител, предотвратявайки срива на програмата. Нека разгледаме как функционират такива алгоритми в създадената програма.

Първоначалното въвеждане на списъка се извършва със следния код:

if (atoi (ss)! = NULL)

mylist.Add (atoi (ss));

Преди да извикате метода add, за да добавите нов елемент към списъка, входният низ се проверява. Функцията atoi преобразува низ в числова стойност и връща NULL, ако входният низ не е число. По този начин при въвеждане всички редове, които не са числа, ще бъдат игнорирани, с изключение на реда с командата за спиране на въвеждането (вижте Фигура 10).

Фигура 10 - Въвеждане на неверни данни

След въвеждане на тези данни списъкът ще изглежда така (вижте фигура 11).

Фигура 11 - Получен списък

Програмата продължава да работи коректно след, дори след въвеждане на грешни данни. Подобни методи за работа с неверни данни се използват за останалите операции за въвеждане, присъстващи в програмата.

Заключение

В тази работа бяха получени понятия за абстрактните типове данни, за принципите на тяхното представяне в съвременните езици за програмиране, в частност в C ++. В повечето съвременни императивни езици основната концепция, използвана за описание на абстракциите в програмния код, е обектно-ориентираният подход. Обектно-ориентираното програмиране (ООП), подобно на базирания на 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" Специално издание или 3-то издание. Бином, Невски диалект, 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");

coutcoutcoutcoutcoutcoutcoutcom_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 абстрактномодели за информационна сигурност ... управляващи взаимодействията и с двете видове данни(Правила за сертифициране): Всички ... различни вариации и допълнения към съществуващите Списъкът... Нива на сигурност - определени...

Абстрактен тип данни

Абстрактен тип данни (ATD)е тип данни, който предоставя определен набор от функции за работа с елементи от този тип, както и възможността за създаване на елементи от този тип с помощта на специални функции. Цялата вътрешна структура от този тип е скрита от разработчика на софтуер - това е същността на абстракцията. Абстрактен тип данни дефинира набор от независими от реализацията функции на типа, за да оперират върху неговите стойности. Специфичните реализации на ADT се наричат ​​структури от данни.

В програмирането абстрактните типове данни обикновено се представят като интерфейси, които крият реализациите на съответния тип. Програмистите работят с абстрактни типове данни изключително чрез своите интерфейси, тъй като реализацията може да се промени в бъдеще. Този подход е в съответствие с принципа на капсулиране в обектно-ориентираното програмиране. Силната страна на тази техника е скриването на изпълнението. След като само интерфейсът е публикуван извън, тогава докато структурата на данните поддържа този интерфейс, всички програми, работещи с дадена структура на абстрактния тип данни, ще продължат да работят. Разработчиците на структури от данни се опитват, без да променят външния интерфейс и семантиката на функциите, постепенно да прецизират реализациите, подобрявайки алгоритмите по отношение на скорост, надеждност и използвана памет.

Разликата между абстрактни типове данни и структури от данни, които реализират абстрактни типове, може да се илюстрира със следния пример. Списъкът с абстрактни типове данни може да бъде реализиран с помощта на масив или линеен списък, като се използват различни методи за динамично разпределение на паметта. Въпреки това, всяка реализация дефинира един и същ набор от функции, които трябва да работят еднакво (по производителност, а не по скорост) за всички реализации.

Абстрактните типове данни ви позволяват да постигнете модулност на софтуерните продукти и да имате няколко алтернативни взаимозаменяеми реализации на отделен модул.

Примери за ADT

Вижте също

Връзки

• Лапшин В.А. Абстрактни типове данни в програмирането

Фондация Уикимедия. 2010 г.

Вижте какво е "Абстрактен тип данни" в други речници:

абстрактен тип данни- Тип данни (абстрактен клас), дефиниран чрез изброяване на неговите методи и свойства, без да се създава тяхната конкретна реализация. Теми на информационните технологии като цяло EN Abstract Data TypeADT ... Ръководство за технически преводач

В теорията на програмирането всеки тип, чиито стойности са стойности от някои други типове, "увита" от конструктори от алгебричен тип. С други думи, алгебричният тип данни има набор от конструктори на типове, всеки от които ... ... Wikipedia

Цело число, целочислен тип данни (англ. Integer), в компютърните науки един от най-простите и разпространени типове данни в езиците за програмиране. Служи за представяне на цели числа. Много числа от този тип представляват ... ... Уикипедия

Този термин има други значения, вижте набор (значения). Набор, тип и структура от данни в компютърните науки, е реализация на набор от математически обекти. Наборът от тип данни ви позволява да съхранявате ограничен брой стойности ... ... Уикипедия

Някои езици за програмиране предоставят специален тип данни за комплексни числа. Вграденият тип улеснява съхраняването и изчисляването на сложни стойности. Съдържание 1 Аритметика над комплекс 2 Поддръжка на езици ... Wikipedia

Този термин има други значения, вижте Индекса. Диаграма на показалец Указател (указател) е променлива, чийто диапазон от стойности се състои от адреси на паметта и специална стойност на нулевия адрес. ... ... Уикипедия.

Един от видовете алгебрични типове данни, който се характеризира с факта, че неговите конструктори могат да връщат стойности, които не са от техния собствен тип. Тази концепция е реализирана в няколко езика за програмиране, по-специално в езиците ML и Haskell, и в ... ... Wikipedia

Черта е абстрактен тип, използван в компютърните науки като „прост концептуален модел за структуриране на обектно-ориентирани програми“. Чертите са подобни на миксините, но могат да включват дефиниции на метод на клас. ... ... Wikipedia

Двоично дърво, прост пример за разклонена свързана структура от данни. Структурата на данните е програмна единица, която позволява съхраняване на ... Wikipedia

- (горен тип) в теорията на типовете, често обозначаван като само връх или "фиксиран" символ (⊤), универсален тип, тоест тип, който съдържа всеки възможен обект в желаната система от типове. Най-високият тип понякога се нарича ... ... Wikipedia