П_ЛР10
.doc
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
-
Федеральное государственное автономное образовательное учреждение высшего образования
«Санкт-Петербургский государственный университет аэрокосмического приборостроения»
КАФЕДРА № 2
Преподаватель
Ст. преподаватель Куртяник Д.В.
Отчёт
по лабораторной работе №10
по дисциплине Информатика
на тему: « Методы сортировки»
Работу выполнил
студент гр. 4616 Павлов А.В.
Санкт-Петербург
Цель лабораторной работы: изучение методов сортировки структур данных; совершенствование навыков процедурного программирования на языке C/С++ при решении задач обработки статических и динамических массивов.
Задание на программирование: используя технологию процедурного программирования реализовать заданный метод сортировки и применить его для указанных фрагментов числовой матрицы в соответствии с индивидуальным заданием.
Порядок выполнения работы:
1) Получить у преподавателя индивидуальное задание: метод сортировки и вид сортируемых фрагментов матрицы. Исходная матрица, содержащая 2*n строк и 2*n столбцов, не должна содержать элементов с одинаковыми и нулевыми значениями. Значения элементов матрицы необходимо формировать программно (с клавиатуры не вводить) с помощью формул.
2) Разработать математическую модель: описать с помощью формул и рисунков структуру массива и процесс его преобразования. У результирующей матрицы должны быть отсортированы заданные фрагменты, а значения элементов не сортируемых фрагментов должны быть обнулены.
3) Построить схему алгоритма решения задачи.
4) Составить программу на языке C/С++.
5) Входные данные на этапах тестирования и демонстрации работы преподавателю должны задаваться либо с использованием специально подобранных арифметических формул, либо вводиться с клавиатуры по запросу. Датчики псевдослучайных чисел использовать запрещается.
Выходные данные должны выводиться на экран с пояснениями.
6) Проверить и продемонстрировать преподавателю работу программы на полном наборе тестов, в том числе с ошибочными входными данными. Входные и выходные массивы должны выводиться в одном и том же формате.
7) Использовать стандартные потоковые объекты ввода/вывода cin и cout.
8) Оформить отчет о лабораторной работе в составе: постановка задачи, математическая модель, схема алгоритма решения, текст программы, контрольные примеры.
1-3)
Вариант 9
Сортировка по возрастанию методом вставки.
Текст программы
#include <iostream>
#include <cstdlib>
using namespace std;
void outmassiv(int **,int); //Вывод массива
void inmassiv(int **,int); //Ввод массива
void sortirovka(int **,int); //Сортировка массива вставками
typedef int telem ; //определение типа элементов массива
typedef telem *tstr ; //определение типа "указатель на telem"
typedef tstr *tmatr; //определение типа "указатель на указатель на telem"
int main(){
int razmernost;
//динамический массив
cout<<"\nСортировка по возрастанию методом вставки"<<endl;
cout<<"\nВведите размерность динамического двумерного массива: ";
cin>>razmernost;
tmatr massiv=new tstr [(razmernost*2)]; //выделение динамической памяти под массив
//указателей на строки массива
for(int i=0;i<razmernost*2;i++) //цикл выделения памяти под каждую строку
*(massiv+i)=new telem [(razmernost*2)]; //каждому элементу массива указателей
//на строки присваивается адрес начала
//области памяти, выделяемой под строку
//ввод массива
inmassiv(massiv,razmernost);
//вывод массива
cout<<"\nИзначальный массив:"<<endl;
outmassiv(massiv,razmernost);
//сортировка вставками
sortirovka(massiv,razmernost);
//вывод массива
cout<<"\nОтсортированный массив методом вставки:"<<endl;
outmassiv(massiv,razmernost);
return 0;
}
//Вывод массива
void outmassiv(int **massiv,int razmernost){
for(int i=0;i<razmernost*2;i++){
for(int j=0;j<razmernost*2;j++){
cout<<" "<<*(*(massiv+j)+i);
}
cout<<endl;
}
}
//Ввод массива
void inmassiv(int **massiv,int razmernost){
for(int i=0;i<razmernost*2;i++){
for(int j=0;j<razmernost*2;j++){
//авто заполнение
*(*(massiv+j)+i)=rand()%10;
//заполнение в ручную
cin>>*(*(massiv+j)+i);
}
}
}
//Сортировка массива вставками
void sortirovka(int **massiv,int razmernost){
int bufer;
for(int i=0;i<razmernost*2;i++){
for(int j=i;j<razmernost*2-1;j++){
for(int sort=j;sort>=i;sort--){
if((*(*(massiv+sort)+i))>(*(*(massiv+sort+1)+i))){
bufer=*(*(massiv+sort+1)+i);
*(*(massiv+sort+1)+i)=*(*(massiv+sort)+i);
*(*(massiv+sort)+i)=bufer;
}
else break;
}
}
}
}
Примеры.