Массивы. Поиск элемента в массиве

Массивы
Строки
Записи и таблицы
Множества
Динамические массивы
Постановка задачи поиска элемента в массиве
Алгоритмы поиска:
последовательный поиск;
двоичный

Рассмотрим статические структуры данных:
массивы,
записи,
множества.
Цель описания типа данных

1. Массивы

Массив – это поименованная совокупность однотипных элементов, упорядоченных по индексам, определяющих

Количество используемых индексов определяет размерность массива.
Массив может быть
одномерным (вектор),

В Паскале определены такие операции над массивами в целом,
как сравнение

Можно также выполнять операции над отдельными элементами массива.
Перечень таких операций

2. Строки

Строка – это последовательность символов (элементов символьного типа).
В Паскале количество символов

Каждый символ строки имеет свой индекс, принимающий значение от 1 до

Однако есть ряд отличий:
операций сравнения строк больше, чем аналогичных операций

3. Записи и таблицы

Запись – это агрегат, составляющие которого (поля) имеют имя и могут

В Паскале определена операция присваивания для записей в целом (записи должны

Таблица представляет собой одномерный массив (вектор), элементами которого являются записи.
Отдельная запись

Характерной особенностью таблиц является то, что доступ к элементам таблицы производится

Если последовательность записей упорядочена относительно какого-либо столбца (поля), то такая таблица

Перечень операций над отдельной ячейкой определяется типом ячейки:

PersonList[1].Index := 190000;
PersonList[1].Name :=

4. Множества

Наряду с массивами и записями существует еще один структурированный тип –

Тип множество соответствует математическому понятию множества в смысле операций, которые допускаются

Множества, так же как и массивы, объединяют однотипные элементы. Поэтому в

В отличие от массивов и записей в множестве отсутствует возможность обращения

В Паскале в качестве типов элементов множества могут использоваться типы, максимальное

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

При работе с массивами практически всегда возникает задача настройки программы на

Первый вариант – использование констант для задания размерности массива.

Program first;
const

Второй вариант – программист планирует некоторое условно максимальное (теоретическое) количество элементов,

Program second;
var a : array [1..25] of real;
i,

Вариант третий – в нужный момент времени надо выделить динамическую память

Program dynam_memory;
type mas = array[1..2] of <требуемый_тип_элемента>;
ms = ^mas;
var

Где нужны динамические массивы?

Задача. Ввести размер массива, затем – элементы массива.

© С.В.Кухта, 2010

Использование указателей

program qq;
type intArray = array[1..1] of integer;
var A:

Использование указателей

для выделения памяти используют процедуру
GetMem( указатель, размер в байтах

6. Постановка задачи поиска элемента в массиве

Поиск в массиве

Одно из наиболее часто встречающихся в программировании действий –

Пусть A = {a1, a2, ...} – последовательность однотипных элементов и

Поскольку представление последовательности в памяти может быть осуществлено в виде массива,

Максимальный элемент

Задача: найти в массиве максимальный элемент.
Алгоритм:

Псевдокод:

{ считаем, что первый

Максимальный элемент

max := a[1]; { считаем, что первый – максимальный }
iMax

© С.В.Кухта, 2009

program qq;
const N = 5;
var a: array [1..N] of

При дальнейшем рассмотрении делается принципиальное допущение:
группа данных, в которой необходимо

Задача заключается в поиске элемента, ключ которого равен заданному «аргументу поиска»

С точки зрения теории множеств поиск можно рассматривать, как
отображение множества

Алгоритм поиска может
возвратить элемент массива (или всю найденную запись массива)
или

Поиск, по завершении которого найден элемент массива с ключом, равным аргументу

Однако возможно, что поиск некоторого конкретного аргумента в массиве является неудачным

Поиск требуемой информации применяется ко всем основным структурам данных с произвольным

Задача – найти в массиве элемент, равный x, или установить, что

7. Алгоритмы поиска элемента
в массиве

Нахождение информации в неотсортированной структуре данных, например в массиве, требует применения

Линейный поиск

nX := 0;
for i:=1 to N do
if A[i] =

Рассмотрим примеры последовательного поиска с циклами for и while.

Функции линейного

Функции линейного поиска

function search_s1(A: Mas; N: integer; key: Item):
integer;
var

Функции линейного поиска

function search_s2(A: Mas; N: integer; key: Item):
integer;
var

Последовательный поиск выполнит
в среднем случае проверку N/2 элементов,
в лучшем

Недостаток этого поиска:
медленное выполнение при большом объеме просматриваемого массива.
Но

Двоичный (или бинарный) поиск основан на итерационном сравнении ключа поиска с

При каждой итерации находится середина текущей анализируемой части,
т.е. интервал анализа

Двоичный поиск

X = 7

X < 8

8

4

X > 4

6

X > 6

Выбрать средний

Двоичный поиск

nX := 0;
L := 1; R :=

Этот метод поиска значительно эффективнее чем последовательный поиск, но требует, чтобы