Динамические структуры данных: дек
Министерство образования и науки РФФедеральное агентство по образованиюГосударственное образовательное учреждение высшего профессионального образования«Омский государственный технический университет»Кафедра прикладной математики и информационных системКурсовая работа по дисциплине: «Высокоуровневые методы»Омск 2008СодержаниеВведениеПостановка задачиДинамические структуры данных: декОписание алгоритмаПриложение 1. Текст программыПриложение 2. ФормаВведениеОбъектно-ориентированное программирование – это естественное продолжение структурного программирования. Объектно-ориентированное программирование требует сложных программных действий, но делает создание программы достаточно легким. В результате создаются совершенные коды, которые легко распространять и просто поддерживать. Однажды созданный для приложения объект можно использовать в других приложениях. Повторное использование объектов намного сокращает время разработки и увеличивает производительность труда. Объектно-ориентированное программирование основано на использовании классов. Использование классов – это основное отличие языка С++ от языка С, на котором он основан.Класс наряду с понятием «Объект», является важным понятием объектно-ориентированного подхода в программировании. Под классом подразумевается некая сущность, которая задает некоторое общее поведение для объектов. Таким образом, любой объект может принадлежать или не принадлежать определенному классу, то есть обладать или не обладать поведением, которое данный класс подразумевает. Класс определяет для объекта правила, с помощью которых с объектом могут работать другие объекты, обычно это делается с помощью определения методов класса. Кроме того, классы могут находиться друг с другом в различных отношениях, таких как наследование или агрегация.Класс - это собрание связной информации, которая включает в себя и данные, и функции. Класс – это дальнейшее развитие структур: в них тоже объединяется данные разных типов. Это такой же шаблон, под который, как и под структуру, память выделяется только тогда, когда мы создаем «переменную типа этого шаблона». Класс определяется как список своих членов. К членам класса относятся его поля (свойства) и функции (методы).Каждому члену класса можно установить его область доступа (access control level). Область доступа члена класса определяет участки кода, из которых к этому члену будет возможно обращаться. В большинстве объектно-ориентированных языков программирования поддерживаются следующие области доступа:private (закрытый, внутренний член класса) — обращения к члену допускаются только из кода методов класса, в котором этот член определён. Любые наследники класса уже не смогут получить доступ к этому члену; protected (защищённый, внутренний член иерархии классов) — обращения к члену допускаются из кода методов класса, в котором этот член определён, или из любых его классов-наследников; public (открытый член класса) — обращения к члену допускаются из любого кода. В каждом классе определены характеристики тех объектов, которые использует данный класс. В классе также задаются программы, называемые методами, которые обрабатывают характеристики объектов, принадлежащих данному классу. Поведение объекта в реальном мире определяется его характеристиками. Изменяя значение характеристик, мы получим разное поведение объектов. Когда мы создаем экземпляр класса и определяем значение его конкретных характеристик, мы получаем конкретный объект. В составе класса существует специальный метод, который формирует экземпляр класса. Этот метод носит название конструктора. В противоположность конструктору, существует программа-деструктор, которая уничтожает экземпляр класса в памяти.Постановка задачиСоздать класс «Дек». Реализовать методы:Добавление элемента в начало дека. Удаление элемента из начала дека. Добавление элемента в конец дека. Удаление элемента из конца дека. Проверка дека на наличие в нем элементов. Динамические структуры данных: декВ языках программирования существует такой способ выделения памяти под данные, который называется динамическим. В этом случае память под величины отводится во время выполнения программы. Такие величины называются динамическими. Раздел оперативной памяти, распределяемый статически, называется статической памятью; динамически распределяемый раздел памяти называется динамической памятью (динамически распределяемой памятью). Использование динамических величин предоставляет программисту ряд дополнительных возможностей. Во-первых, подключение динамической памяти позволяет увеличить объем обрабатываемых данных. Во-вторых, если потребность в каких-то данных отпала до окончания программы, то занятую ими память можно освободить для другой информации. В-третьих, использование динамической памяти позволяет создавать структуры данных переменного размера. Работа с динамическими величинами связана с использованием еще одного типа данных — ссылочного типа. Величины, имеющие ссылочный тип, называются указателями. Указатель содержит адрес поля в динамической памяти, хранящего величину определенного типа. Сам указатель располагается в статической памяти. Структурированные типы данных, такие, как массивы, множества, записи, представляют собой статические структуры, так как их размеры неизменны в течение всего времени выполнения программы.Часто требуется, чтобы структуры данных меняли свои размеры в ходе решения задачи. К таким структурам относятся списки (однаправленные, двунаправленные, кольцевые однаправленные и кольцевые двунаправленные), стеки, деки, очереди, деревья и другие. Описание динамических структур с помощью массивов, записей и файлов приводит к неэкономному использованию памяти ЭВМ и увеличивает время решения задач.Адрес величины — это номер первого байта поля памяти, в котором располагается величина. Размер поля однозначно определяется типом.Динамическая структура называется деком
Другие файлы:
Динамические структуры данных: двусвязные списки и двоичные деревья
Линейные динамические структуры. Построение списочной структуры, состоящей из трехнаправленного и двух однонаправленных списков, связанных между собой...
Динамические структуры данных
Разработка алгоритмов на динамических структурах данных. Описание структуры данных "стек". Процедуры добавления и удаления элемента, очистки памяти. К...
Основы структур данных
Способы ограждения пользователей от деталей фактического устройства данных. Список описателей переменных, указателей или массивов. Статические или дин...
Динамические структуры данных
Проблемы с организацией данных. Определение и классификация динамических структур данных. Линейные односвязные, двухсвязные, кольцевые списки. Очередь...
Динамические структуры данных
Главной особенностью динамических структур является возможность изменения их структуры и размера в процессе работы программы. Это существенно повышает...
