Массивы в С++

Для данного типа Т, Т[size] есть тип «массив из size элементов типа Т». Элементы нумеруются (индексируются) от 0 до size-1.

Например:

float v[3];
int   a[32];

Количество элементов массива должно быть константным выражением.

Многомерные массивы описываются как массивы массивов.

Например:

int d[10][20];   // d2 является массивом из 10 массивов по 20 целых.

Инициализаторы массивов

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

Например:

int  v1[]={ 1, 4, 6, 2};
char v2[] = { 't', 'e', 'x', 't', 0 };

Когда массив объявлен без указания размера, но при этом инициализирован списком, его размер вычисляется путём подсчёта числа элементов этого списка. Следовательно, v1 и v2 являются массивами int[4] и char[5] соответственно. Если размер задан явно, то задание большего числа элементов в списке инициализации будет ошибкой. Если в списке инициализации недостаёт элементов, всем остальным элементам массива присваивается значение 0. Не существует присваивания массиву, соответствующего описанному выше способу инициализации.

Доступ к элементам массивов

Доступ к элементам массива осуществляется по имени массива и индексу элемента.

Массивы как аргументы функций

Массив всегда неявно передаётся по ссылке. Это означает, что копии массива не создаётся и функция работает с альтернативным именем оригинального массива. Изменение элементов массива в функции привёдет к их изменению в оригинальном массиве. В примерах я буду писать «передаётся массив», подразумевая при этом, что передаётся ссылка на массив, чтобы не усложнять текст примеров.

После того, как будет изучена тема «указатели» ситуация станет несколько понятнее.

При передаче массива в функцию размер массива (если он нужен в алгоритме) необходимо передавать явно. Функция не делает никаких предположений относительно размера массива. То есть она получает тип «массив элементов заданного типа», но размер остаётся неизвестен.

Примеры

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

Обнулить элементы массива

1
2
3
4

void fill(int arr[], int count) {
  for (int i=0; i < count; ++i)
    arr[i]=0;
}

В функцию передаётся массив arr и число элементов в нём count. Начиная с нулевого до элемента count-1, всем элементам массива присваивается нулевое значение. В качестве индекса при обращении к элементам массива используется переменная i.

Если внимательно посмотреть на код этой функции, то можно заметить, что одна из переменных может быть удалена. Выполнение начинается с нулевого элемента и заканчивается элементом count-1. Именно поэтому в конце приходится производить сравнение i < count.

Если для обращения к элементам массива использовать переменную count и двигаться по массиву в обратном направлении, то проверять условие завершения цикла можно иначе:

1
2
3
4

void fill(int arr[], int count) {
  for ( --count; count >= 0; --count)
    arr[count]=0;
}

При инициализации цикла for в первом выражении значение count уменьшается на 1 с тем, чтобы первое обращение в массиве происходило к элементу count-1, поскольку в массиве на count элементов элементы индексируются с 0 до count-1.

При каждой итерации цикла значение переменной count уменьшается на единицу. Цикл завершается, когда нарушается условие count >= 0, т.е. count становится отрицательным.

Присвоить элементам массива последовательные значения

1
2
3
4

void fill_ sequential(int arr[], int count, int start_value) {
  for (int i=0; i < count; ++i)
    arr[i]=start_value++;
}

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

Несмотря на кажущуюся большую сложность данного алгоритма относительно предыдущего, он так же может быть «обращён» с удалением переменной count. Данное упражнение можно выполнить самостоятельно.

Поиск заданного элемента

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

В первую очередь требуется решить архитектурную задачу – сформировать интерфейс функции. В случае, если элемент присутствует функция должна возвращать индекс элемента. Как функция должна сообщать о том, что искомый элемент не найден?

Учитывая, что индексы – это целые числа большие или равные нулю, можно предложить следующий вариант: в случае, если искомое значение не найдено – возвращать значение -1, как индекс элемента. Поскольку такого индекса в массиве не может быть, вызывающая функция (клиент) может трактовать такой результат как сообщение о том, что элемент не найден.

Есть и другие варианты – например, использовать значение count как индекс искомого элемента, когда элемент не найден. Поскольку индекс последнего элемента массива count-1, то вызывающая функция сможет также трактовать это значение, как «отсутствие искомого элемента».

Выбор между этими вариантами зависит от принятых в проекте стандартов кодирования и необходимости поддержки совместимости с различными библиотеками. В учебных целях рекомендую использовать первый вариант, поскольку значение «-1» более явно свидетельствует об отсутствии искомого результата.

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

 
 
 
1
2
3
4
5
6
7

// Поиск ключа в массиве
// Функция возвращает индекс искомого элемента
// В случае отсутствия искомого элемента возвращает -1
int find_1(int arr[], int count, int key ) {
  for (int i=0; i < count; ++i)
    if (arr[i] == key)
      return i;

  return -1;
}

Перебираются все элементы массива (строка 2) и в случае, если найден искомый элемент (строка 3), возвращается его индекс (строка 4).

Если цикл завершается, и элемент найти не удаётся - возвращается -1 (строка 6).

Несмотря на всю простоту данного алгоритма его можно оптимизировать с целью ускорения поиска элемента. Как же ускорить линейный поиск в той реализации, которая приведена в данном алгоритме? Необходимо разделить действия, выполняемые на каждом шаге:

• Проверка на выход за пределы массива (строка 2)
• Проверка на равенство значения элемента искомому ключу (строка 3)

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

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

 
 
 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

// Поиск ключа в массиве
// Функция возвращает индекс искомого элемента
// В случае отсутствия искомого элемента возвращает -1
int find_2(int arr[], int count, int key ) {
  int temp=arr[count-1];
  arr[count-1]=key;

  int i;
  for (i=0; arr[i] != key ; ++i)
    ;

  arr[count-1]=temp;

  return arr[i] == key ? i : -1;
}

Значение, находящееся в последнем элементе, запоминается во временной переменной temp (строка 2). В последний элемент копируется искомое значение (строка 3).

В цикле производится поиск искомого элемента (6). Цикл выполняется до тех пор, пока не будет нарушено условие arr[i] != key. Как только будет найдет элемент, равный ключу, выполнение цикла будет прервано.

Возможны два случая:

• Если найденный элемент будет иметь индекс count-1, это будет тот элемент, который мы подложили в качестве ограничителя в конец массива. Это будет означать, что искомое значение в массиве не найдено. Но оно ещё может быть в сохранённом мной в переменной temp элементе из ячейки arr[count-1].
• Если найденный элемент будет иметь индекс, меньший, чем count-1, то это и будет элемент, который мы должны были найти.

До того, как завершить выполнение функции и вернуть результат, необходимо восстановить массив в начальном состоянии (строка 9).

Далее проверяется, равен ли найденный элемент (индекс i по-прежнему указывает на него) искомому. Если равен, значит, значение было найдено в массиве и его индексом является i. Если нет – возвращается -1.

Обращаю внимание на пустой оператор тела цикла в строке 7. Настоятельно рекомендую в подобных ситуациях всегда ставить пустой оператор тела цикла в отдельной строке (а не в той же строке, что и цикл for). Это позволит избежать впоследствии множества проблем и недоразумений.

Имеет ли смысл реально такая «оптимизация» - сложный вопрос. В чистом виде, на современных архитектурах – скорее всего – нет. Однако, она может быть с успехом использована как поисковый приём в составе более сложных алгоритмов, где соответствующие предусловия сохраняются. Я покажу это чуть ниже в алгоритме заполнения массива уникальными случайными числами.

Поиск в упорядоченной последовательности (двоичный поиск)

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

Однако, есть возможность значительно ускорить поиск, если ввести дополнительное предусловие к исходному массиву: данные в нём должны быть упорядочены.

Будем полагать, что в исходном массиве данные упорядочены по возрастанию.

В этом случае алгоритм двоичного поиска может быть реализован следующим образом:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

// Поиск ключа в упорядоченном массиве
// Массив должен быть упорядочен по возрастанию (неубыванию)
// Функция возвращает индекс искомого элемента
// В случае отсутствия искомого элемента возвращает -1.
int bin_search(int arr[], int count, int key ) {
  int l=0;            // нижняя граница
  int u=count-1;      // верхняя граница
  while ( l <= u ) {
    int m = (l+u)/2;
    if (arr[m] == key) return m;
    if (arr[m] < key) l = m + 1;
    if (arr[m] > key) u = m -1;
  }
  return -1;
}

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

Пока выполняется условие, что верхняя граница не стала меньше нижней (строка 4), функция выполняет следующие действия:

1. Алгоритм делает предположение, что искомое число находится посередине между нижней и верхней границами (строка 5)
2. В том случае, если в этом (среднем) элементе оказывается искомое число, то функция возвращает результат – индекс данного элемента (строка 6)
3. Если значение в среднем элементе меньше, чем искомое значение, то нижняя граница устанавливается на элемент, следующий за средним, поскольку искомое число не может быть среди элементов arr[0]..arr[m] (строка 7)
4. Если значение в среднем элементе больше, чем искомое значение, то верхняя граница устанавливается на элемент, находящийся перед средним, поскольку искомое число не может быть среди элементов arr[m]..arr[count-1] (строка 8).

Присвоить элементам массива случайные значения

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

Для получения случайных значений я буду использовать специальную функцию, называемую генератором псевдо-случайных чисел (ПСЧ). Функция rand стандартной библиотеки генерирует случайные числа в интервале от нуля до значения константы RAND_MAX, также определённой в стандартной библиотеке.

Заполнение случайными числами:

1
2
3
4

void fill_random(int arr[], int count) {
  for (int i=0; i < count; ++i)
    arr[i]=rand();
}

Присвоить элементам массива уникальные случайные значения

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

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

Входные данные в подобных ситуациях обязана проверять функция, не надеясь на то, что их проверит перед вызовом клиент (вызывающая функция). Но, поскольку необходимые средства диагностики ещё не известны учащимся, то при рассмотрении примера будем полагать, что требуемое условие выполняется, и размер массива не превышает количества уникальных чисел, которые может сгенерировать генератор ПСЧ.

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

Вернёмся к решению задачи. Простейший (наивный) вариант решения данной задачи выглядит следующим образом:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

void fill_random_unique_1(int arr[], int count) {
  for (int i=0; i < count; ++i ) {
    arr[i]=rand(MaxRnd);
    for (int j=0; j < i; ++j)
      if (arr[i]==arr[j]) {
        --i;
        break;
      }
  }
}

Алгоритм работает следующим образом: для текущего элемента массива генерируется случайное число и помещается в ячейку массива (строка 3). Далее проверяется, существует ли уже такое значение в предыдущих элементах массива (строки 4,5):

• Если не существует – сгенерированное значение остаётся в текущей ячейке массива и алгоритм переходит к следующему элементу массива (строка 2)
• Если такой элемент существует, то индекс элемента уменьшается на единицу (строка 6). Это так называемое «компенсационное уменьшение». Я знаю, что по завершении итерации цикла по элементам массива значение индекса будет увеличено (строка 2). Поэтому для того, чтобы следующая итерация вновь работала с текущим элементом (пытаясь сгенерировать такое значение, которого нет в предыдущих элементах) я уменьшаю значение индекса. В результате в сумме к следующей итерации алгоритм вновь будет генерировать случайное значение для текущей ячейки массива. Так будет продолжаться до тех пор, пока не найдётся значение, которое отсутствует в предыдущем массиве.

Оператор break (строка 7) служит для выхода из вложенного (поискового) цикла for в случае, если найден искомый элемент. После того, как совпадение найдено дальнейший поиск не требуется.

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

Для того, чтобы избавиться от этого эффекта, алгоритм можно переписать следующим образом:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

void fill_random_unique_2(int arr[], int count) {
  for (int i=0; i < count; ) {
    arr[i]=rand(MaxRnd);
    int j;
    for ( j=0 ; j < i; ++j)
      if (arr[i]==arr[j])
        break;

    if ( j == i )
      ++i;
  }
}

В данном случае проверка на наличие элемента производится циклом в строках 5-7. Но окончательный вывод делается в строке 9.

Перебираются все существующие в массиве элементы (строка 5) и если находится элемент, равный сгенерированному (строка 6), то выполнение цикла прерывается (строка 7).

• В том случае, если искомый элемент будет найден, то выполнение цикла будет прервано оператором break и управление будет передано в строку 9, а значение переменной j будет равно индексу элемента, в котором нашлось сгенерированное нами значение.
• Если искомый элемент не будет найден, то цикл будет завершён по нарушнинию условия j

В строке 9 проверяется равенство индексов i и j. Согласно предыдущему пояснению, это выражение будет истинно, если сгенерированного элемента не нашлось в массиве. В этом случае можно переходить к генерации следующего элемента, зафиксировав текущий (строка 10).

Обратим внимание на строки 5-7. В цикле производится проверка выхода за переделы уже заполненного массива (строка 5) и проверка на искомый элемент (строка 6). Удачным совпадением оказалось то, что искомый нами элемент и есть тот самый элемент, который был добавлен в элемент arr[i]. То есть мы точно знаем, что за последовательностью, в которой мы ищем только что добавленный элемент, есть элемент массива, в котором точно есть искомый элемент – мы только что сами его туда поместили. С учётом этой информации данный цикл можно переписать проще:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

void fill_random_unique_3(int arr[], int count) {
  for (int i=0; i < count; ) {
    arr[i]=rand(MaxRnd);
    int j;
    for ( j=0; arr[i]!=arr[j]; ++j)
      ;
       if ( j == i )
      ++i;
  }
}

В данном примере весь код поиска сгенерированного числа среди заполненных элементов массива сосредоточен в строках 6 и 7.

В строке 6 указывается, что перебор элементов должен идти с нулевого элемента массива до тех пор, пока не будет нарушено условие arr[i]!=arr[j], то есть пока не будет найдет элемент arr[j] равный элементу arr[i].

Это может произойти только в двух случаях:

• Такое значение присутствовало в заполненных элементах массива. В этом случае j будет хранить индекс такого элемента и будет заведомо меньше i.
• Такое значение отсутствует в заполненных элементах массива. В этом случае поставленное условие будет нарушено, когда i станет равен j и произойдёт сравнение сгенерированного элемента с самим собой.

Такое завершение поиска полностью соответствует постусловию, которое накладывалось на поисковый цикл в предыдущем примере.

Недостаток этого алгоритма – сравнительно большое время выполнения, которое сильно зависит от качества (равномерности) генератора ПСЧ и размера массива. Чем больше будет размер массива, тем сложнее алгоритму будет добавить новое число, поскольку будут действовать сразу два фактора:

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

То есть алгоритм будет иметь непостоянное время выполнения. К тому же это время будет достаточно сложно оценить.

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

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

Самое простое решение будет выглядеть следующим образом:

 1
 2
 3
 4
 5
 6
 7
 8
 9

void fill_random_unique_4(int arr[], int count)
{
  fill_ sequential(arr,count,0);

   for (int i=0; i < count; ++i) {
    int idx1 = rand()%count;
    swap(arr[i],arr[idx1]);
  }
}

В строке вызывается функция fill_ sequential, написанная мной ранее (см.выше).

Самое сложное в данном алгоритме – обеспечить однородность или равномерность использования случайных чисел. Если следовать оригинальной постановке задачи, то простое последовательное заполнение случайными числами от 0 до count-1 не подходит, поскольку по постановке задачи требуется использовать равномерное заполнение случайными числами в диапазоне от 0 до RAND_MAX. Написание алгоритма, заполняющего массив на count элементов числами с диапазоном от 0 до RAND_MAX, оставляется учащимся в качестве упражнения.

Алгоритмы для самостоятельного изучения

Дальнейшие алгоритмы приводятся без пояснений. Учащимся предлагается самостоятельно провести разбор этих алгоритмов. Их обсуждение будет на лекции.

Прямой поиск подстроки в строке

Постановка задачи: требуется найти первое вхождение одной строки в другой.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

// Функция ищет первое вхождение подстроки substr в строке str
// Возвращает индекс первого символа вхождения в строке str
// Возвращает -1 в случае, если подстрока не найдена
// Возвращает  0 в случае, если строка sub_str пустая
int substr_search(const char str[], const char sub_str[]) {
  int str_idx=0;
  int compare_idx=0;
  while(sub_str[compare_idx]) {
    if (str[str_idx+compare_idx] == 0 )
        return -1;
		
     if (str[str_idx+compare_idx] == sub_str[compare_idx])
     ++compare_idx;
    else {
      ++str_idx;
      compare_idx=0;
    }
  }
  return str_idx;
}
 

Алгоритмы сортировки

Постановка задачи: упорядочить исходную последовательность.

Прямое включение

Элементы мысленно делятся на уже готовую последовательность и исходную. На каждом шаге, начиная с i=1 и увеличивая каждый раз i на единицу, из последовательности извлекается i-ый элемент и вставляется в готовую последовательность на нужное место.

 1
 2
 3
 4
 5
 6
 7
 8
 9

void sort_insert(int arr[], int n) {
  for (int i=1; i < n; ++i) {
    int temp = arr[i];
    int j;
    for ( j=i ; j > 0 && temp < arr[j-1] ; --j )
      arr[j]=arr[j-1];
    arr[j]=temp;
  }
}

Прямой выбор

Выбирается элемент с наименьшим ключом. Он меняется местами с первым элементом. Затем процесс продолжается с оставшимися n-1 элементами.

 1
 2
 3
 4
 5
 6
 7
 8
 9

void sort_select(int arr[], int n) {
  for (int i=0; i < n-1; ++i) {
    int min=i;
    for (int j=i+1; j < n ; ++j )
      if (arr[min] > arr[j])
        min = j;
    swap(arr[min],arr[i]);
  }
}

Прямой обмен (пузырьковая)

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

 1
 2
 3
 4
 5
 6
 7

void sort_exchange(int arr[], int n) {
  for (int i=1; i < n; ++i) {
    for (int j=n-1; j >= i; --j)
      if (arr[j-1] > arr[j])
        swap(arr[j],arr[j-1]);
  }
}

Возможные оптимизации:

• Смотреть, были ли перестановки. Если на текущем проходе перестановок не было – останавливаться.
• Смотреть, до какого индекса были перестановки на последнем проходе – останавливаться.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

void sort_exchange_2(int arr[], int n) {
  int k=0;
  int limit=1;
  do {
    k=0;
    for (int j=n-1; j >= limit; --j)
      if (arr[j-1] > arr[j]) {
        swap(arr[j],arr[j-1]);
        k=j+1;
      }
    limit=k;
  } while (k);
}

Проблема: для 2 3 4 5 6 7 8 1 всё будет сделано за один проход, а для 9 1 2 3 4 5 6 7 8 – за восемь. Вывод: надо чередовать направление просмотров (шейкерная сортировка).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

void sort_exchange_2(int arr[], int n) {
  int k=0;
  int L=1;
  int R=n-1;

   while ( L < R) {
    for (int j=R; j >= L; --j)
      if (arr[j-1] > arr[j]) {
        swap(arr[j],arr[j-1]);
        k=j;
      }
    print(a,n);
    L=k+1;
    for (int j=L; j <= R; ++j)
      if (arr[j-1] > arr[j]) {
        swap(arr[j],arr[j-1]);
        k=j;
      }
    print(a,n);
    R=k-1;
  }
}