Лабораторная работа №4 разработка и спецификация структур данных, использование указателей и динамических массивов структур

Цель работы – освоение на практике методов разработки и спецификации данных и основных приемов работы в С++ с указателями и динамическими структурами данных.

Задание

1. Разработать на языке С++ 3-ю версию консольного приложение для хранения и отображения сведений об объектах некоторого вида (варианты указаны в работе №2).

2. Изменить способ хранения данных в памяти. Хранение данных в оперативной памяти организовать в виде динамического массива структур.

3. Разработать функции, включенные во 2-ю версию в виде заглушек:

   1. Поиск и редактирование записей в массиве.

   2. Сортировка данных в массиве по любому элементу структуры.

4. Сравнить варианты реализации во 2 и 3 версиях программы, сделать вывод.

Краткая теория

Указатели

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

В выражениях операция * используется для разадресации, то есть выборки содержимого по адресу. Существует обратная операция & взятия адреса. Присвоение указателю адреса какой-либо другой переменной позволяет полу­чить ее значение путем разадресации указателя (*р).

double v,*p;

*p=10.0;

v = *p + 2;

p=&v;

После выполнения оператора указатель р содержит адрес пере­менной v, который компилятор определил для хранения значений этой локаль­ной переменной.

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

р = new int;

присваивает переменной р адрес начала области памяти длиной в один элемент типа int. Память выделяется динамически из специальной области центрального пула памяти, которая называется heap. Эле­мент занимает sizeof(int) байт. Операция sizeof(arg) возвращает размер в бай­тах своего аргумента arg, который может быть либо типом, либо выражением.

Операция delete освобождает ранее занятую память, возвращая ее в heap. Сам указатель при этом продолжает указывать на тот же участок памяти, но он больше ею не управляет. При освобождении памяти нет необходимости явно указывать ее размер, так как эту информацию сохраняет система при реализации операции new. Если программист забывает освободить память, то это остается незамеченным в небольших программах, однако часто приводит к отказам в достаточно серьезных разработках и является плохим стилем программирования.

В языке C++ имеется возможность инициализировать указатель путем запро­са памяти прямо в момент объявления переменной. Например,

float *р = new float[n]; // Инициализация указателя р

Эту же операцию можно было бы выпол­нить в два этапа.

float *р; // Объявление указателя р р = new float [n]; // Присвоение указателю р

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

Указатели, объявленные вне функций или объявленные с описателем static, автоматически инициализируются нулями, как и все глобальные переменные в C++. Указатели, объявленные внутри функции (автоматические переменные), не инициализированы вовсе. Использование такого указателя до присвоения ему осмысленного значения является серьезной ошибкой. Нулевой адрес (NULL или 0) служит признаком того, что указатель еще не был инициализирован программистом. NULL — это символическая константа, определенная в stdio.h для нулевого указа­теля.

При объявлении указателя задается тип переменных, на которые он может ука­зывать, так как с указа­телями связана адресная арифметика, правила которой различны для разных типов указателей. Так, если к указателю на тип int прибавить единицу, то его значение изменится на 4 байта или sizeof(int). При увели­чении указателя на массив объектов какой-либо структуры (например, Man) указатель сдвинется в памяти ровно на один объект структуры.

Указатели и статические массивы

Имя массива в языке С фактически является указателем на первый его эле­мент, который соответствует нулевому значению индекса (или индексов в слу­чае многомерных массивов). Если объявлен массив float a[16];, то справедливо равенство а = = &а[0]. Переменные типа «указатель» могут быть использованы и часто используются для доступа к элементам массива. Имеют смысл следующие присвоения:

float a[16],*p: // Объявление массива и указателя for (int i=0; i<16; i++)

a[i]=float(i*i); //Заполнение массива p = &а[6]; //p указывает на а[6] *р = 3.14f; // Равносильно а[6] = 3.14; p++; // Теперь р указывает на а[7]. Произошел сдвиг на 4 байта а[1] = *(р+3); // Равносильно а[1] = а[10]; В а[1] попадает 100 а[2] = ++*р; //Равносильно а[2] = ++а[7]; В а[2] попадает 50 а[3] = *++р; //Равносильно а[3] = а[8]; В а[3] попадает 64

Адресная арифметика, например р+3 или ++р, осуществляется в единицах объяв­ленного базового типа данных float. Если в конкретной вычислительной систе­ме число типа float занимает 4 байта, то результатом операции р+3 будет адрес, отстоящий от р на 12 байтов. Значение ++*р вычисляется так: сначала выбирает­ся (*р) — содержимое по адресу р, то есть а[7], так как в данный момент указа­тель содержит &а[7]. Затем выполняется приращение (increment) a[7], то есть увеличение а[7] на единицу. При вычислении *++р, наоборот, сначала произво­дится изменение указателя (++р), потом выборка содержимого по адресу, на ко­торый он указывает.

Рассмотрим теперь двухмерный массив int a[2][3];. Встретив описание такого типа, компилятор отводит в памяти место для линейного размещения мас­сива в виде последовательности ячеек.

1-й эл-т 1-й строки			Посл. эл-т 1-й строки	1-й эл-т 2-й строки			Посл. эл-т посл. строки
а[0][0]	а[0][1]	…	а[0][2]	а[1][0]	а[1][1]	…	а[1][2]

Двухмерный массив рассматривается как массив массивов. Элементами глав­ного массива из двух элементов являются одномерные массивы, каждый из трех элементов типа int*. В языке имеют смысл такие объекты:

• а[0][0] — первый элемент массива типа int;

• а[0] — адрес первого элемента массива типа int*;

• а — адрес первой строки массива типа int**.

Выражение а+1 означает адрес второй строки массива, то есть адрес, сдвину­тый на один элемент массива массивов, а таким элементом является строка двух­мерного массива.

Выражение а+1 подразумевает сдвиг от а на размер одной строки (а не на размер числа типа int). Адресная арифметика всегда осуществ­ляется в единицах базового типа данных. Теперь такой единицей является стро­ка двухмерного массива или массив целых из трех элементов. Имеют место сле­дующие равенства:

а= =&а[0] а[0]= =&а[0][0] **а= = а[0][0].

Так как а является адресом адреса, то понадобилась двойная разадресация (**а) для того, чтобы до­браться до первого элемента массива.

Указатели и динамические массивы

При решении на компьютере серьезных задач важно экономно расходовать имеющуюся память и освобождать ее по мере возможности. Прин­цип организации динамического двухмерного массива очень похож на принцип организации статическо­го двухмерного массива. Отличие состоит в том, что теперь для адресов а, а[0], а[1],..., а[n-1] должно быть отведено реальное физическое пространство памя­ти, в то время как для статического двухмерного массива выражения вида а, а[0], а[1],..., а[n-1] были лишь возможными конструкциями для ссылок на ре­ально существующие элементы массива, но сами эти указатели не существовали как объекты в памяти компьютера.

Алгоритм выделения памяти таков:

• Определяем переменную а как адрес массива адресов: float **a;.

• Захватываем память из области heap для массива из n указателей на тип float и присваиваем адрес начала этой памяти указателю а. Оператор, вы­полняющий это действие, выглядит так:

а = new float* [n];.

• В цикле пробегаем по массиву адресов а[], присваивая каждому указателю а[i] адрес вновь захватываемой памяти под массив из n чисел типа float (a[i]=new float [m];).

Если был размещен массив переменных, то следует освобождать память оператором

delete [] р;.

Здесь квадратные скобки указывают компилятору на то, что освобождать следу­ет то количество ячеек, которое было захвачено последней операцией new в при­менении к указателю р. Явно указывать это число не нужно.