Сортировка матриц
Цель работы: изучение приёмов сортировки двумерных массивов данных, выработка умений алгоритмизации и программирования задач сортировки массивов, отладки и тестирования программ с массивами.
/* Программа 12. Программа демонстрирует типовые процедуры сортировки двумерных массивов по заданным условиям: поиск строки матрицы, сортировка столбцов по возрастанию значений чисел заданной строки, перемещение строк или столбцов. Задачи решаются без использования дополнительных массивов. */
// Прототипы функций программы:
void in_matr(int x[ ][10], int m, int n); // ввод матрицы размером m *n
// с клавиатуры
void in_matr_rand(int x[ ][10], int m, int n); // заполнение матрицы размером
// m*n случайными числами из интервала [-10, 10].
void out_matr(int x[ ][10], int m, int n); // вывод матрицы размером m*n
// на экран.
void processing(int x[ ][10], int *y, int m, int n); // функция заменяет
// в матрице размером m*n строки, не содержащие "+"-ых элементов,
// элементами массива y[ ].
void sort_columns(int x[ ][10], int m, int n); // располагает столбцы матрицы
// размером m*n в порядке возрастания элементов первой строки.
void rows_move(int x[ ][10], int m, int n); // перемещение строк с первым 0-м
// элементом на место последних строк матрицы.
#include <stdio.h>
#include <conio.h>
void main( )
{ int m, n, x[10][10], y[10] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
char ch;
printf(" *** Matrix Sort *** ");
printf("\n\n Введите размеры матрицы m<=10, n<=10: ");
scanf("%d %d", &m, &n);
printf("\n Ввод матрицы с клавиатуры - 'c' или заполнение \
случайными числами - 'r'? - ");
scanf("%c%c", &ch, &ch);
if((ch=='c') || (ch=='C')) in_matr( x, m, n);
else { randomize(); in_matr_rand( x, m, n);}
printf("\n Исходная матрица: %d*%d \n", m, n);
out_matr( x, m, n );
processing(x, y, m, n);
printf("\n Замена строк с отрицательными элементами числами \
заданного массива: \n");
out_matr( x, m, n );
sort_columns(x, m, n);
printf("\n Сортировка столбцов матрицы в порядке возрастания \
элементов первой строки: \n");
out_matr( x, m, n );
printf("\n перемещение строк с первым 0-м элементом на место \
последних строк матрицы: \n");
rows_move( x, m, n );
out_matr( x, m, n );
getch();
return 0;
} /* Коды функций in_matr( ), in_matr_rand( ) и out_matr( ) приведены в
программе 10. Модификацию функций для матрицы размером m х n
выполните самостоятельно. */
Функция processing( ) заменяет в матрице размером m х n строки
с отрицательными элементами числами массива y[ ].
ТЕСТ: m = 4, n = 4, y[ ] = { 10, 9, 8, 7 },
-1 -1 -1 -1 10 9 8 7
x = -2 2 -2 -2 => -2 2 -2 -2
-3 -3 -3 -3 10 9 8 7
4 -4 4 4 4 -4 4 4
void processing( int x[ ][10], int *y, int m, int n )
{ int i, j, k;
for ( i = 0; i < m; i++ ) // проверка всех строк
{ j = -1;
do // поиск в строке 'i' элемента x[i][j] >= 0
{ j++;
if( x[i][j] >= 0 && j != n) break; // то элемент найден
if( j == n ) // строка 'i' с "-"-ми элементами
for ( k=0; k<n; k++) x[i][k] = y[k];
}
while ( j != n );
}
/* Функция rows_move( ) перемещает строки с первым 0-м элементом на место последних строк матрицы размером m*n.
ТЕСТ: m = 4, n = 4,
0 1 1 1 4 4 4 4
x = 2 2 2 2 => 2 2 2 2
0 3 3 3 0 3 3 3
4 4 4 4 0 1 1 1
*/
void rows_move(int x[ ][10], int m, int n)
{ int ii = 0, // номер строки с первым нулевым элементом
kk = n-1, // номер строки с первым ненулевым элементом
// от последней строки
i, j, k, w;
while( ii < kk )
{ for ( i = ii; i < m-1; i++) // поиск строки с первым нулевым элементом
if( x[i][0] == 0 ) break;
ii = i;
for ( k = kk; k > ii; k- -) // поиск строки с первым ненулевым элементом
if( x[k][0] != 0 ) break; // от последней строки
kk = k;
if( ii < kk ) // меняем строки ii и kk местами
for ( j = 0; i < n; j++) // столбцы j и k
{ w = x[ii][j];
x[ii][j] = x[kk][j];
x[kk][j] = w;
}
ii++, kk--;
}
}
/* Функция sort_columns( ) располагает столбцы матрицы размером m*n
в порядке возрастания элементов первой строки.
ТЕСТ: m = 4, n = 4,
3 1 2 0 0 1 2 3
x = 3 1 2 0 => 0 1 2 3
3 1 2 1 1 1 2 3
3 1 2 2 2 1 2 3
*/
void sort_columns(int x[ ][10], int m, int n)
{ int i, j, k, z;
for ( j = 0; j < n-1; j++)
for ( k = j+1; k < n; k++)
if ( x[0][j] > x[0][k] ) // меняем местами
for ( i = 0; i < m; i++) // столбцы j и k
{ z = x[i][j];
x[i][j] = x[i][k];
x[i][k] = z;
}
}
Вопросы и упражнения
1. Сколько циклов нужно для просмотра всех элементов n-мерного массива?
2. Запишите циклы для инвертирования матрицы m х n (замена строк столбцами).
3. Поясните следующий фрагмент программы обработки матрицы а размером n x n:
for( j = 0; j < n; j++ )
for( i = n-1; i > j; i-- ) а[i][j] = а[ i - j ] [ n-1 - j ]
4. Составьте функцию для удаления: а) k- го столбца матрицы; б) k-ой строки матрицы.
5. Поясните алгоритм сортировки в функции sort_columns(). Модифицируйте функцию для сортировки по методу «пузырька».
6. Как выполнить перемещение строк в функции rows_move( ) сохранив последовательность строк с ненулевым первым элементом относительно друг друга?