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

Материал из Вики ИТ мехмата ЮФУ
Перейти к: навигация, поиск
(Массивы)
 
(не показано 16 промежуточных версий 3 участников)
Строка 1: Строка 1:
 
[[Категория:Основы программирования]]
 
[[Категория:Основы программирования]]
==Массивы==
+
[[Страница курса Основы программирования|К основной странице курса]]
 +
== Массивы ==
 +
=== Введение ===
 +
:'''Массивом''' называется совокупность данных одного типа, каждое из которых имеет свой номер, называемый '''''индексом'''''. <br />Индексов может быть несколько. Такие массивы называются '''''многомерными''''' (с одним индексом — '''''одномерными''''' соответственно).
  
Понятие структурированного типа данных.
+
''<u>Пример</u>.''
 +
<source lang="Pascal">
 +
var
 +
  a: array[1..10] of real;
 +
  b: array[2..5, 'a'..'z'] of integer;
 +
</source>
 +
 
 +
Как и диапазонный тип, индексы могут иметь типы:
 +
* целый
 +
* символьный
 +
* перечислимый
 +
 
 +
Кроме того, в качестве индекса может выступать порядковый тип, например:
 +
<source lang="Pascal">
 +
var c: array[Marks, Letters] of integer;
 +
</source>
 +
 
 +
=== Обращение к элементам массивов ===
 +
Чтобы обратиться к элементу массива, нужно использовать конструкцию
 +
<массив>[<индекс>]
 +
 
 +
<source lang="Pascal">
 +
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.
 +
</source>
 +
 
 +
В некоторых компиляторах можно специальными директивами отключить проверку выхода за границы диапазона, это увеличивает скорость выполнения. <br />
 +
В ''PascalABC.NET'' проверка выполняется ''всегда''. А вот в Delphi и Free Pascal существует соответствующая директива
 +
'''{$R-}'''
 +
'''{$R+}'''
 +
 
 +
=== Динамические массивы ===
 +
Динамическим называется массив, память под который выделяется в процессе работы программы.
 +
В 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 может быть не только константой, но и переменной.
  
<small>'''Лекция 16'''</small>
+
В обоих случаях элементы массивов заполняются нулями.
  
Обращение к элементам массивов.
+
До выделения памяти в переменной-динамическом массиве хранится специальное значение nil. Присваивание nil переменной-массиву приводит к освобождению памяти, им занимаемой:
 +
<source lang="Delphi">a := nil;</source>
  
Выход за границы диапазона. Контроль выхода в Delphi и PascalABC.NET.
+
При попытке использования неинициализированного динамического массива выдается исключение времени выполнения "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>
  
Присваивание a := nil для динамических массивов.
+
=== Циклы по массиву ===
 +
<source lang="Delphi">for var i:=0 to a.Length-1 do
 +
  write(a[i],' ');</source>
  
Цикл foreach.
+
или с помощью цикла foreach (для каждого)
 +
<source lang="Delphi">
 +
foreach x: integer in a do
 +
  write(x,' ');</source>
 +
В цикле foreach доступ к элементам массива осуществляется только на чтение.
  
Именная и структурная эквивалентность типов.
+
=== Инициализация массивов ===
 +
Элементы массива можно инициализировать при описании:
 +
<source lang="Delphi">
 +
var a: array of string:= ('Иванов','Петров','Сидорова');</source>
 +
При этом под массив автоматически выделится память: в данном случае под 3 элемента.
  
<small>'''Лекция 17'''</small>
+
=== Хранение массивов в памяти ===
<H3>Массивы как параметры подпрограмм</H3>
 
  
 +
=== Присваивание и сравнение массивов ===
 +
 +
=== Именная и структурная эквивалентность типов ===
 +
 +
=== Передача массивов в качестве параметров подпрограмм ===
 
При передаче статического массива должна соблюдаться именная эквивалентность
 
При передаче статического массива должна соблюдаться именная эквивалентность
 
<source lang="delphi">
 
<source lang="delphi">
Строка 50: Строка 130:
 
Передавать массив по ссылке необходимо только если внутри п/п нужно изменить длину массива.
 
Передавать массив по ссылке необходимо только если внутри п/п нужно изменить длину массива.
 
Иначе можно передавать по значению, т.к. при вызове п/п на программный стек кладется только адрес участка памяти, хранящего значения элементов массива, а значит все изменения формального массива-параметра внутри п/п меняют соответствующий ему фактический параметр.
 
Иначе можно передавать по значению, т.к. при вызове п/п на программный стек кладется только адрес участка памяти, хранящего значения элементов массива, а значит все изменения формального массива-параметра внутри п/п меняют соответствующий ему фактический параметр.
Массивы как возвращаемые значения функции
 
  
 +
=== Массив как возвращаемое значение функции ===
 
Часто требуется использовать массив как возвращаемое значение функции, для этого удобно использовать динамический массив, который хранит свою длину.
 
Часто требуется использовать массив как возвращаемое значение функции, для этого удобно использовать динамический массив, который хранит свою длину.
  
<h3>Переменное число параметров подпрограмм</h3>
+
== Переменное число параметров подпрограмм ==
 
 
 
П/п можно создавать с переменным количеством параметров.
 
П/п можно создавать с переменным количеством параметров.
 
Для этого исп. ключевое слово params.
 
Для этого исп. ключевое слово params.
Строка 61: Строка 140:
 
Пар-р params может быть только один и должен находиться последним в списке пар-ов.
 
Пар-р params может быть только один и должен находиться последним в списке пар-ов.
  
<small>'''Лекция 18'''</small>
+
== Обобщенные подпрограммы ==
==Шаблоны подпрограмм==
 
 
 
 
Часто требуется выполнять одно и то же действие для разных типов данных.
 
Часто требуется выполнять одно и то же действие для разных типов данных.
 
В этом случае неудобно использовать перегрузку, т.к. п/п отличаются только заголовками.
 
В этом случае неудобно использовать перегрузку, т.к. п/п отличаются только заголовками.
  
Выход - шаблоны.
+
Выход - обобщенные подпрограммы.
  
 
Пример:
 
Пример:
Строка 80: Строка 157:
 
Если для такого типа код уже инстанцировался, то повторно действие не выполняется.
 
Если для такого типа код уже инстанцировался, то повторно действие не выполняется.
  
==Задачи на одномерные массивы==
+
== Массивы (продолжение) ==
 
+
=== Задачи на одномерные массивы ===
 
* инвертирование массива (шаблон)
 
* инвертирование массива (шаблон)
 
* поиск элемента в массиве - найти и вернуть индекс (шаблон)
 
* поиск элемента в массиве - найти и вернуть индекс (шаблон)
Строка 96: Строка 173:
 
знакомство со значением default(T), Т - тип
 
знакомство со значением default(T), Т - тип
  
<small>'''Лекция 19'''</small>
+
Задачи на одномерные массивы
 
 
<h3>Задачи на одномерные массивы</h3>
 
  
 
pas-файл с задачами
 
pas-файл с задачами
Строка 114: Строка 189:
 
* вставка элемента по заданному индексу (Insert)
 
* вставка элемента по заданному индексу (Insert)
  
<H3>Задачи с процедурными переменными в качестве параметров</H3>
+
<h4> Задачи с процедурными переменными в качестве параметров </h4>
  
 
Определяется тип IUnPred = function (x: integer): boolean
 
Определяется тип IUnPred = function (x: integer): boolean
Строка 125: Строка 200:
 
'''Примечание.''' Для проверки выхода индекса за границы диапазона (внутри цикла) следует проверять граничные значения счетчика, подставляя их во все индексы
 
'''Примечание.''' Для проверки выхода индекса за границы диапазона (внутри цикла) следует проверять граничные значения счетчика, подставляя их во все индексы
  
<small>'''Лекция 20'''</small>
+
=== Сортировки массивов ===
 +
<h4> Сортировка выбором </h4>
  
==Сортировки==
+
<h4> Пузырьковая сортировка </h4>
 +
 
 +
<h4> Сортировка вставками </h4>
  
 
* '''Выбором''' (нахождение минимального элемента в неупорядоченной части массива и перемещение его на первую после уже отсортированного участка позицию)  
 
* '''Выбором''' (нахождение минимального элемента в неупорядоченной части массива и перемещение его на первую после уже отсортированного участка позицию)  
Строка 138: Строка 216:
  
 
'''Замечание.''' Рассмотренные виды сортировки не являются самыми эффективными.
 
'''Замечание.''' Рассмотренные виды сортировки не являются самыми эффективными.
Асимптотическая сложность алгоритмов
 
  
 +
=== Асимптотическая оценка количества шагов алгоритма ===
 
'''Определение.''' Число шагов алгоритма асимптотически равно  Θ(f(n)) если, существуют такие N, с1, с2>0 (c1<c2), что для любых n ≥ N выполняется:
 
'''Определение.''' Число шагов алгоритма асимптотически равно  Θ(f(n)) если, существуют такие N, с1, с2>0 (c1<c2), что для любых n ≥ N выполняется:
  
Строка 148: Строка 226:
 
'''Замечание 2.''' Существуют алгоритмы сортировки с асимптотической сложностью = Θ(n*logn) (они будут рассмотрены в следующем семестре).
 
'''Замечание 2.''' Существуют алгоритмы сортировки с асимптотической сложностью = Θ(n*logn) (они будут рассмотрены в следующем семестре).
  
<small>'''Лекция 21'''</small>
+
=== Бинарный поиск в отсортированном массиве ===
==Алгоритм бинарного поиска в отсортированном массиве==
 
  
Его асимптотическая сложность - Θ(logn).
+
=== Задачи на двумерные массивы (матрицы) ===
Двумерные массивы
 
 
 
Двумерный массив как матрица (соответствие индексов строкам и столбцам)
 
 
 
Элементы строки. Элементы столбца (рисунки)
 
 
 
Понятие замороженного индекса
 
 
 
<H3>Задачи на двумерные массивы</H3>
 
  
 
* Вывод матрицы  
 
* Вывод матрицы  
Строка 176: Строка 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 КОНЕЦ_ВНЕШНЕГО_ЦИКЛА