Радиоконструктор

0

Язык C, Часть 24

Двухмерные массивы

Стандартом С определены многомерные массивы. Простейшая форма многомерного массива — двухмерный массив. Двухмерный массив — это массив одномерных массивов. Объявление двухмерного массива d с размерами 10 на 20 выглядит следующим образом: 
int d[10][20];
Во многих языках измерения массива отделяются друг от друга запятой. В языке С каждое измерение заключено в свои квадратные скобки.
Аналогично обращению к элементу одномерного массива, обращение к элементу с индексами 1 и 2 двухмерного массива d выглядит так: 
d[1][2]
 
 
В следующем примере элементам двухмерного массива присваиваются числа от 1 до 12 и значения элементов выводятся на экран построчно: 
#include <stdio.h>

int main(void)
{
  int t, i, num[3][4];

  for(t=0; t<3; ++t)
    for(i=0; i<4; ++i)
      num[t][i] = (t*4)+i+1;

  /* вывод на экран */
  for(t=0; t<3; ++t) {
    for(i=0; i<4; ++i)
      printf("%3d ", num[t][i]);
    printf("\n");
  }

  return 0;
}
В этом примере num[0][0] имеет значение 1, num[0][1] — значение 2, num[0][2] — значение 3 и так далее. Наглядно двухмерный массив num можно представить так: 
num[t][i]
      | 0  1  2  3
    --+----------- 
    0 | 1  2  3  4
    2 | 5  6  7  8
    3 | 9  10 11 12
Двухмерные массивы размещаются в матрице, состоящей из строк и столбцов. Первый индекс указывает номер строки, а второй — номер столбца. Это значит, что когда к элементам массива обращаются в том порядке, в котором они размещены в памяти, правый индекс изменяется быстрее, чем левый. На рис. 4.2 показано графическое представление двухмерного массива в памяти.
Рис. 4.2. Двухмерные массивы 
            Объявление массива char ch[3][4]

        Правый индекс определяет номер столбца
                   |          |          |
   о               V          V          V
   п      +----------+----------+----------+
Л  р    ->|ch [0] [0]|ch [0] [1]|ch [0] [2]|
е  е      +----------+----------+----------+
в  д
ы  е      +----------+----------+----------+
й  л  с ->|ch [1] [0]|ch [1] [1]|ch [1] [2]|
   я  т   +----------+----------+----------+
и  е  р
н  т  о   +----------+----------+----------+
д     к ->|ch [2] [0]|ch [2] [1]|ch [2] [2]|
е  н  и   +----------+----------+----------+
к  о
с  м      +----------+----------+----------+
   е    ->|ch [3] [0]|ch [3] [1]|ch [3] [2]|
   р      +----------+----------+----------+
Объем памяти в байтах, занимаемый двухмерным массивом, вычисляется по следующей формуле: 
количество_байтов =
= размер_1-го_измерения × размер_2-го_измерения × sizeof(базовый_тип)
Например, двухмерный массив 4-байтовых целых чисел размерностью 10×5 занимает участок памяти объемом 
10×5×4
то есть 200 байтов.
Если двухмерный массив используется в качестве аргумента функции, то в нее передается только указатель на начальный элемент массива. В соответствующем параметре функции, получающем двухмерный массив, обязательно должен быть указан размер правого измерения[1], который равен длине строки массива. Размер левого измерения указывать не обязательно. Размер правого измерения необходим компилятору для того, чтобы внутри функции правильно вычислить адрес элемента массива, так как для этого компилятор должен знать длину строки массива. Например, функция, получающая двухмерный массив целых размерностью 10×10, должна быть объявлена так: 
void func1(int x[][10])
{
  /* ... */
}
Компилятор должен знать длину строки массива, чтобы внутри функции правильно вычислить адрес элемента массива. Если при компиляции функции это неизвестно, то невозможно определить, где начинается следующая строка, и вычислить, например, адрес элемента 
x[2][4]
В следующем примере двухмерные массивы используются для хранения оценок студентов. Предполагается, что преподаватель ведет три класса, в каждом из которых учится не более 30 студентов. Обратите внимание на то, как происходит обращение к массиву grade в каждой функции. 
/* Простая база данных оценок студентов. */
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>

#define CLASSES  3
#define GRADES  30

int grade[CLASSES][GRADES];

void enter_grades(void);
int get_grade(int num);
void disp_grades(int g[][GRADES]);

int main(void)
{
  char ch, str[80];

  for(;;) {
    do {
      printf("(В)вод оценок студентов\n");
      printf("В(ы)вод оценок студентов\n");
      printf("Вы(х)од\n");
      gets(str);
      ch = toupper(*str);
    } while(ch!='В' && ch!='ы' && ch!='х');

    switch(ch) {
      case 'В':
        enter_grades();
        break;
      case 'ы':
        disp_grades(grade);
        break;
      case 'х':
        exit(0);
    }
  }

  return 0;
} 

/* Занесение оценок студентов в массив. */
void enter_grades(void)
{
  int t, i;

  for(t=0; t<CLASSES; t++) {
    printf("Класс № %d:\n", t+1);
    for(i=0; i<GRADES; ++i)
      grade[t][i] = get_grade(i);
  }
}

/* Ввод оценок. */
int get_grade(int num)
{
  char s[80];

  printf("Введите оценку студента № %d:\n", num+1);
  gets(s);
  return(atoi(s));
}

/* Вывод оценок. */
void disp_grades(int g[][GRADES])
{
  int t, i;

  for(t=0; t<CLASSES; ++t) {
    printf("Класс № %d:\n", t+1);
    for(i=0; i<GRADES; ++i)
      printf("Студент № %d имеет оценку %d\n", i+1, g[t][i]);
  }
}

Массивы строк

В программах на языке С часто используются массивы строк. Например, сервер базы данных сверяет команды пользователей с массивом допустимых команд. В качестве массива строк в языке С служит двухмерный символьный массив. Размер левого измерения определяет количество строк, а правого — максимальную длину каждой строки. Например, в следующем операторе объявлен массив из 30 строк с максимальной длиной 79 символов: 
char str_array[30][80];
Чтобы обратиться к отдельной строке массива, нужно указать только левый индекс. Например, вызов функции gets() с третьей строкой массива str_array в качестве аргумента можно записать так: 
gets(str_array[2]);
Этот оператор эквивалентен следующему: 
gets(&str_array[2][0]);
Из этих двух форм записи предпочтительной является первая.
Для лучшего понимания свойств массива строк рассмотрим следующую короткую программу, в которой на основе применения массива строк создан простой текстовый редактор: 
/* Очень простой текстовый редактор. */
#include <stdio.h>

#define MAX 100
#define LEN 80

char text[MAX][LEN];

int main(void)
{
  register int t, i, j;

  printf("Для выхода введите пустую строку.\n");

  for(t=0; t<MAX; t++) {
    printf("%d: ", t);
    gets(text[t]);
    if(!*text[t]) break; /* выход по пустой строке */
  }

  for(i=0; i<t; i++) {
    for(j=0; text[i][j]; j++) putchar(text[i][j]);
    putchar('\n');
  }

  return 0;
}
Пользователь вводит в программу строки текста, заканчивая ввод пустой строкой. Затем программа выводит текст посимвольно.


[1]Размер правого измерения указывать не нужно, если в вызывающей функции массив объявлен как **х и размещен динамически (см. главу 5)

Многомерные массивы

В языке С можно пользоваться массивами, размерность которых больше двух. Общая форма объявления многомерного массива следующая: 
тип имя_массива [Размер1][Размер2]...[РазмерN];
Массивы, у которых число измерений больше трех, используются довольно редко, потому что они занимают большой объем памяти. Например, четырехмерный массив символов размерностью 10x6x9x4 занимает 2160 байтов. Если бы массив содержал 2-байтовые целые, потребовалось бы 4320 байтов. Если бы элементы массива имели тип double, причем каждый элемент (вещественное число двойной точности) занимал бы 8 байтов, то для хранения массива потребовалось бы 17280 байтов. Объем требуемой памяти с ростом числа измерений растет экспоненциально. Например, если к предыдущему массиву добавить пятое измерение, причем его толщину по этому измерению сделать равной всего 10, то его объем возрастет до 172800 байтов.
При обращении к многомерным массивам компьютер много времени затрачивает на вычисление адреса, так как при этом приходится учитывать значение каждого индекса. Поэтому доступ к элементам многомерного массива происходит значительно медленнее, чем к элементам одномерного.
Передавая многомерный массив в функцию, в объявлении параметров функции необходимо указать все размеры измерений, кроме самого левого. Например, если массив m объявлен как 
int m[4] [3] [6] [5];
то функция, принимающая этот массив, должна быть объявлена примерно так: 
void func1(int d[][3][6][5])
{
  /* ... */
}
Конечно, можно включить в объявление и размер 1-го измерения, но это излишне. 

Индексация указателей

Указатели и массивы тесно связаны друг с другом. Имя массива без индекса — это указатель на первый (начальный) элемент массива. Рассмотрим, например, следующий массив: 
char p[10];
Следующие два выражения идентичны: 
p
&p[0]
Выражение 
p == &p[0]
принимает значение ИСТИНА, потому что адрес 1-го элемента массива — это то же самое, что и адрес массива.
Как уже указывалось, имя массива без индекса представляет собой указатель. И наоборот, указатель можно индексировать как массив. Рассмотрим следующий фрагмент программы: 
int *p, i[10];
p = i;
p[5] = 100;  /* в присваении используется индекс */
*(p+5) = 100; /* в присвоении используется адресная арифметика */
Оба оператора присваивания заносят число 100 в 6-й элемент массива i. Первый из них индексирует указатель p, во втором применяются правила адресной арифметики. В обоих случаях получается один и тот же результат. (Подробно указатели и адресная арифметика рассматриваются в главе 5.)
Можно также индексировать указатели на многомерные массивы. Например, если а — это указатель на двухмерный массив целых размерностью 10×10, то следующие два выражения эквивалентны: 
a
&a[0][0]
Более того, к элементу (0,4)[1] можно обратиться двумя способами: либо указав индексы массива: а[0][4], либо с помощью указателя: *((int*)а+4). Аналогично для элемента (1,2): а[1][2] или *((int*)а+12). В общем виде для двухмерного массива справедлива следующая формула: 
a[j][k] эквивалентно *((базовый_тип*)а+(j*длина_строки)+k)
Правила адресной арифметики требуют явного преобразования указателя на массив в указатель на базовый тип (см. главу 5). Указатели используются для обращения к элементам массива потому, что часто операции адресной арифметики выполняются быстрее, чем индексация массива.
Двухмерный массив может быть представлен как указатель на массив одномерных массивов. Добавив еще один указатель, можно с его помощью обращаться к элементам отдельной строки массива. Этот прием демонстрируется в функции pr_row(), которая печатает содержимое конкретной строки двухмерного глобального массива num: 
int num[10][10];

/* ... */

void  pr_row(int j)
{
  int *p, t;

  p = (int *) &num[j][0]; /* вычисление адреса 1-го
                             элемента строки номер j */

  for(t=0; t<10; ++t) printf("%d ", *(p+t));
}
Эту функцию можно обобщить, включив в список аргументов номер строки, длину строки и указатель на 1-й элемент: 
void pr_row(int j, int row_dimension, int *p)
{
  int t; 

  p = p + (j * row_dimension);

  for(t=0; t<row_dimension; ++t)
    printf("%d ", *(p+t));
} 

/* ... */

void f(void)
{
  int num[10][10];

  pr_row(0, 10, (int *) num); /* печать 1-й строки */
}
Такой прием "понижения размерности" годится не только для двухмерных массивов, но и для любых многомерных. Например, вместо того, чтобы работать с трехмерным массивом, можно использовать указатель на двухмерный массив, причем вместо него в свою очередь можно использовать указатель на одномерный массив. В общем случае вместо того, чтобы обращаться к n-мерному массиву, можно работать с указателем на (n-1)-мерный массив. Причем этот процесс понижения размерности кончается на одномерном массиве.


[1]Так обозначается элемент, у которого первая координата равна 0, а вторая — 4.

Комментарии

Отправить комментарий