Государственное образовательное учреждение высшего профессионального образования «Московский государственный технический университет им. Н.Э. Баумана»
Калужский филиал
Факультет"Фундаментальных Наук"
Кафедра "Программного обеспечения ЭВМ, информационных технологий и прикладной математики" (ФН1-КФ)
КУРСОВАЯ РАБОТА
ПО КУРСУ: «ПРОГРАММИРОВАНИЕ НА С++»
На тему: «Работа со списками»
Калуга - 2008
Список – это динамическая структура, иными словами, массив данных некоторого типа, размеры которого могут меняться в процессе выполнения программы. Списки очень широко используются в информационных технологиях. В том числе, в области машинной графики для описания графических примитивов. Так, например, некоторая геометрическая модель может быть представлена списком вершин, линий или других объектов любой сложности.
Данная программа представляет собой редактор изображений, позволяет создавать графические изображения, в основе которых лежат некоторые графические примитивы, такие как линии, прямоугольники и кривые Безье, а также выделять и удалять части объектов и менять цвет объектов. Все графическое изображение представляется списком линий. Все возможные в программе операции с объектами – это наглядное представление операций со списками, которые осуществляются при помощи нескольких классов для работы с ними.
Создать несколько классов, реализующих работу со списками и применить эти классы к задаче построения геометрических фигур, тем самым продемонстрировав их работоспособность.
Для реализации поставленной задачи используется стек (он представляет собой список типа LIFO, в котором последний добавленный элемент считывается первым), а также обратная стеку динамическая структура – очередь (FIFO). В программе используются методы объектно-ориентированного программирования для облегчения способа решения задачи: шаблоны классов (для записи в список элементов различного типа), наследование (для сокращения объема программного кода), виртуальные функции (для корректного переопределения методов различных классов), абстрактный класс (для общего описания основных функций).
1.3Исследование поставленной задачи
1.3.1 Создание стека
Стек представляет собой список типа LIFO, в котором последний добавленный элемент считывается первым. Для создания стека в программе используется структура List, содержащая поле ссылки на следующий элемент и шаблонный тип данных в качестве информационного поля. Для программной реализации стека необходимо описать 2 переменные указанного выше типа List: p (указатель на текущий элемент) и top (указатель на вершину списка). При добавлении элемента в стек, новому элементу присваивается ссылка на вершину стека, а затем и он сам становится вершиной. Таким образом, стек растет как бы назад:
p=new list;
p->next=top;
p->inf=value;
top=p;
1.3.2 Создание очереди
Очередь очень похожа на стек за исключением того, что элементы в ней располагаются в нормальном порядке, а не в обратном. Обход очереди и обход стека идентичны. Учитывая это сходство, можно создать класс очереди как наследника класса стека, переопределив в нем только функции создания и добавления элемента. Так как в очереди первый элемент должен быть создан заранее, то заносим его создание в конструктор класса:
top=new list;
top->next=NULL;
p=top;
Добавление элемента в очередь тоже отличается от добавления элемента в стек. Здесь вершина списка остается на своем месте, меняется только положение текущего указателя, а элементы заносятся в прямом порядке, и ссылка на новый элемент создается из текущего, а не наоборот, как было в стеке, после чего новый элемент становится текущим:
p->next=new list;
p->next->next=NULL;
p->inf=value;
p=p->next;
1.4 Актуальность поставленной задачи
Исследуемые алгоритмы применяются для решения многих прикладных задач, особенно в области машинной графики. Работа со списками очень важна при построении графических моделей, моделировании графических приложений, создании видеоигр, а также для организации памяти под данные пользовательских типов и так далее. Списки – это основная динамическая структура, на которой базируются остальные.
2.1 Обоснование выбора средства программирования
Для написания данной курсовой работы был использован язык Borland C++ Builder 6. C++ Builder позволяет быструю визуальную разработку приложений на языке C++. Профессиональные средства языка C++ интегрированы в визуальную среду разработки. Интегрированная среда разработки объединяет редактор форм, инспектор объектов, палитру компонент, администратор проекта и полностью интегрированные редактор кода и отладчик – инструменты быстрой разработки программных приложений, обеспечивающие полный контроль над кодом и ресурсами. C++Builder воплощает важнейшие аспекты объектно-ориентированного программирования в удобном для пользования инструменте визуального проектирования, что лучше всего подходит для реализации и отображения результатов работы программы.
Для удобной работы со списком необходимо представить его как отдельный тип данных. C++ позволяет определять пользовательские типы, а также определять набор операций, производимых над экземплярами этого типа. Ключевым понятием C++ является класс. Класс – это тип данных, определяемый пользователем, переменные которого являются объектами. Т.о., в программе, созданной на C++, определение класса должно быть определением типа данных, содержащим информацию о значениях, которые могут храниться в его переменных, а также о функциях-членах этого класса.
В языке существует возможность одиночного и множественного наследования. При одиночном наследовании базовым является один класс, а при множественном наследовании базовыми классами должны быть несколько классов.
Виртуальные функции являются средством позднего связывания в языке С++.
Виртуальной функцией называется функция, которая еще, не будучи определённой каким-либо образом, может использоваться. Эта технология, когда определение реализации процедуры откладывается до времени выполнения программы, называется поздним или динамическим связыванием.
Для удобства работы со списком нужно предоставить специальные функции, которые дают возможность без изменений в реализации и описании классов получить дополнительную информацию о нем. С этой целью может быть использован реализованный в С++ механизм дружественности и создан дружественный класс, который, оперируя внутренними методами абстрактного типа данных, возвращает дополнительную информацию, полезную при работе со структурой.
Т.о. язык С++ содержит все необходимые возможности для реализации списковой структуры, а также возможность работы с ней как со встроенным типом данных, который к тому же может быть со временем преобразован и расширен.
Программа может применяться для создания графических изображений
Для реализации этой задачи необходимо создать список, в который будут заноситься объекты различных пользовательских типов (например, линии). Список должен обладать всеми необходимыми методами, используемыми для обработки находящихся в нем данных: добавление, удаление, поиск, изменение и выборка элементов.
Пользователь может выбрать один из графических примитивов, создаваймых на основе линий, например, кривая Безье, установить цвет объекта и его позицию на плоскости рисунка. После создания объект появляется на экране, а список составляющих его линий выводится в ListBox-элемент на форме. Пользователь имеет возможность менять цвет объекта, удалять объект, а также удалять отдельные составляющие его линии.
2.3 Описание логической структуры
Курсовая работа представляет собой программу, написанную на C++ Builder 6. Для упрощения программного кода используется иерархия классов.
Абстрактный класс Spisok содержит основные свойства и методы, которые необходимы всем его наследникам, то есть, общие для всех списков данные: структура List, указатели *top и *p, чисто-виртуальные функции:
- add(Data value, AnsiString name). Добавление элемента с именем «Name», содержащего информацию «Data». Data – это шаблонный тип данных, который может принять значение любого переданного в класс типа. Это позволяет использовать один и тот же класс списка для хранения данных разных типов. Функция не возвращает значений.