Система поиска автобусных маршрутов

Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

ФГБОУ ВПО Рыбинский государственный авиационный технический университет им. П. А. Соловьева

Факультет радиоэлектроники и информатики

Кафедра вычислительных систем

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

по дисциплине

«Объектно-ориентированное программирование»

на тему: Система поиска автобусных маршрутов

Пояснительная записка

Студент группы ИВБ-14 Бойцов П.В.

Руководитель Паламарь И. Н.

Рыбинск 2015



Содержание

delphi автобусный маршрут приложение

Введение

1. Алгоритм решения задачи

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

1.2 Математическая постановка задачи

1.3 Алгоритмизация

2. Исходные данные

2.1 Пользовательские типы данных

2.2 Описание переменных

2.3 Способы ввода/вывода информации

2.4 Интерфейс пользователя

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

3.1 Описание модулей программы

3.2 Описание функций программы

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

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

4.2 Обработка ошибок

Заключение

Список использованных источников

Приложение

Введение

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

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

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

Заданием на данную курсовую работу является разработка приложения с использованием среды разработки Delphi для поиска автобусных маршрутов с использованием принципов объектно-ориентированного подхода.

В качестве средства разработки использована популярная среда разработки Delphi 7.

1. Алгоритм решения задачи

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

Необходимо разработать программу для поиска автобусных маршрутов. В качестве среды разработки должна использоваться Delphi 7.

В программе должно быть:

- использование объектно-ориентированного подхода, а именно, свои классы, конструкторы, деструкторы, ограничения области видимости, поля и наследование;

- использование MDI интерфейса;

- использование элементов управления CheckBox и RadioButton.

1.2 Математическая постановка задачи

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

Но алгоритм необходимо модифицировать, т.к. две остановки могут соединяться сразу несколькими маршрутами. Также необходимо исключить пути, содержащие кольца.

1.3 Алгоритмизация

На рисунке 1.1 приведена блок-схема основного алгоритма программы.



Рисунок 1.1 -- Блок-схема поиска путей в графе

2. Исходные данные

2.1 Пользовательские типы данных

В программе использовано несколько пользовательских типов данных. Так как программа написана с использованием объектно-ориентированного подхода, то пользовательские типы данных описаны как классы.

Класс для хранения элемента коллекции называется TCollectionElement. Этот класс имеет единственный абстрактный метод для сравнения двух элементов.

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

Для описания автобусной остановки добавлен класс TOneStop, наследник от класса TCollectionElement. Класс расширен полем Title, предназначенным для хранения названия остановки.

Для описания списка автобусных остановок добавлен класс TStop, наследник класса TCollection. Для него переопределены методы загрузки из файла и сохранения данных в файл.

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

Основным классом в программе является класс TTown. Данный класс также является наследником класса TCollection. Данный класс содержит список остановок и список автобусных маршрутов.



2.2 Описание переменных

В программе описана и используется одна глобальная переменная Town: TTown.

Данная переменная содержит список остановок и автобусных маршрутов.

Остальные переменные проекта являются локальными и используются в функциях для хранения промежуточных результатов.

2.3 Способы ввода/вывода информации

Программа поддерживает два способа ввода исходных данных:

1. Ручной ввод с клавиатуры

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

2. Ввод из файла.

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

Файл, содержащий список остановок, представляет собой обычное перечисление:

<Остановка 1>

<Остановка 2>

<Остановка N>

Аналогичный формат имеет файл, содержащий список маршрутов:

<Маршрут 1>

< Маршрут 2>

< Маршрут N>

Каждый маршрут сохраняется в отдельном текстовом файле. Формат:

<Название маршрута>

<Остановка 1>

<Остановка 2>

<Остановка N>

2.4 Интерфейс пользователя

Интерфейс программы показан на рисунке 2.1.

Рисунок 2.1 -- Интерфейс пользователя

Программа выполнена с использованием MDI-интерфейса. Интерфейс содержит главную форму и три дочерних формы. На главной форме расположено меню. Элементы управления, расположенные на остальных формах, перечислены в таблицах 2.1-2.3.

Таблица 2.1 -- Элементы пользовательского интерфейса формы для поиска маршрутов

Название	Тип	Назначение
ComboBoxFrom	TComboBox	Выпадающий список для выбора начальной остановки маршрута
ComboBoxTo	TComboBox	Выпадающий список для выбора конечной остановки маршрута
CheckBox1	TCheckBox	Признак поиска маршрутов с пересадками
MemoRoute	TMemo	Поле для вывода результатов поиска
Label1, Label2, Label3	TLabel	Текстовые метки
ButtonFindRoute	TButton	Кнопка, запускающая процесс поиска маршрутов

Таблица 2.2 -- Элементы пользовательского интерфейса формы для редактирования списка маршрутов

Название	Тип	Назначение
LabelRouteTitle	TLabel	Текстовая метка
MemoRoute	TMemo	Список остановок маршрута
ButtonSave	TButton	Кнопка «Сохранить»
ComboBoxRoutes	TRadioGroup	Выбор маршрута

Таблица 2.3 -- Элементы пользовательского интерфейса формы для редактирования списка остановок

Название	Тип	Назначение
MemoStop	TMemo	Список остановок
ButtonSave	TButton	Кнопка «Сохранить»
Label1	TLabel	Текстовая метка

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

3.1 Описание модулей программы

Проект приложения содержит следующие модули.

Модуль UnitCollection.pas содержит описание классов для работы с коллекцией и элементом коллекции.

Модуль UnitRoute.pas содержит описание классов для работы с коллекцией маршрутов и маршрутом.

Модуль UnitStop.pas содержит описание классов для работы с коллекцией остановок и остановкой.

Модуль UnitTown.pas содержит описание основного класса программы.

Модули MainUnit.pas, ChildUnit.pas, UnitStopFrom.pas и UnitTownForm.pas содержат функции для организации пользовательского интерфейса программы. MainUnit.pas - содержит функции главной формы, остальные три модуля содержат функции дочерних модулей.

3.2 Описание функций программы

В приложении реализован набор функций для работы с автобусными маршрутами. Программа позволяет:

-редактировать список остановок;

-редактировать список автобусных маршрутов;

-искать автобусные маршруты, позволяющие добраться от остановки A до остановки B. Можно также искать маршруты поездок с пересадками.

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

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

Проверим работоспособность программы на нескольких различных наборах исходных данных.

На рисунке 4.1 показан процесс редактирования списка остановок. Редактирование происходит средствами стандартного многострочного поля ввода.

Рисунок 4.1 -- Редактирование

На рисунке 4.2 показан процесс редактирования списка маршрутов.



Рисунок 4.2 -- Редактирование

Протестируем поиск маршрутов (рисунок 4.3).

Рисунок 4.3 -- Поиск

В выпадающем списке можно просмотреть информацию по каждому предложенному маршруту (рисунок 4.4).

Рисунок 4.4 -- Поиск

4.2 Обработка ошибок

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

Заключение

В процессе работы над курсовой работой были изучены принципы объектно-ориентированного программирования и основы разработки приложений в среде Delphi 7.

Было разработано приложение для поиска автобусных маршрутов.

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

Приложение имеет графический интерфейс.

Список использованных источников

1. Архангельский А. Приемы программирования в Delphi на основе VCL / А. Архангельский. -- Москва. : Бином-Пресс, 2009. -- 944 с.

2. Климов Л.М. Delphi 7. Основы программирования. Решение типовых задач. Самоучитель: Л. М. Климова -- Санкт-Петербург, КУДИЦ-Образ, 2006 г.- 480 с.

3. Желонкин А. Основы программирования в интегрированной среде DELPHI: А. Желонкин -- Москва, Бином. Лаборатория знаний, 2004 г.- 240 с.

4. Культин Н. Основы программирования в Delphi XE/ Н. Культин. -- СПб. : БХВ-Петербург, 2011. -- 416 с.

5. Осипов Д. Delphi XE2 / Д. Осипов. -- Санкт-Петербург : БХВ-Петербург, 2012. -- 869 с.

6. Понамарев В. Самоучитель Delphi 7 Studio: Вячеслав Понамарев -- Москва, БХВ-Петербург, 2003 г.- 504 с.

7. Фаронов В.В. Программирование баз данных в Delphi 7: Учебный курс. - СПб.: Питер, 2004 - 464 с.

Приложение

Исходный код

UnitCollection.pas

unit UnitCollection;

interface

type TCollectionElement=class

protected function EqualTo(X:TCollectionElement):boolean; virtual; abstract;

end;

type TCollection = class

private

protected

Data:array of TObject;

F:TextFile;

public

function Add(E:TCollectionElement):integer; overload;

function Add(E:TObject):integer; overload;

procedure Delete(index:integer);

function Find(E:TCollectionElement):integer; virtual;

procedure LoadFromFile(FileName:string);virtual; abstract;

procedure SaveToFile(FileName:string);virtual; abstract;

function ToString():string;virtual; abstract;

public

function Count:integer;

function Element(index:integer):TObject;

procedure Clear; virtual;

end;

implementation

{ TCollection }

function TCollection.Add(E:TCollectionElement):integer;

begin

Result := Find(E);

if Result>=0 then Exit; //Одинаковых элементов быть не должно

SetLength(Data,Length(Data)+1);

Result := High(Data);

Data[Result] := E;

end;

function TCollection.Add(E:TObject):integer;

begin

SetLength(Data,Length(Data)+1);

Result := High(Data);

Data[Result] := E;

end;

procedure TCollection.Clear;

begin

SetLength(Data,0);

end;

function TCollection.Count: integer;

begin

Result := Length(Data);

end;

procedure TCollection.Delete(index: integer);

var i:integer;

begin

for I := index to High(Data) - 1 do Data[i] := Data[i+1];

SetLength(Data,Length(Data)-1);

end;

function TCollection.Element(index: integer): TObject;

begin

Result := Data[index];

end;

function TCollection.Find(E:TCollectionElement):integer;

var i:integer;

begin

Result := -1;

for I := 0 to High(Data) do

if (Data[i] as TCollectionElement).EqualTo(E) then begin Result := i; Exit; end;

end;

end.

UnitRoute.pas

unit UnitRoute;

interface

uses UnitCollection;

type TRouteElement = class(TCollectionElement)

StopTitle:string; //Название остановки

function EqualTo(X:TCollectionElement):boolean; override;

end;

type TRoute = class(TCollection)

Title:string; //Название маршрута

Delimiter:string; //Разделитель при выводе

constructor Create();

procedure LoadFromFile(FileName:string);override;

procedure SaveToFile(FileName:string);override;

function ToString():string; override;

end;

implementation

{ TRoute }

constructor TRoute.Create;

begin

Delimiter := #13#10;

end;

procedure TRoute.LoadFromFile(FileName: string);

var RE:TRouteElement;

begin

AssignFile(F,FileName); Reset(F);

ReadLn(F,Title); //Первая строка - название маршрута

while not EOF(F) do begin

RE := TRouteElement.Create();

Readln(F,RE.StopTitle);

Add(RE);

end;

CloseFile(F);

end;

procedure TRoute.SaveToFile(FileName: string);

var i:integer;

begin

AssignFile(F,FileName); Rewrite(F);

WriteLn(F,Title);

for I := 0 to High(Data) do with TRouteElement(Data[i]) do

WriteLn(F,StopTitle);

CloseFile(F);

end;

function TRoute.ToString: string;

var i:integer;

begin

Result:='';

for I := 0 to High(Data) do with TRouteElement(Data[i]) do

Result := Result+ StopTitle + Delimiter;

end;

{ TRouteElement }

function TRouteElement.EqualTo(X: TCollectionElement): boolean;

begin

Result := (X as TRouteElement).StopTitle = StopTitle;

end;

end.

UnitStop.pas

unit UnitStop;

interface

uses UnitCollection;

type TOneStop=class(TCollectionElement)

Title:string;

// x,y:integer;

// procedure Paint(); virtual; abstract;

function EqualTo(X:TCollectionElement):boolean; override;

end;

type TStop=class (TCollection)

public

procedure LoadFromFile(FileName:string);override;

procedure SaveToFile(FileName:string);override;

end;

implementation

{ TStop }

procedure TStop.LoadFromFile(FileName: string);

var Stop:TOneStop;

begin

AssignFile(F,FileName); Reset(F);

while not EOF(F) do begin

Stop := TOneStop.Create();

Readln(F,Stop.Title);

Add(Stop);

end;

CloseFile(F);

end;

procedure TStop.SaveToFile(FileName: string);

var i:integer;

begin

AssignFile(F,FileName); Rewrite(F);

for I := 0 to High(Data) do with TOneStop(Data[i]) do

WriteLn(F,Title);

CloseFile(F);

end;

{ TOneStop }

function TOneStop.EqualTo(X: TCollectionElement): boolean;

begin

Result := (X as TOneStop).Title = Title;

end;

end.

UnitTown.pas

unit UnitTown;

interface

uses UnitCollection,UnitStop,UnitRoute;

type TTown = class(TCollection)

private

function FindDirect(A, B: string): TRoute;

public

Stops:TStop; //Список остановок (Один на весь город)

constructor Create();

procedure LoadFromFile(FileName:string);override;

//Основная функция - найти маршрут из пунка А в пункт В

//Direct - требование только "прямого" маршрута

function FindPath(A:string; B:string; Direct:boolean):TRoute;

procedure SaveToFile(FileName:string);

function ToString():string;

end;

var Pathes:array of array of integer; //Полученные пути (список)

implementation

type TRegisterProc = procedure();

var M:array of array of boolean; //Матрица смежности транспортного графа

var V:array of boolean; //Вершины графв

var Path:array of integer; //Текущий путь

{ TTown }

constructor TTown.Create;

begin

Stops := TStop.Create;

end;

procedure TTown.LoadFromFile(FileName: string);

var R:TRoute;

VAR S:string;

begin

AssignFile(F,FileName); Reset(F);

while not EOF(F) do begin

ReadLn(F,S);

R := TRoute.Create();

R.LoadFromFile(S+'.txt');

Add(R);

end;

CloseFile(F);

end;

procedure TTown.SaveToFile(FileName: string);

begin

//Не применимо

end;

function TTown.ToString: string;

begin

//Слабо применимо

end;

procedure RegisterPath();

var i:integer;

begin

//Зарегистрировать путь в списке найденных путей

SetLength(Pathes,Length(Pathes)+1);

SetLength(Pathes[High(Pathes)],Length(Path));

for I := 0 to High(Path) do

Pathes[High(Pathes)][i] := Path[i];

end;

function TTown.FindDirect(A,B:string):TRoute;

var R:TRoute;

REA,REB,RE:TRouteelement;

I:Integer;

K1,K2:integer;

Found:boolean;

ST:TOneStop;

begin

//Простым перебором маршрутов выяснить, есть ли прямой

//Если есть - сформировать маршрут, начинающийся в A и заканчивающийся в B

REA := TRouteElement.Create; REA.StopTitle := A;

REB := TRouteElement.Create; REB.StopTitle := B;

Found := False;

Result := TRoute.Create;

for I := 0 to Count - 1 do begin

R := Element(I) as TRoute;

K1 := R.Find(REA);

K2 := R.Find(REB);

if (K1>=0) and (K2>=0) then begin

Found := True;

break;

end;

end;

if not Found then Exit;

//Заполнить Result элементами маршрута от A до B

if K1>K2 then begin I:=K1; K1:=K2; K2:=I; end;

//Заодно заполнить путь

SetLength(Pathes,0,0);

SetLength(Path,K2-K1+1);

ST := TOneStop.Create;

for I := K1 to K2 do begin

RE := TRouteElement.Create;

RE.StopTitle := (R.Element(I) as TRouteElement).StopTitle;

ST.Title := RE.StopTitle;

Path[I-K1] := Stops.Find(ST);

Result.Add(RE);

end;

RegisterPath;

end;

procedure FindPathR(V1,V2:integer; Level:integer; RegisterPath: TRegisterProc);

//Рекурсивный поиск пути в графе

var i:integer;

begin

//Если длина пути первышена, то поиск окончен. Неудачно.

if Level<=0 then Exit;

//Если V1 = V2 то поиск окончен удачно

if V1 = V2 then

if assigned(RegisterPath) then begin

SetLength(Path,Length(Path)+1);

Path[High(Path)] := V2; //Отметить

RegisterPath;

SetLength(Path,Length(Path)-1);

Exit;

end;

//Для всех вершин, смежных с V1, попробовать найти путь

for i := 0 to High(M) do

if M[V1][i] then begin

SetLength(Path,Length(Path)+1);

Path[High(Path)] := V1; //Отметить

FindPathR(i,V2,Level-1,RegisterPath);

SetLength(Path,Length(Path)-1);

end;

end;

function TTown.FindPath(A, B: string; Direct: boolean):TRoute;

var eA,eB:TOneStop;

var iA,iB:integer; //Номера остановок

var route,i,j,N:integer;

R : TRoute;

K1,K2:integer;

Stop:TOneStop;

RE : TRouteElement;

begin

if Direct then begin Result := FindDirect(A,B); Exit; end;

//Составить матрицу смежности взвешенного графа транспортной сети

//Для этого

//Сначала создать и очистить матрицу

N := Stops.Count;

SetLength(V,N);

SetLength(M,N,N);

for i := 0 to N - 1 do

for j := 0 to N - 1 do

M[i][j] := false;

//Перебрать все маршруты

Stop := TOneStop.Create;

for route := 0 to Count-1 do begin

R := Element(route) as TRoute;

//В каждом маршруте соседние остановки объявить связанными

for i := 0 to R.Count - 1-1 do begin

Stop.Title := (R.Element(i) as TRouteElement).StopTitle;

K1 := Stops.Find(Stop);

Stop.Title := (R.Element(i+1) as TRouteElement).StopTitle;

K2 := Stops.Find(Stop);

if K2<0 then continue;

M[K1][K2] := true; //Граф считается ненаправленным

M[K2][K1] := true;

end;

end;

//Найти путь в нем

//Для этого

//Очистить список вершин

for i := 0 to N - 1 do V[i] := false;

Stop.Title := A;

K1 := Stops.Find(Stop);

Stop.Title := B;

K2 := Stops.Find(Stop);

SetLength(Pathes,0,0);

FindPathR(K1,K2,Stops.Count,RegisterPath);

Result := TRoute.Create;

//И самый первый путь туда записать

for I := 0 to High(Pathes[0]) do

begin

RE := TRouteElement.Create;

RE.StopTitle := (Stops.Element(Pathes[0][i]) as TOneStop).Title;

Result.Add(RE);

end;

end;

end.

Размещено на Allbest.ru