Презентація на тему: "Рекурсивні структури даних"

Рекурсивні структури даних. Реалізація з допомогою об’єктно-орієнтованого програмування в середовищі Python

Статичні та динамічні структури даних. Типи даних можна поділити на статичні та динамічні з точки зору використання пам’яті комп’ютера. Пам’ять для статичних структур даних виділяється один раз перед (або під час) виконанням програми, а її обсяг не може бути змінений. Прикладом таких статичних типів у Python є, зокрема, дійсний тип даних. Динамічні структури даних можуть змінювати обсяг виділеної для них пам’яті у процесі виконання програми. Прикладами динамічних структур даних у Python є списки та словники.

Статичні та динамічні структури данихІснує багато задач, в яких розмір даних суттєво залежить від умов, які обчислюються тільки під час виконання програм. Для таких задач необхідно мати саме динамічні структури даних. Реалізація динамічних структур даних залежить від мови програмування: динамічні структури даних можуть бути вбудовані у мову програмування або можуть бути надані засоби побудов таких структур. Найпоширенішим засобом побудови є вказівники.

Рекурсивні структури даних. Серед динамічних структур даних окремо виділяють рекурсивні структури. Аналогічно рекурсивним підпрограмам, рекурсивні структури даних у своєму описі посилаються самі на себе. Взагалі поняття динамічних структур даних є більш широким, ніж поняття рекурсивних структур даних, але в цій темі ми будемо розглядати саме рекурсивні структури даних, їх визначення, реалізацію та використання.

Рекурсивні структури данихІснує цілий ряд стандартних рекурсивних структур даних: стеки, черги, деки, різноманітні списки, дерева, графи. У Python для реалізації рекурсивних структур даних використовують як вбудовані структури (списки, словники), так і аналог вказівників – посилання на об’єкти. Для багатьох структур даних найпростішою є реалізація на базі списків Python, які самі є рекурсивною структурою даних. Спільним для реалізації всіх рекурсивних структур даних буде використання розглянутих раніше класів та об’єктів. Для рекурсивної структури даних визначаються свої операції відношення та інструкції. Тому ми можемо вважати, що кожна рекурсивна структура даних є новим типом даних.

СТЕКИ

Стек. Першою та найбільш простою з рекурсивних структур даних є стек. Визначимо стек як:1). Порожній стек.2). Верхівка стеку; стек. Читати це означення треба так: стек – це або порожній стек, або верхівка стеку, за якою слідує стек.

Стек(stack)Стек можна також представити, як сукупність однотипних елементів, в якій ми маємо доступ тільки до верхнього елемента. Цей елемент називають верхівкою стеку. Стеки називають ще структурами LIFO(Last In-First Out або Останнім прийшов –першим вийшов) або магазинами через схожість з магазинами стрілецької зброї.

Операції, відношення та інструкції для стеків. Операції, відношення та інструкції для стеків:1. Почати роботу.2. Чи порожній стек?3. Вштовхнути елемент у стек.4. Виштовхнути верхівку стеку. Дії 1, 3, 4 –інструкції; 2 –відношення.“Почати роботу” означає створити порожній стек.«Чи порожній стек?» -перевірити, чи є стек порожнім.“Вштовхнути елемент у стек” –додати до стеку один елемент, який стає верхівкою стеку.“Виштовхнути верхівку стеку” –повернути та видалити верхній елемент. Верхнім стає попередній елемент стеку або стек стає порожнім. Для порожнього стеку ця інструкція повинна давати помилку.

Реалізація стеку# Для реалізації стеку використаємо списокclass Stack: def __init__(self): self._lst = [] def isempty(self): return len(self._lst)==0 def push(self, data): self._lst.append(data) def pop(self): if self.isempty(): print('Рop: Стек порожній') exit(1) data = self._lst.pop() return data

Реалізація стеку. Клас Stack має одне внутрішнє поле _lst – список, який містить елементи стеку, та методи, що реалізують дії над стеком. Ми бачимо, що реалізація стеку на базі списку є дуже простою. Звернемо увагу на реалізацію повідомлення про помилку, якщо ми намагаємось взяти елемент з порожнього стеку: Функція exit(1) аварійно завершує роботу програми у Python.if self.isempty(): print('Рop: Стек порожній') exit(1)

Приклад 1 Дано послідовність рядків, яка вводиться з клавіатури. Показати цю послідовність у оберненому порядку. Код програми див. додаток 1 Результат: Слайд 57

Черги

Черга(queue)Черга – ще одна рекурсивна структура даних, яку можна визначити так:1). Порожня черга.2). Перший елемент; черга. Чергу можна представити, як сукупність однотипних елементів, в якій ми маємо доступ до кінця черги при додаванні елементів та до початку черги при взятті елементів.

Реалізація черги. 1 Для реалізаії черги використаємо список. Опишемо клас Queue(англійською - черга) наступним чиномclass Queue: def __init__ (self): # Створити порожню чергу self._lst = [] #список елементів черги def isempty(self): # Чи порожня черга ? return len(self._lst) == 0 def add(self, data): # додати елемент в кінець черги self._lst.append(data)

Реалізація черги. 2 def take(self): # взяти елемент з початку черги if self.isempty(): print(‘Таkе: Черга порожня') exit(1) data=self._lst.pop(0) return data def __del__(self): # закінчити роботу з чергою print('Deleting gueue') del self._lst

Реалізація черги.3 Реалізація черги на базі списку настільки ж нескладна, як і реалізація стеку. Звернемо увагу на метод __del__. Він є внутрішнім методом Python та викликається тоді, коли об’єкт класу Queue знищується. Такі методи називають деструкторами. Часто у деструкторах можна не писати код. Ми його написали з метою демонстрації а також з метою вивільнення пам’яті, раніше виділеної під список _lst.

Приклад 2. Задача «Лічилка»По колу розташовано n гравців з номерами від 1 до n. У лічилці m слів. Починають лічити з першого гравця. m-й за ліком вибуває. Потім знову лічать з наступного гравця за вибулим. Знову m-й вибуває. Так продовжують, поки не залишиться жодного гравця. Треба показати послідовність номерів, що вибувають, при заданих n та m. Для розв’язання задачі використаємо чергу. Опишемо клас Player(Гравець), який містить методи __init__ -створити гравця – та show – показати номер гравця. Спочатку до черги додамо n гравців з номерами від 1 до n. Потім будемо (m-1) раз перекладати гравця з початку до кінця черги (брати спочатку да додавати до кінця), імітуючи лік. m-го гравця візьмемо спочатку черги та покажемо його номер. Будемо повторювати лік, поки черга не спорожніє.

Код програми див. додаток 2 Результат: Слайд 58

ДЕКИ

Дек. Дек називають двостороннім стеком або двосторонньою чергою. Визначимо дек:1) Порожній дек.2) Перший елемент; дек.3) Дек; останній елемент. Дек можна представити, як сукупність однотипних елементів, в якій ми маємо доступ до початку або кінця деку для додавання або взяття елементів.

Операції, відношення та інструкції для деків1. Почати роботу.2. Чи порожній дек?3. Додати елемент до початку деку.4. Взяти елемент з початку деку.5. Додати елемент до кінця деку.6. Взяти елемент з кінця деку. Дії 1, 3, 4, 5, 6 –інструкції; 2 –відношення.“Почати роботу” означає створити порожній дек.“Додати елемент до початку деку” –додати до деку один елемент, який стає першим у деку.“Взяти елемент з початку деку” –взяти та повернути значення першого елемента. Першим стає наступний елемент деку або дек стає порожнім. Для порожнього деку ця інструкція повинна давати відмову.“Додати елемент до кінця деку” –додати до деку один елемент, який стає останнім у деку.“Взяти елемент з кінця деку” –взяти та повернути значення останнього елемента. Першим стає попередній елемент деку або дек стає порожнім. Для порожнього деку ця інструкція повинна давати відмову.

Реалізація деку. 1 Для реалізації деку використаємо посилання на об’єкти. При створенні об’єкту Python динамічно виділяє нову пам’ять, а сама змінна є посиланням на початкову адресу виділеного блоку пам’яті. Тому ми можемо зв’язати між собою елементи деку за допомогою посилань на об’єкти а також визначити клас для деку в цілому.

Реалізація деку.2 Опишемо класи _Delem та Deque. Клас _Delem є є внутрішнім класом модуля та реалізує елемент деку з даними та посиланнями на попередній та наступний елементи( _prev та _next). Клас Deque реалізує сам дек як сукупність елементів з визначеними посиланнями. Можемо вважати, що елементи деку зв’язані у ланцюг двома посиланнями: на попередній та наступний елемент. А сам дек містить посилання на перший та останній елементи деку.

Реалізація деку. Клас_Delemclass _Delem: # Реалізує елемент деку def __init__(self, data): # створити елемент деку self.data = data # дані, що зберігаються в елементі стеку self._next = None # посилання на наступний елемент self._prev = None # посилання на попередній елемент

Реалізація деку. Клас Dequeclass Deque: # реалізує дек без використання списку def __init__ (self): # створити порожній дек self._bg = None self._en = None def isempty(self): # чи порожній дек ? return self._bg == None and self._en == None

Реалізація деку. Клас Deque.2def pubg(self, data): # додати елемент до початку деку elem = Delem(data) # створюємо новий елемент деку elem._next = self._bg # наступний елемент для нового - це # елемент, який є першим if not self.isempty(): # якщо додаємо до непорожнього деку self._bg._prev = elem # новий елемент стає попереднім для # першого else: self._en = elem # якщо додаємо до порожнього деку, # новий елемент буде й останнім self._bg = elem # новий елемент стає першим у деку

Реалізація деку. Клас Deque.3def getbg(self): # взяти елемент з початку деку if self.isempty(): print('getbg: Дек порожній') exit(1) elem = self._bg # elem - посилання на перший елемент деку data = elem._data # запам'ятовуємо дані для повернення self._bg = elem._next # першим стає наступний елемент деку if self._bg == None: # якщо в деку був 1 елемент self._en = None # дек стає порожнім else: self._bg._prev = None # інакше у новому першому елементі # посилання на попередній - None del elem return data

Реалізація деку. Клас Deque.4def puten(self, data): # додати елемент до кінця деку elem = Delem(data) elem._prev = self._en if not self.isempty(): self._en._next = elem else: self._bg = elem self._en = elem def geten(self): # взяти елемент з кінця деку if self.isempty(): print('geten: дек порожній’); exit(1) elem = self._en data = elem._data self._en = elem._prev if self._en == None: self._bg = None else: self._en._next = None del elem return data

Реалізація деку. Клас Deque.5def __del__(self): # закінчити роботу з деком while self.bg != None: # проходимо по всіх елементах деку elem = self._bg # запам'ятовуємо посилання на елемент self._bg = self._bg._next # переходимо до наступного елементу del elem # видаляємо елемент self._en = None

Реалізація деку. Завершення. Слід відмітити, що дії додавання елемента до кінця деку та взяття елемента з кінця деку (puten та geten) повністю симетричні діям додавання елемента до початку деку та взяття елемента з початку деку (putbg та getbg). Їх навіть можна отримати формально, паралельно замінивши всюди у тексті putbg та getbg bg на en, en на bg, next на prev та prev на next. Деструктор __del__ для Deque не просто демонстраційним, але й корисний тим, що звільняє пам’ять, виділену не тільки під об’єкт дек, але й під всі його елементи.

Приклад. Задача «Лічилка» з використанням деку. По колу розташовано n гравців з номерами від 1 до n. У лічилці m слів. Починають лічити з першого гравця. m-й за ліком вибуває. Потім знову лічать з наступного гравця за вибулим. Знову m-й вибуває. Так продовжують, поки не залишиться жодного гравця. Треба показати послідовність номерів, що вибувають, при заданих n та m. Розв’язок цієї задачі з використанням деків практично не відрізняється від раніше розглянутого розв’язку з використанням черг. Ми тільки використовуємо відповідні методи для деку замість методів для черги.

Код програми розміщено в додатку 3 Результат: Слайд 60

СПИСКИ

Списки. Списки також є рекурсивними структурами даних. Списки відрізняються від стеків, черг та деків тим, що ми можемо багато разів проходити вздовж списку, отримувати доступ до будь-якого елемента, не змінюючи сам список. Список можна визначити так:1) Порожній список.2) Перший елемент; список.Є декілька різновидів списків: однозв’язні списки, кільцеві списки, двозв’язні списки. Для кожного з цих різновидів списків визначається свій набір операцій, відношень та інструкцій. У Python списки є стандартною структурою даних. Реалізація списків у Python є специфічною, оскільки ми можемо отримати прямий доступ до довільного елемента списку. Списки у Python ближчі до двозв’язних списків. Розглянемо натомість один з різновидів списків, який не реалізований у Python: кільцевий список.

Кільцевий список. Кільцевий список відрізняється від звичайного списку тим, що для кільцевого списку не визначають перший та останній елемент. Всі елементи зв’язані у кільце та відомий лише порядок слідування, а також елемент, який є поточним. Визначимо кільцевий список:1). Порожній список.2). Список; поточний елемент; список.

Набір дій над кільцевими списками1. Почати роботу.2. Довжина списку.3. Перейти до наступного елемента.4. Повернути поточний елемент.5. Оновити поточний елемент.6. Вставити елемент.7. Видалити елемент. Дії 1, 3, 5, 6, 7 –інструкції; 2, 4 -операції.Інструкція “Почати роботу” повертає порожній список. Операція “ Довжина списку” повертає кількість елементів у списку.“Перейти до наступного елемента” –зробити поточним наступний елемент списку. Якщо список порожній, то нічого не робити.“Повернути поточний елемент” повертає значення поточного елемента. Список при цьому не зміню ється. Якщо список порожній, ця операція повинна давати відмову.“Оновити поточний елемент” змінює значення поточного елемента. Якщо список порожній, ця операція повинна давати відмову.“Вставити елемент” –вставити новий елемент у список перед поточним.“Видалити елемент” –видалити поточний елемент. Поточним стає наступний елемент або список стає порожнім. Якщо список порожній, інструкція повинна давати відмову.

Реалізація кільцевого списку. 1 Для реалізації кільцевого списку використаємо список Python, у якому будем зберігати елементи кільцевого списку. Опишемо клас Rlist, який містить поля _lst – список елементів – та _cur – індекс поточного елемента. Цей клас також містить методи, що реалізують дії над кільцевим списком.

Реалізація кільцевого списку. 2class Rlist: def __init__(self): self._lst=[] # список елементів self._cur=None # індекс поточного елемента def len(self): # довжина списку return len(self._lst) def next(self) # Перейти до наступного елемента. l=self.len() if l != 0: if self._cur == l-1: self._cur=0 else: self._cur +=1

Реалізація кільцевого списку.3 def getcurrent(self): # Повернути поточний елемент. if self.len()==0: print('getcurrent: список порожній') exit(1) data=self._lst[self._cur] return data def update(self, data): # Оновити поточний елемент. if self.len()==0: print('update: список порожній') exit(1) self._lst[self._cur]=data

Реалізація кільцевого списку.4 def insert(self, data): # Вставити елемент перед поточним. if self.len()==0: self._lst.append(data) self._cur=0 else: self._lst.insert(self._cur, data) self._cur += 1 def delete(self): # Видалити поточний елемент. if self.len() == 0: print('delete: список порожній') exit(1) l=self.len()

Реалізація кільцевого списку.5 del self._lst[self._cur] if l==1: self._cur=None elif self._cur==l-1: self._cur=0 else: pass # Закінчити роботу зі списком. def __del__(self): del self._lst

Приклад 4. Гра у відгадування слів. Реалізувати гру у відгадування слів, яка полягає у наступному. • По колу розташовані гравці (відгадувачі), яким презентують слово для відгадування. • Всі літери цього слова спочатку закриті (замінені зірочками, ‘*’). • Гравці вступають у гру по порядку. Кожен гравець може назвати літеру або слово. • Якщо гравець називає літеру, а цієї літери, у слові немає, - хід переходить до наступного гравця. Якщо ж така літера у слові є, то всі входження цієї літери у слово відкриваються, а гравцю нараховуються стільки балів, скільки є входжень названої літери у слово. Якщо всі літери слова відкриті, - гравець стає переможцем.• Якщо гравець називає слово і це слово не дорівнює заданому, то всі бали гравця анулюються, а хід переходить до наступного гравця. Якщо ж слово названо правильно, - гравець отримує стільки балів, скільки є у слові невідгаданих літер, та стає переможцем.• Переможець отримує премію: стільки балів, скільки літер було у слові.

Приклад 4. Гра у відгадування слів. Розв’язання• Для реалізації гри використаємо кільцевий список гравців (відгадувачів). • Опишемо клас Guesser(Відгадувач), у якому будемо зберігати ім’я гравця та кількість зароблених балів.• Слово будемо вибирати з текстового файлу наступним чином: знайдемо випадкове місце у файлі. Починаючи з цього місця, прочитаємо 10 рядків файлу, видалимо з них символи-розділювачі, переведемо до нижнього регістру та побудуємо список слів. З цього списку виберемо випадкове слово для відгадування. • Побудуємо також рядок, який буде містити закриті та вгадані літери вибраного слова (спочатку –всі зірочки).• Далі гравці будуть називати літери або слова а програма буде аналізувати відповіді та слідувати правилам гри до моменту, поки не буде відгадано задане слово.42

Код програми в додатку 4 Результат: Слайд 62

Бінарні дерева

Бінарні дерева. Бінарним деревом називається дерево з напівстепінню виходу всіх вершин не більше 2. Впорядкованим бінарним деревом називається бінарне дерево, кожна вершина якого завжди має 2 сини: лівий син та правий син, які можуть бути порожніми або непорожніми деревами. Далі будемо розглядати тільки впорядковані бінарні дерева.

Операції, відношення та інструкції для бінарних дерев. Бінарні дерева використовують для пошуку та сортування даних, для представлення інформації, обчислення виразів тощо. Визначимо операції, відношення та інструкції для бінарних дерев:1) Почати роботу.2) Чи порожнє дерево?3) Створити дерево.4) Корінь дерева.5) Лівий син.6) Правий син.7) Змінити корінь дерева.8) Змінити лівого сина.9) Змінити правого сина. Дії 1, 3, 4, 5, 6 –операції; 2 –відношення, 7, 8, 9 -інструкції.

Операції, відношення та інструкції для бінарних дерев.2“Почати роботу” повертає порожнє дерево.“Створити дерево” –за двома деревами t1, t2 та даними data створити бінарне дерево з коренем з навантаженням data, лівим сином t1 та правим сином t2.“Корінь дерева” повертає навантаження кореня дерева. Дерево при цьому не змінюється. Для порожнього дерева ця операція повинна давати відмову.“Лівий син” повертає піддерево, яке є лівим сином дерева. Лівий син порожнього дерева за означенням –порожнє дерево.“Правий син” повертає піддерево, яке є правим сином дерева. Правий син порожнього дерева за означенням –порожнє дерево.“Змінити корінь дерева” –змінити навантаження кореня дерева значенням data. Якщо дерево порожнє, то після цієї інструкції дерево стає таким, що містить одну вершину.“Змінити лівого сина” –змінити значення лівого сина дерева значенням t.“Змінити правого сина”-змінити значення правого сина дерева значенням t.

Реалізація бінарного дерева. 1 Бінарні дерева будемо реалізовувати за допомогою посилань на об’єкти. Опишемо клас Btree. Згідно з описом, бінарне дерево – це об’єкт з полями, що містять навантаження кореня (_data), лівого сина (_ls) та правого сина (_rs). Поля _ls та _rs є об’єктами класу Btree. Клас Btree також містить методи, що реалізують описані раніше дії над деревами. Бінарні дерева будемо реалізовувати за допомогою посилань на об’єкти.

Реалізація бінарного дереваclass Btree: # реалізує бінарне дерево def __init__(self): # створити порожнє дерево self._data= None # навантаження кореня дерева self._ls = None # лівий син self._rs = None # правий син def isempty(self): # чи порожнє дерево ? return self._data == None and self._ls == None and self._rs == None def maketree(self, data, t1, t2): # створити дерево self._data = data # дані у корені - data self._ls = t1 # лівий син - t1 self._rs = t2 # правий син - t2

Реалізація бінарного дерева.3 def root(self): # корінь дерева if self.isempty(): print('root: дерево порожнє') exit(1) return self._data def leftson(self): # лівий син if self.isempty(): t = self else: t = self._ls return t def rightson(self): # правий син if self.isempty(): t = self else: t = self._rs return t

Реалізація бінарного дерева.4 def updateroot(self, data): # змінити корінь значенням дата if self.isempty(): # якщо дерево порожнє, # додати лівого та правого сина self._ls = Btree() self._rs = Btree() self._data = data def updateleft(self, t): # змінити лівого сина значенням t self._ls = t def updateright(self, t): # змінити правого сина значенням t self._rs = t

Приклад 5. Бінарне дерево пошуку• Бінарним деревом пошуку називається таке бінарне дерево, у якому навантаження кореня більше навантаження будь-якої вершини, що належить лівому сину, та менше навантаження будь-якої вершини, що належить правому сину. • Побудувати бінарне дерево пошуку за списком рядків та перевірити, чи входять у дерево задані рядки.• Програма, що розв’язує цю задачу, містить функції побудови списку слів, побудови дерева пошуку за списком слів, пошуку у дереві. • Побудова дерева пошуку та пошук у дереві використовують одну внутрішню функцію, яка шукає місце, куди можна вставити нове слово w, а також перевіряє, чи є w у дереві.

Код програми розміщено в додатку 5 Результат: Слайд 69

Слайд 12

Слайд 20

Слайд 34

Слайд 46

Слайд 56