Файл: Упорядочивание массива (История криптографии).pdf

Реализация:

Мы приведем реализацию первого шага алгоритма, сортирующего числа (для элементов другой природы потребуется изменить только процесс считывания):

new(root);

read(f,root^.chislo);

root^.kol:= 1;

root^.left:= nil;

root^.right:= nil;

while not eof(f) do

begin

read(f,x);

p:= root;

while true do

begin

if x = p^.chislo

then begin inc(p^.kol);

break

end;

if x > p^.chislo

then if p^.right <> nil

then p:= p^.right

else begin new(p^.right);

p:= p^.right;

p^.chislo:= x;

p^.kol:= 1;

p^.left:= nil;

p^.right:= nil;

break

end

(* x < p^.chislo *)

else if p^.left <> nil

then p:= p^.left

else begin new(p^.left);

p:= p^.left;

p^.chislo:= x;

p^.kol:= 1;

p^.left:= nil;

p^.right:= nil;

break

end

end;

end;

2.3.1. Блок-схема алгоритма:

Алгоритм Комп Связ-Итер:

Прочитать начало и конец очередного ребра. Далее возможны 4 различные ситуации:

1. Оба конца ребра еще не относятся ни к одной из ранее встретившихся компонент связности ( mark[u]=0 и mark[v]=0 ). В этом случае количество компонент связности kol увеличивается на единицу, а новая компонента связности получает очередной номер ks+1.
2. Один конец ребра уже относится к какой-то компоненте связности, а второй - еще нет ( mark[u]=0, а mark[v]<>0 ). В этом случае общее количество компонент связности kol остается прежним, а непомеченный конец ребра получает ту же пометку, что и второй его конец.
3. Оба конца нового ребра относятся к одной и той же компоненте связности ( mark[u]= mark[v]<>0 ). В этом случае не нужно производить никаких действий.
4. Концы нового ребра относятся к разным компонентам связности (  ). В этом случае нужно объединить две ранее созданные компоненты связности в одну. Общее количество компонент связности kol уменьшается на 1, а все вершины, принадлежавшие к более новой компоненте связности (больший номер), получают новую пометку. Заметим, что переменная ks, обозначающая очередной свободный номер для следующей компоненты связности, в данном случае изменяться не должна, поскольку нет никакой гарантии, что изменен будет номер именно самой последней компоненты связности.

По окончании работы этого алгоритма в массиве mark будет записано S различных целых чисел, каждое из которых будет означать отдельную компоненту связности. Кроме того, в массиве могут остаться нулевые компоненты: каждая из них будет соответствовать изолированной вершине, которая тоже является отдельной компонентой связности. Следовательно, количество нулей должно быть прибавлено к количеству компонент, найденному в процессе работы основного алгоритма.
Реализация задачи:

kol:=0;

ks:=0;

while not eof(f) do

begin

readln(f,u,v);

if mark[u]=0

then if mark[v]=0

then begin {случай 1}

inc(kol);

inc(ks);

mark[u]:= ks;

mark[v]:= ks;

end

else mark[u]:= mark[v] {случай 2}

else if mark[v]=0

then mark[v]:= mark[u]

{случай 2 - симметричный}

else if mark[u]<>mark[v] {случай 4}

then begin

max:= v;

min:= u;

if u>v then begin

max:= u;

min:= v end;

for i:= 1 to n do

if mark[i]= max

then mark[i]:= min;

dec(kol);

end

end;

for i:=1 to N do

if mark[i]=0 then inc(kol);

2.3.2. Описание переменных: идентификатор, тип:

javascript удалить элемент массива можно при помощи оператора delete:

var myColors = new Array("red", "green", "blue");

delete myColors[1];

alert(myColors); // red,,blue

2.3.3. Листинг программы:

• При сравнении 40 и 100 метод sort() вызывает функцию сравнения (40,100).
• Функция вычисляет 40-100, и возвращает -60 (отрицательное значение).
• Функция сортировки сортирует 40 как значение ниже 100.
• Этот фрагмент кода можно использовать для сортировки чисел и сортировки по алфавиту:

<button onclick="myFunction1()">Сортировать по алфавиту</button>
<button onclick="myFunction2()">Сортировать по числам</button>

<p id="demo"></p>

<script>
var points = [40, 100, 1, 5, 25, 10];
document.getElementById("demo").innerHTML = points;

function myFunction1() {
    points.sort();
    document.getElementById("demo").innerHTML = points;
}
function myFunction2() {
    points.sort(function(a, b){return a - b});
    document.getElementById("demo").innerHTML = points;
}
</script>

Листинг программы в текстовом редакторе. Скриншот листинга в окне компилятора

2.3.5. Контрольные примеры:

Найти наибольшее или наименьшее значение массива:

Нет встроенных функций для нахождения максимального и минимального значение в массиве.

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

Сортировка по возрастанию:

Пример

var points = [40, 100, 1, 5, 25, 10];
points.sort(function(a, b){return a - b});
// теперь points[0] содержит наименьшее значение
// и points[points.length-1] содержит наибольшее значение

Сортировка по убыванию:

Пример

var points = [40, 100, 1, 5, 25, 10];
points.sort(function(a, b){return b - a});
// теперь points[0] содержит наибольшее значение
// и points[points.length-1] содержит наименьшее значение