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

Материал из Вики ИТ мехмата ЮФУ
Перейти к: навигация, поиск
(Массивы)
(Массивы)
 
(не показано 14 промежуточных версий 3 участников)
Строка 1: Строка 1:
 
[[Категория:Основы программирования]]
 
[[Категория:Основы программирования]]
 +
[[Страница курса Основы программирования|К основной странице курса]]
 
== Массивы ==
 
== Массивы ==
 
=== Введение ===
 
=== Введение ===
Строка 44: Строка 45:
  
 
=== Динамические массивы ===
 
=== Динамические массивы ===
 +
Динамическим называется массив, память под который выделяется в процессе работы программы.
 +
В pascalABC.NET имеются встроенные динамические массивы, которые описываются следующим образом:
 +
<source lang="Delphi">var a: array of integer;</source>
 +
 +
Динамические массивы индексируются с нуля, тип индекса - только целое.
 +
 +
==== Выделение памяти ====
 +
Для выделения памяти динамическому массиву имеется два варианта. Объектный стиль:
 +
<source lang="Delphi">a := new integer[n];</source>
 +
Процедурный стиль:
 +
<source lang="Delphi">SetLength(a,n);</source>
 +
Здесь n может быть не только константой, но и переменной.
 +
 +
В обоих случаях элементы массивов заполняются нулями.
 +
 +
До выделения памяти в переменной-динамическом массиве хранится специальное значение nil. Присваивание nil переменной-массиву приводит к освобождению памяти, им занимаемой:
 +
<source lang="Delphi">a := nil;</source>
 +
 +
При попытке использования неинициализированного динамического массива выдается исключение времени выполнения "System.NullReferenceException: Ссылка на объект не указывает на экземпляр объекта."
 +
 +
==== Перевыделение памяти ====
 +
В процессе работы можно изменить память, занимаемую динамическим массивом. Для этого следует повторно вызвать SetLength:
 +
<source lang="Delphi">var a : array of integer;
 +
SetLength(a,3);
 +
a[0] := 1;
 +
a[1] := 3;
 +
a[2] := 2;
 +
SetLength(a,4);
 +
writeln(a[0]); // выведется 1
 +
</source>
 +
 +
При этом старое содержимое массива будет сохранено.
 +
 +
==== Длина массива ====
 +
Чтобы узнать количество элементов в динамическом массиве, следует воспользоваться функцией Length:
 +
<source lang="Delphi">Length(a)</source>
 +
или свойством Length:
 +
<source lang="Delphi">a.Length</source>
 +
Таким образом, элементы динамического массива:
 +
<source lang="Delphi">a[0],...,a[a.Length-1]</source>
  
 
=== Циклы по массиву ===
 
=== Циклы по массиву ===
 +
<source lang="Delphi">for var i:=0 to a.Length-1 do
 +
  write(a[i],' ');</source>
 +
 +
или с помощью цикла foreach (для каждого)
 +
<source lang="Delphi">
 +
foreach x: integer in a do
 +
  write(x,' ');</source>
 +
В цикле foreach доступ к элементам массива осуществляется только на чтение.
  
 
=== Инициализация массивов ===
 
=== Инициализация массивов ===
 +
Элементы массива можно инициализировать при описании:
 +
<source lang="Delphi">
 +
var a: array of string:= ('Иванов','Петров','Сидорова');</source>
 +
При этом под массив автоматически выделится память: в данном случае под 3 элемента.
  
 
=== Хранение массивов в памяти ===
 
=== Хранение массивов в памяти ===
Строка 79: Строка 132:
  
 
=== Массив как возвращаемое значение функции ===
 
=== Массив как возвращаемое значение функции ===
Часто требуется использовать массив как возвращаемое значение функции, для этого удобно использовать динамический массив, который хранит свою дли
+
Часто требуется использовать массив как возвращаемое значение функции, для этого удобно использовать динамический массив, который хранит свою длину.
  
=== Переменное число параметров подпрограмм ===
+
== Переменное число параметров подпрограмм ==
 
П/п можно создавать с переменным количеством параметров.
 
П/п можно создавать с переменным количеством параметров.
 
Для этого исп. ключевое слово params.
 
Для этого исп. ключевое слово params.
Строка 87: Строка 140:
 
Пар-р params может быть только один и должен находиться последним в списке пар-ов.
 
Пар-р params может быть только один и должен находиться последним в списке пар-ов.
  
=== Шаблоны подпрограмм ===
+
== Обобщенные подпрограммы ==
 
 
=== Задачи на одномерные массивы ===
 
 
 
=== Сортировки массивов ===
 
<h4> Сортировка выбором </h4>
 
 
 
<h4> Пузырьковая сортировка </h4>
 
 
 
<h4> Сортировка вставками </h4>
 
 
 
=== Асимптотическая оценка количества шагов алгоритма ===
 
 
 
=== Бинарный поиск в отсортированном массиве ===
 
 
 
=== Задачи на двумерные массивы (матрицы) ===
 
 
 
==Шаблоны подпрограмм==
 
 
 
 
Часто требуется выполнять одно и то же действие для разных типов данных.
 
Часто требуется выполнять одно и то же действие для разных типов данных.
 
В этом случае неудобно использовать перегрузку, т.к. п/п отличаются только заголовками.
 
В этом случае неудобно использовать перегрузку, т.к. п/п отличаются только заголовками.
  
Выход - шаблоны.
+
Выход - обобщенные подпрограммы.
  
 
Пример:
 
Пример:
Строка 122: Строка 157:
 
Если для такого типа код уже инстанцировался, то повторно действие не выполняется.
 
Если для такого типа код уже инстанцировался, то повторно действие не выполняется.
  
==Задачи на одномерные массивы==
+
== Массивы (продолжение) ==
 
+
=== Задачи на одномерные массивы ===
 
* инвертирование массива (шаблон)
 
* инвертирование массива (шаблон)
 
* поиск элемента в массиве - найти и вернуть индекс (шаблон)
 
* поиск элемента в массиве - найти и вернуть индекс (шаблон)
Строка 138: Строка 173:
 
знакомство со значением default(T), Т - тип
 
знакомство со значением default(T), Т - тип
  
<small>'''Лекция 19'''</small>
+
Задачи на одномерные массивы
 
 
<h3>Задачи на одномерные массивы</h3>
 
  
 
pas-файл с задачами
 
pas-файл с задачами
Строка 156: Строка 189:
 
* вставка элемента по заданному индексу (Insert)
 
* вставка элемента по заданному индексу (Insert)
  
<H3>Задачи с процедурными переменными в качестве параметров</H3>
+
<h4> Задачи с процедурными переменными в качестве параметров </h4>
  
 
Определяется тип IUnPred = function (x: integer): boolean
 
Определяется тип IUnPred = function (x: integer): boolean
Строка 167: Строка 200:
 
'''Примечание.''' Для проверки выхода индекса за границы диапазона (внутри цикла) следует проверять граничные значения счетчика, подставляя их во все индексы
 
'''Примечание.''' Для проверки выхода индекса за границы диапазона (внутри цикла) следует проверять граничные значения счетчика, подставляя их во все индексы
  
<small>'''Лекция 20'''</small>
+
=== Сортировки массивов ===
 +
<h4> Сортировка выбором </h4>
  
==Сортировки==
+
<h4> Пузырьковая сортировка </h4>
 +
 
 +
<h4> Сортировка вставками </h4>
  
 
* '''Выбором''' (нахождение минимального элемента в неупорядоченной части массива и перемещение его на первую после уже отсортированного участка позицию)  
 
* '''Выбором''' (нахождение минимального элемента в неупорядоченной части массива и перемещение его на первую после уже отсортированного участка позицию)  
Строка 180: Строка 216:
  
 
'''Замечание.''' Рассмотренные виды сортировки не являются самыми эффективными.
 
'''Замечание.''' Рассмотренные виды сортировки не являются самыми эффективными.
Асимптотическая сложность алгоритмов
 
  
 +
=== Асимптотическая оценка количества шагов алгоритма ===
 
'''Определение.''' Число шагов алгоритма асимптотически равно  Θ(f(n)) если, существуют такие N, с1, с2>0 (c1<c2), что для любых n ≥ N выполняется:
 
'''Определение.''' Число шагов алгоритма асимптотически равно  Θ(f(n)) если, существуют такие N, с1, с2>0 (c1<c2), что для любых n ≥ N выполняется:
  
Строка 190: Строка 226:
 
'''Замечание 2.''' Существуют алгоритмы сортировки с асимптотической сложностью = Θ(n*logn) (они будут рассмотрены в следующем семестре).
 
'''Замечание 2.''' Существуют алгоритмы сортировки с асимптотической сложностью = Θ(n*logn) (они будут рассмотрены в следующем семестре).
  
<small>'''Лекция 21'''</small>
+
=== Бинарный поиск в отсортированном массиве ===
==Алгоритм бинарного поиска в отсортированном массиве==
 
  
Его асимптотическая сложность - Θ(logn).
+
=== Задачи на двумерные массивы (матрицы) ===
Двумерные массивы
 
 
 
Двумерный массив как матрица (соответствие индексов строкам и столбцам)
 
 
 
Элементы строки. Элементы столбца (рисунки)
 
 
 
Понятие замороженного индекса
 
 
 
<H3>Задачи на двумерные массивы</H3>
 
  
 
* Вывод матрицы  
 
* Вывод матрицы  
Строка 218: Строка 244:
  
 
* Квадратные матрицы и элементы выше-ниже главной (побочной) диагонали.
 
* Квадратные матрицы и элементы выше-ниже главной (побочной) диагонали.
 
<small>'''Лекция 22'''</small>
 
  
 
* Поиск элемента в матрице
 
* Поиск элемента в матрице

Текущая версия на 08:18, 2 сентября 2013

К основной странице курса

Содержание

Массивы

Введение

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

Пример.

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+}

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

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

var a: array of integer;

Динамические массивы индексируются с нуля, тип индекса - только целое.

Выделение памяти

Для выделения памяти динамическому массиву имеется два варианта. Объектный стиль:

a := new integer[n];

Процедурный стиль:

SetLength(a,n);

Здесь n может быть не только константой, но и переменной.

В обоих случаях элементы массивов заполняются нулями.

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

a := nil;

При попытке использования неинициализированного динамического массива выдается исключение времени выполнения "System.NullReferenceException: Ссылка на объект не указывает на экземпляр объекта."

Перевыделение памяти

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

var a : array of integer;
SetLength(a,3);
a[0] := 1;
a[1] := 3;
a[2] := 2;
SetLength(a,4);
writeln(a[0]); // выведется 1

При этом старое содержимое массива будет сохранено.

Длина массива

Чтобы узнать количество элементов в динамическом массиве, следует воспользоваться функцией Length:

Length(a)

или свойством Length:

a.Length

Таким образом, элементы динамического массива:

a[0],...,a[a.Length-1]

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

for var i:=0 to a.Length-1 do
  write(a[i],' ');

или с помощью цикла foreach (для каждого)

foreach x: integer in a do
  write(x,' ');

В цикле foreach доступ к элементам массива осуществляется только на чтение.

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

Элементы массива можно инициализировать при описании:

var a: array of string:= ('Иванов','Петров','Сидорова');

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

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

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

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

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

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

  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. Для рассмотренных алгоритмов сортировки асимптотическая сложность = Θ(n2).

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

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

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

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

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

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

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

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