Xreferat.com » Рефераты по информатике и программированию » Алгоритмический язык Паскаль

Алгоритмический язык Паскаль

rules="GROUPS" style="page-break-before: always;"> ОПЕРАТОРЫ

ПОЯСНЕНИЕ








Var ST:SS;





EL:integer;





Алгоритмический язык Паскаль K:SS;

ST *
nil

Begin





New(ST);





ST:=nil;












Алгоритмический язык Паскаль New(K);

K *










Randomize;





EL:=random(10);





Алгоритмический язык Паскаль K^.elem:=el;

K *
el1 nil
K^.next:=ST;



















Алгоритмический язык ПаскальАлгоритмический язык Паскаль

K *
el1 nil
ST:=K;





Алгоритмический язык Паскаль

ST *

















Алгоритмический язык Паскаль New(K);

K *

















Алгоритмический язык ПаскальАлгоритмический язык Паскаль EL:=random(10);

K *
el2 *
K^.elem:=EL;












Алгоритмический язык ПаскальАлгоритмический язык Паскаль







Алгоритмический язык Паскаль

ST *
el1 nil
K^.next:=ST;



















Алгоритмический язык ПаскальАлгоритмический язык ПаскальАлгоритмический язык Паскаль ST:=K;

K *
el2 *







Алгоритмический язык ПаскальАлгоритмический язык Паскаль














Алгоритмический язык ПаскальАлгоритмический язык Паскаль

ST *
el1 nil







Запишем теперь саму процедуру формирования стека:

procedure SOZDAN_STACK (var ST: SS);

var K: SS;

EL: integer;

begin

randomize;

EL:= random(10);

new(ST); ST:= nil;

while EL <> 0 do

begin

¦ new(K); K^.elem:= EL;

¦ k^.next:= ST; ST:= K;

¦ EL:= random(10);

end;

end.

ЗАМЕЧАНИЕ. Как видно из процедуры, организация очереди и стека отличается только порядком установления связи: предыдущий элемент очереди указывает на следующий, а следующий элемент стека ссылается на предыдущий.

Известно, что новый элемент всегда вставляется на первое место - в вершину стека. Отсюда получаем схему вставки звена в стек:


Алгоритмический язык ПаскальАлгоритмический язык ПаскальАлгоритмический язык ПаскальАлгоритмический язык ПаскальАлгоритмический язык ПаскальАлгоритмический язык ПаскальST

*



Eln * … EL1 nil











Алгоритмический язык ПаскальАлгоритмический язык Паскаль



Eln+1 *






Процедура имеет два параметра: ST - указатель на стек, EL - заносимый элемент:

PROCEDURE VSTAVKA_V_STACK(var ST: SS; EL: integer);

var K: SS;

begin

new(K); K^.elem:= EL;

K^.next:= ST; ST:= K

end.

Схематически процесс удаления можно изобразить так:













Алгоритмический язык ПаскальАлгоритмический язык ПаскальАлгоритмический язык ПаскальАлгоритмический язык ПаскальST

*
Eln *
Eln-1 * … EL1 nil

Алгоритмический язык ПаскальАлгоритмический язык Паскаль












По схеме видно, что удаляется N-е звено (вершина стека), которое надо запомнить в специальной ячейке SKLAD:

procedure UDALENIE_IZ_STACK(var ST: SS; var SKLAD: integer);

begin

¦ SKLAD:= ST^.elem;

¦ ST:= ST^.next

end.

Мы видим, что здесь переменная ST начинает хранить ссылку на N-1 элемент.

Данная процедура имеет недостатки:

1) предполагается, что стек заведомо не пуст, иначе программа зависнет;

Алгоритмический язык Паскаль2) исключаемое звено не уничтожается, т.к. меняется только ссылка в переменной ST. Если таких удалений несколько, то память будет забита "мусором". Поэтому следует исключить элементы не только из списка, но и из памяти. Для этого можно использовать процедуру DISPOSE.

Указанные недостатки учтены в следующей процедуре:

procedure UDALENIE_MOD(var ST: SS; var SKLAD: integer);

var K: SS;

begin

¦ if ST = nil then writeln('стек пустой')

¦ else begin

¦ ¦ SKLAD:= ST^.elem; K:=ST;

¦ ¦ ST:= ST^.next; dispose(K);

end;

end.

Здесь мы ввели в употребление вспомогательную ссылочную переменную К, т.к. писать DISPOSE (ST) нельзя, ведь ST содержит ссылку на вершину стека.

Для извлечения из стека N-го элемента необходимо поступить так же, как при выборке элемента из файла, - "прокрутить" стек на N-1 позиций и затем извлечь N-й элемент. Для "прокрутки" стека можно воспользоваться процедурой UDALENIE, т.к. удаление в динамических структурах означает не уничтожение звеньев списка, а только передвижение указателя на следующий элемент.

Для написания этой процедуры следует уточнить, что под N-м элементом стека следует понимать элемент, отстоящий на N позиций от вершины стека:

procedure VIBORKA_IZ_STACKA(var ST: SS; var SKLAD: integer;

N: integer);

var K: SS; i: integer;

begin

¦ K:= ST;

¦ for i:= 1 to N-1 do

¦ UDALENIE_IZ_STACK(K, SKLAD);

¦ SKLAD:= K^.elem;

end.

Для вывода на печать элементов стека можно воспользоваться процедурой печати для цепочки, т.к. в этом смысле цепочка ничем не отличается от стека. Отметим только, что элементы стека будут выведены в порядке, обратном его заполнению.


14.3 Дек


Дек - это двунаправленная очередь, т.е. линейный список, в котором все включения и исключения (и обычно всякий доступ) достигаются на обоих концах списка:



левый второй
второй правый

конец слева
справа конец

Алгоритмический язык ПаскальАлгоритмический язык ПаскальАлгоритмический язык ПаскальАлгоритмический язык Паскаль

EL1
EL2 .. .. Eln-1
Eln

Алгоритмический язык ПаскальАлгоритмический язык Паскаль











включить




включить

или





или

исключить




исключить

Более точно следует представить так:

















EL1
EL2
EL3


Eln

Алгоритмический язык ПаскальАлгоритмический язык ПаскальАлгоритмический язык ПаскальАлгоритмический язык ПаскальАлгоритмический язык Паскаль


*
*
*
…
*
nil

Алгоритмический язык ПаскальАлгоритмический язык ПаскальАлгоритмический язык ПаскальАлгоритмический язык ПаскальАлгоритмический язык Паскальnil


*
*
*
…
*















Формирование дека

Для организации дека в виде динамической цепочки необходимо иметь следующие типы:

type SS = ^ZVENO;

ZVENO = record

ELEM: integer;

next: SS;

pred: SS;

end.

Очевидно, что дек обладает большей общностью, чем стек и очередь; он имеет некоторые общие свойства с каждой из этих структур. Существуют деки с ограниченным входом (реестры) и выходом (архивы). В таких деках соответственно включение и исключение допускается только в одном конце.

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

procedure FORMIR_DEK_1(var L, R: SS);

var Z: SS; EL: integer;

begin

¦ new(L); read(L^.elem);

¦ L^.pred:= nil; R:= L; Z:= L;

¦ WHILE R^.elem <> 0 do

¦ begin

¦ ¦ new(R^.next); R:=R^.next;

¦ ¦ read(r^.elem); R^.pred:= Z; Z:= R;

¦ end;

¦ R^.next:= nil; readln;

end.

ПРИМЕЧАНИЕ. В рассмотренном примере для образования дека используются три ссылочные переменные: L - начало дека, R – конец дека, Z - промежуточное звено. Однако эта программа может быть упрощена за счет использования более сложных ссылок типа R^.NEXT^.ELEM и R^.NEXT^.PRED.

Рассмотрим подробно эти объекты. Пусть ссылочная переменная Z указывает на текущее звено дека:




Звено 1 Звено 2

Алгоритмический язык ПаскальАлгоритмический язык ПаскальАлгоритмический язык ПаскальX

*
next
next
…

Алгоритмический язык ПаскальАлгоритмический язык Паскаль

…
pred
pred




ELi
ELi+1










При таких обозначениях динамическая переменная Z^.NEXT^.ELEM означает числовое поле звена 2 (т.е элемент ELi+1), а переменная Z^.NEXT^.PRED - поле PRED звена 2. Учитывая эти соображения, представим программу формирования дека следующим образом:

procedure FORMIR_DEK_2(var L, R: SS);

begin

¦ randomize; new(L);

¦ L^.elem:= random (10);

¦ L^.pred:= nil; R:= L;

¦ while R^.elem <> 0 do

¦ begin new(R^.next);

¦ ¦ R^.next^.elem:= random(10);

¦ ¦ R^.next^.pred:= R; R:=R^.next

¦ end;

R^.next:= nil

end.

Для дека справедливы те же операции, что для очереди и стека - вставка и удаление звеньев.

Для процедуры вставки в дек, как и в любой другой линейный список, необходимы два параметра: X - звено, после которого (перед которым) надо поместить элемент, и Y - вставляемое звено. Схема вставки остается такой же, как, например, в очереди, но в деке после включения нового звена нужно установить две связи – на последующий и предыдущий элементы.












Алгоритмический язык Паскаль



ELi

Z *
ELi+1

Алгоритмический язык ПаскальАлгоритмический язык ПаскальАлгоритмический язык ПаскальАлгоритмический язык ПаскальАлгоритмический язык ПаскальАлгоритмический язык ПаскальX

*
*




*

Алгоритмический язык ПаскальАлгоритмический язык ПаскальАлгоритмический язык ПаскальАлгоритмический язык ПаскальАлгоритмический язык Паскаль

…
*
Y *

* …

Алгоритмический язык Паскаль

















EL



Алгоритмический язык ПаскальАлгоритмический язык Паскаль






*



Алгоритмический язык ПаскальАлгоритмический язык Паскаль






*















Рассмотрим предварительно схему связи между звеньями дека в процессе вставки нового элемента:


ОПЕРАТОРЫ

ПОЯСНЕНИЕ














Z


X Elx


Elz

Алгоритмический язык ПаскальАлгоритмический язык ПаскальАлгоритмический язык ПаскальАлгоритмический язык Паскаль


*


*

Алгоритмический язык ПаскальY^.next:=X^.next;


* Y Ely
*

Алгоритмический язык Паскаль




*






*























Z


X Elx


Elz

Алгоритмический язык ПаскальАлгоритмический язык ПаскальАлгоритмический язык Паскаль


*


*

Алгоритмический язык ПаскальАлгоритмический язык ПаскальY^.pred:=X;


* Y Ely
*

Алгоритмический язык Паскаль




*


Алгоритмический язык Паскаль




*























Z


X Elx


Elz

Алгоритмический язык ПаскальАлгоритмический язык ПаскальАлгоритмический язык ПаскальАлгоритмический язык ПаскальАлгоритмический язык ПаскальX^.next:=Y;


*


*

Алгоритмический язык Паскаль


* Y Ely
*

Алгоритмический язык ПаскальАлгоритмический язык ПаскальАлгоритмический язык Паскаль




*


Алгоритмический язык Паскаль




*







Z


X Elx


Elz

Алгоритмический язык ПаскальАлгоритмический язык ПаскальАлгоритмический язык ПаскальАлгоритмический язык ПаскальАлгоритмический язык Паскаль


*


*

Алгоритмический язык Паскаль


* Y Ely
*

Алгоритмический язык ПаскальАлгоритмический язык ПаскальАлгоритмический язык ПаскальАлгоритмический язык ПаскальY^.next^.pred:=Y;




*


Алгоритмический язык ПаскальАлгоритмический язык Паскаль




*



















Процедура вставки нового звена Y в дек после звена X принимает вид:

procedure VSTAVKA_V_DEK_POSLE(X, Y: SS);

begin

¦ Y^.next:= X^.next;

¦ Y^.pred:= X;

¦ X^.next:= Y;

¦ Y^.next^.pred:= Y;

end.

ЗАМЕЧАНИЕ 1. Мы рассмотрели теперь процедуры вставки нового звена во все виды линейных списков с односторонней связью (цепочки, очереди, стеки) и в дек. Однако во всех этих процедурах новое звено вставлялось ПОСЛЕ указанного звена (в стеке - в вершину, в очереди - в хвост). Конечно, можно в односвязном линейном списке поставить новый элемент и ПЕРЕД указанным, но это требует некоторых дополнительных операций. Например, можно новый элемент поместить в следующее звено, а затем произвести обмен информационными полями. В деке же возможна прямая вставка звена ПЕРЕД указанным с использованием ссылки PRED. В результате получаем:

procedure VSTAVKA_V_DEK_PERED(X, Y: SS);

begin

¦ Y^.next:= X^.pred^.next; X^.pred^.next:= Y;

¦ Y^.pred:= X^.pred; X^.pred:= Y;

end.

ЗАМЕЧАНИЕ 2. При вставке нового звена Y в дек относительно X следует учитывать, что на момент применения рассмотренных процедур звенья X и Y уже сформированы и значения этих ссылочных переменных определены. Так, например, звено Y можно сформировать следующим образом:

NEW(Y); Y^.NEXT:= NIL; Y^.PRED:= NIL; READ(Y^.ELEM).

Что касается звена X, то здесь возможны два случая:

1) известен адрес (ссылка) на элемент X; тогда при обращении к процедуре уже задано значение фактического параметра;

2) известен только сам элемент (информационное поле звена X);

для определения ссылки на звено X в указанном деке следует "прокрутить" дек до этого звена (подобно поиску N-го звена в стеке).

Заметим также, что обе процедуры неприменимы для дека, состоящего из одного звена.

При удалении звена из дека, как и в любом линейном списке, происходит перебрасывание ссылок через удаляемое звено: ссылка NEXT предыдущего звена получает своим значением адрес третьего звена, а ссылка PRED третьего звена указывает на первое звено. В результате второе (удалямое) звено X оказывается изолированным от остальных звеньев, что и означает его удаление из дека.

ЗАМЕЧАНИЕ. Данная процедура применима только для звена X, находящегося внутри дека. Для пограничных случаев, когда звено X является первым или единственным, необходимо использовать более сложную процедуру:

procedure UDAL_DEK_1(X: SS; VAR Y, Z: SS);

begin

¦ if Y^.next = nil then writeln('Дек пуст !') else

¦ if X = Y then Y:= Y^.next else

¦ begin x^.pred^.next:=x^.next;

¦ ¦ {Переброска ссылки next вверху}

¦ ¦ x^.next^.pred:=x^.pred;

¦ ¦ {Переброска ссылки pred внизу}

¦ end;

end.

В этой процедуре введены параметры-переменные: Y - начало дека и Z - ссылка на конец дека. Они необходимы, т.к. здесь могут быть изменены начало и конец дека.

Если Y^.NEXT = NIL, то это означает, что дек пуст и никаких действий не производится. Равенство X = Y показывает, что дек состоит из одного звена, которое удаляется путем присваивания ссылке Y (началу дека) значения указателя на последнее нулевое звено дека. Для остальных случаев все действия производятся, как и в предыдущем примере.


14.4 Общие приемы работы с линейными списками


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

Процедура печати списка имеет вид:

procedure VIVOD_SPISOK(var Y: SS);

var X: SS;

begin X:= Y;

¦ while X^.next <> nil do

¦ begin

¦ ¦ write(X^.elem,' '); X:=X^.next;

¦ end;

end.

ПОЯСНЕНИЕ. Здесь Y - начало списка, а переменная X введена, чтобы после печати списка значение переменной Y не изменилось (не потерялось начало списка).

Поиск заданного элемента в списке осуществляется чаще всего не для констатации факта присутствия этого элемента, а для его удаления или для вставки после него (перед ним в деке) нового элемента. Именно поэтому возвращаемым параметром этой процедуры должна быть ссылка на данный элемент (если такой факт имеет место). Кроме того, полезно знать и номер найденного звена от начала списка:

procedure POISK_V_SPISKE(var Y,Z: SS; ZNACH: integer;

var N: integer);

var X: SS;

begin

¦ N:= 1; X:= Y;

¦ while (X^.elem <> ZNACH) and (X^.next <> nil) do

¦ begin

¦ ¦ X:= X^.next; Z:= X;

¦ ¦ N:= N+1

¦ end;

¦ if X^.next = nil then

¦ begin N:= 0; Z:= nil; end;

end.

ПОЯСНЕНИЕ. С помощью данной процедуры в списке Y ищется звено с элементом ZNACH. Значение переменной N дает номер искомого звена, а переменная Z - ссылку на это звено. Если такого звена нет, то N = 0 и Z = NIL.

Сортировка линейных списков незначительно отличается от сортировки массивов. При этом надо помнить, что при сортировке односвязных списков применяются методы, в которых движение идет в одну сторону (здесь пузырьковая сортировка неприемлема). Для двухсвязных списков (деков) таких ограничений нет. Очевидно, что при сортировке динамических объектов происходит не сама их перестановка, а переброска соответствующих ссылок:

procedure SORTSPISOK (var X: SS);

{ X - Ссылка на начало списка }

var X1, Y1:SS; P: integer;

begin

¦ X1:= X; { Выбор элемента для сравнения }

¦ while X1^.next <> nil do { Проход по списку до

¦ предпоследнего элемента}

¦ begin

¦ ¦ Y1:=X1^.next;

¦ ¦ while Y1^.next <> nil do { Проход до последнего

¦ ¦ элемента }

¦ ¦ begin

¦ ¦ ¦ { Перестановка местами элементов}

¦ ¦ ¦ if Y1^.elem < X1^.elem

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: