Описание методов решения

Пример решения задачи

Индивидуальное задание:

· матрица содержит нули ниже главной диагонали;

· индексация начинается с 0.

Представление в памяти

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

Модульная структура программного изделия

Программное изделие должно быть отдельным модулем, файл LAB2.C, в котором должны размещаться как данные (матрица и вспомогательная информация), так и функции, которые обеспечивают доступ. Внешний доступ к программам и данным модуля возможен только через вызов функций чтения и записи элементов матрицы. Доступные извне элементы программного модуля должны быть описаны в отдельном файле LAB2.H, который может включаться в программу пользователя оператором препроцессора:

#include "lab2.h"

Пользователю должен поставляться результат компиляции — файл LAB2.OBJ и файл LAB2.H.

Преобразование 2-компонентного адреса элемента матрицы, которую задает пользователь, в 1-компонентную должно выполняться отдельной функцией (так называемой, функцией линеаризации), вызов которой возможен только из функций модуля. Возможны три метода преобразования адреса:

· при создании матрицы для нее создается также и дескриптор D[N] — отдельный массив, каждый элемент которого соответствует одной строке матрицы; дескриптор заполняется значениями, подобранными так, чтобы: n = D[x] + y, где x, y — координаты пользователя (строка, столбец), n — линейная координата;

· линейная координата подсчитывается методом итерации как сумма полезных длин всех строк, предшествующих строке x, и к ней прибавляется смещение y -го полезного элемента относительно начала строки;

· для преобразования подбирается единое арифметическое выражение, которой реализует функцию: n = f(x,y).

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

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

Описание логической структуры

Общие переменные

В файле LAB2.C описаны такие статические переменные:

· int NN — размерность матрицы;

· int SIZE — количество ненулевых элементов в матрице;

· int *m_addr — адрес сжатой матрицы в памяти, начальное значение этой переменной — NULL — признак того, что память не выделена;

· int L2_RESULT — общий флаг ошибки, если после выполнения любой функции он равен -1, то произошла ошибка.

Переменные SIZE и m_addr описаны вне функций с квалификатором static, это означает, что они доступны для всех функций в этом модуле, но недоступны для внешних модулей. Переменная L2_RESULT также описана вне всех функций, не без явного квалификатора. Эта переменная доступна не только для этого модуля, но и для всех внешних модулей, если она в них буде описана с квалификатором extern. Такое описание имеется в файле LAB2.H.

Функция creat_matr

Функция creat_matr предназначена для выделения в динамической памяти места для размещения сжатой матрицы. Прототип функции:

int creat_matr (int N);

где N — размерность матрицы.

Функция сохраняет значение параметра в собственной статической переменной и подсчитывает необходимый размер памяти для размещения ненулевых элементов матрицы. Для выделения памяти используется библиотечная функция C malloc. Функция возвращает -1, если при выделении произошла ошибка, или 0, если выделение прошло нормально. При этом переменной L2_RESULT также присваивается значение 0 или -1.

Функция close _ matr

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

Прототип функции:

int close_matr (void);

Функция возвращает 0 при успешном освобождении, -1 — при попытке освободить невыделенную память.

Если адрес матрицы в памяти имеет значения NULL, это признак того, что память не выделялась, тогда функция возвращает -1, иначе — освобождает память при помощи библиотечной функции free и записывает адрес матрицы — NULL. Соответственно функция также устанавливает глобальный признак ошибки — L2_RESULT.

Функция read _ matr

Функция read_matr предназначена для чтения элемента матрицы. Прототип функции:

int read_matr(int x, int y);

где x и y — координаты (строка и столбец). Функция возвращает значение соответствующего элемента матрицы. Если после выполнения функции значение переменной L2_RESULT -1, то это указывает на ошибку при обращении.

Проверка корректности задания координат выполняется обращением к функции ch_coord, если эта последняя возвращает ненулевое значение, выполнение read_matr на этом и заканчивается. Если же координаты заданы верно, то проверяется попадание заданного элемента в нулевой или ненулевой участок. Элемент находится в нулевом участке, если для него номер строки больше, чем номер столбца. Если элемент в нулевом участке, функция просто возвращает 0, иначе — вызывает функцию линеаризации lin и использует значение, которое возвращает lin, как индекс в массиве m_addr, по которому и выбирает то значения, которое возвращается.

Функция write_matr

Функция write_matr предназначена для записи элемента в матрицу. Прототип функции:

int write_matr(int x, int y, int value);

где x и y — координаты (строка и столбец), value — то значение, которое нужно записать. Функция возвращает значение параметра value, или 0 — если была попытка записи в нулевой участок. Если после выполнения функции значение переменной L2_RESULT -1, то это указывает на ошибку при обращении.

Выполнение функции подобно функции read_matr с тем отличием, что, если координаты указывают на ненулевой участок, то функция записывает value в массив m_addr.

Функция ch_coord

Функция ch_coord предназначена для проверки корректности задания координат. Эта функция описана как static и поэтому может вызываться только из этого же модуля. Прототип функции:

static char ch_coord(int x, int y);

где x и y — координаты (строка и столбец). Функция возвращает 0, если координаты верные, -1 — если неверные. Соответственно, функция также устанавливает значение глобальной переменной L2_RESULT.

Выполнение функции собственно состоит из проверки трех условий:

· адрес матрицы не должен быть NULL, то есть, матрица должна уже находиться в памяти;

· ни одна из координат не может быть меньше 0;

· ни одна из координат не может быть больше NN.

Если хотя бы одно из этих условий не выполняется, функция устанавливает признак ошибки.

Функция lin

Функция lin предназначена для преобразования двумерных координат в индекс в одномерном массиве. Эта функция описана как static и поэтому может вызываться только из этого же модуля. Прототип функции:

static int lin(int x, int y);

где x и y — координаты (строка и столбец). Функция возвращает координату в массиве m_addr.

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

x x x x x x

0 x x x x x

0 0 x x A x

0 0 0 x x x

0 0 0 0 x x

0 0 0 0 0 x

Координату элемента можно определить как:

n = SIZE — sizeX +offY,

где SIZE — общее количество элементов в матрице,

SIZE = NN * (NN — 1) / 2 + NN;

sizeX — количество ненулевых элементов, которые содержатся в строке x и ниже,

sizeX = (NN — x) * (NN — x — 1) / 2 + (NN — x);

offY — смещение нужного элемента от начала строки x,

offY = y — x

Программа пользователя

Для проверки функционирования нашего модуля создается программный модуль, который имитирует программу пользователя. Этот модуль обращается к функции creat_matr для создания матрицы нужного размера, заполняет ненулевую ее часть последовательно увеличивающимися числами, используя для этого функцию write_matr, и выводит матрицу на экран, используя для выборки ее элементов функцию read_matr. Далее в диалоговом режиме программа вводит запрос на свои действия и читает/пишет элементы матрицы с заданными координатами, обращаясь к функциям read_matr/ write_matr. Если пользователь захотел закончить работу, программа вызывает функцию close_matr.

Тексты программных модулей

/******* Файл LAB2.H *************************/

/* Описание функций и внешних переменных файла LAB2.C */

extern int L2_RESULT; /* Глобальна переменная — флаг ошибки */

/***** Выделение памяти под матрицу */

int creat_matr (int N);

/***** Чтение элемента матрицы по заданным координатам */

int read_matr (int x, int y);

/***** Запись элемент в матрицу по заданным координатам */

int write_matr (int x, int y, int value);

/***** Уничтожение матрицы */

int close_matr (void);

/******* Конец файла LAB2.H *******************/

/********** Файл LAB2.C *************************/

/* В этом файле определены функции и переменные для обработки матрицы, заполненной нулями ниже главной диагонали */

#include <alloc.h>

static int NN; /* Размерность матрицы */

static int SIZE; /* Размер памяти */

static int *m_addr=NULL; /* Адрес сжатой

матрицы */

static int lin(int, int); /* Описание функции линеаризации */

static char ch_coord(int, int); /* Описание функции проверки */

int L2_RESULT; /* Внешняя переменная, флаг ошибки */

/*************************************************/

/* Выделение памяти под сжатую матрицу */

int creat_matr (int N) {

/* N — размер матрицы */

NN=N;

SIZE=N*(N-1)/2+N;

if ((m_addr=(int *)malloc(SIZE*sizeof(int))) == NULL)

return L2_RESULT=-1;

else

return L2_RESULT=0;

/* Возвращает 0, если выделение прошло успешно, иначе -1 */

}

/*************************************************/

/* Уничтожение матрицы (освобождение памяти) */

int close_matr(void) {

if (m_addr!=NULL) {

free(m_addr);

m_addr=NULL;

return L2_RESULT=0;

}

else return L2_RESULT=-1;

/* Возвращает 0, если освобождение пршло успешно, иначе — -1 */

}

/*************************************************/

/* Чтение элемента матрицы по заданным координатам */

int read_matr(int x, int y) {

/* x, y -координати (строка, столбец) */

if (ch_coord(x,y)) return 0;

/* Если координаты попадают в нулевой участок — возвращается 0, иначе — применяется функция линеаризации */

return (x > y)? 0: m_addr[lin(x,y)];

/* Проверка успешности чтения — по переменной

L2_RESULT: 0 — без ошибок, -1 — была ошибка */

}

/*************************************************/

/* Запись элемента матрицы по заданным координатам */

int write_matr(int x, int y, int value) {

/* x, y -координати, value — записываемое значение */

if (chcoord(x,y)) return;

/* Если координаты попадают в нулевой участок — записи нет, иначе — применяется функция линеаризации */

if (x > y) return 0;

else return m_addr[lin(x,y)]=value;

/* Проверка успешности записи — по L2_RESULT */

}

/**************************************************/

/* Преобразование 2-мерных координат в линейную */

/* (вариант 3) */

static int lin(int x, int y) {

int n;

n=NN-x;

return SIZE-n*(n-1)/2-n+y-x;

}

/*************************************************/

/* Проверка корректности обращения */

static char ch_coord(int x, int y) {

if ((m_addr==NULL) ||

(x>SIZE) || (y>SIZE) || (x<0) || (y<0))

/* Если матрица не размещена в памяти, или заданные координаты выходят за пределы матрицы */

return L2_RESULT=-1;

return L2_RESULT=0;

}

/*******Конец файла LAB2.C ********************/

/******** Файл MAIN2.C **************************/

/* "Программа пользователя" */

#include "lab2.h"

main(){

int R; /* размерность */

int i, j; /* номера строки и столбца */

int m; /* значения элемента */

int op; /* операция */

clrscr();

printf('Введите размерность матрицы >'); scanf("%d",R);

/* создание матрицы */

if (creat_matr (R)) {

printf("Ошибка создания матрицы\n");

exit(0);

}

/* заполнение матрицы */

for (m=j=0; j<R; j++)

for (i=о; i<R; i++)

write_matr(i,j,++m);

while(1) {

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

clrscr();

for (j=0; j<R; j++) {

for (i=0; i<R; i++)

printf("%3d ",read_matr(i,j));

printf("\n");

}

printf("0 — выход\n1 — чтение\n2 — запись\n>")

scanf("%d",&op);

switch(op) {

case 0:

if (close_matr()) printf("Ошибка при уничтожении\n");

else printf("Матрица уничтожена\n");

exit(0);

case 1: case 2:

printf("Введите номер строки >");

scanf("%d",&j);

printf("Введите номер столбца >");

scanf("%d",&i);

if (op==2) {

printf("Введите значение элемента >");

scanf("%d",&m);

write_matr(j,i,m);

if (L2_RESULT<0) pritnf("Ошибка записи\n");

}

else {

m=read_matr(j,i);

if (L2_RESULT<0) pritnf("Ошибка считывания\n");

else printf("Считано: %d\n",m);

}

printf("Нажмите клавишу\n"); getch();

break;

}

}

}

/*****Конец файла MAIN2.C **********************/

Варианты

Вариант 1 требует:

· добавления к общим статическим переменным еще переменной:

static int *D; /* адрес дескриптора */

· добавления такого блока в функцию creat_matr:

{

int i, s;

D=(int *)malloc(N*sizeof(int));

for (D[0]=0,s=NN-1,i=1; i<NN; i++)

D[i]=D[i-1]+s--;

}

· изменения функции lin на:

static int lin(int x, int y) {

return D[x]+y;

}

Вариант 2 требует:

· изменения функции lin на:

static int lin(int x, int y) {

int s;

for (s=j=0; j<x; j++)

s+=NN-j;

return s+y-x;

}

:

Дата добавления: 2017-02-01