Информатика -продвинутый курс


         

В этой связи выделяют сортировку


В этой связи выделяют сортировку двух классов объектов: массивов (внутреняя сортировка) и файлов (внешняя сортировка).

Процедура сортировки предполагает, что при наличии некоторой упорядочивающей функции F расположение элементов исходного множества меняется таким образом, что

a1, а2… аn > ak1, ak2…akn

F(ak1) < F(ak2) < F(akn)

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

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

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

var a:array[0..N] of item;

где item - заданный структурированный тип данных обладающий хотя бы одним полем (ключом), по которому необходимо проводить поиск.

Результатом поиска, как правило, служит элемент массива, равный эталону, или отсутствие такового.

Линейный поиск. Процедура заключается в простом последовательном просмотре всех элементов массива и сравнении их с эталоном X.

i:=0;

while (i<=N)and(a[i]<>X) do i:=i+1 end.

Часто бывает целесообразнее осуществлять поиск с барьером, вводя дополнительно граничный элемент массива a[N+l]:

a[N+l]:=X;i:=0;

while a[i]<>X do i:=i+l end.

Равенство i = N + 1 означает, что совпадений не было, т.е. что эталонный элемент отсутствует.

Попытайтесь разобраться в чем различие представленных конструкций. Приведем пример программы поиска эталона х в массиве а[0..n].

Программа 42

program poiskl; (*линейный поиск*) const

N=8;

type item= integer;

var a : array[0..n] of item; i :integer; x : item;

begin

(*задание

искомого массива*) for i:=0 to N do

begin writet'Bвeди элемент a[ ',i, ']= '); readln(a[i]);

end;

writeln; write('введи эталон x= '); readln(x);

(* линейный поиск*)

i:=0; while (i<=N)and(a[i]<>X) do begin i:=i+l end;

(*вывод результата*)

if i<=N then write( 'найден элемент на ',i, ' месте ') else write( 'такого элемента в массиве нет ') ;


Содержание  Назад  Вперед





Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий