Абстрактным принято называть тип данных, в явном виде не имеющийся в языке программирования, в этом смысле это понятие относительное - тип данных, отсутствующий в одном языке программирования, может присутствовать в другом.
Абстрактный тип данных (АТД) определяется независимо от способа его реализации:
множеством возможных значений этого типа,
и набором операций со значениями этого типа.
Использование АТД может быть ограничено этапом разработки программного обеспечения, но для его явного использования в программе надо иметь его реализацию на основе уже имеющихся (и ранее реализованных) типов данных в языке программирования:
способ представления значений этого типа,
и реализацию операций со значениями этого типа.
АТД не является предопределенным в языке программирования, и даже более того – операции конструирования таких типов, предопределенные в языке, перекладывают на разработчика-программиста вопрос о способе представления значений такого типа и реализации операций со значениями этого типа. А потому, для таких типов данных вопрос о выборе определений и способов реализации операций вида конструктор (значений и хранилищ данных) такого типа, селектор и модификатор компонентов (значений и хранилищ данных) такого типа возлагается на разработчика-программиста.
В концепции АТД особый статус имеют понятия интерфейс , открытый пользователю, и реализация , скрытая от него. Особая роль этих понятий в концепции АТД связана с основополагающим положением о независимости понятия АТД от способа его реализации.
В современных «практических языках программирования» для конструирования АТД обычно используется предопределенная операция конструирования типов class , которая дает разработчику-программисту не только средства группировки данных и операций (с этими данными) в единое целое, но и средства инкапсуляции, наследования и полиморфизма для управления способами конструирования и доступа к таким данным. Отметим, что класс описывает одну возможную реализацию АТД, отображение класса в АТД выражается функцией абстракции, но обратное отношение, обычно, не является функциональным, реализаций одного и того же АТД может быть несколько.
В исследованиях по абстрактным типам данных уже на раннем этапе была осознана важная роль понятия «параметризация типа ». Действительно, например АТД «Стек» не зависит от типа элементов стека, но реализовать этот АТД указанием на «элементы какого-то одинакового типа» невозможно. В язык программирования Ada соответствующие средства конструирования параметризованных типов данных были включены изначально, а в современных «практических языках программирования» какие средства появились только со времен появления разработки по STL-библиотеке . На сегодня понятие «обобщенное программирование» занимает значимое положение в практическом программировании благодаря включению в «практические языки программирования» средств конструирования параметризованных типов данных (шаблоны, template , generic) .
Всё вышесказанное означает, что с методологической и теоретической точки зрения необходимо более детальное точное определение понятия «абстрактный тип данных». В теории понятие «абстрактный тип данных» обычно определяется как многосортная (многоосновная) алгебраическая система , в которой дополнительно к множеству возможных значений (носителю) и набору операций над такими значениями выделены понятия:
Сорт и сигнатура – эти понятия позволяют расклассифицировать и элементы носителя и операции с ними по их типам (для операций - по типам их аргументов и возвращаемого значения).
Предикаты – отношения на элементах носителя. Это позволяет определять область возможных значений наложением ограничений (требований) на допустимые значения, а также в естественной трактовке работать с произвольными логическими выражениями, не принуждая интерпретировать их как функции принадлежности для множеств или как многозначные операции.
На такой основе можно рассматривать абстрактные типы данных с единой целостной логико-алгебраической точки зрения, включая вопросы о конструкторах (типов и значений), селекторах и модификаторах свойств для объектов такого типа .
Понятия «структура данных» и «абстрактный тип данных» в чем-то очень близкие. Можно конечно считать, что эти понятия - просто два взгляда на одно и то же. Способ представления значений АТД всегда основан на некоторой структуре данных, менее или более сложной, и реализация операций с такими значениями естественно зависит от этой выбранной структуры данных. С другой стороны, заинтересовавшую нас структуру данных при большом желании мы всегда можем оформить как АТД.
Но все же мы будем различать эти два понятия, учитывая:
Абстрактный тип данных - подразумевает определенный уровень абстрагирования с целью фиксации прикладного (предметно-ориентированного) типа данных безотносительно к способам его реализации, и возможно включения этого типа данных в прикладную библиотеку, ну хотя бы для конкретной разработки конкретной программной системы. АТД может иметь несколько альтернативных реализаций, основанных на различных структурах данных.
Структура данных - скорее некоторая схема организации данных и управления ими, которая предполагает соответствующие конкретизации при ее использовании в конкретных ситуациях при решении конкретных задач.
К абстрактным типам данных прежде всего естественно относятся математические базовые алгебраические системы – последовательности, множества, отношения и отображения (функциональные отношения, функции) . Но в программировании на переднем плане не исследование общих свойств этих математических понятий, а возможности их использования в разработке моделей решения задач предметной области, алгоритмов решения этих задач и эффективной реализации разработанных алгоритмов. А потому в программировании в виде АТД обычно оформляются с одной стороны ограниченные варианты этих базовых алгебраических систем, а с другой стороны расширенные специализированными наборами операций, представляющими прагматический интерес с точки зрения области применения.
Министерство Образования и Науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ЯДЕРНЫЙ УНИВЕРСИТЕТ «МИФИ»
Димитровградский инженерно-технологический институт
Кафедра Информационные технологии
К защите допустить «» 2012 г.
Зав. кафедрой Ракова О.А.
Курсовая работа
по дисциплине «Объектно-ориентированное программирование»
Тема: «Абстрактные типы данных. Списки»
Выполнил: студент гр. ВТ-31
Шаяков А.Ф.
Руководитель: ст. преподаватель кафедры ИТ
Аленин В. А.
Нормоконтролер: ст. преподаватель кафедры ИТ
Аленин В. А.
Оценка:
Дата защиты:
Димитровград, 2012
Министерство Образования и Науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ЯДЕРНЫЙ УНИВЕРСИТЕТ «МИФИ»
Димитровградский инженерно-технологический институт
на курсовую работу
Дисциплина: Объектно-ориентированное программирование
Тема: Абстрактные типы данных. Списки
Исполнитель: Шаяков А.Ф.
Руководитель: Аленин В.А.
1.Теоретическая часть:
Абстрактные типы данных. Понятие объектно-ориентированного программирования. Линейные односвязные списки.
2.Практическая часть:
На языке С++ написать программу с объектно-ориентированной структурой для реализации линейных односвязных списков.
Сроки выполнения работы по графику:
Теоретическая часть - 15% к 5 неделе
Практическая часть – 80% к 7 неделе
Экспериментальный раздел - ____% к ____ неделе
Защита – 100% к 10 неделе
Требования к оформлению:
Расчетно-пояснительная записка курсовой работы должна быть представлена электронной и твердой копиях;
Объем отчета должен быть не менее 20 машинописных страниц без учета приложений
РПЗ подписывается у ответственного за нормоконтроль
Руководитель работы _________________
Исполнитель ________________________
Дата выдачи «_____» ___________ 2012 г.
ШАЯКОВ А.Ф.ТЕМА: АБСТРАКТНЫЕ ТИПЫ ДАННЫХ. СПИСКИ, Курсовая работа/ ДИТИ,№230105.65-Димитровград, 2012. - 29 стр., рис. 11, библ. назв. 10, приложений 1.
Ключевые слова: линейные односвязные списки, С++, объектно-ориентированное программирование.
Объект исследования – линейные односвязные списки.
Цель работы – исследовав линейные односвязные списки, написать на языке С++ программу с объектно-ориентированной структурой для их реализации.
Выводы: в данной работе была полностью изучены линейные односвязные списки, а также методы их представления в памяти. Написанная на языке С++ программа полностью соответствует объектно-ориентированной структуре, корректно и качественно выполняет свою основную задачу - реализует линейные односвязные списки.
Введение 6
1 Теоретическая часть 7
1.1 Абстрактные типы данных. Линейные списки 7
1.2 Понятие объектно-ориентированного программирования 8
2 Практическая часть 15
3 Тестирование 23
Заключение 25
Список литературы 26
Приложение A 27
Часто в процессе работы с данными невозможно определить, сколько памяти потребуется для их хранения, память следует распределять во время выполнения программы по мере необходимости отдельными блоками. Блоки связываются друг с другом с помощью указателей. Такой способ организации данных называется динамической структурой данных, поскольку она размещается в динамической памяти и ее размер изменяется во время выполнения программы.
Из динамических структур в данной работе используются линейные списки. Динамическая структура, в отличие от массива или записи, может занимать несмежные участки оперативной памяти.
Динамические структуры широко применяют и для более эффективной работы с данными, размер которых известен, особенно для решения задач сортировки.
Элемент любой динамической структуры состоит из двух частей: информационной, ради хранения которой и создается структура, и указателей, обеспечивающих связь элементов друг с другом.
Понятие абстрактных типов данных является ключевым в программировании. Абстракция подразумевает разделение и независимое рассмотрение интерфейса и реализации.
Абстракция данных предполагает определение и рассмотрение абстрактных типов данных (АТД) или, что то же самое, новых типов данных, введенных пользователем.
Абстрактный тип данных - это совокупность данных вместе с множеством операций, которые можно выполнять над этими данными.
Линейные списки
В линейном списке каждый элемент связан со следующим и, возможно, с предыдущим. В первом случае список называется односвязным, во втором - двусвязным. Если последний элемент связать указателем с первым, получится кольцевой список.
Каждый элемент списка содержит ключ, идентифицирующий этот элемент. Ключ обычно бывает либо целым числом, либо строкой и является частью поля данных. В качестве ключа в процессе работы со списком могут выступать разные части поля данных. Ключи разных элементов списка могут совпадать.
Над списками можно выполнять следующие операции:
начальное формирование списка (создание первого элемента);
добавление элемента в конец списка;
чтение элемента с заданным ключом;
вставка элемента в заданное место списка (до или после элемента с заданным ключом);
удаление элемента с заданным ключом;
упорядочивание списка по ключу.
Для работы со списком в программе требуется определить указатель на его начало. Чтобы упростить добавление новых элементов в конец списка, можно также завести указатель на конец списка.
По определению авторитета в области объектно-ориентированных методов разработки программ Гради Буча «объектно-ориентированное программирование (ООП) – это методология программирования, которая основана на представлении программы в виде совокупности объектов, каждый из которых является реализацией определенного класса (типа особого вида), а классы образуют иерархию на принципах наследуемости».
Объектно-ориентированная методология так же, как и структурная методология, была создана с целью дисциплинировать процесс разработки больших программных комплексов и тем самым снизить их сложность и стоимость.
Объектно-ориентированная методология преследует те же цели, что и структурная, но решает их с другой отправной точки и в большинстве случаев позволяет управлять более сложными проектами, чем структурная методология.
Как известно, одним из принципов управления сложностью проекта является декомпозиция. Гради Буч выделяет две разновидности декомпозиции: алгоритмическую (так он называет декомпозицию, поддерживаемую структурными методами) и объектно-ориентированную, отличие которых состоит, по его мнению, в следующем: «Разделение по алгоритмам концентрирует внимание на порядке происходящих событий, а разделение по объектам придает особое значение факторам, либо вызывающим действия, либо являющимся объектами приложения этих действий».
Другими словами, алгоритмическая декомпозиция учитывает в большей степени структуру взаимосвязей между частями сложной проблемы, а объектно-ориентированная декомпозиция уделяет больше внимания характеру взаимосвязей.
На практике рекомендуется применять обе разновидности декомпозиции: при создании крупных проектов целесообразно сначала применять объектно-ориентированный подход для создания общей иерархии объектов, отражающих сущность программируемой задачи, а затем использовать алгоритмическую декомпозицию на модули для упрощения разработки и сопровождения программного комплекса .
ОО-программирование является, несомненно, одним из наиболее интересных направлений для профессиональной разработки программ.
Объекты и классы
Базовыми блоками объектно-ориентированной программы являются объекты и классы. Содержательно объект можно представить как что-то ощущаемое или воображаемое и имеющее хорошо определенное поведение. Таким образом, объект можно либо увидеть, либо потрогать, либо, по крайней мере, знать, что он есть, например, представлен в виде информации, хранимой в памяти компьютера. Дадим определение объекта, придерживаясь мнения ГрадиБуча: «Объект – осязаемая сущность, которая четко проявляет свое поведение».
Объект - это часть окружающей нас реальности, т. е. он существует во времени и в пространстве (впервые понятие объекта в программировании введено в языке Simula). Формально объект определить довольно трудно. Это можно сделать через некоторые свойства, а именно: объект имеет состояние, поведение и может быть однозначно идентифицирован (другими словами, имеет уникальное имя).
Класс - это множество объектов, имеющих общую структуру и общее поведение. Класс - описание (абстракция), которое показывает, как построить существующую во времени и пространстве переменную этого класса, называемую объектом. Смысл предложений «описание переменных класса» и «описание объектов класса» один и тот же .
Объект имеет состояние, поведение и паспорт (средство для его однозначной идентификации); структура и поведение объектов описаны в классах, переменными которых они являются.
Определим теперь понятия состояния, поведения и идентификации объекта.
Состояние объекта объединяет все его поля данных (статический компонент, т.е. неизменный) и текущие значения каждого из этих полей (динамический компонент, т.е. обычно изменяющийся).
Поведение выражает динамику изменения состояний объекта и его реакцию на поступающие сообщения, т.е. как объект изменяет свои состояния и взаимодействует с другими объектами .
Идентификация (распознавание) объекта - это свойство, которое позволяет отличить объект от других объектов того же или других классов. Осуществляется идентификация посредством уникального имени (паспорта), которым наделяется объект в программе, впрочем как и любая другая переменная.
Выше уже говорилось, что процедурный (а также и модульный) подход позволяет строить программы, состоящие из набора процедур (подпрограмм), реализующих заданные алгоритмы. С другой стороны, объектно-ориентированный подход представляет программы в виде набора объектов, взаимодействующих между собой. Взаимодействие объектов осуществляется через сообщения. Предположим, что нашим объектом является окружность. Тогда сообщение, посланное этому объекту, может быть следующим: «нарисуй себя». Когда мы говорим, что объекту передается сообщение, то на самом деле мы вызываем некоторую функцию этого объекта (компонент-функцию). Так, в приведенном выше примере мы вызовем функцию, которая будет рисовать окружность на экране дисплея .
Инкапсуляция
Инкапсуляция - один из основополагающих принципов объектно-ориентированного программирования, идея которого заключается в том, что все свойства и методы объединены в рамках некоторого объекта.
Само название термина "инкапсуляция" происходит от английского слова encapsulate, которое в дословном переводе означает "запечатывать в капсулу" или "покрывать оболочкой". Таким образом объект (капсула) заключает в себе методы и свойства (содержимое) .
Понятие инкапсуляции может быть рассмотрено в более широком смысле, далеко выходящим за рамки объектно-ориентированного программирования в целом. Если говорить о инкапсуляции на максимально возможном уровне абстракции, тогда инкапсуляцию можно представить как способность объекта заключать в себе некое множество других объектов. Так применительно к компьютерной программе можно сказать, что она инкапсулирует в себе несколько модулей, каждый из которых в свою очередь инкапсулирует какие-то объекты, которые инкапсулируют в себе методы и свойства, которые, кстати, тоже могут быть объектами, и так далее .
Исходя из всего вышеописанного, еще одним представлением инкапсуляции может считаться любая древовидная структура, в которой любой узел дерева инкапсулирует в себе всех своих непосредственных детей, которые могут быть как листьями (примитивы, который не могут ничего в себе инкапсулировать) так и другими узлами.
И все же, если говорить о объектно-ориентированном программировании, тогда инкапсуляция - объединение данных и методов в рамках объекта.
Иногда говоря о инкапсуляции в объектно-ориентированном программировании понятие инкапсуляции приравнивается к понятию "черного ящика" или сокрытию данных, однако это не одно и то же. Да, в некоторых объектно-ориентированных языках программирования при помощи инкапсуляции разработчик может сделать свой объект черным ящиком, однако это реализуется при помощи модификаторов доступа, которые есть не во всех объектно-ориентированных языках программирования. Само понятие инкапсуляции намного шире. И даже более того, мы может все свойства и методы сделать доступными из вне, то есть ни о каком черном ящике и речи идти не может, однако инкапсуляция все еще будет присутствовать в любом объекте. Поэтому сокрытие данных по средствам модификаторов доступа является следствием инкапсуляции но никак не являются тождественно равными понятиями .
Во-первых благодаря инкапсуляции объекты перестали быть просто пользовательскими структурами данных, основная цель которых просто быть логически объединить несколько отдельных типов данных в рамках нового составного типа данных. Благодаря инкапсуляции каждый объект теперь может содержать в себе данные, описывающие состояние объекта, и свое поведение, описанное в виде методов. Другими словами объект в объектно-ориентированном программировании перестал быть примитивным пассивным типом данных, управление которым полностью отдано на откуп внешней среде, но стал обладать собственным поведением, можно даже сказать, некоторой волей и разумом, способностью активно реагировать на внешние воздействия и изменять свое состояние и по своим собственным законам и правилам.
Во-вторых, инкапсуляция дает нам возможность контролировать доступ к данным объекта. Ограничение видимости можно так же рассматривать, как проявление собственной воли объекта - объект сам решает, что из своего поведения или свойств сделать доступным для всех, что сделать доступным только для определенного круга объектов, а что и вовсе сделать сугубо интимным, о чем не будет знать ни один другой объект. Зачем, да за тем, что только сам объект точно знает, как с ним можно работать а как нет. Можно даже сказать о новой философии программирования, где объекты более на предметы, над которыми производятся некоторые действия, а, если можно так сказать, новая форма абстрактного синтетического разума, взаимодействуя с которой можно достичь нужного результата.
И еще раз повторюсь, что именно благодаря инкапсуляции объект может быть наделен некоторой волей, разумом, способностью реагировать на внешние воздействие, а не быть пассивным хранилищем данных.
Наследование
Наследование - один из четырёх важнейших механизмов объектно-ориентированного программирования (наряду с инкапсуляцией, полиморфизмом и абстракцией), позволяющий описать новый класс на основе уже существующего (родительского), при этом свойства и функциональность родительского класса заимствуются новым классом.
Другими словами, класс-наследник реализует спецификацию уже существующего класса (базовый класс). Это позволяет обращаться с объектами класса-наследника точно так же, как с объектами базового класса
Типы наследования
Простое наследование
Класс, от которого произошло наследование, называется базовым или родительским (англ. baseclass). Классы, которые произошли от базового, называются потомками, наследниками или производными классами (англ. derivedclass).
В некоторых языках используются абстрактные классы. Абстрактный класс - это класс, содержащий хотя бы один абстрактный метод, он описан в программе, имеет поля, методы и не может использоваться для непосредственного создания объекта. То есть от абстрактного класса можно только наследовать. Объекты создаются только на основе производных классов, наследованных от абстрактного.
Например, абстрактным классом может быть базовый класс «сотрудник вуза», от которого наследуются классы «аспирант», «профессор» и т. д. Так как производные классы имеют общие поля и функции (например, поле «год рождения»), то эти члены класса могут быть описаны в базовом классе. В программе создаются объекты на основе классов «аспирант», «профессор», но нет смысла создавать объект на основе класса «сотрудник вуза» .
Множественное наследование
При множественном наследовании у класса может быть более одного предка. В этом случае класс наследует методы всех предков. Достоинства такого подхода в большей гибкости. Множественное наследование реализовано в C++. Из других языков, предоставляющих эту возможность, можно отметить Python и Эйфель. Множественное наследование поддерживается в языке UML.
Множественное наследование - потенциальный источник ошибок, которые могут возникнуть из-за наличия одинаковых имен методов в предках. В языках, которые позиционируются как наследники C++ (Java, C# и др.), от множественного наследования было решено отказаться в пользу интерфейсов. Практически всегда можно обойтись без использования данного механизма. Однако, если такая необходимость все-таки возникла, то, для разрешения конфликтов использования наследованных методов с одинаковыми именами, возможно, например, применить операцию расширения видимости - «::» - для вызова конкретного метода конкретного родителя.
Попытка решения проблемы наличия одинаковых имен методов в предках была предпринята в языке Эйфель, в котором при описании нового класса необходимо явно указывать импортируемые члены каждого из наследуемых классов и их именование в дочернем классе.
Большинство современных объектно-ориентированных языков программирования (C#, C++, Java, Delphi и др.) поддерживает возможность одновременно наследоваться от класса-предка и реализовать методы нескольких интерфейсов одним и тем же классом. Этот механизм позволяет во многом заменить множественное наследование - методы интерфейсов необходимо переопределять явно, что исключает ошибки при наследовании функциональности одинаковых методов различных классов-предков.
Для решения поставленной задачи используется объектно-ориентированная структура программы. Программа представлена двумя классами и основным cpp-файлом, содержащим пользовательский интерфейс для удобства работы со списками.
Класс cList представляет собой линейный односвязный список, состоящий из объектов класса cElement.
Класс cElement имеет следующую структуру:
cElement *next;
~cElement(void);
void setdata (int);
void setref (cElement*);
cElement* getref ();
Поле data типа int содержит числовое значение элемента списка, поле next типа cElement* - ссылку на следующий элемент списка. Методы setdata и getdata используются для доступа к приватному полю data класса с целью получения и соответственно установки значения данного поля. Метод setref используется для установки ссылки с текущего на следующий элемент списка, а getref – для перехода на следующий элемент.
void cElement::setdata(int sd)
int cElement::getdata()
returnthis->data;
void cElement::setref(cElement* rf)
cElement* cElement::getref()
returnthis->next;
Реализация данных методов исключительно проста, что видно из их программных кодов, представленных выше.
Теперь рассмотрим структуру класса cList
#include"cElement.h"
cElement *head;
void Add (int);
void Insert(int, int);
void Remove(int);
void RemoveAll();
Данный класс содержит ссылку на головной элемент списка - head, типа cElement*. Хранение данной ссылки необходимо для корректного выполнения операций добавления, удаления данных и печати списка. Дело в том что, при выполнении любой из вышеуказанных операций, происходит перебор элементов списка, чтобы дойти до нужного, так как список не имеет произвольного доступа к элементам, поэтому перебор рациональней начинать с "головы" списка. Кроме ссылки на начало списка, каждый объект данного класса будет иметь поле elcount, которое содержит количество элементов списка.
Продолжим рассмотрение данного класса с изучения методов, реализованных в нем, для работы со списками.
Метод Add - добавление данных в конец списка.
В качестве параметра данный метод принимает числовое значение (переменная xd), которое нужно сохранить в добавляемый элемент списка.
void cList::Add(int xd)
Так происходит создание нового элемента и установка значения его числового поля:
cElement *temp = newcElement;
temp->setdata(xd);
После осуществляется проверка количества элементов списка, если список пуст, то создается головной элемент, иначе "рядовой" компонент списка:
if (elcount ==0)
temp->setref(NULL);
temp->setref(NULL);
p->setref(temp);
Можно заметить, что в вышеуказанной конструкции используется метод setref класса cElement, который необходим для установки ссылки на следующий элемент списка, иначе список будет несвязанным, что чревато потерей данных и некорректной работы программы.
При первом запуске программы, описанный выше метод, используется для последовательного добавления элементов в список, с которым затем можно работать, для остановки ввода в командной строке необходимо вместо числового значения элемента ввести команду "stop" (см. рисунок 1).
Рисунок 1 – Процесс добавления элементов в список
После ввода команды "stop", происходит печать списка и программа переходит в режим ожидания команды (см. рисунок 2).
Рисунок 2 – Распечатанный список
Метод Print - печать списка.
Для печати важно знать начало списка, чтобы последовательно распечатать значения всех элементов списка, поэтому в переменную temp устанавливается ссылка на "голову" списка, после чего проверяется факт существования списка и выводится соответствующие сообщение, если он не подтверждается, если же список не пуст, то он выводится на экран:
void cList::Print()
cElement * temp = head;
if (temp == NULL) cout while(temp != NULL)
temp = temp->getref();
Метод Del - удаление начального элемента списка.
Для удаления начального элемента необходимо сначала перенести ссылку на следующий компонент списка, сделав его первым таким образом и затем уже удалить требуемый элемент:
voidcList::Del()
cElement * temp = head;
head = head->getref();
Метод RemoveAll - удаление всего списка.
Данный метод основан на вышеуказанном и заключается в последовательном удалении начальных элементов списка, пока не будет удален весь список.
void cList::RemoveAll()
while (elcount!=0)
Для запуска данного метода, в меню работы со списком необходимо ввести команду "dellist" (см. рисунок 3).
Рисунок 3 – Ввод команды на очистку списка
И если пользователь действительно уверен в своих действиях, необходимо принять предложение программы, после чего произойдет удаление всего списка (см. рисунок 4).
Рисунок 4 – Пустой список
Метод Remove - удаление определенного элемента списка.
Менее радикальный метод, чем предыдущий. Удаляется лишь один, указанный в качестве параметра, элемент списка. Происходит это следующим образом: программа сначала проверяет корректность введенного параметра, если номер удаляемого элемента меньше единицы или больше общего числа элементов списка, то она выводит сообщение об ошибке, если же претензий к введенному параметру у программы нет, то переносятся необходимые ссылки элементов, находящихся рядом с удаляемым, так чтобы список остался связанным, после чего происходит удаление требуемого элемента.
void cList::Remove(int del)
cElement *cur = head, *de;
if ((del>=1) && (del
head = head->getref();
while (j!=del-1)
cur = cur->getref();
de=cur->getref();
cur->setref(de->getref());
coutsystem ("pause");
Для запуска данного метода, в меню работы со списком необходимо ввести команду "delete". Затем ввести номер удаляемого элемента или же команду "back" для отмены удаления (см. рисунок 5).
Рисунок 5 – процесс удаления элемента списка
Список после удаления четвертого элемента будет выглядеть следующим образом (см. рисунок 6).
Рисунок 6 – Список после удаления одного элемента
Метод Insert - вставка нового элемента в указанное место в списке.
В качестве параметров данный метод принимает: позицию добавляемого элемента и его числовое значение. Новый элемент встанет именно на указанное место, таким образом, элементы находящие справа от текущего будут сдвинуты на одну позицию. При добавлении нового элемента в начало списка необходимо просто перенести ссылку с данного элемента на следующий, связав тем самым список и указать ссылку на начальный элемент. Несколько другая ситуация возникает при добавлении нового элемента между двумя уже существующими, для этого с помощью цикла дойти до места вставки элемента, затем связать с новым элементом компоненты, находящиеся справа и слева от него. Ведь что, к примеру, нужно сделать, если необходимо удлинить цепь: необходимо разомкнуть ее, затем прикрепив новое звено к первой части цепи, прицепить к этому же звену вторую, нечто подобное реализуется в данном методе. Стоит отметить, что при указании неверной позиции для добавления, которая меньше единицы или больше общего числа элементов, программа выдаст соответствующие сообщение об ошибке.
void cList::Insert (int pos, int val)
cElement *cur = head;
cElement *temp = new cElement;
temp->setdata(val);
if ((pos>=1) && (pos
temp->setref(head);
while (j!=pos-1)
cur = cur->getref();
p=cur->getref();
cur->setref(temp);
temp->setref(p);
coutsystem ("pause");
Для запуска данного метода, в меню работы со списком необходимо ввести команду "insert". Затем ввести позицию и числовое значение добавляемого элемента или же команду "back" для отмены удаления (см. рисунок 7).
Рисунок 7 - Процесс вставки элемента
Список после добавления в третью позицию элемента со значением 111, список будет выглядеть следующим образом (см. рисунок 8).
Рисунок 8 – Список после добавления элемента
В процессе описания не раз упоминалось меню работы со списком, остается отметить, что данное меню значительно облегчает работу со списком. Алгоритм его работы заключается в циклическом вызове одних и тех же методов, печати списка например, пока не будет введена определённая команда. Список доступных команд можно увидеть, введя "help" в консоли (см. рисунок 9)
Рисунок 9 – Доступные команды
Полностью программный код меню представлен в приложении А.
Часто в процессе работы возникают ситуации, связанные с некорректным вводом данных, что может вызвать выход из строя программы. Разумеется, в каждой программе должны быть реализованы алгоритмы защиты от неопытного пользователя, предостерегающие программу от сбоя. Рассмотрим, каким образом функционируют такие алгоритмы в созданной программе.
Первоначальный ввод списка реализуется представленным ниже кодом:
if (atoi(ss)!=NULL)
mylist.Add(atoi(ss));
Перед вызовом метода add для добавления нового элемента в список, осуществляется проверка введенной строки. Функция atoi переводит строковое значение в числовое и возвращает NULL в случае, если введенная строка не является числом. Таким образом, при вводе будут игнорироваться любые строки не являющиеся числами, кроме строки с командой остановки ввода (см. рисунок 10).
Рисунок 10 – Ввод некорректных данных
После ввода таких данных, список будет выглядеть следующим образом (см. рисунок 11).
Рисунок 11 – Полученный список
Программа продолжает корректно работать после, даже после ввода ошибочных данных. Аналогичные методы борьбы с некорректными данными используются, при остальных операциях ввода, присутствующих в программе.
В данной работе были получены понятия об абстрактные типах данных, о принципах их представления в современных языках программирования, в С++ в частности. В большинстве современных императивных языков основной концепцией, используемой для описания абстракций в программном коде, является объектно-ориентированный подход. Объектно-ориентированное программирование (ООП) также, как и подход к программированию на основе АТД, является, в некоторой степени, развитием идей о модульном программировании. Модули – это компоненты программы, которые имеют два важных свойства:
Модули скрывают в себе детали реализации.
Модули могут быть повторно использованы в различных частях программы.
Дэвид Парнас в своей работе 1972 года, представлял модули как абстрактные машины, хранящие внутри себя состояния и позволяющие изменять это состояние посредством определенного набора операций. Эта концепция является базовой, как для концепции абстрактных типов данных, так и для объектно-ориентированного программирования. Проведя параллели между работой Парнаса и современных понятиях ООП, нетрудно заметить взаимосвязь понятий класс и модуль.
В данной работе, линейные односвязные списки, являющие собой абстрактный тип данных, представлены разработанными модулями, для доступа к состояниям которых также реализованы специальные операции, называемые методами в объектно-ориентированном программировании.
1. Иан Грэхем Объектно-ориентированные методы. Принципы и практика = Object-Oriented Methods: Principles & Practice. - 3-е изд. - М.: «Вильямс», 2004. - С. 880.
2. Антони Синтес Освой самостоятельно объектно-ориентированное программирование за 21 день = Sams Teach Yourself Object-Oriented Programming in 21 Days. - М.: «Вильямс», 2002. - С. 672.
3. Бертран Мейер Объектно-ориентированное конструирование программных систем + CD . Интернет-университет информационных технологий - ИНТУИТ.ру, Русская Редакция, 2005
4. Биллиг В.А. Основы программирования на C# . Интернет-университет информационных технологий - ИНТУИТ.ру, 2006
5. “Новые языки программирования и тенденции их развития”, Ушкова В., 2005 г.
6. Бьерн Страуструп "Язык программирования C++" Специальное издание либо 3-е издание изд. Бином, Невский Диалект, ISBN 5-7989-0226-2, 5-7940-0064-3, 0-201-70073-5
7. Бьерн Страуструп "Дизайн и эволюция языка C++". ДМК-Пресс, Питер, ISBN 5-469-01217-4, 0-201-54330-3
8. Бьярне Страуструп "Программирование принципы и практика использования C++". "И.Д. Вильямс", 2011, ISBN 978-5-8459-1621-1 (рус.)
9. Гради Буч и др. "Объектно-ориентированный анализ и проектирование с примерами приложений" 2-е либо 3-е издание. Бином, Невский диалект, Вильямс ISBN 978-5-8459-1401-9, 0-201-89551-X, 0-8053-5340-2, 5-7989-0067-3, 5-7940-0017-1
10. Скотт Мейерс "Эффективное использование C++. 50 рекомендаций по улучшению ваших программ и проектов" ДМК, Питер, ISBN 0-201-92488-9, 5-93700-006-4, 5-469-01213-1
Программный код меню
#include "cList.h"
#include "string.h"
using namespace std;
coutwhile (strstr(ss,"stop")==NULL)
if (atoi(ss)!=NULL)
mylist.Add(atoi(ss));
system ("cls");
while (strstr(com,"exit")==NULL)
coutmylist.Print();
if (strstr(com,"help")!=NULL) com_ind=1;
if (strstr(com,"add")!=NULL) com_ind=2;
if (strstr(com,"insert")!=NULL) com_ind=3;
if (strstr(com,"delete")!=NULL) com_ind=4;
if (strstr(com,"dellist")!=NULL) com_ind=5;
switch (com_ind)
system ("cls");
system ("cls");
coutcoutcoutcoutcoutcoutcoutcom_ind=0;
if (strstr(ss,"back")==NULL)
if (atoi(ss)!=NULL)
mylist.Add(atoi(ss));
system ("cls");
//insert elements
if (strstr(ss,"back")==NULL)
if (atoi(ss)!=NULL)
system ("cls");
if (strstr(ss,"back")==NULL)
if (atoi(ss)!=NULL)
mylist.Insert(pos,atoi(ss));
system ("cls");
//delete elements
if (strstr(ss,"back")==NULL) определяется множеством значений данного и набором операций... связных структур данных – списков . Структура данных – это совокупность элементов данных , между которыми... в памяти ЭВМ называется абстрактной или логической. Чаще...
... тип похожим на простые типы данных . Множественные типы описываются в разделе типов ... ВУ может быть описано. Абстрактные вычислительные структуры, описывающие ввод... других случаях типы всех компонент списка должны совпадать с типом компоненты файла. ...
Развивающимися направлениями языков программирования с абстрактными типами данных и объектно-ориентированных языков программирования. ... типов данных - список и массив. Каждый литерал уникально идентифицируется индексом в массиве и порядковым номером в списке ...
Защиты информации………………………………………………..17 Абстрактные модели защиты информации... регулирующих взаимодействие с обоими типами данных (Certification Rules): Все... различные вариации и дополнения к имеющемуся списку . Уровни безопасности – определенное...
Все встроенные типы данных, являются абстрактными, хотя так их называют редко.
Абстракция - это суждение или представление о некотором объекте, которое содержит только свойства, являющиеся существенными в данном контексте. Абстракция позволяет объединять экземпляры объектов в группы, внутри которых общие свойства объектов можно не рассматривать, т.е. абстрагироваться от них. Абстракция - это эффективное средство против сложности программирования, позволяющее программисту сосредоточиться на существенных свойствах объектов. Виды абстракций: абстракция процесса и абстракция данных .
Абстракция процесса. Все подпрограммы являются абстракциями процессов, они определяют способ, с помощью которого программа устанавливает, что необходимо выполнить некоторый процесс, без уточнения деталей того, как именно это следует сделать. Возможность абстрагироваться от многочисленных деталей алгоритма, который выполняется подпрограммой, позволяет создавать, читать и понимать большие программы. Любой абстракции данных являются операции, определяемые как абстракции процессов.
Абстракция данных. Абстрактный тип данных - это инкапсуляция, которая содержит только представления данных одного конкретного типа и подпрограммы, которые выполняют операции с данными этого типа. С помощью управления доступом несущественные детали описания типа можно скрыть от внешних модулей, которые используют такой тип. Программные модули, которые используют абстрактный тип данных, могут объявлять переменные этого типа, даже несмотря на то, что реальное представление типа скрыто от них. Экземпляр абстрактного типа данных называется объектом.
Причина создания абстракции типа данных и абстракции процесса - это средство против сложности, способ сделать большие и/или сложные программы более управляемыми.
Разделение программы на синтаксические контейнеры, которые содержат группы логически связанных подпрограмм и данных. Эти синтаксические контейнеры называются модулями, а процесс их разработки- модуляризацией.
Составление программы из наборов подпрограмм и данных, каждый из которых можно компилировать отдельно, без повторной компиляции остальной части программы. Такой набор называется единицей компиляции.
Инкапсуляция - это способ объединения в единое целое подпрограмм и данных, которые они обрабатывают. Инкапсуляция, которая компилируется либо отдельно, либо независимо от других, является основой абстрактной системы и логической организации набора соответствующих вычислений.
Абстрактные типы данных, определяемые пользователем, должны иметь следующие свойства:
1) определение типа, позволяющее программным модулям объявлять переменные этого типа, создавая при этом реальное представление этих переменных в памяти.
2) набор операций для манипуляций с объектами данного типа.
Формальное определение абстрактного типа данных в контексте типов, определенных пользователем: абстрактный тип данных - это тип данных, который удовлетворяет следующим двум условиям.
Представление (определение типа) и операции над объектами данного типа содержатся в одной синтаксической единице, переменные данного типа можно создавать и в других модулях.
Представление объектов данного типа скрыто от программных модулей, использующих этот тип, над объектами можно производить операции, которые прямо предусмотрены в определении типа.
Упаковка представления типа и операций в отдельную синтаксическую единицу, позволяет организовывать программу в виде логических единиц, которые можно компилировать отдельно. Во-вторых, появляется возможность модифицировать представления объектов данного типа или операции с ними в отдельной части программы. У сокрытия деталей представления типа есть преимущества. Клиенты не могут "видеть" детали представления объектов, и их код не зависит от этого представления. Таким образом, представления объектов можно изменять в любое время, не требуя при этом вносить изменения в код клиентов. Другим очевидным и важным преимуществом сокрытия информации является повышенная надежность. Клиенты не могут непосредственно изменять основные представления объектов ни преднамеренно, ни случайно, следовательно, возрастает целостность таких объектов. Объекты можно изменять только с помощью предусмотренных для этого операций.
Вопросы разработки типов
Должна существовать возможность делать имя типа и заголовки подпрограмм видимыми в клиентах абстракции. Это позволяет клиентам объявлять переменные абстрактного типа и манипулировать их значениями. Несмотря на то что имя типа должно быть видимым извне, его определение должно быть скрыто.
Существует очень мало общих встроенных операций, которые можно выполнять с объектами абстрактных типов, в отличие от операций, предусмотренных определением типа. К таким операциям относятся присваивания, а также проверки равенства и неравенства. Если язык не позволяет пользователям перегружать операцию присваивания, то она должна быть встроенной. Проверки равенства и неравенства в одних случаях должны быть заранее определены, а в других - нет. Разработчик типа должен определить операции для большинства абстрактных типов данных сам.
Языки Smalltalk, C++ и Java непосредственно поддерживают абстрактные типы данных.
Абстрактные типы данных в языке C++
Языки Ada и Modula-2 обеспечивают инкапсуляцию, которая может использоваться при моделировании абстрактных типов данных, в языке C++ введено понятие класса, который непосредственно поддерживает абстрактные типы данных. В языке C++ классы - это типы, а пакеты языка Ada и модули языка Modula-2 типами не являются. Пакеты и модули импортируются, позволяя импортирующей программной единице объявлять переменные любого типа, определенного в пакете или модуле. В программе на языке C++ переменные объявляются как сущности, имеющие тип данного класса. Таким образом, классы гораздо больше похожи на встроенные типы, чем пакеты или модули. Программная единица, которая видит пакет в языке Ada или модуль в языке Modula-2, имеет доступ к любым открытым сущностям просто по их именам. Программная единица на языке C++, которая объявляет экземпляр класса, также имеет доступ к любым открытым сущностям в этом классе, но только через экземпляр этого класса.
Приложение к рабочей программе по дисциплине «Структуры и алгоритмы обработки данных в ЭВМ»
Абстрактный тип данных "Список".
Список – последовательность элементов определенного типа a 1 , a 2 , ..., a n , где n https://pandia.ru/text/78/308/images/image001_307.gif" width="13" height="16">1, то a 1
Называется первым элементом, а an – последним элементом списка. Элементы списка линейно упорядочены в соответствии с их позицией в списке. Элемент ai предшествует элементу ai +1 для i = 1,2, n -1 и ai следует за ai -1 для i = 2,3, n . Каждый элемент списка ai имеет позицию i , i =1,2, n . В списке существует позиция, означающая конец списка – nil . Она следует за последним элементом списка.
Операторы АТД "Список":
1. INSERT(x , р, L ). Этот оператор вставляет объект х в позицию р в списке L, перемещая элементы от позиции р и далее в следующую, более высокую позицию. Таким образом, если список L состоит из элементов a 1 , a 2 , ..., а n а1, а2, ..., ар-1, х, ар, ..., a n. . Если р принимает значение nil , то будем иметь a 1 , a 2 , ..., a n , , х . Если в списке L нет позиции р, то результат выполнения этого оператора не определен.
2. LOCATE (x , L ). Эта функция возвращает позицию объекта х в списке L. Если в списке объект x встречается несколько раз, то возвращается позиция первого от начала списка объекта х. Если объекта х нет в списке L , то возвращается nil .
3. RETRIEVE (p , L ). Эта функция возвращает элемент, который стоит в позиции р в списке L. Результат не определен, если р = nil или в списке L нет позиции р.
4. DELETE (p , L ). Этот оператор удаляет элемент в позиции р списка L. Так, если список L состоит из элементов a 1 , a 2 , ..., а n , то после выполнения этого оператора он будет иметь вид а1, а2, ...,, ap - i , ap + i , ..., а n. Результат не определен, если в списке L нет позиции р или р = nil .
5. NEXT(p, L ) и PREVIOUS(p, L ). Эти функции возвращают соответственно следующую и предыдущую позиции от позиции р в списке L. Если р - последняя позиция в списке L, то NEXT(p , L ) = nil . Функция NEXT не определена, когда р= nil . Функция PREVIOUS не определена, если р = 1. Обе функции не определены, если в списке L нет позиции р.
6. MAKENULL ( L ) . Эта функция делает список L пустым и возвращает позицию nil .
7. FIRST (L ). Эта функция возвращает первую позицию в списке L. Если список пустой, то возвращается позиция nil .
8. PRINTLIST (L ). Печатает элементы списка L в порядке их расположения в списке.
Представление списка с помощью массива:
Представление списка с помощью односвязного списка:
Обозначения:
· – указатель на начало списка,
· last - указатель на последний элемент в списке,
· maxlenght – максимальная длина (количество элементов) в списке.
Представление списка с помощью двусвязного списка:
Упражнения:
1. Напишите программы вставки, удаления и поиска элементов отсортированного списка, используя для реализации списка
§ массив,
§ указатели.
2. Напишите программу для слияния
§ двух отсортированных связных списков,
§ n отсортированных связных списков,
3. Дан многочлен вида
р(х) = с1 х e 1 + c 2 xe 2 + + с n х n , где е1 > е2 > ... > e n > 0.
Такой многочлен можно представить в виде связанного списка, где каждый элемент имеет три поля: одно - для коэффициента с i второе - для показателя степени е i третье - для указателя на следующий элемент. Для описанного, представления многочленов напишите программу сложения и умножения многочленов, используя это представление.
4. Реализуйте АТД LIST (Список) для любого типа данных и его операторы INSERT, LOCATE, RETRIEVE, DELETE, NEXT, PREVIOUS, MAKENULL, PRINTLIST:
§ список задан в виде массива,
§ список задан в виде односвязного списка,
§ список задан в виде двусвязного списка.
Раздел рабочей программы 2.1.2
Абстрактный тип данных "Стек".
Стек - это специальный тип списка, в котором все вставки и удаления выполняются только на одном конце, называемом вершиной , (top). Для стека используется метод доступа LIFO (last-in-first-out - последний вошел - первый вышел).
Операторы АТД "Стек":
1. MAKENULL (S ). Делает стек S пустым.
2. TOP (S ). Возвращает элемент из вершины стека S. Обычно вершина стека идентифицируется позицией 1, тогда TOP(S) можно записать в терминах общих операторов списка как RETRIEVE(FIRST(S), S).
3. POP (S ). Удаляет элемент из вершины стека (выталкивает из стека), в терминах операторов списка этот оператор можно записать как DELETE(FIRST(S), S ).
4. PUSH (x , S ). Вставляет элемент х в вершину стека S (заталкивает элемент в стек). Элемент, ранее находившийся в вершине стека, становится элементом, следующим за вершиной, и т. д. В терминах общих операторов списка данный оператор можно записать как INSERT(;c, FIRST(S), S ).
5. EMPTY (S ) . Эта функция возвращает значение true (истина), если стек S пустой, и значение false (ложь) в противном случае.
массива:
Представление стека с помощью односвязного списка:
Упражнения:
Реализуйте АТД STACK(Стек) для любого типа данных и его операторы MAKENULL, TOP, POP, PUSH, EMPTY.
§ стек задан в виде массива,
§ стек задан в виде односвязного списка.
Раздел рабочей программы 2.1.2
Абстрактный тип данных "Очередь".
Очередь (queue) - это специальный тип списка, где элементы вставляются с одного конца, называемого задним (rear), а удаляются с другого, переднего (front). Очереди также называют "списками типа FIFO" (аббревиатура FIFO расшифровывается как first-in-first-out: первым вошел - первым вышел). Операторы, выполняемые над очередями, аналогичны операторам стеков. Существенное отличие между ними состоит в том, что вставка новых элементов осуществляется в конец списка , а не в начало, как в стеках.
Операторы АТД "Очередь":
1. MAKENULL (Q ) очищает очередь Q, делая ее пустой.
2. FRONT (Q ) - функция, возвращающая первый элемент очереди Q. Можно реализовать эту функцию с помощью операторов списка как RETRIEVE(FIRST(Q), Q).
3. ENQUEUE (a , Q ) вставляет элемент х в конец очереди Q.
С помощью операторов списка этот оператор можно выполнить следующим образом: INSERT(x, END(Q), Q).
4. DEQUEUE (Q ) удаляет первый элемент очереди Q. Также реализуем с помощью операторов списка как DELETE(FIRST(Q), Q).
5. EMPTY (Q ) возвращает значение true тогда и только тогда, когда Q является пустой очередью.
циклического массива:
Обозначения:
Q – очередь,
Q . front – указатель на начало очереди,
Q . rear - укаазатель на конец очереди.
Представление очереди с помощью односвязного списка:
Упражнения:
Реализуйте АТД QUEUE (Очередь) для любого типа данных и его операторы MAKENULL, FRONT, ENQUEUE, DEQUEUE, EMPTY.
§ очередь задана в виде циклического массива,
§ очередь задана в виде двусвязного списка.
Абстрактный тип данных "Дерево".
Дерево - это совокупность элементов, называемых узлами (один из которых определен как корень ), и отношений ("родительских"), образующих иерархическую структуру узлов. Узлы, так же, как и элементы списков, могут быть элементами любого типа. Формально дерево можно рекуррентно определить следующим образом.
1. Один узел является деревом. Этот же узел также является корнем этого дерева.
2. Пусть п - это узел, a T 1 , Т2, ..., Tk - деревья с корнями n 1 . n 2 , ..., nk соответственно. Можно построить новое дерево, сделав п родителем узлов n 1 . n 2 , ..., nk . В этом дереве п будет корнем, a T 1 , Т2, ..., Tk - поддеревьями этого корня. Узлы n 1 . n 2 , ..., nk называются сыновьями узла п.
Часто в это определение включают понятие нулевого дерева , т. е. "дерева" без узлов, такое дерево обозначается словом nill .
Пример: О главление книги, схематически можно представить деревом. Отношение родитель-сын отображается в виде линии. Деревья обычно рисуются сверху вниз так, что родители располагаются выше "детей".
DIV_ADBLOCK135">
Высотой узла дерева называется длина самого длинного пути из этого узла до какого-либо листа. В примере высота узла Гл.1 равна 1, узла Гл.2 - 2, а узла Гл. З - 0. Высота дерева совпадает с высотой корня. Глубина узла определяется как длина пути (он единственный) от корня до этого узла.
Сыновья узла обычно упорядочиваются слева направо. Поэтому два дерева на рисунке различны, так как порядок сыновей узла а различен. Если порядок сыновей игнорируется, то такое дерево называется неупорядоченным , в противном случае дерево называется упорядоченным .
Операторы АТД "Дерево":
1. PARENT (n , Т). Эта функция возвращает родителя (parent) узла п в дереве Т. Если п является корнем, который не имеет родителя, то в этом случае возвращается nill . Здесь nill указывает на то, что произошел выход за пределы дерева.
2. LEFTMOST __ CHILD (n , Т). Данная функция возвращает самого левого сына узла n в дереве Т. Если n является листом (и поэтому не имеет сына), то возвращается nill .
3. RIGHT _ SIBLING (n , Т). Эта функция возвращает правого брата узла п в дереве Т или значение nill , .если такового не существует. Для этого находится родитель р узла п и все сыновья узла р, затем среди этих сыновей находится узел, расположенный непосредственно справа от. узла п.
4. LABEL (n , T ). Возвращает метку узла n . дерева Т. Для выполнения этой функции требуется, чтобы на узлах дерева были определены метки.
5. CREATE (v , T 1 , T 2 , ..., Ti ,) - это cемейство функций, которые для каждого i = 0, 1, 2,... создают новый корень r с меткой v и далее для этого корня создает i сыновей, которые становятся корнями поддеревьев T 1 , Т2, .... Ti ;. Эти функции возвращают дерево с корнем r . Отметим, что если i = 0, то возвращается один узел r , который одновременно является и корнем, и листом.
6. ROOT (T ) возвращает узел, являющимся корнем дерева T , Если T - пустое дерево, то возвращается nill .
7. MAKENULL (T ). Этот оператор делает дерево T пустым деревом.
Представление дерева с помощью массива родителей:
Представление дерева с помощью связанных списков:
Представление дерева посредством, левых сыновей и правых братьев.
Обозначения в рисунке:
nodespace – массив узлов дерева,
cellspase – массив списков сыновей узлов,
Упражнения:
1. Дано дерево:
DIV_ADBLOCK137">
§ дерево задано в виде массива записей узлов, содержащих индекс самого левого сына, индекс правого брата и метку,
§ связное двоичное дерево задано с помощью указателей на левого и правого сыновей.
4. Напишите функции обхода двоичного дерева в прямом, обратном и симметричном порядке.
Раздел рабочей программы 2.1.3
Абстрактный тип данных "Множество".
Множество обычно изображается в виде последовательности его элементов, заключенной в фигурные скобки, например {1, 4} обозначает множество, состоящее из двух элементов, - чисел 1 и 4. Порядок, в котором записаны элементы множества, не существен, поэтому можно писать {4, 1} так же, как и {1, 4}, при записи одного и того же множества. Множество не является списком (хотя бы по признаку произвольного порядка записи элементов). В множестве отсутствуют повторяющиеся элементы ({1, 4, 1} не является множеством).
Фундаментальным понятием теории множеств является понятие отношения принадлежности к множеству , обозначаемое символом . Таким образом, запись х х не принадлежит множеству А ", т. е. х не является элементом множества А . Существует специальное множество, обозначаемое символом , которое называется пустым, множеством , и которое не имеет элементов. Множество DIV_ADBLOCK138">
Говорят, что множество А содержится в множестве В (или включается в множество В), пишется A В или В А , если любой элемент множества А является также элементом множества В. В случае A В также говорят, что множество А является подмножеством множества В.
Например, {1, 2} https://pandia.ru/text/78/308/images/image019_36.gif" width="15" height="15 src=">В и А В, то множество А называют собственным, истинным или строгим подмножеством множества В.
Основными операциями, выполняемыми над множествами, являются операции объединения, пересечения и разности. Объединением множеств А и В (обозначается А В) называется множество, состоящее из элементов, принадлежащих хотя бы одному из множеств A и В.
Пересечением множеств А и В (обозначается А В) называется множество, состоящее только из тех элементов, которые принадлежат и множеству А , и множеству В. Разностью множеств А и В (обозначается A \ B ) называется множество, состоящее только из тех элементов множества А , которые не принадлежат множеству В .
Например, если А = {а, b, с} и В= {b, а}, то А В= {а, b, с, d}, A В = { b } и А \ В = {а, с}.
Операторы АТД “Множество”:
1. UNION (A , В, С) А и В С, равное А В.
2. INTERSECTION (A , В, С) имеет "входными" аргументами множества А и В , а в качестве результата - "выходное" множество С, равное А В. .
3. DIFFERENCE (A , В, С) имеет "входными" аргументами множества А и В , а в качестве результата - "выходное" множество С, равное А\ В.
4. MERGE ( A , В, С) оператор выполняет слияние (merge ), или объединение непересекающихся множеств . Этот оператор не отличается от оператора. UNION , но здесь предполагается, что множества-операнды не пересекаются (т. е. не имеют общих элементов). Оператор присваивает множеству С значение А В , но результат будет не определен, если А В , т. е. в случае, когда множества А и В имеют общие элементы.
5. member (х, А ) имеет аргументами множество А и объект х того же типа, что и элементы множества А , и возвращает булево значение true (истина), еcли х a", "b", "с"})= "а". Подобным образом определяется оператор МАХ .
11.EQUAL (A , В ) возвращает значение true тогда и только тогда, когда множества А и В состоят из одних и тех же элементов.
12. FIND (x ) оперирует в среде, где есть набор непересекающихся множеств. Он возвращает имя (единственное) множества, в котором есть элемент х.
Представление множества:
Множество можно задать с помощью массива или связного списка.
Упражнения:
1. Заданы два множества А = {1, 2, 3} и В = {3, 4, 5}. Каков будет результат выполнения следующих операторов?
· UNION(A. В. С),
· INTERSECTION(A, В, С),
· DIFFERENCE(A. В. С),
· MEMBER(l. A),
· INSERT(1,А),
· DELETE(1, А),
2. Реализуйте АТД “Множество” для любого типа данных и его операторы MAKENULL, UNION, INTERSECTION, MEMBER, MIN.
· множество задано с помощью массива фиксированной длины и указателя на последнюю занятую позицию в массиве,
· множество задано с помощью несортированного связного списка,
· множество задано с помощью отсортированного связного списка,
Раздел рабочей программы 2.1.3
Дерево двоичного поиска - структура данных для представления множеств, чьи элементы упорядочены посредством некоторого отношения линейного порядка. На деревьях двоичного поиска можно реализовать операторы множества INSERT , DELETE , MEMBER и MIN , причем время их выполнения в среднем имеет порядок O (log n) для множеств, состоящих из п элементов.
Характерным для дерева двоичного поиска является то, что его узлы помечены элементами множеств (узлы дерева содержат элементы множества). Причем, все элементы, хранящиеся в узлах левого поддерева любого узла х, меньше элемента, содержащегося в узле х, а все элементы, хранящиеся в узлах правого поддерева узла х, больше элемента, содержащегося в узле х.
Примеры двоичного дерева:
https://pandia.ru/text/78/308/images/image023_7.jpg" width="277" height="122 src=">
Представление АВЛ-дерева не отличается от представления двоичного дерева поиска.
Другой разновидностью сбалансированного дерева поиска является 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 дерево, которое получится в результате вставки в пустое множество (представленное как 2-3 дерево) элементов 5, 2, 7, 0, 3, 4, 6, 1, 8, 9.
5. Покажите результат удаления элемента 3 из 2-3 дерева, полученного в предыдущем упражнении.
3. Реализуйте АТД “Дерево поиска” для любого типа данных и его операторы INSERT, DELETE, MEMBER и MIN.
· дерево задано в виде связного двоичного дерева
· дерево задано в виде 2-3 дерева
Раздел рабочей программы 2.1.3
Абстрактный тип данных "Словарь".
Словарь – множество, предназначенное для хранения "текущих" объектов с периодической вставкой или удалением некоторых из них. Время от времени также возникает необходимость узнать, присутствует ли конкретный элемент в данном множестве. Словарь реализуется с помощью АТД “Словарь” с операторами INSERT, DELETE и MEMBER . В набор операторов словаря также входит оператор MAKENULL для инициализации структур данных АТД.
Словарь можно представить с помощью хеш-таблицы. Таблица строится на основе следующей идеи: потенциальное множество элементов (возможно, бесконечное) разбивается на конечное число классов. Для В классов, пронумерованных от 0 до В -1 , строится хеш-функция h такая, что для любого элемента х исходного множества функция h(x} принимает целочисленное значение из интервала 0, ..., В - 1, которое, соответствует классу, которому принадлежит элемент х. Элемент х часто называют ключом, h( x) - хеш -значением х, а "классы" – сегментами . Поспособу разрешения коллизий хеширования (два элемента множества имеют одинаковое значение h(x) ) применяется открытое и закрытое хеширование.
открытой хеш-таблицы
Массив, называемый таблицей сегментов и проиндексированный номерами сегментов 0, 1,...,В - 1 , содержит заголовки для В связных списков. Элемент i -го списка - это элемент исходного множества, для которого h (.х:) = i .
Представление словаря с помощью закрытой хеш-таблицы
В таблице сегментов хранятся непосредственно элементы словаря. Поэтому в каждом сегменте можно хранить только один элемент словаря. При закрытом хешировании применяется методика повторного хеширования . При попытке поместить элемент x в сегмент с номером h ( x ) , который уже занят другим элементом выбирается последовательность номеров сегментов h 1 ( x ) ,h 2 ( x ) , … , куда можно поместить элемент. Последовательно проверяется занятость каждого из этих сегментов, пока не будет найден свободный сегмент. В него помещается элемент x . Для задания номеров сегментов при повторном хешировании применяются различные методы разрешения коллизий. Например, метод линейного хеширования, метод середины квадрата, метод случайного хеширования
Упражнения:
1. Предположим, что для хеширования целых чисел в 7-сегментную хеш-таблицу используется хеш-функция h(i) = i % 7.
· приведите результирующую хеш-таблицу, если в нее вставляются точные кубы 1, 8, 27,64,125, 216,343;
· повторите предыдущий пункт для закрытой хеш-таблицы с линейной методикой разрешения коллизий.
2. Предположим, что есть закрытая хеш-таблица с 5 сегментами, хеш-функцией h(i) = i % 5 и линейной методикой разрешения коллизий. Покажите результат вставки в первоначально пустую хеш-таблицу последовательности чисел 23, 48, 35, 4, 10.
3. Реализуйте АТД “Словарь” для текстовых строк и его операторы INSERT, DELETE, MEMBER и MAKENULL
· словарь задан с помощью открытой хеш-таблицы,
· словарь задан с помощью закрытой хеш-таблицы с линейной методикой разрешения коллизий,
Раздел рабочей программы 2.1.3
Абстрактный тип данных " Отображение".
Отображение - это множество, на элементах которого определена функция отображения элементов одного типа (области определения ) на элементы другого типа (области значений ) другого типа. Отображение М ставит в соответствие элемент d типа domaintype из области определения элементу r типа rangetype из области значений: M (d ) = r .Пустое отображение не содержит никаких элементов
Операторы АТД "Отображение":
1. MAKENULL (M ). Делает отображение М пустым.
2. ASSIGN(М d, r). Делает M (d ) равным r независимо от того, как M (d ) было определено ранее.
3. COMPUTE(M, d, r). Возвращает значение true и присваивает переменной r значение M (d ), если последнее определено, и возвращает false в противном случае.
Представление отображения: отображение можно эффективно реализовать с помощью хеш-таблиц. Здесь x задает значение из области определения отображения, а элемент таблицы с номером h ( x ) – элемент из области значений.
Раздел рабочей программы 2.1.3
Очередь с приоритетами - это множество, для элементов которого задана функция приоритета (priority), т. е. для каждого элемента x множества можно вычислить функцию р( x )- приоритет элемента x , которая обычно принимает значения из множества действительных чисел, или, в более общем случае, из некоторого линейно упорядоченного множества.
АТД “Очередь с приоритетом” основано на АТД “Множество” с операторами INSERT и DELETEMIN , а также с оператором MAKENULL для инициализации структуры данных. Оператор INSERT для очереди с приоритетами понимается в обычном смысле, тогда как DELETEMIN является функцией, которая возвращает элемент с наименьшим приоритетом и в качестве побочного эффекта удаляет его из множества.
Представление очереди с помощью упорядоченного двузвязного списка.
Основная идея такой реализации заключается в том, чтобы организовать элементы очереди в виде двоичного дерева. На нижнем уровне, где некоторые листья могут отсутствовать, все отсутствующие листья могут располагаться только справа от присутствующих листьев нижнего уровня. Более существенно, что дерево частично упорядочено . Это означает, что приоритет узла v не больше приоритета любого сына узла v , где приоритет узла - это значение приоритета элемента, хранящегося в данном узле. Из рисунке видно, что малые значения приоритетов не могут появиться на более высоком уровне, где есть большие значения приоритетов.
При выполнении функции DELETEMIN возвращается элемент с минимальным приоритетом, который должен быть корнем дерева. Чтобы не разрушить дерево и сохранить частичную упорядоченность значений приоритетов на дереве после удаления корня, выполняются следующие действия: на самом нижнем уровне находится самый правый узел и временно помещается в корень дерева. Затем этот элемент спускается по ветвям дерева вниз (на более низкие уровни), по пути меняясь местами с сыновьями, имеющими меньший приоритет, до тех пор, пока этот элемент не станет листом или не встанет в позицию, где его сыновья будут иметь по крайней мере не меньший приоритет.
Представление очереди с помощью массива, содержащего узлы частично упорядоченного дерева:
В массиве A первые n позиций соответствуют n узлам дерева. Элемент A содержит корень дерева. Левый сын узла дерева A [ i ], если он существует, находится в ячейке A , а правый сын, если он существует – в ячейке A . И наоборот, если сын находится в ячейке A [ i ], то его родитель в ячейке A [ i %2] . Узлы дерева заполняют ячейки A , A , … A [ n ] последовательно уровень за уровнем, начиная с корня, а внутри уровня – слева направо. Дерево, показанное выше, будет представлено в массиве следующей последовательностью своих узлов: 3, 5, 9, 6, 8, 9, 10, 10, 18, 9.
Упражнения:
1. Нарисуйте частично упорядоченное дерево, полученное в результате вставки в пустое дерево целых чисел 5, 6, 4, 9, 3, 1 и 7. Каков будет результат последовательного применения к этому дереву трех операторов DELETEMIN?
2. Реализуйте АТД “Очередь с приоритетами” для любого типа данных и его операторы INSERT, DELETEMIN и MAKENULL
§ частично упорядоченное дерево реализуется с помощью указателей,
§ частично упорядоченное дерево реализуется с помощью массива.
Раздел рабочей программы 2.1.3
Абстрактный тип данных " Объединение множеств".
АТД представляет собой объединение объектов, каждый из которых является множеством. Основные действия, выполняемые над такой совокупностью, заключаются в объединении множеств в определенном порядке, а также в проверке принадлежности определенного объекта конкретному множеству. Эти задачи решаются с помощью операторов MERGE (Слить) и FIND (Найти). Оператор MERGE(A , В, С ) делает множество С равным объединению множеств А и В , если эти множества не пересекаются (т. е. не имеют общих элементов); этот оператор не определен, если множества А и В пересекаются. Функция FIND(x ) возвращает множество, которому принадлежит элемент х; в случае, когда х принадлежит нескольким множествам или не принадлежит ни одному, значение этой функции не определено.
Операторы АТД “Объединение множеств”:
1. MERGE (A , В) объединяет компоненты А и. В, результат присваивается или А, или В.
2. FIND (x ) - функция, возвращающая имя компонента, которому принадлежит х.
3. INITIAL (A , х ) создает компонент с именем А, содержащим только элемент х.
Представление объединения множеств с помощью массивов:
Имя множества совпадает со значением индекса массива setheaders (имя 0)
Обозначения:
setheaders – массив заголовков множеств:
§ с ount – число элементов в множестве,
§ firstelement – индекс массива names с первым элементом множества,
names – массив списков элементов множеств:
Раздел рабочей программы 2.1.3
Абстрактный тип данных “ Ориентированный граф”
Основные определения:
Ориентированный граф (орграф ) G = (V, Е) состоит из множества вершин V и множества дуг Е. Вершины также называются узлами , а дуги - ориентированными ребрами . Дуга представима в виде упорядоченной пары вершин (u , w ), где вершина и называется началом , a w - концом дуги.
Говорят также, что дуга и -> w ведет от вершины и к вершине w, а вершина w смежная с вершиной v .
Пример 1 орграфа:
Вершины орграфа можно использовать для представления объектов, а дуги - для отношений между объектами.
Путем в орграфе называется последовательность вершин v 1 , v 2 , … , vn , , для которой существуют дуги v 1 -> v 2 , v 2 , -> v 3, , ..., vn -1 , -> vn . Этот путь начинается в вершине v 1 и, проходя через вершины v 2 , v 3 , ..., vn -1 заканчивается в вершине vn . Длина пути - количество дуг, составляющих путь, в данном случае длина пути равна п - 1 . Как особый случай пути рассмотрим одну вершину v как путь длины 0 от вершины v к этой же вершине v . На рисунке последовательность вершин 1, 2, 4 образуют путь длины 2 от вершины 1 к вершине 4.
Путь называется простым , если все вершины на нем, за исключением, может быть, первой и последней, различны. Цикл - это простой путь длины не менее 1, который начинается и заканчивается в одной и той же вершине. На рисунке вершины 3, 2, 4, 3 образуют цикл длины 3.
Во многих приложениях удобно к вершинам и дугам орграфа присоединить какую-либо информацию. Для этих целей используется помеченный орграф , т. е. орграф, у которого каждая дуга и/или каждая вершина имеет соответствующие метки. Меткой может быть имя, вес или стоимость (дуги), или значение данных какого-либо заданного типа.
Пример 2 помеченного орграфа:
DIV_ADBLOCK149">
3. Алгоритм транзитивного замыкания (алгоритм Уоршелла):
Для графа G = (V , E ) алгоритм вычисляет матрицу транзитивности T , каждый элемент которой T [i , j ] = 1 только тогда, когда существует путь от вершины i к вершине j и T [ i , j ] = 0 в противном случае.
4. Алгоритм нахождения центра орграфа:
Пусть и - произвольная вершина орграфа G = (V ,Е}. Эксцентриситет (максимальное удаление) вершины и определяется как
max{минимальная длина пути от вершины w до вершины v }
w V
Центром орграфа G называется вершина с минимальным эксцентриситетом. Другими словами, центром орграфа является вершина, для которой максимальное расстояние (длина пути) до других вершин минимально.
Пример: Центром орграфа является вершина d
Эксцентр-т |
||
| ||
5. Алгоритм обхода орграфа в глубину (поиска в глубину):
При решении многих задач, касающихся ориентированных графов, необходим эффективный метод систематического обхода вершин и дуг орграфов. Таким методом является так называемый поиск в глубину - обобщение метода обхода дерева в прямом порядке. Поиск в глубину начинается с выбора начальной вершины v графа G, эта вершина помечается меткой visited (посещалась). Затем для каждой вершины, смежной с вершиной v и которая не посещалась ранее, рекурсивно применяется поиск в глубину. Когда все вершины, которые можно достичь из вершины v , будут "удостоены" посещения, поиск заканчивается. Если некоторые вершины остались не посещенными, то выбирается одна из них и поиск повторяется. Этот процесс продолжается до тех пор, пока обходом не будут охвачены все вершины орграфа G .
6. Алгоритм построения глубинного остовного дерева графа:
При обходе графа методом поиска в глубину только определенные дуги ведут к непосещённым вершинам. Такие дуги, ведущие к новым вершинам, называются дугами дерева и формируют для графа остовный лес, построенный методом поиска в глубину – глубинный остовный лес . При построении леса еще выделяются 3 типа дуг: обратные, прямые и поперечные.. Обратные дуги - такие дуги, которые в остовном лесе идут от потомков к предкам. Прямыми дугами называются дуги, идущие от предков к истинным потомкам, но которые не являются дугами дерева.
Дуги, соединяющие вершины, не являющиеся ни предками, ни потомками друг друга, называются поперечными дугами . Если при построении остовного дерева сыновья одной вершины располагаются слева направо в порядке их посещения и если новые деревья добавляются в лес также слева направо, то все поперечные дуги идут справа налево.
Например, дуги D ->С и G->D – поперечные, дуга C -> A – обратная, прямых дуг нет.
При глубинном обходе дерева часто удобно нумеровать вершины в порядке их посещения. Такие номера называются глубинными.
Представление орграфа:
§ Представление орграфа с помощью матрицы смежности:
Матрица смежности для орграфа G - это матрица А размером n n со значениями булевого типа, где A [ i , j ] = true тогда и только тогда, когда существует дуга из вершины i в вершину j. Часто в матрицах смежности значение true заменяется на 1, а значение false - на 0.
Обобщением представления орграфа с помощью матрицы смежности можно считать представление помеченного орграфа также посредством матрицы смежности, но у которой элемент A [ i , j ] равен метке дуги i -> j . Если дуги от вершины i к вершине j не существует, то значение A[i , j ] не может быть значением какой-либо допустимой метки, а может рассматриваться как "пустая" ячейка.
Матрица смежности для помеченного орграфа (пример 2):
§ Представление орграфа с помощью списков смежности:
Списком смежности для вершины i называется список всех вершин, смежных с вершиной i , причем определенным образом упорядоченный. Орграф G можно представить посредством массива HEAD (Заголовок), чей элемент HEAD [i ] является указателем на список смежности вершины i .
 |
Операторы АТД “Орграф”:
Наиболее общие операторы, выполняемые над ориентированными графами, включают операторы чтения меток вершин и дуг, вставки и удаления вершин и дуг и оператор перемещения по последовательностям дуг.
Для просмотра множества смежных вершин необходимы следующие три оператора.
1. FIRST(v ) возвращает индекс первой вершины, смежной с вершиной v . Если вершина v не имеет смежных вершин, то возвращается "нулевая" вершина nil .
2. NEXT(v , i ) возвращает индекс вершины, смежной с вершиной v, следующий за индексом i. Если i - это индекс последней вершины, смежной с вершиной v, то возвращается nil .
3. VERTEX(v ,i ) возвращает вершину с индексом i из множества вершин, смежных с v .
Упражнения:
Дан ориентированный граф (орграф):
https://pandia.ru/text/78/308/images/image043_12.gif" width="125" height="100 src=">
Пример несвязного графа:
Циклом (простым) называется путь (простой) длины не менее 3 от какой-либо вершины до нее самой. Граф называется циклическим , если имеет хотя бы один цикл. Связный ациклический граф, представляющий собой "дерево без корня", называют свободным деревом . На втором рисунке, приведенном выше, показан граф, состоящий из двух связных компонент, каждая из которых является свободным деревом. Свободное дерево можно сделать "обычным" деревом, если какую-либо вершину назначить корнем, а все ребра сориентировать в направлении от этого корня.
Свободные деревья имеют два важных свойства:
1. Каждое свободное дерево с числом вершин n , n > 1 , имеет в точности n - 1 ребер.
2. Если в свободное дерево добавить новое ребро, то обязательно получится цикл.
Пусть G = (V , Е) - связный граф, в котором каждое ребро (r , w ) помечено числом с(v , w), которое называется стоимостью ребра . Остовным деревом графа G называется свободное дерево, содержащее все вершины V графа G. Стоимость остовного дерева вычисляется как сумма стоимостей всех ребер, входящих в это дерево
Основные алгоритмы обработки неориентированных графов:
1. Построение остовного дерева минимальной стоимости (алгоритм Прима):
Строится множество вершин U , из которого "вырастает" остовное дерево. Пусть V= {1, 2, ..., n }. Сначала U = {1}. На каждом шаге алгоритма находится ребро наименьшей стоимости (u , v ) такое, что u U и v V\U , затем вершина v переносится из множества V \ U в множество U . Этот процесс продолжается до тех пор, пока множество U не станет равным множеству V .
Последовательность построения остовного дерева приведена ниже.
https://pandia.ru/text/78/308/images/image048_12.gif" width="501" height="384 src=">
3. Обход неориентированных графов методом поиска в глубину:
Для систематического обхода всех вершин графа используется поиск в глубину. Алгоритм поиска в глубину аналогичен алгоритму обхода вершин орграфа. Последний используется и для неориентированных графов, поскольку неориентированное ребро (v , w ) можно представить в виде пары ориентированных дуг v -> w и w -> v .
Обход в глубину можно использовать для построения остовного дерева.
Граф и остовное дерево, полученное при обходе его вершин методом поиска в глубину приведены ниже:
4. Обход неориентированных графов методом поиска в ширину
Другой метод систематического обхода вершин графа называется поиском в ширину . Он получил свое название из-за того, что при достижении во время обхода любой вершины v далее рассматриваются все вершины, смежные с вершиной v , т. е. осуществляется просмотр вершин "в ширину". Этот метод также можно применить и к ориентированным графам.
Так же, как и при применении поиска вглубь, посредством метода поиска в ширину при обходе графа создается остовный лес. Если после достижения вершины х при рассмотрении ребра (х, у) вершина у не посещалась ранее, то это ребро считается ребром дерева. Если же вершина у уже посещалась ранее, то ребро (х, у) будет поперечным ребром, так как оно соединяет вершины, не связанные наследованием друг друга.
Остовное дерево, полученное методом поиска в ширину показано ниже.
Представление неориентированного графа с помощью матрицы смежности:
Для представления неориентированных графов можно применять те же методы, что и для представления ориентированных графов, если неориентированное ребро между вершинами 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. Постройте:
остовное дерево минимальной стоимости посредством алгоритма Прима;
остовное дерево минимальной стоимости с помощью алгоритма Крускала;
остовное дерево методом поиска в глубину, начиная с вершин а и d;
остовное дерево методом поиска в ширину, начиная с вершин а и d.
2. Реализуйте алгоритмы Прима и Крускала.
3. Реализуйте построение остовного дерева методом поиска в глубину
§ для неориентированного графа представленного с помощью матрицы смежности,
§ для неориентированного графа представленного с помощью списков смежности.
4. Реализуйте построение остовного дерева методом поиска в ширину
§ для неориентированного графа представленного с помощью матрицы смежности,
§ для неориентированного графа представленного с помощью списков смежности.
Абстрактный тип данных Общие положения о данных Абстрактный тип данных общие положения спецификация, представление, реализация 1
Что такое данные? Набор различных информационных объектов, над которыми выполняются те или иные действия операторами программы, называются данными. Данные - непременный атрибут любой программы. Ими могут быть: - отдельные биты; - последовательность независимых битов; -числа в разных формах представления; -байты и группы независимых байтов; -массивы чисел; -связные списки; -отдельные файлы и системы файлов. 2
Универсальное представление этого многообразия данных сложно и нецелесообразно Целесообразно разделить их на типы 3
Что такое тип данных? Тип данных определяется: – Форматом представления в памяти компьютера по определенным соглашениям алгоритмического языка, но без необходимости вычислений; – Множеством допустимых значений, которые может принимать принадлежащая к выбранному типу переменная или константа; – Множеством допустимых операций, применимых к этому типу. 4
Примеры типов данных Целочисленные типы Вещественный тип Логический тип Символьный тип Перечисляемый тип Интервальный тип Указатели 5
Целочисленные типы имеется пять предопределенных целочисленных типов: Shortint, Integer, Longint, Byte и Word. Каждый тип обозначает определенное подмножество целых чисел. Значение одного целочисленного типа может быть явным образом преобразовано к другому целочисленному типу с помощью приведения типов. 6
Вещественный тип К вещественному типу относится подмножество чисел, представляемых в формате с плавающей точкой и с фиксированным числом цифр. Запись значения в формате с плавающей запятой обычно включает три значения - m, b и e - таким образом, что m * b ^ e = n, где b всегда равен 2, а m и e являются целочисленными значениями в диапазоне вещественного типа. Эти значения m и e далее определяют диапазон представления и точность вещественного типа. Пример: 0. 143 E+22, где m - 0. 143; b=2(подразумевается), e=22. Имеется пять видов вещественных типов: вещественное (Real), с одинарной точностью (Single), с двойной точностью (Double), с повышенной точностью (Extended) и сложное (Comp). 7
Логический тип Существует 4 предопределенных логических (булевских) типа: Boolean, Byte. Bool, Word. Bool и Long. Bool. Значения булевского типа обозначаются встроенными идентификаторами констант False и True. Логические переменные могут использоваться для хранения результатов каких - либо логических вычислений. Для булевых переменных разрешены только 2 операции сравнения "="(равно) и ""(неравно). 8
Символьный тип Множеством значений этого типа являются символы, упорядоченные в соответствии с расширенным набором символов кода ASCII. Это буквы ["A". . . "Z", "a". . . "z"], цифры ["0". . . "9"], знаки препинания и специальные символы. Переменная этого типа в памяти занимает один байт. 9
Перечисляемый тип Перечислимые типы определяют упорядоченные множества значений через перечисление идентификаторов, которые обозначают эти значения. Упорядочение множеств выполняется в соответствии с последовательностью, в которой перечисляются идентификаторы. Type Week = (Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday); 10
Интервальный тип Интервальный тип представляет собой диапазон значений из порядкового типа. Определение интервального типа включает наименьшее и наибольшее значение в поддиапазоне. Type Interval = 0. . . 1000; Такая декларация типа указывает компилятору, что для переменных этого типа допустимы только числа из указанного диапазона. Тем самым в программе могут быть автоматически организованы проверки корректности операций присвоения для этих переменных. 11
Общее для типов данных Каждому из типов данных соответствует множество простых операций. INTEGER-операции +, -, *, div, mod REAL - операции + , -, *, / BOOLEAN- операции - конъюнкция (и), дизъюнкция V (или), отрицание (не) CHAR-операции ORD (с) -N: (С в ASCII), CHR (I) I -тый символ в ASCII По мере возрастания объемов и сложности представления информации возникает необходимость в удобных формах ее представления, хранения и обработки. 12
Определение абстрактный тип данных (АТД или abstract data type, или ADT), - это множество абстрактных объектов, представляющих элементы данных, и определенные на нем наборы операций, которые могут быть выполнены над элементами этого множества. 13
АТД – обобщение типов данных Абстрактные типы данных (АТД) можно рассматривать как средство расширения языков программирования. Сравним абстрактный тип данных с таким знакомым понятием, как процедура. Процедуру можно рассматривать как обобщённое понятие оператора. Две характерные особенности процедур – обобщение и инкапсуляция, отлично характеризуют абстрактные типы данных. АТД можно рассматривать как обобщение простых типов данных (целых, действительных и т. д.), точно также как процедура является обобщением простых операторов (+, - и т. д.) 14
Преимущества АТД Абстрактные структуры данных предназначены для удобного хранения и доступа к информации. Они предоставляют удобный интерфейс для типичных операций с хранимыми объектами, скрывая детали реализации от пользователя. Конечно, это весьма удобно и позволяет добиться большей модульности программы. 15
Пример Для автоматизированного управления температурой в различных комнатах большого здания полезным АТД был бы ТЕРМОСТАТ. В программе может быть много переменных типа ТЕРМОСТАТ, соответствующих реальным термостатам в различных помещениях здания. АТД может быть описан своим именем, множеством значений и допустимыми операциями так же, как и любой другой тип данных. Описание для типа ТЕРМОСТАТ: – Тип данных: ТЕРМОСТАТ – Область значений: температура может изменяться в диапазоне от 0 до 50 градусов (по Цельсию). – Операции: Выше, Ниже, Установить, Проверить, Тревога. (Можно придумать много полезных операций, но слишком большое их количество ухудшает абстракцию) 16
Уровни абстракции Уровни абстракции напоминают слои программного обеспечения. Высшие уровни абстракции отражают представление пользователя о решении задачи. Нижние уровни абстракции – возможности языка программирования. 17
Пример абстракции на уровне пользователя Архитектор представляет дом в виде стен, полов, окон, дверей и т. д. В этом случае тип данных Рисунок. Двери мог бы стать хорошим абстрактным типом. Тип данных: Рисунок. Двери Операции: Рисовать. Дверь Стереть. Дверь Рисовать. Двойную. Дверь ……. Рисунок. Двери являются абстракцией высокого уровня, отражающего взгляд пользователя на проблему 18
Пример абстракции на уровне программиста Программист может предложить другой уровень абстракции для этих объектов, например, прямоугольник. Тип данных: Прямоугольник Операции: Рисовать. Прямоугольник Стереть. Прямоугольник Разделить. Прямоугольник. На. Части ……. Прямоугольник – абстракция более низкого уровня, поскольку она ближе к реализации. 19
Конструкторы АТД Каждый АТД должен содержать операции построения значений своего типа. Такие операции называются конструкторами. Конструкторов должно быть достаточно для порождения всего множества значений данного типа. АТД, удовлетворяющий этому свойству, называется полным. Неполный АТД – ошибка проектирования. 20
Рекомендации к выбору операций абстрактного типа данных Целесообразно включение следующих операций: – операции-конструкторы, – операции проверки, – операции преобразования типов, – операции ввода-вывода, – операции копирования, – операции-селекторы. Постарайтесь свести к минимуму число операций. Простой АТД легче понять. Поддерживайте связь операций с выбранной абстракцией типа. 21
Первичный конструктор Операции, создающие новые значения АТД вне зависимости от его предшествующего значения, называются первичными конструкторами. Каждый АТД включает по меньшей мере один первичный конструктор: без него невозможно сформировать начальное значение. 22
Использование скрытых типов Абстрактные типы данных лучше объявлять в виде скрытых типов. Это позволяет переместить описание структуры данных в модуль реализации, где оно преимущественно используется. Они также обеспечивают возможность предотвращения прямого доступа к компонентам типа со стороны импортера. Поскольку скрытый тип всегда реализуется с помощью указателя, то в АТД должны быть включены три операции. – Создать - операция, создающая узел соответствующей структуры. – Уничтожить - операция по освобождению памяти узла скрытого типа. – Присвоить - операция копирования полей динамической структуры узла скрытого типа. 23
Что такое спецификация и реализация у абстрактного типа данных Абстрактный тип данных - это способ определения некоторого понятия в виде класса объектов с некоторыми свойствами и операциями. В языке программирования такое определение оформляется как специальная синтаксическая конструкция, называемая в разных языках капсулой, модулем, кластером, классом, пакетом, формой и т. д. Эта конструкция в самой развитой форме содержит: спецификацию типа данных, включающую описание интерфейса (имя определяемого типа, имена операций с указанием их профилей) и абстрактное описание операций и объектов, с которыми они работают, некоторыми средствами спецификации; реализацию типа данных, включающую конкретное описание тех же операций и объектов. 24
Классификация типов данных по способу описания и защиты пакетированный, если описание типа данных собрано в одном месте (в одном пакете), т. е. его объекты и операции объединены в одно понятие; он имеет определение, которое может содержать, однако, лишь его реализацию; инкапсулированный, если тип данных пакетированный, его определение содержит описание интерфейса и реализацию, а также предусмотрена инкапсуляция реализации; абстрактный, если тип данных инкапсулированный и его спецификация включает абстрактное описание. 25
Составляющие спецификации Программирование, как процесс, начинается с постановки задачи (ее определения), или спецификации задачи. Далее повсеместно в тексте используются спецификации, состоящие из шести составляющих: – Название - название решаемой задачи; – Описание - несколько предложений, описывающих суть задачи; – Вход - детальное описание предполагаемой формы входных данных; – Выход - детальное описание предполагаемой формы выходных данных; – Ошибки - подробный список ситуаций, возникающих при неправильных входных данных; – Пример - пример выполнения в терминах вход-выход. 26
П р и м е р спецификации Абстрактный тип данных СТЕК, реализующий широко известную структуру данных, которая характеризуется тем, что в нее можно "поместить" некоторый элемент и "выбрать" из нее элемент, помещенный туда самым последним. Синтаксическая часть спецификации типа данных СТЕК имеет вид type СТЕК specification is СОЗДАТЬ: function () return (@); ВСТАВИТЬ: function (integer; @) return (@); УДАЛИТЬ: function (@) return (@); ВЕРШИНА: function (@) return (integer); ПУСТ: function (@) return (boolean); end specification; Здесь операция СОЗДАТЬ выдает в качестве результата пустой стек, ВСТАВИТЬ - стек с добавленным на "верх" его элементом, УДАЛИТЬ - стек с удаленным "верхним" элементом, ВЕРШИНА - значение "верхнего" элемента стека, ПУСТ - признак пустоты стека. Элементами стека здесь могут быть только целые числа. 27
РЕАЛИЗАЦИЯ АБСТРАКТНОГО ТИПА ДАННЫХ Реализацию удобнее делать с помощью объектноориентированных языков программирования, таких как C++ или Java, в которых абстрактные типы данных поддерживаются с помощью классов Реализация АТД включает конкретное описание объектов определяемого типа и реализацию операций этого типа. Это означает, что объекты описываются либо как данные простых типов, либо как массивы, записи или объединения. Причем используются предопределенные типы данных или АТД, определенные ранее. Реализация операций состоит в описании подпрограмм, выполняющих необходимые действия с указанными объектами. Например операции +, *, =. . и т. п, но при этом скрывается сама реализация этих операций. 28
