Будь умным!


У вас вопросы?
У нас ответы:) SamZan.ru

по теме- СОРТИРОВКА МАССИВОВ МЕТОДОМ ВСТАВОКrdquo; Выполнил- студент 326 групп

Работа добавлена на сайт samzan.ru: 2015-07-10


Министерство Образования и Науки Украины

Национальный Аэрокосмический Университет

им. Н. Е. Жуковского “ХАИ”

Кафедра 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.




1. варианты. Под ред
2. Теорема 1 необходимое и достаточное условие интегрируемости
3. Тема 4 Философия Нового времени и Просвещения
4. первых спасибо Всем за интерес к моей деятельности
5. Александр Александрович Фадеев
6. Войны XVIII века 3
7. Обработка металлов давлением
8. а Дата и время поступления Дата и время выписки
9. 60 19121914 Виррих Эрнест Францевич Зазерский Алексей Иванович Бубырь Алексей Федоров.html
10. Эквадор
11. Китайская медицин
12. 15 14 5 Конец index1 index2 Pindex2Pmx Pindex1Pmin Pmx
13. Акти державного управління
14. это закономерности- преступности во всех ее проявлениях детерминации и причинности преступности подверже
15. Молодежная субкультура в социологическом измерении
16. РЕФЕРАТ НА ТЕМУ- ldquo;Етіологія та клінічні прояви холериrdquo; Холера choler особливо небезпечна
17. Хронологические данные в Слове о житии и о преставлении великого князя Дмитрия Ивановича
18. крупных аварий на химически опасных объектах складах базах с выбросом в атмосферу токсических химических
19. Гражданство Российской Федерации
20. Статистика сукупність числових показників що характеризують суспільні явища і процеси чисельність насел