4.5. Агрегатные типы данных

Кроме рассмотренных ранее стандартных типов данных язык С++ позволяет создавать дополнительные агрегатные типы данных:

– массивы;

– структуры (structure);

– объединения (union);

– поля битов (bit fields);

– перечисления или перечислимый тип (enumeration);

– с помощью оператора typedef .

4.5.1. Массивы

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

<тип> <имя массива> [n1] [n2]…

где n1, n2 – размер массива по данному измерению.

Элемент массива представляет собой индексированную переменную , индекс которой указывается в квадратных скобках. Индекс может быть целой константой, целой переменной или выражением целого типа. Все массивы индексируются с нуля.

Массивы подобно переменным могут быть инициализированы начальными значениями, например.

float a[3]={1.2, 3.4, -0.1};

где a[0]=1.2, a[1]=3.4, a[2]=-0.1.

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

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

При работе с массивами выделяют следующие типовые операции:

1. Заполнение массива возможно либо с помощью генератора случайных чисел (random()), либо с клавиатуры, либо по определенному правилу.

Пример.

for (i=0; i<n; i++)

for (j=0; j<n; j++)

cin>> a [i][j];

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

Рис. 2. Принятое деление матрицы на четверти

Условия нахождения элементов в каждой из частей матрицы следующие:

• I: (i<j) && (i+j<n-1)

• II: (i<j) && (i+j>n-1)

• III: (i>j) && (i+j>n-1)

• IV: (i>j) && (i+j<n-1)

• на главной диагонали: i = = j

• на побочной диагонали: i+j = = n-1

где i – номер строки, j – номер столбца, в которых находится элемент матрицы, n – размерность квадратной матрицы.

2. Вычисление суммы, произведения, среднего арифметического, среднего геометрического, количества элементов, удовлетворяющих некоторому условию.

Пример. Вычислить сумму положительных элементов матрицы и количество отрицательных элементов.

for (i=0; i<n; i++)

for (j=0; j<n; j++)

{if a[i][j]>0 s+=a[i][j];

else k++;

}

3. Сортировка массива

Можно выделить пять типов алгоритмов сортировки:

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

• вставками – отдельно анализируется каждый конкретный элемент, который затем помещается на надлежащее ему место среди других, уже отсортированных элементов;

• выбором – сначала отыскивается наименьший элемент массива, затем он меняется местами с элементом, стоящим первым в сортируемом массиве, и т.д.;

• слиянием – сортируемый файл, расположенный во внешней памяти, разбивается на части, которые могут быть считаны в память, отсортированы каким-либо методом и записаны в отдельные временные файлы. Затем отсортированные временные файлы сливаются попарно с сохранением порядка сортировки. И так до тех пор, пока все временные файлы не будут объединены в один отсортированный файл;

• деревом – сортируемые элементы добавляются в бинарное дерево. Отсортированный массив формируется путем концевого обхода построенного дерева.

Основной характеристикой алгоритма сортировки является время, затраченное на его выполнение. Так, для массива из N элементов:

• сортировка выбором производит в среднем N^2 / 2 операций сравнения и операций обмена;

• сортировка вставками – в среднем N^2 / 4 сравнений и N^2 / 4 операций полуобмена (перемещений) и в два раза больше в наихудшем случае;

• сортировка обменом (метод пузырька) – N^2 / 2 операций сравнения и N^2 / 2 обменов как в среднем, так и наихудшем случае;

• сортировка деревом – N * log₂ (N) операций сравнения и N операций вставки.

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

Шаги алгоритма:

1. находим минимальное значение в текущем списке;

2. производим обмен этого значения со значением на первой позиции;

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

Будем строить выходную последовательность, начиная с левого конца массива. Алгоритм состоит из n последовательных шагов, начиная с нулевого и заканчивая (n-1)-м.

На i-м шаге выбираем наименьший из элементов x[i] ... x[n] и меняем его местами с x[i]. Последовательность шагов при n=5 изображена на рис. 2.

Рис. 2. Сортировка выбором

Вне зависимости от номера текущего шага i, последовательность x[0]...x[i] (выделена курсивом) является упорядоченной. Таким образом, на (n-1)-м шаге вся последовательность, кроме x[n], оказывается отсортированной, а x[n] стоит на последнем месте по праву: все меньшие элементы уже ушли влево.

Пример программной реализации.

for (i = 0; i < n-1; i++) {

min = i;

for (j = i+1; j < n; j++) {

if (x[min] > x[j]) { // сортировка по убыванию

min = j;

}

}

temp = x[i];

x[i] = x[min];

x[min] = temp;

}

4. Вставка и удаление элементов массива

Удаление одного элемента из массива происходит по следующей схеме:

- указывается или ищется порядковый номер элемента, который необходимо удалить из массива;

- все элементы, стоящие за удаляемым элементом, сдвигаются на одну позицию влево;

- количество элементов уменьшается на единицу.

for (i=0; i<n; i++) // n – номер удаляемого элемента

a[j]=a[j+1];

k-=1; // количество элементов