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

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

Цель работы:

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

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

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

<тип><имя>[<размер 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