Одномерные массивы

Тема 3 Массивы

КОРПОРАЦИЯ YAMAHA МОТОРС

НАПЕЧАТАНО НА ПЕРЕРАБОТАННОЙ БУМАГЕ ЯПОНИЯ

Приложение

Код проводов

B черный

BR коричневый

Ch шоколадный

Dg темно-зеленый

G зеленый

L синий

O оранжевый

P Розовой

R красный

Sb сине-голубой

W белый

Y желтый

B/Y черно-желтый

Br/W коричнево-белый

G/Y зелено-желтый

L/W сине-белый

L/Y сине-желтый

R/B красно-черный

R/W красно-белый

W/L бело-синий

W/R бело-красный

Легенда

* - пометка авторов перевода, дополнительная информация отсутствующая в оригинале

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

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

· все элементы массива имеют одинаковый тип и имя;

· доступ к конкретному элементу массива осуществляется по его номеру или индексу (индексам).

В С++ различают массивы фиксированного размера и массивы переменного размера (динамические). Количество элементов в массиве первого типа известно при написании программы и никогда не меняется. Память под такой массив выделяет компилятор. Количество элементов динамического массива на этапе компиляции не известно и, как правило, зависит от входных данных. Память под динамический массив выделяется во время выполнения программы с помощью операций выделения памяти.

Описание массива фиксированного размера отличается от описания простой переменной наличием после имени квадратных скобок, в которых задается количество элементов массива (или размерность):

float A [10]; // пример описания массива из 10 вещественных чисел

Тип элементов массива – любой допустимый тип С++, например, встроенный или библиотечный, кроме типа void. Элементы массива нумеруются, начиная с нуля. Таким образом, последний элемент массива имеет индекс на единицу меньше, чем число элементов массива. Глобальный массив по умолчанию инициализируется нулями. Локальный массив, как и обычная переменная, по умолчанию никак не инициализируется. Инициализирующие значения при желании задают в фигурных скобках. Количество значений в списке инициализации не должно превышать размерность массива, иначе будет выдано сообщение об ошибке. Если же их меньше, то недостающие значения считаются равными нулю, например:

int Mas[5] = {3, 2, 1}; // 3 2 1 0 0

int Mas[5] = {0}; // все элементы проинициализированы нулем

Размерность массива может быть задана не только целой положительной константой, но и константным выражением, например:

const int Nmax = 5;

int Mas [Nmax] = {5, 4, 3, 2, 1};

int Mas [Nmax+10];

Одномерные массивы можно объявлять без указания размерности. Но в этом случае в объявлении массива обязательно использование инициализации. Это позволяет определить размер памяти, которую нужно выделить для массива:

int Mas[ ] = {30, 20, 10}; // одномерный массив из трёх элементов

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

Mas[0] = 10; Mas[k] = k + 5; Mas[i – 10] = sin(x);

Прежде чем выполнять обработку массива, нужно заполнить его исходными данными. Чаще всего для этого используется ввод значений с клавиатуры или из файла. Если же массив является результатом работы программы, то его нужно вывести на экран или в файл. Как правило, массив объявляется максимальной размерности, необходимой для решения задачи, а реальная размерность вводится пользователем во время работы программы. Далее приведены блоки ввода одномерного массива с клавиатуры и вывода его на экран:

#include <stdio.h>

void main()

{

const int Nmax = 10; // максимальная размерность массива

int Mas[Nmax]; // объявление массива максимальной размерности

int N; // реальная размерность массива

printf("\n N = ");

scanf("%d", &N); // ввод реальной размерности массива

for (int i = 0; i < N; i++) // блок ввода массива

{

printf(" Mas[%d] = ", i + 1);

scanf("%d", &Mas[i]);

}

printf("\n\n Massiv \n");

for (int i = 0; i < N; i++) // блок вывода массива

printf("%5d", Mas[i]); // ИЛИ printf(" %d ", Mas[i]);

getch();

}

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

N = 5

Mas[1] = 11

Mas[2] = 22

Mas[3] = 33

Mas[4] = 44

Mas[5] = 55

Massiv

11 22 33 44 55

Приведём некоторые из наиболее распространённых алгоритмов для обработки одномерных массивов. Во всех примерах опущен ввод размерности и массива.

Пример 1. Вычислить сумму и произведение элементов массива.

const int Nmax = 10;

int Mas[Nmax], N; // массив и его реальная размерность

int Sum, Pr; // сумма и произведение

Sum = 0, Pr = 1; // обязательная инициализация!

for (int i = 0; i < N; i++)

{

Sum += Mas[i]; // Sum = Sum + Mas[i];

Pr *= Mas[i]; // Pr = Pr * Mas[i];

}

printf("\n Sum = %d Pr = %d", Sum, Pr);

Инициализация переменных Sum = 0 и Pr = 1 перед началом вычислений обязательна, т.к. в этих ячейках памяти хранятся случайные значения, которые могут повлиять на результат вычислений.

Пример 2. Определить минимальный элемент массива и его номер.

const int Nmax = 10;

int Mas[Nmax], N;

int Min, Num; // минимальный элемент и его номер

Min = Mas[0], Num = 0; // обязательная инициализация!

for (int i = 1; i < N; i++)

if(Mas[i] < Min) // если текущий элемент меньше минимального

Min = Mas[i], Num = i; // запомнить его значение и номер

printf("\n Min = %d Num = %d", Min, Num + 1);

Перед началом вычислений переменной Min присваивается значение первого элемента массива Min = Mas[0], а переменной Num – его номер: Num = 0. Затем все элементы массива, начиная со второго, последовательно сравниваются с переменой Min, и если какой-то из них оказывается меньше, чем Min, то в этой переменной запоминается значение элемента массива Min = Mas[i], а в переменной Num – его текущий номер Num = i.

Если элементов с таким значением в массиве несколько, то в данном примере будет напечатан номер самого первого из них. Чтобы получить номер самого последнего, нужно в операторе if заменить знак операции на “<=”. Для того, чтобы найти максимальный элемент массива нужно в операторе if заменить знак операции на “>” (и, разумеется, изменить имя переменной на Max).

В операторе вывода для удобства восприятия печатается номер элемента больший на единицу Num + 1, т.к. нумерация элементов начинается с нуля.

Пример 3. Определить номер элемента массива, имеющего заданное значение (линейный поиск элемента в массиве).

const int Nmax = 10;

int Mas[Nmax], N;

int V, Num; // заданное значение и его номер

int Flag = 0; // флажок наличия или отсутствия результата

printf("\n V = ");

scanf("%d", &V); // ввод заданного значения

for (int i = 0; i < N; i++)

if(Mas[i] == V) // если текущий элемент равен заданному

{

Num = i; // запомнить его номер

Flag = 1; // есть результат

break; // выйти из цикла, прекратив поиск

}

if(Flag) // если есть искомое значение

printf("\n Num = %d", Num + 1); // печать номера элемента массива

else

printf("\n Искомое значение отсутствует!");

После ввода искомого значения все элементы массива последовательно сравниваются с ним, и если какой-то из элементов равен заданному значению, то запоминается его номер Num = i, флажок наличия результата устанавливается в единицу Flag = 1 (в начале программы он равен 0, что означает отсутствие результата) и происходит окончание поиска с выходом из цикла (break).

В данном примере поиск заканчивается при нахождении первого элемента массива, содержащего заданное значение (если таких элементов несколько). Если же оператор break удалить из цикла, то будет определён номер последнего элемента, содержащего заданное значение.

В конце проверяется, есть ли результат (Flag!= 0). Если есть, то он выводится на экран. В противном случае выводится сообщение о его отсутствии. Вместо целой переменной в данном примере можно использовать логическую: bool Flag.

Пример 4. Выполнить сортировку элементов массива по возрастанию (пузырьковая сортировка).

Схема сортировки

Схема перестановки элементов массива

const int Nmax = 10;

int Mas[Nmax], N;

int i, j, temp;

for (int i = 0; i < N – 1; i ++)

for (int j = i + 1; j < N; j ++)

if(Mas[i] > Mas[j]) // если предыдущий элемент больше следующего

{

temp = Mas[i]; // перестановка элементов массива

Mas[i] = Mas[j];

Mas[j] = temp;

}

Выделяем первый элемент массива (у него номер i) и последовательно сравниваем его со всеми остальными (с номером j). Если первый элемент окажется больше какого-то из остальных, то меняем их местами. За один проход массив не будет отсортирован, но самое маленькое значение окажется в первом элементе массива. На следующем проходе берём второй элемент массива (номер i) и также последовательно сравниваем его со всеми остальными (у них номер j). Если он окажется больше какого-то из них, то также меняем их местами. Теперь минимальный из оставшихся элементов массива окажется на втором месте. Повторяем эту процедуру, пока не останется сравнить два элемента: предпоследний (i -й) и последний (j -й). Когда оба цикла выполнятся до конца, элементы массива будут отсортированы по возрастанию. Замена операции “>” на “<” в операторе if меняет порядок сортировки на противоположный – по убыванию.

Рисунок наглядно показывает алгоритм решения задачи. Для этого потребуются вложенные циклы. Параметр внешнего цикла позволяет выделять очередной элемент массива, а его номер i меняется от первого до предпоследнего элемента. Параметр внутреннего цикла позволяет последовательно перебирать оставшиеся элементы массива, а их номер j всегда начинается со значения i + 1 и увеличивается до номера последнего элемента.

Пример 5. Выполнить двоичный поиск элемента в одномерном массиве.

Такой поиск используется для массивов большой размерности и выполняется значительно быстрее линейного, т.к. позволяет перебирать не все элементы. Обязательным условием является то, что исходный массив уже должен быть отсортирован по возрастанию.

Зная номер первого a и последнего z элементов, определяется номер среднего элемента m=(a+z)/2. Если значение элемента массива Mas[m] совпадает с искомым, то поиск закончен. Иначе нужно выяснить, в какой части массива продолжить поиск. Если искомое значение меньше чем Mas[m], то поиск продолжится в левой части массива, а правая граница смещается z=m–1. В противном случае поиск продолжится в правой части массива, а левая граница смещается a=m+1. Затем вновь находится номер среднего элемента и определяется, содержит ли он искомое значение. Таким образом, область поиска каждый раз уменьшается вдвое, что позволяет быстро найти нужное значение.

Если же массив не содержит искомое значение, то в процессе смещения границ левая граница a становится больше правой z, что является признаком окончания поиска с отрицательным результатом.

Дата добавления: 2014-12-23