">
Информатика Программирование
Информация о работе

Тема: Программа сортировки методом Выбора

Описание: Описание метода решения задачи, программы, файла main.cpp, файла header.h, методики тестирования. Блок-схема программы. Руководство пользователя по работе. Особенности ввода из файла. Распечатка текста программ. Метод сортировки выбором массива элементов.
Предмет: Информатика.
Дисциплина: Программирование.
Тип: Курсовая работа
Дата: 15.08.2012 г.
Язык: Русский
Скачиваний: 47
Поднять уникальность

Похожие работы:

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

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ

Кафедра радиотехники и защиты информации (РЗИ)

ПРОГРАММА СОРТИРОВКИ МЕТОДОМ «ВЫБОРА»

Пояснительная записка к курсовой работе.

Студент гр. 181

______________С. Е. Рогожкин

Руководитель

Доцент кафедры РЗИ, к.т.н.

______________Д. А. Конкин

2012 Реферат

Курсовая работа 18 с., 1 рис.,1 источник, 1 приложение.

МЕТОД ВЫБОРА, СОРТИРОВКА, ПРОГРАММА.

Объектом разработки является демонстрационная программа сортировки массива данных.

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

В процессе работы был использован метод сортировки выбором массива элементов.

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

Программное обеспечение разработано в среде DevCpp 4.9.9.6. Пояснительная записка выполнена в текстовом редакторе Microsoft Word 2010.

СОДЕРЖАНИЕ

Введение5

1. Описание метода решения задачи6

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

2.1 Описание файла main.cpp7

2.2 Описание файла header.h7

3. Описание методики тестирования программы9

4. Руководство пользователя по работе с программой11

5. Блок схема программы12

Заключение7

Приложение А Файл main.cpp14

Приложение B Файл header.h14

Введение

Основной целью работы является разработка программного продукта,

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

Существует несколько методов сортировки данных. Например, пузырьком, методом Шелла, быстрая сортировка и т. д.

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

1 Описание метода решения задачи

Алгоритм сортировки методом выбора.

Сортировка массива данных будет производиться в порядке возрастания.

Алгоритм:

1. Поиск минимального значения в неотсортированном массиве.

2. Обмен этого значения со значением на первой неотсортированной позиции.

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

Таким образом, элементы слева от массива выстраиваются от наименьшего элемента до наибольшего.

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

Программа состоит из основного файла – main.cpp и дополнительного файла – header.h, в котором находятся прототипы функций, описанных в основном файле программы.

2.1 Описание файла main.cpp

Переменные в функции main:

int fail – переменная, в которую записывается значение функций возвращающих 0 или 1, в зависимости от корректности вводимых или проверяемых данных.

В программе использованы следующие функции:

void vvodsklaviatury(void) – функция, реализующая ввод данных с клавиатуры.

int chteniesfaila(void) – функция, реализующая ввод данных из файла. Функция возвращает 1, если данные в файле некорректны.

void sluchzap(void) – функция, реализующая заполнение массива случайными числами.

void vyborvvoda(void) – функция, реализующая выбор варианта ввода данных.

int proverka(char*) – функция проверки вводимых данных на корректность. В функцию пересылается строка с введёнными данными. Функция возвращает целое двузначное число, хранящееся в передаваемой ей строке. При некорректности данных функция изменяет глобальную переменную flag.

void processort (void) – функция, реализующая процесс сортировки данных.

Описание функции main():

Вызываем функцию vyborvvoda() для выбора варианта ввода.

Если выбран ввод с клавиатуры, вызываем функцию vvodsklaviatury().

Если выбран вариант заполнения массива случайными символами, вызываем функцию sluchzap().

Если выбран ввод из файла, вызываем функцию chteniesfaila() и присваиваем возвращаемое ею значение переменной ret. Если функция возвратила 1, то закрываем программу.

Вызываем функцию processort().

Закрываем программу.

Ход выполнения программы:

Вызываем функцию vyborzapmas(), в которой программа запрашивает вариант ввода: с клавиатуры, из файла или заполнение случайными числами. Затем, в зависимости от выбранного варианта ввода происходит ввод данных. Если какое-либо значение введенное пользователем некорректно, то меняем сигнализирующую о некорректном вводе данных переменную flag на единицу и выходим из функции.

Далее проверяется flag. Если переменная равна единице, то происходит вывод на экран сообщения о некорректном вводе данных пользователем и предлагается ввести корректные данные.

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

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

После ввода данных программа запрашивает режим сортировки: пошаговый или автоматический.

Затем происходит процесс сортировки, после которого программа закрывается.

2.2 Описание файла header.h

Во вспомогательном файле header.h описаны следующие глобальные переменные:

int flag – переменная, сигнализирующая о некорректности введённых данных.

int N – переменная, в которую вводится количество элементов массива.

int choice – переменная, в которой хранится информация о выбранном варианте ввода.

int mass[40] – массив, в который вводятся исходные данные.

Созданы прототипы следующих функций, описанных в основном файле программы:

void vvodsklaviatury(void);

int chteniesfaila(void);

void sluchzap(void);

void vyborzapmas(void);

void processort(void);

int proverka(char*);

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

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

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

Введённый массив:

64 3 78 23 15 75 20 0 63 75

Отсортированный массив:

0 3 15 20 23 63 64 75 75 78

Введённый массив:

23 34 45 46 67 43 23 26 46 03 94 85

Отсортированный массив:

3 23 23 26 34 43 45 46 46 67 85 94

Введённый массив:

28 39 10 47 58 39 20 17 37 48 29 10 4 2

Отсортированный массив:

2 4 10 10 17 20 28 29 37 39 39 47 48 58

4 Блок-схема программы

Ниже, на рисунке 4.1 изображена блок-схема программы .



Рисунок 4.1

5 Руководство пользователя по работе с программой

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

Скопируйте программу в произвольную папку.

5.2 Запуск программы.

Запустите файл main.exe.

5.3 Ввод данных.

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

Для ввода данных нужно следовать указаниям на экране.

5.4 Особенности ввода из файла.

Имя файла должно содержать не более 255 символов (включая путь), должно содержать только латинские буквы, не должно содержать пробелов.

Файл должен содержать информацию в виде.

Input.txt

N

mass1 mass2 mass3 …

mass1, mass2 … – элементы массива, N – количество элементов.

Количество элементов не более 40.

5.5 Примечание.

Программа тестировалась и корректно работает в ОС Windows 7.

Заключение

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

Рекомендации по использовании программного продукта:

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

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

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

1. Ананий В. Левитин Глава 3. Метод грубой силы: Сортировка выбором // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 143-144.

Приложение А

(обязательное)

Распечатка текста программы

Ниже приведена распечатка исходного кода для файла main.exe

#include

#include

#include

#include

#include

using namespace std;

int flag;

int N;

int choice;

int mass[40];

void vvodsklaviatury(void);

int chteniesfaila(void);

void sluchzap(void);

void vyborzapmas(void);

void processort(void);

int proverka(char*);

int main()

{

int fail=0;

//Выбор варианта ввода данных

vyborzapmas();

//Если выбран ввод с клавиатуры

if (choice==1)

vvodsklaviatury();

//Если выбрано случайное заполнение

if (choice==2)

sluchzap();

//Если выбрано чтение с файла

if (choice==3)

fail=chteniesfaila();

//Если ошибка, то закрываем программу

if (fail)

{

system(“pause”);

return 0;

}

//Процесс сортировки

processort();

return 0;

}

//Функция выбора варианта ввода

void vyborzapmas(void)

{

char string[50];

while((choice!=1)&&(choice!=2)&&(choice!=3))

{

cout << "Kak sformirovst massiv? 1. Vvesti s klaviatury 2. Datchikom sluchajnyh chisel 3. Schitat s faila ";

cin >> string;

cout << " ";

choice=proverka(string);

if ((choice!=1)&&(choice!=2)&&(choice!=3))

cout << "Vy dolzhny vvesti 1,2 ili 3. ";

}

}

//Функция чтения данных с файла

int chteniesfaila(void)

{

char filename[255];

while (1) //Ввод имени и проверка файла

{

for (int i=0;i<255;i++) filename[i]=0;

cout << "Vvedite imia faila. ";

cin >> filename;

cout << " ";

fstream input; //проверка файла

input.open (filename);

char symbol=0;

input >> symbol;

input.close();

if (symbol==0)

{

cout << "Fail "" << filename << "" ne sushestvuet ili pustoj. ";

continue;

}

break;

}

fstream input;

input.open (filename);

//Читаем файл

char string[50];

input >> string;

N=proverka(string);

if (flag==1)

{

cout << "Dannye v faile nekorrektny. Programma budet zakryta. ";

return 1;

}

for (int i=0;i{

for (int q=0; q<50; q++) string[q]=0;

input >> string;

mass[i]=proverka(string);

if (flag==1)

{

cout << "Dannye v faile nekorrektny. Programma budet zakryta. ";

return 1;

}

if (!(0<=N&&N<=40))

{

cout << "Dannye v faile nekorrektny. Programma budet zakryta. ";

return 1;

}

}

return 0;

}

//Функция ввода данных с клавиатуры

void vvodsklaviatury(void)

{

char string[50];

while(1)

{

for (int i=0;i<50;i++) string[i]=0;

cout << "Skolko elementov soderjit massiv? ";

cin >> string;

cout << " ";

N=proverka(string);

if (flag==1)

{

cout << "Vvednnoe chislo nekorrektno! ";

continue;

}

if (!(0<=N&&N<=40))

{

cout << "Kollichestvo elementov ne bolee 40! ";

continue;

}

break;

}

cout << "Vvodute elementy massiva. ";

for (int i=0;i{

for (int q=0;q<50;q++) string[q]=0;

cin >> string;

mass[i]=proverka(string);

if (flag==1)

{

cout << "Vvedennoe chislo (" << i+1 << ") nekorrektno. Vvedite ego povtorno. ";

i--;

}

if (!(0<=mass[i]&&mass[i]<=99))

{

cout << "Vy doljny vvesti celoe, neotricatelnoe chislo ot 0 do 99! Vvedite ego povtorno. ";

i--;

}

}

}

//Функция случайного заполнения массива

void sluchzap(void)

{

while(true)

{

char string[50];

for (int i=0;i<50;i++) string[i]=0;

cout << "Skolko elementov soderjit massiv? ";

cin >> string;

cout << " ";

N=proverka(string);

if (flag==1)

{

cout << "Vvednnoe chislo nekorrektno! ";

continue;

}

if (!(0<=N&&N<=40))

{

cout << "Kollichestvo elementov ne bolee 40! ";

continue;

}

break;

}

for (int i=0;i{

mass[i]=rand()%100;

}

}

//Функция вычисления интеграла

void processort(void)

{

char string[50];

int rejim=0;

while(rejim!=1&&rejim!=2)

{

cout << "Kak otobrazit dannye? 1. V poshagovom rejime 2. V avtomaticheskom rejime ";

cin >> string;

cout << " ";

rejim=proverka(string);

if (rejim!=1&&rejim!=2)

cout << "Vy dolzhny vvesti 1 ili 2. ";

}

if (rejim==1)

{

cout << "Sortiruem massiv po stadijam, vybiraja kajdyj raz naimenshee iz pravoj chasti i stavja ego sleva. ";

}

cout << "Ishodnyj massiv imeet vid: ";

for (int q=0;q{

cout << mass[q] << " ";

}

cout << " ";

system(“pause”);

for (int i=0;i{

int min=i;

for (int q=i+1;q{

if (mass[q]{

min=q;

}

}

int temp=mass[i];

mass[i]=mass[min];

mass[min]=temp;

if (rejim==1)

{

cout << "Massiv na dannoj stadii imeet vid: ";

for (int q=0;q{

cout << mass[q] << " ";

}

cout << " ";

system(“pause”);

}

}

cout << "Otsortirovannyj massiv: ";

for (int q=0;q{

cout << mass[q] << " ";

}

cout << " ";

system(“pause”);

}

//Функция проверки вводимых данных

int proverka(char string[50])

{

flag=0;

if (strlen(string)>2)

{

flag=1;

return 0;

}

for (int i=0; i{

if (!(0<=string[i]&&string[i]<=9))

{

flag=1;

return 0;

}

}

return atoi(string);

}

Приложение Б

(обязательное)

Распечатка текста программы

Ниже приведена распечатка исходного кода для файла header.h

#include

#include

#include

#include

#include

using namespace std;

int flag;

int N;

int choice;

int mass[40];

void vvodsklaviatury(void);

int chteniesfaila(void);

void sluchzap(void);

void vyborzapmas(void);

void processort(void);

int proverka(char*);