Министерствообразования и науки РФ
Федеральное агентствопо образованию
Государственноеобразовательное учреждение высшего профессионального образования
«Омскийгосударственный технический университет»
Кафедра прикладной математики и информационных систем
Курсовая работа по дисциплине: «Высокоуровневые методы»
Омск 2008
Содержание
Введение
Постановка задачи
Динамические структуры данных: дек
Описание алгоритма
Приложение 1. Текст программы
Приложение 2. Форма
Введение
Объектно-ориентированноепрограммирование – это естественное продолжение структурного программирования.Объектно-ориентированное программирование требует сложных программных действий,но делает создание программы достаточно легким. В результате создаютсясовершенные коды, которые легко распространять и просто поддерживать. Однаждысозданный для приложения объект можно использовать в других приложениях.Повторное использование объектов намного сокращает время разработки иувеличивает производительность труда. Объектно-ориентированное программированиеосновано на использовании классов. Использование классов – это основное отличиеязыка С++ от языка С, на котором он основан.
Класс наряду с понятием«Объект», является важным понятием объектно-ориентированного подхода впрограммировании. Под классом подразумевается некая сущность, которая задаетнекоторое общее поведение для объектов. Таким образом, любой объект можетпринадлежать или не принадлежать определенному классу, то есть обладать или необладать поведением, которое данный класс подразумевает. Класс определяет дляобъекта правила, с помощью которых с объектом могут работать другие объекты,обычно это делается с помощью определения методов класса.
Кроме того, классы могутнаходиться друг с другом в различных отношениях, таких как наследование илиагрегация.
Класс — это собраниесвязной информации, которая включает в себя и данные, и функции. Класс – этодальнейшее развитие структур: в них тоже объединяется данные разных типов. Этотакой же шаблон, под который, как и под структуру, память выделяется толькотогда, когда мы создаем «переменную типа этого шаблона».
Класс определяется каксписок своих членов. К членам класса относятся его поля (свойства) и функции(методы).
Каждому члену классаможно установить его область доступа (access control level). Область доступачлена класса определяет участки кода, из которых к этому члену будет возможнообращаться. В большинстве объектно-ориентированных языков программированияподдерживаются следующие области доступа:
· private (закрытый, внутренний членкласса) — обращения к члену допускаются только из кода методов класса, вкотором этот член определён. Любые наследники класса уже не смогут получитьдоступ к этому члену;
· protected (защищённый, внутреннийчлен иерархии классов) — обращения к члену допускаются из кода методов класса,в котором этот член определён, или из любых его классов-наследников;
· public (открытый член класса) —обращения к члену допускаются из любого кода.
В каждом классеопределены характеристики тех объектов, которые использует данный класс. Вклассе также задаются программы, называемые методами, которые обрабатываютхарактеристики объектов, принадлежащих данному классу. Поведение объекта вреальном мире определяется его характеристиками. Изменяя значениехарактеристик, мы получим разное поведение объектов. Когда мы создаем экземпляркласса и определяем значение его конкретных характеристик, мы получаемконкретный объект. В составе класса существует специальный метод, которыйформирует экземпляр класса. Этот метод носит название конструктора. Впротивоположность конструктору, существует программа-деструктор, котораяуничтожает экземпляр класса в памяти.
Постановка задачи
Создать класс «Дек».
Реализовать методы:
1. Добавлениеэлемента в начало дека.
2. Удаление элементаиз начала дека.
3. Добавлениеэлемента в конец дека.
4. Удаление элементаиз конца дека.
5. Проверка дека наналичие в нем элементов.
Динамические структурыданных: дек
В языках программированиясуществует такой способ выделения памяти под данные, который называетсядинамическим. В этом случае память под величины отводится во время выполненияпрограммы. Такие величины называются динамическими. Раздел оперативной памяти,распределяемый статически, называется статической памятью; динамическираспределяемый раздел памяти называется динамической памятью (динамическираспределяемой памятью).
Использованиединамических величин предоставляет программисту ряд дополнительныхвозможностей. Во-первых, подключение динамической памяти позволяет увеличитьобъем обрабатываемых данных. Во-вторых, если потребность в каких-то данныхотпала до окончания программы, то занятую ими память можно освободить длядругой информации. В-третьих, использование динамической памяти позволяетсоздавать структуры данных переменного размера.
Работа с динамическимивеличинами связана с использованием еще одного типа данных — ссылочного типа.Величины, имеющие ссылочный тип, называются указателями.
Указатель содержит адресполя в динамической памяти, хранящего величину определенного типа. Самуказатель располагается в статической памяти.
Структурированные типыданных, такие, как массивы, множества, записи, представляют собой статическиеструктуры, так как их размеры неизменны в течение всего времени выполненияпрограммы.
Часто требуется, чтобыструктуры данных меняли свои размеры в ходе решения задачи. К таким структурамотносятся списки (однаправленные, двунаправленные, кольцевые однаправленные икольцевые двунаправленные), стеки, деки, очереди, деревья и другие. Описаниединамических структур с помощью массивов, записей и файлов приводит кнеэкономному использованию памяти ЭВМ и увеличивает время решения задач.
Адрес величины — этономер первого байта поля памяти, в котором располагается величина. Размер поляоднозначно определяется типом.
Динамическая структураназывается деком (англ. deque – аббревиатура от double-ended queue,двухсторонняя очередь) или двунаправленным списком, если каждый узел еёсодержит два указателя: один указывает на предшествующий узел, другой — напоследующий. Такие списки могут быть линейными и циклическими, а члены в нихдобавляются и удаляются с 2 сторон.
/>/> />
Рис. 1. Дек
Мы будем различать деки сограниченным выходом или ограниченным входом; в таких деках соответственноисключение или включение допускается только на одном конце.
/>
/>
Рис. 2. Дек сограниченным входом
/>
/>
Рис. 3. Дек сограниченным выходом
Дек с ограниченным входомможет быть использован как простая очередь или как стек.
В деке все исключения идобавления происходят на обоих его концах.
Дек достаточно простоможно организовать в виде двусвязанного ациклического списка. При этом первый ипоследний элементы списка соответствуют входам (выходам) дека.
Описание алгоритма
Создаваемый класс вданной программе называется Deq.
Данный класс долженреализовывать функции вставки и удаления элементов в начало и конец дека.
Для создания класса «Дек»необходимо сначала создать структуру элемента с указателем на следующийэлемент. В данной программе такой структурой является Node.
При создании класса надосоздать указатели на первый и последний элементы дека. Данные указателипрописываются в private, т. е.обращаться к этим указателям возможно только из методов класса Deq.
В общедоступной областидоступа прописываются методы класса, прописанные в постановке задачи.
Указателям изначальноприсваиваются пустые значения (NULL).
Добавление элемента вначало дека
Для добавления элемента вначало дека используется метод класса add. Его параметрами является добавляемый элемент b.
Необходимо создать новыйэлемент структуры Node (el). Элементу el присваивается значение введенного с клавиатуры числа. Длядобавления элемента в начало дека, необходимо, чтобы ячейка была пуста.Поэтому, проверяется условие наличия в ячейке элемента. Если ячейка не пуста,то указатель на первый элемент переходит на следующую ячейку, в которую и будетзаписан элемент. Количество ячеек возрастает на 1.
Удаление элемента изначала дека
Для удаления элемента изначала дека используется метод класса delete.
Удаление элементапроисходит по тому же алгоритму, но ячейка не проверяется на наличие элемента внем. Элементу el присваивается указатель first и указатель переходит в следующуюячейку. Затем элемент elудаляется и количество ячеек понижается на единицу.
Добавление элемента вконец дека
Для добавления элемента вначало дека используется метод класса add_end. Его параметрами является добавляемыйэлемент b.
Необходимо создать новыйэлемент структуры Node (el). Элементу el присваивается значение введенного с клавиатуры числа. Длядобавления элемента в конец дека, необходимо, чтобы ячейка была пуста.Указатель на последний элемент переходит на следующую ячейку, в которую и будетзаписан элемент. Далее указателю на последний элемент переходит на следующуюячейку, которой присваивается значение NULL. Количество ячеек возрастает на 1.
Удаление элемента изконца дека
Для удаления элемента изначала дека используется метод класса delete_end.
Для удаления элемента изконца дека надо создать новый элемент структуры Node (el).Элементу el присваивается указатель на первыйэлемент. Пока el не примет значения NULL, элемент будет принимать значенияследующего элемента. Затем elудаляется и ссылке на последний элемент присваивается значение el. Количество ячеек уменьшается.
Проверка дека на наличиев нем элемента
Для проверки декаиспользуется метод класса prov. Этот методимеет тип Boolean.
Для проверки на наличиеэлементов в деке, создается новый элемент структуры Node и ему присваивается указатель на первый элемент дека.Если ячейка не пуста, то возвращается значение true, в противном случае, false.
Функция вывода дека в StringGrid
Данная функция необходимадля отображения вставки и удаления элементов в таблицу StringGrid. Функция увеличивает количествоячеек таблицы, если обнаруживает, что ячейка не пуста.
Приложение 1
Текст программы
#include
#pragmahdrstop
#include
#include«Unit1.h»
//---------------------------------------------------------------------------
#pragmapackage(smart_init)
#pragmaresource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcallTForm1::TForm1(TComponent* Owner)
:TForm(Owner)
{
}
int s,count=0;
struct Node
{
int key;
Node *next;
};
class deq
{
private:
Node *first;
Node *last;
public:
deq()
{first=NULL;
last=NULL;}
voiddeq::add(int b)
{
Node *el=newNode;
el->key=b;
if(first==NULL)
{
el->next=first;
first=el;
last=first;
}
else
{
el->next=first;
first=el;
}
count++;
}
voiddeq::del()
{
Node *el=newNode;
el=first;
first=el->next;
delete el;
count--;
}
voiddeq::add_end(int b)
{
Node *el=newNode;
el->key=b;
last->next=el;
last=el;
last->next=NULL;
count++;
}
voiddeq::del_end()
{
Node *el=newNode;
el=first;
while(el->next->next!=NULL)
el=el->next;
deleteel->next;
last=el;
last->next=NULL;
count--;
}
booldeq::prov()
{ Node*el=new Node;
el=first;
if(first==NULL)
return true;
else
return false;
}
void Draw ()
{
for (int i=0;i
Form1->StringGrid1->Cells[0][i]="";
Node*temp=first;
for (int i=0;i
{
Form1->StringGrid1->Cells[0][i]=temp->key;
if(temp->next!=NULL)
temp=temp->next;
}
}
};
deq a;
int i=0;
//---------------------------------------------------------------------------
void__fastcall TForm1::Button1Click(TObject *Sender)
{
a.add(StrToInt(Edit2->Text));
a.Draw();
}
//---------------------------------------------------------------------------
void__fastcall TForm1::Button2Click(TObject *Sender)
{
a.add_end(StrToInt(Edit2->Text));
a.Draw();
}
//---------------------------------------------------------------------------
void__fastcall TForm1::Button3Click(TObject *Sender)
{
if(a.prov())
ShowMessage(«Декпуст. Нечегоудалять») ;
else
a.del();
a.Draw();
}
//---------------------------------------------------------------------------
void__fastcall TForm1::Button4Click(TObject *Sender)
{
if(a.prov())
ShowMessage(«Декпуст!»);
else
ShowMessage(«Декне пуст!»);
}
//---------------------------------------------------------------------------
void__fastcall TForm1::Button5Click(TObject *Sender)
{
Edit3->Text=StrToInt(count);
}
//---------------------------------------------------------------------------
void__fastcall TForm1::Button6Click(TObject *Sender)
{
if(a.prov())
ShowMessage(«Декпуст. Нечего удалять») ;
else {
a.del_end();
a.Draw();}
}
//---------------------------------------------------------------------------
Приложение 2
Форма
Главная форма содержит:
· Label (Введите добавляемый элемент)
· GroupBox1 (Добавление элементов)
o Button1 (Добавление элемента в начало дека)
o Button2 (Добавление элемента в конец дека)
· GroupBox2 (Удаление элементов)
o Button3 (Удаление первого элемента)
o Button6 (Удаление последнего элемента)
· GroupBox3 (Другие функции)
o Button4 (Проверка на наличие элементов)
o Button5 (Узнать размер дека)
o Edit3 (Используется для вывода количестваэлементов в деке)
· StringGrid (Отображение дека)
· Edit2 (Значение, введенное с клавиатуры вEdit2, добавляется в дек)
/>
Рис. 4. Главная форма