7.1.13Поиск позиции элемента в отсортированном массиве

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

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

Функция, возвращающая номер позиции элемента в отсортированном массиве приведена ниже. Если элемент не найден, функция возвращает 0.

// Поиск позиции элемента в сортированом массиве

// x – элемент, позицию которого нужно найти

// а – упорядоченный массив, count – число элементов в нем

function FindPosInSortArray (x: integer; a: TArray100; count: integer): integer;

var pos, left, right: integer;

begin

// left и right – левая и правая границы области поиска

left := 1; right := count;

while left <= right do

begin

// Позиция в середине области поиска

pos:=(right + left) div 2;

if a[pos] = x then begin

{ элемент найден}

result := pos;

exit;

end;

if x < a[pos]

then right := pos – 1 { элемент находится слева}

else left := pos + 1; { элемент находится справа}

end;

// Элемент не найден

result := 0;

end;

7.1.14Удаление элемента из отсортированного массива

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

Процедура удаления элемента из отсортированного массива приведена ниже.

// Удаление элемента из отсортированного массива

// x – элемент, который нужно удалить

// а – упорядоченный массив, count – число элементов в нем

procedure DelFromSortArray (x: integer; var a: TArray100; var count: integer);

var i, pos, left, right: integer;

begin

pos := FindPosInSortArray (x,a,count);

if pos = 0 then exit;

count := count – 1;

for i := pos to count do a[i]:=a[i+1];

end;

Задание для самостоятельной работы

В лабораторной работе следует создать проект, в соответствии с требованиями варианта из таблицы 8.1. Номер варианта выбирается по последней цифре номера зачетной книжки.

Главное меню проекта должно включать следующие пункты:

• Создание массива

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

• Вставка элемента в массив

• Удаление элемента из массива

На форме должно быть поле для ввода количества элементов массива и поле для максимального значения числа в массиве (если тип элементов ±Real ).

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

Компоненты для хранения исходного массива и массива, получаемого в результате обработки, должны соответствовать варианту задания. Глобальные переменные для хранения массива и количества данных в нем использовать не следует. При выполнении каждого пункта меню всю необходимую информацию считывать с формы.

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

Таблица 8.1 – Задания на лабораторную работу
№	Создание исходного массива	Хране ние масс.	Тип данных массива	1-й уровень сортировки	2-й уровень сортировки	Метод сортировки
0	InputBox	TMemo	String	По длине строки на возрастание	По алфавиту	Вставкой
1	Random	Tedit	±Real	Отрицатель- ные, затем положительн.	На убывание	Обменом
2	InputBox	Tmemo	String	По длине строки на убывание	По алфавиту	Выбором
3	Random	Tedit	±Real	Положитель-ные, затем отрицател.	На возраста-ние	Вставкой
4	InputBox	Tmemo	String	По длине строки на убывание	С конца алфавита	Обменом
5	Random	Tedit	±Real			Выбором
6	InputBox	Tmemo	String	По длине строки на возрастание	С конца алфавита	Вставкой
7	Random	Tedit	±Real	Вначале большие 1 затем меньшие	На возраста-ние	Обменом
8	InputBox	TMemo	String	Слова с цифрами в конец	По алфавиту	Выбором
9	Random	TEdit	±Real	Вначале меньшие 1 затем большие	На убыва-ние	Вставкой

Содержание отчета

• Наименование работы

• Цель работы

• Краткое описание изученных методов сортировки массивов

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

• Результаты тестирования проекта в виде копий экранов

• Выводы

Контрольные вопросы

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

• Сортировка обменом

• Сортировка вставкой

• Вставка элемента в отсортированный массив

• Слияние отсортированных массивов.

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

• Удаление элемента из отсортированного массива

ЛАБОРАТОРНАЯ РАБОТА № 9. РАБОТА С ДВУМЕРНЫМИ МАССИВАМИ (МАТРИЦАМИ)

Цели работы:

• Познакомиться со способами описания матриц в Object Pascal.

• Освоить алгоритмы тотальной и выборочной обработки элементов матриц

• Освоить алгоритмы простейших преобразований матриц

• Освоить алгоритмы сортировки матриц

• Познакомиться с процедурным типом данных

Краткие теоретические сведения

Матрица – это тип данных, которому соответствует таблица. При работе с матрицами оперируют понятиями имя матрицы, столбец, номер столбца, строка, номер строки, элемент, размер матрицы, например 3 х 4.

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

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

В матрице, для идентификации элемента, требуется два индекса. Это как бы координаты элемента в матрице. При обращении к элементу его индексы указывают после имени матрицы в квадратных скобках, разделяя их запятой. Например, если имя матрицы matrix, то matrix[2,3] – это элемент матрицы с координатами 2 и 3. Какой из индексов определяет строку, а какой столбец - это решает программист. Мы будем далее считать, что первый индекс задает номер строки, а второй – номер столбца, и начинать нумерацию будем с 1. Так принято у математиков. Но у компонента StringGrid, который будет часто использоваться в этой лабораторной работе все наоборот, первый индекс – это номер столбца, второй индекс – это номер строки, и нумерация начинается с 0. Это пример плюрализма мнений. Постарайтесь не запутаться.

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