Поиск, перестановка и сортировка в динамических массивах

Задачи по обработке динамических массивов (задачи на поиск, перестановки и сортировки в динамических массивах) реализуются аналогично соответствующим задачам по обработке данных статических массивов.

При этом в задачах на обработку двумерных массивов необходимо определить способ просмотра массива (по строкам, по столбцам, вдоль диагоналей и т.д.). При выборе обхода матрицы следует помнить, что параметр внешнего цикла меняется медленнее, чем параметр вложенных в него циклов. Под сортировкой двумерного массива понимают упорядочивание элементов, объединенных в строки или столбцы. В этом случае строку или столбец рассматривают как одномерный массив.

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

#include <iostream.h>

#include <stdlib.h>

#include <time.h>

void Initialization(int **mas, int *k, int *l,int **vmas);

void Print(int *mas, int k, int l);

void Work(int *mas, int k, int l,int *vmas);

void FindMax(int *mas, int k, int l,int *vmas);

void Obmen(int *mas,int k,int l,int i,int q);

void Distraction(int *mas,int *vmas);

void main(){

int *mass, n, m, *vmass;

Initialization(&mass, &n, &m, &vmass);

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

Print(mass, n, m);

Work(mass, n, m, vmass);

cout << "Преобразованная матрица" << "\n";

Print(mass, n, m);

Distraction(mass, vmass);

}

void Initialization(int **mas, int *k, int *l,int **vmas){

int i, j, a, b;

cout << "Введите размерность матрицы:" << "\n";

cout << "n = ";

cin >> *k;

cout << "m = ";

cin >> *l;

cout << "Введите границы генерации элементов

матрицы:"<<"\n";

cout << "a = ";

cin >> a;

cout << "b = ";

cin >> b;

srand(time(NULL)*1000);

*mas = new int[(*k)*(*l)];

*vmas = new int[(*l)];

for (i = 0; i < *k ; i++)

for (j = 0; j < *l ; j++)

(*mas)[i*(*l)+j] = rand()%(b-a)+a;

}

void Print(int *mas, int k, int l){

int i, j;

for (i = 0; i < k ; i++){

for (j = 0; j < l ; j++)

cout << mas[i*l+j] << " ";

cout << "\n";

}

}

void Work(int *mas, int k, int l,int *vmas){

int i, j, q, r;

FindMax(mas, k, l, vmas);

for( i=0; i < l; i++) { // i - номер текущего шага

q=i;

for( j=i+1; j < l; j++)

//цикл выбора наименьшего максимального элемента

if (vmas[j]<vmas[q])

q=j;//q - индекс наименьшего максимального элемента

r = vmas[q]; // меняем местами наименьший с vmas[i]

vmas[q] = vmas[i];

vmas[i] = r;

Obmen(mas, k, l, i, q);

//меняем местами столбцы с номерами i и q матрицы mas

}

}

void FindMax(int *mas, int k, int l,int *vmas){

int i, j;

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

vmas[j] = mas[j];

for (i = 1; i < k; i++)

if (vmas[j] < mas[i*l+j])

vmas[j] = mas[i*l+j];

}

}

void Obmen(int *mas,int k,int l,int i,int q){

int j, r;

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

r = mas[j*l+i];

mas[j*l+i] = mas[j*l+q];

mas[j*l+q] = r;

}

}

void Distraction(int *mas,int *vmas){

delete(vmas);

delete(mas);

}

Задания

1.Наберите код программы из Примера 1. Выполните компиляцию и запуск программы.

2.Двумерная целочисленная квадратная матрица размера n задает преобразование базиса Е в базис Е´, а одномерный массив из n вещественных чисел – координаты вектора в базисе Е. Найдите координаты этого вектора в базисе Е´.

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

Домашние задания

1.Наберите код программы из Примера 2. Выполните компиляцию и запуск программы.

2.Латинским квадратом размера n называется таблица n × n, заполненная n различными символами таким образом, чтобы в каждой строке и в каждом столбце встречались все n символов (каждый по одному разу). Латинские квадраты существуют для любого n. Заполните латинский квадрат размера n натуральными числами от 1 до n.

3.Для данной вещественной квадратной матрицы составьте соответствующую матрицу миноров каждого ее элемента.