Хранение строк в массивах символов.

Массивы

 

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

Массивы – это «статические» сущности, они сохраняют свои размеры на протяжении всего времени выполнения программы.

Стеки, списки, очереди, деревья – это динамические структуры данных.

 

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

 

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 будет потеряно. Следовательно, необходима дополнительная переменная.

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

Однако пузырьковая сортировка выполняется медленно. Это очень заметно при сортировке больших массивов. В задачах вы разработаете более эффективные варианты пузырьковой сортировки.