Составление алгоритма сортировки линейной вставкой. Понятие однонаправленного циклического списка символов, реализация процедуры подсчета суммы элементов и составление алгоритма. Прямое представление дерева, алгоритм работы с ним на абстрактном уровне.
Аннотация к работе
Описание алгоритма: Сортируется вектор A длиной N Нач Для i от 2 до N Цикл X:= A[i]; j:= i-1; Пока (j ? 1) и (A[j] > X) Цикл A[j 1]:= A[j];{сдвиг элементов} j:= j - 1; КЦикл A[j 1]:= X;{вставка элемента на свое место} КЦикл Кон На каждой итерации первое число не отсортированного списка удаляется из него и помещается на соответствующее ему место в отсортированном списке. Покажем работу алгоритма на примере: 27 412 71 81 59 14 273 87 Итерация 0: Неотсортированный: 412 71 81 59 14 273 87 Отсортированный: 27 Итерация 1: Неотсортированный: 412 71 81 59 14 273 87 Отсортированный: 27412 Итерация 2: Неотсортированный: 71 81 59 14 273 87 Отсортированный: 2771 412 Итерация 3: Неотсортированный: 81 59 14 273 87 Отсортированный: 2771 81 412 Итерация 4: Неотсортированный: 59 14 273 87 Отсортированный: 2759 71 81 412 Итерация 5: Неотсортированный: 14 273 87 Отсортированный: 14 27 59 71 81 412 Итерация 6: Неотсортированный: 273 87 Отсортированный: 14 27 59 71 81 273 412 Итерация 7: Неотсортированный: 87 Отсортированный: 14 27 59 71 81 87 273 412 Листинг программы {сортировка массива целых чисел алгоритмом линейная вставка} Program Sort1; uses crt, dos; const ARRAYSIZE=50; {максимальный размер вектора} type arrayType=array [1..ARRAYSIZE] of integer; {тип вектора} var a: arrayType; {сортируемый вектор} n: integer; {количество элементов в векторе} i,j: integer; ch: char; {процедура создания и вывода вектора theArray с размером SIZE} Procedure Vector (SIZE, MAX: integer; var theArray:arrayType); begin randomize; for i:=1 to SIZE do theArray[i]:=random(MAX); Writeln(Исходный массив: ); for i:=1 to Size do Write (theArray[i], ); end; {процедура сортировки} Procedure InsertSort (size: integer; var theArray: arrayType); var newPos: integer; {начальная позиция вставляемого на место элемента} newValue: integer; {значение вставляемого на место элемента} currentPos: integer; {позиция вставляемого в упорядоченном векторе} begin for newPos:=2 to SIZE do begin newValue:=theArray [newPos]; currentPos:=newPos-1; while (currentPos>=1) and (theArray[currentPos]>newValue) do begin theArray[currentPos 1]:=theArray[currentPos]; currentPos:=currentPos-1; end; theArray[currentPos 1]:=newValue; end; end; {главная программа} begin repeat clrscr; writeln(Введите желаемое количество элементов (до 50)); Readln(n); Vector(n,ARRAYSIZE,a); InsertSort (n,a); Writeln; Writeln (Отсортированный массив: ); for i:=1 to n do write ( ,a[i]); Readln; writeln (Будете еще?. (да - y; нет - n)); ch:=ReadKey; Until (ch=N) or (ch=n); end. Меняем этот указатель до тех пор, пока элемент Аi меньше центрального элемента х (АiNIL) then (* Если список не пуст *) begin nextel:=list; repeat list:=nextel; (* Перейти к следующему элементу списка *) if (list^.next