Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






Листинг 1. Сортировка слиянием

⇐ ПредыдущаяСтр 21 из 83Следующая ⇒

procedure merge(k: integer; { длина входной серии } fl, f2, gl, g2: file of recordtype);

var outswitch: boolean; { равна true, если идет запись в gl и false, если в g2 }

winner: integer; { номер файла с меньшим ключом в текущей записи }

used: array[1..2] of integer; { used[j] сообщает, сколько записей прочитано к настоящему времени из текущей серии файла fj }

fin: array[1..2] of boolean; { fin[j]=true, если уже закончена серия из файла fj:

либо прочитано k записей, либо достигнут конец файла fj}

current: array[1..2] of recordtype; { текущие записи из двух файлов }

 

procedure getrecord(i: integer); { Перемещение по файлу fi, не выходя за конец файла или

конец серии. Устанавливается fin[i]=true, если достигнут конец серии или файла }

begin

used[i]:= used[i] + 1;

if (used[i]= k ) or(i = 1) and eof(fl) or (i = 2) and eof(f2) then

fin[i]:= true

else if i = 1 then read(fl, current[1])

else read(f2, current[2])

end; { getrecord }

begin { merge }

outswitch:= true; {первая объединенная серия записывается в gl}

rewrite(gl); rewrite(g2);

reset(fl); reset(f2);

 

while not eof(fl) or not eof(f2) do begin { слияние двух файлов }
{ инициализация }

used[l]:= 0,- used[2]:= 0;

fin[l]:= false; fin[2]:= false;

getrecord(l); getrecord(2);

while not fin[l] or not fin[2] do begin { слияние серий }

{ вычисление переменной winner (победитель) }

if fin[l] then winner:= 2 {f2 "побеждает" по умолчанию: серия из fl исчерпалась}

else if fin[2] then winner:= 1 {fl "побеждает" по умолчанию}

else {не исчерпалась ни одна из серий}

if curren t [1].key<current[2].key then winner:= 1

else winner:= 2;

if outswitch then write(gl, current[winner])

else write(g2, current[winner]); getrecord(winner)

end;

{ закончено слияние двух серий, далее надо "переключить" выходной файл и повторить процедуру }

outswitch:= not outswitch;

end

end; { merge }

Обратите внимание, что процедура merge, показанная в листинге 1, вовсе не требует, чтобы отдельная серия полностью находилась в памяти: она считывает и за­писывает последовательно запись за записью. Именно нежелание хранить целые се­рии в основной памяти заставляет нас использовать два входных файла. В противном случае можно было бы читать по две серии из одного файла одновременно.

 

Таблица 11.1. Сортировка слиянием

 

28 3   93 10   54 65   30 90   10 69    
31 5   96 40   85 9   39 13   8 77    
а) исходные файлы  
28 31   93 96   54 85   30 39   8 10    
3 6   10 40   9 65   13 90   69 77    
б) серии длиной 2  
3 5   28 31   9 54   65 85   8 10    
10 40   93 96   13 30   39 90   8 10    
в) серии длиной 4  
3 5 10 28 31 40   93 96   8 8   10 10 22 69 77  
9 13 30 39 54 65   85 90              
г) серии длиной 8  
  10 13 28 30 31   39 40 54   65 85 90  
8 8 10   10 22 69 77  

д) серии длиной 16

3 5 8 8 9 10 10 10 13 22 28 30 31 39 40 54 65 69 77 85 90 93 96

е) серии длиной 32


⇐ Предыдущая16171819202122232425Следующая ⇒





Date: 2016-08-30; view: 277; Нарушение авторских прав


mydocx.ru - 2015-2024 year. (0.007 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию