Понятие абстрактного типа данных

Дисциплина «Алгоритмы и структуры данных» Лекция № 5 Понятие абстрактного типа данных. Филатов Вячеслав Валерьевич к.т.н., доцент кафедры КБ-2 «Прикладные информационные технологии» Литература • Структуры данных и алгоритмы. Альфред В. Ахо, Джон Э. Хопкрофт, Джеффри Д. Ульман. – М.: Издательский дом «Вильямс», 2016 • Алгоритмы: построение и анализ. Т. Кормен, Ч. Лейзерсон, Р. Ривест. – М.: МЦНМО, 2017. • Д. Кнут. Искусство программирования для ЭВМ. – М.: Издательский дом «Вильямс», 2016 Абстрактный тип данных Процесс создания программ для решения прикладных задач Математическая модель Абстрактные типы данных Структуры данных Неформальный алгоритм Программа на псевдокоде Программа на ЯВУ Математик Программист Абстрактный тип данных Процесс создания программ для решения прикладных задач Математическая модель Абстрактные типы данных Структуры данных Неформальный алгоритм Программа на псевдокоде Программа на ЯВУ Математик Программист Абстрактный тип данных Процесс создания программ для решения прикладных задач Математическая модель Абстрактные типы данных Структуры данных Неформальный алгоритм Программа на псевдокоде Программа на ЯВУ Математик Программист Абстрактный тип данных Процесс создания программ для решения прикладных задач Математическая модель Абстрактные типы данных Структуры данных Неформальный алгоритм Программа на псевдокоде Программа на ЯВУ Математик Программист Абстрактный тип данных Абстрактный тип данных (АТД) – это математическая модель с совокупностью операторов, определенных в рамках этой модели. Примеры? Абстрактный тип данных Абстрактный тип данных (АТД) – это математическая модель с совокупностью операторов, определенных в рамках этой модели. Абстрактному типу данных в ООП соответствует … Абстрактный тип данных Абстрактный тип данных (АТД) – это математическая модель с совокупностью операторов, определенных в рамках этой модели. Абстрактному типу данных в ООП соответствует понятие класса. Элементы парадигмы ООП? Абстрактный тип данных Абстрактный тип данных (АТД) – это математическая модель с совокупностью операторов, определенных в рамках этой модели. Абстрактному типу данных в ООП соответствует понятие класса. 1) Абстракция 2) Инкапсуляция 3) Наследование Абстрактный тип данных Абстрактный тип данных (АТД) – это математическая модель с совокупностью операторов, определенных в рамках этой модели. Абстрактному типу данных в ООП соответствует понятие класса. 1) Абстракция АТД можно рассматривать как обобщение простых типов данных (целых и действительных чисел и т.д.), точно так же, как процедура является обобщением простых операторов (+, - и т.д.) 2) Инкапсуляция 3) Наследование Абстрактный тип данных Абстрактный тип данных (АТД) – это математическая модель с совокупностью операторов, определенных в рамках этой модели. Абстрактному типу данных в ООП соответствует понятие класса. 1) Абстракция 2) Инкапсуляция АТД инкапсулирует типы данных в том смысле, что определение типа и все операторы, выполняемые над данными этого типа, помещаются в один раздел программы. 3) Наследование Абстрактный тип данных Абстрактный тип данных (АТД) – это математическая модель с совокупностью операторов, определенных в рамках этой модели. Абстрактному типу данных в ООП соответствует понятие класса. 1) Абстракция 2) Инкапсуляция 3) Наследование Можем рассматривать типы АТД как первичные (базовые) типы, на основе которых строятся более сложные АТД Реализация АТД Термин реализация АТД подразумевает перевод в операторы языка программирования • объявлений, определяющие переменные этого абстрактного типа данных • процедуры (в смысле вычислительного процесса) для каждого «оператора», выполняемого над объектами АТД. Реализация зависит от структуры данных, представляющих АТД. Что есть «структура» (данных)?.. Реализация АТД Термин реализация АТД подразумевает перевод в операторы языка программирования • объявлений, определяющие переменные этого абстрактного типа данных • процедуры (в смысле вычислительного процесса) для каждого «оператора», выполняемого над объектами АТД. Реализация зависит от структуры данных, представляющих АТД. Что есть «структура данных» в программировании?.. Реализация АТД Термин реализация АТД подразумевает перевод в операторы языка программирования • объявлений, определяющие переменные этого абстрактного типа данных • процедуры (в смысле вычислительного процесса) для каждого «оператора», выполняемого над объектами АТД. Реализация зависит от структуры данных, представляющих АТД. Что есть «структура данных» в программировании и «в жизни»? Реализация АТД Термин реализация АТД подразумевает перевод в операторы языка программирования • объявлений, определяющие переменные этого абстрактного типа данных • процедуры (в смысле вычислительного процесса) для каждого «оператора», выполняемого над объектами АТД. Реализация зависит от структуры данных, представляющих АТД. Под структурой (вообще) понимается совокупность устойчивых связей этого объекта, обеспечивающих его целостность, тождественность самому себе, т.е. сохранение основных свойств при различных внешних и внутренних изменениях. «Структурность» Структуры (данных) по способу организации отношений между элементами делятся на … Одиночные связи Множественные связи «один-к-одному» «один-ко-многим», «многие-ко-многим» Структуры данных по способу реализации отношения следования между элементами делятся на … Линейные структуры Нелинейные структуры «Структурность» Структуры (данных) по способу организации отношений между элементами делятся на … Одиночные связи Множественные связи «один-к-одному» «один-ко-многим», «многие-ко-многим» Структуры данных по способу реализации отношения следования между элементами делятся на … Линейные структуры Примеры? Нелинейные структуры Примеры? «Структурность» Структуры (данных) по способу организации отношений между элементами делятся на … Одиночные связи Множественные связи «один-к-одному» «один-ко-многим», «многие-ко-многим» Структуры данных по способу реализации отношения следования между элементами делятся на … Линейные структуры Примеры? Нелинейные структуры Примеры? Спасибо за внимание!