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


 

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

28322. Понятие, виды и особенности правового режима ценных бумаг 16.33 KB
  Если бы право могло быть осуществлено беспрепятственно без бумаги то ему незачем было искать воплощение в бумаге. К ценным бумагам относятся: государственная облигация; облигация; вексель; чек; депозитный и сберегательный сертификаты; банковская сберегательная книжка на предъявителя; коносамент; акция; приватизационные ценные бумаги и другие документы которые законами о ценных бумагах или в установленном ими порядке отнесены к числу ценных бумаг. Ценные бумаги могут быть классифицированы по различным признакам. Так по содержанию...
28323. Сделки: понятие, признаки, виды 20.42 KB
  Сделки акты осознанных целенаправленных волевых действий физических и юридических лиц совершая которые они стремятся к достижению определенных правовых последствий. Сущность сделки составляют воля и волеизъявление сторон. Волеизъявление важнейший элемент сделки с которым как правило связываются юридические последствия. Признаки сделки: 1.
28324. Условия действительности сделок. Последствия признания сделок недействительными 16.85 KB
  Действительность сделки означает признание за ней качеств юридического факта порождающего тот правовой результат к которому стремились субъекты сделки. Действительность сделки определяется законодательством посредством следующей системы условий: законность содержания; способность физических и юридических лиц совершающих ее к участию в сделке; соответствие воли и волеизъявления; соблюдение формы сделки. Законность содержания сделки означает ее соответствие требованиям законодательства. Законность содержания сделки предполагает ее...
28325. Недействительность сделок: понятие, виды, последствия 22.11 KB
  Недействительность сделки означает что она не влечет юридических последствий на достижение которых была направлена но в то же время порождает последствия установленные законом в связи с ее не действительностью. ГК РФ подразделяет недействительные сделки на ничтожные и оспоримые. В теории гражданского права такие сделки называются абсолютно недействительными. Ничтожные сделки не влекут возникновения изменения или прекращения гражданских прав и обязанностей на которые они были направлены.
28326. Осуществление гражданских прав и исполнение обязанностей: понятие, принципы и способы осуществления 15.41 KB
  Под осуществлением гражданского права понимается совершение действий по реализации возможностей заложенных в содержании субъективного права. Содержание границы того или иного субъективного права определяются нормативными актами или договорами например согласно статье 209 ГК РФ содержание права собственности составляет возможность владеть пользоваться и распоряжаться вещью. 9 ГК РФ граждане и юридические лица осуществляют принадлежащие им гражданские права по своему усмотрению принцип диспозитивности. Носитель субъективного права...
28327. Пределы осуществления субъективных гражданских прав. Злоупотребление правом 13.92 KB
  Пределы осуществления субъективных гражданских прав. Злоупотребление правом. Пределы осуществления субъективных гражданских прав ОСГП – это законодательно очерченные границы деятельности управомоченных лиц по реализации возможностей составляющих содержание данных прав. Пределы ОСГП: а осуществление субъективных гражданских прав е имеет временные границы т.
28328. Представительство по гражданскому праву: понятие, виды, основания возникновения 16.43 KB
  Представительство отношение в соответствии с которым сделка совершенная одним лицом представителем от имени другого лица представляемого в силу полномочия основанного на доверенности указании закона либо акта уполномоченного на то органа государственного местного самоуправления непосредственно создает изменяет и прекращает гражданские права и обязанности представляемого ст. Представитель это лицо юридическими действиями которого приобретаются изменяются или прекращаются права и обязанности для представляемого по отношению...
28329. Доверенность по гражданскому праву 15.53 KB
  Доверенность по гражданскому праву. Доверенность это документ выдаваемый представителю в целях определения характера и объема предоставляемых ему полномочий. Общая доверенность определяет полномочия на совершение разнообразных сделок и иных юридических действий на управление имуществом гражданина руководителю филиала юридического лица. Специальная доверенность необходима для совершения однородных действий на распоряжение вкладом на вождение автомобиля на ведение судебных и арбитражных дел.
28330. Защита гражданских прав: понятие, предмет и форма защиты 14.21 KB
  Защита гражданских прав: понятие предмет и форма защиты. Защита гражданских прав выражается в действиях субъектов права а также уполномоченных органов по предупреждению правонарушения или восстановлению нарушенных прав. Право на защиту выражается в применении мер имущественного характера и направлено на компенсацию восстановление существующего положения и реализуется в исковой форме в судебном порядке. Защита гражданских прав в административном порядке осуществляется лишь в случаях предусмотренных законом.