Удаление и вставка элементов матрицы

Здесь подразумевается удаление столбца или стоки матрицы, так как удалять отдельный элемент матрицы мы не можем, не нарушив прямоугольную структуру.

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

Сортировка элементов матрицы

Есть две разновидности задачи сортировки матриц

Первая из них заключается в том, что сортируются отдельные части матрицы, независимо от других частей. К этой разновидности можно отнести следующие задачи.

– Сортировка каждой строки или каждого столбца независимо от других.

– Сортировка одной из диагоналей матрицы.

– Сортировка строк или столбцов матрицы по значению первого элемента.

– Сортировка строк матрицы по сумме элементов строки.

– Сортировка столбцов по сумме элементов столбца.

Решение этих задач не намного сложнее сортировки массива.

Для решения первой задачи списка, сортировку массива следует применить последовательно для каждой строки или столбца.

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

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

Для решения последней задачи потребуется еще функция вычисления суммы элементов столбца или строки.

Вторая разновидность задач сортировки матрицы заключается в том, что в одной процедуре сортировки участвуют все элементы матрицы.

Такая сортировка обеспечивает расположение элементов матрицы по возрастанию или убыванию в направлении заданного способа обхода матрицы.

Варианты обхода элементов матрицы могут быть самые разные. Некоторые из них приведены ниже.

– По строкам сверху вниз и слева направо, или снизу вверх и справа налево, или змейкой.

– То же самое по столбцам.

– То же самое по линиям параллельным главной или вспомогательной диагоналям.

– Углом, вершина которого находится на главной или вспомогательной диагонали.

Каким бы не был способ обхода элементов матрицы, саму сортировку всегда можно свести к сортировке массива. Для этого следует переписать элементы матрицы в массив. Затем массив отсортировать одним из известных способов. После этого элементы массива нужно снова переписать в матрицу, обходя ее по требуемому маршруту.

Написать процедуру переписывания матрицы в массив не составляет труда.

//Допоміжна процедура для переписування матриці у одновимірний масив

Procedure MatrToArray(m:TMatrInt10x10; nRow,nCol:integer; var a:TArray100);

var n, i, j: integer;

Begin

n:= 0;

for i:= 1 to nRow do

for j:= 1 to nCol do

Begin

n:= n + 1;

a[n]:= m[i,j];

end;

end;

Проблема сортировки массива нами тоже уже решена. Можно использовать любой из ранее рассмотренных методов.

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

Подходы к созданию процедур маршрутизации могут быть разными.

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

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

Предположим, что матрица имеет 3 строки и 4 столбца, и обход матрицы совершается по строкам слева направо. Тогда элементы матрицы условно следует перенумеровать так, как показано на рисунке 9.2.

Рисунок 9.2 – Схема маршрута обхода матрицы при сортировке по строкам

Пусть номер элемента в массиве равен 7. Координаты этого элемента в матрице будут такими.

Номер строки будет (7-1) div 4 + 1 = 2.

Номер столбца будет (7-1) mod 4 + 1 = 3.

При расчете предполагается, что нумерация элементов во всех последовательностях начинается с единицы.

Ниже приведена процедура, реализующая запись элементов массива в матрицу, использующая приведенные расчетные формулы.

Исходными данными для процедуры являются

– m – матрица, которую нужно заполнить по строкам;

– nCol – количество столбцов матрицы;

– nRow – количество строк матрицы;

– аr – упорядоченный массив, из которого берутся данные для заполнения матрицы;

В процедуре вычисляются номер строки и номер столбца в матрице, соответствующие номеру i элемента в массиве, и в соответствии со значениями этих координат элемент массива переписывается в матрицу.

//Допоміжна процедура типу TcalcPos для сортування горизонтальною змією

procedure fillHrzLine(var m: TMatrInt10x10; nRow, nCol: integer; ar: TArray100);

var i, row,col:integer;

Begin

for i:= 1 to nRow*nCol do

Begin

// Вычисляем координаты точки в матрице по значению i

row:=(i-1) div nCol+1;

col:=(i-1) mod nCol +1;

//Записываем в матрицу элемент массива

m[row,col]:= ar[i];

end;

end;

end;

В тех случаях, когда маршрут сортировки сложный, расчетный способ непригоден.

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

Рисунок 9.3 – Схема маршрута обхода матрицы уголком вниз и налево, в направлении главной диагонали

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

В качестве примера можно привести процедуру маршрутизации для сортировки квадратной матрицы «Уголком, сверху – вниз – налево, от начала главной диагонали». Схема маршрута реализованного в процедуре приведена на рисунке 9.3.

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

Указанные особенности маршрута учитываются в приводимом ниже алгоритме.

//Процедура переписування масиву за маршрутом кутом Зверху-ліворуч

procedure fillCornerTopLeft(var m: TMatrInt10x10; nRow, nCol: integer;

ar: TArray100);

var i, row, col: integer;

Begin

//Переписываем массив в матрицу по маршруту кутом Зверху-ліворуч

row:=1;col:=1; // Координаты начала маршрута

// Цикл по элементам массива

for i:=1 to nRow*nCol do

Begin

// Записываем в матрицу элемент массива

m[row,col]:= ar[i];

// Определяем координаты в матрице для следующего элемента

if col = 1 then begin col:= row + 1;row:= 1; end

else if row < col then row:= row + 1

else col:= col - 1;

end;

end;

Названия формальных параметров в этой процедуре такие же, как и в предыдущем примере. В теле процедуры организован цикл последовательного формирования номеров столбца и строки для элементов отсортированного массива.

При каждом повторении цикла вычисляются координаты очередной точки маршрута. Способ вычисления координат следующей точки изменяется при достижении левого края матрицы или главной диагонали.

Задача сортировки матрицы, при наличии рассмотренных выше процедур, решается очень легко. Например, отсортировать некоторую матрицу, расположенную в компоненте StringGrid1, уголком вдоль главной диагонали сверху и налево можно так, как показано ниже. Конечно, если процедуры, к которым производятся обращения, написаны.

procedure TfrmSortMatr.btnCornerTopLeftClick(Sender: TObject);

var m: TMatrInt10x10; nRow, nCol: integer; ar: TArray100;

Begin

//Читаем матрицу с экрана

getMatrFromGrid(m, nRow, nCol, StringGrid1);

//Переписываем в массив

MatrToArray(m,nRow,nCol,ar);

//Сортируем массив

SortArray(ar,nRow*nCol);

//Переписываем упорядоченный массив в матрицу по заданному маршруту

fillCornerTopLeft(m,nRow, nCol, ar);

// Выводим матрицу на экран

showMatrInGrid(m,nRow,nCol,StringGrid2);

end;

9.2 Задание для самостоятельной работы

Расчетно-графическая работа № 3 выполняется в рамках проекта для данной лабораторной работы. Варианты заданий приведены в таблицах 9.3, 9.4, 9.5 и 9.6. Номер варианта выбирается в соответствии с последней цифрой номера зачетной книжки.

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

Интерфейс разрабатываемого проекта должен обеспечивать тестирование ваших заданий по РГР3, которые приведены ниже. Все компоненты интерфейса выбирайте по своему усмотрению. Примеры решения подобных задач можете найти в примерах к лекциям и модуле UnitMatrixDop.

Таблица 9.3 Задачи тотальной обработки матриц
Вариант	Задание
	Найти наибольшее и наименьшее число и его координаты в матрице случайных чисел.
	Подсчитать количество нулей и единиц в матрице, состоящей из случайных двоичных чисел.
	Найти наибольшее и наименьшее из четных значений и их координаты в матрице.
	Найти координаты всех элементов равных заданномучислу в матрице.
	Подсчитать суммы для четных и нечетных чисел в матрице.
	Сравнить элементы двух матриц и создать третью, элементы которой равны большему числу из каждой пары чисел. Результат вывести в окно ShowMessage
	Создать и вывести в окно ShowMessage матрицу, в которой нули расположены в клетках, у которых четная сумма индексов. Остальные клетки заполнить единицами.
	Из матрицы, заполненной числами, создать новую матрицу, элементы которой равны сумме цифр чисел в исходной.
	Создать матрицу, значения элементов которой равны сумме индексов этих элементов.
	Подсчитать, сколько раз встречается заданное число в матрице. Число вводить через InputBox.

 

 

Таблица 9.4 Задачи на выборочную обработку матриц
Вариант	Задание
	Создать массив, элементы которого равны количеству цифр чисел, расположенных по кромке матрицы.
	Создать массив, элементы которого равны максимальным элементам в нечетных столбцах матрицы.
	Создать массив, элементы которого равны минимальным элементам в четных строках матрицы.
	Создать массив, элементы которого равны сумме цифр чисел, расположенных по кромке случайно заполненной матрицы.
	Создать массив, элементы которого равны суммам пар чисел, расположенных на главной и вспомогательной диагонали матрицы.
	Создать массив, элементы которого соответствуют столбцу матрицы, номер которого вводится через InputBox.
	Создать массив, элементы которого равны сумме элементов в нечетных столбцах матрицы.
Продолжение таблицы 9.3
	Создать массив, элементы которого равны сумме элементов в четных строках матрицы.
	Создать массив, элементы которого соответствуют строке матрицы, номер которой вводится через InputBox.
	Создать массив, элементы которого равны суммам пар чисел, на осях квадратной матрицы с нечетного размера
Таблица 9.5 Задачи на перестановку элементов матрицы
Вариант	Задание по обработке
	Поменять местами наибольший и наименьший элементы матрицы.
	Перевернуть квадратную матрицу вдоль второй диагонали
	Перевернуть матрицу вдоль горизонтальной оси.
	Перевернуть матрицу вдоль вертикальной оси.
	Поменять местами элементы главной и вспомогательной диагонали матрицы.
	Поменять местами элементы вертикальной и горизонтальной оси квадратной матрицы с нечетным размером.
	Перевернуть задом - наперед элементы главной диагонали квадратной матрицы
	Перевернуть задом - наперед элементы второй диагонали квадратной матрицы
	Сдвинуть элементы по кромке квадратной матрицы так, чтобы первая строка стала последним столбцом, последний столбец – нижней строкой в обратном порядке, нижняя строка – первым столбцом и перевернутый первый столбец – первой строкой.
	Удалить заданные столбец и строку матрицы
Таблица 9.6 Задачи на сортировку матриц
Вариант	Маршрут сортировки
	Уголком, сверху – вниз – налево, от начала главной диагонали.
	Уголком, сверху – вниз – налево, с конца главной диагонали.
	Уголком, слева – направо – вверх, от начала главной диагонали.
	Уголком, слева – направо – вверх, с конца главной диагонали.
	Уголком, снизу – верх – направо, от начала главной диагонали.
	Уголком, снизу – верх – направо, с конца главной диагонали.
	Уголком, справа – налево – вниз, от начала главной диагонали.
	Уголком, справа – налево – вниз, с конца главной диагонали.
	Уголком, слева – направо – вниз, от начала второй диагонали
	Уголком, сверху – вниз – направо, с конца второй диагонали
	Уголком, слева – направо – вниз, с конца второй диагонали

9.3 Содержание отчета

– Наименование работы.

– Цель работы.

– Способы описание матриц.

– Схема алгоритма маршрутизации при сортировке матрицы по варианту расчетно-графической работы

– Тексты модуля формы с пояснениями в виде комментариев.

– Результаты тестирования проекта в виде копий окна приложения.

– Выводы.

Контрольные вопросы

– Способы описания матриц. Примеры.

– Тотальная обработка данных в матрицах. Примеры.

– Выборочная обработка матрицы. Примеры.

– Перестановки элементов матрицы. Примеры.

– Сортировка элементов матрицы. Примеры.

– Удаления и вставки в матрицы

– Свойства компонента StrinGrid и работа с ним. Примеры.

– Объяснение текстов подпрограмм модуля и связей их с событиями и другими подпрограммами.

– Написать процедуру для реализации одного из заданий таблиц 9.3 – 9.6.

 

10 ЛАБОРАТОРНАЯ РАБОТА № 10. РАБОТА С ЗАПИСЯМИ

Цели работы:

– Познакомиться со способами описания записей в Object Pascal.

– Освоить алгоритмы обработки записей.

10.1 Краткие теоретические сведения

Запись – это тип данных, которому соответствует смесь элементов данных разных типов. Каждый из таких элементов, входящих в состав записи, называется полем. При работе с записями оперируют понятиями имя записи и имя поля. Имена записям и ее полям присваиваются в соответствии со стандартными правилами конструирования имен идентификаторов. Программист может оперировать как со всей записью, так и с отдельными полями - это зависит от решаемой задачи и используемых инструкций.

Для записи используется ее имя, а для идентификации отдельных полей записи используется составное имя, которое состоит из имени записи и имени поля, разделенных точкой.

Объявление типа для записи

Синтаксис объявления для типа записи выглядит так:

 

Рисунок 10.1 – Синтаксис объявления записи

где <список для имен полей> - это идентификатор поля или список таких идентификаторов, разделенных запятыми.

В качестве примера рассмотрим описание типа записи о результатах аттестации студентов. Запись должна содержать три поля – фамилию студента с инициалами, наименование группы, в которой учится студент, и средний балл текущей успеваемости.

Ниже приведено описание такого типа

Type

TAttRecord = record

Fio: String[20];

Gr: String[5];

srBall: real

end;

 

Объявить переменные соответствующего типа можно так:

var r1, r2,r3: TAttRecord;

Для записей можно определить и константы, например,

Const

someStud: TAttRecord = (fio: ‘Полуботко Г.’; gr: ’СП001’; srBall: 4.53);

Значения полей можно определять с помощью оператора присваивания:

r1.fio:=’Петренко А,П,’;

r1.gr:= ‘КС041’;

r1.srBall:= ‘3.2’;

В тех случаях, когда полей много, для сокращения можно использовать конструкцию with … do, которая позволяет обращаться к полям без указания имени записи.

with r2 do

Begin

fio:=’Петров А,П,’;

gr:= ‘КС042’;

srBall:= ‘4.3’;

end;

Оператор присваивания можно использовать и для записи в целом. В примере, приведенном ниже, всем полям записи r3 будут присвоены значения полей записи r2.

r3:= r2;

Массивы записей

Из записей может быть создан массив, точно так же как из данных других типов. Например, если мы хотим иметь результаты аттестации для всех студентов, можно создать массив соответствующих записей.

Type

TAttArray = array [1..100] of TAttRec;

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

Например.

var a: TAttArray;

…

a[1].fio:=’Петренко А,П,’;

a[1].gr:= ‘КС041’;

a[1].srBall:= ‘3.2’;

 

Поля записей как массивы

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

Ниже описан другой вариант типа записи, который предусматривает наличие массива оценок в записи вместо среднего балла.

Type

TMarkArray = array[1..10] of integer;

TAttRecord = record

Fio: String[20]; Gr: String[5]; marks: TMarkArray;

end;

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

Например.

var r: TAttRecord;

…

r.mark[1]:=5;

 

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

Рассмотрим пример, в котором описан массив результатов модульного контроля с массивами оценок.

Type

TMarkArray = array[1..10] of integer;

TAttRecord = record

Fio: String[20]; Gr: String[5]; marks: TMarkArray;

end;

TAttArray=array[1..100] of TAttRecord;

var a: TAttArray;

…

a[15].mark[6]:=5;

 

Здесь в запись под номером 15 заносится пятерка по предмету под номером 6.

Сортировка массивов записей

Сортировка массива записей производится так же, как и сортировка массива чисел, то есть записи сравниваются и, если необходимо, переставляются. Единственная проблема здесь заключается в том, что способов сравнения записей, а, следовательно, и вариантов сортировки, может быть много, и каждый из них может понадобиться. Так для массива, рассмотренного в предыдущем примере, записи можно сортировать по фамилии студента или по среднему баллу, найденному из массива оценок, по количеству неудовлетворительных оценок и т.д. Более того, возможны и более сложные случаи сортировки, например, по группе, а в пределах одной группы по фамилии студента.

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

Ввод-вывод записей

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

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

Исходя из изложенных особенностей, можно рекомендовать вводить и выводить записи через компонент TStringGrid. Нулевую строку компонента целесообразно использовать для вывода названий полей, а в следующей строке выводить или выводить их значения. При работе с массивом технология работы остается та же. Количество столбцов и строк компонента, а также названия полей в нулевой строке можно задать программно, при загрузке формы.

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

Возможен и другой вариант ввода, при котором перед добавлением очередной записи вызывается процедура увеличения количества строк в компоненте TStringGrid. В этом случае о размере массива можно судить по количеству строк в компоненте. Этот вариант на наш взгляд предпочтительнее, но требует написания дополнительной процедуры.

При выводе массива записей количество строк компонента TStringGrid можно настраивать программно, в соответствии с количеством записей в массиве.

10.2 Создание проекта «Результаты аттестации»

В этом проекте мы будем работать с массивом, содержащим результаты промежуточной аттестации студентов. Каждый элемент массива будет хранить запись, полями которой будут фамилия студента с инициалами, наименование группы, в которой учится студент, средний балл и количество неудовлетворительных оценок у студента.

Требуется разработать интерфейс пользователя для проекта, который бы обеспечивал ввод нужного числа записей в компонент TstringGrid, чтение массива записей из компонента TstringGrid, вывод результатов обработки этого массива, и реализацию следующих функций по обработке массива записей.

– Комплексная сортировка по группе + по фамилии студента.

– Комплексная сортировка по количеству неудовлетворительных оценок ↓ + по среднему баллу ↑.

– Выборка студентов какой-нибудь группы, имеющих средний балл выше 4.

– Подсчет общего числа студентов, имеющих более 2-х неудовлетворительных оценок.

Данный проект может служить примером того, как выполнить задание для самостоятельной работы. Реализация проекта находится в папке