Файл: Особенности и примеры использования массивов при разработке программ (Основные понятия массивов и их типы).pdf

Введение

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

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

Цель работы состоит в рассмотрении основных алгоритмов обработки массивов максимально близко к практическому их применению

В работе будут решены следующие задачи:

1. Изучение типов массивов.
2. Изучение типовых алгоритмов обработки одномерных и двумерных массивов.
3. Группировать задачи по методам решения.
4. Обобщить и систематизировать теоретический и практический материал по теме.

Основные понятия массивов и их типы

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

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

---

Каждый элемент массива имеет свой номер - индекс, который используют для получения доступа к нему. Индекс имеет целочисленный тип, так как он определяет местоположения элемента в массиве.

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

Массивы могут быть:

• 1. одномерными (одна строка – несколько столбцов);
  2. многомерными (несколько строк – несколько столбцов).

Создание массива начинается с его описания либо в разделе var, либо в разделе type. Для задания массива используется зарезервированное слово array , после которого указывается тип индекса (-ов) компонент (в квадратных скобках) и после слова of - тип самих компонент:

Type

<имя массива>= array [<тип индекса(-ов)>] of <тип компонент>;

Или

Var

<имя массива>: array [<тип индекса(-ов)>] of <тип компонент>;

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

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

Приведем пример:

Type

arr = array [1..3] of real;

matrix = array [1..3, 1..2] of integer;

mas1: arr = (1, 2, 3);

mas2: matrix = ((1, 2), (3, 4), (5, 6));

Тип массив можно вводить и непосредственно при определении соответствующих переменных или типизированных констант.

Приведем пример:

Var

m1, m2 : array [1..3] of integer;

matr :array [1..3, 1..3] ofreal;

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

Например, m1 [2], matr[i,j].

Для обработки массива и последовательного доступа к данным, как правило, используется цикл FOR.

Например ,

for i:=1 to 10 do read(mas[i]);

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

---

Например,

for i:=1 to 10 do

for j:=1 to 10 do read(mas[i, j]);

Над элементами массива можно производить те же операции, которые допустимы для данных его базового типа. Если два массива имеют одинаковые типы индексов и одинаковые типы элементов, то к ним применимы булевы операции (<>=).

Основные операции обработки одномерного массива

Заполнение одномерного массива

Для того чтобы заполнить массив необходимо последовательно перебрать все ячейки (компоненты) массива и записать в них некоторые значения. Для перебора ячеек массива используется цикл for , в котором с помощью счетчика перебираются индексы ячеек. Заносимые в массив данные могут запрашиваться как с клавиатуры, так и выбираться случайным образом с помощью генератора случайных чисел Random.

Рассмотрим разные варианты ввода одномерного массива.

1. Ввод массива с использованием цикла с параметром

Программный код:
Program Primer;
Var i: integer;
     X: array [1..30] of Integer;
Begin
     For i := 1 To 30 Do Read (X[i]);
     Readl
End.

Блок схема алгоритма ввода массива представлена на рисунке 1:

Начало

i:=1,30

Ввод x[i]

Конец

Рисунок 1. Блок схема алгоритма ввода массива

1. Ввод массива с использованием цикла с постусловием

Программный код:
Program Primer;
Var i: integer;
     X: array [1..30] of Integer;
Begin
     i := 1;
     While i <= 30 Do
         Begin
            Read (X[i]); 
            i := i + 1;
          End;
       Readln
End

Блок схема алгоритма ввода массива представлена на рисунке 2:

Начало

Конец

i:=1

i<=30

Ввод x[i]

i:=i+1

Да

Нет

Рисунок 2. Блок схема алгоритма ввода массива( 2 способ)

Можно ввести с клавиатуры элементы следующим образом: -7 _ 4 _ -2 _ 0 _ 12 _ -1 _ -5 _  9 _ 11 _ -3 _ -5 _ … _15, то есть через пробел ввести в строчку и нажать клавишу Enter.

Можно было ввести элементы в столбец, отделяя элементы клавишей Enter, то есть каждый элемент с новой экранной строки:

-7 Enter

4 Enter

-2 Enter

....

15 Enter

Вывод одномерного массива

Вывод одномерного массива осуществляется аналогично. В программе вместо операторов Read или Readln используются операторы Write или Writeln. Но просто заменить одни операторы на другие здесь недостаточно. Для того чтобы выводимые значения не сливались между собой, надо явным образом вставлять между ними разделитель – пробел или перевод строки.

Рассмотрим два варианта вывода массива:

For i := 1 To n Do Write (X[i],’ ‘);

---

For i := 1 To n Do Writeln (x[i]).

Пример для приведенных двух вариантов вывода массива выглядят так:

Выведем одномерный массив Х1, Х2, …, Хn, состоящий из 30 элементов целого типа (30 единиц), используя цикл с параметром.

Программный код выгладит таким образом:

Program Primer;
Const n = 30;
Var i: Integer;
     X: Array [1..n] Of Integer;
Begin
        For i:=1 to n do x[i]:=1;
        For i:= 1 To n Do Write (X[i]);
        Writeln; {курсор переводит на новую строку}
        Readln;
End.

Блок схема алгоритма представлен на рисунке 3:

Начало

x[i]:=1

Ввод x[i]

i:=1,30

i:=1,30

Конец

Рисунок 3. Блок схема алгоритма вывода массива

Поиск максимального и минимального элементов массива

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

• • 1. сначала задаются переменные (max и min), в которые в результате выполнения алгоритма будут записаны соответственно максимальное и минимальное значения;
    2. следующим этапом происходит перебор массива. На каждом шаге происходит проверка «является ли данный элемент больше максимального или меньше минимального». Если условие истинно, то значение элемента массива присваивается соответствующей переменной;

Основной алгоритм выглядит следующим образом:

Max:= - 16000;

Min:= 16000;

For i:=1 to n do

begin

If mas[i]>max then max:=mas[i];

If mas[i]<min then min:=mas[i];

End;

Рассмотри ход выполнения.

В таблице представлен массив с элементами и их индексами.

9	-7	0	-10	Элементы
1	2	3	4	Индексы

Таблица 1 - Одномерный массив

В таблице 2 представлены шаги с объяснением действий.

	i =	Данные	Условие	Ответ	Действие
Шаг 1	1	Max=-32000 Min=32000 Mas[1] = 9	9 > -32000 9 < 32000	истина истина	Max=9 Min=9
Шаг 2	2	Max=9 Min=9 Mas[2]= - 7	-7 > 9 -7 < 0	ложь истина	Max=9 Min= - 7
Шаг 3	3	Max=9 Min= - 7 Mas[3]=0	0 > 9 0 < -7	ложь ложь	Max=9 Min= - 7
Шаг 4	4	Max=9 Min= - 7 Mas[4] = - 10	-10 > 9 - 10 < -7	ложь истина	Max=9 Min= - 10

---

Таблица 2 - Описание шагов алгоритма

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

Сортировкой называется процесс упорядочивания набора данных одного типа по возрастанию или убыванию значения какого-либо признака.

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

1. Так как в отсортированных массивах осуществить поиск необходимой информации значительно быстрее по сравнению с несортированными, то сортировка массивов является значимым действием в системах сбора и поиска информации.
2. Алгоритмов по сортировке много и основное их отличие это скорость работы;
3. Способы, обладающие максимальной скоростью сортировки дают огромный выигрыш на больших массивах, которые могут содержать до тысячи элементов, но для малых массивов можно применять способы по проще.

Рассмотрим способы сортировки:

• • 1. Линейная сортировка (сортировка отбором)

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

• • 1. Сортировка методом «пузырька»

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

• • 1. Метод быстрой сортировки с разделением.

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

Примеры задач с одномерным массивами

1. Задача 1. Сформировать одномерный массив из N элементов, где элементы массива- целые случайные числа в пределах от 1 до 45. Напечатать элементы массива в прямом и обратном порядке.

Рассмотрим решение. Для получения случайных чисел воспользуемся следующей функцией: функция Random [(x)], которая формирует случайное число от 0 до X целого или вещественного типа (перед обращением к функции ее целесообразно инициализировать, использовав процедуру Randomize).
X - параметр, несущий информацию о диапазоне значений случайного числа, изменяющегося в пределах 0 до X. Результат в этом случае имеет тип число в диапазоне значений - 0...65535. Если параметр X не задан, результат будет типа Real в пределах 0.0 <Х< 1.0. Для получения массива целых

---