Основы программирования — Осенний семестр; Михалкович С.С.; 2008; VI — различия между версиями

Версия 08:33, 2 сентября 2011

Массивы

Введение

Массивом называется совокупность данных одного типа, каждое из которых имеет свой номер, называемый индексом.
Индексов может быть несколько. Такие массивы называются многомерными (с одним индексом — одномерными соответственно).

Пример.

var 
  a: array[1..10] of real;
  b: array[2..5, 'a'..'z'] of integer;

Как и диапазонный тип, индексы могут иметь типы:

• целый
• символьный
• перечислимый

Кроме того, в качестве индекса может выступать порядковый тип, например:

var c: array[Marks, Letters] of integer;

Обращение к элементам массивов

Чтобы обратиться к элементу массива, нужно использовать конструкцию

<массив>[<индекс>]

var 
  a: array[1..10] of integer;
  b: array[2..5, Mon..Sun] of string;

begin
  a[3] := 666;
  b['x', Tue] := 'zzz';
  
  a[11] := 0; // Ошибка выполнения — выход за границы изменения индекса
end.

В некоторых компиляторах можно специальными директивами отключить проверку выхода за границы диапазона, это увеличивает скорость выполнения.
В PascalABC.NET проверка выполняется всегда. А вот в Delphi и Free Pascal существует соответствующая директива

{$R-}
{$R+}

Динамические массивы

Описание: var a: array of integer;

Память под динамические массивы выделяется в процессе работы программы, т.е.динамически. Для выделения памяти используются следующие конструкции: a := new integer[10]; или SetLength(a,10);

Циклы по массиву

Инициализация массивов

Хранение массивов в памяти

Присваивание и сравнение массивов

Именная и структурная эквивалентность типов

Передача массивов в качестве параметров подпрограмм

При передаче статического массива должна соблюдаться именная эквивалентность

  procedure xxx(a: array [1..100] of integer); // неверно
 
  type IArr = array [1..100] of integer;
  procedure yyy(a: IArr);

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

  procedure zzz(const a: IArr);
  procedure sss(var a: IArr);

Динамический массив можно передавать в виде array of integer, т.к. для него определена структурная эквивалентность типов.

  procedure ttt(a: array of integer);

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

Массив как возвращаемое значение функции

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

Переменное число параметров подпрограмм

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

Шаблоны подпрограмм

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

Выход - шаблоны.

Пример:

 procedure Print<T> (array of T);

В момент вызова п/п происходит:

• выведение типов шаблона по фактическим параметрам
• инстанцирование - подстановка конкретных типов шаблонов и генерация кода подпрограммы с этими конкретными типами.

Если для такого типа код уже инстанцировался, то повторно действие не выполняется.

Массивы (продолжение)

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

• инвертирование массива (шаблон)
• поиск элемента в массиве - найти и вернуть индекс (шаблон)

можно с for и break,

можно и другим способом - с while

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

знакомство со значением default(T), Т - тип

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

pas-файл с задачами

doc-файл

используется тип IArr = array [1..size] of integer

• сдвиг элементов массива вправо (ShiftRight)

[ два варианта определения граничных значений цикла (от n-1 до 1; от n до 2) ]

• циклический сдвиг элементов массива вправо (CycleShiftRight)
• удаление элемента по заданному индексу (Delete)
• вставка элемента по заданному индексу (Insert)

Задачи с процедурными переменными в качестве параметров

Определяется тип IUnPred = function (x: integer): boolean

• поиск элемента по заданному условию (Find)
• количество элементов, удовлетворяющих условию (Count)
• условный минимум (MinElem)
• удаление всех элементов, удовлетворяющих условию (DeleteAll)

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

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

Сортировка выбором

Пузырьковая сортировка

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

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

• Пузырьковая

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

• Вставками (вставка элемента из еще не упорядоченного участка массива в "нужную" позицию отсортированного, для чего сдвиг части элементов вправо и вставка нового в освободившуюся позицию)

Замечание. Рассмотренные виды сортировки не являются самыми эффективными.

Асимптотическая оценка количества шагов алгоритма

Определение. Число шагов алгоритма асимптотически равно Θ(f(n)) если, существуют такие N, с1, с2>0 (c1<c2), что для любых n ≥ N выполняется:

   c1*f(n) ≤ число шагов ≤ c2*f(n)

Замечание 1. Для рассмотренных алгоритмов сортировки асимптотическая сложность = Θ(n²).

Замечание 2. Существуют алгоритмы сортировки с асимптотической сложностью = Θ(n*logn) (они будут рассмотрены в следующем семестре).

Бинарный поиск в отсортированном массиве

Задачи на двумерные массивы (матрицы)

• Вывод матрицы
  • внешний цикл по строкам
  • если внешним сделать цикл по столбцам будет выведена транспонированная матрица

• Сумма элементов в j-том столбце

• Сумма элементов в каждом столбце
  • использование функции для нахождения суммы в j-ом столбце
• Минимальный элемент в каждой строке
  • в отличие от предыдущей задачи, для реализации не создается дополнительная п/п.

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

• Квадратные матрицы и элементы выше-ниже главной (побочной) диагонали.

• Поиск элемента в матрице

если для поиска используется функция, то при нахождении элемента выходить из циклов с помощью exit,

иначе удобно использовать goto КОНЕЦ_ВНЕШНЕГО_ЦИКЛА