Теоретические сведения. В силу особенности представления двумерных массивов в виде таблиц смысл сортировки такого массива сводится к упорядочиванию элементов
В силу особенности представления двумерных массивов в виде таблиц смысл сортировки такого массива сводится к упорядочиванию элементов, объединенных в столбцы или строки. Например, сортировка по убыванию элементов столбцов означает, что элементы следует расположить по убыванию сверху вниз в каждом столбце отдельно. При этом, рассматривая строку или столбец как одномерный массив, к ним применяют алгоритмы сортировок одномерных массивов.
Пример 1. Сортировка в двумерном целочисленном массиве элементов k-той строки по убыванию.
void sort_dn(int k,int slb, int m[max_x][max_y]) {
int i,j,buf;
for (i=0;i<slb-1;i++)
for (j=slb-1;j>=i;j--)
if (m[k][j]>m[k][j-1]){
//фиксированная строка с номером k
buf= m[k][j];
m[k][j]= m[k][j-1];
m[k][j-1]=buf;
}
}
Для поиска максимальных (минимальных) элементов с целью их дальнейшего упорядочивания удобно выделять отдельно одномерный массив, в котором хранить не значения элементов, а номера столбцов или строк, в которых они располагаются. Например, чтобы найти минимальные элементы в каждом столбце массива n ´ m отдельно, удобно выделить одномерный массив min[m], в котором число элементов равно числу столбцов. Значениями элементов такого массива будут номера строк, в которых располагаются минимальные элементы каждого столбца. Если же минимальных элементов в столбце несколько, то будет найден первый (или последний) минимальный, что не скажется на значении.
Пример 2. Поиск минимальных элементов в каждом столбце двумерного массива.
void minimum(int str,int slb, int m[max_x][max_y],int min[max_y]){
int i,j;
for (j=0;i<slb;i++){//фиксируем номер столбца
min[j]=0;
for (i=1;i<str;i++)
//пробег по столбцу, меняется номер строки
if (m[i][j]<m[min[j]][j]) min[j]=i;
}
}
В данном примере min[max_y] – это массив, значениями которого будут номера строк, в которых располагается первый минимальный элемент столбца. Так для min[j] начальное значение инициализируется как 0, то есть предполагается, что минимальный элемент расположен в строке с номером 0. Обращение m[min[j]][j]понимается так: элемент массива m, расположенный в строке с номером min[j] и столбце с номером j. Но в строке min[j] для столбца j как раз и находится минимальный элемент.
В задачах на перестановку отдельных элементов массива, столбцов или строк используется алгоритм обмена значениями двух переменных через третью переменную (возможны и другие способы обмена значениями двух переменных).
Пример 3. Обмен значениями элементов диагоналей квадратной матрицы, расположенных в одной строке.
void obmen(int strslb, int m[max_x][max_y]) {
int i,buf,t;
for (i=0;i<strslb;i++){
//номера строки и столбца элемента главной диагонали равны
buf= m[i][i];
//t-номер столбца соответствующего элемента побочной диагонали
t= abs(strslb-i-1);
m[i][i]= m[i][t];
m[i][t]=buf;
}
}
Задания
1.Объявите двумерный вещественный массив, в котором n ´ m элементов. Заполните его числами, полученными по закономерности: . Отсортируйте каждую строку массива по убыванию. Распечатайте его в виде таблицы с точностью до 3 знаков после запятой дважды – до и после сортировки. Оформите генерацию, вывод массива и сортировку строк с помощью функций.
2.Объявите двумерный целочисленный массив, в котором n строк по m элементов. Выполните генерацию массива случайными целыми числами из промежутка [a; b). Переставьте столбцы массива так, чтобы их максимальные элементы образовали возрастающую последовательность. Выведите массив на экран в виде таблицы дважды – до и после перестановки. Оформите генерацию, вывод массива и перестановку столбцов с помощью функций.
3.Дана квадратная матрица размера n ´ т, заполненная с клавиатуры целыми числами так, что в каждой строке и каждом столбце ровно по одному нулевому элементу. Переставьте строки матрицы так, чтобы нулевые элементы были расположены вдоль главной диагонали. Выведите массив на экран в виде таблицы дважды – до и после перестановки. Оформите генерацию, вывод массива и перестановку строк с помощью функций.
Домашние задания
1.Объявите двумерный вещественный массив, в котором n ´ m элементов. Выполните генерацию массива случайными вещественными числами из промежутка [a; b). Отсортируйте каждый столбец массива по возрастанию. Распечатайте его в виде таблицы с точностью до 2 знаков после запятой дважды – до и после сортировки. Оформите генерацию, вывод массива и сортировку столбцов с помощью функций.
2.Дана квадратная матрица размера 2n ´ 2т. Получите новую матрицу, переставляя ее блоки размера n ´ n в соответствии с рисунком.
3.Приведите квадратную целочисленную матрицу n ´ n к треугольному виду. Способ генерации матрицы выберите самостоятельно.
Дата добавления: 2015-02-16; просмотров: 752;