Массивы
Массивы – это структуры, содержащие связанные друг с другом однотипные элементы данных.
Массивы – это «статические» сущности, они сохраняют свои размеры на протяжении всего времени выполнения программы.
Стеки, списки, очереди, деревья – это динамические структуры данных.
Массив – это последовательная группа ячеек памяти, имеющих одинаковое имя и тип. Чтобы сослаться на отдельную ячейку или элемент массива, мы указываем имя массива и номер позиции отдельного элемента массива.
| a[0] | |
| a[1] | -45 |
| a[2] | |
| a[3] | |
| a[4] | |
| a[5] | |
| a[6] | |
| a[7] |
Массив содержит 8 элементов. На любой элемент массива можно сослаться, указывая имя массива и номер позиции элемента, заключенный в квадратные скобки ([ ]). Первый элемент каждого массива – это нулевой элемент.
Имена массивов должны удовлетворять тем же требованиям, которые предъявляются к другим именам переменных.
Номер позиции, указанный внутри квадратных скобок, называется индексом. Индекс должен быть целым числом или целым выражением. Если программа использует выражение в качестве индекса, то выражение вычисляется с целью определения индекса.
Например,
переменная b=5. а переменная c=2, то оператор
a[b+c] +=2;
добавляет 2 к элементу массива a[7].
Чтобы напечатать сумму значений, содержащихся в первых трех элементах массива a, нужно написать оператор
cout << a[0] + a[1] + a[2] << endl;
Чтобы разделить значение седьмого элемента массива a на 2 и присвоить результат переменной x, нужно написать оператор
x=a[6] / 2;
Квадратные скобки, внутри которых записывается индекс массива, рассматриваются в С++ как операция индексации и имеют тот же уровень старшинства, что и круглые скобки.
| Операции | Ассоциативность | Тип операций |
| () [ ] | слева направо | наивысший |
| + --! (тип) | справа налево | унарные |
| * / % | слева направо | мультипликативные |
| + - | слева направо | аддитивные |
| << >> | слева направо | поместить в /взять из |
| < <= > >= | слева направо | отношение |
| ==!= | слева направо | проверка на равенство |
| && | слева направо | логическое И |
| || | слева направо | логическое ИЛИ |
| ?: | справа налево | условная |
| = + = - = *= /= %= | справа налево | присваивание |
| , | слева направо | запятая (последование) |
Рис. 4.2. Приоритеты и ассоциативность операций
Объявление массивов
Массивы занимают область в памяти. Программист указывает тип каждого элемента, количество элементов, требуемое каждым массивом, и компилятор резервирует соответствующий объем памяти.
Пример:
int a [12]; – массив из 12 элементов.
Память может быть зарезервирована для нескольких массивов с помощью одного объявления.
Пример:
int a [12], b[27];
Массивы могут быть объявлены и для хранения других типов данных. Например, для хранения строки символов можно использовать массив типа char.
Инициализация массивов
Начальные значения могут присваиваться при объявлении массива (с помощью списка, заключенного в фигурные скобки):
int a [3] = {3,5,11}; int a [] = {3,8,54} – можно не указывать размер массива, тогда выделяется столько памяти, сколько начальных значений.
Присваивание начального значения - это инициализация. Если начальных значений меньше, чем элементов в массиве int a [3]={3,89}, то остальные элементы автоматически получают нулевое начальное значение.
Можно присвоить нулевые начальные значения с помощью объявления
int n [10] = {0};
которое явно присваивает нулевое начальное значение первому элементу и неявно присваивает нулевые начальные значения оставшимся девяти элементам.
Задание в списке начальных значений больше, чем задано элементов в массиве, является синтаксической ошибкой.
Например,
int a [5] = {37,57,98,76,45,90}; - синтаксическая ошибка.
Рис.4.5.
Массивы символов.
Хранение строк в массивах символов.
Массиву символов можно задать начальное значение, используя литеральную константу.
Например, объявление
char string1[ ] = “first”;
присваивает элементам массива string1 в качестве начальных значений отдельные символы строки “first”.
Строка “first” содержит пять символов плюс специальный символ окончания строки – нулевой символ.
Нулевой символ – это нулевая константа ‘\0’.
Все строки заканчиваются этим символом.
Можно было задать
char string1 = {‘f’, ‘i’, ‘r’, ‘s’, ‘t,’,’\0’};
Так как строка является массивом символов, то можно получить доступ к отдельным символам строки, используя индексы.
strng1[ 0 ] - это символ ‘f’
strng1[ 3 ] - это символ ‘s’.
Мы можем ввести строку непосредственно в символьный массив с клавиатуры, используя cin и >>.
Например,
char string2 [20];
создает символьный массив из 19 символов и завершающий нулевой символ.
Оператор
cin>>string2;
считывает строку в массив string2.
В данном операторе используется только имя массива и нет никакой информации о его размере.
Программист обязан убедиться в том, что массив, в который записывается строка, способен вместить любую строку, которую пользователь наберет на клавиатуре.
cin считывает символы с клавиатуры до тех пор, пока не встретится первый разделитель в тексте, и при этом не заботится о размерах массива.
Символьный массив, представляющий строку, может быть выведен с помощью cout и <<.
Массив string2 печатается оператором
cout << string2 << endl;
cout также не заботится о размерах массива. Символы строки печатаются до тех пор, пока не встретится завершающий нулевой символ \0.
Сортировка массивов.
Сортировка данных имеет огромное значение.
// программа 4.16 сортирует элементы массива в возрастающем порядке
#include "stdafx.h"
#include <iostream>
#include <iomanip>
using namespace std;
int main ()
{
setlocale(LC_ALL, "rus");
const int arraySize = 10;
int a [arraySize] = {2, 6, 4, 8, 10, 12, 89, 68, 45, 37};
int i, hold;
cout << "элементы"<<endl;
//вывод исходного массива
for (i = 0; i < arraySize; i++)
cout << setw(4)<< a[i];
//пузырьковая сортировка
//цикл контролирует число проходов
for (int pass = 0; pass < arraySize - 1; pass++)
//один проход
for (int j = 0; j < arraySize - 1; j++)
//одно сравнение
//одна перестановка
if (a[j] > a[ j + 1 ])
{hold = a[j];
a[j] = a[ j + 1 ];
a[ j + 1 ] = hold;
} // конец if
cout << "\n элементы возрастают\n";
for (int k = 0; k < arraySize; k++)
cout << setw (4) << a[k];
cout << endl;
return 0; //успешное завершение
} // конец main
Программа на рис.4.16 сортирует значения массива a из 10 элементов в возрастающем порядке. Используемая при этом техника, получила название пузырьковая сортировка или сортировка погружением. Потому что наименьшее значение постепенно «всплывает», продвигаясь к вершине (началу) массива, подобно пузырьку воздуха в воде, а наибольшее значение погружается на дно (конец) массива. Этот прием требует нескольких проходов по массиву. При каждом проходе сравнивается пара следующих друг за другом элементов. Если пара расположена в возрастающем порядке или элементы одинаковы, то мы оставляем значения как есть. Если же пара расположена в убывающем порядке, то значения в массиве меняются местами.
Сортировка выполняется с помощью вложенного цикла for.
Если необходима перестановка, она выполняется тремя присваиваниями.
hold = a[i];
a[i] = a[i+1];
a[i+1] = hold;
где дополнительная переменная hold временно хранит одно из двух переставляемых значений. Перестановку нельзя выполнить двумя присваиваниями
a[i] = a[i+1];
a[i+1] = a[i];
Если, например, a[i] равно 7, а a[i + 1] равно 5, то после первого присваивания оба значения будут 5,а значение 7 будет потеряно. Следовательно, необходима дополнительная переменная.
Главное достоинство пузырьковой сортировки заключается в простоте ее программирования.
Однако пузырьковая сортировка выполняется медленно. Это очень заметно при сортировке больших массивов. В задачах вы разработаете более эффективные варианты пузырьковой сортировки.
