36221

Очередь. Работа с динамической очередью

Доклад

Информатика, кибернетика и программирование

Например: Работа с очередью Для создания очереди и работы с ней необходимо иметь как минимум два указателя: на начало очереди возьмем идентификатор BegQ; на конец очереди возьмем идентификатор EndQ. Установка указателей BegQ и EndQ на созданный первый элемент: Удаление элемента очереди 1. Перестановка указателя начала очереди BegQ на следующий элемент используя значение поля Link которое хранится в первом элементе. После этого освобождается память начального...

Русский

2013-09-21

246 KB

1 чел.

Очередь. Работа с динамической очередью

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

Очередь может быть динамической (строится на базе односвязного динамического списка) и статической (на базе массива).

Рассмотрим работу динамической очереди. Основой ее является односвязный динамический список. Каждый элемент имеет как минимум 2 поля: одно для хранения собственно информации, другое – для хранения указателя на следующий элемент списка.

Правило последовательности описаний в Turbo Pascal требует, чтобы каждый идентификатор был описан, прежде чем он будет использоваться для других объявлений. Однако для создания динамического списка такой порядок невозможен. Поэтому для описания типов элементов динамических структур данных сделано исключение. Тип указателя на элемент динамической структуры данных может и должен быть описан перед описанием типа этого элемента.

Например:

Type

Yk  :=^TElem ;

TElem = record

Inf  : integer;

Link : Yk

end;

Работа с очередью

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

• на начало очереди (возьмем идентификатор BegQ);

• на конец очереди (возьмем идентификатор EndQ).

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

Создание очереди

1. Исходное состояние:

2. Выделение памяти под первый элемент очереди:


3. Занесение информации в первый элемент

4. Установка указателей BegQ и EndQ на созданный первый элемент:

Удаление элемента очереди

1. Исходное состояние:

2. Печать информации из удаляемого элемента и установка на него вспомогательного указателя P:

3. Перестановка указателя начала очереди BegQ на следующий элемент, используя значение поля Link, которое хранится в первом элементе. После этого освобождается память начального элемента очереди, используя дополнительный указатель P:


BegQ:= nil;

EndQ:= nil;

P

nil

EndQ

BegQ

nil

nil

nil

P

nil

EndQ

nil

BegQ

New (p);

Int

Link

     ?

?

nil

P

nil

EndQ

nil

BegQ

p^.Int:= 3;

p^.Link:= nil;

Int

Link

     3

nil

BegQ

EndQ

Int

Link

     3

nil

BegQ:= p;

EndQ:= p;

BegQ

2

4

3

EndQ

Очередь, в которой содержатся элементы (2, 4 и 3) и указатель Р, значение которого пока неопределенно.

P

?

печать

BegQ

2

4

3

EndQ

Р

Writeln ( BegQ^.inf);

Р := ( BegQ^.Link);  { это делается

для того, чтобы впоследствии можно было освободить память}

2

4

10

EndQ

Р

BegQ := BegQ^.Link);

Dispose (Р); {освобождение памяти}

BegQ


 

А также другие работы, которые могут Вас заинтересовать

20290. Новаторство создателей МХТ в области декорационного искусства и технологии 82 KB
  Станиславский Константин Сергеевич Алексеев 17. Опираясь на богатейшую творческую практику и высказывания своих выдающихся предшественников и современников Станиславский заложил прочный фундамент современной науки о театре создал школу направление в сценическом искусстве которое нашло теоретическое выражение в так называемой системе Станиславского. 1877 Станиславский впервые выступил на домашней любительской сцене. Станиславский сыграл десятки комедийных ролей с пением и танцами.
20291. Русская художественная культура 20-х - середины 30-х годов XX века 315 KB
  А русский авангард своеобразный феномен искусства 20 в. но и с новым искусством стиля модерн господствующим в это время повсеместно и во всех видах искусства от архитектуры и живописи до театра и дизайна. Русский художник теоретик искусства и писатель. Был членом объединений Мир искусства и Четыре искусства.
20292. Европейский театр классицизма 78 KB
  В основе классицизма лежат идеи рационализма которые формировались одновременно с таковыми же идеями в философии Декарта. Художественное произведение с точки зрения классицизма должно строиться на основании строгих канонов тем самым обнаруживая стройность и логичность самого мироздания. Интерес для классицизма представляет только вечное неизменное в каждом явлении он стремится распознать только существенные типологические черты отбрасывая случайные индивидуальные признаки.
20293. Свет в театре и на эстраде 56.5 KB
  Его история во многом определялась теми источниками света которые имелись в распоряжении театра в те или иные периоды его развития. особенно в его вторую половину стремительно модернизировались новыми техническими возможностями и расширяли сферу применения света как средства сценической выразительности. С точки зрения эстетической искусство сценического света в 1718 вв.Станиславского партитуры сценического света особенно в чеховских спектаклях на сцене передавались меняющиеся состояния природы утро день вечер ночь; солнечно...
20294. Русская художественная культура середины 50-х - 60-х годов XX века 266.5 KB
  В связи с разоблачением культа личности Сталина происходило преодоление откровенно лакировочного искусства особенно характерного для 30 40х годов. Коммерциализация литературы и искусства привела к распространению произведений не отличающихся высокими художественными достоинствами. В советской культуре наблюдались две противоположные тенденции: искусства политизированного лакирующего действительность и искусства формально социалистического но по существу критически отражающего действительность в силу сознательной позиции художника...
20295. Западно-европейский театр второй половины XIX века 264.5 KB
  Театр XIX в. европейский театр растерял многие свои ценные завоевания. Повсюду в театрах для высшего общества вновь воцарилось величественное но холодное искусство классицизма утратившего после французской революции 1789 1794 гг.
20296. Костюм и декорация 74.5 KB
  В спектаклях первого Русского сезона оформленных Бакстом Клеопатра и Рерихом Половецкие пляски у Бенуа сложились некоторые принципы новой сценографии хореографического театра. Ряд статей Бенуа под рубрикой Русские спектакли в Париже знакомит читателей газеты Речь с ходом сезонов. Они по словам Бенуа не только создавали обрамление в котором блистали Фокин Нижинский Павлова Карсавина Федорова и столько других но им принадлежала генеральная идея спектаклей. Но как бы то ни было в создании мастеров сплотившихся вокруг...
20297. Современная русская художественная культура 78 KB
  Художественная культура современной России. Однако в самой России творчество букеровских лауреатов постоянно вызывало неоднозначную реакцию поэтому в 1995 г. Тополь Завтра в России А. Читателю предлагается непривычная для РУС России было присуще стремление подняться над описательностью и бытовизмом найти тот единственный и точный конкретнозримый образ который воплотил бы в себе всю полноту и драматизм многогранной жизни.
20298. Реализм в сценическом искусстве Европы XIX века 63.5 KB
  Центральной фигурой театральной жизни рубежа XIX XX вв. Наряду с ростом прогрессивных тенденций в развитии европейского театра в последние десятилетия XIX в. все явственнее проявляются признаки глубокого идейнотворческого кризиса театральной культуры. Если раньше черты надвигающегося кризиса проявлялись в отрыве театра от большой литературы в натуралистическом перерождении критического реализма то в конце века театр приобретает иное свойство он становится выражением кризиса всей духовной культуры буржуазного мира.