Организация и функционирование компьютеров

Приведем вспомогательную процедуру восстановления регулярности дерева в корне (k – длина еще не отсортированной части массива):

j := 1; {дерево регулярно везде, кроме, возможно, вершины с номером j}

while ((2*j+1 a[j])) or ((2*j a[j])) do

if (2*j+1 =a[2*j]) {Больше элемент a[2j+1]}

then begin x:=a[2*j+1]; {обменять местами a[j] и a[2j+1] }

a[2*j+1]:=a[j];

a[j] := x;

j := 2*j+1 {текущей будет вершина с номером 2j+1}

end

else begin x:=a[2*j]; {обменять местами a[j] и a[2j] }

a[2*j]:=a[j];

a[j] := x;

j := 2*j {текущей будет вершина с номером 2j}

end;

Возможно вместо указанного алгоритма использовать рекурсивную процедуру:

procedure regul (j,k: integer); {Восстановить регулярность поддерева с корнем j в массиве длины k}

var i: integer;

begin

if 2*j> k then i:=0 {Вершина j не имеет подчиненных}

else if 2*j= k then i:=2*j {Вершина j имеет одну подчиненную вершину 2j}

else {Вершина j имеет две подчиненные вершины 2j и 2j+1}

if a[2*j+1]>=a[2*j] {Выбрать максимальную из двух подчинееных вершин}

then i:=2*j+1

else i:= 2*j;

if (i>0) and (a[j]

begin x := a[i]; {обменять местами a[j] и a[i] }

a[i] := a[j];

a[j] := x;

regul (i,k) {Рекурсивный вызов процедуры regul для того, чтобы восстановить

регулярность поддерева с корнем в вершине с номером i}

end

end;

Аналогичная процедура используется для того, чтобы сделать весь массив регулярным на начальной стадии сортировки. Мы не будем ее здесь приводить.

4.16. Вывод на дисплей в текстовом и графическом режиме.

Стандартный экран монитора состоит из отдельных точек – пикселов. Каждый пиксел может быть окрашен в определенный цвет. Обычно это один из 24=16 цветов. В более совершенных компьютерах пиксел можно окрасить в 28=256 цветов. Если используется 16 цветов, то для описания цвета пиксела требуется 4 байта. При стандартном размере экрана 640*480 пикселов для полного описания экрана требуется 153.6Кб.

Монитор может работать в двух режимах – текстовом и графическом. В графическом режиме можно управлять окраской каждого пиксела в отдельности. В текстовом режиме экран разбивается на строки и столбцы (обычно 25 строк и 80 столбцов), и в каждой клетке изображается символ (один из 256). Изображения символов хранятся в специальной таблице, называемой знакогенератором, и представляют собой совокупность выделенных клеток в прямоугольной матрице.

Состояние экрана задается строкой из 80*25*2=4000 байтов – по два байта на каждый символ. Первый байт – это код символа, первые четыре бита второго байта – это цвет символа (всего возможно 24=16 цветов), другие четыре бита второго байта – это цвет фона, на котором нарисован символ (всего возможно 23=8 цветов, еще один бит задает мерцание символа). Содержимое строки хранится в специальном разделе оперативной памяти, называемом видеопамятью. Физически видеопамять входит в состав монитора, а логически ей зерезервировано место в оперативной памяти (с адресами от A000 до DFFF в 16-ричной системе счисления). Содержимое видеопамяти можно менять программным образом. Параллельно электронная трубка с определенной тактовой частотой выводит содержимое видеопамяти на экран монитора, формируя изображение.

Для изменения содержимого видеопамяти в текстовом режиме в Турбо-Паскале предусмотрен ряд процедур и функций. Перечислим основные из них (кроме функции write, описанной ранее).

Процедура window(l,u,r,d) устанавливает активное окно экрана, занимающее область от u-ой до d-ой строки и от l-ого до r-ого столбца включительно. После вызова процедуры window во всех процедурах вывода на экран текстовой информации номер строки и номер столбца отсчитывается от верхнего левого угла окна и действителен только в пределах окна.