§ 8. Структурированные типы данных. Массивы
Информатика. 11 класса. Босова Л.Л. Оглавление
8.1. Общие сведения об одномерных массивах
Мы повторили основные приёмы работы с простыми типами данных. Из элементов простых типов в языке Pascal можно образовывать составные типы данных (структуры данных). Примером таких структур являются одномерные массивы.
Массив — это поименованная совокупность однотипных элементов, упорядоченных по индексам, определяющим положение элемента в массиве.
Массив в языке Pascal — это набор однотипных данных, причём количество этих данных фиксировано и определяется при описании массива. Все переменные, входящие в массив, имеют одно и то же имя — имя массива, а различаются они по индексу — номеру (месту) в массиве.
Описание массива выглядит так:
array [<тип индекса>] of <тип компонент>
Здесь:
• array и of — служебные слова («массив» и «из»);
• <тип индекса> — описание индексации компонент (элементов) массива;
• <тип компонент> — тип величин, составляющих массив. Например:
• var day: array [1..365] of integer — 365 целочисленных элементов пронумерованы от 1 до 365;
• var tern: array [1..12] of real — 12 вещественных элементов пронумерованы от 1 до 12;
• var ocenka: array [2..5] of integer — 4 целочисленных элемента пронумерованы от 2 до 5;
• const n = 10; var slovo: array [1..n] of string — n строковых величин пронумерованы от 1 до n.
Вспомним основные приёмы работы с массивами.
Пример 1. Имеются сведения о количестве ежедневных осадков в течение июня месяца в некотором регионе. Требуется найти среднее количество осадков и вывести таблицу, в которой для каждого дня месяца указать количество осадков в этот день и его отклонение от среднемесячного значения.
Для решения этой задачи данные о количестве ежедневных осадков в течение месяца будут просмотрены дважды:
1) при поиске среднего значения;
2) при расчёте отклонения.
Для решения задачи нам понадобится массив из 30 вещественных чисел. Назовём его osad. В программе будет два цикла. В первом цикле мы введём значения элементов массива и сразу же подсчитаем их сумму — по завершении цикла мы получим сумму осадков, выпавших в течение месяца. Во втором цикле мы выведем строки таблицы и вычислим значения отклонений.
При работе с элементами массива воспользуемся переменной osad[i], значение индекса i при этом будет изменяться от 1 до 30 с шагом 1. Для вычисления среднего значения задействуем вещественную переменную sred, присвоив ей начальное значение 0 и последовательно накапливая в ней сумму осадков, выпавших в течение месяца. Разделив по завершении цикла полученное значение на 30, вычислим требуемое среднемесячное количество осадков и присвоим результат этой же переменной.
Найдите в Интернете информацию о количестве ежедневных осадков, выпавших в течение месяца, в вашем регионе. Используя эти данные, выполните программу в среде программирования Pascal.
Выполните аналогичные расчёты с помощью электронных таблиц.
Чаще всего массив обрабатывается в цикле for. Но при работе с массивами можно использовать и другие циклы.
Пример 2. Имеется массив символов. Требуется вывести на экран элементы данного массива в обратном порядке.
Элементами массива символов могут быть любые символы, имеющиеся на клавиатуре, причём каждому элементу соответствует именно один символ. Если в качестве элементов нашего массива рассматривать последовательности букв, образующие некоторое слово или фразу на естественном языке, то, решив поставленную задачу, мы научимся строить «перевёртыши» слов.
Будем рассматривать слова и фразы не более чем из 20 символов, задав соответствующую размерность массива:
simbol: array [1..20] of char;
Если какое-то слово или фраза будут короче, то часть массива окажется не занятой, но это не повлияет на работу программы. Договоримся признаком конца слова считать точку — ввод символов продолжается, пока не введена точка; после ввода точки ввод символов прекращается.
Запустите программу в среде программирования Pascal.
Модифицируйте программу так, чтобы в начале её работы пользователю задавался вопрос о количестве символов, которые он будет вводить. Какой цикл при этом лучше использовать?
Как изменить программу, чтобы она выводила на экран в обратном порядке элементы целочисленного массива?
К типовым задачам обработки одномерных массивов, решаемым в процессе их однократного просмотра, относятся:
• задачи поиска элементов с заданными свойствами, в том числе максимумов и минимумов;
• проверка соответствия элементов массива некоторому условию (подсчёт количества или суммы элементов, удовлетворяющих некоторому условию;
• проверка соответствия всех элементов массива некоторому условию;
• проверка массива на упорядоченность и др.);
• задачи на удаление и вставку элементов массива;
• задачи на перестановку всех элементов массива в обратном порядке и т. д.
8.2. Задачи поиска элемента с заданными свойствами
Очень часто в реальной жизни нам приходится сталкиваться с задачей поиска информации в большом массиве данных. Например, поиск нужного слова в словаре, поиск времени отправления нужного поезда в расписании, поиск нужного товара в интернет- магазине и т. д.
В программировании поиск — одна из наиболее часто встречающихся задач невычислительного характера.
В алгоритмах поиска существует два возможных варианта окончания их работы: поиск может оказаться удачным — заданный элемент найден в массиве и определено его месторасположение, либо поиск может оказаться неудачным — необходимого элемента в данном объёме информации нет.
Рассмотрим несколько типовых задач поиска, первое знакомство с которыми у вас состоялось ещё в основной школе.
Пример 3. Последовательный поиск в неупорядоченном массиве.
Имеется массив а[1..n]; требуется найти элемент массива, равный р.
Алгоритм последовательного поиска в неупорядоченном массиве может быть следующим.
1. Установить i = 1.
2. Если a[i] = р, алгоритм завершил работу успешно.
3. Увеличить i на 1.
4. Если i ? n, то перейти к шагу 2. В противном случае алгоритм завершил работу безуспешно.
Возможная программа, реализующая этот алгоритм на языке Pascal, имеет вид:
Внимательно рассмотрите условие продолжения цикла. В каком случае выполнение цикла продолжается? В каких случаях осуществляется выход из цикла?
Запустите программу на выполнение в среде программирования Pascal.
Как иначе можно решить эту задачу, например, с использованием цикла for? Напишите соответствующую программу.
Оценим сложность рассмотренного алгоритма последовательного поиска, непосредственно зависящую от числа сравнений с искомым элементом. В худшем случае искомый элемент окажется на последнем месте или не будет найден вообще. В таком случае необходимо будет проделать n сравнений, т. е. сложность алгоритма будет равна 0(n).
Пример 4. Поиск максимумов и минимумов.
Имеется массив а[1..n]; требуется найти значение наибольшего (наименьшего) элемента массива.
Алгоритм поиска значения наибольшего (максимального) элемента в неупорядоченном массиве может быть следующим.
1. Установить значение текущего максимума равным первому исследуемому элементу (max := а[1]).
2. Установить счётчик равным 2 (i:= 2).
3. Если исследованы ещё не все элементы (i <= n), то перейти к шагу 4, иначе алгоритм окончен (максимальный элемент равен max).
4. Если рассматриваемый элемент больше, чем текущий максимум (a[i] > max), то max присвоить значение a[i].
5. Перейти к следующему элементу (увеличить i на единицу).
6. Перейти к шагу 3.
Возможная программа, реализующая этот алгоритм на языке Pascal, имеет вид:
Запустите программу на выполнение в среде программирования Pascal.
Как иначе можно решить эту задачу, например, с использованием цикла for? Напишите соответствующую программу.
Преобразуйте программу так, чтобы с её помощью можно было находить минимальный элемент массива.
Какие изменения надо внести в программу для поиска индекса максимального (минимального) элемента массива?
Самостоятельно оцените сложность рассмотренного алгоритма.
8.3. Проверка соответствия элементов массива некоторому условию
Пример 5. Подсчёт количества элементов, удовлетворяющих некоторому условию.
Зачастую бывает важно выяснить, сколько элементов, обладающих определённым свойством, содержится в массиве. Для решения этой задачи следует:
1) присвоить нулевое значение переменной, введённой для подсчёта количества элементов, удовлетворяющих заданному условию (k := 0);
2) организовать просмотр всех элементов массива: если просматриваемый элемент удовлетворяет заданному условию, значение переменной k увеличивать на 1.
Фрагмент программы подсчёта количества элементов массива, например больших некоторого числа р, имеет вид:
Запишите полный текст программы и выполните её на компьютере для рассматриваемого в примере 8 массива а, состоящего из семи элементов, и числа р = 15.
Как модифицировать программу, чтобы можно было вычислить сумму элементов массива, больших некоторого числа р?
Пример 6. Проверка соответствия всех элементов массива некоторому условию.
Для того чтобы установить факт соответствия всех элементов массива некоторому условию, достаточно:
1) подсчитать количество элементов массива, соответствующих заданному условию;
2) сравнить найденное количество с общим числом элементов массива и вывести соответствующий результат.
Самостоятельно разработайте программу, позволяющую определить, все ли элементы массива являются двузначными числами. Выполните её на компьютере для рассматриваемого в примере 8 массива а, состоящего из семи элементов.
Пример 7. Проверка массива на упорядоченность.
Рассмотрим алгоритм, позволяющий определить, упорядочены ли элементы массива а[1..n] по неубыванию, т. е. каждый элемент массива с 1-го по (n — 1)-й не больше последующего.
Самый простой путь решения этой задачи — проверить, есть ли в массиве такие пары элементов, что a[i] > a[i + 1]. Если подобные пары элементов есть, то массив не упорядочен по неубыванию, а если таких пар нет, то упорядочен.
В программе будем использовать логическую переменную flag:
• если flag = true, то массив упорядочен;
• если flag = false, то массив неупорядочен.
Ниже представлен фрагмент программы, реализующей этот алгоритм:
Запишите полный текст программы и выполните её на компьютере для рассматриваемого в примере 8 массива а, состоящего из семи элементов.
Как можно решить эту же задачу путём подсчёта количества пар элементов массива, таких что a[i] > a[i + 1] (a[i] <= a[i + 1])?
8.4. Удаление и вставка элементов массива
Пример 8. Удаление из массива элемента с индексом к.
Имеется одномерный целочисленный массив из семи элементов:
Удалим из массива элемент с индексом k = 4, а все элементы, расположенные справа от него, сдвинем на одну позицию влево. Получим следующий целочисленный массив из шести элементов:
При удалении из массива любого из элементов размерность массива уменьшается на 1.
Мы видим, что элементы с индексами от 1 до k — 1 не изменились. На место элемента с индексом k (4) переместился элемент, имевший индекс k + 1 (5), на место элемента с индексом k + 1 (5) переместился элемент, имевший индекс k + 2 (6) и т. д.
В общем случае, фрагмент программы удаления из массива а[1..n] элемента с индексом k и последующим сдвигом всех расположенных справа от него элементов на одну позицию влево имеет вид:
Запишите полный текст программы и выполните её на компьютере для рассмотренного выше массива а.
Пример 9. Вставка в массив элемента на место с индексом k.
Будем работать с тем же массивом из семи элементов. Но теперь наша задача будет состоять в том, чтобы вставить в массив на место с индексом k = 4 (т. е. после элемента с индексом k — 1) ещё один элемент, имеющий значение 11.
Получим следующий целочисленный массив из восьми элементов:
При вставке в массив ещё одного элемента размерность массива увеличивается на 1. Это надо учесть при описании массива.
Итак, а[4] := 11. Элементу а[5] следует присвоить то значение, которое было у а[4], элементу а[6] — значение, которое было у а[5], и т. д. В общем случае, элементу a[k + 1] следует присвоить то значение, которое было у a[k].
Подумайте, что получится в результате выполнения следующих групп операторов присваивания:
1) а[4]:=11; а[5]:=а [ 4]; а[б]:=а [ 5] ; а[7]:=а[6]; а[8]:=а[7];
2) а[8]:=а[7] ; а[7]:=а[б]; а[6]:=а[5] ; а[5]:=а[4]; а[4]:=11;
В общем случае, фрагмент программы вставки в массив а[1..n — 1] элемента на место с индексом k и сдвигом k-гo, (k + 1)-го, …, (n — 1)-го элементов на одну позицию вправо имеет вид:
В общем случае, меняются местами элементы a[i] и а[n -i+1].
Запишите полный текст программы и выполните её на компьютере для рассмотренного выше массива а. Помните, что при описании массива надо учесть размерность массива, получающегося в результате работы программы.
8.5. Перестановка всёх элементов массива в обратном порядке
Пример 10. Перестановка всех элементов массива а[1..n] в обратном порядке сводится к тому, что меняются местами первый и последний элементы, второй и предпоследний элементы и т. д.
Перестановка нашего массива из семи элементов даст такой результат:
Вспомним, как можно произвести обмен значений между двумя переменными. Выполнение операторов:
а[1]:=а[n]; а[n]:=а[1]; к желаемому результату не приводит. Самый простой вариант — использование вспомогательной переменной:
Выясним, сколько всего операций обмена следует произвести.
Если произведена перестановка, например, первого и последнего элементов, то одновременно произведена и перестановка последнего и первого элементов. Таким образом, если число элементов массива чётное, то достаточно произвести n/2 операций обмена.
Но что происходит, если массив содержит нечётное число элементов? Например, в нашем массиве из семи элементов выполнялось три обмена, а четвёртый элемент, занимающий центральную позицию, оставался на своём месте. В общем случае число операций обмена при перестановке в обратном порядке всех n элементов массива определяется как n div 2.
В общем случае, фрагмент программы по перестановке в обратном порядке всех элементов массива а[1..n] имеет вид:
Запишите полный текст программы и выполните её на компьютере для рассмотренного выше массива а, состоящего из семи и из шести элементов.
8.6. Сортировка массива
Сортировка — один из наиболее распространённых процессов современной обработки данных.
Сортировка — это распределение элементов массива в соответствии с определёнными правилами.
Под сортировкой (упорядочением) массива понимают перераспределение значений его элементов в некотором определённом порядке.
Порядок, при котором в массиве первый элемент имеет самое маленькое значение, а значение каждого следующего элемента не меньше значения предыдущего элемента, называют неубывающим.
Порядок, при котором в массиве первый элемент имеет самое большое значение, а значение каждого следующего элемента не больше значения предыдущего элемента, называют невозрастающим.
Цель сортировки — ускорить последующий поиск элементов, т. к. нужный элемент легче искать в упорядоченном массиве.
Рассмотрим и проанализируем несколько алгоритмов сортировки для решения следующей задачи. Дан одномерный массив целых чисел. Требуется отсортировать его так, чтобы все элементы были расположены в порядке неубывания: a[i] <= a[i 4- 1].
Обменная сортировка методом «пузырька»
Своё название алгоритм получил благодаря следующей ассоциации: если сортировать этим алгоритмом массив по неубыванию, то максимальный элемент «тонет», а «лёгкие» элементы поднимаются на одну позицию к началу массива на каждом шаге алгоритма.
Пусть n — количество элементов в неупорядоченном массиве.
1. Поместим на место п-го элемента (а[n]) наибольший элемент массива. Для этого:
1) положим i = l;
2) пока не обработана последняя пара элементов, т. е. (n — 1)-й и n-й элементы:
• сравниваем i-и и (i + 1)-й элементы массива;
• если a[i] > a[i +1] (элементы расположены не по порядку), то меняем элементы местами;
• переходим к следующей паре элементов, сдвинувшись на один элемент вправо.
2. Повторяем пункт 1, каждый раз уменьшая размерность неупорядоченного массива на 1, до тех пор, пока не будет обработан массив из одной пары элементов (таким образом, на k-м просмотре будут сравниваться первые (n — k) элементов со своими соседями справа).
Пример 11. Есть массив: 5 4 3 2 1. На примере этого массива подсчитаем количество элементарных действий в вычислительном процессе алгоритма сортировки методом «пузырька»:
• 1-я итерация: 4 3 2 1 5 (4 сравнения, 4 обмена);
• 2-я итерация: 3 2 1 4 5 (3 сравнения, 3 обмена);
• 3-я итерация: 2 1 3 4 5 (2 сравнения, 2 обмена);
• 4-я итерация: 1 2 3 4 5 (1 сравнение, 1 обмен).
Алгоритм закончил работу. Было сделано 10 сравнений и 10 обменов (4 + 3 + 2 + 1).
Этот алгоритм легко запоминается, но на практике он используется достаточно редко из-за квадратичной сложности, означающей, что в общем случае количество выполненных сравнений и обменов сопоставимо с п2, где тг — количество элементов массива.
Попытайтесь самостоятельно запрограммировать алгоритм сортировки методом «пузырька».
Сортировка выбором
Сортировка выбором (в порядке неубывания) осуществляется следующим образом:
1) в массиве выбирается минимальный элемент;
2) минимальный и первый элементы меняются местами (первый элемент считается отсортированным);
3) в неотсортированной части массива снова выбирается минимальный элемент и меняется местами с первым неотсортированным элементом массива;
4) действия, описанные в пункте 3, повторяются с неотсортированными элементами массива до тех пор, пока не останется один неотсортированный элемент (его значение будет максимальным).
Пример 12. Есть массив: 5 4 3 2 1.
1- я итерация: 1 4 3 2 5 (4 сравнения, 1 обмен).
2- я итерация: 1 2 3 4 5 (3 сравнения, 1 обмен).
3- я итерация: 1 2 3 4 5 (2 сравнения, 0 обменов).
4- я итерация: 1 2 3 4 5 (1 сравнение, 0 обменов).
В общем случае алгоритм сортировки выбором имеет квадратичную сложность относительно операций сравнения и линейную сложность относительно операций обменов. Этот алгоритм целесообразно применять, когда операция обмена над элементами массива особенно трудоёмка (например, если элементом массива является запись с большим числом полей).
Приведём фрагмент программы, реализующей описанный выше алгоритм:
Запишите полный текст программы и выполните её на компьютере для рассмотренного выше массива.
САМОЕ ГЛАВНОЕ
Из элементов простых типов в языке Pascal можно образовывать составные типы данных (структуры данных). Примером таких структур являются одномерные массивы.
Массив в языке Pascal — это набор однотипных данных, причём количество этих данных фиксировано и определяется при описании массива. Все переменные, входящие в массив, имеют одно и то же имя — имя массива, а различаются они по индексу — номеру (месту) в массиве.
Перед использованием в программе массив должен быть описан, т. е. должно быть указано имя массива, количество элементов массива и их тип. Это необходимо для того, чтобы выделить в памяти под массив блок ячеек нужного типа.
Чаще всего массив обрабатывается в цикле for. Но при работе с массивами можно использовать и другие циклы.
К типовым задачам обработки одномерных массивов, решаемым в процессе их однократного просмотра, относятся:
• задачи поиска элемента с заданными свойствами, в том числе максимумов и минимумов;
• проверка соответствия элементов массива некоторому условию (подсчёт количества или суммы элементов, удовлетворяющих некоторому условию; проверка соответствия всех элементов массива некоторому условию; проверка массива на упорядоченность и др.);
• задачи на удаление и вставку элементов массива;
• задачи на перестановку всех элементов массива в обратном порядке и т. д.
Сортировка — один из наиболее распространённых процессов современной обработки данных. Под сортировкой (упорядочением) массива понимают перераспределение значений его элементов в некотором определённом порядке.
Вопросы и задания
1. Приведите примеры задач поиска информации в больших массивах данных.
3. Программист написал программу суммирования элементов массива, но допустил в ней ошибку.
4. Программист написал программу нахождения произведения элементов массива, но допустил в ней ошибку.
6. Имеется одномерный целочисленный массив из семи элементов:
8. Имеется одномерный целочисленный массив из семи элементов:
10. Дано натуральное десятичное число n <= 32 000. Напишите программу, в которой:
§ 7. Запись алгоритмов на языках программирования
§ 8. Структурированные типы данных. Массивы
§ 9. Структурное программирование