Массивы указателей как структура данных

Массив указателей (МУ) – простейшая структура данных, в которой проявляется различие между физическим и логическим порядком следования элементов. Способ организации данных ясен уже из самого определения: это массив, каждый элемент которого содержит указатель на переменную (объект).

Если это записать в терминах контекстного определения переменных, то получим, например

double *p[20];

Переменную p следует понимать как массив (операция []), каждым элементом которого является указатель на переменную типа double (операция *). Переменная p является массивом указателей как тип данных, но не является таковой как структура данных. Чтобы превратиться в структуру данных, она быть дополнена указуемыми переменными и указателями (связями).

Многообразие вариантов реализации массивов указателей возникает по нескольким причинам:

·cам массив указателей, указуемые переменные и ссылки (указатели) могут быть заданы статически (в тексте программы), либо динамически созданы во время ее выполнения;

·двоякая интерпретация указателя как указателя на отдельную переменную и на массив переменных (строку), позволяет создавать одномерные СД – массивы указателей на переменные и двумерные – массивы указателей на массивы (строки) таких переменных;

·указуемые переменные могут быть «собственностью» структуры данных, однако массив указателей может ссылаться и на переменные (объекты), являющиеся составными частями других структур данных.

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

Типы данных, используемые при работе с массивами указателей

Один тип данных уже был нами упомянут – это массив указателей, переменная вида int *p[]. Кроме нее используется еще одни тип вида int **pp, который можно определить в общем виде какуказатель на указатель.

Многоуровневые указатели.

·Рассмотрим определение переменной:
double **pp;

·В соответствии принципом контекстного определения pp нужно интерпретировать как переменную, при косвенном обращении к которой получается указатель на переменную типа double, то есть как указатель на указатель или адрес указателя.

Но

·Поскольку любой указатель в Си может ссылаться как на отдельную переменную, так и на область памяти (массив), то в применении к двойному указателю получаются 4 вариантаструктур данных, а именно:

1) указатель на одиночный указатель на переменную типа double;
2) указатель на одиночный указатель на массив переменных типа double;
3) указатель на массив, содержащий указатели на одиночные переменные типа double;
4) указатель на массив, содержащий указатели на массивы переменных типа double.

·Третья интерпретация позволяет нам использовать двойной указатель для работы с известными нам массивами указателей следующим образом:
double **pp, *pd[20];
pp = pd; // или pp = & pd[0];
*(pp+i) // или pp[i]
**(pp+i) // или *pp[i]

Здесь повторяется та же самая система эквивалентности обычных массивов и указателей - типов double* и double[], но применительно не к массивам обычных переменных, а к массивам указателей.

Короче говоря, типы double** и double *[] различаются так же, как указатель-переменная и указатель-константа.

·Массив указателей типа double *[] является статической структурой данных, размерность которой определяется при трансляции. Двойной указатель типа double** может ссылаться и на динамический массив указателей, который создается во время работы программы под заданную размерность:

double **create(int sz){
double **pp,*q;
int i;// создать динамический массив указателей размерностью sz+1
pp = (double **)malloc(sizeof(double *)*(sz+1));
for (i=0; i< sz; i++){ // создать динамическую переменную
q = (double *)malloc(sizeof(double));
*q = i;
pp[i] = q; // указатель занести в динамический массив}
pp[sz] = NULL;
return(pp); // возвратить указатель на динамический массив указателей}

Динамические матрицы.

Статические массивы, аля int a[3]={3,5,7}, хороши своей простотой. Но бывают случаи, когда "статика" массивов мешает. Например, Вы хотите написать программу перемножения матриц любых порядков. Вот тут статический массив не просто мешает - его применение здесь практически невозможно! Итак, встречайте - динамический массив!

Что же это такое? Это когда Вы во время работы своей программы (а не во время разработки) можете менять размеренность массивов. И начнем мы с одномерных (векторных) массивов.

int x = 5; // тут задается "длина" массива (при заданном значении нам доступно 5 элементов int)
int *arr = new int[x]; // это создание
// а это проверка
arr[0]=1347;
arr[4]=-124;
cout << arr[0] << endl << arr[4] << endl;

Освобождение памяти (или удаление, что не совсем точно) производиться так:

delete[]arr;

Двумерные (матричные) массивы создаются немногим сложнее:

int x = 5;
int y = 5;
/* размеры масива */
int **arr = new int*[x];
for(int i=0;i<x;i++) arr[i]=new int[y];

"Удаление" производиться так:

for(int i=0;i<x;i++) delete[]arr[i];
delete[]arr;

Передача параметров функции main.