Delphi_part2

требованиями варианта из таблицы 8.1. Номер варианта выбирается по последней цифре номера зачетной книжки.

Главное меню проекта должно включать следующие пункты:

–Создание массива

–Сортировка массива

–Вставка элемента в массив

–Удаление элемента из массива

На форме должно быть поле для ввода количества элементов массива и поле для максимального значения числа в массиве (если тип элементов ±Real ).

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

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

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

8.5 СОДЕРЖАНИЕ ОТЧЕТА

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

–Цель работы

–Краткое описание изученных методов сортировки массивов

–Тексты процедур и функций, разработанных самостоятельно

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

–Выводы

КОНТРОЛЬНЫЕ ВОПРОСЫ

–Сортировка выбором

–Сортировка обменом

–Сортировка вставкой

–Вставка элемента в отсортированный массив

–Слияние отсортированных массивов.

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

–Удаление элемента из отсортированного массива

41

Таблица 8.1 – Задания на лабораторную работу
						Метод
№	Создание	Хране	Тип	1-й уровень	2-й
	исходного	ние	данных	сортировки	уровень	сортиров
	массива	масс.	массива		сортировки	ки
0	InputBox	TMemo	String	По длине	По	Вставкой
				строки на	алфавиту
				возрастание		Обменом
1	Random	Tedit	±Real	Отрицатель-	На
				ные, затем	убывание
				положительн.		Выбором
2	InputBox	Tmemo	String	По длине	По
				строки на	алфавиту
				убывание		Вставкой
3	Random	Tedit	±Real	Положитель-	На
				ные, затем	возраста-
				отрицател.	ние	Обменом
4	InputBox	Tmemo	String	По длине	С конца
				строки на	алфавита
				убывание		Выбором
5	Random	Tedit	±Real	По	Положи-
				абсолютной	тельные,
				величине	затем
					отрицател.	Вставкой
6	InputBox	Tmemo	String	По длине	С конца
				строки на	алфавита
				возрастание		Обменом
7	Random	Tedit	±Real	Вначале	На
				большие 1	возраста-
				затем	ние
				меньшие		Выбором
8	InputBox	TMemo	String	Слова с	По
				цифрами в	алфавиту
				конец
						Вставкой
9	Random	TEdit	±Real	Вначале	На убыва-
				меньшие 1	ние
				затем большие

42

9 ЛАБОРАТОРНАЯ РАБОТА № 9. РАБОТА С ДВУМЕРНЫМИ МАССИВАМИ (МАТРИЦАМИ)

Цели работы:

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

–Освоить алгоритмы тотальной и выборочной обработки элементов матриц

–Освоить алгоритмы простейших преобразований матриц

–Освоить алгоритмы сортировки матриц

–Познакомиться с процедурным типом данных

9.1 КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

Матрица – это тип данных, которому соответствует таблица. При работе с матрицами оперируют понятиями имя матрицы, столбец, номер столбца, строка, номер строки, элемент, размер матрицы, например 3 х 4.

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

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

Вматрице, для идентификации элемента, требуется два индекса. Это как бы координаты элемента в матрице. При обращении к элементу его индексы указывают после имени матрицы в квадратных скобках, разделяя их запятой. Например, если имя матрицы matrix, то matrix[2,3] – это элемент матрицы с координатами 2 и 3. Какой из индексов определяет строку, а какой столбец - это решает программист. Мы будем далее считать, что первый индекс задает номер строки, а второй – номер столбца, и начинать нумерацию будем с 1. Так принято у математиков. Но у компонента StringGrid, который будет часто использоваться в этой лабораторной работе все наоборот, первый индекс – это номер столбца, второй индекс – это номер строки, и нумерация начинается с 0. Это пример плюрализма мнений. Постарайтесь не запутаться.

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

9.1.1Описание матриц

Матрицу логичнее всего описать как массив массивов. Во фрагменте подпрограммы, представленном ниже в качестве примера, описан тип TMatrix4x3, представляющий таблицы целых чисел. Эти таблицы имеют по 4 столбца и 3 строки. Индексы столбцов и строк начинаются с 1. В примере

43

описана и переменная myMatrix типа TMatrix4x3.

…

type

TMatrix4x3 = Array[1..4] of Array[1..3] of Integrer; var

myMatrix:TMatrix4x3;

…

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

…

type

TMatrix4x3 = Array[0..3, 0..2] of Integrer; var

myMatrix:TMatrix4x3;

…

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

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

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

чисел. Соответствующий тип назовем	TMatrixInt10x10. Описание
соответствующего типа будет выглядеть так.
…

type

TMatrixInt10x10= Array[1..10,1..10] of Integrer;

…

9.1.2 Использование компонента StringGrid для вводавывода матриц

Значок этого компонента находится на вкладке Additional панели инструментов Delphi. Компонент StringGrid представляет собой таблицу, ячейки которой содержат строки символов. При появлении на форме этот компонент первоначально имеет вид, показанный на рисунке 9.1.

44

Рисунок 9.1. Исходный вид компонента StringGrid

Фактически, компонент представляет собой матрицу, у которой строки и столбцы нумеруются с 0.

Получить доступ к конкретной ячейке таблицы StringGrid можно, используя свойство Cells[Col, Row], где Col - номер колонки, Row - номер строки. Это свойство возвращает текст, записанный в ячейке.

Некоторые свойства компонента представлены в таблице 9.1. Таблица 9.1 - Свойства компонента StringGrid

Свойство	Что определяет
Name	Имя компонента
RowCount	Количество строк таблицы
ColCount	Количество колонок
FixedCols	Количество зафиксированных колонок таблицы в левой
	части таблицы. При горизонтальной прокрутке таблицы
	колонки остаются на месте.
	Ячейки этих колонок имеют серый цвет.
FixedRows	Количество зафиксированных строк в верхней части
	таблицы.
DefaultRowHeight	Высота строк таблицы
DefaultColWidth	Ширина колонок
Options.GoEditing	True – редактирование разрешено, False – запрещено

Компонент идеально подходил бы для визуального представления матрицы, если бы мы определяли матрицу так, как StringGrid. Но так как мы нумеруем строки и столбцы с 1, а не с 0 и, кроме того, вначале задаем индекс строки, а затем столбца, то возникает небольшая путаница. Об этом нельзя забывать.

9.1.3 Тотальная обработка данных в матрицах

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

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

–Заполнение матрицы случайными или другими числами.

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

45

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

–Умножение матрицы на число.

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

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

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

procedure fillMatrixWithZero(var m:TMatrixInt10x10, nRow, nCol); var i, j : integer;

begin

for i:=1 to nRow do for j:=1 to nCol do m[i,j]:=0;

end;

В эту процедуру передается адрес матрицы, а также количество строк (nRow) и количество столбцов (nCol)

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

9.1.4 Выборочная обработка матрицы

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

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

–Элементы вспомогательной диагонали квадратной матрицы.

–Элементы некоторого столбца или строки матрицы.

–Элементы матрицы, расположенные по ее кромке.

–Элементы квадратной матрицы, расположение которых соответствует расположению белых или черных клеток шахматной доски.

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

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

Во втором случае, на вспомогательной диагонали, номер столбца j связан с номером строки i соотношением j=nCol–i+1. В этом соотношении nCol – это максимальный индекс для столбца.

46

Вслучае обработки одного из столбцов матрицы, его номер фиксирован,

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

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

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

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

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

–Транспонирование матрицы (поворот вокруг главной диагонали).

–Поворот вокруг вспомогательной диагонали.

–Поворот вокруг горизонтальной оси.

–Поворот вокруг вертикальной оси.

Таблица 9.2 – Параметры циклов при перестановках элементов матрицы

	Линия			Индексы элемента
	симметрии	Внешний цикл	Внутренний цикл
				текщ.	симметр.
	при повороте
	Главная	от i=2 до nRow	По элементам строки	[ i, j ]	[ j, i ]
	диагональ		(индексы столбца)
			от j = 1 до i-1
	Вторая	По строкам,	от j = 1 до nCol - i	[ i, j ]	[nRow–j +1,
	диагональ	от i=1 до nRow -1			nCol – i+1]
	Горизонталь-	По строкам,	По элементам строки	[ i, j ]	[nRow –i+1,
	ная ось	от i=1 до nRow div 2	(индексы столбца)		j ]
			от j = 1 до nCol
	Вертикальная	По строкам,	По элементам строки	[ i, j ]	[ i,
	ось	от i=1 до nRow	(индексы столбца)		nCol – j+1 ]
			от j = 1 до nCol div 2

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

47

Основная трудность, возникающая при решении этих задач, это определение индексов элемента, симметричного текущему элементу.

В таблице 8.1 приведены параметры циклов, обеспечивающих перевороты элементов матрицы вокруг различных осей симметрии. Индексные выражения, приведенные в таблице, составлены в предположении, что нижние индексы строк и столбцов раны единице, верхние индексы столбцов и строк соответственно равны nCol и nRow, а m – имя матрицы.

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

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

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

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

Есть две разновидности задачи сортировки матриц Первая из них заключается в том, что сортируются отдельные части

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

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

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

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

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

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

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

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

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

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

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

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

Такая сортировка обеспечивает расположение элементов матрицы по

48

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

Некоторые из них приведены ниже.

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

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

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

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

диагонали.

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

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

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

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;

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

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

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

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

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

49

строк.

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

1	2	3	4
5	6	7	8
9	10	11	12

Рисунок 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];

50