Массивы

Указатели

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

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

Оперативная память состоит из ячеек, которые идентифицируются по их адресам. Адреса обычно 16-ричные числа. Их можно хранить как значения переменных. Эти переменные, содержащие адреса ячеек с другими переменными, тоже хранятся в ячейках памяти. Переменная, значение которой указывает, по какому адресу находятся данные, называется указателем.

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

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

В программировании используются массивы. Они состоят из однотипных переменных. Количество переменных известно заранее при объявлении массива. Каждая переменная занимает одинаковое количество ячеек памяти, так как переменные однотипные. Следовательно, если записать элементы массива подряд в память, то начало каждого следующего элемента будет отстоять от начала предыдущего на Х ячеек. Тогда элемент номер К будет отстоять от начала массива на Х*(К-1) ячеек памяти.

Таким образом, если указатель на массив содержит адрес начала массива, то есть адрес ячейки, в которой начинается первый элемент массива, то адрес ячейки, в которой начинается К-й элемент массива, будет отстоять от адреса начала массива на Х*(К-1) ячеек памяти.

При объявлении большого количества отдельных, но однотипных переменных для них выделяются ячейки в памяти для хранения их значений. При этом каждой переменной соответствует адрес. Хранение этого адреса также занимает место в памяти. Теоретически, хранение адресов может занимать больше места, чем хранение значений переменных некоторых типов.

Для экономии места в памяти, удобно разместить информацию не в отдельных однотипных переменных, а в массиве, состоящем из соответствующего количества переменных. Тогда для адреса будет выделено место один раз, и там будет храниться адрес начала массива, то есть значение указателя на массив.

Если массив двумерный, например A(n,m), то его можно разместить в памяти в виде непрерывной последовательности элементов, то есть как одномерный из такого же количества элементов. Тогда к элементу A(i,j) компьютер будет обращаться так: от начала массива требуемый элемент отстоит на (i-1)*m+(j-1) элемент, и если каждый элемент занимает Х ячеек памяти, то от значения указателя на массив (от адреса начала первого элемента) требуемый элемент A(i,j) отстоит на Х*((i-1)*m+(j-1)) ячейку. Выражение, позволяющее вычислить адрес нужного элемента массива, называют адресным полиномом.

Массивы, размеры которых определены однозначно, считаются статическими, хотя значения их элементов могут изменяться. Массивы, размеры которых изменяются автоматически (то есть не бывает выхода за пределы массива) считаются динамическими.

При обращении к массиву, фактически программа обращается к ячейке памяти, где хранится указатель на массив. Указатель содержит адрес первой ячейки массива (адрес его первого элемента).