Поиск элемента в массиве по ключу
Лабораторная работа № 12
Массивы
Цель работы: освоение приемов объявления, обращения и использования массивов при решении задач.
Массив представляет собой пример композитной структуры. Это означает, что он создан из более простых, уже существующих в языке структур данных. Изучение каждой композитной структуры предполагает анализ того, каким образом происходит организация такой структуры из более простых структур, а также того, каким образом из композитной структуры извлекаются его компоненты.
Простейшая форма массива - одномерный массив. Он может быть определен как конечный (фиксированный), упорядоченный набор однородных элементов. Под словом упорядочный понимается тот факт, что, все элементы массива упорядочены по номеру. Однородный, означает, что все элементы массива принадлежат одному и тому же типу данных. Примером модели однородного массива является вектор, коэффициент многочлена. Над одномерным массивом можно выполнять две базовые операции: извлечение элементов из массива и помещение элементов в массив. Массив - это структура произвольного доступа. Доступ к элементам осуществляется посредствам его номера. Номер элемента является его относительным адресом.
Типовые алгоритмы обработки массивов:
1. Определение количества элементов массива, удовлетворяющих заданному условию (<key).
2. Инвертирование массива.
3. Суммирование элементов массива, удовлетворяющих заданному условию(<key ).
|
|
|
4. Объединение двух массивов в один с чередованием элементов исходных массивов (размеры исходных массивов равны).
5. Формирование массива из элементов другого массива, удовлетворяющих заданному условию (<key).
6. Дан массив. Найти максимальный (минимальный) элемент и его номер.
7. Циклический сдвиг элементов массива вправо (влево) на m позиций.
8. Слияние двух упорядоченных массивов в один упорядоченный.
9. Сравнение двух упорядоченных по возрастанию (убыванию) массивов.
10. Сортировка выбором.
11. Линейный поиск (в произвольном массиве).
12. Линейный поиск в упорядоченном по возрастанию (убыванию) массиве.
13. Бинарный поиск (дихотомический) в отсортированных массивах.
Типовые алгоритмы обработки одномерных массивов
Рассмотрим некоторые типовые алгоритмы обработки массивов. Положим, что в декларативной части программы описаны следующие переменные: одномерные массивы А и В, переменные целого типа n, i и j и вспомогательные переменные типа элементов массива.
Суммирование элементов массива
Реализация:
s:=0;
for i:=1 to n do
s:=s+a[i];
writeln('Сумма элементов= ', s);
Суммирование элементов массива по ключу
|
|
|
Реализация:
s:=0;
writeln(‘ Введите ключ’);
readln( key);
for i:=1 to n do
if a[i]=key then s:=s+a[i];
writeln('Сумма элементов= ', s);
Подсчет элементов массива по ключу
Реализация:
kol:=0;
writeln(‘ Введите ключ’);
readln( key);
for i:=1 to n do
if a[i]=key then kol:=kol+1;
writeln('Количество элементов= ', kol);
Поиск минимального (максимального) элемента
Данный алгоритм заключается в следующем: вначале запоминаем номер первого элемента массива, принимая его за минимальный (максимальный) элемент. Далее, начиная со второго, все элементы сравниваются с предполагаемым минимумом (максимумом) и если какой-нибудь из них меньше (больше) предполагаемого минимума (максимума), то запоминается номер этого элемента. Эти действия повторяются до тех пор, пока не закончатся элементы массива. Ниже написан фрагмент программы для поиска минимального элемента. Для реализации алгоритма введем еще один объект программы n_min, переменную, в которой будет храниться номер минимального элемента.
Реализация:
writeln(‘ Введите количество элементов массива’);
readln(n);
write(' Введите элементы массива’);
for i:=1 to n do readln(a[i]);
{ Пусть первый элемент минимальный }
n_min:=1;
for i:=2 to n do
if a[i]<a[n_min] then n_min:=i;
|
|
|
writeln('Минимальный элемент массива: ', a[n_min]);
writeln('Номер элемента: ', n_min);
Формирование нового массива из элементов исходного массива
Для формирования нового массива из элементов исходного необходимо, прежде всего, подготовить переменную целого типа, которая будет, является индексом элементов для нового массива, и увеличивать значение номера элемента после того, как очередной элемент помещен в новый массив. Рассмотрим два алгоритма: формирование нового массива из элементов исходного массива, удовлетворяющих заданному условию (< key); слияние двух упорядоченных массивов в один упорядоченный.
Реализация:
{Формирование нового массива по ключу}
writeln(‘ Введите ключ’);
readln( key);
j:=0; {индекс нового массива}
For i:=1 to n do
If a[i] < key then
begin
j:=j+1;
b[j]:=a[i]
end;
{Печать сформированного массива}
for i:=1 to j do writeln(‘b[‘, i, ‘]= ’, b[i]);
Поиск элемента в массиве по ключу
Df: Процесс нахождения элемента в последовательности по значению одного или более чем одного поля называется поиском в последовательности. Линейный поиск заключается в последовательном просмотре всех элементов массива до тех пор пока либо будет найден искомый элемент, либо пока не закончатся элементы массива. Для реализации алгоритма заведем переменную логического типа flag, с помощью которой можно будет выйти из цикла в случае нахождения искомого элемента.
|
|
|
Реализация:
write(' Введите образец для поиска');
readln(key);
flag:=FALSE; {совпадений нет}
i:=1;
repeat
if a[i] = key then flag:=TRUE {совпадение с образцом}
else i:=i+1; {переход к следующему элементу}
until (i>n) or flag; {окончание цикла, если произошло совпадение с образцом или проверены все элементы массива}
if flag then writeln(' Совпадение с элементом номер которого = ', i)
else writeln(' Совпадений с образцом нет');
Инвертирование массива
Суть алгоритма, состоит в перестановке элементов массива в обратном порядке, т.е. меняет местами первый с последним элементом, второй с предпоследним элементом массива и т.д. Число перестановок равно n div 2, т.к. если менять местами элементы n раз, то все элементы массива встанут на свои места.
Реализация:
for i:=1 to n div 2 do
begin
{ Обменяем i-й и (n-i+1)-й элементы}
temp:=a[i];
a[i]:=a[n-i+1];
a[n-i+1]:=temp
end;
Дата добавления: 2021-03-18; просмотров: 621; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!