Понедельник, Июль 5th, 2010

Структуры и алгоритмы обработки данных

pelem = ^elem;
elem  = record
left : pointer;
right : pointer;
K : integer;
end;
K — элемент массива, V — указатель на созданный элемент.
В процедуре создания дерева бинарного поиска будут использованы следующие указатели :
tree — указатель на корень дерева;
p — рабочий указатель;
q — указатель отстающий на шаг от p;
key — новый элемент массива;

Создание дерева бинарного поиска :
(псевдокод)

writeln(‘ Введите элемент массива ‘);
readln(key);
tree:=maketree(key);
p:=tree;
while not eof do
begin
readln(key);
v:=maketree(key);
while p<>nil do
begin
q:=p;
if key<k(p) then p:=left(p)
else p:=right(p);
end;
if p=nil then
begin
writeln(‘Это корень’);
tree:=v;
end
else
if key<k(q) then left(p):=v
else right(p):=v;
end;

При обходе дерева слева — направо получаем отсортированный массив 20, 30, 35, 45, 60, 70, 82, 85, 86, 87, 88, 90. Элемент дерева заносится в массив при втором заходе в него (на рисунке вторые заходы показаны зелеными стрелками).

Обход дерева слева — направо
procedure InTree(tree);
begin
if Tree = nil then write(‘Дерево пусто’)
else
with Tree^ do
begin
if left<>nil then InTree(left);
if right<>nil then InTree(right);
end;
end;

Задания

Вариант 1: На заводе выпустили детали со следующими серийными номерами : 45, 56, 13, 75, 14, 18, 43, 11, 52, 12, 10, 36, 47, 9. Детали с четными номерами поступают на склад №1, а с нечетными на слад №2. Требуется отсортировать детали на складе №1.

Вариант 2 : Угнали автомобиль. Свидетель запомнил, что первой цифрой номера была 4. В базе угнанных автомобилей в этот день были следующие номера : 456, 124, 786, 435, 788, 444, 565, 127, 458, 322, 411, 531, 400, 546, 410. Нужно составить список номеров начинающихся на 4 и упорядочить его по возрастанию.

Вариант 3 : За неделю езды в транспорте накопились билеты с номерами  124512, 342351, 765891, 453122, 431350, 876432, 734626, 238651, 455734, 234987.  Нужно отобрать «счастливые» билеты и расположить их по возрастанию.

Вариант 4 : Дан список людей с указанием их возраста. Для составления графика ухода сотрудников на пенсию требуется составить новый список новый список в том порядке, в каком они будут уходить на пенсию.

Вариант 5 : Студенты сдали пять экзаменов. Нужно отсортировать список студентов по возрастанию общего балла по результатам сданных экзаменов.

Вариант 6 :  В городе был один автобусный парк, куда приезжали автобусы с номерами : 11, 32, 23, 12, 6, 52, 47, 63, 69, 50, 43, 28, 35, 33, 42, 56, 55, 101. После строительства второго автопарка решили перевести туда автобусы с нечетными номерами. Для того чтобы составить расписание их движения нужно организовать список номеров автобусов второго парка, упорядочив их по убыванию.

Вариант 7 : Была составлена ведомость по зарплате, представленная в виде : Иванов — 166000, Сидоров — 180000, … Требуется упорядочить этот список таким образом, чтобы размер зарплаты уменьшался.

Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

Категория: Учебники