Министерство
Образования и Науки Украины
Национальный
Аэрокосмический Университет
им. Н. Е. Жуковского “ХАИ”
Кафедра 302
Домашнее задание по курсу
„Программирование
и алгоритмические языки”
по теме:
„СОРТИРОВКА МАССИВОВ МЕТОДОМ ВСТАВОК”
Выполнил:
студент 326 группы
Чаплыгин В. И.
Проверил:
Момот М. А.
Харьков
2003
1.
Постановка задачи
……………………………………………………………… 3
2.
Теоретическое обоснование и алгоритм
решения задачи …………………… 3
3.
Пример работы программы
……………………………………………………. 4
4.
Исходный код программы с
комментариями …………...……………………. 9
5.
Список литературы
…………………………………………………………… 13
6.
Приложение 1: блок-схема программы
……………………………………... 14
7.
Приложение 2: блок-схема функции сортировки
(SortByIncrease()) ……… 15
Постановка
задачи
Задание:
Упорядочить
массив x по убыванию
или возрастанию (т.е. переставить его элементы так чтобы для всех k выполнялось xk<=xk-1 или xk>=xk-1 соответственно),
используя следующий алгоритм сортировки (упорядочивания):
сортировка вставками: пусть первые k
элементов массива уже упорядочены по не убыванию; берется (k+1)-й
элемент и размещается среди первых k элементов так, чтобы упорядоченными
оказались уже k+1 первых элементов; этот метод применяется при k
от 1 до n-1.
Основные
требования к программе:
·
В
программе должны использоваться функции, для которых следует явно сопоставить
прототипы (объявления, описания), определения и вызовы.
·
Как
минимум в одной функции должны быть параметры по умолчанию и соответственно в
программе должны быть вызовы такой функции в разной форме.
·
Использовать
все циклы С++.
·
Доступ
к элементам массива по [] и *.
·
Заполнение
массива случайным образом.
·
Программа
должна создаваться из проекта, содержащего несколько файлов исходного кода (*.h, *.срр).
·
Должны
использоваться уловная компиляция (стражи включения).
·
Программа
должна иметь дружественный интерфейс - основные операции должны вызываться
через соответствующие элементы текстового меню.
·
Итерации
в текстовый файл отчета.
·
Передача
имени файла отчета в командной строке.
·
Считывание
исходных данных из файла.
·
Использование
параметров командной cтроки.
Теоретическое обоснование метода
«Сортировка при помощи прямого включения»
и алгоритм решения задачи
Метод
основывается на следующем: считается, что перед рассмотрением записи R[j]
предыдущие записи R[1],R[2],...,R[j-1] уже упорядочены, и R[j]
вставляется в соответствующее место. Сортировка таблицы начинается со второй
записи. Ее ключ сравнивается с ключом первой записи, и, если упорядоченность нарушена,
то записи R[1] и R[2] переставляются. Затем ключ записи R[3] сравнивается с ключами
записей R[2] и R[1]. Как только программа обнаруживает, что (j+1)-й
элемент массива меньше (при сортировке по возрастанию) j-го элемента,
она копирует значение этого элемента в буферную переменную и с начала массива
до j анализирует,
пока значение буферной переменной не будет меньше какого-либо элемента х. Затем
кусок массива, начиная с х и до j, перемещается на одну ячейку в сторону возрастания, и
на образовавшееся место х записывается значение перемещаемого элемента. Дальше
продолжается перемещение по основному массиву до элемента n-1
(т.к. мы сравниваем j-й и (j+1)-й элементы):
41
54 10 66 27 42 80 61 43 37
^
<~~
10
41 54 66 27 42 80 61 43 37
^ <~~
10
27 41 54 66 42 80 61 43 37
^ <~~
10
27 41 42 54 66 80 61 43 37
^ <~~
10
27 41 42 54 61 66 80 43 37
^ <~~
10
27 41 42 43 54 61 66 80 37
^ <~~
10
27 37 41 42 43 54 61 66 80
см. приложение 2.
Пример работы программы
Запускаем
программу InsetSort:
Программа
прелагает нам выбрать один из пунктов меню для выполнения соответствующей
операции. Итак, выбираем 1:
Введем
желаемое количество элементов массива.
Массив
создан. Теперь можно вывести массив на экран, добавить некоторое количество
элементов, найти какой-либо элемент по значению и т.д. Выведем массив на экран.
Также
эта программа предоставляет возможность удалить какой-либо элемент, введя его
порядковый номер. Допустим, мы хотим удалить элемент под номером 7 со значением
89, затем выведем снова массив на экран:
Теперь
добавим 6 элементов к существующему массиву:
В
программе реализована функция чтения из файла. Если задано три параметра
запуска программы, то она принимает argv[2], как название файла, из
которого будет происходить считывание информации. Если же задано меньшее
количество параметров, то InsetSort предложит
ввести названии файла в течении выполнения программы.
Перед выбором пункта 7 (Open File)
необходимо очистить массив (пункт 6), иначе программа сигнализирует об ошибке.
А после выбора элемента меню 7 введем название считываемого файла данных, если
это необходимо.
(Первым элементом файла должно быть число, значение
которого равно количеству элементов в файле.) Проделаем вышеуказанные действия
и выведем результат на экран:
При
выборе пункта 9 у нас будет возможность отсортировать массив элементов, как по
возрастанию, так и по убыванию. Например, отсортируем существующий массив по
возрастанию и выведем результат на экран:
В
итоге мы получили отсортированный массив и массу удовольствия при работе в этой
чудотворной программе. А кроме этого еще и файл отчёта, в который были записаны
все шаги к полной сортировке массива.
Помните, что
файл будет создан только после корректного завершения программы InsetSort.
Исходный код программы с комментариями
----------------------------------------------------------------- MAIN.CPP
#include "func.h"
int menu();
ofstream f;
char fname[20],foname[20];
int
*MasP[100]={0},n=0,argcGlobal;
////////////////////MAIN/////////////////////
int main(int argc,char
*argv[]){
// int M[10];
int
bool=0;//Ïåðåìåííàÿ,
ïðèíèìàþùàÿ
äâà
çíà÷åíèÿ.(Äëÿ
âûõîäà)
argcGlobal=argc;
if (argc>1)//Åñëè
çàäàí
ïàðàìåòð, òî
ïðèíÿòü åãî
strcpy(fname,argv[1]);//êàê
íàçâàíèå
äëÿ ôàéëà
îò÷åòà.
else
strcpy(fname,"Log.txt");
if (argc>2)
strcpy(foname,argv[2]);//Âòîðîé
àðãóìåíò -
äëÿ ÷òåíèÿ.
f.open(fname);//Ñîçäàíèå
è
ïîäãîòîâêà
ôàéëà ê
çàïèñè.
do{//Âûïîëíÿòü
ïîêà bool=0.
bool=menu();//Áàçîâàÿ
ôóíêöèÿ
ïðîãðàììû.
}while (bool==0);
f.close();//Çàêðûòèå
ôàéëà è
çàïèñü íà ÆÄ.
cout<<"\n\n\n\n\n\n\n\n\n\n";
cout<<"InsetSort. v 0.3 (C) 2003-2004
Created by Chaplygin Vasilij.";
cin.get();
cin.get();
return 0;
}
////////////////////MENU////////////////////
int menu(){
cout<<endl<<"
Main Menu:"<<endl;
cout<<" 1. Make
New List." <<endl;
cout<<" 2. Add
Element." <<endl;
cout<<" 3. Print
List." <<endl;
cout<<" 4. Delete
Element."<<endl;
cout<<" 5. Save
List." <<endl;
cout<<" 6. Erase
List." <<endl;
cout<<" 7. Open
File." <<endl;
cout<<" 8. Find
Element." <<endl;
cout<<" 9. Sort
List." <<endl;
cout<<" 0.
Exit." <<endl;
cout<<endl<<"Your
choice : ";
int i;
do
{cin>>i;
if (i<0 || i>9)
cout<<endl<<"Error! Try again : ";
}
while (i<0 || i>9);
switch (i)
{case 1 : MakeNewList();
break; //Make New List
case 2 : AddElements();
break; //Add Element
case 3 : PrintList(); break;
//Print List
case 4 : DeleteElement();
break; //Delete Element
case 5 : SaveList();
break; //Save List
case 6 : n=0;
break; //Erase List
case 7 : OpenList();
break; //Open File
case 8 : FindElement();
break; //Find Element
case 9 : SubMenu();
break; //Sort List
case 0 : return -1; //Exit
}
return 0;
}//menu
-----------------------------------------------------------------
func.cpp
#include "func.h"
extern int *MasP[100],n,argcGlobal;
extern ofstream f;
const int N=100;
//////////////////MakeNewList//////////////////
void MakeNewList(){
if (n!=0)
{cout<<endl<<"Error! You have existing list.";
cout<<endl<<"Erase
your prvious list ang try again."<<endl;}
else
{cout<<endl<<"Input quantity of elements: ";
do{
cin>>n;
if ((n<1)||n>N){
cout<<endl<<"The
quantity is incorrect!"<<endl;
cout<<"Max
quantity of elemets: "<<N<<endl;
cout<<"Try
again: ";}
}while ((n<1)||(n>N));
srand(time(NULL));
for (int i=0; i<n; i++){
MasP[i]=new int;
*MasP[i]=rand()%100;}
}
}
//////////////////AddElements///////////////////
void AddElements(){
cout<<endl<<"Input
quantity of elements: ";
int p;
do{
cin>>p;
if
((p<1)||((n+p)>N)){
cout<<endl<<"The
quantity is incorrect!"<<endl;
cout<<"You
have "<<N-n<<" free cells."<<endl;
cout<<"Try
again: ";}
}while
((p<1)||((n+p)>N));
srand(time(NULL));
for (int i=n; i<(n+p);
i++){
MasP[i]=new int;
*MasP[i]=rand()%100;}
n=n+p;
}
////////////////////PrintList///////////////////
void PrintList(){
if (n==0)
cout<<endl<<"List is empty."<<endl;
else{
cout<<endl;
for(int i=0; i<n; i++){
if (i%10==0)
cout<<endl;
cout<<setw(3)<<*MasP[i];}
cout<<endl;
}
}
////////////////DeleteElement///////////////////
void DeleteElement(){
if (n==0)
cout<<endl<<"List is empty."<<endl;
else{
cout<<endl<<"Input
number of element: ";
int p;
do{
cin>>p;
if ((p<0)||(p>n))
cout<<endl<<"Error! Try again: ";}
while
((p<0)||(p>n));
cout<<endl;
for (int j=(p-1); j<n;
j++)
MasP[j]=MasP[j+1];
MasP[n]=0;
n--;
}
}
////////////////////Save
List/////////////////////
void SaveList(){
if (n==0)
cout<<endl<<"List is empty."<<endl;
else{
for (int i=0; i<n;
i++){
if (i%10==0)
f<<endl;
f<<setw(3)<<*MasP[i];}
f<<endl;
}
}
///////////////////FindElement////////////////////
void FindElement(){
if (n==0)
cout<<endl<<"List is empty."<<endl;
else{
cout<<endl<<"Input
the value, which must be finded: ";
int a,s=0; cin>>a;
for (int i=0; i<n;
i++){
if (*MasP[i]==a) {
cout<<endl<<(i+1)<<"-th
element"<<" - "<<*MasP[i];
s=i;}}
if (s==0)
cout<<endl<<"The existing list hasn't element with this
value";
cout<<endl;
}
}
//////////////////SubWork(Sort)///////////////////
void SubMenu(){
if (n==0)
cout<<endl<<"List is empty."<<endl;
else{
cout<<endl<<"
Sub Menu:"<<endl;
cout<<" 1. Sort
list by increase."<<endl;
cout<<" 2. Sort
list by decrease."<<endl<<endl;
int i;
cout<<"Your choice:
";
do {
cin>>i;
if (i<1 || i>2)
cout<<endl<<"Error! Try again : "<<endl;
}while (i<1 || i>2);
switch (i)
{case 1 :
SortByIncrease(); break; //Increase
case 2 :
SortByDecrease(); break; //Decrease
}
}
}
/////////////////SortByIncrease//////////////////
void SortByIncrease(){
int buf;
for (int i=0; i<(n-1);
i++){
if
(*MasP[i]>*MasP[i+1]){
SaveList();
buf=*MasP[i+1];
for (int j=0;
j<(i+1); j++){
if
(buf<*MasP[j]){
for (int q=i+1;
q>j; q--)
*MasP[q]=*MasP[q-1];
*MasP[j]=buf;
break;
}//Incert place
}//for Incert place
}//Find unsorted element
}//for Find unsorted element
SaveList();
}
/////////////////SortByDecrease//////////////////
void SortByDecrease(){
int buf;
for (int i=0; i<(n-1);
i++){
if
(*MasP[i]<*MasP[i+1]){
SaveList();
buf=*MasP[i+1];
for (int j=0;
j<(i+1); j++){
if
(buf>*MasP[j]){
for (int q=i+1;
q>j; q--)
*MasP[q]=*MasP[q-1];
*MasP[j]=buf;
break;
}//Incert place
}//for Incert place
}//Find unsorted element
}//for Find unsorted element
SaveList();
}
///////////////////Open
File/////////////////////
void OpenList(char s[20]){
if (n!=0)
{cout<<endl<<"Error! You have existing list.";
cout<<endl<<"Erase
your prvious list ang try again."<<endl;}
else {
if (argcGlobal<3){
cout<<endl<<"Input
file name: ";
char *FileName=new
char[20];
cin>>FileName;
s=FileName;}
ifstream
fo(s,ios::nocreate);
if (! fo)
cout<<"File not found."<<endl;
else{
int b;
fo>>b;
for (int i=0; i<b;
i++){
if (n==N) break;
MasP[n]= new int;
fo>>*MasP[n];
n++;
}
}//if (! fo)...
}
}
-------------------------------------------------------------------
func.h
//Ïîäêëþ÷àåì
ñòðàæè
âêëþ÷åíèé.
#ifndef __func_h
#define __func_h
#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>
#include <iomanip.h>
#include <string.h>
#include <time.h>
extern char foname[20];
//Ïðîòîòèïû
ôóíêöèé.
void MakeNewList();
void AddElements();
void PrintList();
void DeleteElement();
void SaveList();
void EraseList();
void FindElement();
void SubMenu();
void SortByIncrease();
void SortByDecrease();
void OpenList(char
s[20]=foname);
#endif
Список литературы
1.
Лафоре Р. Объектно-ориентированное
программирование в С++, 4-е изд. - СПб.: Питер, 2003. – 928 с.: ил.
2.
Дейтел Х.М., Дейтел П.Дж. Как
программировать на С++.. – М.: Бином, 1999. - 1024 с.
3.
Страуструп Б. Язык
программирования С++, 3-е изд. - СПб.; М.: Невский Диалект - Бином, 1999.
- 991 с.
4.
Керниган Б., Ритчи Д. Язык программирования Си.\Пер. с англ., 3-е изд.,
испр. - СПб.: "Невский Диалект", 2001. - 352 с.: ил.
Примечание 1.
Примечание 2.
| ! |
Как писать рефераты Практические рекомендации по написанию студенческих рефератов. |
| ! | План реферата Краткий список разделов, отражающий структура и порядок работы над будующим рефератом. |
| ! | Введение реферата Вводная часть работы, в которой отражается цель и обозначается список задач. |
| ! | Заключение реферата В заключении подводятся итоги, описывается была ли достигнута поставленная цель, каковы результаты. |
| ! | Оформление рефератов Методические рекомендации по грамотному оформлению работы по ГОСТ. |
| → | Виды рефератов Какими бывают рефераты по своему назначению и структуре. |