МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ НЕФТЕГАЗОВЫЙ УНИВЕРСИТЕТ»

КАФЕДРА ИНФОРМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

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

по дисциплине «Алгоритмические языки и программирование»

Тема:

Разработка приложения для Windows,

представляющего собой компьютерную модель стека

Выполнил

студент группы

АСОИУс-1

Васечкин Иван

Проверила

Лозикова И.О.

Тюмень 2003

СОДЕРЖАНИЕ

Разработка эскизного и технического проектов программы.. 3

Введение. 3

Назначение и область применения. 4

Технические характеристики. 4

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

Описание алгоритма. 4

Организация входных и выходных данных. 6

Выбор состава технических и программных средств. 6

Источники, использованные при разработке. 7

Разработка программы.. 8

Спецификация программы.. 9

Текст программы.. 10

Описание программы.. 14

Общие сведения. 14

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

Используемые технические средства. 16

Вызов и загрузка. 16

Входные и выходные данные. 17

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

Заключение. 19

Литература. 20

Разработка эскизного и технического проектов программы

Введение

Задание на курсовую работу по дисциплине «Алгоритмические языки и программирование».

Студент группы АСОИУс-1 Васечкин И.И.

Специальность: «Автоматизированные системы обработки информации и управления».

Тема: Разработка приложения для Windows, представляющего собой компьютерную модель стека.

Условие задачи:

Для выполнения задачи используется среда разработки Borland C++ Builder. В приложении должен быть реализован класс стека и создан интерфейс, иллюстрирующий работу стека.

Задание выдано:________________________/Число и подпись/

Назначение и область применения

Целью данной курсовой работы является изучение структуры данных типа «стек» и создание приложения, иллюстрирующего его работу.

Данное приложение может быть использовано при обучении основам структур данных, как компьютерная модель структуры данных «стек».

Технические характеристики.

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

Приложение «Stack» должно работать на платформе Windows.

Интерфейс приложения должен предоставлять возможности для выполнения следующих действий:

 - инициализация стека;

 - очистка стека;

 - ввод значений в стек;

 - вывод значений из стека;

Также должна обеспечиваться возможность слежения за элементами в стеке.

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

Описание алгоритма

Стек - такой последовательный список с переменной длиной, включение и исключение элементов из которого выполняются только с одной стороны списка, называемого вершиной стека. Применяются и другие названия стека - магазин и очередь, функционирующая по принципу LIFO (Last - In - First- Out - "последним пришел - первым исключается"). Примеры стека: винтовочный патронный магазин, тупиковый железнодорожный разъезд для сортировки вагонов.

Основные операции над стеком - включение нового элемента (английское название push - заталкивать) и исключение элемента из стека (англ. pop - выскакивать).

Полезными могут быть также вспомогательные операции:

·         определение текущего числа элементов в стеке;

·         очистка стека;

·         неразрушающее чтение элемента из вершины стека, которое может быть реализовано, как комбинация основных операций:

 x:=pop(stack);  push(stack,x);

Некоторые авторы рассматривают также операции включения/исключения элементов для середины стека, однако структура, для которой возможны такие операции, не соответствует стеку по определению.

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

·         а). пустого;

·         б-г). после последовательного включения в него элементов с именами 'A', 'B', 'C';

·         д, е). после последовательного удаления из стека элементов 'C' и 'B';

·         ж). после включения в стек элемента 'D'.

Рисунок 1: Включение и исключение элементов из стека

Как видно из рис. 1 С.1, стек можно представить, например, в виде стопки книг (элементов), лежащей на столе. Присвоим каждой книге свое название, например A,B,C,D... Тогда в момент времени, когда на столе книг нет, про стек аналогично можно сказать, что он пуст, т.е. не содержит ни одного элемента. Если же мы начнем последовательно класть книги одну на другую, то получим стопку книг (допустим, из n книг), или получим стек, в котором содержится n элементов, причем вершиной его будет являться элемент n+1. Удаление элементов из стека осуществляется аналогичным образом т. е. удаляется последовательно по одному элементу, начиная с вершины, или по одной книге из стопки.

Организация входных и выходных данных

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

Выбор состава технических и программных средств

Программа создавалась при помощи среды разработки Borland C++ Builder 6.0, что было обусловлено заданием.

Требования к рабочей станции типа PC:

 - операционная система Microsoft Windows 2000 и выше;

- процессор 300 Мгц и выше;

 - ОЗУ 32 Мб и выше;

 - комплектация: монитор, манипулятор «мышь», клавиатура.

Источники, использованные при разработке

В данной работе использовалась стандартная библиотека STL, входящая в состав стандарта ANSI на язык С++, а также исходный код и файлы справочной системы данной библиотеки.

Разработка программы

Интерфейс программы должен иметь следующие компоненты:

 - кнопка для инициализации стеков;

 - кнопка для очистки стеков;

 - текстовое поле для ввода элементов стека;

 - кнопка для добавления в стек элемента;

 - кнопка для вывода элемента из стека;

 - поясняющие надписи для обозначения функционального назначения элементов интерфейса;

 - списки элементов в каждом стеке.

Windows-окно приложения приведено на рисунке 2.

Рисунок 2. Интерфейс программы Stack.

Техническая спецификация на используемые компоненты:

1.                             Компонент Кнопка TButton. Активизирует остальные элементы. Событие – Click(). Изменены свойства:

a.     Name=”btnCreate”

2.                             Компонент Кнопка TButton. Очищает стеки, деактивизирует компоненты. Событие – Click(). Изменены свойства:

a.     Name=”btnDestroy”

3.                             Компонент Кнопка TButton. Добавляет элемент в стеки, отображает его в списках элементов. Событие – Click(). Изменены свойства:

a.     Name=”btnAdd”

4.                             Компонент Кнопка TButton. Выводит элемент из стеков, удаляет этот элемент из стека. Событие – Click(). Изменены свойства:

a.     Name=”btnDelete”

5.                             Компонент Текстовое Поле TEdit. Поле для ввода строк элементов стека. Изменены свойства:

a.     Name=”eInput”

6.                             Компоненты Надпись TLabel. Поясняющие надписи – в свойстве Captioin.

7.                             Компоненты Список TListBox. Отображение списка элементов. Изменены Name: lbElements, lbChars.

Спецификация программы

Ниже приводится точное название программы и ее состав.

Обозначение	Наименование	Примечание
Stack.bpr	Файл проекта	Связывает все файлы приложения
MainUnit.cpp	Файл главного модуля проекта	Реализованы все события кнопок
Mystack.h	Заголовочный файл реализации класса стека	Реализация класса  «стек»

Текст программы

Код программы полностью откомментирован, ниже приводится листинг с опущенными комментариями, чтобы уменьшить его объем.

Файл MainUnit.cpp

//---------------------------------------------------------------------------

#include <vcl.h>

#pragma hdrstop

#include "MainUnit.h"

#include <string>

#include <stack>

#include "mystack.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma resource "*.dfm"

TFrmMain *FrmMain;

using namespace std;

stack<string> s;

MyStack<string> st;

//---------------------------------------------------------------------------

__fastcall TFrmMain::TFrmMain(TComponent* Owner)

        : TForm(Owner)

{

}

//---------------------------------------------------------------------------

void __fastcall TFrmMain::btnCreateClick(TObject *Sender)

{

eInput->Enabled=true;

btnAdd->Enabled=true;

btnDelete->Enabled=true;

btnDestroy->Enabled=true;

btnCreate->Enabled=false;

}

//---------------------------------------------------------------------------

void __fastcall TFrmMain::btnDestroyClick(TObject *Sender)

{

while (!s.empty())

        {

        s.pop();

        }

lbElements->Clear();

eInput->Clear();

btnCreate->Enabled=true;

eInput->Enabled=false;

btnAdd->Enabled=false;

btnDelete->Enabled=false;

btnDestroy->Enabled=false;

}

//---------------------------------------------------------------------------

void __fastcall TFrmMain::btnAddClick(TObject *Sender)

{

if (eInput->Text!="")

        {

        //готовый класс

        s.push(eInput->Text.c_str());

        lbElements->Items->Insert(0,AnsiString(s.top().c_str()));

        //свой класс

        st.PushElement(eInput->Text.c_str());

        string dt;

        int i=st.ViewTopElement(dt);

        lbChars->Items->Insert(0,AnsiString(dt.c_str()));

        eInput->Text="";

        }

else ShowMessage("Необходимо ввести строку - элемент стека!");

}

//---------------------------------------------------------------------------

void __fastcall TFrmMain::btnDeleteClick(TObject *Sender)

{

if (lbElements->Items->Count>0)

        {

        s.pop();

        lbElements->Items->Delete(0);

        string dt;

        st.PopTopElement(dt);

        lbChars->Items->Delete(0);

        }

else ShowMessage("Нет элементов, которые можно удалить!");

}

//---------------------------------------------------------------------------

Файл MyStack.h

//Объявление класса стека

template <class T> struct Element_T {

      T Data;

      Element_T *Previous;

};

template <class T> class MyStack

{

Element_T<T> *TopElement;

public:

MyStack();

~MyStack();

int MakeEmpty()

        {

      Element_T<T> *temp;

      while (!(TopElement==NULL))

                {

            temp=TopElement->Previous;

            delete TopElement;

            TopElement=temp;

            }

        return 0;

      }

bool Empty()

        {

      if (!(TopElement==NULL))

                {

              return false;

              }

        else

                {

            return true;

            }

      }

int PushElement(T data)

        {

      Element_T<T> *temp;

      temp=new Element_T<T>;

      temp->Data=data;

      temp->Previous=TopElement;

      TopElement=temp;

      return 0;

      }

int PopTopElement(T &data)

        {

      if (!(TopElement==NULL))

                {

            Element_T<T> *temp;

            data=TopElement->Data;

            temp=TopElement->Previous;

            delete TopElement;

            TopElement=temp;

            }

        return 0;

      }

int ViewTopElement(T &data)

        {

      if (!(TopElement==NULL))

                {

            data=(TopElement->Data);

            return 0;

            }

        return 1;

      }

};

// конструктор

template <class T>

MyStack<T>::MyStack()

        {

      TopElement=NULL;

        }

// деструктор

template <class T>

MyStack<T>::~MyStack()

        {

      int i;

      i=MakeEmpty();

        }

Описание программы

Общие сведения

Программа Stack была разработана в рамках курсовой работы. Основной целью являлось создание Windows-приложения, представляющего собой компьютерную модель стека.

Для функционирования программы необходимо наличие трех библиотек производства Borland Interprise, которые реализуют функционирование используемых компонентов.

Список библиотек: stlpmt45.dll, cc3260mt.dll, borlndmm.dll. Библиотеки поставляются вместе с исполняемым файлом Stack.exe. Программа не требует установки.

Программа разработана в среде Borland C++ Builder 6.0. Для функционирования программы необходима операционная система Windows версии 2000 и выше и наличие указанных библиотек. Библиотеки могут находиться как в папке с исполняемым файлом, так и в папке Windows.

Функциональное назначение: демонстрация работы структуры данных «стек».

В рамках создания программы был реализован класс mystack и изучена работа стандартного класса стек, входящего в стандартную библиотеку STL языка программирования С++. Класс реализован как динамическая структура и ограничением его использования является только объем оперативной памяти компьютера.

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

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

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

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

Класс предоставляет пользователю следующий интерфейс:

 - создание стека;

 - очистка стека;

 - добавление элемента;

 - выборка элемента;

 - получение значения верхнего элемента;

 - проверка, пуст ли стек.

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

Также в программе используется стандартный класс <stack>, предоставляющий примерно тот же интерфейс. Конечно, стандартный класс обладает большими возможностями, так как реализован в более общем варианте и может использовать для хранения элементов различные структуры данных.

Основной модуль MainUnit включает в себя заголовочный файл mystack.h при помощи директивы include, что позволяет использовать в нем созданный класс. Также модуль включает в себя и стандартный класс стека.

В общем пространстве видимости модуля объявлены два экземпляра обоих используемых классов стека – s и st.

При нажатии на кнопки вызываются соответствующие процедуры.

Например, процедура void __fastcall TFrmMain::btnAddClick(TObject *Sender) выполняет следующие действия:

 - проверка, введены ли в текстовое поле данные. Если да, то выполнение продолжается, если нет – на экран выводится сообщение.

 - добавление элемента в оба стека;

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

Используемые технические средства

Программа создавалась при помощи среды разработки Borland C++ Builder 6.0, что было обусловлено заданием.

Требования к рабочей станции типа PC:

 - операционная система Microsoft Windows 2000 и выше;

- процессор 300 Мгц и выше;

 - ОЗУ 32 Мб и выше;

 - комплектация: монитор, манипулятор «мышь», клавиатура.

Вызов и загрузка

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

Входные и выходные данные

Входными данными являются элементы стека – строковые значения, вводимые пользователем в текстовое поле. Ограничение на длину – 255 символов.

Выходными данными является поведение программы и списки элементов стека, которые подчиняются правилам его работы.

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

Для создания программы был использован Borland C++ Builder 6.0 Enterprise Edition - визуальная среда для быстрой разработки приложений на языке C++, промышленный выпуск.

Для проверки кода использовался CodeGuard – средство проверки стиля написания кода.

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

Основным требованием при испытании программы было, кроме корректного исполнения ею своих функций, гарантировать контроль очищения памяти.

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

Забивание и освобождение памяти проводилось следующим кодом:

for (int i=0;i<100000;i++)

        {

        string dt="test";

        st.PushElement(dt);

        }

for (int i=0;i<100000;i++)

        {

        string dt="test";

        st.PopTopElement(dt);

        }

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

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

Заключение

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

В ходе выполнения данной работы была изучена среда программирования Borland C++ Builder 6.0, приемы объектно-ориентированного программирования, стандартная библиотека STL, организация структуры данных «стек».

Создан собственный класс организации работы стека, основанный на динамическом выделении памяти.

Литература

1.     Архангельский А.Я. Программирование в С++Builder 6. – М.: «Издательство БИНОМ», 2003 г. – 1152 с.

2.     Гамма Э., Хелм Р., Джонсон Р., Влиссидес Дж. Приемы объектно-ориентированного проектирования. Паттерны проектирования. – СПб.: Питер, 2001 г. – 368 с.

3.     Б. Страуструп. Язык программирования С++, 3-е изд. / Пер. с англ. – СПб.: М.: «Невский диалект» - «Издательство БИНОМ», 1999 г., 991 с.

4.     Айра Пол, Объектно-ориентированное программирование на С++, 2-е изд. СПб.: М.: «Невский диалект» - «Издательство БИНОМ», 1999 г. – 462 с.

5.     Одинцов И.О. Профессиональное программирование. Системный подход. – СПб.: БХВ-Петербург, 2002. – 512 с.: ил.

6.     Александровский А.Д. Delphi 4. Шаг в будущее. – М.:ДМК, 1999 – 528 с.