Сортировка статических структур данных

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

Введение

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

Цель курсовой работы - изучение методов сортировки структур данных; совершенствование навыков процедурного программирования на языке C/С++ при решении задач обработки статических и динамических массивов. Приобретение знаний по оформлению документации на программные средства.

1. Постановка задачи

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

2. Спецификация

Обозначение	Наименование	Примечания
44.В4441.15-01	Документация Программа “Сортировка статических структур данных” Спецификация
44.В4441.15-12	Документация Программа “Сортировка статических структур данных” Текст программы
44.В4441.15-13	Документация Программа “Сортировка статических структур данных” Описание программы
44.В4441.15-31	Документация Программа “Сортировка статических структур данных” Описание применения

Аннотация

В документе приводится текст программы “Сортировка статических структур данных”, а также результат отладки и тестирования.

3. Текст программы

3.1 Текст программы

//Методы сортировки

//Массивы динамические двумерные

//Сортировка элементов всех строк двумерного массива целых чисел

//по убыванию

#include "iostream"

#include "locale.h"

#include <cmath>

using namespace std;

typedef bool boolVal ; //определение типа элементов массива

typedef boolVal *bStr ; //определение типа "указатель на telem"

typedef bStr *bMatr;

//определение типа "указатель на указатель на telem"

typedef int telem ; //определение типа элементов массива

typedef telem *tStr ; //определение типа "указатель на telem"

typedef tStr *tMatr;

//определение типа "указатель на указатель на telem"

int Color();

void inputValMatr(bMatr a, int str, int sto);

void inputMatr(tMatr a, int str, int sto) ;

void handInput(tMatr a, int str, int sto) ;

void outputMatr(tMatr a, int str, int sto) ;

void sortVstavka(tMatr a, bMatr b, int str, int sto) ;

void zanulenieElementov(tMatr a, bMatr b, int str, int sto);

void outputBoolMatr(bMatr a, int str, int sto);

int main()

{

while(true)

{

int i, j ;

int n = 0; //число строк матрицы

int m = 0; //число столбцов матрицы

bool y;

tMatr a; //объявляется переменная-указатель на указатель на telem

bMatr b;

setlocale(LC_ALL,"Russian") ;

cout << "\nСорт матрицы целых чисел!: \nВведите 2 числа > 3 (Пример: 10 11):\n" ;

while(n < 3 && m < 3)

{

cin.sync();

try

{

char n1[3], m1[3];

cin >> n1 >> m1;

n = (int)atof(n1);

m = (int)atof(m1);

}

catch(...)

{

}

cout << "Неверный ввод, нужно число строк< 20"<< endl;

}

a = new tStr [n] ;

//выделение динамической памяти под массива

//указателей на строки массива

for(i = 0; i < n; i++) //цикл выделения памяти под каждую строку

*(a + i) = new telem [m] ;//каждому элементу массива указателей

//на строки присваивается адрес начала

//области памяти, выделяемой под строку

b = new bStr [n] ;

for(i = 0; i < n; i++)

*(b + i) = new boolVal [m] ;

cout << "Введите 0 - матрица заполнится сама, введите 1 и вводите числа через enter.\n";

cin >> y;

if(!y)

{

inputMatr(a, n, m) ;

}

else

{

handInput(a, n, m);

}

inputValMatr(b, n, m);

if(n <= 20)

{

cout << "Исходная матрица:\n" ;

outputMatr(a, n, m) ;

sortVstavka(a, b, n, m);

cout << "Матрица с отсортированными строками:\n" << endl ;

zanulenieElementov(a, b, n, m);

outputMatr(a, n, m) ;

}

else

{

cout << "\n\nВаша матрица НЕ ВЛЕЗЕТ в Вашу консоль по ширине" << endl;

return;

}

cout << endl ;

//Освобождение динамической памяти

for(i = 0; i < n; i++)

delete a[i] ;

delete a ;

char isExit =0;

cout << "Введите 1 для выхода\n";

try

{

cin >> isExit;

if(isExit==1)

break;

}

catch(...)

{

}

}

}

void inputMatr(tMatr a, int str, int sto)

{

for(int i = 0 ; i < str ; i++)

for(int j = 0 ; j < sto ; j++)

*(*(a + i) + j) = (str*sto) - (i + j);

}

void inputValMatr(bMatr a, int str, int sto)

{

for(int i = 0 ; i < str ; i++)

for(int j = 0 ; j < sto ; j++)

*(*(a + i) + j) = false;

}

void handInput(tMatr a, int str, int sto)

{

int input = 0;

int *inputPointer = &input;

int *elemPointer;

for(int i = 0 ; i < str ; i++)

{

for(int j = 0 ; j < sto ; j++)

{

elemPointer = (*(a + i) + j);

*elemPointer = 0;

while(*elemPointer == 0)

{

try

{

cin >> *inputPointer;

*elemPointer = (int)input;

}

catch(...)

{

cout << "Введите ещё раз для этой ячейки" << endl;

}

}

}

}

}

//сортировка элементов массива по возрастанию методом вставки

void sortVstavka(tMatr a, bMatr b, int str, int sto)

{

telem *curElem = 0;

telem *nextElem = 0;

if((str > 3) && (sto >3) && (str <= 20))

{

#pragma region |sto > str|

//Соответственно, если количество столбцов больше строк :

if(sto > str)

{

telem curTemp;

int begSto = 0;

int begStr = 0;

int curStr=0;

double predelStr = 0;

double predelSto = 0;

//Этот цикл содержит 4 цикла выравнивания и повторяется столь-

//ко раз, чтобы все элементы были выровнены по возрастанию

for(int l=0;l<=((str/2)-sto+str+1);l++)

{

begSto = 1;

(sto/2 == 0) ? predelSto = sto/2 : predelSto = (sto/2)-1;

(str/2==0)? begStr = (str/2)+1 : begStr = (str/2);

predelStr = begStr+1;

//1-й цикл выравнивания

for(int curSto = begSto;

curSto <= predelSto; curSto++)

{

curStr = begStr;

if(predelStr >0)

predelStr--;

while(curStr >= predelStr)

{

boolVal *curBool = (*(b + curStr) + curSto);

boolVal *nextBool = (*(b + curStr - 1) + curSto);

curElem = (*(a + curStr) + curSto);

curTemp = *curElem;

if(curStr>0)

nextElem =

(*(a + curStr - 1) +curSto);

if( (*curElem > *nextElem) && curStr > 0 )

{

*curElem = *nextElem;

*nextElem = curTemp;

}

*curBool = true;

if(((curStr-1) >= 0) &&

((curStr+1)<=str-1))

{

*nextBool = true;

}

curStr--;

if((curSto > (sto/2 + 1)))

break;

}

}

begSto = (sto-2);

predelStr = begStr+1;

//2-й цикл выравнивания

for(int curSto = begSto; curSto > predelSto; curSto--)

{

curStr = begStr;

if(predelStr >0)

predelStr--;

while(curStr >= predelStr)

{

boolVal *curBool =

(*(b + curStr) + curSto);

boolVal *nextBool =

(*(b + curStr - 1) + curSto);

curElem = (*(a + curStr) + curSto);

curTemp = *curElem;

if(curStr>0)

nextElem =

(*(a + curStr - 1) + curSto);

if( (*curElem > *nextElem) && curStr > 0 )

{

*curElem = *nextElem;

*nextElem = curTemp;

}

*curBool = true;

if( ((curStr-1) >= 0) &&

((curStr+1)<=str-1) )

{

*nextBool = true;

}

curStr--;

if((curSto < (sto/2 - 1)))

break;

}

}

(str/2==0)? begStr = (str/2) : begStr = (str/2)+0.5;

predelStr = begStr;

//3-й цикл выравнивания

for(int curSto = 1; curSto <= predelSto; curSto++)

{

curStr = begStr+1;

if(predelStr < str-1)

predelStr++;

while(curStr <= predelStr)

{

boolVal *curBool =

(*(b + curStr) + curSto);

boolVal *nextBool =

(*(b + curStr + 1)

+ curSto);

curElem =

(*(a + curStr) + curSto);

curTemp =

*curElem;

if(curStr<(str-1))

nextElem =

(*(a + curStr + 1) + curSto);

if( (*curElem > *nextElem)

&& curStr < str-1 )

{

*curElem = *nextElem;

*nextElem = curTemp;

}

*curBool = true;

curStr++;

if((curSto > (sto/2 + 1)))

break;

}

}

predelStr = begStr;

//4-й цикл выравнивания

for(int curSto = sto-2;

curSto > predelSto; curSto--)

{

curStr = begStr+1;

if(predelStr < str-1)

predelStr++;

while(curStr <= predelStr)

{

boolVal *curBool =

(*(b + curStr) + curSto);

boolVal *nextBool =

(*(b + curStr + 1) + curSto);

curElem = (*(a + curStr) + curSto);

curTemp = *curElem;

if(curStr<(str-1))

nextElem =

(*(a + curStr + 1) +

curSto);

if( (*curElem > *nextElem)&&

curStr < (str-1) )

{

*curElem = *nextElem;

*nextElem = curTemp;

}

*curBool = true;

curStr++;

if((curSto < ((sto/2 - 1))))

break;

}

}

}

}

#pragma endregion

#pragma region |sto < str|

if(sto < str)

{

telem curTemp;

int begSto = 0;

int begStr;

if(str % 2 == 0)

begStr = (str / 2) - 1;

else

begStr = (str / 2);

for(int l=0;l<=((str/2)-sto+str+1);l++)

{

int curStr=begStr;

double predelSto;

double predelStr = 0;

predelSto = sto/2-1;

predelStr = begStr+1;

begSto = 0;

//1

for(int curSto = begSto;

curSto <= predelSto; curSto++)

{

curStr = begStr;

if(predelStr >1)

predelStr--;;

while(curStr >= predelStr)

{

boolVal *curBool =

(*(b + curStr) + curSto);

curElem = (*(a + curStr) + curSto);

curTemp = *curElem;

if(curStr<(str-1))

nextElem =

(*(a + curStr - 1) + curSto);

if( (*curElem > *nextElem) &&

curStr <(str-1) )

{

*curElem = *nextElem;

*nextElem = curTemp;

}

*curBool = true;

curStr--;

}

}

//2-й цикл выравнивания

predelStr = begStr+1;for(int curSto = sto-1;

curSto > predelSto; curSto--)

{

curStr = begStr;

if(predelStr > 1)

predelStr--;

while(curStr >= predelStr)

{

boolVal *curBool =

(*(b + curStr) + curSto);

curElem = (*(a + curStr) + curSto);

curTemp = *curElem;

if(curStr<(str-1))

nextElem =

(*(a + curStr - 1) + curSto);

if( (*curElem > *nextElem) &&

curStr <(str-1) )

{

*curElem = *nextElem;

*nextElem = curTemp;

}

*curBool = true;

curStr--;

}

}

//3-й цикл выравнивания

if(str % 2 == 0)

begStr = (str / 2);

else

begStr = (str / 2);

begSto = 0;

predelStr = begStr-1;

for(int curSto = begSto;

curSto <= predelSto; curSto++)

{

curStr = begStr;

if(predelStr < (str-1))

predelStr++;;

while(curStr <= predelStr)

{

boolVal *curBool =

(*(b + curStr) + curSto);

curElem = (*(a + curStr) + curSto);

curTemp = *curElem;

if(curStr<(str-1))

nextElem =

(*(a + curStr + 1) + curSto);

if( (*curElem > *nextElem) &&

curStr < (str-1) )

{

*curElem = *nextElem;

*nextElem = curTemp;

}

*curBool = true;

curStr++;

}

}

//4-й цикл выравнивания

predelStr = begStr-1;

for(int curSto = sto-1;

curSto > predelSto; curSto--)

{

curStr = begStr;

if(predelStr < (str-1))

predelStr++;

while(curStr <= predelStr)

{

boolVal *curBool =

(*(b + curStr) + curSto);

curElem = (*(a + curStr) + curSto);

curTemp = *curElem;

if(curStr<(str-1))

nextElem =

(*(a + curStr + 1) + curSto);

if( (*curElem > *nextElem) &&

curStr < (str-1) )

{

*curElem = *nextElem;

*nextElem = curTemp;

}

*curBool = true;

curStr++;

}

}

}

}

#pragma endregion

#pragma region |sto == str|

if(sto == str)

{

telem curTemp;

for(int l=0;l<=((str/2)-sto+str+1);l++)

{

int begSto = 0;

int begStr = 0;

int curStr=begStr;

double predelSto = 0;

double predelStr = 0;

begSto = 0;

if(str % 2 == 0)

begStr = (str / 2) - 1;

else

begStr = (str / 2);

(sto/2 == 0) ? predelSto = sto/2 :

predelSto = (sto/2)+0.5;

predelStr = begStr+1;

for(int curSto = begSto;

curSto <= predelSto; curSto++)

{

curStr = begStr;

if(predelStr >0)

predelStr--;

while(curStr >= predelStr)

{

boolVal *curBool =

(*(b + curStr) + curSto);

boolVal *nextBool =

(*(b + curStr - 1) + curSto);

curElem = (*(a + curStr) + curSto);

curTemp = *curElem;

if(curStr>0)

nextElem =

(*(a + curStr - 1) + curSto);

if( (*curElem > *nextElem) &&

curStr > 0 )

{

*curElem = *nextElem;

*nextElem = curTemp;

}

*curBool = true;

curStr--;

}

}

//2-й цикл выравнивания

predelStr = begStr+1;

for(int curSto = sto-1;

curSto > predelSto; curSto--)

{

curStr = begStr;

if(predelStr > 0)

predelStr--;

while(curStr >= predelStr)

{

boolVal *curBool =

(*(b + curStr) + curSto);

boolVal *nextBool =

(*(b + curStr - 1) + curSto);

curElem = (*(a + curStr) + curSto);

curTemp = *curElem;

if(curStr>0)

nextElem = (*(a + curStr - 1) +

curSto);

if( (*curElem > *nextElem) &&

curStr > 0 )

{

*curElem = *nextElem;

*nextElem = curTemp;

}

*curBool = true;

curStr--;

}

}

if(str % 2 == 0)

{

begStr = (str / 2);

begSto = sto-1;

}

else

{

begStr = (str / 2)+1;

begSto = sto-2;

}

predelStr = begStr-1;

//3-й цикл выравнивания

for(int curSto = begSto; curSto >= predelSto; curSto--)

{

curStr = begStr;

if(predelStr < (str-1))

predelStr++;

while(curStr <= predelStr)

{

boolVal *curBool =

(*(b + curStr) + curSto);

boolVal *nextBool =

(*(b + curStr + 1) + curSto);

curElem = (*(a + curStr) + curSto);

curTemp = *curElem;

if(curStr<(str-1))

nextElem = (*(a + curStr + 1) + curSto);

if( (*curElem > *nextElem) &&

curStr < (str-1) )

{

*curElem = *nextElem;

*nextElem = curTemp;

}

*curBool = true;

curStr++;

}

}

if(str % 2 == 0)

{

begStr = (str / 2);

begSto = 0;

}

else

{

begStr = (str / 2)+1;

begSto = 1;

}

predelStr = begStr-1;

//4-й цикл выравнивания

for(int curSto = begSto;

curSto < predelSto; curSto++)

{

curStr = begStr;

if(predelStr < (str-1))

predelStr++;

while(curStr <= predelStr)

{

boolVal *curBool =

(*(b + curStr) + curSto);

boolVal *nextBool =

(*(b + curStr + 1) + curSto);

curElem = (*(a + curStr) + curSto);

curTemp = *curElem;

if(curStr<(str-1))

nextElem =

(*(a + curStr + 1) + curSto);

if( (*curElem > *nextElem) &&

curStr < (str-1) )

{

*curElem = *nextElem;

*nextElem = curTemp;

}

*curBool = true;

curStr++;

}

}

}

}

#pragma endregion

}

if((str == 3) && (sto == 3))

{

int var = 0;

int *one = (*(a + 1) + 1);

int *two = (*(a + 0) + 1);

if(one > two)

{

var = *one;

*one = *two;

*two = var;

}

}

}

void zanulenieElementov(tMatr a, bMatr b, int str, int sto)

{

for(int stro = 0; stro <= (str -1); stro++)

{

for(int stol = 0; stol <= (sto -1); stol++)

{

if(*(*(b + stro) + stol) == false)

{

*(*(a + stro) + stol) = 0;

}

}

}

}

void outputMatr(tMatr a, int str, int sto)

{ int i, j ;

for(i = 0; i < str; i++)

{for(j = 0; j < sto; j++)

{cout.width(3) ;//ширина поля выводимого параметра

cout << *(*(a + i) + j) << ' ' ;

}

cout << "\n\n";

}

}

void outputBoolMatr(bMatr a, int str, int sto)

{ int i, j ;

for(i = 0; i < str; i++)

{for(j = 0; j < sto; j++)

{cout.width(3) ;//ширина поля выводимого параметра

cout << *(*(a + i) + j) << ' ' ;

}

cout << "\n\n";

}

}

3.2 Результаты тестирования

Рис 1 - сортировка квадратной матрицы

Рис 2 - сортировка прямоугольной матрицы #1

Рис 3 - сортировка прямоугольной матрицы #1

сортировка данные матрица

Рисунок 4 - вывод уведомления о неправильности ввода данных

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

Аннотация

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

Общие сведения

Программа написана на языке C++, реализована на ПЭВМ IMB PC и состоит из меню программы и набора функций. В совей совокупности это даёт возможность создания, просмотра, сортировки строк в заданных областях матрицы по возрастанию методов вставки. Для функционирования данной программы, а также, в частности, раздела кода, реализующего директивы препроцессора #region и #endregion необходимо наличие ПЭВМ, совместимой с IBM PC с предустановленным пакетом программного обеспечения Microsoft Visual Studio C++ 2010. Технические средства должны обеспечивать вывод результатов сортировки на экран.

Функциональное назначение

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

Описание логической структуры

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

Алгоритм программы

void sortVstavka()

void outputMatr();

int main()

void zaulenie()

void inputMatr()

void inputValMatr()

Используемые технические средства

Для нормального функционирования программы необходимо наличие ПЭВМ или сравнимого по техническим характеристикам ПК с IBM PC, для возможности компилирования программы из файла .cpp потребуется установить пакет программ Microsoft Visual Studio C++ 2010 или более позднюю её версию.

Вызов и загрузка

Вызов и загрузка осуществляется в следующей последовательности: С использованием компилятора C++ открыть файл laba6.cpp с текстом программы, после чего откомпилировать и запустить программу на выполнение. Дальнейшие действия определяются выбором параметра меню.

Входные данные

Входные данные для обработки программа запрашивает у пользователя при запуске. Пользователю необходимо ввести 2 числа, представляющих число строк и столбцов матрицы, эти данные преобразуются из введённых пользователем массивов переменных типа char в переменные типа int с помощью явного приведения возвращаемого значения функции atof(); с возможностью генерации исключения.

Выходные данные

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

5. Описание применения

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

Назначение программы

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

Условия применения

Для запуска программы из файла laba6.cpp необходимо наличие: ПЭВМ IBM PC или сравнимого с ним по техническим характеристикам ПК, компилятор C++.

Для запуска откомпилированного приложения laba6.exe необходимо наличие ПК с операционной системой Windows XP/Vista/7/8/10 или эмулятора, позволяющего запускать приложения Windows из-под другой ОС.

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

Описание задачи

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

Входные и выходные данные

Входные данные представляют собой 2 целых числа, разделённые пробелом.

Выходные данные представляют собой видоизменённый двумерный массив.

Условие задачи

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

Объём занимаемой памяти

Файл laba6.cpp занимает на диске 20 480 байт

Файл laba6.exe занимает на диске 73 728 байт

Заключение

В процессе работы над программа были закреплены навыки программирования на C++.

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

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

Список используемой литературы

ГОСТ 19.701-90 Единая система программной документации. Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения.

Х.М. Дейтел, П.Дж. Дейтел. Как программировать на С++.

Размещено на Allbest.ru

...