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

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

else if right(p) = nil
then v = left(p)
else
‘У nod(p) — два сына’
‘Введем два указателя (t отстает от v на 1 ‘шаг, s — опережает)
t = p
v = right(p)
s = left(v)
while s <> nil do
t = v
v = s
s = left(v)
endwhile
if t <> p then
‘v не является сыном p’
left(t) = right(v)
right(v) = right(p)
endif
left(v) = left(p)
endif
endif
if q = nil then ‘p — корень’
tree = v
else  if p = left(q)
then left(q) = v
else right(q) = v
endif
endif
freenode(p)
return

Паскаль:

q := nil;
p := tree;
while (p <> nil) and (p^.k <> key) do
begin
q := p;
if key < p^.k then
p := p^.left
else
p := p^.right;
end;
if p = nil then
WriteLn(‘Ключ не найден’);
exit;
end;
if p^.left = nil then
v := p^.right
else
if p^.right = nil then
v := p^.left
else
begin
{Введем два указателя (t отстает от v на 1 шаг, s — опережает)}
t := p;
v := p^.right;
s := v^.left;
while s <> nil do
begin
t := v;
v := s;
s := v^.left;
end;
if t <> p then
begin
WriteLn(‘v не является сыном p’);
t^.left := v^.right;
v^.right := p^.right;
end;
v^.left := p^.left;
end;
end;
if p = q^.left then
q^.left := v
else
q^.right := v;
end;
dispose(p);
end;

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

1.В чем состоит назначение поиска ?
2.Что такое уникальный ключ ?
3.Какая операция производится в случае отсутствия заданного ключа в списке ?
4.В чем разница между  последовательным  и  индексно-последовательным поиском ?
5.Какой из них более эффективный и почему ?
6.Какие способы переупорядочивания таблицы вы знаете ?
7.Основные отличия метода перестановки в начало от метода транспозиции .
8.Где они будут работать быстрее, в массиве или списке ?
9.В каких списках они работают, упорядоченных или нет ?
10.В чем суть бинарного поиска?
11.Как можно обойти бинарное дерево?
12.Можно ли применять бинарный поиск к массивам ?
13.Если удалить корень в непустом бинарном дереве, какой элемент станет на его место ?

6.  Сортировка

При обработке данных важно знать  информационное поле данных и размещение их в машине.
Различают внутреннюю и внешнюю сортировку:
— внутренняя сортировка — сортировка в оперативной памяти;
— внешняя сортировка — сортировка во внешней памяти.
Сортировка — это расположение данных в памяти в регулярном виде по их ключам. Регулярность рассматривают как возрастание (убывание) значения ключа от начала к концу в массиве.

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

Страницы: 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

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