2. Статические структуры данных. Их представление, выделение памяти, привести пример.

Различают два способа распределения памяти:

 - статическое – во время трансляции программы, что эффективно, поскольку в ходе выполнения программы на управление памятью не расходуется ни время, ни память;

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

Динамическая память широко используется при работе с графическими и звуковыми средствами компьютера.

 Значением указателя является адрес области памяти, содержащей переменную заранее определенного типа. В этом случае указатели называются типизированными.

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

Для указателей область памяти выделяется статически, а для переменных, на которые они указывают, – динамически. Адреса задаются совокупностью двух 16-разрядных слов, которые называются сегментом и смещением. Сегмент – это участок памяти, имеющий длину 64 Кбайт и начинающийся с адреса, кратного 16. Смещение указывает, сколько байт от начала сегмента необходимо пропустить, чтобы обратиться к нужному адресу. В результате, абсолютный адрес образуется: сегмент*16+смещение.

При решении прикладных задач, с использованием языков высокого уровня, наиболее частые случаи, когда могут понадобиться указатели, следующие:

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

2) При работе с динамическими структурами данных. Память под них выделяется в ходе выполнения программы, стандартные процедуры/функции выделения памяти возвращают адрес выделенной области памяти, т.е. указатель на нее. К содержимому динамически выделенной области памяти можно обращаться только через такой указатель.

При объявлении типизированного указателя определяется и тип объекта в памяти, адресуемого этим указателем. Для объявления переменных используется символ « ^», после которого указывается тип динамической (базовой) переменной.

Представление указателей. Операции над указателями.

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

Операция получения адреса – одноместная, ее операнд может иметь любой тип, результатом является типизированный (в соответствии с типом операнда) указатель, содержащий адрес объекта-операнда.

Операция выборки – одноместная, ее операндом является типизированный указатель, результат – данные, выбранные из памяти по адресу, заданному операндом. Тип результата определяется типом указателя-операнда.

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

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

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

Операции адресной арифметики выполняются только над типизированными указателями. Единицей измерения в адресной арифметике является размер объекта, который указателем адресуется. Так, если переменная x определена как указатель на целое число, то выражение x+1 даст адрес, больший не на 1, а на количество байт в целом числе. Вычитание указателей также дает в результате не количество байт, а количество объектов данного типа, помещающихся в памяти между двумя адресами. Это справедливо как для указателей на простые типы, так и для указателей на сложные объекты, размеры которых составляют десятки, сотни и более байт.

ХЕШИРОВАНИЕ ДАННЫХ

Открытое хеширование

Закрытое хеширование