Работа со списками

БОЛЬШАЯ ЛЕНИНГРАДСКАЯ БИБЛИОТЕКА - РЕФЕРАТЫ - Работа со списками

Работа со списками

5

Государственное образовательное учреждение высшего профессионального образования «Московский государственный технический университет им. Н.Э. Баумана»

Калужский филиал

Факультет"Фундаментальных Наук"

Кафедра "Программного обеспечения ЭВМ, информационных технологий и прикладной математики" (ФН1-КФ)

КУРСОВАЯ РАБОТА

ПО КУРСУ: «ПРОГРАММИРОВАНИЕ НА С++»

На тему: «Работа со списками»

Калуга - 2008

АННОТАЦИЯ

Список - это динамическая структура, иными словами, массив данных некоторого типа, размеры которого могут меняться в процессе выполнения программы. Списки очень широко используются в информационных технологиях. В том числе, в области машинной графики для описания графических примитивов. Так, например, некоторая геометрическая модель может быть представлена списком вершин, линий или других объектов любой сложности.

Данная программа представляет собой редактор изображений, позволяет создавать графические изображения, в основе которых лежат некоторые графические примитивы, такие как линии, прямоугольники и кривые Безье, а также выделять и удалять части объектов и менять цвет объектов. Все графическое изображение представляется списком линий. Все возможные в программе операции с объектами - это наглядное представление операций со списками, которые осуществляются при помощи нескольких классов для работы с ними.

ИССЛЕДОВАТЕЛЬСКАЯ ЧАСТЬ

1.1 Постановка задачи

Создать несколько классов, реализующих работу со списками и применить эти классы к задаче построения геометрических фигур, тем самым продемонстрировав их работоспособность.

1.2 Способы реализации

Для реализации поставленной задачи используется стек (он представляет собой список типа 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. КОНСТРУКТОРСКАЯ ЧАСТЬ

2.1 Обоснование выбора средства программирования

Для написания данной курсовой работы был использован язык Borland C++ Builder 6. C++ Builder позволяет быструю визуальную разработку приложений на языке C++. Профессиональные средства языка C++ интегрированы в визуальную среду разработки. Интегрированная среда разработки объединяет редактор форм, инспектор объектов, палитру компонент, администратор проекта и полностью интегрированные редактор кода и отладчик - инструменты быстрой разработки программных приложений, обеспечивающие полный контроль над кодом и ресурсами. C++Builder воплощает важнейшие аспекты объектно-ориентированного программирования в удобном для пользования инструменте визуального проектирования, что лучше всего подходит для реализации и отображения результатов работы программы.

Для удобной работы со списком необходимо представить его как отдельный тип данных. C++ позволяет определять пользовательские типы, а также определять набор операций, производимых над экземплярами этого типа. Ключевым понятием C++ является класс. Класс - это тип данных, определяемый пользователем, переменные которого являются объектами. Т.о., в программе, созданной на C++, определение класса должно быть определением типа данных, содержащим информацию о значениях, которые могут храниться в его переменных, а также о функциях-членах этого класса.

Механизм наследования позволяет определять новые классы на основе уже имеющихся. Класс, на основе которого создаётся новый класс, называется базовым (родительским) классом, а новый - производным (наследником). Непосредственным базовым классом называется такой класс, который входит в список базовых классов при определении класса. Любой производный класс может в свою очередь стать базовым для других создаваемых классов. Т.о. формируется направленный граф иерархии классов, а при объявлении объектов и иерархия объектов. В иерархии объектов производный объект имеет возможность доступа к элементам данных и методам объектов, типизированных базовым классом.

В языке существует возможность одиночного и множественного наследования. При одиночном наследовании базовым является один класс, а при множественном наследовании базовыми классами должны быть несколько классов.

Виртуальные функции являются средством позднего связывания в языке С++.

Виртуальной функцией называется функция, которая еще, не будучи определённой каким-либо образом, может использоваться. Эта технология, когда определение реализации процедуры откладывается до времени выполнения программы, называется поздним или динамическим связыванием.

Для удобства работы со списком нужно предоставить специальные функции, которые дают возможность без изменений в реализации и описании классов получить дополнительную информацию о нем. С этой целью может быть использован реализованный в С++ механизм дружественности и создан дружественный класс, который, оперируя внутренними методами абстрактного типа данных, возвращает дополнительную информацию, полезную при работе со структурой.

Т.о. язык С++ содержит все необходимые возможности для реализации списковой структуры, а также возможность работы с ней как со встроенным типом данных, который к тому же может быть со временем преобразован и расширен.

2.2 Функциональное назначение

Программа может применяться для создания графических изображений

Для реализации этой задачи необходимо создать список, в который будут заноситься объекты различных пользовательских типов (например, линии). Список должен обладать всеми необходимыми методами, используемыми для обработки находящихся в нем данных: добавление, удаление, поиск, изменение и выборка элементов.

Пользователь может выбрать один из графических примитивов, создаваймых на основе линий, например, кривая Безье, установить цвет объекта и его позицию на плоскости рисунка. После создания объект появляется на экране, а список составляющих его линий выводится в ListBox-элемент на форме. Пользователь имеет возможность менять цвет объекта, удалять объект, а также удалять отдельные составляющие его линии.

2.3 Описание логической структуры

Курсовая работа представляет собой программу, написанную на C++ Builder 6. Для упрощения программного кода используется иерархия классов.

Абстрактный класс Spisok содержит основные свойства и методы, которые необходимы всем его наследникам, то есть, общие для всех списков данные: структура List, указатели *top и *p, чисто-виртуальные функции:

- add(Data value, AnsiString name). Добавление элемента с именем «Name», содержащего информацию «Data». Data - это шаблонный тип данных, который может принять значение любого переданного в класс типа. Это позволяет использовать один и тот же класс списка для хранения данных разных типов. Функция не возвращает значений.

- remove(int index). Удаляет элемент с порядковым номером «Index» из списка. Для этого создается дополнительный указатель на удаляемый элемент, а ссылка с предыдущего элемента переносится на следующий, после чего, отделенный от списка элемент удаляется из памяти стандартной процедурой delete(*list). Функция не возвращает значений.

- change(int index, Data value). Изменяет значение элемента с порядковым номером «Index» на значение «Data».

- int count(). Возвращает число элементов в списке. Подсчет производится с помощью цикла с предусловием до тех пор, пока не будет достигнут конец списка. На каждом шаге цикла происходит инкремент счетчика.

- Data getvalue(int index). Возвращает информационное поле элемента с порядковым номером «Index». Происходит обход списка до тех пор, пока не будет достигнут порядковый номер (цикл с параметром). После этого возвращается информационное поле.

- AnsiString getname(int index). Возвращает имя элемента с порядковым номером «Index». Работает аналогично предыдущей функции.

- int search (AnsiString name). Возвращает порядковый номер первого найденного элемента с именем «Name».

Класс Spisok является абстрактным, так как он содержит выше указанные чисто-виртуальные функции.

Класс Stack - наследник класса Spisok. В нем переопределяются все чисто-виртуальные функции предка, им присваивается описанное выше назначение.

Класс Queue - очередь - наследник класса Spisok. Этот класс может использовать все функции предка применительно к своим свойствам, но очередь все же отличается от стека своим созданием и добавлением элементов, поэтому функция добавления элементов в этом классе переопределяется еще раз, уже для очереди.

Класс TLine - линия. Это основной графический примитив программы. Остальные объекты строятся из линий. Линия передается в качестве информационного поля в классы списков. Линия имеет несколько свойств:

- p1, p2 - точки, каждая из которых имеет 2 координаты: x и y. Это конечные точки линии (отрезка). Точка описывается отдельной структурой point.

- Color - цвет линии. Используется стандартный тип C++ Builder - TColor.

- Secondary - логическая переменная, показывающая, является ли данная линия вспомогательной для построения объекта, либо она основная. Для более наглядного представления способа построения объектов в программе используются вспомогательные линии, которые при желании пользователь может отключать.

Методы класса TLine:

- setline(point p1,point p2,long int col,bool sec). Устанавливает значения свойств линии в соответствии с переданными параметрами.

- point cut(float k). Возвращает точку на линии, которая находится на расстоянии, равном k*<длина линии> от ее первого конца.

Класс BCurve - Кривая Безье. Среди свойств объекта: имя, цвет основных и вспомогательных линий, 2 опорные линии и коэффициент гладкости k (чем больше коэффициент, тем больше линия похожа на ломаную. Максимум k=0.99, минимум - 0.01. Оптимальное значение k=0.25). Класс имеет 2 функции:

- queue <Tline> Create(float,Tline,Tline,TColor,TColor,bool,AnsiString). Возвращает список линий, принадлежащих созданной по переданным параметрам кривой Безье.

- queue <Tline> Load().Возвращает список линий, принадлежащих созданной по заранее установленным параметрам кривой Безье.

Класс TRectangle - Прямоугольник. Создает список из 4-х линий по переданным параметрам с помощью функции: queue <Tline> Create(int x1,int y1,int x2,int y2,TColor col).

2.4 Абстрактные типы данных, определенные в программе

АТД тип данных, определяемый только через операции, которые могут выполняться над соответствующими объектами безотносительно к способу представления этих объектов.

2.4.1 ADT Spisok

Данные

Указатель на вершину списка элементов и на текущий элемент;

Структура, описывающая список элементов;

Операции

Add:

Вход: значение, имя;

Предусловие: нет;

Процесс: добавление элемента в список;

Выход: нет;

Постусловия: нет;

Remove:

Вход: порядковый номер;

Предусловие: нет;

Процесс: удаление элемента из списка;

Выход: нет;

Постусловия: нет;

Search:

Вход: имя;

Предусловие: нет;

Процесс: поиск элемента в списке;

Выход: порядковый номер найденного элемента;

Постусловия: нет;

Change:

Вход: порядковый номер, значение;

Предусловие: нет;

Процесс: изменение выбранного элемента на элемент с переданным значением;

Выход: нет;

Постусловия: нет;

Count:

Вход: нет;

Предусловие: нет;

Процесс: подсчет количества элементов в списке;

Выход: количество элементов в списке;

Постусловия: нет;

Getvalue:

Вход: порядковый номер;

Предусловие: нет;

Процесс: получение информационного поля элемента;

Выход: информационное поле элемента;

Постусловия: нет;

Getname:

Вход: порядковый номер;

Предусловие: нет;

Процесс: получение имени элемента;

Выход: имя элемента;

Постусловия: нет;

Конец ADT Spisok

2.4.2 ADT Tline

Данные

2 конечные точки, цвет, тип линии;

Операции

Setline:

Вход: 2 конечные точки, цвет, тип линии;

Предусловие: нет;

Процесс: установка данных объекта;

Выход: нет;

Постусловия: нет;

Cut:

Вход: коэффициент k;

Предусловие: нет;

Процесс: вычисление точки на линии, которая находится на расстоянии, равном k*<длина линии> от ее первого конца;

Выход: точка на линии, которая находится на расстоянии, равном k*<длина линии> от ее первого конца;

Постусловия: нет;

Конец ADT TLine

2.4.3 ADT BCurve

Данные

Цвет вспомогательных и основных линий, 2 базовые линии, коэффициент, имя;

Операции

Create:

Вход: Цвет вспомогательных и основных линий, 2 базовые линии, коэффициент, имя;

Предусловие: нет;

Процесс: создание кривой Безье;

Выход: Список линий, принадлежащих данной кривой;

Постусловия: нет;

Load:

Вход: нет;

Предусловие: нет;

Процесс: создание кривой Безье на основе уже имеющихся в классе данных;

Выход: Список линий, принадлежащих данной кривой;

Постусловия: нет;

Конец ADT BCurve

2.4.4 ADT TRectangle

Данные

нет;

Операции

Create:

Вход: Цвет 4 координаты и цвет;

Предусловие: нет;

Процесс: создание прямоугольника;

Выход: Список линий, принадлежащих данному прямоугольнику;

Постусловия: нет;

Конец ADT TRectangle

3. ТЕХНОЛОГИЧЕСКАЯ ЧАСТЬ

3.1 Руководство программиста

3.1.1 Назначение и условия применения программы

Данная программа предназначена для создания графических изображений на основе нескольких графических примитивов. Поддерживает интерактивное изменение параметров объекта, позволяет выделять и удалять отдельные объекты или их части.

3.1.2 Минимальные системные требования:

1) 64 Мб оперативной памяти.

2) 100 Кб свободного места на жёстком диске

3) Клавиатура и манипулятор мышь

4) Операционная система Windows 9x/ME/NT/2000/XP

3.1.3 Установка программы

Чтобы установить программу, нужно целиком скопировать на целевой компьютер *.exe файл программы.

Запустить файл Editor.exe.

3.1.4 Структура программы.

Алгоритм программы

При запуске программы выполняются действия:

· Выбор объекта с помощью клавиатуры или с помощью мыши.

· Указание места расположения объекта на плоскости рисунка с помощью мыши (2 или 3 клика).

· Работа с объектами: их выделение с помощью ListBox-элемента и изменение их параметров или удаление объектов или их частей.

· Окончание программы происходит при закрытии окна.

· Создание объектов

После того, как указано место расположения объекта, происходит его создание. Каждый объект представляет собой список линий, поэтому, для создания любого объекта программа создает новый экземпляр класса очереди (Queue), если он не был создан до этого, и добавляет в него полученный из функции Create(<параметры объекта>) соответствующего объекта список линий. Для того чтобы предоставить пользователю возможность работы с полученным списком (а значит и объектом), этот список заносится в ListBox-элемент на форме, где пользователь сможет получить к нему доступ.

· Изменение объектов и их частей

Для изменения объектов используется функция класса списков Change(int, Data). При выборе пользователем элемента ListBox'а (отдельной линии-части объекта), в эту функцию передается порядковый номер выбранной линии и новые ее параметры, установленные пользователем.

· Удаление объекта или его части

Для удаления объектов необходимо удалить из списка соответствующие им элементы. Это осуществляется при помощи функции класса списков Remove(int). В функцию передается порядковый номер выбранной линии.

3.1.5 Тестирование программы

Для выполнения тестирования программы следует произвести следующие действия:

1. Запустить файл “Editor.exe”.

2. Выбрать объект

3. Установить его параметры с помощью ComboBox-элементов

4. Установить положение объекта на плоскости путем 2-х или 3-х кликов мышкой на белой области формы

5. В случае кривой Безье можно увидеть вспомогательные линии, используемые для построения объекта, щелкнув на флажке «Показать все линии». Сюрос этого флажка уберет вспомогательные линии с экрана

6. В ListBox'е «Все линии» выбрать различные линии. Они будут выделяться на объекте цветом выделения, который также можно интерактивно изменить

7. При щелчке на объекте в списке «Объекты» будет выделена первая линия выделенного объекта в списке вверху

8. При нажатии Delete выделенная линия удаляется из списка, оставляя при этом объект как единое целое. После удаления линий из объекта над ним можно произвести те же операции, что и до удаления. При удалении всех линий из объекта, он сам удаляется из списка

9. Закрыть окно для выхода из программы

3.2 Руководство оператора

В данной главе приводится описание действий оператора (пользователя) для достижения нужных результатов.

3.2.1 Запуск программы

Чтобы запустить программу, нужно из папки с программой открыть файл «Editor.exe».

При запуске программы перед Вами находиться следующее окно:

Рис. 1. Вид главного окна приложения

3.2.2 Создание объекта

- Выбрать объект

- Установить его параметры с помощью ComboBox-элементов

- Установить положение объекта на плоскости путем 2-х или 3-х кликов мышкой на белой области формы

- В случае кривой Безье можно увидеть вспомогательные линии, используемые для построения объекта, щелкнув на флажке «Показать все линии». Сюрос этого флажка уберет вспомогательные линии с экрана.

3.2.3 Выделение и удаление объектов

- В ListBox'е «Все линии» выбрать различные линии. Они будут выделяться на объекте цветом выделения, который также можно интерактивно изменить

- При щелчке на объекте в списке «Объекты» будет выделена первая линия выделенного объекта в списке вверху

- При нажатии Delete выделенная линия удаляется из списка, оставляя при этом объект как единое целое. После удаления линий из объекта над ним можно произвести те же операции, что и до удаления. При удалении всех линий из объекта, он сам удаляется из списка

3.2.4 Изменение объекта

Для изменения параметров объекта необходимо выделить его в списке объектов и установить новые значения цветов с помощью ComboBox-элементов.

3.2.5 Завершение программы

Чтобы выйти из программы, нужно нажать на кнопку с изображением крестика в правом верхнем углу окна.

3.3 Сообщения оператору

Вся работа со списком объектов отображается на экране. При добавлении линии или объекта, он появляется на экране, при удалении - исчезает оттуда, при выделении - меняет цвет на цвет выделения.

СПИСОК ЛИТЕРАТУРЫ

1. Дейтел Х., Дейтел П. Как программировать на С++: пер. с англ. - М.: «Издательство Бином», 2003 г.

2. Кондратьева С.Д. Введение в структуры данных: лекции и упражнения по курсу. - М.: Издательство МГТУ им. Н. Э. Баумана, 2000 г.

3. Стивенс Р. Delphi. Готовые алгоритмы: Пер. с англ. - М.: Издательство ДМК Пресс, 2001.-384с.

4. Рейсдорф Кент и Хендерсон Кен Borland C++ Builder. Освой самостоятельно: [Электронный ресурс].