|
Примеры реализации статических массивов на C++Курс по структурам данных: https://stepik.org/a/134212 Мы продолжаем тему статических массивов. На протяжении этого курса я буду показывать примеры использования различных структур данных на языках С++ и Python. Почему именно эти языки программирования? На самом деле можно было бы еще взять C#, Java, PHP и некоторые другие довольно популярные ЯП. Но, сами понимаете, во что тогда превратится этот курс. Вначале я вообще хотел взять только Python и все показывать на нем. Но, во-первых, на нем программируют далеко не все и, во-вторых, не все можно так явно показать, как например, на языке С++. Собственно, вторым языком программирования я и взял С++. Тем более, что многие современные и популярные языки Java, C# и прочие вышли из языка С++, а потому очень на него похожи. К тому же, С++ хоть и высокоуровневый язык, но, тем не менее, остается достаточно низкоуровневым, например, при работе с памятью, когда после ее выделения обязательно нужно ее освободить. Сборщика мусора здесь нет, как во многих других языках, таких как Python, Java и C#. В результате, грамотно написанный программный код на С++ очень хорошо переводится компилятором в набор машинных команд центрального процессора. По этой причине С++ еще называют ассемблером высокого уровня. Мне показалось этот язык очень хорошо подходит для демонстрации различных структур данных, которые мы будем рассматривать. Итак, давайте вернемся к статическим массивам. Строго говоря, на языке Python их нет, в нем используются динамические массивы, о которых речь пойдет далее. Поэтому сразу перейдем к языку С++ и посмотрим, как в нем объявляются статические массивы. Общий синтаксис для определения статических массивов имеет вид: <тип данных> <имя массива>[число элементов]; Например, чтобы
сохранить значения линейной функции float y[100]; Здесь y – это имя массива (придумываем сами); float – тип элементов массива; 100 – размер массива (максимальное число элементов). Все, мы создали массив. Теперь, чтобы в его первый элемент запишем значение функции при x = 0: float k = 0.5f, b = -1.4f; y[0] = k*0+b; Для второго элемента, получим: y[0] = k*0+b; и так далее. Давайте заполним все значения через цикл: for (int x = 0; x < 100; ++x) y[x] = k * x + b; и выведем первые 10 значений в консоль: for (int i = 0; i < 10; ++i) printf("%.2f ", y[i]); Вот простейший пример того, как можно объявить статический массив в С++, заносить в него значения и считывать их. При этом память под массив выделяется автоматически и также автоматически освобождается. То есть, здесь все работает так, словно массив – это обычная переменная, только может содержать сразу множество значений. Однако при создании массива командой: int ar[243]; в квадратных скобках можно указывать только константное значение. Записывать там переменную не допустимо: int n = 100; float y[n]; // ошибка, n – переменная Но что делать, если нам нужно выделить под массив память в n элементов, а n определяется в процессе работы программы? Для этого следует воспользоваться другим способом объявления массивов через оператор new: float* y = new float[n]; Здесь мы используем указатель типа float с именем y, который будет ссылаться на первый элемент массива. Сам же оператор new выделяет непрерывную область памяти под n элементов с типом float. Но при использовании такого оператора нужно быть очень аккуратным, т.к. в С++, как я уже говорил, нет сборщика мусора и всю явно выделенную память нужно самостоятельно освобождать, когда она становится не нужной. Делается это оператором delete следующим образом: delete[] y; То есть, пишется ключевое слово delete, ставятся квадратные скобки, говорящие, что освобождается память статического массива, и затем, указатель на начало этого массива. Если не прописывать эту команду, то память будет автоматически освобождена самой ОС после завершения программы. Но правила хорошего тона подразумевают наличие этой команды после команды new. Вставка и удаление элементов в статическом массивеТеперь, когда мы научились объявлять статические массивы на С++, давайте реализуем простые алгоритмы вставки и удаления элементов. Еще раз уточню, что здесь речь идет о вставке значения в массив по определенному индексу. Общее число элементов массива при этом остается постоянным. Чтобы все это было понятнее, рассмотрим очень простую задачку хранения оценок студента в статическом массиве. Из своего опыта преподавания я знаю, что максимальное число оценок для одного студента за один семестр точно не будет больше 20. Именно такого размера мы и возьмем массив. Далее нужно определиться с типом его элементов. Так как оценки меняются в диапазоне от 0 до 5, то можно взять тип char: const int N = 20; char marks[N]; Вы можете спросить, как так, тип char является символьным, а мы собираемся целые значения хранить? Все так, но этот тип (char) в действительности представляется одним байтом и хранит целые числа, только сам С++ их интерпретирует как символы, когда это нужно. А нам в данной задаче этого типа будет вполне достаточно. Конечно, можно было бы прописать тип int, но он занимает в памяти 4 байта, т.е. в 4 раза больше. Лишний расход памяти нам ни к чему, поэтому возьмем char. Итак, у нас есть массив marks из 20 элементов. Как нам теперь понять, сколько оценок он хранит? Для этого введем еще одну переменную, на этот раз я ее объявлю целочисленной: int count_marks = 0; и она будет показывать, сколько оценок уже было проставлено. Изначально, конечно же 0. Вы здесь опять же можете сказать, а почему count_marks имеет тип int? У нас массив всего в 20 элементов и достаточно было бы типа char, т.к. он также хранит целые значения? Да, формально, можно было бы. Но в практике программирования все же принято счетчики определять типом int. Тем более он всего один на весь массив и к особому расходу памяти не приводит. Как вариант, можно указать тип short, тоже как целочисленный в 2 байта. Но все же int используется чаще. Отлично, массив и счетчик оценок у нас имеются. Теперь представим, что студент уже получил несколько оценок. Для простоты я это пропишу в программе следующим образом: char marks[N] = {2, 2, 3}; int count_marks = 3; Мы сразу в момент объявления массива инициализируем его тремя оценками. Соответственно, счетчик оценок принимает также значение три. Но потом оказалось, что я поставил не все оценки. Неожиданно выяснилось, что у него есть еще четверка, которая должна стоять на втором месте: 2, 4, 2, 3 Так как в массивах все элементы должны идти по порядку с самого начала без каких-либо пропусков, из-за этой четверки придется сместить последние два значения вправо, а затем, на вторую позицию записать 4. На уровне языка С++ это можно сделать так: int indx_insert = 1; int end = (count_marks < N) ? count_marks : N - 1; for (int i = end; i > indx_insert; --i) marks[i] = marks[i - 1]; marks[indx_insert] = 4; if (count_marks < N) count_marks++; Мы здесь объявляем вспомогательную переменную indx_insert – индекс вставляемого (добавляемого) значения; и переменную end – конечную позицию, от которой делать цикл при сдвиге значений. Величина end должна быть равна count_marks, если count_marks меньше длины массива, либо N-1 (самый последний элемент в массиве сдвигать не нужно, он будет теряться). Затем, в цикле смещаем все оценки справа на один элемент от удаляемого и записываем новое значение 4 в массив. В конце должны увеличить общее число оценок count_marks на единицу, но только так, чтобы count_marks не превосходил значения N – размера массива. Вот общий принцип вставки нового значения в статических массивах. Разумеется, здесь мы полагаем, что величина indx_insert меньше count_marks, иначе цикл просто не отработает. Теперь посмотрим, как обстоят дела с удалением значения из массива. Допустим, студент увидел у себя две двойки и в слезах бросился перед вами на колени, умоляя убрать первую двойку, якобы у него в этот день разболелась голова и даже есть справка. Видя могучую фигуру студента, от греха подальше, преподаватель решил просто удалить первую двойку. На уровне языка С++ это можно сделать так: const int N = 20; char marks[N] = {2, 4, 2, 3}; int count_marks = 4; int indx_del = 0; for (int i = indx_del; i < count_marks - 1; ++i) marks[i] = marks[i + 1]; if (count_marks > 0) count_marks--; Фактически, все удаление делается в одном цикле путем смещения всех актуальных значений влево на место удаляемого. В конце уменьшаем счетчик оценок count_marks на единицу и все. Вот так выполняются основные операции при работе со статическими массивами в языке С++. Я, надеюсь, что из этого занятия вы стали лучше понимать концепцию этой структуры данных и сможете эффективно и грамотно применять ее в своих программах. Курс по структурам данных: https://stepik.org/a/134212 Видео по теме |
при
,
необходимо задать массив в 100 элементов с вещественным типом элементов:
