Алгоритмы и программы для работы с векторами и матрицами. Часть 1

1. Введение

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

2. Организация работы с массивами

в программах сложной модульной структуры

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

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

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

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

Листинг 1

/*                         define99.h

*/

//==============================================================

//  одномерные массивы - векторы

//  двумерные массивы - матрицы

//  просто Vector

typedef double Vector[100];

//  просто Matrix

typedef double Matrix[10][10];

//==============================================================

//  структуры векторов и матриц

//  вещественный вектор

struct nVector

{

int n;

double X[100];

};

//  вещественная матрица с различным числом строк и столбцов

struct mnMatrix

{

int m,n;

double A[10][10];

};

//  квадратная вещественная матрица 

struct nMatrix

{

int n;

double A[10][10];

};

//==============================================================

//  строковые переменные

typedef  char   str12[12];

typedef  char   str80[80];

//==============================================================

//  конец заголовочного файла  define99.h

//==============================================================

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

Листинг 2

// головная программа

#include “define99.h”

void Murka(int, int, Matrix, Vector);  // прототип функции Murka

void Bobik(int, Vector, Matrix);       // прототип функции Bobik

void main()

{

int m,n;

Matrix B,C;

Vector Z;

…

Murka(m,n,B, Z);

…

Bobik(m,Z, C);

…

}

// модуль Murka

#include “define99.h”

void Murka(int m, int n, Matrix A, Vector& X);

{

…

}

// модуль Bobik

#include “define99.h”

void Bobik(int m, Vector X, Matrix& A);

{

…

}

Предполагается, что модули Murka и Bobik размещены в разных файлах и перед построением задачи объединены и головной программой в общий проект (project).

3. Использование записей для работы с векторами и матрицами

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

Записи представляют собой сложную структуру