Представление двухмерной матрицы в виде одномерного массива

@s.t.o.k.a.t.o · Регистрация: 15.02.2011

Author24 — интернет-сервис помощи студентам

Здравствуйте, учюсь в институте и дали мне задачу не обьяснив толком сути вещей. По условию задачи необходимо для разряженной матрицы целых чисел в соответствии с индивидуальным заданием создать модуль доступа к ней, у котором обеспечить экономию памяти при размещении данных. .
Мне выпал вариант с матрицей в которой все нулевые элементы размещены в шахматном порядке, начиная с 1-го элемента 1-й строки.
В качестве примера приводится решение этой задачи с матрицей, которая содержит нули ниже главной диагонали; индексация начинается с 0.
Экономное использование памяти предусматривает, что для тех элементов матрицы, в которых наверняка содержатся нули, память выделяться не будет. Поскольку при этом нарушается двумерная структура матрицы, она может быть представлена в памяти как одномерный массив, но при обращении к элементам матрицы пользователь имеет возможность обращаться к элементу по двум индексам.
Преобразование 2-компонентного адреса элемента матрицы, которую задает пользователь, в 1-компонентную должно выполняться отдельной функцией (так называемой, функцией линеаризации), вызов которой возможен только из функций модуля. Возможны три метода преобразования адреса:
• при создании матрицы для нее создается также и дескриптор D[N] - отдельный массив, каждый элемент которого соответствует одной строке матрицы; дескриптор заполняется значениями, подобранными так, чтобы: n = D[x] + y, где x, y - координаты пользователя (строка, столбец), n - линейная координата;
• линейная координата подсчитывается методом итерации як сумма полезных длин всех строк, предшествующих строке x, и к ней прибавляется смещение y-го полезного элемента относительно начала строки;
• для преобразования подбирается единое арифметическое выражение, которой реализует функцию: n = f(x,y).
Прочитав все это я приступил к разбору примера, собственно ключевых функций три:

C

/*            Выделение памяти под сжатую матрицу        */
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 */

Массив m_addr хранит элементы матрицы.

C

/*      Запись элемента матрицы по заданным координатам      */
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 */
}

Функция ch_coord() проверяет, выходят ли координаты за границы заданного диапазона значений.

C

/*       Преобразование 2-мерних координат в линейную       */
/*                      (вариант 3)                         */
static int lin(int x, int y) {
   int n;
    n=NN-x;
   return SIZE-n*(n-1)/2-n+y-x;
}

Причем в примере почему-то перепутаны строки со столбцами, а нули наоборот распологаются выше главной диоганали, ну да ладно.
Сначало я посчитал что достаточно поменять условие проверки на нулевой элемент и изменил функцию write_matr() следующим образом:

C

int write_matr(int x, int y, int value) {
   if ( ch_coord(x,y) ) return 0;
   double c = 0;
   c = fmod(x+y,2);
   if (c == 0) return 0;
   else return m_addr[lin(x,y)]=value;
}

То есть использовал fmod() которая возвращает остаток от деления двух чисел, если сумма х+у четная, значит элемент нулевой и наоборот. Нолики вроде бы встали по своим местам, но теперь программа путала координаты элементов, вернее присваивала значение сразу нескольким элементам.
Например, я задаю матрицу 5 на 5 и запускаю цикл, чтобы присвоить элементам значения от 1 до 25, получалось следующее:
0 2 0 4 0
6 0 22 0 4
0 12 0 14 0
16 0 18 0 24
0 22 0 24 0
Тогда я нашел формулу вычисления индекса в линейном представлении конкретно для моей матрицы и изменил функцию lin():

C

1
2
3

static int lin(int x, int y) {
return((y-1)*NN+x)/2;
}

Теперь все записывается правильно, но при закрытии программы выходит ошибка, компилятор указывает на строку free(m_addr); функции close_matr().

C

int close_matr(void) {
   if ( m_addr!=NULL ) {
      free(m_addr);
      m_addr=NULL;
      free(D);
      return L2_RESULT=0;
      }
   else return L2_RESULT=-1;
}

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

Добавлено через 23 часа 23 минуты
Неужели ни кто не подскажет?

	16.02.2011, 08:38

Опции темы