Программирование циклических процессов с использованием

Многомерных массивов. Динамическое распределение памяти

 

Цель работы:

Изучить работу с многомерными массивами, освоить возможности динамического размещения данных.

 

Краткие теоретические сведения

Кроме одномерных массивов возможна работа с многомерными массивами. Объявление многомерного массива:

<тип><имя>[<размер 1 >][<размер 2 >]…[<размер N>]={{список начальных значений}, {список начальных значений},…};

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

Например, элементы двухмерного массива b[2][1] размещаются в памяти в следующем порядке:

b[0][0], b[0][1], b[1][0], b[1][1], b[2][0], b[2][1].

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

int a[3][4] = {{0,1,2,0},{9,-2,0,0},{-7,1,6,8}};

Если в какой-то группе {…} отсутствует значение, то соответствующему элементу присваивается 0. Предыдущий оператор будет эквивалентен следующему определению:

int a[3][4] = {{0,1,2},{9,-2},{-7,1,6,8}};

При обработке двухмерных массивов используются вложенные циклы. Например, ввод массива int a[5][4]:

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

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

scanf(“%d”,&a[i][j]);

 

Пример программы

Создать двухмерный массив целых чисел NxM (N и M не более 50), используя функцию rand, и вывести на экран в форме матрицы, N,M ввести с клавиатуры:

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

#define rnd (rand()/ 32768.0) /* rand - генератор случайных чисел от

0 до int, rnd – от 0 до 1 */

void main(void)

{ int i,j,n,m,a[50][50];

puts(“\n Input n, m:”); scanf(“%d %d”,&n,&m);

printf(“\n Array a \n”);

for(i=0; i<n; i++) // Оформление вывода в виде матрицы

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

a[i][j]=rnd*10-5; // случайные числа от –5 до 5

printf(“%d%c“, a[i][j], (j= =m-1)?’\n’:’ ‘);

}

getch();

}

Указатели на указатели

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

float name[5][10];

Если рассматривать его как массив пяти массивов размерностью по десять элементов каждый, то очевидна схема его размещения в памяти - последовательное размещение «строк» элементов. Обращению к элементам name[i][j] соответствует эквива­лентное выражение *(*(name+i)+j), а объявление этого массива указателем будет:

float **name;

Таким образом, имя двухмерного массива - имя указателя на указатель. Аналогичным образом можно установить соответствие между указателями и массивами с произвольным числом измерений. Количество символов «*» определяет уровень вложенности указателей друг в друга. При объявлении указателей на указатели возможна их одновременная инициализация.

Например:

int a=5;

int *p1=&a;

int **pp1=&p1;

int ***ppp1=&pp1;

Теперь присвоим целочисленной переменной а новое значение, например, 10. Одинаковое присваивание произведут следующие операции:

a=10; *p1=10; **pp1=10; ***ppp1=10;

Для доступа к области памяти, отведенной под переменную а, можно использовать и индексы. Справедливы следующие аналоги:

*p1 равносильно p1[0]

**pp1 равносильно pp1[0][0]

***ppp1 равносильно ppp1[0][0][0]

Таким образом, указатели на указатели – это имена многомерных массивов.

 

Динамическое размещение данных

Если в задаче заранее неизвестно количество объектов и объект описан указателем, удобно использовать динамическое размещение данных.

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

void * calloc (unsigned n, unsigned m); - возвращает указатель на начало области памяти для размещения n элементов по m байт каждый, при неудачном завершении возвращает значение NULL;

void * malloc (unsigned n); - возвращает указатель на блок памяти длиной n байт, при неудачном завершении возвращает значение NULL;

void * realloc (void *bf, unsigned n); - изменяет размер ранее выделенной памяти с адресом начала bf на n байт;

void free (void *bf); - освобождает ранее выделенный блок памяти с адресом bf;

coreleft (void); - возвращает значение объема неиспользованной памяти (тип возвра­ща­емого результата unsigned – для моделей памяти tiny, small, medium; unsigned long – для других моделей памяти).

Пример выделения памяти для массива действительных чисел размером n:

float *x; // Указатель объекта типа float – x[0]

int n; // Количество элементов массива

...

x=(float*)calloc(n,sizeof(float)); // Захват памяти для n элементов

...

free(x); // Освобождение памяти

Пример работы со строковыми данными

Проверить, является ли введенная строка палиндромом (справа налево читается так же, как и слева направо).

#include <stdio.h>

#include <string.h>

#include <conio.h>

#include <calloc.h>

void main(void)

{

char *s; // Объявление строки указателем

int i, k;

clrscr();

puts(" Vvedi stroky"); gets(s);

k=strlen(s);

s=(char*)calloc(k,sizeof(char)); // Захват памяти для строки длиной k

for (i=0; i<(int)(k/2); i++)

if(s[i]!=s[k-i-1])

{

puts("\t\a NO!!");

getch();

free(s); // Освобождение памяти

return;

}

puts("\t\a YES - Pаlindrom!");

getch();

free(s); // Освобождение памяти

}

 

Пример динамического размещения одномерного массива

Ввести массив действительных чисел размером n и вывести на экран.

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

#include<alloc.h>

void main()

{

int i,n;

float *a;

puts(“\n Введите размер массива n:”);

scanf(“%d”,&n);

printf(“\n Свободная память -%d”,coreleft());

a=(float*)calloc(n,sizeof(float)); // Захват памяти

printf(“\n Введите элементы массива a: \n”);

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

scanf(“%f”,(a+i)); // scanf(“%f”,&a[i]);

printf(“\n Массив a \n”);

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

printf(“ %6.3f \n“, a[i]);

printf(“\n Память после захвата -%d”,coreleft());

free(a); // Освобождение памяти

getch();

}

Пример динамического размещения двухмерного массива

...

void main(void)

{ int i,j,n,m;

float **a;

puts(“\n Введите n,m:”);

scanf(“%d %d”,&n,&m);

printf(“\n Свободная память -%d”,coreleft());

a=(float **)calloc(n,sizeof(float*)); // Захват памяти

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

a[i]=(float *)calloc(m,sizeof(float));

...

for(i=0; i<n; i++) free(a[i]); // Освобождение памяти

free(a);

getch();

}

 

Варианты индивидуальных заданий

1. В вещественной матрице размером NxN найти максимальный и минимальный элементы. Переставить строки, в которых они находятся. Если они находятся в одной строке, выдать об этом сообщение.

2. Квадратную вещественную матрицу А размером N возвести в K-ю степень, т.е. вычислить: А¹=А, А²=А·А, А³=А²·А и т.д.

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

4. Дана вещественная матрица размером NxM. Упорядочить ее строки по возрастанию наибольших элементов в строках матрицы.

5. Задан массив размером NxN, состоящий из 0 и 1. Повернуть элементы массива на 90⁰ по часовой стрелке.

6. Элемент матрицы назовем седловой точкой, если он наименьший в своей строке и наибольший (одновременно) в своем столбце (или наоборот, наибольший в своей строке и наименьший в своем столбце). Для заданной целочисленной матрицы размером NxM напечатать индексы всех ее седловых точек.

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

8. Определить, является ли заданная целочисленная квадратная матрица размером N ортонормированной, т.е. такой, в которой скалярное произведение каждой пары различных строк равно 0, а скалярное произведение каждой строки на себя равно 1.

9. Определить, является ли заданная матрица N-го порядка магическим квадратом, т.е. такой, в которой сумма элементов во всех строках и столбцах одинакова.

10. Дана целочисленная матрица размером N. Найти сумму наименьших элементов ее нечетных строк и наибольших элементов ее четных строк.

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

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

13. Дана квадратная целочисленная матрица порядка N. Упорядочить элементы в строках по возрастанию.

14. Дана действительная квадратная матрица порядка N. Найти сумму и произведение элементов, расположенных в заштрихованной части матрицы, см. рисунок «а».

15. То же, см. рисунок «б».

16. То же, см. рисунок «в».

17. Дана действительная квадратная матрица порядка N. Найти наименьшее и наибольшее из значений элементов, расположенных в заштрихованной части матрицы, см. рисунок «а».

 

 

 

 

а б в

 

18. То же, см. рисунок «б».

19. То же, см. рисунок «в».

20. Получить целочисленную квадратную матрицу порядка N, элементами которой являются числа 1, 2, 3, …, расположенные в ней по спирали.

 

Контрольные вопросы

 

1. Укажите способы декларирования двухмерных массивов.

2. Формы (способы) работы с элементами двухмерного массива.

3. Что такое указатель?

4. Операция sizeof().

ЛАБОРАТОРНАЯ РАБОТА № 5