Сортировка матриц

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

/* Программа 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() сохранив последовательность строк с ненулевым первым элементом относительно друг друга?