Динамические структуры данных

двух видов:
с использованием указателя типа void *
без его

использования.
В языке С допускается присваивание указателя типа void * указателю любого другого типа (и наоборот) без явного преобразования типа указателя
Тип указателя void * используется, если тип объекта неизвестен. Например, использование типа void * в качестве параметра функции позволяет передавать в функцию указатель на объект любого типа, при этом сообщение об ошибке не генерируется. Также он полезен для ссылки на произвольный участок памяти, независимо от размещенных там объектов. Например, функция размещения malloc()возвращает значение типа void *, что позволяет использовать ее для размещения в памяти объектов любого типа.

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

*)
В языке C++ требуется явно указывать преобразование типа указателей, в том числе указателей типа void *.

может вызвать непредсказуемое поведение программы.
#include
int main(void)
{
double x =

100.1, y;
int *p;
/* В следующем операторе указателю на целое p
присваивается значение, ссылающееся на double. */
p = (int *) &x;
/* Следующий оператор работает не так, как ожидается. */
y = *p; /* attempt to assign y the value x through p */
/* Следующий оператор не выведет число 100.1. */
printf("Значение x равно: %f (Это не так!)", y);
return 0;
}

указателями:
суммирование
вычитание
Предположим, текущее значение указателя p1 типа int * равно

2000.
Предположим также, что переменная типа int занимает в памяти 2 байта.
Тогда после операции увеличения
p1++;
указатель p1 принимает значение 2002, а не 2001. То есть, при увеличении на 1 указатель p1 будет ссылаться на следующее целое число. Это же справедливо и для операции уменьшения. Например, если p1 равно 2000, то после выполнения оператора
p1--;
значение p1 будет равно 1998.
Операции адресной арифметики подчиняются следующим правилам. После выполнения операции увеличения над указателем, данный указатель будет ссылаться на следующий объект своего базового типа. После выполнения операции уменьшения — на предыдущий объект

обычные арифметические операции, потому что длина объекта char всегда равна

1. Для всех указателей адрес увеличивается или уменьшается на величину, равную размеру объекта того типа, на который они указывают. Поэтому указатель всегда ссылается на объект с типом, тождественным базовому типу указателя. На рисунке приведен пример размещения в памяти переменных char (слева) и int (справа) (предполагается, что длина целочисленной переменной равна 2 байтам).

целые числа. Выполнение оператора
p1 = p1 + 12;
"передвигает" указатель

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

два указателя р и q, то следующий оператор является правильным:

if(p < q) printf("p ссылается на меньший адрес, чем q\n");
Однако, сравнение указателей может оказаться полезным, только тогда, когда два указателя ссылаются на общий объект, например, на массив.

программы:
char str[80], *p1;
p1 = str;
Имя массива без индекса возвращает

адрес первого элемента массива. Поэтому здесь p1 указывает на первый элемент массива str. Обратиться к пятому элементу массива str можно с помощью любого из двух выражений:
str[4]
или
* (p1+4)

к элементу массива:
адресная арифметика
индексация массива
Стандартная запись массивов с индексами

наглядна и удобна в использовании, однако с помощью адресной арифметики иногда удается сократить время доступа к элементам массива. Поэтому адресная арифметика часто используется в программах, где существенную роль играет быстродействие.
/* Индексация указателя s как массива. */
void putstr(char *s) {
register int t;
for(t=0; s[t]; ++t) putchar(s[t]);
}
/* Использование адресной арифметики. */
void putstr(char *s) {
while(*s) putchar(*s++);
}

10
 int main(void) {
int mass[SIZE], *p, *first,*max, *i; first=mass;
for (p=first;

pp=mass; max=first;
while (p if (*p>*max) max=p;
p++;
}
printf("max = %d", *max);
 for (p=first; pprintf("%d ", *p);
 getch();
return 0;
}

на двухмерный массив целых размерностью 10×10, то следующие два выражения

эквивалентны:
a == &a[0][0]
Более того, к элементу (0,4) можно обратиться двумя способами:
либо указав индексы массива: а[0][4],
либо с помощью указателя: *((int*)а+4).
Аналогично для элемента (1,2): а[1][2] или *((int*)а+12).
В общем виде для двухмерного массива справедлива следующая формула:
a[j][k] эквивалентно *((базовый_тип*)а+(j*кол-во_столбцов)+k)
Правила адресной арифметики требуют явного преобразования указателя на массив в указатель на базовый тип

массив. В следующем операторе объявлен массив из 10 указателей на

объекты типа int:
int *x[10];
Для присвоения, например, адреса переменной var третьему элементу массива указателей, необходимо написать:
x[2] = &var;
В результате этой операции, следующее выражение принимает то же значение, что и var:
*x[2]
Для передачи массива указателей в функцию используется тот же метод, что и для любого другого массива: имя массива без индекса записывается как формальный параметр функции.
Например, следующая функция может принять массив x в качестве аргумента:
void display_array(int *q[])
{
int t;
for(t=0; t<10; t++)
printf("%d ", *q[t]);
}
Необходимо помнить, что q – это не указатель на целые, а указатель на массив указателей на целые.

работают с указателями. Рассмотрим, например, приведенную ниже бесполезную, но поучительную

программу:
/* Указатели и строки */
#include
#include
#define PX(X) printf("X = %s; значение = %u; &X = %u\n",X,X,&X)
void main( )
{SetConsoleCP(1251);
SetConsoleOutputCP(1251);
static char *mesg = "Сообщение";
static char *copy;
copy = mesg;
printf("%s\n",copy);
PX(mesg);
PX(copy);
}

]="Я люблю язык Cи!";
char *head = "Я люблю язык Pascal!";
Основное

отличие состоит в том, что указатель heart является константой, в то время как указатель head - переменной. Посмотрим, что на самом деле дает эта разница.
Во-первых, и в том и в другом случае можно использовать операцию сложения с указателем:
for(i=0;i<7;i++)
putchar(* (heart+i));
putchar('\n');
for(i=0;i<7;i++)
putchar(* (head+i));
putchar('\n');
В результате получаем:
Я люблю
Я люблю

'\0') /* останов в конце строки */
putchar(*(head++)); /* печать символа и перемещение

указателя */
В результате получаем:
Я люблю язык Pascal!

теперь head указывает на массив heart */
но теперь можно и

так
heart = head; /* запрещенная конструкция */
Ситуация аналогична x = 5 или 5 = x. Левая часть оператора присваивания должна быть именем переменной. В данном случае head = heart, не уничтожит строку про язык Cи, а только изменит адрес, записанный в head.

в сам массив:
heart[13] = 'C';
или
*(heart+8)='C';
Обратите внимание, переменными являются элементы массива,

но не имя!

функцию, выводящую нужную строку с сообщением об ошибке по индексу

num:
void syntax_error(int num)
{
static char *err[] = {
"Нельзя открыть файл\n",
"Ошибка при чтении\n",
"Ошибка при записи\n",
"Некачественный носитель\n"
};
printf("%s", err[num]);
}
Массив err содержит указатели на строки с сообщениями об ошибках. Здесь строковые константы в выражении инициализации создают указатели на строки. Аргументом функции printf() служит один из указателей массива err, который в соответствии с индексом num указывает на нужную строку с сообщением об ошибке. Например, если в функцию syntax_error() передается num со значением 2, то выводится сообщение Ошибка при записи.

данных во время своего выполнения
Память для глобальных переменных выделяется во

время компиляции, а для нестатических локальных переменных – в стеке
Во время выполнения программы ни глобальным, ни локальным переменным не может быть выделена дополнительная память. Но довольно часто такая необходимость возникает, причем объем требуемой памяти заранее неизвестен
Такое случается, например, при использовании динамических структур данных, таких как связные списки или двоичные деревья. Такие структуры данных при выполнении программы расширяются или сокращаются по мере необходимости. Для реализации таких структур в программе нужны средства, способные по мере необходимости выделять и освобождать для них память.

т.н. куче – динамически распределяемой области памяти (heap)
Динамически распределяемая область

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

free() освобождает участок памяти, то есть возвращает системе
В программу,

использующую эти функции, должен быть включен заголовочный файл
Прототип функции malloc() следующий:
void *malloc(size_t количество_байтов);
количество_байтов — размер памяти, необходимой для размещения данных
тип size_t определен в как некоторый целый без знака
Функция malloc() возвращает указатель типа void *, поэтому его можно присвоить указателю любого типа
При успешном выполнении malloc() возвращает указатель на первый байт непрерывного участка памяти, выделенного в динамически распределяемой области памяти
Если в динамически распределяемой области памяти недостаточно свободной памяти для выполнения запроса, то память не выделяется и malloc() возвращает нуль

malloc(1000); /* выделение 1000 байтов */
 
В C++ нужно преобразовывать типы

указателей явно. Для этого строчку, в которой указателю р присваивается это значение, нужно переписать следующим образом:
char *p;
p = (char*) malloc(1000); /* выделение 1000 байтов */
 После присвоения указатель p ссылается на первый из 1000 байтов выделенного участка памяти.
В следующем примере выделяется память для 50 целых. Для повышения мобильности (переносимости программы с одной машины на другую) используется оператор sizeof.
int *p;
p = malloc(50*sizeof(int));

выделить требуемый участок памяти, то она возвращает нуль
p = malloc(100);
if(!p)

{
printf("Нехватка памяти.\n");
exit(1);
}
Конечно, вместо выхода из программы exit() можно поставить какой-либо обработчик ошибки

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

функции malloc().
Функция free() имеет следующий прототип:
void free(void *p)
Здесь р — указатель на участок памяти, выделенный перед этим функцией malloc()
Функцию free() ни в коем случае нельзя вызывать с неправильным аргументом, это мгновенно разрушит всю систему распределения памяти

register int t;
s= (char*)malloc(80); // указателю присваивает адрес первой

ячейки памяти, выделенной для хранения 80 байт информации
if(!s) {
printf("Требуемая память не выделена.\n");
exit(1);
}
gets(s);
for(t=strlen(s)-1; t>=0; t--) putchar(s[t]);
free(s);
getch();
return 0;
}

b);
 
int main(void)
{
/* Объявление указателя на массив из 10 строк

в которых хранятсяцелые числа (int). */
int (*p)[10];
 
register int i, j;
 
/* выделение памяти для массива 4 x 10 */
p = (int(*)[10]) malloc(40*sizeof(int));
 
if(!p) {
printf("Требуемая память не выделена.\n");
exit(1);
}
 
for(j=1; j<11; j++)
for(i=1; i<5; i++) p[i-1][j-1] = pwr(j, i);
 
for(j=1; j<11; j++) {
for(i=1; i<5; i++) printf("%10d ", p[i-1][j-1]);
printf("\n");
}
getch();
return 0;
}
 
/* Возведение чисел в степень. */
int pwr(int a, int b)
{
register int t=1;
 
for(; b; b--) t = t*a;
return t;
}

отметить, что скобки вокруг *р обязательны
Такое объявление означает, что р

указывает на массив из 10 целых. Если увеличить указатель р на 1, то он будет указывать на следующие 10 целых чисел
Таким образом, р – это указатель на двухмерный массив с 10 числами в каждой строке. Поэтому р можно индексировать как обычный двухмерный массив. Разница только в том, что здесь память выделена с помощью malloc(), а для обыкновенного массива память выделяет компилятор

памяти new и delete
указатель = new тип;
delete указатель;
Пример
Выделение памяти под

переменную целого типа
int *p;
p=new int;
delete p;
Выделение под массив целых чисел
int *p;
p=new int [10];
delete [] p;