ЦИКЛ ДЛЯ J=1 ДО N-1 ШАГ 1
ЦИКЛДЛЯI=1ДОN-JШАГ1
ЕСЛИ A[I]>A[I+1]ТООБМЕН A[I],A[I+1] СЛЕДУЮЩЕЕ I СЛЕДУЮЩЕЕ J
|
FOR J=1TO N-1
STEP 1 FOR I=1TO N-J STEP 1 IF A[I]>A[I+1]THEN SWAP A[I],A[I+1] NEXT I NEXT J
|
Блок-схема 1 - Блок схема алгоритма пузырька
Для поиска, из имеющихся методов, был выбран метод последовательного
поиска.
Суть метода заключается в том, что последовательно просматривается
массив, пока не будет найден нужный элемент массива. Последовательный поиск в
среднем случае выполнит проверку 1/2n элементов. В наилучшем случае она
выполнит проверку только одного элемента, а в наихудшем - n элементов. Если
объем данных не велик, эта производительность будет приемлемой.
4. Алгоритм решения задачи
.1 Метод
проектирования алгоритма
Методы проектирования алгоритмов включают: нисходящее проектирование,
модульность, структурное программирование.
Нисходящее проектирование предполагает последовательное разбиение
исходной задачи на подзадачи до такой конкретизации, когда подзадача сможет
быть реализована одним оператором выбранного для программирования языка.
По ходу нисходящего проектирования та или иная подзадача может
сформировать самостоятельный модуль. Тогда может быть применен принцип
модульного программирования.
Он обеспечивает легкость составления алгоритмов и отладки программ,
легкость сопровождения и модификации, а также возможность одновременной
разработки различных модулей разными специалистами с использованием разных
языков программирования.
При работе над модулем можно применить принцип структурного программирования.
Его цель - повышение читабельности и ясности алгоритма (и программы),
более высокой производительности программистов и упрощение отладки. В
соответствии с этим принципом для построения любого алгоритма (программы)
требуются три типовых блока:
. Функциональный. Используется для представления линейных
алгоритмов. Описывается языком графических символов следующим образом:
2.
Циклический. Используется для представления циклических алгоритмов. Описывается
языком графических символов одним из двух способов:
3. Конструкция принятия двоичного решения. Применяется для
представления разветвляющихся алгоритмов. Описывается языком графических
символов следующим образом:
При решении нашей курсовой работы мы будем придерживаться модульного
метода проектирования.
Вся наша программа будет состоять из нескольких модулей, у каждой из
которых будет своя функция. Это позволит проще отслеживать ошибки, а также
каждый модуль будет работать независимо от наличия ошибок в других частях
программы (модулях).
Далее приведеныблое-схемы модулей.
4.2
Блок-схемы функций
. Ввод БД из txt файла
. Сохранение текущей БД в txt файл
3.
Вывод текущей БД на экран
. Добавление новой строки с данными в БД
.
Удаление строки из БД
. Cортировка БД по номерам поездов
7.
Информация о поезде по
его номеру
8. Поиск поездов по первой букве пункта назначения
9.
Поиск поездов по
количеству мест
4.3 Метод
тестирования
Тестирование - очень важный и трудоемкий этап процесса разработки
программногообеспечения, так как правильное тестирование позволяет выявить
подавляющее большинствоошибок, допущенных при составлении программ.
Процесс разработки программного обеспечения предполагает три стадии
тестирования:автономное, комплексное и системное, каждая из которых
соответствует завершениюсоответствующей части Системы.
Различают два подхода к формированию тестов: структурный и
функциональный. Каждый изуказанных подходов имеет свои особенности и области
применения.
Структурное тестирование.
Структурное тестирование называют также тестированием по
"маршрутам", так как в этомслучае тестовые наборы формируют путем
анализа маршрутов, предусмотренных алгоритмом.
Под маршрутами при этом понимают последовательности операторов программы,
которыевыполняются при конкретном варианте исходных данных.
В основе структурного тестирования лежит концепция максимально полного
тестированиявсех маршрутов программы. Так, если алгоритм программы включает
ветвление, то при одномнаборе исходных данных может быть выполнена
последовательность операторов, реализующаядействия, которые предусматривает
одна ветвь, а при втором - другая. Соответственно, дляпрограммы будут
существовать маршруты, различающиеся выбранным при ветвлениивариантом.
Считают, что программа проверена полностью, если с помощью тестов удается
осуществитьвыполнение программы по всем возможным маршрутам передач управления.
Однако нетрудновидеть, что даже в программе среднего уровня сложности число
неповторяющихся маршрутовможет быть очень велико, и, следовательно, полное или
исчерпывающее тестированиемаршрутов, как правило, невозможно.
Структурный подход к тестированию имеет ряд недостатков. Так тестовые
наборы, построенные по данной стратегии:
§ не обнаруживают пропущенных маршрутов;
§ не обнаруживают ошибок, зависящих от обрабатываемых данных, например, в
операторе if (a - b) <eps - пропуск функции абсолютного значения abs
проявится только, если а <b;
§ не дают гарантии, что программа правильна, например, если вместо сортировки
по убыванию реализована сортировка по возрастанию.
Для формирования тестов программу представляют в виде графа, вершины
которогосоответствуют операторам программы, а дуги представляют возможные
варианты передачиуправления.
Функциональное тестирование.
Одним из способов проверки программ является тестирование с управлением
по данным или попринципу "черного ящика". В этом случае программа
рассматривается как "черный ящик", и цельютестирования является
выяснение обстоятельств, в которых поведение программы не
соответствуетспецификации.
Для обнаружения всех ошибок в программе, используя управление по данным,
необходимовыполнить исчерпывающее тестирование, т. е. тестирование на всех
возможных наборах данных. Длятех же программ, где исполнение команды зависит от
предшествующих ей событий, необходимопроверить и все возможные
последовательности. Очевидно, что проведение исчерпывающеготестирования для
подавляющего большинства случаев невозможно. Поэтому обычно
выполняют"разумное" или "приемлемое" тестирование, которое
ограничивается прогонами программы нанебольшом подмножестве всех возможных
входных данных. Этот вариант не дает гарантииотсутствия отклонений от
спецификаций.
Правильно выбранный тест должен уменьшать, причем более чем на единицу,
число другихтестов, которые должны быть разработаны для обеспечения требуемого
качества программногообеспечения.
Мы будем использовать именно этот способ тестирования, так как он менее
трудоемкий, чем метод "белого ящика" (структуный анализ).
5. Создание программы
.1 Дерево
функций
5.2
Последовательность создания программы
Мы проанализировали и исследовали задачу курсовой работы, выбрали метод
проектирования алгоритма, определили функции и возможности, которые будет
предоставлять программа. Теперь можно приступить непосредственно к разработке
программы и её модулей.
5.3 Сценарий диалога программы
№ вершины графа
|
Операция
|
Запуск программы
|
1
|
Меню программы
|
2
|
Создание файла
|
3
|
Вывод таблицы на экран
|
4
|
Сохранение таблицы в файл
|
5
|
Добавление записи
|
6
|
Удаление записи
|
7
|
Сортировка по номерам
поездов
|
8
|
Информация о поезде
|
9
|
Поиск поездов по первой
букве пункта назначения
|
10
|
Поиск поездов по количеству
мест
|
11
|
Завершение работы программы
|
Заключение
В данной курсовой работе была разработана программа, позволяющая работать
с базой данных "TRAIN" в соответствии с поставленными требованиями.
Программа включает в себя процедуры, обеспечивающие выполнение всех
поставленных задач для работы с базой данных. Главное меню программы позволяет
обеспечить доступ к функциям программы и к сведениям, хранящимся в базе данных
"TRAIN".
С помощью класса статических массивов эффективно использовалась память,
необходимая для работы программы. Проведенное тестирование показало
работоспособность программы и соответствие её требованиям задания на курсовой
проект.
Приложение 1
Описание разработанных функций
Название функции
|
Назначение функции
|
voidoutputfile()
|
Сохранение текущей БД в txt
файл
|
voidinputfile()
|
Ввод БД из txt файла
|
voidadd()
|
Добавление новой строки с
данными в БД
|
voiddeletetrain()
|
Удаление строки из БД
|
voidoutput()
|
Вывод текущей БД на экран
|
voidsort_np()
|
Сортировка по номерам
поездов
|
voidpoisk_no()
|
Информация о поезде по его
номеру
|
voidpoisk_pb()
|
Поиск поездов по первой
букве пункта назначения
|
voidpoisk_km()
|
Поиск поездов по количеству
мест
|
Описание глобальных переменных
struct train
char po[l] char pnl[l] int km intnp
|
-структура
"TRAIN" -пункт отправления -пункт назначения -количество мест -номер
поезда
|
Приложение 2
Листинг программы
#include<iostream.h>
#include<fstream.h>
#include<string.h>
#include<stdlib.h>
#include<conio.h>
#include<iomanip.h>
#include<vcl>l=30;train
{charpo[l], pn[l]; int km, np; };N=100;
{private: train x[N];:n;();();add();();output();_np();_no();_pb();_km();
};main()
{ trai a;.n=0;j;(1)
{ cout<<"1. Zagruzka is
faila.\n";<<"2. Vivodnaekran.\n";<<"3.
Sokhranenietablici v fail.\n";<<"4.
Dobavleniezapisi.\n";<<"5.
Udaleniezapisi.\n";<<"6. Sortirovkaponomerampoezdov.\n";<<"7.
Vivodinformacii o poezdepo ego nomeru.\n";<<"8. Poiskpoezdovpo
1 bukvepunktanaznacheniya.\n";<<"9.
Poiskpoezdovpokolichestvumest.\n";<<"10.
Vixod.\n\n";<<"Vashvibor (1%10):";>>j;(j)
{ case 1: a.inputfile(); break;2: a.output(); break;3:
a.outputfile();break;4: a.add(); break;5: a.deletetrain(); break;6:
a.sort_np();break;7: a.poisk_no();break;8: a.poisk_pb();break;9:
a.poisk_km();break;10: cout<<"Konecprogrammi."; getch();
exit(0);:cout<<"Net takogopunkta menu!\n"; getch(); break;}
}
}::inputfile()
{ifstream fin;file[l];<<"File name:";
cin>>file;.open(file);(fin==NULL) {cout<<"Doesn't
open.\n"; getch();
exit(1);}=0;{fin>>x[n].po>>x[n].pn>>x[n].km>>x[n].np;++;
}while(fin.good());-;<<"File was
inputted.\n"; getch();.close();();
}::output()
{cout<<"|"<<setw(3)<<i+1
<<"|"<<setw(19)<<setiosflags(ios::left)<<x[i].po
<<"|"<<setw(20)<<setiosflags(ios::left)<<x[i].pn
<<"|"<<setw(18)<<setiosflags(ios::left)<<x[i].km
<<"|"<<setw(13)<<setiosflags(ios::left)<<x[i].np<<"|"<<endl;
}<<"------------------------------------------------------------------------------\n";
}::add()
{ train t;(n==N)
{cout<<"Massivperepolnen.\n"; getch();
exit(0);}<<"Punktotpravleniya:";
cin>>x[n].po;<<"Punktnaznacheniya:";
cin>>x[n].pn;<<"Kolichestvomest:"; cin>>x[n].km;<<"Nomerpoezda:";
cin>>x[n].np;++;<<"Zapisdobavlena.\n";();();
}::deletetrain()
{charch;,j;();<<"Nomerudalennoistroki:";>>j;(j<1||j>n)
{cout<<"Net takoistroki.\n"; getch();
exit(0);}<<setw(20)<<x[j-1].po<<endl;<<"Udalit?(y/n):";
cin>>ch;(ch=='y')
{for(i=j;i<n;i++)[i-1]=x[i];-;
}<<"Zapisudalena.\n"; getch();
}::outputfile()
{ofstream out;file[l];;<<"File
name:";>>file;.open(file);(out==NULL) {cout<<"Ne
naiden"; getch(); exit(1);}(i=0;i<n;i++)
{out<<setw(22)<<setiosflags(ios::left)<<x[i].po
<<setw(25)<<setiosflags(ios::left)<<x[i].pn
<<setw(18)<<setiosflags(ios::left)<<x[i].km
<<setw(18)<<setiosflags(ios::left)<<x[i].np<<endl;}.close();<<"Fail
soxranen\n"; getch();
}::sort_np()
{intfl,nn;t;,j;,b;(i=0; i<n-1; i++)
{(j=i; j<n; j++)
{(x[i].np>x[j].np) {t=x[i]; x[i]=x[j]; x[j]=t;}
}
}();
}