Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
Математическая формулировка задачи
Разработать программу, реализующую сортировку массива структур (50 элементов). В качестве элемента массива выбрать структуру, соответствующую индивидуальному варианту. Предусмотреть заполнение массива из файла (подготовить файл на 50 элементов).
Программа должна реализовать не менее 3-х алгоритмов сортировки (на выбор программиста). При этом алгоритм сортировки, направление сортировки (по возрастанию/по убыванию), ключ сортировки (одно или несколько полей) и длину ключа (для текстовых полей) выбирает пользователь. Выполнить сравнительный анализ для различных алгоритмов сортировки (скорость выполнения, количество сравнений, количество перестановок). Отсортированный массив и результаты анализа хранить в текстовых файлах.
Предусмотреть многоуровневое меню:
1) Заполнение массива из файла (выбор файла, тек. папка, любая папка)
2) Выбор алгоритма сортировки
3) Выбор ключевого поля (или нескольких полей – до 3-х)
4) Установка длины ключа (для текстовых полей)
5) Сохранение результата
6) Вывод сравнительного анализа последних сортировок
a) на экран
b) в файл
7) Выход
Описание использованных сортировок:
Сортировка - это процесс перестановки объектов данного множества в определённом порядке. Цель сортировки - облегчить последующий поиск элементов в отсортированном множестве. Поэтому элементы сортировки присутствуют во многих задачах прикладного программирования.
Пузырьковая сортировка
Этот метод назван так потому, что с каждым циклом самый легкий элемент поднимается вверх списка, подобно пузырьку.
В первом проходе сравниваются попарно элементы: первый – второй, второй – третий, третий – четвертый и т.д. до n-1 – n. Каждый раз в паре самый легкий перемещается вверх. В результате одного прохода самый тяжелый элемент опустится на дно.
Сортировка методом простого выбора
Основные действия алгоритма для сортировки массива длиной L заключаются в следующем:
Для каждого значения индекса i выполнить два действия:
1) Среди элементов с индексами от i до (L-1) найти элемент с минимальным значением (если сортировка производится по возрастанию).
2) Обменять значения i-го и минимального элементов.
Сортировка методом простого включения
В сортировке включениями элементы разделяются на уже упорядоченную и неупорядоченную последовательности. В начале упорядоченная часть содержит только один элемент. Очередной элемент из начала неупорядоченной части вставляется на подходящее место в упорядоченную часть. При этом упорядоченная часть удлиняется на один элемент, а неупорядоченная - укорачивается. Сортировка заканчивается при исчезновении неупорядоченной части.
Описание программы.
В начале программы пользователю предлагается многоуровневое меню с выбором действий, которые программа выполняет. В первом пункте меню предлагается заполнить массив структурами из файла. При его выборе пользователю будет предложено ввести имя и адрес файла, который будет считан в массив.
При выборе второго пункта меню будет предложен выбор алгоритма сортировки, с помощью которой будет отсортирован массив.
При выборе третьего пункта меню будет предложен выбор ключевого поля, по которому и будет сортироваться массив.
При выборе четвёртого пункта меню на экран выведется количество элементов.
При выборе пятого пункта меню будет предложено сохранить результаты сортировки в файл.
При выборе шестого пункта меню будет предложено вывести сравнительный анализ последних сортировок на экран или записать в файл.
При выборе седьмого пункта меню произойдёт выход из программы.
Подробнее об основных функциях программы.
Функции, использованные в программе:
Здесь будет дано описание функций содержащихся в программе. Сам код программы будет представлен на «Приложении 1».
- Функция «main()» содержит вызов функции «Меню»;
- Функция «PrintMenu()» выводит на экран первый уровень меню, где пользователь должен сделать выбор, что делать дальше;
- Функция «Menu()» содержит остальные уровни меню, с последуюющим вызовом других функций, в зависимости от выбора действий пользователем;
- Функция «Load(string fileName)» используется для считывания массива структур с файл для дальнейших операций с ним;
- Функция «Sort1(bool up)» предназначена для выполнения пузырьковой сортировки;
- Функция «Sort2(bool up)» предназначена для выполнения сортировки методом простого выбора;
- Функция «Sort3(bool up)» предназначена для выполнения сортировки методом простого включения;
- Функция «compare(sotrudnik *a, sotrudnik *b, bool up)» предназначена для сравнения параметров при сортировке;
- Функция «swap(sotrudnik *a, sotrudnik *b)» предназначена для выполнения перестановки при сортировке;
- Функция «SaveResult(string fileName)» предназначена для сохранения результатов сортировки в файл;
- Функция «SaveSortInfo(string fileName)» предназначена для сохранения сравнительного анализа последних сортировок в файл;
- Функция «DisplaySortInfo()» предназначена для вывода сравнительного анализа последних сортировок на экран.
3.3. Блок-схема алгоритма:
4.Контрольный пример.
При запуске программы на экране появится окно с главным меню, в котором предложены варианты возможных действий программы (рисунок 1).
Рисунок 1 – Вид окна сразу после запуска программы.
При выборе первого пункта меню, будет предложено ввести имя файла (при необходимости и путь) в котором расположен массив структур (рисунок 2, 3 и 4).
Рисунок 2 – Первый пункт, считывание массива структур с файла.
Нажатием любой клавиши, меню обновится. При выборе второго пункта, будет предложен выбор метода сортировки (рисунок 3).
Рисунок 3 – Второй пункт, выполнение сортировки.
Рисунок 4 – Второй пункт, выполнение сортировки.
Рисунок 5 – Второй пункт, выполнение сортировки.
При нажатии любой клавиши, меню обновится. При выборе третьего пункта, будет предложено выбрать ключевое поле (рисунок 4.6).
Рисунок 6 – Выбор ключевого поля.
При нажатии любой клавиши, меню обновится. При выборе четвертого пункта на экран выведется количество элементов (рисунок 7).
Рисунок 4.7 – Четвертый пункт, вывод количества элементов.
При нажатии любой клавиши, меню обновится. При выборе пятого пункта, будет предложено сохранить результаты сортировки в файл (рисунок 8).
Рисунок 8 – Пятый пункт, сохранение результатов в файл.
При нажатии любой клавиши, меню обновится. При выборе шестого пункта, будет предложено вывести сравнительный анализ на экран или в файл(рисунок 9 и 10).
Рисунок 9 – Шестой пункт, вывод сравнительного анализа на экран.
Рисунок 10 – Шестой пункт, вывод сравнительного анализа в файл.
При нажатии любой клавиши, меню обновится. При выборе седьмого пункта, осуществится выход из программы (рисунок 11).
Рисунок 11 – Седьмой пункт, выход из программы.
5. ВЫВОДЫ
В результате работы была написана программа, которая реализует алгоритм очереди как в статическом варианте (на основе массива структур), так и в динамическом. В неё предусмотрены функции добавления и удаления элементов. Программа может считывать данные, как с консоли, так и из файла. Также она может выводить полученный результат и в файл и на консоль. В программе реализован алгоритм обработки исключений. Также в программе реализована обработка ошибочных ситуаций, например переполнение очереди, удаление из пустого дека, вывод элементов пустой очереди и т.п. На практике были закреплены знания по алгоритмическому языку С++, а именно работа с операторами циклов и ветвлений, стандартными функциями ввода-вывода, функциями работы с файлами и строками. Программа не использует временных файлов и поэтому.exe файл может находиться на защищенном от записи носителе, главное правильно указать расположение файла результата.
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
1. Уолтер Сэвитч. С++ в примерах. Москва: Эком, 1997.
2. Язык программирования Си. Москва: Производственно-внедренческий кооператив "И Н Т Е Р Ф Е Й С", 1988.
3. Б.В. Керниган,Д.М. Ричи. ЯЗЫК С.
4. В.А. Скляров. Программирование на языках Си и Си++. Мн.: Выш. шк.,1997. - 528с.
5. Страуструп Бьерн. Язык программирования Си++. М.: Софт,1999.
6. Шилд Герберт. - Самоучитель C++ / Герберт Шилдт. - СПб: BHV - Санкт-Петербург, 1997. - 511 с.
7. Nixon M., Aguado A. Feature extraction and image processing // Newnes, 2002, p. 350.
Приложение А
#include "stdafx.h"
#include <iostream>
#include <string>
#include <ctime>
#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <fstream>
#include <boost/chrono.hpp>
#include <boost/thread.hpp>
#include <windows.h>
#include <conio.h>
using namespace std;
using namespace boost;
int kolich=0; //переменная для подсчета количества элементов
string Par1 = "Номер", Par2; //параметр, отображающий установленную сортировку
long Time1, Time2, Time3; //время сортировки
using boost::chrono::high_resolution_clock;
using boost::chrono::nanoseconds;
struct Shop //структура
{
int num; //номер (ключ)
string name; //Название
string fio; //ФИО директора
int kol; //Количество сотрудников
int dohod; //Годовой доход
};
Shop mass[50]; //объявление массива структур
byte index = 0; //начальное значение индекса
void swap(Shop *a, Shop *b) //своп структуры
{
auto t = a;
a = b;
b = t;
}
bool compare(Shop *a, Shop *b, bool up) //сравнивание параметров при сортировке
{
if (index == 0) // номер (ключ)
{
Par1 = "Номер";
auto v1 = a->num;
auto v2 = b->num;
if (up? (v1 > v2): (v1 < v2)) //если соритировка по убыванию то (v1>v2), иначе (v1<v2)
{
return true;
}
else
{
return false;
}
}
if (index == 1) // Название
{
Par1 = "Название магазина: ";
auto v1 = a->name;
auto v2 = b->name;
if (up? (v1 > v2): (v1 < v2)) //если соритировка по убыванию то (v1>v2), иначе (v1<v2)
{
return true;
}
else
{
return false;
}
}
if (index == 2) // Фамилия Имя директора
{
Par1 = "Фамилия Имя директора: ";
auto v1 = a->fio;
auto v2 = b->fio;
if (up? (v1 > v2): (v1 < v2)) //если соритировка по убыванию то (v1>v2), иначе (v1<v2)
{
return true;
}
else
{
return false;
}
}
if (index == 3) //Количество сотрудников
{
Par1 = "Количество сотрудников:";
auto v1 = a->kol;
auto v2 = b->kol;
if (up? (v1 > v2): (v1 < v2)) //если соритировка по убыванию то (v1>v2), иначе (v1<v2)
{
return true;
}
else
{
return false;
}
}
if (index == 4) // Доход
{
Par1 = "Доход: ";
auto v1 = a->dohod;
auto v2 = b->dohod;
if (up? (v1 > v2): (v1 < v2)) //если соритировка по убыванию то (v1>v2), иначе (v1<v2)
{
return true;
}
else
{
return false;
}
}
}
void Load(string fileName) //загрузка файла
{
ifstream file; //объявленеие переменной для файла
file.open(fileName); //открытие файла
if (!file)
{
cout << "Неверное имя файла " << fileName << endl;
return;
}
kolich = 0;
for (int i = 0; i < 50; i++) //очистка массива
{
mass[i].num = 0;
mass[i].name = "";
mass[i].fio = "";
mass[i].kol = 0;
mass[i].dohod = 0;
}
while (!file.eof()) //чтение файла
{
string str;
getline(file, str);
mass[kolich].num = atoi(str.c_str()); //чтение номера
getline(file, mass[kolich].name); //чтение названия
getline(file, mass[kolich].fio); //чтение ФИ
getline(file, str);
mass[kolich].kol = atoi(str.c_str()); //чтение количества сотрудников
getline(file, str);
mass[kolich].dohod = atoi(str.c_str()); //чтение дохода
kolich = kolich++;
}
cout << "Файл " << fileName << " загружен" << endl;
}
void SaveResult(string fileName) //сохранение результата сортировок
{
if (kolich == 0) //если в списке нет данных
{
cout << "Данных нет в списке!" << endl;
return;
}
ofstream file(fileName);
if (!file)
{
cout << "Неверное имя файла " << fileName << endl;;
exit(1);
}
if (kolich!= 0) //если в списке есть данные
{
if (Par2!= "")
{
file << "Сортировка списка: " << Par2 << endl;
file << "Ключевое поле: " << Par1 << endl;
}
else
{
file << "Список не отсортирован!" << endl;
}
for (int i = 0; i < kolich; i++)
{
file << mass[i].num << endl;
file << mass[i].name << endl;
file << mass[i].fio << endl;
file << mass[i].kol << endl;
file << mass[i].dohod << endl;
file << endl;
}
}
file.close();
cout << "Файл " << fileName << " сохранен" << endl;
}
void SaveSortInfo(string fileName) //сохранение информации по времени сортировок
{
if (kolich == 0)
{
cout << "Данных нет в списке!" << endl;
return;
}
ofstream file(fileName);
if (!file)
{
cout << "Неверное имя файла " << fileName << endl;;
exit(1);
}
else
{
if ((Time1 == 0) && (Time2 == 0) && (Time3 == 0))
{
file << "Список не отсортирован!" << endl;
}
else
{
file << "Время сортировок в наносекундах:" << endl;
if (Time1!= 0)
{
file << "1)пузырьковая сортировка = " << Time1 << endl;
}
else
{
file << "Структуры не сортировалась пузырьковой сортировкой!" << endl;
}
if (Time2!= 0)
{
file << "2)методом простого выбора = " << Time2 << endl;
}
else
{
file << "Структуры не сортировалась методом простого выбора!" << endl;
}
if (Time3!= 0)
{
file << "3)методом простого включения = " << Time3 << endl;
}
else
{
file << "Структуры не сортировалась методом простого включения!" << endl;
}
}
}
file.close();
cout << "Файл " << fileName << " сохранен" << endl;
}
void DisplaySortInfo() //вывод информации по времени сортировок на экран
{
if (kolich == 0)
{
cout << "Список пустой!" << endl;
return;
}
else
{
if ((Time1 == 0) && (Time2 == 0) && (Time3 == 0))
{
cout << "Список не отсортирован!" << endl;
}
else
{
cout << "Время сортировок в наносекундах:" << endl;
if (Time1!= 0)
{
cout << "1)пузырьковая сортировка = " << Time1 << endl;
}
else
{
cout << "Структуры не сортировалась пузырьковой сортировкой!" << endl;
}
if (Time2!= 0)
{
cout << "2)методом простого выбора = " << Time2 << endl;
}
else
{
cout << "Структуры не сортировалась методом простого выбора!" << endl;
}
if (Time3!= 0)
{
cout << "3)методом простого включения = " << Time3 << endl;
}
else
{
cout << "Структуры не сортировалась методом простого включения!" << endl;
}
}
}
}
void Sort1(bool up) //пузырьковая сортировка
{
Par2 = up? ("по убыванию"): ("по возрастанию");
if (kolich == 0) //если список пуст
{
cout << "Список пуст!" << endl;
return;
}
if (kolich == 1) //если в списке 1 элемент
{
cout << "В списке 1 элемент!" << endl;
return;
}
auto t0 = high_resolution_clock::now(); //счетчик времени
int i, j;
for (i = kolich - 1; i > 0; i--) //проходы элементов
{
for (j = 0; j < i; j++)
{
if (compare(mass + j, mass + j + 1, up)) //сравнивание текущего и следущего элемента
{
swap(mass[j], mass[j + 1]); //обмен элементов
}
}
}
Sleep(1);
auto t1 = high_resolution_clock::now(); //время выполнения сортировки
nanoseconds total_ms = boost::chrono::duration_cast<nanoseconds>(t1 - t0);
Time1 = total_ms.count();
cout << "Структуры отсортированы" << endl;
}
void Sort2(bool up) //сортировка методом простого выбора
{
Par2 = up? ("по убыванию"): ("по возрастанию");
if (kolich == 0) //если список пуст
{
cout << "Список пуст!" << endl;
return;
}
if (kolich == 1) //если в списке 1 элемент
{
cout << "В списке 1 элемент!" << endl;
return;
}
auto t0 = high_resolution_clock::now(); //счетчик времени
int i, j;
for (i = 0; i < kolich; i++) //цикл проходов, i - номер прохода
{
auto temp = mass[i];
for (j = i - 1; j >= 0 && (compare(mass + j, &temp, up)); j--) //поиск места элемента
{
mass[j + 1] = mass[j]; //сдвигаем элемент вправо, пока не дошли
}
mass[j + 1] = temp; //вставить элемент
}
Sleep(1);
auto t1 = high_resolution_clock::now(); //время выполнения сортировки
nanoseconds total_ms = boost::chrono::duration_cast<nanoseconds>(t1 - t0);
Time2 = total_ms.count();
cout << "Структуры отсортированы" << endl;
}
void Sort3(bool up) //cортировка методом простого включения
{
Par2 = up? ("по убыванию"): ("по возрастанию");
if (kolich == 0) //если список пуст
{
cout << "Список пуст!" << endl;
return;
}
if (kolich == 1) //если в списке 1 элемент
{
cout << "В списке 1 элемент!" << endl;
return;
}
auto t0 = high_resolution_clock::now(); //счетчик времени
int i, j, min;
for (i = 0; i < kolich - 1; i++) {
min = i; //устанавливаем начальное значение минимального индекса
for (j = i + 1; j < kolich; j++) //находим минимальный индекс элемента
{
if (compare(mass + j, mass + min, up))
{
min = j; //меняем значения местами
}
}
swap(mass[i], mass[min]); //обмен элементов
}
Sleep(1);
auto t1 = high_resolution_clock::now(); //время выполнения сортировки
nanoseconds total_ms = boost::chrono::duration_cast<nanoseconds>(t1 - t0);
Time3 = total_ms.count();
cout << "Структуры отсортированы" << endl;
}
void PrintMenu() //Меню
{
cout<<"Введите номер пункта, соответствующего вашему выбору: "<<endl;
cout<<"___________________________________________________________"<<endl;
cout<<"| 1 |Заполнение массива из файла |"<<endl;
cout<<"|-----|---------------------------------------------------|"<<endl;
cout<<"| 2 |Выбор алгоритма сортировки |"<<endl;
cout<<"|-----|---------------------------------------------------|"<<endl;
cout<<"| 3 |Выбор ключевого поля |"<<endl;
cout<<"|-----|---------------------------------------------------|"<<endl;
cout<<"| 4 |Вывод количества элементов |"<<endl;
cout<<"|-----|---------------------------------------------------|"<<endl;
cout<<"| 5 |Сохранение результата |"<<endl;
cout<<"|-----|---------------------------------------------------|"<<endl;
cout<<"| 6 |Вывод сравнительного анализа последних сортировок |"<<endl;
cout<<"|-----|---------------------------------------------------|"<<endl;
cout<<"| 7 |Выход |"<<endl;
cout<<"|_____|___________________________________________________|"<<endl;
}
void Menu() //Управление меню
{
int v=0; //переменная выбора пункта меню
int w=0; //переменная выбора подпункта меню
do
{
PrintMenu();
cin>>v;
switch(v)
{
case 1: //Заполнение списка из файла (выбор файла, тек. папка, любая папка)
{
cout << "Введите имя файла, при необходимости с путём" << endl;
string fileName;
cin >> fileName;
Load(fileName); //загрузка файла
getch(); //задержка экрана
std::system("cls"); //очистка экрана
break;
}
case 2: //Выбор алгоритма сортировки
{
cout<<"Выберите алгоритм сортировки: "<<endl;
cout<<"1/2. Пузырьковая сортировка (по возрастанию/по убыванию)"<<endl;
cout<<"3/4. Сортировка методом простого выбора (по возрастанию/по убыванию)"<<endl;
cout<<"5/6. Сортировка методом простого включения (по возрастанию/по убыванию)"<<endl;
cin>>w;
switch(w)
{
case 1:
{
cout << "Пузырьковая сортировка по возрастанию" << endl;
Sort1(false);
getch();
std::system("cls");
break;
}
case 2:
{
cout << "Пузырьковая сортировка по убыванию" << endl;
Sort1(true);
getch();
std::system("cls");
break;
}
case 3:
{
cout << "Сортировка методом простого выбора по возрастанию" << endl;
Sort2(false);
getch();
std::system("cls");
break;
}
case 4:
{
cout << "Сортировка методом простого выбора по убыванию" << endl;
Sort2(true);
getch();
std::system("cls");
break;
}
case 5:
{
cout << "Сортировка методом простого включения по возрастанию" << endl;
Sort3(false);
getch();
std::system("cls");
break;
}
case 6:
{
cout << "Сортировка методом простого включения по убыванию" << endl;
Sort3(true);
getch();
std::system("cls");
break;
}
}
break;
}
case 3: //Выбор ключевого поля (или нескольких полей – до 3-х)
{
cout<<"Выберите ключевое поле: "<<endl;
cout<<"1. Номер (ключ)"<<endl;
cout<<"2. Название магазина"<<endl;
cout<<"3. ФИ директора"<<endl;
cout<<"4. Количество сотрудников"<<endl;
cout<<"5. Доход"<<endl;
cin>>w;
switch (w)
{
case 1:
{
cout << "Выбрано ключевое поле [Номер (ключ)] " << endl;
index = 0;
getch();
std::system("cls");
break;
}
case 2:
{
cout << "Выбрано ключевое поле [Название магазина] " << endl;
index = 1;
getch();
std::system("cls");
break;
}
case 3:
{
cout << "Выбрано ключевое поле [ФИ директора] " << endl;
index = 2;
getch();
std::system("cls");
break;
}
case 4:
{
cout << "Выбрано ключевое поле [Количество сотрудников] " << endl;
index = 3;
getch();
std::system("cls");
break;
}
case 5:
{
cout << "Выбрано ключевое поле [Доход] " << endl;
index = 4;
getch();
std::system("cls");
break;
}
}
break;
}
case 4: //Вывод количества элементов в списке
{
cout << "в списке " << kolich << " элемента/ов" << endl;
getch();
std::system("cls");
break;
}
case 5: //Вывод результата (на экран/в файл)
{
cout << "Введите имя файла, при необходимости с путём" << endl;
string fileName;
cin >> fileName;
SaveResult(fileName);
getch();
std::system("cls");
break;
}
case 6: //Вывод сравнительного анализа последних сортировок (на экран/в файл)
{
cout<<"1.Вывод сравнительного анализа последних сортировок на экран"<<endl;
cout<<"2.Вывод сравнительного анализа последних сортировок в файл"<<endl;
cin>>w;
switch (w)
{
case 1:
{
DisplaySortInfo();
getch();
std::system("cls");
break;
}
case 2:
{
cout << "Введите имя файла, при необходимости с путём" << endl;
string fileName;
cin >> fileName;
SaveSortInfo(fileName);
getch();
std::system("cls");
break;
}
}
break;
}
case 7: //Выход
{
break;
}
default:
{
cout << "Некоректный выбор" << endl;
getch();
std::system("cls");
break;
}
}
}
while(v!=7);
}
int main() //Главная функция программы
{
setlocale(LC_CTYPE, "Russian");
Menu(); //вызов меню
return 0;
}
Date: 2016-05-24; view: 534; Нарушение авторских прав; Помощь в написании работы --> СЮДА... |