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


 

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

10162. Определение техники как философская проблема. Основные способы определения техники 47 KB
  Определение техники как философская проблема. Основные способы определения техники. Отсутствие должной степени разработки философских аспектов техники во многом вызвано тем обстоятельством что техника как объект исследования со стороны философии представляет с...
10163. Специфика технического отношения к миру и технического типа мышления 36 KB
  Специфика технического отношения к миру и технического типа мышления. В имеющихся определениях техники обнаруживается существенно общий смысловой срез: по отношению к человеку техника является вопервых воплощением его деятельности и вовторых таким вопло...
10164. Специфика технического знания и технических наук 53 KB
  Специфика технического знания и технических наук. Поскольку техническое знание ближе всего естественнонаучному то его специфику легче всего усмотреть на основе их сравнения. Техника большую часть своей истории была мало связана с наукой люди могли делать и делал...
10165. Отношение техники и прикладного знания. Типология технических наук 24.5 KB
  Отношение техники и прикладного знания. Типология технических наук. Это одна из причин почему традиционная характеристика техники как прикладного Е сейчас оценивается как устаревшая. Это утверждение может быть признано лишь отчасти справедливым по отношению к не
10166. Периодизация развития техники как философская проблема. Основные способы периодизации развития техники 50.5 KB
  Периодизация развития техники как философская проблема. Основные способы периодизации развития техники. Закономерности исторического развития техники. Проблема периодизации. Предметная сторона Т. Техника и наука. Т как деятельность. ФТ выделяе...
10167. Взаимоотношение науки и техники на различных этапах эволюции техники 50 KB
  Взаимоотношение науки и техники на различных этапах эволюции техники Они не всегда были взаимосвязаны Т долгое время развивалась независимо от всякой науки. Это не означает что в технике не применялись научные знания. Доинженерный период. Но наука не имела дисциплин
10168. Техногенная цивилизация, ее история и перспективы 108 KB
  Техногенная цивилизация ее история и перспективы. Информационное общество это высшая стадия развития техногенной цивилизации. Для характеристики его места в истории вернемся к общим представлениям о развитии культуры. С т.з. современной социальной философии сущ
10169. Чернобыльская радиация в вопросах и ответах 735.41 KB
  Когда в СССР сообщили об аварии на Чернобыльской АЭС Первая информация об аварии прозвучала в программе Время вечером 27 апреля, первая публикация в печати состоялась 28 апреля...
10170. Информационное общество как тип социальной организации 58 KB
  Информационное общество как тип социальной организации. Оценка сущности последней стадии в социальной философии ХХ в. претерпела эволюцию. Первоначально она характеризовалась как постиндустриальное общество Д. Белл технотронное общество З. Бжезинский. В 80х г...