Правила записи программы на языке Си 5 Правила формального описания синтаксиса языка программирования 6

Вид материала

Лекции

Содержание 10.3.Особенности работы с двумерными массивами 10.3.1.Пересчет индексов вручную 10.3.2.Массивы с постоянной длиной строки 10.3.3.Общий случай двумерного массива

Подобный материал:

• Правила преобразований из одного типа в другой и правила приведения типов в языке Object, 19.03kb.
• Оформление программы на языке Паскаль. Оператор вывода. Описание переменных. Оператор, 186.34kb.
• Программа наименование дисциплины Латинский язык (1,2 уровни), 154.48kb.
• Экзаменационные вопросы по курсу "Методы программирования", 32.44kb.
• Вопросы по курсу Программирование на языке высокого уровня (яву), 102.97kb.
• Структура программы в языке программирования С++. Обмен данными между функциями (параметры, 37.24kb.
• Программа курса " Азы программирования", 26.19kb.
• Структура программы языка Турбо Паскаль Программа на языке Турбо Паскаль имеет вид, 792.5kb.
• Эволюция языков программирования, 493.92kb.
• Структура программы на языке Turbo Pascal, 26.15kb.

10.3.Особенности работы с двумерными массивами

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

10.3.1.Пересчет индексов вручную

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


#include

#include

#include


#define MAXVAL 1000


void *Malloc ( size_t size );

void RandomMatr ( double *Matr, int n, int l );

void OutMatr ( char *name,

double *Matr, int n, int m );


void main( void )

{

size_t n = 5, m = 6;

double *A;

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

A = (double *) Malloc( n*m*sizeof(double) );

/* Заполнение матрицы значениями и распечатка */

RandomMatr(A, n, m);

OutMatr("A", A, n, m);

/* освобождение памяти */

free(A);

}


void RandomMatr (double *Matr, int n, int m)

{

int i, j;

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

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

Matr[i*m+j] = random(MAXVAL) + 1;

}


void OutMatr( char *name, double *Matr, int n, int m )

{

int i, j;

printf("\nМатрица %s\n---------------\n", name);

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

{

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

printf("%8.1lf ", Matr[i*m+j]);

printf("\n");

}

}


void * Malloc( size_t size )

{

void *p = malloc(size);

if( !p )

{ printf("Недостаточно памяти!\n"); exit(1); }

return p;

}


Функция rand() с прототипом из возвращает псевдослучайное число в диапазоне от 0 до MAXVAL-1.

10.3.2.Массивы с постоянной длиной строки

Если у массива длина строки постоянная, то адресацию динамического двумерного массива может выполнить компилятор:


#include

#include

#include


#define MAXVAL 1000

#define STRLEN 6


void *Malloc ( size_t size );

void RandomMatr ( double (*Matr)[STRLEN], int n );

void OutMatr ( char *name,

double (*Matr)[STRLEN], int n );


void main( void )

{

size_t n = 5;

double (*A)[STRLEN];

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

A = (double (*)[STRLEN])

Malloc( n*sizeof(double[STRLEN]) );

/* Заполнение матрицы значениями и распечатка */

RandomMatr(A, n);

OutMatr("A", A, n);

/* освобождение памяти */

free(A);

}


void RandomMatr (double (*Matr)[STRLEN], int n)

{

int i, j;

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

for(j = 0; j < STRLEN; j++)

Matr[i][j] = random(MAXVAL) + 1;

}


void OutMatr( char *name, double (*Matr)[STRLEN], int n )

{

int i, j;

printf("\nМатрица %s\n---------------\n", name);

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

{

for(j = 0; j < STRLEN; j++)

printf("%8.1lf ", Matr[i][j]);

printf("\n");

}

}


void * Malloc( size_t size )

{

void *p = malloc(size);

if( !p )

{ printf("Недостаточно памяти!\n"); exit(1); }

return p;

}


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

10.3.3.Общий случай двумерного массива

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


#include

#include

#include


#define MAXVAL 1000


void *Malloc ( size_t size );

double **MakeMatr ( size_t n, size_t m );

void DelMatr ( double *Matr[] );

void RandomMatr ( double *Matr[], int n, int m );

void OutMatr ( char *name,

double *Matr[], int n, int m );


void main( void )

{

int n = 5, m = 6;

double **A;

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

A = MakeMatr(n, m);

/* Заполнение матрицы значениями и распечатка */

RandomMatr(A, n, m);

OutMatr("A", A, n, m);

/* освобождение памяти */

DelMatr(A);

}


void RandomMatr (double *Matr[], int n, int m)

{

int i, j;

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

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

Matr[i][j] = random(MAXVAL) + 1;

}


void OutMatr( char *name, double *Matr[], int n, int m )

{

int i, j;

printf("\nМатрица %s\n---------------\n", name);

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

{

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

printf("%8.1lf ", Matr[i][j]);

printf("\n");

}

}


void *Malloc( size_t size )

{

void *p = malloc(size);

if( !p )

{ printf("Недостаточно памяти!\n"); exit(1); }

return p;

}


/* Конструктор матрицы */

double **MakeMatr( size_t n, size_t m )

{

double **Matr; size_t i;

Matr = (double**) Malloc( (n + 1) * sizeof(double *) );

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

Matr[i] = (double *) Malloc( m * sizeof(double) );

Matr[n] = NULL;

return Matr;

}


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

void DelMatr( double *Matr[] )

{

size_t i;

for(i = 0; Matr[i]; i++) free(Matr[i]);

free(Matr);

}


Вначале в функции-конструкторе MakeMatr() выделяется вектор памяти размером n+1 элементов для хранения указателей на double. Затем для каждой из n строк массива выделяется память и адрес ее записывается в ранее выделенный вектор указателей. В последний элемент вектора заносится величина NULL, которая в деструкторе будет сигнализировать о конце вектора. Иначе в деструктор пришлось бы передавать дополнительный параметр n.

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

Если массив целиком укладывается в сегмент, то для работы с ним можно предложить следующую схему с меньшими накладными расходами на выделение памяти:


/* Конструктор матрицы */

double **MakeMatr( size_t n, size_t m )

{

double **Matr; size_t i;

Matr = (double**) Malloc( n * sizeof(double *)

+ n * m * sizeof(double) );

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

Matr[i] = (double *)(Matr + n) + i * m;

return Matr;

}


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

void DelMatr( double *Matr[] )

{

free(Matr);

}


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

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


#include

#include

#include


#define MAXVAL 1000


void *Malloc ( size_t size );

double **MakeMatr ( size_t n, size_t m );

void DelMatr ( double *Matr[] );

size_t GetN ( double *Matr[] );

size_t GetM ( double *Matr[] );

void RandomMatr ( double *Matr[] );

void OutMatr ( char *name, double *Matr[] );


void main( void )

{

int n = 5, m = 6;

double **A;

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

A = MakeMatr(n, m);

/* Заполнение матрицы значениями и распечатка */

RandomMatr( A );

OutMatr("A", A );

/* освобождение памяти */

DelMatr(A);

}


void RandomMatr ( double *Matr[] )

{

int i, j, n = GetN(Matr), m = GetM(Matr);

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

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

Matr[i][j] = random(MAXVAL) + 1;

}


void OutMatr( char *name, double *Matr[] )

{

int i, j, n = GetN(Matr), m = GetM(Matr);

printf("\nМатрица %s\n---------------\n", name);

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

{

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

printf("%8.1lf ", Matr[i][j]);

printf("\n");

}

}


void * Malloc( size_t size )

{

void *p = malloc(size);

if( !p )

{ printf("Недостаточно памяти!\n"); exit(1); }

return p;

}


/* Конструктор матрицы */

double **MakeMatr( size_t n, size_t m )

{

double **Matr; size_t i;

Matr = (double**) Malloc( 2 * sizeof(size_t)

+ n * sizeof(double *) );

(size_t *)Matr += 2;

for(i=0; i
Matr[i] = (double *) Malloc( m * sizeof(double) );

Matr[n] = NULL;

*( (size_t *)Matr - 2 ) = n;

*( (size_t *)Matr - 1 ) = m;

return Matr;

}


size_t GetN( double *Matr[] )

{

return *( (size_t *)Matr - 2 );

}


size_t GetM( double *Matr[] )

{

return *( (size_t *)Matr - 1 );

}


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

void DelMatr( double *Matr[] )

{

size_t i, n = GetN(Matr);

for(i = 0; i < n; i++) free(Matr[i]);

free( (size_t *)Matr - 2 );

}


В конструкторе теперь выделяется память для хранения n указателей на double и для двух величин типа size_t, которые служат для хранения размеров матрицы. Выделять дополнительный элемент для занесения NULL теперь нет необходимости, так как теперь с помощью функций GetN() и GetM() можно получить соответствующие размеры массива. Способ индексации не изменяется и она по-прежнему выполняется в стиле индексации двумерных массивов.

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