Пример

Меню

Главная

Статистика

Пример #2.

Сравните: при N=1000 последовательный поиск требует, в среднем, 500 шагов, а дихотомия - только 10.

Подведем промежуточные итоги. В отношении нескольких алгоритмов, обсуждавшихся в этой главе, можно сказать, что они применимы как для вектора, так и к массивам бОльших размерностей. Это относится к алгоритмам E1-1, E2-1, E2-2, - разве что понадобятся некоторые "косметические" изменения. Но вот алгоритм E3-1 явно использует отличительные особенности линейной структуры данных, каковой является вектор.

Рассмотрим еще несколько задач, типичных для обработки именно линейных массивов.

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

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

Алгоритм E3-2

Вызов процедуры ShiftRightArray, сдвигающей вправо на одну позицию значения всех компонент, начиная c k-й (0£k£N-1) ячейки; содержимое (N-1)-й ячейки теряется.
Запись в k-ю ячейку заданного значения Elem.

Приведем возможный вариант реализации алгоритма E3-2 на языке паскаль.

type
  index1 = 0..N-1; {N > 1}
  massive1 = array [index1] of item;

function Max (Mas: massive1; left, right: index1): item;
var i: index1; temp: item;
begin
  temp:= Mas[left];
  for i:= left+1 to right do
    if Mas[i] > temp then temp := Mas[i];
  Max := temp
end;
        
procedure ShiftRightArray (var Mas: massive1; ind: index1);
  {сдвиг значений вправо, начиная от позиции ind}
var i: index1;
begin
  for i:= N-1 downto ind do
    Mas[i] := Mas[i-1]
end; {ShiftRightArray}

procedure InsArray (var Mas: massive1; K: index1; Elem: item);
var i: index1;
begin
  ShiftRightArray (Mas, k);
  Mas[K] := Elem
end; {InsArray}
            
type
  index1 = 0..N-1; {N > 1}
  massive1 = array [index1] of item;

function Partition
  (var Mas: massive1; left, right: index1): index1;
var i, j: index1; barrier: item;
begin
  barrier := Mas[(left + right) div 2];
  i := left;
  j := right;
  repeat
    while (Mas[i] < barrier) do i := i+1;
    while (Mas[j] > barrier) do j := j-1;
    if i ? j then begin
      Swap{Mas[i], Mas[j]}; i := i+1; j:= j-1
    end;
  until i > j;
  Partition := j
end;