Анализ задачи и разработка алгоритма

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

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

TYPE u=^uzl;

uzl= RECORD

inf:Word; {информационное поле}

link:u; {указательное поле }

END;

VAR h:u; {указатель на голову (начало) списка}

Следует отметить, что указательное поле содержит адрес следующего узла, голова списка h (head) – адрес первого узла (указательное поле называют еще ссылочным полем, а ее значение ссылкой). Указатель, кроме того, может иметь значение nil (ссылка «в никуда») и при обработке списков интерпретируется как признак конца списка. Графическая модель списка приведена на рис. 1:

h - голова списка nil - признак конца списка

Рис. 1. Односвязный линейный список

Учитывая динамические свойства списка, он обычно формируется и обрабатывается в динамической памяти. Наиболее распространенными операциями со списком являются:

· создание списка;

· прохождение списка;

· сортировка списка;

· добавление нового узла;

· удаление заданного узла;

· и др.

В дальнейшем нас будет интересовать задача создания отсортированного списка. Для ознакомления с алгоритмом решения данной задачи сначала составим программу-прототип на языке Паскаль с тем, чтобы упростить разработку программы для ГМ. При написании программы на Паскале будем пользоваться приемами, характерными для программирования на Ассемблере (например, пользоваться оператором goto и т.п.), чтобы структура прототипа наиболее полно соответствовала программе ГМ. Ниже приведена указанная программа на Паскале.

Program Prototip1; { программа создания отсортированного списка }

Uses Crt;

Label 1;

Const kuz=10; { кол-во узлов }

Type u=^uzl;

uzl = Record { структура узла }

i: Word; { поле inf }

l:u; { поле link }

End;

Var h,p,t,s:u; { переменные для указателей }

R0,R1,R2: Word; { рабочие переменные }

Begin

Randomize;

ClrScr; { очистка экрана }

R1:=0; { R1 сч. цикла:= 0 }

R2:=kuz; { к-во узлов -> R2 }

h:= Nil; { h – голова списка, вначале список пустой }

{------------- Цикл создания узлов списка ------------- }

Repeat

R0:= Random (100); { взяли очередной inf -> R0 }

New (s); { создали новый узел, его адрес в s }

s^.i:=R0; { inf -> в новый узел }

t:=h; { t - указатель на текущий узел }

p:= Nil; { p - указатель на предыдущий узел}

{ Цикл поиска и вставки узла в надлежащее место списка }

While t <> Nil Do { пока не достигнут конец списка }

If t^.i > R0 { поиск места вставки }

Then { если место вставки найдено }

If p = Nil { и если р не успел измениться,то}

Then Begin { вставка в начало списка }

s^.l:= t; { соответствующая }

h:= s; { коммутация узлов }

Goto 1; { alles с этим вариантом }

End

Else Begin { вставка в середину списка }

s^.l:= t; { соответствующая }

p^.l:= s; { коммутация узлов }

Goto 1; { alles }

End

Else Begin { место вставки не найдено и переход к след. узлу }

p:= t; { предыдущий становится текущим, }

t:= t^.l; { а текущий - следующим }

End;

{ конец цикла While }

If p= Nil Then Begin { вставка в пустой список }

h:=s; { соответствующая }

s^.l:=Nil; { коммутация узлов}

End

Else Begin { вставка в конец списка }

p^.l:=s; { соответствующая }

s^.l:=Nil; { коммутация узлов}

End;

1: R1:=R1+1; { увеличение счетчика цикла }

Until R2 <= R1; { If счетчик < kuz Then на начало цикла}

{ Прохождение и печать списка }

t:=h; { встали на начало списка }

Writeln(' отсортированный список');{ вывели заголовок }

While t<> Nil Do { цикл прохождения списка }

Begin Write(t^.i:3); { печать узла }

t:=t^.l; { переход к след. узлу }

End;

ReadKey; { ожидание нажатия клавиши }

End.

В программе реализуется следующей алгоритм создания отсортированного списка. Сначала список пустой и h=nil. Внешний цикл REPEAT UNTIL детерминированного типа управляет числом создаваемых узлов. При каждом повторении этого цикла в динамической памяти создается новый узел с адресом (указателем) s и в его информационное поле s^. i записывается очередное случайное число. Далее, с помощью итерационного цикла WHILE осуществляется поиск места вставки нового узла и его коммутация с соседними так, чтобы список сохранил свойство отсортированности. Отметим, что для коммутации необходимо знать указатель как на текущий узел (узел, перед которым вставляется новый), так и указатель на предыдущий (узел, после которого вставляется новый). Эти указатели обозначены соответственно t и p. Таким образом, при прохождении списка указатель p отстает на один шаг от t. Начальное значение p равно nil, а t равнво h. Следует иметь в виду 4 варианта вставки:

· вставка в пустой список – в этом случае голове списка h присваивается значение указателя s нового узла, а в указательное поле этого узла записывается nil;

· вставка в начало списка – распознается по сохранившемуся после начальной инициализации p=nil; в указательное поле нового узла записывается значение h (s^.l:=h), а новым значением головы списка становится s (h:=s);

· вставка в середину списка – сводится к коммутации нового узла s с узлами p и t; сначала в ссылочное поле нового узла записывается ссылка (адрес) узла t (s^.l:=t), затем адрес s копируется в ссылочное поле узла p (p^.l:=s);

· вставка в конец списка – распознается, когда список пройден до конца (t=nil), а место вставки в цикле WHILE не найдено; узел s коммутируется с последним узлом списка (с узлом p): в ссылочное поле p записывается адрес нового узла (p^.l:=s), а в ссылочное поле s – значение nil (s^.l:=nil).

После того, как создано заданное число узлов, следует выход из внешнего цикла. Далее список просматривается от начала к концу и информационное поле каждого текущего узла (t^.i) выводится на экран монитора. После нажатия любой клавиши программа завершает свою работу.

Следующим шагом разработки является адаптация полученной программы к структуре ГМ. При этом необходимо учитывать следующие обстоятельства:

1. Будем считать, что ГМ имеет только статическую память. Поэтому список сформируем в массиве целых чисел Spis, в котором для каждого узла отводится два последовательных слова – первое для поля inf, второе для поля link. Причем, с целью упрощения задачи в качестве указателя в поле link будем использовать не абсолютный адрес, а смещение (индекс) соответствующего слова ГМ в Spis, т.е. указатели будут изменяться в диапазоне 0..2*kuz-1. Очевидно, что в данной постановке задачи параметр fw подразумевается равным 16.

2. В программе на Паскале исходные данные для списка поставляются генератором случайных чисел. Поскольку природа происхождения данных для нашей задачи не имеет принципиального значения (лишь бы они носили случайный характер), мы можем в качестве них выбрать содержимое любой области памяти (например, объектный код самой программы сортировки списка). Для удобства обработки эти данные предварительно копируются в непрерывную область памяти Buf. Необходимый размер области Buf в битах определяется количеством узлов списка kuz и форматом слова fw ГМ: Vbuf=kuz*fw. В следующем варианте программы на Паскале исходные данные для списка берутся из области программы начиная с адреса переменной ih.

3. В модифицированной программе на Паскале будем использовать только простейшие операторы, избегая сложных конструкций с тем, чтобы в ней проявились те операторы, которые легко преобразуются в команды ГМ.

Program Prototip2; { второй вариант программы сортировки списка }

Uses Crt;

Label Cycl1, While1, EndWhile, InsUz, NextUz, InsHead, InsMed,

EndCycl1, Empty, InsEnd, Wcycl, endPrn;

Const kuz=10; { кол-во узлов }

Niil=255; { код для Nil }

Var Buf: Array [0..kuz-1] Of Word; { буфер для исх. данных }

Spis: Array [0..2*kuz-1] Of Word; { обл-ть памяти для списка }

h,p,t,s: Word; { переменные для указателей }

R0,R1,R2,R3: Word; { "регистры" ГМ }

Cnil: Word; { переменная для Nil }

ih: Word; {индекс для резервирования нового узла в Spis }

Begin

ClrScr; { очистка экрана }

Move(ih,Buf,SizeOf(Buf)); {заполнение Buf исходными данными}

R1:= 0;

R2:= kuz;

h:= Niil;

Cnil:= Niil;

ih:= 0;

Cycl1: {------------- Цикл создания узлов списка ------------- }

R0:= Buf[R1]; { взяли очередной inf -> R0 }

s:= ih; { New(s) - создали новый узел }

Inc(ih); { ih указ-т на следующий новый узел }

Inc(ih);

Spis[s]:= R0; { s^.i:=R0; inf -> в новый узел }

t:= h; { t - указатель на текущий узел }

p:= Niil; { p - указатель на предыдущий узел }

While1: { Цикл поиска и вставки узла в список }

If t = Niil Then Goto EndWhile;

R3:= Spis[t]; { R3:= t^.i }

If R3 > R0 Then Goto InsUz; { поиск места вставки }

NextUz: { переход к след. узлу}

p:= t; { предыдущий становится текущим }

Inc(t); { t:=t+1 для получения доступа в поле link}

t:= Spis[t]; { t:=t^.l переход к след. узлу }

Goto While1;

InsUz: { Реализация различных вариантов вставки }

If p = Niil Then Goto InsHead;

InsMed: { вставка в середину }

Inc(p); { p:=p+1 для получения доступа в поле link }

R0:= Spis[p]; { R0:= p^.l }

Spis[p]:= s; { p^.l:= s }

Inc(s); { s:=s+1 для получения доступа в поле link }

Spis[s]:= R0; { s^.l:= R0 }

Goto EndCycl1;

InsHead: { вставка в начало списка }

h:= s; { новое начало списка }

Inc(s); { s:=s+1 для получения доступа в поле link }

Spis[s]:= t; { s^.l:= t }

Goto EndCycl1;

EndWhile: { реализация других вариантов }

If p=Niil Then Goto Empty;

InsEnd: { вставка в конец списка }

Inc(p); { p:=p+1 для получения доступа в поле link }

Spis[p]:= s; { p^.l:= s}

Inc(s); { s:=s+1 для получения доступа в поле link }

Spis[s]:= Niil; { s^.l:= NIL }

Goto EndCycl1;

Empty: { вставка в пустой список }

h:= s;

Inc(s); { s:=s+1 для получения доступа в поле link }

Spis[s]:= Niil; { s^.l:=NIL }

EndCycl1:

Inc(R1); { увеличение счетчика цикла }

If R2 > R1 Then Goto Cycl1;{ If счетчик < kuz Then на начало цикла }

{----------- Прохождение и печать списка --------------------}

WriteLn(' Отсортированный список'); { вывод заголовка списка}

t:= h; { встали на начало списка }

Wcycl: { цикл прохождения списка }

If t = Niil Then Goto endPrn;{ While t <> NIL Do}

Write(Spis[t]:3); { Печать узла}

Inc(t); { t:=t+1 для получения доступа в поле link}

t:= Spis[t]; { t:=t^.l переход к след.. узлу }

Goto Wcycl;

endPRN:

ReadKey; { ждать нажатия клавиши}

End.

Результаты работы программы приведены на рис. 2.